Рефераты. Цифровая обработка графики
Наиболее
распространены в настоящее время модификации
алгоритма LZ (по имени их авторов - Лемпела и Зива). По сравнению с RLE сделан шаг вперед - будем
искать в исходном материале не последовательности одинаковых видов, а
повторяющихся цепочек символов. Повторяющие цепочки в кодированном сообщении
хранятся как ссылка на первое появление данной цепочки. Например, в цепочке КЗСЗБСКЗСЗБ
начиная с 7 символа, идет цепочка КЗСЗ, которую мы можем заменить ссылкой на
1-ый символ. Рассмотрим наиболее распространенные реализации алгоритма LZ:
1. LZ77 - при работе выдает тройки вида (A, B, C), где A - смещение (адрес предыдущей цепочки B
байтов которой совпадают с кодируемой цепочкой), B - длина цепочки, C - первый символ в кодируемом
массиве, следующий за цепочкой. Если совпадение не обнаружено то создается
тройка вида (0, 0, С), где C - первый
символ кодируемой цепочки. Недостаток такого подхода очевиден - при кодировании
«редких» байтов мы «сжимаем» один байт в три. Преимущество - простота
реализации, большая скорость декодирования.
2. LZSS - создает при работе вектора вида (флаг, C) и (флаг, A,
B). Если битовый флаг=0, то следующий за ним C трактуется, как единичный байт и выдается в декодируемый массив. Иначе,
когда флаг=1, то в декодируемый массив выдается цепочка длиною B по смещению A. LZSS кодирует намного более
эффективно, по сравнению с LZ77, так как использует
битовые флаги и мало проигрывает при кодировании одиночных символов. При
кодировании строится словарь встречающихся цепочек в виде двоичного
упорядоченного дерева. Скорость и простота алгоритма декодирования массива у LZSS
также высока.
3.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.
Энтропийное сжатие
в отличие от последовательного, в качестве информации о входном массиве
использует только частоты встречаемости в нем отдельных байтов. Эту информацию
он использует как при кодировании, так и при декодировании массива. Ее
представляют в виде 256 компонентного вектора, координата i которого представляет собой сколько раз байт со значением i встречается в исходном массиве. Данный вектор занимает небольшое
пространство и почти не влияет на степень компрессии. Многие методы
энтропийного кодирования видоизменяют данный вектор в соответствии с
используемым алгоритмом. Рассмотрим два наиболее часто используемых методов:
Метод Хаффмана . Данный метод сокращает
избыточность массива, создавая при кодировании переменную битовую длину его
элементов. Основной принцип таков: наиболее часто
встречающемуся байту - наименьшую длину, самому редкому -
наибольшую. Рассмотрим простейший пример кодирования методом Хаффмана - способ
конечного нуля. Любой элемент кодируется цепочкой битов, состоящей
из одних единиц и кончающийся нулем. Таким образом, самый частый закодируем
одним битом - 0, следующий за ним по частоте как 10, далее - 110, 1110, 11110 и
т.д. Процедура декодирования также очевидна.
Рассмотрим
вышесказанное на примере. Пусть дана часть изображения длиной 80 бит - десять
цветов и каждый из них закодирован одним байтом (индексированное 256 цветами
изображение): КЗСГКСКБСК (где К - красный, З - зеленый и
т.д.). Закодируем его. Построим таблицу частоты встречаемости цвета и кода ему соответствующего:
Цвет
Частота
Код
К
4
0
З
1
110
С
3
10
Г
1
1110
Б
1
11110