Software & Systems

В настоящее время вейвлетные методы находят широчайшее применение в самых разнообразных прикладных задачах. Одной из таких задач является сжатие изображений. К преимуществам вейвлетных методов можно отнести высокую степень сжатия, простой и изящный способ прогрессивной передачи, возможность заранее указывать размер архива с точностью до байта. В данной статье описывается разработанная автором система для параллельного сжатия изображений EPSILON. Система базируется на вейвлетных преобразованиях [1,2], а также на промышленных стандартах для распараллеливания сложных вычислений.

Благодаря применению вейвлетных методов программа EPSILON имеет отличное соотношение размер–качество и позволяет точно контролировать bit-rate изображения. Другими словами, пользователь может заранее с высокой точностью указать желаемую степень сжатия.

При кодировании данные упорядочиваются особым образом: вначале передается наиболее важная для человеческого восприятия информация, а затем уже малозаметные контуры и детали. Такой способ упорядочения называется прогрессивным. При прогрессивной передаче декодер, получая данные, может постепенно улучшать и уточнять изображение. Это гораздо предпочтительнее, чем наблюдать, как изображение последовательно прорисовывается сверху вниз.

Кроме того, отметим дополнительные характеристики программы EPSILON: поддержка более 30 различных вейвлетных фильтров, огромных изображений (десятки гигабайт), потоков стандарта POSIX, стандарта Message Passing Interface, а также устойчивый к повреждениям формат хранения и открытый исходный код (GNU GPL).

Принцип работы программы

Так как алгоритмы кодирования и декодирования почти симметричны, приведем лишь схему кодирования.

·    Исходное изображение. На вход подается изображение произвольного размера. На выходе получается его сжатое представление, имеющее заранее заданный размер и заданные характеристики.

·    Разбиение изображения на блоки. Поскольку изображение может оказаться очень большим, обрабатывать его необходимо поблочно. Размер и форма блока в значительной степени влияют на производительность и эффективность работы всей системы. Так, увеличение размера блока положительно сказывается на соотношении размер–качество, уменьшает количество служебных данных, выводимых программой с каждым блоком, и уменьшает количество «швов» в изображении, заметных при очень сильном сжатии. Однако эта тенденция довольно быстро сходит на нет. Кроме того, с увеличением размера блока растет и время, необходимое на его обработку. С другой стороны, маленькие блоки быстрее обрабатываются, и при более мелком разбиении повышается устойчивость закодированных данных к повреждениям, но вместе с тем растут и накладные расходы. Программа EPSILON использует квадратные блоки размера 2N либо 2N+1. По умолчанию N=8. Если ширина или высота изображения не кратны размеру блока, изображение отражается относительно своих границ до необходимого размера.

·    Уменьшение граничных искажений. Обработка изображения блоками очень удобна, однако имеет один недостаток: при очень высоких степенях сжатия становятся заметными искажения на стыках блоков. В работе [3] авторы предлагают очень простой и эффективный способ для уменьшения граничных искажений: брать блоки, размер которых нечетный и первый коэффициент разложения низкочастотный (НЧ). Поскольку НЧ и высокочастотные (ВЧ) коэффициенты чередуются, а их общее количество нечетное, последний коэффициент разложения также будет НЧ. Отметим, если размер блока взять равным 2N+1, то требуемые условия будут выполнены на любом уровне вейвлетного разложения. В статье убедительно доказано и подтверждено экспериментально: если по краям сигнала находятся НЧ коэффициенты, граничных искажений становится значительно меньше. Собственные эксперименты также подтверждают выводы авторов статьи. При высоких степенях сжатия применение данного метода действительно уменьшает искажения на стыках блоков – об этом свидетельствуют и визуальная оценка реконструированного изображения, и показатель PSNR.

