Красильников Н.Н., Красильникова О.И. Мультимедиа технологии в информационных системах. Методы сжатия и форматы записи графической информации

Подождите немного. Документ загружается.

(как показано на рис. 7). При этом последовательности 1; 3 будет соот-

ветствовать дробь, заключенная в интервале от 0,3 + 0,85 × 0,2 = 0,47

до 0,3 + 0,90 × 0,2 = 0,48. Поступая аналогичным образом, получим для

последовательности 1; 3; 2 дробь, заключенную в пределах от 0,4765 до

0,4775. Записывая полученный интервал в двоичной системе счисле-

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

этот интервал, и используя знаки после запятой в качестве символов кода,

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

Чтобы произвести декомпрессию, необходимо декомпрессору знать

таблицу, приведенную выше, и длину закодированной последователь-

ности отсчетов сигнала. Обращаясь к вышеупомянутому примеру, про-

ведем декодирование следующим образом. Так как закодированная пос-

ледовательность заключена в пределах от 0,4765 до 0,4775, то значение

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

тервал от 0,4765 до 0,4775 лежит внутри интервала 0,3–0,5. Рассуждая

аналогично, приходим к выводу, что значение второго отсчета состав-

ляет 3, поскольку интервал от 0,4765 до 0,4775 лежит внутри интерва-

ла от 0, 47 до 0, 48. И аналогичным образом находим значение третьего

отсчета сигнала: оно равно двум. После этого остается только от най-

денных последовательностей приращений яркости

()

∆

перейти к

самим значениям яркостей пикселов

()

по формуле:

Рис. 7

0,47

0,5

0,48

0,4775

0,4765

0,47

0,3

∆L = 4→

∆L = –3→

∆L = 3→

∆L = –2→

∆L = 2→

∆L = –1→

∆L = 1→

∆L = 0→

–

0,95

–

0,9

–

0,85

–

0,75

–

0,65

–

0,5

–

0,3

–

() ( ) ()

Ln Ln Ln

=−+∆

Разумеется, мы рассмотрели крайне упрощенный вариант алгоритма

арифметического кодирования, однако он наглядно поясняет, как это

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

следовательностей.

Достоинством арифметического кодирования является то, что оно

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

ность из стационарного некоррелированного сигнала.

Чтобы оценить величину сжатия, обеспечиваемого при арифмети-

ческом кодировании, необходимо найти такое минимальное число N,

чтобы длина интервала при сжатии последнего кодируемого отсчета

сигнала была бы меньше

12 .

Это означает, что внутри интервала

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

торого после N-го знака будут только нули. Длина интервала вычисля-

ется весьма просто: путем перемножения вероятностей всех символов

(вероятностей отсчетов всех сигналов). При этом сжатие будет равно

отношению длины исходного кода к N.

В настоящее время находит применение адаптивное арифметическое

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

ятностей появления каждого из значений сигнала все время обновляется в

процессе упаковки и распаковки очередного отсчета. При использовании

данного метода отпадает необходимость в записи в файл сжатого сооб-

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

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

тей происходили синхронно и в компрессоре, и в декомпрессоре, что

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

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

2.6. Разделение кодируемого сигнала изображения на контексты

Как известно, при сжатии изображений посредством энтропийного

кодирования характеристики кодера настраиваются на статистические

характеристики кодируемого изображения. Однако, как правило, изоб-

ражения неоднородны, и разные их области имеют различные статисти-

ческие характеристики, точнее, различные статистические свойства.

Поэтому для достижения максимальной степени сжатия следовало бы

кодер по-разному настраивать при кодировании этих областей. Другим

вариантом решения этой проблемы является автоматическое разделе-

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

ющие эти области, с последующим кодированием этих сигналов коде-

рами, настроенными на их статистические характеристики.

Поясним это следующим простым примером. Предположим, что пе-

редаче подлежит двухградационное изображение, показанное на рис. 8.

Простейшим способом передачи этого изображения была бы передача

значений яркости каждого пиксела путем их перебора: пиксел за пиксе-

лем и строка за строкой.

Однако для этого потребовалось бы передать

стр пикс

значений.

Обычно количество строк и количество пикселов в строке для реаль-

ных изображений измеряются сотнями, поэтому

стр пикс

представ-

ляет собой достаточно большую величину. Вместе с тем цифровой по-

ток можно существенно сократить, если передавать, например, значения

координат начал и концов отрезков линий, рассматривая при этом точ-

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

ставление изображения устраняет взаимную корреляцию между пере-

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

стр

1000

N =

пикс

1000,

то на передачу каждой координаты потре-

буется 10 двоичных единиц, и общее число двоичных единиц составит:

18×2×20 = 720 вместо

стр пикс

= 1000000, то есть сжатие составит

1389 раз. Приведенный пример демонстрирует эффективность декор-

реляции изображения перед его кодированием.

Эффективность передачи можно еще увеличить, если изображение,

