Алгоритмы сжатия изображений

Разбить на страницы

Показывать лекцию целиком

Рекурсивный (волновой) алгоритм

Английское название рекурсивного сжатия - wavelet. На русский язык оно переводится как волновое сжатие, как сжатие с использованием всплесков, а в последнее время и калькой вэйвлет-сжатие. Этот вид архивации известен довольно давно и напрямую исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков. Степень сжатия задается и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется "лестничный эффект" - ступеньки разной яркости размером в несколько пикселов.

Идея алгоритма заключается в том, что мы сохраняем в файл разницу - число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.

Так два числа $${\rm{a}}_{{\rm{2i}}} $$ и $${\rm{a}}_{{\rm{2i + 1}}}$$ всегда можно представить в виде $${\rm{b}}^{\rm{1}} _{\rm{i}} {\rm{ = (a}}_{{\rm{2i}}} {\rm{ + a}}_{{\rm{2i}}} _{{\rm{ + 1}}} {\rm{)/2}} $$ и $${\rm{b}}^{\rm{2}} _{\rm{i}} {\rm{ = (a}}_{{\rm{2i}}} {\rm{ - a}}_{{\rm{2i + 1}}} {\rm{)/2}} $$. Аналогично последовательность $${\rm{a}}_{\rm{i}}$$ может быть попарно переведена в последовательность $${\rm{b}}^{{\rm{1}}{\rm{,2}}} _{\rm{i}} $$.

