Кодирование изображений


Последовательное сжатие. - часть 2


Если совпадение не обнаружено то создается тройка вида (0, 0, С), где C - первый символ кодируемой цепочки. Недостаток такого подхода очевиден - при кодировании «редких»

байтов мы «сжимаем»

один байт в три. Преимущество - простота реализации, большая скорость декодирования.

 

             LZSS - создает при работе вектора вида (флаг, C) и (флаг, A, B). Если битовый флаг=0, то следующий за ним C трактуется, как единичный байт и выдается в декодируемый массив. Иначе, когда флаг=1, то в декодируемый массив выдается цепочка длиною B по смещению A. LZSS кодирует намного более эффективно, по сравнению с LZ77, так как использует битовые флаги и мало проигрывает при кодировании одиночных символов. При кодировании строится словарь встречающихся цепочек в виде двоичного упорядоченного дерева. Скорость и простота алгоритма декодирования массива у LZSS также высока.

 

            LZMX (упрощенный LZM) - данный алгоритм предназначен для скоростного кодирования и по эффективности уступает LZSS, заметно обгоняя его по скорости работы. При работе кодер LZMX формирует несколько векторов вида:

1.   (0, A, несжатый поток)

- где 00 -2х битовый флаг признака данного блока, A (7 битов с диапазоном в [1..127]) - длина следующего за ним несжатого потока в байтах..

2.   (0, 0000000, A, B)

- где, A

- количество повторяющего байта B. То есть код RLE.

3.   (1, A, B) - где A(7 битов с диапазоном в [1..127]) - длина декодируемой цепочки, B - ее смещение. 

 

Для быстрого поиска повторяющихся цепочек используется хеш. Индекс - 12 битовый, вычисляется как [ (a*4) xor (b*2) ] xor c, где a, b, c - первые символы цепочки. Индекс дает смещение в массиве ранее встреченной цепочки с теми же первыми символами. Использование хеша и дает высокую скорость кодирования.

Декодирование также имеет большую скорость - читается бит - флаг, если он есть 0 и следующие за ним 7 битов также ноль, читаем следующие два байта - A и B

и копируем  в выходной массив байт B  A - раз: если при флаге=0 следующие 7 битов=A больше нуля, то в выходной массив копируем A байтов следующих за A. И, наконец, если флаг установлен в единицу, то  читаем A и следующий за ним байт B и копируем в выходной массив цепочку длиною A байт со смещения B.

 

Существуют и другие модификации алгоритма LZ (LZW, LZS, LZ78 ...). Общее свойство LZ - высокая скорость декодирования. Общая проблема - эффективность поиска кодируемых цепочек. Модификация данного алгоритма используется в графическом формате GIF.




Начало  Назад  Вперед



Книжный магазин