приведенное на рис. 8, разделить на две компоненты (два контекста),

Рис. 8

как это показано на рис. 9, а и б. При таком разделении появляется

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

текста), показанной на рис. 9, б, ограничиться однократной передачей

координат точек, в то время как при передаче отрезков линий необходи-

мо было сообщать координаты их начала и конца. Другими словами,

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

заключающийся в том, что они, в отличие от линий, не имеют длины. В

этом случае получается дополнительный выигрыш. Действительно, для

передачи контекста (а) необходимо затратить 160 двоичных единиц и

для передачи контекста (б) – 280, а всего – 440 двоичных единиц. Та-

ким образом, в нашем примере уже такое простое разделение на кон-

тексты дает дополнительный выигрыш в сжатии в 1,63 раза.

В данном случае мы рассмотрели очень простой пример, на котором

показали эффективность этого приема. В качестве другого примера мож-

но привести разделение сообщения на контексты при использовании

кодов Хаффмена при передаче изображений с сильно выраженной не-

стационарностью статистических характеристик. Простым примером,

демонстрирующим эту ситуацию, является передача изображения жур-

нальной обложки, на которой имеются крупные надписи, и ряд разно-

плановых фотографий: портретов, пейзажей и т. д. Разделение на кон-

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

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

таблицы и, следовательно, благодаря этому увеличить сжатие [2]. На

Рис. 9

а) б)

контексты может разделяться не только само изображение, но также его

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

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

сивным. В настоящее время он начинает широко использоваться в раз-

личных алгоритмах сжатия, например в MPEG4. При использовании

этого метода необходимо иметь в виду, что увеличение числа контек-

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

волов в каждом контексте достаточно велико [3].

3. СЖАТИЕ ИЗОБРАЖЕНИЙ С ПОТЕРЕЙ ИНФОРМАЦИИ

3.1. Дифференциальная кодово-импульсная модуляция

В настоящее время дифференциальная кодово-импульсная модуля-

ция (ДКИМ), которая была предложена Катлером в 1952 г., не находит

самостоятельного применения. Однако принципы, заложенные в ДКИМ,

часто применяют в составе различных методов сжатия изображений как

один из элементов их алгоритмов. В связи с этим рассмотрим принцип

действия ДКИМ на примере кодирования полутонового черно-белого

изображения [1]. Сущность ДКИМ заключается в том, что на основе

известных значений сигнала в предшествующие моменты времени

−−

делается статистическая оценка (предсказание) значения сиг-

нала

()

сn

∧

в момент времени t

. После этого предсказанное значение

сигнала сравнивается с тем значением

()

сn

которое имеется на са-

мом деле, и находится сигнал ошибки предсказания:

()

() ()

ncncn

tUtUt

∧

=−

Сигнал ошибки предсказания квантуется, кодируется и передается в

место приема или записывается, например на магнитный диск. Восста-

новление исходного сигнала осуществляется путем его предсказания с

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

нии, с последующим прибавлением к предсказанному значению сигна-

ла ошибки предсказания:

() ()

()

cn cn n

tUtvt

∧

Таким образом, при использовании ДКИМ передаче (или записи)

подлежит только та составляющая сигнала, которую невозможно пред-

сказать (сигнал ошибки предсказания) и которая, следовательно, несет

информацию. Обратим внимание на то, что восстановленное значение

сигнала отличается от исходного на величину шума квантования сигна-

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

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

это отличие можно сделать очень малым.

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

промоделирован двумерным стационарным марковским процессом 1-го

порядка, наложенным на некоторое среднее значение, определяемое

средней яркостью изображения

Известно, что в этом случае мини-

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

лучается, если статистическую оценку ожидаемого значения сигнала

производить следующим образом:

() ( )

~1~1

сn сn

taUt

∧

−

где

()

−

– переменная составляющая сигнала изображения в мо-

мент времени

;

−

– весовой коэффициент. Для того чтобы при сжа-

тии данных посредством ДКИМ искажения, вносимые в сигнал, кото-

рые обусловлены процессом квантования, были бы минимальны,

необходимо использовать такое значение весового коэффициента a

, при

котором средний квадрат сигнала ошибки предсказания

()

был бы

также минимальным. Это следует из того, что средний квадрат шума

квантования прямо пропорционален среднему квадрату квантуемого

сигнала [1]. Чтобы найти это значение весового коэффициента, запи-

шем вначале выражение для

()

() () () ( ) ()

22 22

~1~~11~

сn сnсn сn

vt Ut aUtUt aUt

−

=− +

(3.1)

а затем продифференцируем его по a

и приравняем результат нулю.

Решая получившееся уравнение относительно a

, получим

() ( ) ()

1~ ~1~1

сnсn сn

UtUt Ut

−−

( 3.2)

Замечая, что

() ( ) () ()

~~1~1сnсn сn сэ

tU t U t

−−

где

()