Разберем конкретный пример: пусть мы сжимаем строку из 8 значений яркости пикселов ( $${\rm{a}}_{\rm{i}}$$ ): (220, 211, 212, 218, 217, 214, 210, 202). Мы получим следующие последовательности $${\rm{b}}^{\rm{1}} _{\rm{i}}$$, и $${\rm{b}}^{\rm{2}} _{\rm{i}}$$ : (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим, что значения $${\rm{b}}^{\rm{2}} _{\rm{i}} $$ достаточно близки к 0. Повторим операцию, рассматривая $${\rm{b}}^{\rm{1}} _{\rm{i}} $$ как $${\rm{a}}_{\rm{i}}$$. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

Заметим, что мы применяли наше преобразование к цепочке только два раза. Реально мы можем позволить себе применение wavelet - преобразования 4-6 раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных степеней сжатия.

Упражнение: Мы восстановили из файла цепочку (215, 211) (0, 5) (5, -3, 2, 4) (см. пример). Постройте строку из восьми значений яркости пикселов, которую воссоздаст алгоритм волнового сжатия.

Алгоритм для двумерных данных реализуется аналогично. Если у нас есть квадрат из 4 точек с яркостями $${\rm{a}}_{{\rm{2i}}{\rm{,2j}}} {\rm{, a}}_{{\rm{2i + 1}}{\rm{, 2j}}} {\rm{, a}}_{{\rm{2i}}{\rm{, 2j + 1}}} {\rm{, и a}}_{{\rm{2i + 1}}{\rm{, 2j + 1}}} ,$$ то

$$ b_{i,j}^1 = (a_{2i,2j} + a_{2i + 1,2j} + a_{2i,2j + 1} + a_{2i + 1,2j + 1} )/4 \\ b_{i,j}^2 = (a_{2i,2j} + a_{2i + 1,2j} - a_{2i,2j + 1} - a_{2i + 1,2j + 1} )/4 \\ b_{i,j}^3 = (a_{2i,2j} - a_{2i + 1,2j} + a_{2i,2j + 1} - a_{2i + 1,2j + 1} )/4 \\ b_{i,j}^4 = (a_{2i,2j} - a_{2i + 1,2j} - a_{2i,2j + 1} + a_{2i + 1,2j + 1} )/4 $$

(см. рис. 7.1)

(рис 7.1)

Используя эти формулы, мы для изображения 512х512 пикселов получим после первого преобразования 4 матрицы размером 256х256 элементов: (рис. 7.2)

(рис 7.2)

В первой, как легко догадаться, будет храниться уменьшенная копия изображения. Во второй - усредненные разности пар значений пикселов по горизонтали. В третьей - усредненные разности пар значений пикселов по вертикали. В четвертой - усредненные разности значений пикселов по диагонали. По аналогии с двумерным случаем мы можем повторить наше преобразование и получить вместо первой матрицы 4 матрицы размером 128х128. Повторив наше преобразование в третий раз, мы получим в итоге: 4 матрицы 64х64, 3 матрицы 128х128 и 3 матрицы 256х256. На практике при записи в файл, значениями, получаемыми в последней строке $$b_{i,j}^4,$$ обычно пренебрегают (сразу получая выигрыш примерно на треть размера файла - 1- 1/4 - 1/16 - 1/64...).

К достоинствам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного "проявления" изображения при передаче изображения по сети. Кроме того, поскольку в начале изображения мы фактически храним его уменьшенную копию, упрощается показ "огрубленного" изображения по заголовку.

В отличие от JPEG и фрактального алгоритма данный метод не оперирует блоками, например, 8х8 пикселов. Точнее, мы оперируем блоками 2х2, 4х4, 8х8 и т.д. Однако за счет того, что коэффициенты для этих блоков мы сохраняем независимо, мы можем достаточно легко избежать дробления изображения на "мозаичные" квадраты.

Характеристики волнового алгоритма:

Степень: 2-200 (Задается пользователем).

Класс изображений: Как у фрактального и JPEG.

Симметричность: ~1.5

Характерные особенности: Кроме того, при высокой степени сжатия изображение распадается на отдельные блоки.

Алгоритм JPEG 2000

Алгоритм JPEG-2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года. Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG заключаются в следующем:

Лучшее качество изображения при сильной степени сжатия. Или, что то же самое, большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.

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

Основной алгоритм сжатия заменен на wavelet. Помимо указанного повышения степени сжатия это позволило избавиться от 8-пиксельной блочности, возникающей при повышении степени сжатия. Кроме того, плавное проявление изображения теперь изначально заложено в стандарт (Progressive JPEG, активно применяемый в Интернет, появился много позднее JPEG).

Для повышения степени сжатия в алгоритме используется арифметическое сжатие. Изначально в стандарте JPEG также было заложено арифметическое сжатие, однако позднее оно было заменено менее эффективным сжатием по Хаффману, поскольку арифметическое сжатие было защищено патентами. Сейчас срок действия основного патента истек, и появилась возможность улучшить алгоритм.

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

Поддержка сжатия однобитных (2-цветных) изображений. Для сохранения однобитных изображений (рисунки тушью, отсканированный текст и т.п.) ранее повсеместно рекомендовался формат GIF, поскольку сжатие с использованием ДКП весьма неэффективно к изображениям с резкими переходами цветов. В JPEG при сжатии 1-битная картинка приводилась к 8-битной, т.е. увеличивалась в 8 раз, после чего делалась попытка сжимать, нередко менее чем в 8 раз. Сейчас можно рекомендовать JPEG 2000 как универсальный алгоритм.

На уровне формата поддерживается прозрачность. Плавно накладывать фон при создании WWW страниц теперь можно будет не только в GIF, но и в JPEG 2000. Кроме того, поддерживается не только 1 бит прозрачности (пиксел прозрачен/непрозрачен), а отдельный канал, что позволит задавать плавный переход от непрозрачного изображения к прозрачному фону.

Кроме того, на уровне формата поддерживаются включение в изображение информации о копирайте, поддержка устойчивости к битовым ошибкам при передаче и широковещании, можно запрашивать для декомпрессии или обработки внешние средства (plug-ins), можно включать в изображение его описание, информацию для поиска и т.д.

Идея алгоритма

Базовая схема JPEG-2000 (рис. 7.3) очень похожа на базовую схему JPEG. Отличия заключаются в следующем:

Вместо дискретного косинусного преобразования ( DCT ) используется дискретное вэйвлет-преобразование ( DWT ).

Вместо кодирования по Хаффману используется арифметическое сжатие.

В алгоритм изначально заложено управление качеством областей изображения.

Не используется явно дискретизация компонент U и V после преобразования цветовых пространств, поскольку при DWT можно достичь того же результата, но более аккуратно.

(рис 7.3) Конвейер операций, используемый в алгоритме JPEG-2000

Рассмотрим алгоритм по шагам.

Шаг 1.

В JPEG-2000 предусмотрен сдвиг яркости ( DC level shift ) каждой компоненты ( RGB ) изображения перед преобразованием в YUV. Это делается для выравнивания динамического диапазона (приближения к 0 гистограммы частот), что приводит к увеличению степени сжатия. Формулу преобразования можно записать как:

$$I'(x,y) = I(x,y) - 2^{ST - 1} $$

Значение степени ST для как каждой компоненты R, G и В свое (определяется при сжатии компрессором). При восстановлении изображения выполняется обратное преобразование:

$$I'(x,y) = I(x,y) + 2^{ST - 1} $$

Шаг 2.

Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную ( Red ), зеленую ( Green ) и синюю ( Blue ) составляющие цвета точки, в цветовое пространство YUV. Этот шаг аналогичен JPEG (см. матрицы преобразования в описании JPEG), за тем исключением, что кроме преобразования с потерями предусмотрено также и преобразование без потерь. Его матрица выглядит так:

$$\left| \begin{array}{c} Y \\ U \\ V \\ \end{array} \right| = \left( \begin{array}{c} {\left\lfloor {{{{\rm{R}} + {\rm{2G}} + {\rm{B}}} \over {\rm{4}}}} \right\rfloor } \\ R-G \\ B-G \\ \end{array} \right) $$

Обратное преобразование осуществляется с помощью обратной матрицы:

$$\left| \begin{array}{c} R \\ G \\ B \\ \end{array} \right| = \left( \begin{array}{c} U+G \\ Y - {\left\lfloor {{{\rm{U}} + {\rm{V}}} \over {\rm{4}}}} \right\rfloor } \\ V+G \\ \end{array} \right) $$