·    Преобразование цветовых пространств. Наиболее употребительным цветовым пространством для полноцветных изображений является пространство RGB. Однако на практике RGB не очень удобно для сжатия изображений. Поскольку человеческий глаз чувствителен даже к малым изменениям яркости, удобно иметь цветовое пространство, в котором яркость, или светимость (Y), является одним из компонентов. Таковым является пространство YCbCr. Последние две компоненты называются хроматическими. Они выражают цвет в терминах присутствия или отсутствия синего и красного при данном значении светимости. После преобразования все три компоненты сжимаются независимо друг от друга. Причем хроматические компоненты Cb и Cr можно сжимать с гораздо большими потерями, чем компоненту Y. Так, на кодирование компоненты Y программой по умолчанию выделяется 90 % общего битового бюджета, в то время как на компоненты Cb и Cr выделяется всего по 5 %. Эти цифры получены экспериментальным путем и в большинстве случаев дают хорошие результаты. При необходимости программа EPSILON позволяет пользователю самостоятельно распределить битовый бюджет по компонентам изображения.

·    Субвыборка в цветовых каналах. Как уже было сказано, человеческий глаз очень чувствителен даже к малым изменениям яркости, в то время как чувствительность к хроматическим составляющим значительно слабее. Этот факт позволяет нам сжимать хроматические компоненты значительно сильнее яркостной, не опасаясь при этом, что глаз заметит искажения. Во многих стандартах для сжатия цветных изображений и видео цветовые каналы дополнительно прореживаются по вертикали и горизонтали в соответствии с различными схемами. Например, алгоритм JPEG из цветовых каналов Cb и Cr выбирает лишь каждый второй пиксел по горизонтали и вертикали. Таким образом, размер каждой из цветовых компонент уменьшается в четыре раза. При декодировании каждый пиксел заменяется на четыре пиксела с такими же значениями. Таким образом, субвыборка позволяет значительно сократить количество обрабатываемых данных, повышая тем самым общую степень сжатия и скорость работы программы. Стоит отметить, что даже такой грубый прием в большинстве случаев остается незаметным для человеческого восприятия. Программа EPSILON может работать как с прореживанием цветовых каналов, так и без него – выбор остается за пользователем.

·    Вейвлетное преобразование. Центральную роль в описываемом алгоритме сжатия изображений играет вейвлетное преобразование. Задача его – в выделении НЧ и ВЧ составляющих сигнала. Уже давно установлено, что НЧ составляющая более ценна для человеческого восприятия. Таким образом, условно разделив информацию на «более важную» и «менее важную», можно закодировать первую с меньшими потерями, чем вторую. В основном за счет этого и достигается сжатие. Реализуется вейвлетное преобразование путем применения к сигналу каскада из НЧ и ВЧ фильтров. Первые выделяют низкочастотную и подавляют высокочастотную информацию, а вторые – наоборот.

·    Кодирование коэффициентов. После того как изображение пройдет через вейвлетное преобразование, полученные коэффициенты округляются до ближайших целых и кодируются специальным методом. В программе EPSILON для этих целей применяется алгоритм SPECK – Set Partitioned Embedded bloCK coder [4].

Как ни странно это звучит, но основная идея SPECK заключается не в непосредственном сжатии изображения, а в том, чтобы переупорядочить биты коэффициентов его вейвлетного разложения специальным образом. Уже давно установлено, что для человеческого восприятия НЧ компоненты изображения (то есть плавные переходы яркости и цвета) несут гораздо больше информации, чем ВЧ (резкие границы, углы, прямые линии). По сути, на принципе выделения НЧ и ВЧ информации, с последующим подавлением последней, и построены многие технологии сжатия изображений с потерями. Не исключение и SPECK. Используя особенности структуры вейвлетных коэффициентов, алгоритм SPECK переупорядочивает их биты. При этом первые биты будут нести наиболее важную информацию, в то время как последние – лишь незначительные, уточняющие детали.

Такое упорядочение данных часто называют прогрессивным. При прогрессивной передаче изображения декодер, получая очередные порции закодированных данных, может последовательно улучшать и уточнять полученное им изображение. При этом вначале декодером будут прорисованы основные цветовые и яркостные переходы, а уже затем второстепенные контуры и малозаметные детали.

Прогрессивное упорядочение, помимо всего прочего, позволяет точно задавать требуемую степень сжатия. Действительно, можно сохранить лишь требуемое количество первых битов закодированного изображения, а оставшийся «хвост» просто отбросить, так как в нем сравнительно мало информации. Отсюда, собственно, и главная идея: выбрать наиболее важную информацию и передать ее в первую очередь.

