Алгоритм Хаффмана

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

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

Близкая модификация алгоритма используется при сжатии черно-белых изображений (1 бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей груп­пой по стандартизации Международного консультационного комитета по телеграфии и телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущ«*^: Черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд уже, в свою оче­редь, сжимается по Хаффману с фиксированной таблицей.

Определение. Набор идущих подряд точек изображения одного цвета называется серией. Длина этого набора точек называется длиной серии.

В таблицах, приведенных ниже (табл. 1.1 и 1.2), заданы два вида кодов:

■ коды завершения серий - заданы с 0 до 63 с шагом 1;

■ составные (дополнительные) коды - заданы с 64 до 2560 с шагом 64.

Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 0. На­пример, последовательность длин серий 0,3, 556, 10,... означает, что в этой строке изображения идут сначала 3 черные точки, затем 556 белых, затем 10 черных и т. д.

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

Алгоритм компрессии выглядит так:

for (по всем строкам изображения) {

Преобразуем строку в набор длин серий; for(по всем сериям) { if(серия белая) { L= длина серии;

while(L > 2623) { // 2623=2560+63 L=L-2560;

ЗаписатьБелыйКодДля(2560); }

if(L > 63) {

Ь2=МаксимальныйСостКодМеньшеЪ(L) ; L=L-L2;

ЗаписатьБелыйКодДля(L2); } ЗаписатьБелыйКодДля(L) ;

//Это всегда код завершения }

else {

[Код, аналогичный белой серии,

с той разницей, что записываются черные коды] ) }

// Окончание строки изображения }

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

В терминах регулярных выражений мы получим для каждой строки на­шего изображения (достаточно длинной, начинающейся с белой точки) вы­ходной битовый поток вида:

((<Б-2560>)*[<Б-сст.>]<Б-зв>(<Ч-2560>)*[<Ч-сст>]<Ч-зв.>)⁺

[(<Б-2560>)*[<Б-сст>]<Б-зв>]

где ()* - повтор 0 или более раз; ()*•- повтор 1 или более раз; [] - включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0хЧ-ЗхБ-512хБ-44хЧ-10>, или, согласно таблице, 001101011001100101001011 №0000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т. е. степень сжатия составляет примерно 17 раз.

Эч Упражнение. Во сколько раз увеличится размер файла в худшем случае? По­чему? (Приведенный в характеристиках алгоритма ответ не является полным, поскольку возможны больиие значения худшей степени сжатия. Найдите их.)

Заметим, что единственное "сложное" выражение в нашем алгоритме: Ь2=МаксимальныйДопКодМеньшеЦЬ) - на практике работает очень про­сто: L2=(L»6)*64, где » - побитовый сдвиг L влево на 6 бит (можно сде­лать то же самое за одну побитовую операцию & - логическое И).

сЭч Упражнение. Дана строка изображения, записанная в виде длин серий - 442, 2, 56, 3, 23, 3,104,1, 94.1, 231, размером 120 байт ((442+2+..+231)/8). Подсчи­тать степень сжатия этой отроки алгоритмом CCITT Group 3.

Табл. 1.1 и 1.2 построены с помощью классического алгоритма Хаффма-на (отдельно для длин черных и белых серий). Значения вероятностей появ­ления для конкретных длин серий были получены путем анализа большого количества факсимильных изображений.

Таблица 1.1. Коды завершения

Таблица 1.2. Составные коды

Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Степени сжатия: лучшая стремится в пределе к 213.(3), средняя 2, в худшем случае увеличивает файл в 5 раз.

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

Симметричность: близка к единице.

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