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

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

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

мерным. На рис. 2 приведена плотность вероятности приращения ярко-

сти

()

∆

. Из сопоставления рис. 1 и 2 видно, что во втором случае

плотность вероятности распределения приращений резко неравномер-

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

большой избыточностью, а следовательно, может быть в большей сте-

пени сжат, что иллюстрируют рис. 3, а и б.

∆

Рис. 2

Рис. 3

а) б)

Рис. 3, а представляет собой исходное изображение, а рис. 3, б – это

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

3, б к приращениям яркости

()

∆

, возникающим при переходе с одно-

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

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

ограничены. Сравнивая эти изображения, мы замечаем, что в исходном

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

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

вероятность больших приращений (больших отклонений от серого фона)

сравнительно мала и имеет место только на контурах.

В дальнейшем, в п. 3.1 будет описан более совершенный вид декор-

реляции изображений.

2.2. Кодирование длин серий

Кодирование длин серий или, как его еще называют, RLE (Run-Length

Encoding) в настоящее время широко применяется при записи графи-

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

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

личных форматах графических файлов, например в JPEG [1]. Этот ме-

тод применяется также в таких распространенных форматах, как PCX,

TIFF и TARGA.

Известно, что многие графические изображения, например чертежи,

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

имеющие одинаковые яркость и цвет. При разложении таких изображе-

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

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

как показано на рис. 4. Эта особенность позволяет при их сжатии рас-

ходовать меньше двоичных единиц, чем при традиционном методе ко-

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

Рис. 4

(n,0)

вых отсчетов) и значение яркости, с которого начинается серия. Так,

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

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

последовательность:

1;3,5;1,2;0,

. Из изложенного следует, что при

использовании этого метода в кодируемом сигнале устраняются (строго

говоря, ослабляются) корреляционные связи.

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

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

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

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

двоич-

ных единиц, а также

двоичных единиц для записи значения са-

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

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

последовательности составит:

посл 2 2

log log .

NNm

Обозначая вероятность нового значения, то есть появления последо-

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

нов

, а число строк в изображении и число отсчетов

в строке, соответственно, через N

стр

и N

пикс

, найдем, что полная затрата

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

()

нов стр пикс 2 2

log log .

pNN N m

Принимая во внимание, что при тра-

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

стр пикс 2

log

NN m

двоичных единиц, находим, что коэффициент сжа-

тия K

сж

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

рий, составит:

()

сж

нов 2 2

log

log log

pNm

Из этой формулы видно, что коэффициент сжатия сильно зависит от

вероятности появления новых значений p

нов

. При малых значениях ве-

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

но быстро убывает при ее увеличении. К сожалению, статистика полу-

тоновых изображений такова, что при 256 уровнях квантования прак-

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

то есть

нов

≅

Обращаясь к формуле, видим, что при

нов

≅

коэф-

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

санного метода приводит не к сокращению числа двоичных единиц, а к

увеличению. Объясняется это тем, что в этом случае дополнительная

затрата двоичных единиц идет на представление длительности после-

довательностей, хотя их протяженность почти всегда равна единице.

Недостатком этого метода является также его низкая помехоустойчи-

вость. Даже редкие помехи приводят либо к появлению на изображени-

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

всей последовательности, либо, что еще хуже, к «раздергиванию» строк,

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

тельности. Достоинством этого метода является простота его реализа-

ции. Отмеченные особенности определили и область его применения, а

именно: при записи графических изображений, в том числе цветных,

содержащих большие однородные поля.

2.3. Кодирование методом LZW

Алгоритм сжатия, реализованный в этом методе, был изобретен

Лемпелом (Lempel) и Зивом (Ziv) в 70-е гг. прошлого века (версии

LZ77и LZ78 названы по первым буквам фамилий соавторов и по

годам разработки), а доработан Терри Уэлчем (Welch) в 1984 г. В

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

графической, так и гипертекстовой информации: GIF, TIFF, PDF и

ряде других. Особенностью этого метода является адаптивность и

использование кодов переменной длины с максимальной длиной 12

двоичных единиц [2].

Рассмотрим принципы, положенные в основу метода сжатия LZW.

Будем считать, что сжатию подлежит черно-белое полутоновое изобра-

жение, проквантованное по яркости на 256 уровней. Сжатие начинает-