Шаг 3.

Дискретное wavelet преобразование ( DWT ) также может быть двух видов - для случая сжатия с потерями и для сжатия без потерь. Его коэффициенты задаются таблицами, приведенными ниже. Для сжатия с потерями коэффициенты представлены в табл. 7.1 и табл. 7.2

Коэффициенты при упаковке
i	Низкочастотные коэффициенты $${\rm{h}}_{\rm{L}} {\rm{(i)}}$$	Высокочастотные коэффициенты $${\rm{h}}_{\rm{H}} {\rm{(i)}}$$
0	1.115087052456994	0.6029490182363579
±1	0.5912717631142470	-0.2668641184428723
±2	-0.05754352622849957	-0.07822326652898785
±3	-0.09127176311424948	0.01686411844287495
±4	0	0.02674875741080976
Другие i	0	0

Коэффициенты при распаковке
i	Низкочастотные коэффициенты $${\rm{g}}_{\rm{L}} {\rm{(i)}}$$	Высокочастотные коэффициенты $${\rm{g}}_{\rm{H}} {\rm{(i)}}$$
0	0.6029490182363579	1.115087052456994
±1	-0.2668641184428723	0.5912717631142470
±2	-0.07822326652898785	-0.05754352622849957
±3	0.01686411844287495	-0.09127176311424948
±4	0.02674875741080976	0
Другие i	0	0

Для сжатия без потерь коэффициенты представлены в табл. 7.3

	При упаковке		При распаковке
i	Низкочастотные коэффициенты $${\rm{h}}_{\rm{L}} {\rm{(i)}}$$	Высокочастотные коэффициенты $${\rm{h}}_{\rm{H}} {\rm{(i)}}$$	Низкочастотные коэффициенты $${\rm{g}}_{\rm{L}} {\rm{(i)}}$$	Высокочастотные коэффициенты $${\rm{g}}_{\rm{H}} {\rm{(i)}}$$
0	6/8	1	1	6/8
±1	2/8	-1/2	1/2	-2/8
±2	-1/8	0	0	-1/8

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

