(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 4. Статистическая избыточность дискретизированных данных

f2 = 2; fi = fi−1 ). Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.

Очевидно, если в разложении числа n присутствует fi, то в этом разложении не может быть числа fi+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа. Примеры кодов Фибоначчи приведены в табл. 4.4. В кодах Фибоначчи все биты, кроме двух последних, являются мантиссами.

Таблица 4.4. Коды Фибоначчи

4.2.2. Алгоритм Шеннона–Фано

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

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

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

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

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

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

Глава 4. Статистическая избыточность дискретизированных данных

Кодирование осуществляется движением слева направо по дереву к каждому кодируемому уровню bi. При этом на каждом узле коду приписывается, например, двоичный «0», если осуществляется шаг вверх и «1», если осуществляется шаг вниз.

Таким образом, для данного случая наиболее вероятные значения b1 и b2 кодируются двухбитовым кодом, величины b3 и b4 — трехбитовым кодом, а наименее вероятные значения b0, b5, b6 и b7 — четырехбитовым кодом (на рис. 4.2, нижняя диаграмма, коды указаны справа).

Нетрудно понять, что эти коды легко различимы:

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

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

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

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

Приемник декодирует информацию, используя то же самое дерево, двигаясь вверх при получении «0» и вниз при получении «1». Средняя битовая скорость

в данном случае ˆ бит/пиксел при энтропии бит/пиксел (т. е. ˆ

L = 2,71 H = 2,68 L

практически совпадает с H).

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

4.2. Виды статистического кодирования

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

ствует упомянутое выше ограничение снизу ˆ бит/отсчет.

L 1

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

Модификация алгоритма Хаффмана с фиксированной таблицей (CCITT, Group 3) [2.63] используется при сжатии черно-белых изображений (один бит на пиксел). Данный алгоритм был предложен третьей группой по стандартизации Международного консультационного комитета по телеграфии и телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, в свою очередь, сжимается, по Хаффману, с фиксированной таблицей.

Ниже приведены два вида кодов соответственно:

–коды серий — от 0 до 63 с шагом 1 (табл. 4.5);

–дополнительные коды — от 64 до 2560 с шагом 64 (табл. 4.6).

Таблица 4.5. Таблица кодов серий длиной от 0 до 63 (CCITT, Group 3)

Глава 4. Статистическая избыточность дискретизированных данных

Таблица 4.5 (окончание)

Каждая строка изображения сжимается независимо. Считается, что в изображениях существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то считается, что строка начинается белой серией с длиной 0. На практике в тех случаях, когда в изображении преобладает черный цвет, изображение инвертируется перед компрессией и записывается эта информация в заголовке файла.

Близким к Хаффмановскому является алгоритм JBIG, разработанный группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений, например, факсов или отсканированных

4.2. Виды статистического кодирования

документов [2.64]. В принципе он может применяться и к 2-, и к 4-битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Распаковываться изображение на экране будет постепенно, как бы медленно «проявляясь».

Как и алгоритм Хаффмана, JBIG использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся — длинные.

4.2.4. Блочное и условное кодирование

Дальнейшее снижение битового потока возможно, если использовать блочное кодирование [2.4], т. е. если кодировать и передавать информацию блоками из N отсчетов, которые можно представить как компоненты вектора:

b = (b1, b2, . . . , bN ).

При квантовании этих компонент K уровнями имеем 2N K возможных значений случайного вектора B, чьи возможные значения b имеют распределение вероят-

ностей {P (b)}. Энтропия N -го порядка (блочная энтропия) определяется как

b

где сумма берется по всем 2N K возможным значениям.

Очевидно, что энтропия вектора H(B) связана с энтропией каждой его компоненты H(B) соотношением

N1 H(B) H(B),

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

Таким образом, при достаточно больших N возможно (хотя и не всегда практично из-за большого объема вычислений) кодировать поблочно и получать битовый поток, максимально отличающийся от энтропии первого порядка H(B) на малую величину N1 .

Существенным недостатком блочного кодирования является необходимость создания таблицы кодирования (или дерева), содержащей 2N K кодовых слов. При этом часто получаются весьма длинные коды.

Эта проблема частично преодолевается при так называемом условном кодировании [2.4], когда кодируется компонента bN при условии, что компоненты b1, b2, . . . , bN −1 уже переданы и известны приемнику. В этом случае коды Хаффмана для bN можно построить на основе условной вероятности {P (bN | b1, b2, . . . , bN −1)}.

Глава 4. Статистическая избыточность дискретизированных данных

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

будет не более чем на 1 бит отличаться от условной энтропии:

H(BN |b1, . . . , bN −1 ) = − P (bN |b1,. . . ,bN −1 ) · log2 P (bN |b1,. . . ,bN −1 ). (4.5)

bN

Если такой код построен для всех возможных (N − 1)-мерных значений, то получается 2(N −1)K кодов, каждый из которых имеет 2K кодовых слов.

Результирующая условная энтропия может быть получена усреднением по всем (N − 1)-мерным векторам:

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

Однако в связи с тем, что ˆc оценена снизу битом на отсчет, условное кодирование