ся с того, что строится (инициализируется) первоначальная таблица ко-

дов, в которой каждому уровню квантования сопоставляется код,

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

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

ние кода – 0, первому – 1 и т. д., 255-му – 255. Всего, как это видно из

изложенного, такая таблица содержит 256 значений кода. Далее в таб-

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

значение 256 и код конца записи – 257. Код очистки используют для

того, чтобы не произошло переполнение таблицы, которая по принято-

му соглашению может включать коды протяженностью не более 12 дво-

ичных единиц (числа до 4096). Он необходим, так как, по мере заполне-

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

ход к кодам протяженностью в 10, 11 и 12 двоичных единиц. Код очис-

тки инициализирует таблицу заново, стирая в ней все коды, начиная

с 258-го и выше и освобождая тем самым место для кодового пред-

ставления встречающихся в изображении комбинаций символов. Код

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

что кодируемая последовательность окончилась. После завершения

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

(изображения).

Алгоритм сжатия данных можно записать следующим образом:

• инициализировать, то есть ввести первоначальную таблицу кодов;

• очистить таблицу кодов, начиная с кода 258 и до конца;

• очистить буферы строки String, Test и Byte.

Далее в цикле:

• прочитать очередной байт кодируемых данных в буфер Byte;

• сцепить (конкатенировать) String + Byte и поместить результат в бу-

фер Test;

• проверить, имеется ли в таблице кодов код, соответствующий ком-

бинации, помещенной в буфер Test. Если имеется, то содержимое буфе-

ра Test переписать в буфер String и перейти в начало цикла; если нет, то

добавить в таблицу код, соответствующий содержимому буфера Test,

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

ковым номером; вывести в выходной поток код, соответствующий со-

держимому буфера String; переписать содержимое буфера Byte в String

и перейти в начало цикла;

• закончить программу записью в выходной поток кода содержимого

String и кода конца записи.

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

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

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

длина полученных кодов будет составлять не 16 и не 24 бита, а суще-

ственно меньше.

Переходя к декодированию (декомпрессии) сжатых данных, отметим,

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

той последовательностью ему бы передавалась и кодовая таблица. Де-

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

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

ляет кодирующий алгоритм. Он несколько сложнее кодирующего и мо-

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

• прочитать новый код сжатых данных Newcode;

• если Newcode представляет собой код конца записи, то завершить

работу;

• если Newcode представляет собой код очистки, то необходимо:

а) проинициализировать таблицу кодов;

б) прочитать следующий код сжатых данных (если это будет код кон-

ца записи, то завершить работу);

в) найти Newcode в кодовой таблице и вывести соответствующую

ему декомпрессированную последовательность отсчетов;

г) скопировать Newcode в буфер, где был записан предыдущий код

(Prevcode);

• если Newcode находится в таблице, но не является ни кодом очистки,

ни кодом конца записи, то необходимо:

а) вывести соответствующую ему декомпрессированную последова-

тельность отсчетов;

б) взять первый байт декомпрессированного кода Newcode и декомп-

рессированного кода Prevcode, конкатенировать их и добавить в кодо-

вую таблицу;

г) скопировать Newcode в буфер, где хранится Prevcode;

• если Newcode в таблице отсутствует, а, кроме того, он не является

кодом очистки и кодом конца записи, то необходимо:

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

Prevcode + первый байт того же значения;

б) добавить в таблицу элемент для вышеприведенного значения;

в) скопировать Newcode в буфер Prevcode.

Метод сжатия LZW может быть применен не только для сжатия дан-

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

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

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

последовательности этих данных объединяются в группы по восемь дво-

ичных единиц. Если каждый отсчет содержит четыре двоичных едини-

цы, то объединение в группы происходит по два отсчета, а если один

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

последовательность делится пополам. Величина сжатия, обеспечивае-

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

делах 2–3 раза.

2.4. Метод кодирования Хаффмена

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

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

ных отсчетов сигналов. Его особенностью является использование ко-

дов переменной длины, при этом наиболее вероятным символам при-

сваиваются самые короткие кодовые слова, а менее вероятным – длинные.

Поясним на примере построение кодовой таблицы. На рис. 5 показа-

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

лов A

, A

и приведены вероятности, с которыми они

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

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