$$y_{output} (2n) = \sum\limits_{j = 0}^{N - 1} {x_{input} (j) \cdot h_H (j - 2n)} $$

$$y_{output} (2n + 1) = \sum\limits_{j = 0}^{N - 1} {x_{input} (j) \cdot h_L (j - 2n - 1)} $$

Поскольку большинство $${\rm{h}}_{\rm{L}} {\rm{(i)}}$$, кроме окрестности i=0, равны 0, то можно переписать приведенные формулы с меньшим количеством операций. Для простоты рассмотрим случай сжатия без потерь.

$$y_{out} (2n) = {{ - x_{in} (2n - 1) + 2 \cdot x_{in} (2n) + 6 \cdot x_{in} (2n + 1) + 2 \cdot x_{in} (2n + 2) - x_{in} (2n + 3)} \over 8} $$

$$y_{out} (2n + 1) = - {{x_{in} (2n)} \over 2} + x_{in} (2n + 1) - {{x_{in} (2n + 2)} \over 2} $$

Легко показать, что данную запись можно эквивалентно переписать, уменьшив еще втрое количество операций умножения и деления (однако теперь необходимо будет подсчитать сначала все нечетные y ). Добавим также операции округления до ближайшего целого, не превышающего заданное число а, обозначаемые как $$\left\lfloor a \right\rfloor $$:

$$y_{out} (2n + 1) = x_{in} (2n + 1) - \left\lfloor {{{x_{in} (2n) + x_{in} (2n + 2)} \over 2}} \right\rfloor $$

$$y_{out} (2n) = x_{in} (2n) + \left\lfloor {{{y_{out} (2n - 1) + y_{out} (2n + 1) + 2} \over 4}} \right\rfloor $$

Упражнение: Самостоятельно уменьшите количество операций для случая без потерь.

Рассмотрим на примере, как работает данное преобразование. Для того, чтобы преобразование можно было применять к крайним пикселам изображения, оно симметрично достраивается в обе стороны на несколько пикселов, как показано на рис. 7.4. В худшем случае (сжатие с потерями) нам необходимо достроить изображение на 4 пиксела.

(рис 7.4) Симметричное расширение изображения (яркости АБ…Е) по строке вправо и влево

Пусть мы преобразуем строку из 10 пикселов. Расширим ее значения вправо и влево и применим DWT преобразование:

Получившаяся строка 1, 0, 3, 1, 11, 4, 13, -2, 8, -5 и является цепочкой, однозначно задающей исходные данные. Совершив аналогичные преобразования с коэффициентами для распаковки, приведенными выше в таблице, получим необходимые формулы:

$$x_{out} (2n) = y_{out} (2n) - \left\lfloor {{{y_{out} (2n - 1) + y_{out} (2n + 1) + 2} \over 4}} \right\rfloor $$

$$x_{out} (2n + 1) = y_{out} (2n + 1) + \left\lfloor {{{x_{out} (2n) + x_{out} (2n + 2)} \over 2}} \right\rfloor $$

Упражнение: Докажите, что во всех случаях округления мы будем получать одинаковые входную и выходную цепочки.

Легко проверить (используя преобразование упаковки), что значения на концах строк в yout также симметричны относительно n =0 и 9. Воспользовавшись этим свойством, расширим нашу строку вправо и влево и применим обратное преобразование:

Как видим, мы получили исходную цепочку ( $${\rm{x}}_{{\rm{in}}} {\rm{ = x}}_{{\rm{out}}} $$ ).

Упражнение: Примените прямое и обратное DWT -преобразования к цепочке из 10 байт:

121, 107, 98, 102, 145, 182, 169, 174, 157, 155.

