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

       

Энтропийное сжатие.


Энтропийное сжатие в отличие от последовательного, в качестве информации о входном массиве использует только частоты встречаемости в нем отдельных байтов. Эту информацию он использует как при кодировании, так и при декодировании массива. Ее представляют в виде 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 - длина кодируемого участка или всего массива):

1.    Читаем из массива очередной символ.

2.    Установка текущего интервала. Интервал И = ВГ - НГ.

3.    ВГ = НГ + И*ВГ символа (берем из таблицы).

4.    НГ = НГ + И*НГ символа (берем из таблицы).

Рассмотрим на примере: КЗСГКСКБСК. Построим необходимую таблицу:

Цвет

Частота

Нижняя граница НГ

Верхняя граница ВГ

К

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.    Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий  в декодируемый массив.

2.    Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).

3.    Ч = (Ч - НГ) / И.

Шаг

Число

Символ

НГ

ВГ

Интервал

1

0.18989472

К

0

0.4

0.4

2

0.4747368

З

0.4

0.5

0.1

3

0.747368

С

0.5

0.8

0.3

4

0.82456

Г

0.8

0.9

0.1

5

0.2456

К

0

0.4

0.4

6

0.614

С

0.5

0.8

0.3

7

0.38

К

0

0.4

0.4

8

0.95

Б

0.9

1

0.1

9

0.5

С

0.5

0.8

0.3

10

0

К

0

0.4

0.4

В данном примере арифметический кодер «обогнал» метод Хаффмана на 1 бит. В отличие от метода Хаффмана трудоемкость алгоритма значительна. В чем же тогда «полезность»

алгоритма? Рассмотрим последовательность КККККККС. При кодировании методом Хаффмана получим выходную последовательность длиной в 9 бит (можно и в 8, так как массив состоит из 2 разных байт). При арифметическом кодировании данную последовательность можно закодировать числом 0.4375 или в двоичном виде как 0111, занимающей 4 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.


Содержание раздела