Главное


Энтропийное кодирование видеосигнала по методу Хаффмана

Первый известный метод эффективного кодирования символов известен как кодирование Шеннона - Фано [7]. Он основан на знании вероятности каждого символа, присутствующего в сообщении. Зная эти вероятности, строят таблицу кодов, обладающую следующими свойствами:

- различные коды имеют различное количество бит;

- коды символов, обладающих меньшей вероятностью, имеют больше бит, чем коды символов с большей вероятностью,

- хотя коды имеют различную битовую длину, они могут быть де кодированы единственным образом.

Этими свойствами обладает алгоритм Хаффмана [7], основанный на элегантной и простой процедуре построения дерева вероятностей.

Средняя длина слов L, находится в диапазоне: Н(В) < L < Н(В)+1 бит/пиксел и L, >1 бит/пиксел, т.е. средняя длина слов не более чем на 1 бит/пиксел больше энтропии, но не менее 1 бит/пиксел (в предельном случае, когда энтропия равна нулю).

Принцип построения дерева вероятностей можно достаточно просто пояснить на конкретном примере. Пусть для передачи изображения используется 8 уровней квантования, распределение которых определяется гистограммой со следующими данными:

Р(b0) - Р(b5) = Р(b6) = Р(b7) = 0,06; Р (b,) = 0,23; Р(b2) = 0,30; Р(bЗ) = 0.15; Р(b4) = 0,08.

Дерево строится справа налево следующим образом (рисунок 9 - верхняя диаграмма):

в секции I уровни пикселов сортируются по вероятности от наибольшей к наименьшей сверху вниз; при равенстве Р(bi) = P(bj) выше ставится уровень bi < bj;

в секции II две самые нижние ветви объединяются в узел, их вероятности складываются, и узел образует новую ветвь; общее количество

количество ветвей уменьшается на одну и они вновь сортируются по вероятности от наибольшей к наименьшей; в секциях III и IV и т.д. производятся операции, аналогичные проводимым в секции II до тех пор, пока не останется одна ветвь с вероятностью, равной 1.

Все это дерево можно перестроить (рисунок 9 - нижняя диаграмма), убрав пересечения.

Кодирование осуществляется движением слева направо по дереву каждому кодируемому уровню bi.

При этом на каждом узле коду приписывается, например, двоичный «0» если осуществляется шаг вверх и «1», если осуществляется шаг вниз. Таким образом, для данного случая наиболее вероятные значения и b2 кодируются двухбитовым кодом, величины b3 и b4 - трехбитовым кодом, а наименее вероятные значения b0, b5, b6 и b7 - четырехбитовым кодом (на рисунке 9 - нижняя диаграмма, - указаны справа). Не трудно понять, что эти коды легко различимы: если второй бит кода является двоичным нулем, то код - двухбитовый; в противном случае количество бит в коде более двух; - если третий бит кода является двоичным нулем, то код трехбитовый; в противном случае количество бит в коде равно четырем. Приемник декодирует информацию, используя то же самое дерево, двигаясь вверх при получении «0» и вниз при получении «1». Средняя битовая скорость в данном случае L, =2,71 бит/пиксел при энтропии =2,68 бит/пиксел (т.е. L, практически совпадает с Н).

Используются неадаптивный и адаптивный варианты хаффманского кодирования. В первом случае перед передачей сообщения передается таблица плотностей вероятностей, если она заранее неизвестна на приемной стороне. При адаптивном варианте кодирования таблица плотностей вероятностей вычисляется как на передающей, так и на приемной стороне по мере поступления данных. При этом до начала кодирования исходно предполагается, например, равновероятное распределение уровней пикселов.

Перейти на страницу: 1 2

Другие статьи по теме

Анализ прохождения периодического сигнала через LC-фильтр с потерями
Дисциплина "Основы теории цепей" является важнейшей дисциплиной в подготовке специалиста направления "Радиотехника". Данный курс лекций помогает студентам приобретать ...

Информационно-измерительная система
Целью данной курсовой работы является анализ информационно-измерительной системы (ИИС), определение типа топологии и оптимального пространственного расположения объектов ИИС, при которо ...

Микропроцессорная система управления объектом
Микропроцессорные и информационно-управляющие системы, в настоящее время, стали одним из наиболее дешевых и быстрых способов обработки информации. Практически ни одна область современно ...

www.techspirit.ru © 2020