– значение коэффициента автокорреляции сигнала при сме-

щении его реализаций на интервал времени, равный интервалу между

двумя смежными отсчетами

, находим, что оптимальным значением

весового коэффициента, при котором обеспечивается минимальный

уровень шума квантования, будет

()

сэ

(3.3)

Обращаясь к формуле (3.1) и заменяя в ней весовой коэффициент a

найденным значением, получим после несложных преобразований

()

22 2

ссэ



=−ρτ



(3.4)

В этой формуле опущены скобки с аргументами t

после значений

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

(3.3) видно, что, чем ближе значение коэффициента автокорреляции

()

сэ

к единице, тем ближе к единице будет значение весового коэф-

фициента a

. В некоторых случаях, например портретных изображений,

()

сэ

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

зываемого значения сигнала

()

сn

∧

использовать значение, которое он

имел на предыдущем отсчете изображения, то есть

()

сn

−

Такая за-

мена, упрощая алгоритм, не приводит к заметному ухудшению качества

декомпрессированного изображения.

Обратим внимание на то, что при формировании сигнала ошибки

предсказания имеет место процесс декорреляции, то есть сигналы

()

−

оказываются некоррелированными:

()( )

tvt

−

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

сигнала ошибки предсказания

при значениях коэффициента авто-

корреляции

()

сэ

сжимаемого сигнала, близких к единице, много мень-

ше среднего квадрата исходного сигнала, что следует из формулы (3.4).

Средний квадрат шума квантования, на это обращалось внимание, пря-

мо пропорционален среднему квадрату квантуемого сигнала и, следо-

вательно, при квантовании сигнала ошибки предсказания мы будем

иметь средний квадрат шума квантования

кв.дким

много меньшим, чем,

если бы мы квантовали сам исходный сигнал:

()

222

кв.дким 0 0

σ=νσ

Заметим, что важно не беспредельно уменьшать шум квантования

при передаче или записи изображений, а только сделать его ниже неко-

торого порогового уровня, при котором он еще заметен на изображе-

нии и ухудшает его качество. Поэтому, заменяя исходный сигнал сигна-

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

квантования и, следовательно, уменьшить число двоичных единиц кода,

которым он представляется, увеличив при этом шум квантования до

прежнего порогового уровня, то есть осуществить сжатие данных.

В отличие от рассмотренного простейшего случая предсказания сиг-

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

ко от одной независимой переменной – времени, изображение можно

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

изображений является функцией двух пространственных координат. В

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

то есть использовать для предсказания не только сигнал от предшеству-

ющего отсчета в данной строке, но также и сигнал от отсчета в преды-

дущей строке, который расположен над отсчетом, сигнал от которого

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

щественно более точным и, следовательно, позволит еще больше умень-

шить средний квадрат сигнала ошибки предсказания. Однако исследо-

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

к двумерному приводит лишь к сравнительно небольшому уменьше-

нию величины

. Именно по этой причине двумерная ДКИМ не име-

ет существенных преимуществ перед одномерной.

Дифференциальная кодово-импульсная модуляция является методом

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

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

В настоящее время ДКИМ используют как компонент достаточно

сложных алгоритмов, предназначенных для сжатия данных при записи

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

отмечено, ДКИМ для этих целей практически не применяется.

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

преобразований

Особенностью данного метода сжатия изображений является то, что

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

тельность отсчетов, которой это изображение представлено, а значения

спектральных коэффициентов, получающихся при ортогональном пре-

образовании изображения. Эта идея кодирования впервые была выдви-

нута в 1968 г. В результате ортогональных преобразований изображе-

ния

()

,,Lkn

имеющего сильные корреляционные связи между

смежными отсчетами (пикселами), имеет место декорреляция, в резуль-

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

()

,Fuv

оказыва-

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

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

энергии между его отсчетами (пикселами), распределение энергии между

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

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

ми индексами u, v, представляющие амплитуды низких пространствен-

ных частот, и лишь небольшая ее часть – на прочие. В целях сжатия

изображений спектральные коэффициенты, имеющие малую амплиту-

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

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

числом двоичных единиц. Так как средний квадрат шума квантования

пропорционален среднему квадрату квантуемого сигнала, то возника-

ющие при этом искажения изображения невелики. При декомпрессии

(восстановлении) изображения вначале по имеющемуся коду восста-

навливаются спектральные коэффициенты, а затем путем обратного

ортогонального преобразования восстанавливается само изображение.

Поскольку при записи или при передаче спектральных коэффициен-

тов, в отличие от записи или передачи значений отсчетов исходного

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

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

остальных, расходуется значительно меньше двоичных единиц, если они

вообще не отбрасываются, достигается высокая степень сжатия. По-

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

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

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

сжатия с потерей информации.

Существуют два метода отбора спектральных коэффициентов: зо-

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

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

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

щие в одну зону, квантуются на одно и то же число уровней, как это

показано на рис. 10.