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

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

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

Сжатие без потерь RLE (Run Length Encoding) LZW (Lempel, Ziv, Welch) Метод Хаффмана (Huffman)

Алгоритм группового кодирования RLE Изображение вытягивается в цепочку байт по строкам растра. Серия повторяющихся величин (значений пиксела) заменяется одной величиной и количеством ее повторений. Abbbbbbbccdddeeee – 1a7b2c3d4e Этот подход хорошо работает с длинными сериями повторяющихся величин, т.е. с изображениями с большими областями постоянной яркости (или цвета). Используется во многих форматах bitmap файлов – TIFF, GEM, PCX и других.

Характеристики RLE Худший, средний, лучший коэффициенты сжатия: 32 – 2 – 0.5 Класс изображений: небольшое количество цветов (деловая и научная графика) Симметричность: 1 Особенности алгоритма: не требует дополнительной памяти при архивации и разархивации, быстро работает.

Алгоритм LZW Метод назван по первым буквам фамилий его разработчиков: Lempel, Ziv, Welch. Сжатие осуществляется за счет одинаковых цепочек байт (шаблонов). Алгоритм создает таблицу кодов, представляющих повторяющиеся пиксельные «узоры», начиная с простой таблицы и формирует более эффективную таблицу по мере своего продвижения – этот алгоритм является адаптивным. Включен в несколько форматов файлов: GIF, TIFF (с правом выбора). (словарный алгоритм)

Характеристики LZW Худший, средний, лучший коэффициенты сжатия:0.7 – 4 –1000 Класс изображений: 8-битные изображения, построенные на компьютере. Симметричность: 1, при оптимальном построении.

Алгоритм Хаффмана Использует частоту появления исходных байт в изображении. При этом более короткие коды используются для часто повторяющихся величин, и наоборот. Присвоения хранятся в таблице перекодировки. Требует двух проходов по изображению. В первый проход создается статистическая модель, т.е. каждой величине ставится в соответствие число ее повторений; во второй проход – кодируются данные. Для кодировки используются алгоритмы построения бинарных деревьев.

Сжатие с потерями JPEG JPEG 2000 (Wavelet) Фрактальное сжатие

Оценка потерь качества Базовая метрика оценки качества сжатия – PSNR (peak-to-peak signal-to-noise ratio) Хорошо работает только на высоком качестве.

Алгоритм JPEG Разработан в 1991 г. группой экспертов в области фотографии (Joint Photographic Expert Group – подразделение в рамках ISO) специально для сжатия 24-битных изображений. Основу алгоритма составляет дискретное косинусное преобразование Фурье (DCT) Оперирует блоками 8 х 8, внутри которых яркость и цвет меняются сравнительно плавно.

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

Характеристики алгоритма JPEG Степень сжатия: (задается пользователем) Класс изображений: полноцветные 24-битные изображения или изображения в градациях серого без резких переходов цветов (фотографии) Симметричность: 1 Характерные особенности: эффект облачности при высоких степенях сжатия и «ореолы» вокруг резких вертикальных и горизонтальных границ.

ПримерJPEG Фотография заката в формате JPEG с уменьшением степени сжатия слева направо

Сравнение JPEG и JPEG2000 Большая степень сжатия при том же качестве для высоких степеней сжатия Поддержка кодирования отдельных областей с лучшим качеством DCT заменено на DWT (wavelet-преобразование), что позволило избежать облачности и достичь плавного проявления изображения Вместо кодирования по методу Хаффмана используется более эффективное арифметическое кодирование Поддержка сжатия без потерь Поддержка сжатия 1-битных изображений Поддержка прозрачности при помощи отдельного канала

JPEG и JPEG2000 при сжатии в 30 раз

Форматы графических файлов BMP (DIB, Device Independent Bitmap) JPEG GIF (Graphics Interchange Format) TIFF (Tag Image File Format) EPS (Encapsulated PostScript) CGM (Computer Graphics Metafile) DXF (Drawing Interchange Format) PNG (Portable Network Graphics)

Продолжение