L

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

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

К методам блочного кодирования можно отнести алгоритм группового кодирования RLE (Run Length Encoding) [2.6, 2.9], который позволяет сжимать данные любых типов независимо от содержащейся в них информации. Сама информация влияет лишь на коэффициент сжатия. Он является самым быстрым и простым алгоритмом компрессии и при этом иногда оказывается весьма эффективным.

В основу алгоритма RLE положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой, в которой указывается код данных и коэффициент повтора. Он оперирует группами данных — последовательностями, в которых один и тот же символ встречается несколько раз подряд. Суть его заключается в том, что при кодировании строка повторяющихся символов, составляющих группу, заменяется строкой, которая содержит сам повторяющийся символ (значение группы) и количество его повторов (счетчик группы).

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

4.2. Виды статистического кодирования

сированной длиной полей. Для текстовых данных методы RLE, как правило, неэффективны.

Из специфики работы алгоритма можно легко понять, для каких изображений коэффициент сжатия будет максимальным. Это изображения, содержащие минимальное количество цветов, без плавных переходов (с резкими границами) и с большими участками, заполненными одним цветом. Так как сканирование данных осуществляется построчно слева на право, высокий коэффициент сжатия будет достигаться на изображениях, строки которых содержат достаточно длинные цепочки одинаковых пикселов.

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

Арифметическое кодирование во многих отношениях превосходит префиксные методы и теоретически обеспечивает среднюю битовую скорость передачи данных равной энтропии.

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

Основная концепция арифметического кодирования принадлежит П. Элайесу [2.56, 2.57] и относится к началу 60-х годов прошлого века. Дальнейшие исследования были направлены на практическую реализацию алгоритма [2.14–2.24].

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

До начала кодирования сообщению ставится в соответствие интервал (0, 1]. Каждому символу из множества N символов, присутствующих в сообщении, на интервале (0, 1] отводится интервал, ширина которого равна вероятности появления символа. Если распределение уровней квантования пикселов изображения соответствует гистограмме, аналогичной той, что приведена в качестве примера при изучении хаффмановского кодирования, то указанный интервал (0, 1] разбивается так, как показано на рис. 4.3 слева.

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

Пусть по мере сканирования изображения первым из N символом, поступающим на кодер, является символ b1. Тогда на первом этапе кодирования интервал (0, 1] преобразуется в новый интервал, границами которого являются границы интервала P (b1) на шкале (0, 1].

Диапазон новой шкалы равен r1P (b1), его минимальное значение равно l1P (b0), а максимальное h1P (b0) + P (b1).

Эта шкала также разбивается на части, пропорциональные вероятностям сообщений P (bi). Значения шкалы в n-й точке

Глава 4. Статистическая избыточность дискретизированных данных

Рис. 4.3. Принцип обработки информации при арифметическом кодировании

причем g1(0) = l1, а g1(N )h1. Если на втором этапе на кодер поступает символ b2, то шкала вновь преобразуется, как показано на рис. 4.3. Диапазон новой шкалы равен r2r1 · P (b2), его минимальное значение равно

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

На k-м этапе при поступлении на кодер n-го символа шкала итеративно изменяется таким образом, что ее диапазон равен rk rk−1 · P (bn). Его минимальное

4.2. Виды статистического кодирования

окончании цикла кодирования формируется такое число g, что выполняется неравенство lk < g hk. Это число g характеризует передаваемую последовательность символов, которая может быть однозначно восстановлена в приемнике.

Как показано на рис. 4.3, по окончании 5-го этапа число g должно быть

0,14762908 < g 0,14772844.

Если на приемной стороне сформирована исходная шкала вероятностей на интервале (0, 1], то это число g попадает на интервал, характеризующий символ b1, поступивший в кодер на первом этапе.

Зная, что на первом этапе на кодер поступил символ b1, можно рассчитать новую шкалу, соответствующую шкале кодера на 1-м этапе. В этой шкале число g попадает на интервал, характеризующий символ b2, поступивший в кодер на втором этапе. Таким образом, последовательно могут быть определены все символы, поступающие на кодер (в данном случае — последовательность b1, b2, b3, b0, b4).

Трудности в реализации приведенного алгоритма арифметического кодирования связаны с хранением чисел с большим количеством знаков после запятой

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

упростить хранение данных. Алгоритм работает быстрее, если удается опери-

ровать двоичными дробями, задаваемыми последовательностью a1/21 + a2/22 + + a3/23 + a4/24 + · · · + ak/2k. При этом на каждом этапе вычислений необходимо дописывать дополнительные последовательности дробей, пока получившееся число не попадет в интервал, соответствующий закодированной цепочке. Чтобы избежать ограничений, связанных с используемой разрядностью переменных, реальный алгоритм работает с целыми числами и оперирует с дробями, числитель

изнаменатель которых являются целыми числами (например, знаменатель равен 216 = 65 536). При этом с потерей точности можно бороться, отслеживая сближе-

ние величин lk и hk и умножая числитель и знаменатель дроби на целое число, обычно на 2n.

4.2.6.Словарные методы кодирования дискретной информации

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