дерева, которому приписывается их суммарная вероятность. В нашем

примере речь идет о символах A

и A

, суммарная вероятность которых

равна 0,14. Далее объединяются следующие символы или узлы с наи-

меньшей вероятностью, как это показано на рисунке. Этот процесс про-

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

узлу, расположенному в вершине. После этого ветви дерева в зависи-

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

нулями или единицами (в нашем примере правые ветви обозначены

Код Символы Вероятность

Рис. 5

10 A

0,27

00 A

0,21

01 A

0,23

110 A

0,15

1110 A

0,07

1111 A

0,07

0,44

0,56

0,29

0,14

нулями, а левые – единицами). Чтобы найти значение кодового слова,

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

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

цы, которыми обозначены пройденные ветви.

В случае применения кода Хаффмена для сжатия изображений необ-

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

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

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

Кроме рассмотренного для сжатия данных при записи изображений

часто используют (например, в формате TIFF) так называемый моди-

фицированный алгоритм Хаффмена, при котором применяется заранее

составленная кодовая таблица.

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

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

жений в формате JPEG, MPEG-2 и др.

2.5. Арифметическое кодирование

Арифметическое кодирование относится к энтропийным методам,

обеспечивающим сжатие без потерь информации [2]. Арифметический

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

последовательностей (цепочек) символов. По этой причине, перед тем,

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

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

ражения

()

,Ln

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

ледовательность отсчетов

()

заменяется на последовательность их

разностей, то есть приращений яркости

()

∆

() ( ) ()

Ln Ln Ln

∆=+−

где n – номер отсчета.

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

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

тентов, срок действия которых в настоящее время истек или истекает.

Рассмотрим принцип действия одного из этих алгоритмов на про-

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

собой последовательность из некоррелированных значений разностей

отсчетов

()

∆

проквантованных на восемь уровней. Кодирование

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

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

табл. 1.

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

ные отсчеты. Кодирование выполняется по схеме, приведенной на рис. 6.

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

ти (интервалы), равные вероятностям P появления соответствующего

квантового уровня

∆

которые приведены в табл. 1. Порядок, в кото-

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

безразличен. Каждому значению сигнала соответствует свой интервал,

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

ния сигнала. Например, сигналу

∆=

–1, вероятность появления кото-

рого равна 0,15, соответствует интервал 0,5–0,65. Подчеркнем, что лю-

бая точка (дробь) на этом интервале соответствует

∆=

–1. На рис. 6

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

значения границ интервалов, на которые разбивается отрезок, а справа –

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

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

соответствующие им интервалы и имеющие самые короткие двоичные

коды мантиссы. Например, для отсчета сигнала

∆=

0 выбирается дробь,

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

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

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

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

янворуоговотнавкеинечанЗ ∆L

ьтсонтяореВ P яинелвяоп

янворуоговотнавк ∆L

03,0

12,0

1–51,0

21,0

2–1,0

350,0

3–50,0

450,0

Таблица 1

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

торая в данном примере равна единице.

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

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

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

их правильного декодирования декомпрессором необходимо между ними

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

для сжатия «одноотсчетных последовательностей» использование ариф-

метического кодирования не имеет смысла. Однако ситуация существен-

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

числа отсчетов.

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

ность состоит всего из трех отсчетов сигнала, значения которых 1, 3 и 2

появляются с вероятностями, приведенными в табл. 1. Для простоты

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

счисления. Обращаясь к рис. 7, видим, что, поскольку значение перво-

го отсчета сигнала равно 1, то дробь, представляющая собой закодиро-

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

0,3–0,5. Более точное значение этой дроби определяется значениями

последующих отсчетов сигнала. Для того чтобы найти это значение,

разобьем диапазон чисел 0,3–0,5 на поддиапазоны, пропорциональные

вероятностям P появления соответствующих отсчетов сигнала

()

∆

Рис. 6

∆L = 4→

∆L = –3→

∆L = 3→

∆L = –2→

∆L = 2→

∆L = –1→

∆L = 1→

∆L = 0→

–

1,000000

0,95

–

0,111100

0,9

–

0,111001

0,85

–

0,110110

0,75

–

0,110000

0,65

–

0,101001

0,5

–

0,100000

0,3

–

0,010011

–

0,000000