3.3. Подходы к сжатию изображений

Методы сжатия изображений обычно разрабатываются для конкретного типа изображений. Здесь перечислены различные подходы к компрессии графических образов. При этом будут обсуждаться только общие принципы. Специфические методы описаны дальше в этой главе (см. также [Salomon 2000]).

Подход 1. Для сжатия двухуровневых изображений. Каждый пиксел такого образа представляется одним битом. Применение принципа сжатия образов к компрессии двухуровневых изображений означает, что непосредственные соседи пиксела Р стремятся совпадать с Р. Поэтому имеет смысл использовать методы кодирования длин серий (RLE) для сжатия таких изображений. Метод сжатия сканирует образ строка за строкой и вычисляет длины последовательных черных и белых пикселов. Длины кодируются кодами переменной длины и записываются в сжатый файл. Примером такого сжатия является факсимильная компрессии (см. § 1.6).

Еще раз подчеркнем, что это всего лишь общий принцип сжатия, конкретные методы могут сильно отличаться друг от друга. Например, метод может сканировать образ по строкам, а может зигзагообразно (см. рис. 3.5.а) или сканировать изображение область за областью с помощью заполняющих их кривых (см. (Salomon 2000]).

Рис. 3.5. (а) Сканирование зигзагом. (b) Распределение Лапласа.

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

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

Кодер вычисляет сколько раз встречался каждый контекст для пиксела цвета с и присваивает контекстам соответствующие вероятности. Если текущий пиксел имеет цвет с и его контекст имеет вероятность р, то кодер может использовать адаптивное арифметическое кодирование для кодирования пиксела с этой вероятностью. Такой подход использован в методе JBIG [Salomon 2000].

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

Подход 3. Расслоить полутоновую картинку на  двухуровневых изображений и каждую сжать с помощью RLE и префиксных кодов. Здесь кажется, что можно применить основной принцип сжатия изображений, но по отношению к каждому отдельному слою полутонового изображения. Однако, это не так, и следующий пример проясняет ситуацию. Представим себе полутоновое изображение с  (то есть, имеем дело с 4-битовыми пикселами, или с 16 градациями серого цвета). Его можно расслоить на 4 двухуровневых изображения. Если два смежных пиксела исходного образа имели величины 0000 и 0001, то они похожи по цвету. Однако два пиксела со значениями 0111 и 1000 также близки на полутоновом изображении (это, соответственно, числа 7 и 8), но они различаются во всех 4 слоях.

Эта проблема возникает, так как в двоичном представлении соседние числа могут отличаться во многих разрядах. Двоичные коды для 0 и 1 отличаются в одном разряде, коды для 1 и 2 различаются в двух разрядах, а коды для 7 и 8 различаются уже во всех четырех битах. Решением этой проблемы может служить разработка специальных последовательностей двоичных кодов, в которых последовательные коды с номерами  и  различались бы ровно на один бит. Примером таких кодов служат рефлексные коды Грея, описанные в § 3.3.1.

Подход 4. Использовать контекст пиксела Р, который состоит из значений нескольких ближайших соседей. Выбираем несколько соседних пикселов, вычисляем среднее значение А их величин и делаем предсказание, что пиксел Р будет равен А. Основной принцип сжатия изображений позволяет считать, что в большинстве случаев мы будем правы, во многих случаях будем почти правы и лишь в немногих случаях будем совершенно неправы. Можно сказать, что в предсказанной величине пиксела Р содержится избыточная информация про Р. Вычислим разность

и присвоим некоторый (префиксный) код переменной длины величине  так, чтобы малым величинам (которые ожидаются часто) соответствовали короткие коды, а большим величинам (которые ожидаются редко) назначались длинные коды. Если значение Р лежит в интервале от 0 до , то значения  попадают в интервал , для чего потребуется  или  кодов.

Экспериментирование с большими числами показывает, что значения  стремятся иметь распределение, близкое к распределению Лапласа (см. рис. 3.5b), которое часто возникает в статистике. Тогда метод сжатия может использовать это распределение для присвоения вероятностей величинам  и весьма эффективно применять арифметическое кодирование для . Этот подход лежит в основе метода сжатия MLP (см. [Salomon 2000]).

Контекст пиксела может состоять из одного или двух его соседей. Однако лучшие результаты получаются, если использовать несколько пикселов, причем каждому пикселу присваивается некоторый вес для вычисления взвешенного среднего: более дальним пикселам присваивается меньший вес. Другое важное рассмотрение касается декодирования. Для декодирования изображения необходимо уметь вычислять контекст до самого пиксела. Это означает, что контекст должен состоять из уже декодированных пикселов. Если изображение сканируется строка за строкой (сверху вниз и слева направо), то контекст может состоять только из пикселов, которые расположены выше и левее данного пиксела.