Далее к строке применяется чересстрочное преобразование, суть которого заключается в том, что все четные коэффициенты переписываются в начало строки, а все нечетные - в конец. В результате этого преобразования в начале строки формируется "уменьшенная копия" всей строки (низкочастотная составляющая), а в конце строки - информация о колебаниях значений промежуточных пикселов (высокочастотная составляющая).

Это преобразование применяется сначала ко всем строкам изображения, а затем ко всем столбцам изображения. В результате изображение делится на 4 квадранта (примеры смотрите в описании рекурсивного сжатия). В первом квадранте будет сформирована уменьшенная копия изображения, а в остальных трех - высокочастотная информация. После чего преобразование повторно применяется уже только к первому квадранту изображения по тем же правилам (рис. 7.5).

(рис 7.5)

Для корректного сохранения результатов под данные 2 и 3 квадрантов выделяется на один бит больше, а под данные 4-го квадранта - на 2 бита больше. Т.е. если исходные данные были 8-битные, то на 2 и 3 квадранты нужно 9 бит, а на 4-й - 10, независимо от уровня применения DWT. При записи коэффициентов в файл можно использовать иерархическую структуру DWT, помещая коэффициенты преобразований с большего уровня в начало файла. Это позволяет получить "изображение для предварительного просмотра", прочитав небольшой участок данных из начала файла, а не распаковывая весь файл, как это приходилось делать при сжатии изображения целиком. Иерархичность преобразования может также использоваться для плавного улучшения качества изображения при передаче его по сети.

Шаг 4.

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

Шаг 5.

Для сжатия получающихся массивов данных в JPEG 2000 используется вариант арифметического сжатия, называемый MQ-кодер, прообраз которого ( QM-кодер ) рассматривался еще в стандарте JPEG, но реально не использовался из-за патентных ограничений. Подробнее об алгоритме арифметического сжатия читайте в соответствующей главе раздела.

Области повышенного качества

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

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

(рис 7.6) Локальное улучшение качества областей изображения

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

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

Такой подход логично применять, если:

Для приложения должна быть критична (максимальна) степень сжатия, причем настолько, что возможен индивидуальный подход к каждому изображению

Изображение сжимается один раз, а разжимается множество раз

В качестве примеров приложений, удовлетворяющим этим ограничениям, можно привести практически все мультимедийные продукты на CD-ROM. И для CD-ROM энциклопедий, и для игр важно записать на диск как можно больше информации, а графика, как правило, занимает до 70% всего объема диска. При этом технология производства дисков позволяет сжимать каждое изображение индивидуально, максимально повышая степень сжатия.

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

В JPEG-2000 используется однобитное изображение-маска, задающее повышение качества в данной области изображения. Поскольку за качество областей у нас отвечают коэффициенты DWT преобразования во 2, 3 и 4 квадрантах, то маска преобразуется таким образом, чтобы указывать на все коэффициенты, соответствующие областям повышения качества (рис. 7.7):

(рис 7.7) Преобразование маски области повышения качества для обработки DWT коэффициентов

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

Характеристики алгоритма JPEG-2000:

Степень сжатия: 2-200 (Задается пользователем). Возможно сжатие без потерь.

Класс изображений: Полноцветные 24-битные изображения. Изображения в градациях серого без резких переходов цветов (фотографии). 1-битные изображения.

Симметричность: 1-1,5

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

Заключение

В заключение рассмотрим таблицы (7.4 и 7.5), в которых сводятся воедино параметры различных алгоритмов сжатия изображений, рассмотренных нами выше.

Алгоритм	Особенности изображения, за счет которых происходит сжатие
`RLE`	Подряд идущие одинаковые цвета: 2 2 2 2 2 2 15 15 15
`LZW`	Одинаковые подцепочки: 2 3 15 40 2 3 15 40
`Хаффмана`	Разная частота появления цвета: 2 2 3 2 2 4 3 2 2 2 4
`CCITT-3`	Преобладание белого цвета в изображении, большие области, заполненные одним цветом
`Рекурсивный`	Плавные переходы цветов и отсутствие резких границ
`JPEG`	Отсутствие резких границ
`Фрактальный`	Подобие между элементами изображения

