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


Энтропийное сжатие. - часть 2


Закодируем предыдущий пример числом, лежащим в единичном диапазоне. Схема кодировки следующая. Строим таблицу частот, каждому элементу таблицы ставим в соответствие диапазон, равный его частоте поделенной на длину входного массива. Устанавливаем верхнюю границу ВГ в 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 раз следующего:




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