7.4 СТАТИСТИЧЕСКОЕ КОДИРОВАНИЕ ИЗОБРАЖЕНИЙ

Методы устранения статистической избыточности не дают сжатие бо-

лее 3:1, однако обеспечивают точное восстановление изображений. В компь-

ютерной технике для архивации данных давно используется кодировани

LZW (Лемпеля – Зива - Уолша), не приводящее к потере информации и при-

годное для сжатия данных любого рода. Кодирование начинается с построе-

ния кодового дерева из короткого блока входного потока данных. Затем про-

веряется, содержат ли последующие блоки данных кодовые слова из дерева.

Если да, то строятся новые кодовые слова как комбинация существующих и посылаются только их адреса. Такое построение кодовых слов от кодовых слов приводит к сжатию длинных последовательностей до коротких адресов.

Метод требует громоздких расчетов и не применяется в цифровом телевиде-

нии.

К этой же группе кодов, сжимающих без потери информации, относят-

ся коды с переменной длиной кодового слова и самый известный из них- код Хаффмана. Он присваивает словам с наибольшей вероятностью появления ко-

роткие кодовые комбинации, а более редким словам - более длинные. Напри-

мер, пусть алфавит источника насчитывает четыре символаa, b, c, d с вероят-

ностями появления соответственно0,5, 0,25, 0,125, 0,125. Если каждому из символов присвоить двухбитовые значения 00, 01, 10, 11, средняя длина кодо-

вого слова составит 2 бита на символ. Присвоив символу а значение 0, симво-

лу b – значение 10, символам c и d – значения соответственно 110 и 111, то в среднем для передачи одного символа расходуется1*0,5 + 2*0,25 + 2*3*0,125 = 1,75 бит. Хотя максимальная длина символа возросла, число битов, необхо-

димых для передачи сообщения, сократилось. По своей Эффективности код приближается к теоретическому пределу расхода битов и потому называется энтропийным. Адаптивная версия кода Хаффмана применяется в том случае,

когда вероятность появления кодовых слов изменяется в процессе передачи.

К группе энтропийных относится и так называемый арифметический код. Процедура кодирования которого, состоит в том, что всей совокупности символов сообщения ставится в соответствие интервал[0,1]. Этот интервал разбивается на участки, соответствующие новым вероятностям символов, и

это разбиение сообщается декодеру. После поступления очередного символа интервал пересчитывается на новые пределы, соответствующие вероятности

295

появления этого символа, и вновь разбивается пропорционально исходным вероятностям. С поступлением каждого нового символа размер интервала уменьшается, причем в строгом соответствии с вероятностями символов. Бо-

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

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

даваемую последовательность символов, и она легко может быть восстановле-

на в декодере по любому числу из этого интервала.

Кодированием длин серий называется присвоение длинным непрерыв-

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

тельная часть коэффициентов принимает нулевые значения.

296

7.5 КОДИРОВАНИЕ С ПРЕОБРАЗОВАНИЕМ

Эффективным методом сжатия изображения является групповое ко-

дирование с преобразованием. При этом преобразование проводится сразу над группой пикселей в пределах кадра(или поля) изображения. Массив отсчетов изображения трансформируется в матрицу коэффициентов. Пре-

имущества кодирования, получаемые в результате преобразования коэф-

фициентов, заключаются в следующем:

- значительное количество элементов матрицы коэффициенто имеют нулевое значение;

-декорреляция связей между пикселями, достигаемая в результате преобразования, повышает эффективность статистического кодирования;

-нелинейное квантование коэффициентов, учитывающее психофи-

зические особенности визуального восприятия искажений, дополнительно позволяет сократить объем передаваемой информации без заметного изме-

нения качества изображения.

Преобразование изображения следует рассматривать как его разло-

жение в обобщенный двумерный спектр по базисным функциям, где ам-

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

циям. Здесь рассмотрим наиболее известные преобразования, используе-

мые в реальной аппаратуре.

Дискретное косинусное преобразование

Дискретное косинусное преобразование (ДКП) является модифика-

цией дискретного преобразования Фурье и обладает полезными свойства-

ми. Во-первых, матрица ДКП хорошо апроксимирует матрицу оптимально-

го декоррелирующего преобразования Карунена - Лоэва и обладает прак-

тически такой же эффективностью, как оптимальное преобразование. Во-

вторых, ДКП реализуется с помощью быстрых преобразований, что суще-

ственно снижает вычислительные затраты на его реализацию по сравне-

нию с оптимальным преобразованием.

При использовании ДКП обработка ведется блоками8х8 пикселей.

В среднем размер блока соответствует интервалу корреляции элементов изображения. В результате выполнения ДКП формируется матрица из64

297

коэффициентов, характеризующих пространственные частоты (двумерные

- x,y) функции яркости изображения формула 7.28:

4

n-1 n-1

æ 2p jv ö æ 2pkv ö

Fuv

=

ååC( j )C k( X)jk

cosç

÷cosç

÷,

(7.28)

2n-1 j=0 k=0

è

2n-1ø è

2n-1ø

C

j =

ì0.5,m =0,

где

(

)

í1,m=1...n-1.

î

Здесь Хjk - элемент матрицы изображения, соответствующий ярко-