Алгоритм	К-ты сжатия	Симметричность по времени	На что ориентирован	Потери	Размерность
`RLE`	32, 2, 0.5	1	3,4-х битные	Нет	1D
`LZW`	1000, 4, 5/7	1.2-3	1-8 битные	Нет	1D
`Хаффмана`	8, 1.5, 1	1-1.5	8 битные	Нет	1D
`CCITT-3`	213(3), 5, 0.25	~1	1-битные	Нет	1D
`JBIG`	2-30 раз	~1	1-битные	Нет	2D
`Lossless JPEG`	2 раза	~1	24-бит. сер.	Нет	2D
`Рекурсивное сжатие`	2-200 раз	1.5	24-битные, серые	Да	2D
`JPEG`	2-200 раз	~1	24-битные, сер.	Да	2D
`Фрактальный`	2-2000 раз	1000-10000	24-бит. сер.	Да	2.5D

В приведенной таблице отчетливо видны тенденции развития алгоритмов графики последних лет:

ориентация на фотореалистичные изображения с 16 миллионами цветов (24 бита);

использование сжатия с потерями, возможность за счет потерь регулировать качество сжатых изображений;

использование избыточности изображений в двух измерениях;

появление существенно несимметричных алгоритмов;

увеличивающаяся степень сжатия изображений.

Вопросы для самоконтроля

В чем разница между алгоритмами с потерей информации и без потери информации?

Приведите примеры мер потери информации и опишите их недостатки.

За счет чего сжимает изображения алгоритм JPEG?

В чем заключается идея фрактального алгоритма компрессии?

В чем заключается идея рекурсивного (волнового) сжатия?

Можно ли применять прием перевода в другое цветовое пространство алгоритма JPEG? в других алгоритмах компрессии?

Сравните приведенные в этой главе алгоритмы сжатия изображений.

Различия между форматом и алгоритмом

Напоследок несколько замечаний относительно разницы в терминологии, путаницы при сравнении рейтингов алгоритмов и т.п.

Посмотрите на краткий перечень форматов, достаточно часто используемых на PC, Apple и UNIX платформах: ADEX, Alpha Microsystems BMP, Autologic, AVHRR, Binary Information File (BIF), Calcomp CCRF, CALS, Core IDC, Cubicomp PictureMaker, Dr. Halo CUT, Encapsulated PostScript, ER Mapper Raster, Erdas LAN/GIS, First Publisher ART, GEM VDI Image File, GIF, GOES, Hitachi Raster Format, PCL, RTL, HP-48sx Graphic Object (GROB), HSI JPEG, HSI Raw, IFF/ILBM, Img Software Set, Jovian VI, JPEG/JFIF, Lumena CEL, Macintosh PICT/PICT2, MacPaint, MTV Ray Tracer Format, OS/2 Bitmap, PCPAINT/Pictor Page Format, PCX, PDS, Portable BitMap (PBM), QDV, QRT Raw, RIX, Scodl, Silicon Graphics Image, SPOT Image, Stork, Sun Icon, Sun Raster, Targa, TIFF, Utah Raster Toolkit Format, VITec, Vivid Format, Windows Bitmap, WordPerfect Graphic File, XBM, XPM, XWD.

В оглавлении вы можете видеть список алгоритмов компрессии. Единственным совпадением оказывается JPEG, а это, согласитесь, не повод, чтобы повсеместно использовать слова "формат" и "алгоритм компрессии" как синонимы (что, увы, можно часто наблюдать).

Между этими двумя множествами нет взаимно однозначного соответствия. Так, различные модификации алгоритма RLE реализованы в огромном количестве форматов. В том числе в TIFF, BMP, PCX. И, если в определенном формате какой-либо файл занимает много места, это не означает, что плох соответствующий алгоритм компрессии. Это означат, зачастую лишь то, что реализация алгоритма, использованная в этом формате, дает для данного изображения плохие результаты. Не более того.

