Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW)
Данный алгоритм отличают высокая скорость работы как при упаковке,
так и при распаковке, достаточно скромные требования к памяти и простая
аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. Существует довольно большое семейство LZW - подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек [7].
Коэффициенты сжатия: 1/1000, 1/4, 7/5. Коэффициент 1/1000 достигается
только на одноцветных изображениях размером больше 4 Мб. Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. Сжатие обеспечивается за счет одинаковых подцепочек в потоке. Алгоритм является почти симметричным, при условии оптимальной реализации операции поиска строки в таблице.
LZW универсален - именно его варианты используются в обычных
архиваторах. Он реализован в форматах GIF, TIFF и TGA.
Алгоритм Хаффмана с фиксированной таблицей CCITTGroup 3
Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.
Определение: Набор идущих подряд точек изображения одного цвета называетсясерией.Длина этого набора точек называется длиной серии.
В таблице, приведенной ниже, заданы два вида кодов:
- Коды завершения серий - заданы с 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) { L2=МаксимальныйСостКодМеньшеL(L); L=L-L2; ЗаписатьБелыйКодДля(L2); } ЗаписатьБелыйКодДля(L); //Это всегда код завершения } else { [Код аналогичный белой серии, с той разницей, что записываются черные коды] } } // Окончание строки изображения }
Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.
В терминах регулярных выражений мы получим для каждой строки нашего изображения (достаточно длинной, начинающейся с белой точки) выходной битовый поток вида:
((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>)+
[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]
Где ()* - повтор 0 или более раз, ()+.- повтор 1 или более раз, [] - включение 1 или 0 раз.
Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0><Ч-3><Б-512><Б-44><Ч-10>, или, согласно таблице, 001101011001100101001011010000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз.
| Изображение, для которого очень выгодно применение алгоритма CCITT-3. (Большие области заполнены одним цветом).
| Изображение, для которого менее выгодно применение алгоритма CCITT-3. (Меньше областей, заполненных одним цветом. Много коротких 'черных' и 'белых' серий).
|
| Заметим, что единственное 'сложное' выражение в нашем алгоритме:L2=МаксимальныйДопКодМеньшеL(L) - на практике работает очень просто: 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.
Приведенные ниже таблицы построены с помощью классического алгоритма Хаффмана (отдельно для длин черных и белых серий). Значения вероятностей появления для конкретных длин серий были получены путем анализа большого количества факсимильных изображений.
Таблица кодов завершения:
| Вопрос к экзамену: Во сколько раз увеличится размер файла в худшем случае? Почему? (Приведенный в характеристиках алгоритма ответ не является полным, поскольку возможны большие значения худшего коэффициента сжатия. Найдите их.)
|
| Длина серии
| Код белой подстроки
| Код черной подстроки
|
| Длина серии
| Код белой подстроки
| Код черной подстроки
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица составных кодов:
| Длина серии
| Код белой подстроки
| Код черной подстроки
|
| Длина серии
| Код белой подстроки
| Код черной подстроки
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| совп. с белой
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
|
|
|
|
|
|
| - // -
|
| Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.
Этот алгоритм реализован в формате TIFF.
Характеристики алгоритмаCCITT Group 3
Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.
Класс изображений: Двуцветные черно-белые изображения, в которых преобладают большие пространства, заполненные белым цветом.
Симметричность: Близка к 1.
Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.
|
Дата добавления: 2015-04-07; просмотров: 1321;
