Метод Хафмана

Груповое сжатие

Одним из простейших методов сжатия изображений является алгоритм RLE (Run Length Encoding – кодирование с переменной длиной строки). Основной идеей этого метода является поиск одинаковых пикселов в одной строке. Найденные цепочки одинаковых элементов заменяются на пары (счетчик повторений, значение), что в определенных случаях существенно уменьшает избыточность данных.

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

Существует много схем группового сжатия, одну из которых можно проиллюстрировать следующим образом:

Входной поток данных:
17 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 3 67 0 0 8

Поток данных после кодирования:
17 8 54 0 3 97 5 16 0 1 45 23 0 5 3 67 0 2 8

Чаще всего для кодирования используется схема, которая называется PackBits. По аналогии с хранением отрицательных чисел, каждые 7 бит исходных данных заменяются в результате на 8 бит. Дополнительный девятый бит интерпретируется как флаг сжатия. Например:

Входные данные: 1,2,3,4,2,2,2,2,4

Данные после кодирования: 1,2,3,4,2,&3,4.

Принцип: Последовательности повторяющихся значений цвета заменяются его значением и количеством повторений.

Форматы: BMP, TIFF, GIF

Коэффициент сжатия: 2

Этот метод назван в честь его разработчика (1950). Алгоритм основан на том предположении, что некоторые значения сигнала встречаются чаще других. Если проанализировать гистограммы изображений, то можно в этом убедиться. Этот факт можно использовать для сжатия изображений. Использовать для хранения значений интенсивности, которые встречаются чаще, меньшее число бит чем на само значение. Главная проблема в том, чтобы отделять одно значение от другого. Ведь на разные значения отводится разное количество бит. Метод сжатия Хафмана можно проиллюстрировать следующим образом:

Входной поток данных: C E G A D F B E A

Поток данных после кодирования: 0010 0001 000011 1 0011 000010 01 0001 1)

Группировка по байтам: (0010 0001) (000011 1 0) (011 00001) (0 01 00 1 0 1)

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

Этот метод иногда используется в усложненной форме, когда кодируется не одно значение, а последовательности значений. Другая модификация метода – подвергнуть коды Хафмана групповому сжатию.

Форматы: TIFF, GIF

Коэффициент сжатия: 3