В то же время многие современные форматы поддерживают запись с использованием нескольких алгоритмов архивации либо без использования архивации. Например, формат TIFF 6.0 может сохранять изображения с использованием алгоритмов RLE-PackBits, RLE-CCITT, LZW, Хаффмана с фиксированной таблицей, JPEG, а может сохранять изображение без архивации. Аналогично форматы BMP и TGA позволяют сохранять файлы как с использованием алгоритма компрессии RLE (разных модификаций!), так и без использования оной.

Вывод 1: Для многих форматов, говоря о размере файлов, необходимо указывать, использовался ли алгоритм компрессии и если использовался, то какой.

Можно пополнить перечень ситуаций некорректного сравнения алгоритмов. При сохранении абсолютно черного изображения в формате 1000х1000х256 цветов в формате BMP без компрессии мы получаем, как и положено, файл размером чуть более 1000000 байт, а при сохранении с компрессией RLE, можно получить файл размером 64 байта. Это был бы превосходный результат - сжатие в 15 000 раз(!), если бы к нему имела отношение компрессия. Дело в том, что данный файл в 64 байта состоит только из заголовка изображения, в котором указаны все его данные. Несмотря на то, что такая короткая запись изображения стала возможна именно благодаря особенности реализации RLE в BMP, еще раз подчеркнем, что в данном случае алгоритм компрессии даже не применялся. И то, что для абсолютно черного изображения 4000х4000х256 мы получаем коэффициент сжатия 250 тысяч раз, совсем не повод для продолжительных эмоций по поводу эффективности RLE. Кстати - данный результат возможен лишь при определенном положении цветов в палитре и далеко не на всех программах, которые умеют записывать BMP с архивацией RLE (однако все стандартные средства, в т.ч. средства системы Windows, читают такой сжатый файл нормально).

Всегда полезно помнить, что на размер файла оказывают существенное влияние большое количество параметров (вариант реализации алгоритма, параметры алгоритма (как внутренние, так и задаваемые пользователем), порядок цветов в палитре и многое другое). Например, для абсолютно черного изображения 1000х1000х256 градаций серого в формате JPEG с помощью одной программы при различных параметрах всегда получался файл примерно в 7 килобайт. В то же время, меняя опции в другой программе, я получил файлы размером от 4 до 68 Кб (всего-то на порядок разницы). При этом декомпрессированное изображение для всех файлов было одинаковым - абсолютно черный квадрат (яркость 0 для всех точек изображения).

Дело в том, что даже для простых форматов одно и то же изображение в одном и том же формате с использованием одного и того же алгоритма архивации можно записать в файл несколькими корректными способами. Для сложных форматов и алгоритмов архивации возникают ситуации, когда многие программы сохраняют изображения разными способами. Такая ситуация, например, сложилась с форматом TIFF (в силу его большой гибкости). Долгое время по-разному сохраняли изображения в формат JPEG, поскольку соответствующая группа ISO (Международной Организации по Стандартизации) подготовила только стандарт алгоритма, но не стандарт формата. Сделано так было для того, чтобы не вызывать "войны форматов". Абсолютно противоположное положение сейчас с фрактальной компрессией, поскольку есть стандарт "де-факто" на сохранение фрактальных коэффициентов в файл (стандарт формата), но алгоритм их нахождения (быстрого нахождения!) является технологической тайной создателей программ-компрессоров. В результате для вполне стандартной программы-декомпрессора могут быть подготовлены файлы с коэффициентами, существенно различающиеся как по размеру, так и по качеству получающегося изображения.

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

Вывод 2: Если вы не умеете пользоваться программами архивации или пользуетесь программами, в которых "для простоты использования" убрано управление параметрами алгоритма - не удивляйтесь, почему для отличного алгоритма компрессии в результате получаются большие файлы.

Страницы: