Предыдущая страница реферата | 1  2  3  4  5  6

Рассмотрим вышесказанное на примере. Пусть дана часть изображения длиной 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.1898918|0.1898976 |0.00000576 |
| | |4 | | |
|9 |С |0.1898947|0.189896448|0.000001728|
| | |2 | | |
|10 |К |0.1898947|0.189895411|0.000000691|
| | |2 |2 |2 |

Таким образом, любое число в диапазоне [0.18989472 .. 0.1898954112] однозначно кодирует исходный массив. В двоичном дробном виде как
0.XXXXXXXX...Для хранения такого числа хватит n бит (размерность
XXXXXXXX....), где n ближайшее целое, удовлетворяющее неравенству: 2n >
Интервал-1=0.0000006912-1. Искомое n равно 21. То есть мы можем закодировать исходный массив 21 битом. В данном примере -
001100001001110111111. Процедура декодирования обратная и состоит в выполнении n раз следующего:

1. Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий в декодируемый массив.
2. Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).
3. Ч = (Ч - НГ) / И.

|Шаг |Число |Символ |НГ |ВГ |Интервал|
|1 |0.1898947|К |0 |0.4|0.4 |
| |2 | | | | |
|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 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.

Обработка графической информации.

Для простоты изложения пусть изображение хранится в квадратной матрице
X с элементами xi,j N строк на N столбцов. Для некоторых методов применяют разбивку исходного изображения на блоки. Обрабатывая матрицу, мы будем иметь временную сложность алгоритма как минимум кратной N3 . Для ее уменьшения поступают следующим образом: разбивают изображение на несколько малых размером n на n, n

Скачали данный реферат: Иовилла, Lesnichij, Jedit, Merkurij, Jagubov, Polovcev, Тюшняков.
Последние просмотренные рефераты на тему: шпаргалка егэ, конспект речь, банк рефератов бесплатно, реферат лист.



Предыдущая страница реферата | 1  2  3  4  5  6

Поделитесь этой записью или добавьте в закладки