Реферат: Кодирование изображений
(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 |
Таким образом, мы закодировали исходный массив как 0 110 10 1110 0 10 0 11110 10 0. Итого: длина выходного сообщения - 22 бита. Степень компрессии ~4.
Метод арифметического кодирования. Данный метод появился позднее. Его принцип - кодирование исходного массива одним числом. Часто входной массив разбивают на одинаковые небольшие участки и кодируют их по отдельности, получая в результате последовательность кодовых чисел. Закодируем предыдущий пример числом, лежащим в единичном диапазоне. Схема кодировки следующая. Строим таблицу частот, каждому элементу таблицы ставим в соответствие диапазон, равный его частоте поделенной на длину входного массива. Устанавливаем верхнюю границу ВГ в 1, нижнюю НГ в 1. Далее N раз выполняем следующую последовательность действий (где N - длина кодируемого участка или всего массива):
Читаем из массива очередной символ.
Установка текущего интервала. Интервал И = ВГ - НГ.
ВГ = НГ + И*ВГ символа (берем из таблицы).
НГ = НГ + И*НГ символа (берем из таблицы).
Рассмотрим на примере: КЗСГКСКБСК. Построим необходимую таблицу:
| Цвет | Частота | Нижняя граница НГ | Верхняя граница ВГ |
| К | 4 | 0 | 0.4 |
| З | 1 | 0.4 | 0.5 |
| С | 3 | 0.5 | 0.8 |
| Г | 1 | 0.8 | 0.9 |
| Б | 1 | 0.9 | 1 |
Теперь, собственно, сама процедура кодирования:
| Шаг | Символ | НГ | ВГ | Интервал |
| 0 | 0 | 1 | 1 | |
| 1 | К | 0 | 0.4 | 0.4 |
| 2 | З | 0.16 | 0.2 | 0.04 |
| 3 | С | 0.18 | 0.192 | 0.012 |
| 4 | Г | 0.1896 | 0.1908 | 0.0012 |
| 5 | К | 0.1896 | 0.19008 | 0.00048 |
| 6 | С | 0.18984 | 0.189984 | 0.000144 |
| 7 | К | 0.18984 | 0.1898976 | 0.0000576 |
| 8 | Б | 0.18989184 | 0.1898976 | 0.00000576 |
| 9 | С | 0.18989472 | 0.189896448 | 0.000001728 |
| 10 | К | 0.18989472 | 0.1898954112 | 0.0000006912 |
Таким образом, любое число в диапазоне [0.18989472 .. 0.1898954112] однозначно кодирует исходный массив. В двоичном дробном виде как 0.XXXXXXXX...Для хранения такого числа хватит n бит (размерность XXXXXXXX....), где n ближайшее целое, удовлетворяющее неравенству: 2n > Интервал-1 =0.0000006912-1 . Искомое n равно 21. То есть мы можем закодировать исходный массив 21 битом. В данном примере - 001100001001110111111. Процедура декодирования обратная и состоит в выполнении n раз следующего:
Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий в декодируемый массив.
Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).
Ч = (Ч - НГ) / И.
| Шаг | Число | Символ | НГ | ВГ | Интервал |
| 1 | 0.18989472 | К | 0 | 0.4 |
К-во Просмотров: 469
Бесплатно скачать Реферат: Кодирование изображений
|