Подход 5. Сделать преобразование пикселов и кодировать преобразованные значения. Понятие преобразования образа, а также наиболее важные преобразования, используемые при компрессии изображений, будут разобраны в § 3.5. Глава 4 посвящена вейвлетным преобразованиям. Напомним, что компрессия достигается путем удаления или сокращения избыточности. Избыточность изображения образуется за счет корреляции между пикселами, поэтому преобразования, которые делают декорреляцию, одновременно удаляют избыточность. Квантуя преобразованные значения, можно получить эффективное сжатие с частичной потерей информации. Мы хотим преобразовывать величины в независимые, так как для независимых величин легче построить простую модель для их кодирования.

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

Подход 6. Идея этого метода заключается в разделении изображения на три полутоновых и в их независимом сжатии на основании одного из подходов 2, 3 или 4.

Принцип сжатия непрерывно-тоновых изображений гласит, что цвет соседних пикселов мало изменяется, хотя и не обязательно постоянен. Однако близость цветов еще не означает близость величин пикселов. Рассмотрим, например, цветной 12-битовый пиксел, в котором каждая компонента имеет 4 бита. Итак, 12 бит 1000|0100|0000 обозначают пиксел, цвет которого получается смешением 8 единиц красного (около 50%, так как всего их 16), четырех единиц зеленого (около 25%) и совсем без голубого. Представим себе теперь два пиксела со значениями 0011|0101|0011 и 0010|0101|0011. Их цвета весьма близки, поскольку они отличаются только в одной красной компоненте, и там их различие состоит только в одном бите. Однако, если рассмотреть их как 12-битовые числа, то два числа 0011|0101|0011=851 и 0010|0101|0011=595 различаются весьма значительно.

Важная особенность этого подхода состоит в использовании представления цвета в виде яркости и цветности вместо обычного RGB. Эти понятия обсуждаются в § 3.7.1 и в книге [Salomon 2000]. Преимущество этого представления основано на том, что глаз чувствителен к маленьким изменениям яркости, но не цветности. Это позволяет допускать значительную потерю в компоненте цветности, но при этом совершать декодирование без значительного визуального ухудшения качества изображения.

Подход 7. Другие методы требуются для компрессии дискретно-тоновых изображений. Напомним, что такие изображения состоят из больших одноцветных областей, причем каждая область может появляться в нескольких местах образа. Хорошим примером служит содержимое экрана компьютера. Такой образ состоит из текста и пиктограмм (иконок). Каждая буква, каждая пиктограмма занимают некоторую область на экране, причем каждая из этих областей может находиться в разных местах экрана. Возможный способ сжатия такого изображение заключается в его сканировании и обнаружении таких повторяющихся областей. Если область В совпадает с ранее выделенной областью A, то можно сжать В, записав в файл указатель на область А. Примером такого метода служит алгоритм блоковой декомпозиции (FABD, [Salomon 2000]).

Подход 8. Разделение изображения на части (перекрывающиеся или нет) и сжатие их одна за другой. Предположим, что следующая требующая сжатия часть имеет номер 15. Постараемся сравнить ее с уже обработанными частями 1-14. Предположим, что ее можно выразить, например, с помощью комбинации частей 5 (растяжение) и 11 (поворот), тогда достаточно сохранить только несколько чисел, которые описывают требуемую комбинацию, а саму часть 15 можно отбросить. Если часть 15 не удается выразить в виде комбинации прежних частей, то ее придется сохранить в «сыром виде».

Другой подход является основой для различных фрактальных методов сжатия изображений. Здесь применяется основной принцип сжатия изображений, но вместо пикселов выступают части изображения. Этот принцип говорит о том, что «интересные» изображения (то есть те, которые будут сжиматься на практике) обладают некоторой степенью самоподобия. Часть изображения совпадает или близка всему изображению.

Методы сжатия изображений вовсе не ограничиваются перечисленными базисными подходами. В книге [Salomon 2000] обсуждаются методы, которые используют контекстные деревья, марковские цепи, вейвлеты и многое другое. Дополнительно следует упомянуть метод прогрессивного сжатия образов (см. § 3.6), который добавляет еще одно измерение сжатию изображений.

Искусство - это техника передачи сообщений.
Труднее всего передавать образы.
- Клез Тур Олденбург