·    Мультиплексирование каналов. Как уже было сказано, цветное изображение представляется в виде трех компонент – Y, Cb и Cr, причем кодируются они независимо друг от друга. Если изображение распаковывается и отображается локально, вполне приемлемо сохранить все три потока по очереди отдельно друг от друга. Если же изображение будет передаваться по сети, сохранять потоки по отдельности нецелесообразно. В противном случае пользователь вначале увидит, как прорисовывается черно-белый вариант изображения, а затем будет наблюдать, как изображение наполняется цветом. Для того чтобы изображение при передаче прорисовывалось равномерно по всем каналам, соответствующие битовые потоки необходимо равномерно перемешать (мультиплексировать) в один поток. Разумеется, перемешивать их следует таким образом, чтобы декодер смог затем восстановить исходные данные. Несмотря на то, что мультиплексировать следует три потока, алгоритму достаточно уметь объединять лишь два: его можно применять рекурсивно, рассматривая только что объединенный поток как новый.

·    Маркеры блоков. Для обеспечения хо- рошей масштабируемости системы изображение обрабатывается по блокам. В закодированных данных блочная структура поддерживается при помощи специальных маркеров. Фактически маркеры – это нулевые байты, отделяющие блоки данных друг от друга. Маркеры позволяют декодировать несколько блоков одновременно, перемешивать блоки в произвольном порядке, а также значительно повысить устойчивость закодированных данных к повреждениям. Применение маркеров требует определенной осторожности: если в закодированных данных встретится нулевой байт, декодер по ошибке может принять его за конец блока. Для того чтобы исключить подобную двусмысленность, нулевые байты, не являющиеся маркерами, подвергаются экранированию – то есть замене на возможно более длинную комбинацию ненулевых байтов. Алгоритм экранирования, использованный в программе EPSILON, называется COBS – Consistent Overhead Byte Stuffing [5]. Этот алгоритм гарантирует, что даже в худшем случае расширение данных составит не более 0,4 %, что близко к теоретическому пределу в 0,07 %. Интересно отметить, что у большинства алгоритмов экранирования этот показатель составляет 200 %, то есть в худшем случае каждый байт экранируется двумя байтами.

·    Двухпроходный алгоритм. Поскольку блоки изображения кодируются независимо друг от друга, встает вопрос о распределении битового бюджета между ними. В самом простом случае битовый бюджет делится поровну между всеми блоками. Эта стратегия называется CBR – Constant Bit-Rate. Если изображение имеет примерно одинаковую структуру, CBR работает вполне приемлемо. Однако в большинстве случаев изображение неоднородно: в нем есть как фрагменты с плавными переходами, так и фрагменты со множеством мелких деталей. Для краткости будем называть их «простыми» и «сложными» соответственно. Отметим также, что, чем больше изображение, тем выше шансы, что оно будет неоднородным. Практика показывает: в случае неоднородных изображений алгоритм CBR работает не очень эффективно, так как для адекватной передачи простого блока требуется меньше битов, чем для передачи сложного. Более того, зачастую простые блоки даже не выбирают весь выделенный для них битовый бюджет. Проблема заключается в том, что при использовании стратегии CBR степень искажения у сложных и простых блоков разная, вследствие этого на стыках блоков заметны искажения (швы). Чтобы решить эту проблему и повысить качество кодирования больших неоднородных изображений, применяется стратегия VBR – Variable Bit-Rate. Суть этого метода очень проста: сэкономить битовый бюджет на простых блоках и использовать его для кодирования сложных. Эксперименты показывают, что применение VBR способно существенно поднять качество реконструируемого изображения. Стратегия VBR, однако, проигрывает CBR в скорости: реализация VBR требует двух проходов по изображению. В программе EPSILON пользователь может выбрать любую из двух стратегий.

·    Удаленный просмотр изображения по сети. Блочная структура данных дает возможность наблюдателю удаленно (то есть по сети) просматривать интересующие его фрагменты изображения. Размер самого изображения при этом может на порядки превосходить размер выбранного фрагмента: допустим, это район города на большой спутниковой фотографии. При этом загружаться будут только действительно необходимые данные, что в значительной степени снижает требования к скорости канала передачи данных. Кроме того, благодаря прогрессивному алгоритму кодирования изображение не загружается сверху вниз строка за строкой, а отображается сразу целиком, создавая тем самым эффект постепенного проявления, при котором размытое изображение становится все более и более четким. Этот процесс можно остановить в любой момент, когда будет достигнуто необходимое визуальное качество изображения. Опыты показывают, что даже ничтожно малой части – тысячной доли от размера оригинала – вполне достаточно для того, чтобы составить о нем впечатление.

Параллельная обработка

EPSILON изначально проектировалась как параллельная система. Распараллеливание наиболее удобно на уровне блоков – то есть небольших квадратных фрагментов изображения. Поскольку блоки никак не связаны друг с другом, обрабатывать их можно одновременно. В программе реализованы два подхода к параллельной обработке. Первый подход основан на применении потоков стандарта POSIX. Этот метод отлично подходит для многопроцессорных компьютеров, а также для компьютеров с многоядерными процессорами. Второй основан на применении MPI (Message Passing Interface) – технологии, которая очень широко используется на высокопроизводительных кластерах.

Результаты испытаний кластерной версии

Испытания кластерной версии программы проводились в Научно-исследовательском вычислительном центре МГУ имени М.В. Ломоносова на кластере ANT, конфигурация которого представлена следующим образом.

Количество узлов –            80

Количество ядер –              160

Конфигурация узла –         2xOpteron 2.2 ГГц, 4 Gb RAM

Коммуникационная сеть – Infiniband

Транспортная сеть –           Gigabit Ethernet

Сервисная сеть –                FastEthernet

Пиковая производительность –    704 GFlops

Тестовое изображение (полноцветное изображение размера 3072´2304, сжатие 1:10, фильтр Добеши 9/7) последовательно сжималось и распаковывалось с использованием различного числа процессоров. Результаты замеров приведены в таблице 1.

Таблица 1

Результаты испытаний многопоточной версии

Испытания многопоточной версии программы проводились на сервере, конфигурация которого следующая.

Тип процессора –                    Intel Xeon CPU 3.2 GHz

Количество CPU –                  2

Количество ядер –                  4

Оперативная память –           2 Gb

Жесткий диск –                       SCSI 200 Gb (RAID 5)

Операционная система –        Linux Mandriva 2007

Тестовое изображение последовательно сжималось и распаковывалось с использованием различного числа потоков. Результаты замеров приведены в таблице 2.

Таблица 2

В обоих случаях при увеличении количества потоков с одного до двух получаем почти двухкратное ускорение программы. При увеличении количества потоков сначала до трех, а затем и до четырех также наблюдается определенный рост производительности. Когда количество потоков превышает количество реальных процессоров, рост производительности замедляется. При дальнейшем увеличении количества потоков отмечаем снижение производительности. Данный факт вполне предсказуем и объясняется тем, что количество потоков превышает количество ядер.

Разработанная программа EPSILON обладает отличным соотношением размер–качество и демонстрирует хорошую производительность и масштабируемость как при работе на высокопроизводительном кластере ANT, так и на многопроцессорном сервере. Кроме того, система EPSILON имеет открытый исходный код (GPL) и свободно распространяется через Интернет.

Список литературы

1. ·Симаков А.В. Сжатие изображений при помощи вейвлетных преобразований. // Вест. молодых ученых: Сер. Прикладная математика и механика. – 2004. – Вып. 4. – С. 53–62.
2. · Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: Диалог-МИФИ, 2003.
3. ·Wei J., Pickering M.R., Frater M.R., Arnold J.F., Boman J., Zeng W. Boundary artifact reduction using odd tile lengths and the low pass. first convention (OTLPF). // Proc. of SPIE. Appl. of Digital Image Proc. July 2001.
4. · Asad I., Pearlman W. An embedded and efficient low-complexity hierarchical image coder. // Proc. of SPIE. Visual Comm. and Image Processing 99. 1999. V. 3653, pp. 294–305.
5. · Cheshire S., Baker M. Consistent overhead byte stuffing // IEEE ACM Transactions on Networking. 1999. V. 7, № 2.