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

Так как в любой графической информации свойственна избыточность, сжатие позволяет значительно уменьшить ее объем [6].

Алгоритмы сжатия можно разбить на два больших класса:

• сжатие с потерями,

• сжатие без потерь.

4.9.1 Сжатие без потерь

Большинство схем сжатия без потерь основано на поиске в растровом изображении повторяющихся пиксельных узоров. Такой узор можно запомнить один раз и впоследствии повторить его необходимое количество раз. Подобные схемы сжатия полностью − пиксел за пикселом − восстанавливают исходное изображение. При этом в исходных данных ничего не отбрасывается и не теряется. Метод сжатия без потерь очень эффективен для растровых рисунков, содержащих большие области однотонной закраски, или повторяющихся растровых узоров. В таких случаях чаще всего достигается коэффициент сжатия 10:1.

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

Метод сжатия RLE (run length encoding) − кодирование с переменной длиной строки. Этот алгоритм является одним из простейших. В основе его принципа действия заложен механизм поиска одинаковых пикселов в одной строке. Алгоритм RLE хорошо работает с изображениями, в которых есть большие одноцветные области и плохо − с фотографиями. В действительности, если фотография детализирована, RLE может даже увеличить размер файла.

Метод сжатия LZW (Lempel-Ziv-Welch). Название алгоритм получил по первым буквам фамилий его разработчиков − Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт. Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, методом поиска повторяющихся цепочек.

В одном из вариантов алгоритма используется четырехкилобайтный словарь, в котором индексы 0-255 отведены для отдельных байтов (символов), а остальные − для последовательностей. Сжимает данные путем поиска одинаковых последовательностей (называемых фразами) во всем файле. Затем выявленные последовательности сохраняются в таблице, где им присваиваются более короткие маркеры (ключи). Например, если в изображении имеются наборы из пурпурного, оранжевого и зеленого пикселов, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7.

Метод LZW, так же как и RLE, лучше работает на однородных участках, свободных от цветового шума. Однако по сравнению с RLE-алгоритмом он более эффективен при сжатии произвольных графических данных, хотя процесс кодирования и распаковки в этом случае происходит медленнее. Коэффициент сжатия для текстов порядка 1:2, а для графики − 1:8.

Коды Хаффмана. Один из классических алгоритмов, известных с 60-х гг., разработан Д.А. Хаффманом (D.A. Huffman). Данный алгоритм использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины и, напротив, встречающимся редко − цепочку большей длины. Для сбора статистики требует двух проходов по изображению. Вот пример кодов Хаффмана. Пусть в исходных данных имеются два символа и известны вероятности появления комбинаций из трех этих символов. Тогда можно поставить в соответствие каждой комбинации определенный код (причем такой, чтобы при последовательной записи кодов их невозможно было перепутать). В результате получим такую таблицу:

Для графики сжатие по Хаффману позволяет уменьшить размер примерно в 1.2-2.5 раза. Этот алгоритм также сжимает данные без потерь. Однако алгоритм Хаффмана оптимален только в тех случаях, когда вероятности появления символов кратны степеням 1/2.