сти пиксела, с коордиатами j,k;

Fuv - элемент матрицы ДКП, с координатами u,v;

n - количество элементов в строке, столбце, обычно n=8.

После операции ДКП коэффициенты могут принимать не целые зна-

чения, однако дальнейшая обработка требует квантованного представления этих коэффициентов. Проведение процедуры квантования коэффициентов следует проводить с учетом психофизических особенностей зрения. Как уже отмечалось, зрительное восприятие допускает больший уровень шу-

мов и ошибок квантования в области изображений с большим уровнем вы-

сокочастотных компонент. Это означает, что коэффициенты этих компо-

нент можно квантовать на малое число уровней, в пределе на два. Посто-

янная составляющая и амплитуды низкочастотных компонент квантуются на большое число уровней и передаются с высокой точностью.

Финальной операцией при квантовании является Z-упорядочивание,

при котором оставшиеся коэффициенты выстраиваются в последователь-

ности возрастания пространственных частот. Если пространственные час-

тоты одинаковы, то впереди ставятся коэффициенты для меньших верти-

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

щих этому элементу нулей. Далее эти сочетания чисел кодируются кодом Хаффмана. Упрощенная структурная схема алгоритма внутрикадрового кодирования и декодирования на основе ДКП приведена на рисунке 7.5.

298

Видео	ДКП		Кв.		КХ	Цифровой
данные						поток
Цифровой						Видео
	ДКХ		Дкв.		ОДКП
поток						данные

Рисунок 7.5 - Упрощенная структурная схема алгоритма внутрикад-

рового кодирования и декодирования на основе ДКП

Здесь приняты обозначения: Кв. - квантователь; КХ - кодер Хаф-

фмена; ДКХ - декодер Хаффмена; Дкв - деквантователь; ОДКП - обрат-

ное дискретное косинусное преобразование.

Вэйвлетное преобразование.

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

ей природе. В этой области применение преобразований позволило достичь од-

новременного снижения сложности и повышения эффективности кодеров[16].

Их нынешний успех обьясняется несколькими причинами. С одной стороны,

концепция вейвлетов может рассматриваться как синтез идей, возникших за последние двадцать или тридцать лет в технике, физике и чистой математике. С

другой стороны, вейвлеты являются довольно простым математическим инст-

рументом с большим разнообразием возможностей для применения.

Обычно под вейвлетами понимаются функции, сдвиги и растяжения ко-

торых образуют базис многих важных пространств [17].

Вейвлеты могут быть ортогональными, полуортогональными и биорто-

гональными. Эти функции могут быть симметричными, асимметричными и не-

симметричными. Для кодирования изображений используют биортогональные вейвлеты.

При Wavelet-преобразовании, также как и при ДКП, осуществляется переход из плоскости изображения в двумерную частотную область. В от-

личие от ДКП это переход осуществляется с помощью гребенки цифровых фильтров. Блочная структура шумов квантования более ярко проявляется при больших степенях сжатия, представляющих наибольший интерес в приложениях к специальной технике.

299

Техническая трактовка Wavelet-преобразования может быть пред-

ставлена рисунке 7.6.

Рисунок 7.6 - Блок Wavelet-преобразования А1 - Аn – субполосные фильтры.

Сигнал изображения разделяется по спектру на две равные части с помощью фильтров нижних и верхних частот. Поскольку НЧ- и ВЧком-

поненты имеют полосу в два раза меньше, чем у исходного сигнала, то их частота дискретизации может быть понижена в два раза. Входной сигнал на рисунке 4.3 является цифровым, поэтому после цифровой НЧ- и ВЧ-

фильтрации производится децимация (исключение каждого второго отсче-

та).

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

понента отображает горизонтальные высокочастотные составляющие изо-

бражения, вторая компонента отображает вертикальные составляющие,

третья высокочастотная компонента связана с диагональными пространст-

венными частотами и отображает яркостные переходы.

Поскольку после каждой процедуры фильтрации количество отсче-

тов на выходе фильтра уменьшается в два раза, то результирующее коли-

чество отсчетов на выходе всей гребенки фильтров в точности равно коли-

честву отсчетов в исходном изображении. Таким образом, при W-

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

300

кодирования спектральных отсчетов изображения, полученных в результа-

те W-преобразования, используются те же принципы, что и при ДКП.

Для восстановления исходного изображения каждая компонента растягивается, т.е. после каждого значащего отсчета вставляется нулевой отсчет.

Затем осуществляется аналогичная рассмотренной выше НЧ- и ВЧ-

фильтрация, в результате которой нулевые отсчеты заменяются интерпо-

лированными.

Структурная схема алгоритма внутрикадрового сжатия на основе

W-преобразования представлена на рисунке 7.7.

Видео	WП		Кв.		КХ	Цифровой
данные						поток
Цифровой						Видео
	ДКХ		Дкв.		ОWП
поток						данные

Рисунок 7.7 – Структурная схема алгоритма внутрикадрового сжа-

тия на основе W-преобразования

На этой схеме WП и ОWП обозначают – W-преобразование и обрат-

ное W-преобразование. Процедуры квантования коэффициентов и стати-

стического кодирования на основе кодов Хаффмана выполняются так же,

как и при ДКП.

301