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

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

Величину «С» можно выбрать, например, как среднее значение длины совпадений, в данном случае сумма длин совпадений равна 34, а C = 34/17 = 2. Если совпадений постистории (правосторонних контекстов) нет, то записывается код номера строки «0».

Бит различия — первый бит пакуемой строки, отличающий ее от строки, максимально с ней совпадающей. В данном случае — 1 (отмечен подчеркиванием):

–в пакуемой строке — 010001011,

–в максимально близкой к ней 4-й строке — 010001010100101110.

Этим битом определяется положение максимально близкой строки: если бит 0, то эта строка выше, если 1 — то ниже. В данном случае пакуемая строка ниже.

Длина «вытяжки» (в терминологии автора алгоритма) — количество нулей или единиц в той части пакуемой строки (ниже отмечено подчеркиванием значений 0101), которая находится между битом различия максимально совпадающей строки (бит отмечен подчеркиванием в нижней строке) и битом различия второй строки (бит отмечен подчеркиванием в верхней строке). Если пакуемая строка лексикографически старше строки, максимально совпадающей с ней, то передается количество нулей, а если младше — то количество единиц. В данном случае подсчитывается количество нулей, которое равно 2.

01010010001010100101110

0100010111. . .

010001010100101110

Длина «вытяжки» также кодируется адаптивным статистическим кодером. Таким образом, упакована строка 010001011 (до бита различия включитель-

но). Операция восстановления строки осуществляется следующим образом: Декодируется номер строки максимального совпадения (в данном случае 4). По биту различия определяется положение запакованной строки (и соседней

строки) — если бит «0», то она выше (лексикографически младше, длина «вытяжки» — количество единиц), в противном случае — ниже (лексикографически старше, длина «вытяжки» — количество нулей) (в данном случае номер соседней строки — 13, она лексикографически старше).

Копируется в искомую строку совпадающая часть строки максимального совпадения (4,010001010100..) и соседней (13,010100100010. . . ), а также следующий бит из строки максимального совпадения (в данном случае — совпадающая часть — 010, а следующий бит — 0). Декодируется длина «вытяжки» (2).

Восстанавливается следующая часть искомой строки по «вытяжке» — копируются из строки максимального совпадения следующие биты, включающие соответствующее длине вытяжки количество нулей или единиц (в данном случае два нуля, так как искомая строка лексикографически старше; строка максимального совпадения — 010001010100. . . , из нее уже скопировано 4 бита, 0100, значит, копируется 010). Далее копируются из строки максимального совпадения все биты до следующего нуля или единицы (в данном случае — до следующего нуля, т. е. 1). Таким образом, восстановленная по «вытяжке» часть строки — 0101.

Дописывается в искомую строку бит различия (в данном случае — 1, а в строке максимального совпадения следующий бит, естественно, 0). Таким образом,

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

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

Метод Барроуза–Уиллера (BWT — Burrows–Wheeler Transform)

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

Принцип преобразования BWT поясняется в табл. 4.13 на примере использования фразы: «на_дворе_трава_на_траве_дрова». Эта фраза обозначена в столбце 2 «Циклические перестановки» под номером «0». Последующие строки в этом столбце представляют собой циклические последовательные сдвиги фразы, каждый раз на один символ влево. Полученный набор матриц фраз пронумерован числами от 0 до 28.

Таблица 4.13. Пример преобразования Барроуза–Уиллера

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

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

Встолбце 3 «Сортированные перестановки» фразы столбца 2 отсортированы

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

впорядке «а», «в», «д», «е», «н», «о», «р», «т», «_». При этом сначала следует сортировать строки по первому символу, затем строки, у которых первые симво-

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

После этой сортировки необходимо выписать из каждой фразы последние символы, приведенные в столбце 5, и запомнить номер строки, в которой записана исходная фраза (указан в столбце 6).

Приведенное преобразование Барроуза–Уиллера позволяет восстановить исходную информацию по данным столбцов 5 и 6. Последовательность операций восстановления информации приведена в табл. 4.14. Исходной информацией являются символы, приведенные в правой части столбца 2 этой таблицы и обозначенные жирным шрифтом.

Символ «а» первым встречается 6 раз; символы «в» и «р» — по 4 раза; символы «д», «е», «н», «о» и «т» — по 2 раза; символ «_» — 5 раз. Ввиду того что сортировка фраз осуществлялась в соответствии с лексикографическим порядком первых символов, их последовательность соответствует правой части столбца 2, обозначенного как «1-е символы».

Символы, идущие вслед за первыми символами, приведены в столбце 3. Принцип их формирования поясним на примерах символов, следующих за первыми шестью символами «а» в столбце 2. Поскольку каждая из строк матрицы бы-

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

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

Таблица 4.14. Восстановление данных после преобразования Барроуза–Уиллера

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

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

Строки, в которых последними символами являются символы «а» справа можно дополнить так:

Строка 7 — в . . . . . . . . . . . . . . . а|в;

Строка 6 — в . . . . . . . . . . . . . . . а|в;

Строка 14 — н . . . . . . . . . . . . . . . а|н;

Строка 24 — _ . . . . . . . . . . . . . . . а|_;

Строка 26 — _ . . . . . . . . . . . . . . . а|_;

Строка 28 — _ . . . . . . . . . . . . . . . а|_.

Это означает, что первые два символа в 6 строках столбца 3 (2-е символы) будут соответственно «ав», «ав», «ан», «а_», «а_» и «а_».

Подобным же образом, используя столбец 3, формируются третьи символы, как приведено в столбце 4, поскольку строки, в которых последними символами являются символы «а» справа, можно дополнить так:

Строка 7 — ва . . . . . . . . . . . . а|ва;

Строка 8 — ве . . . . . . . . . . . . а|ве;

Строка 14 — на . . . . . . . . . . . . а|на;

Строка 24 — _д . . . . . . . . . . . . а|_д;

Строка 26 — _н . . . . . . . . . . . . а|_н;

Строка 28 — _т . . . . . . . . . . . . а|_т.

Это означает, что первые три символа в 6 первых строках столбца 3 (2-е символы) будут соответственно «ава», «аве», «ана», «а_д», «а_н» и «а_т».

Таким образом, последовательно шаг за шагом определяются символы в каждой из строк табл. 4.14, в 14-й строке которой формируется искомая последовательность.

Описанный метод восстановления исходной информации весьма сложен и требует значительного объема оперативной памяти.

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

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

Исследуя столбец 4 табл. 4.15, можно увидеть, что строки, перемещенные в соответствии с номерами столбца 3, имеют последние символы, отсортированные в соответствии с лексикографическим порядком. Первые же символы в этом столбце определяют вторые символы строк, приведенных в столбце 2.

Полученная строка номеров строк (см. столбец 5) — T = {7, 8, 14, 24, 26, 28, 2, 4, 12, 17, 9, 21, 25, 27, 3, 5, 6, 20, 0, 1, 13, 16, 18, 19, 10, 11, 15, 22, 23} и является искомым вектором, содержащим номера позиций символов в строке, которую необходимо декодировать (см. столбцы 5 и 6 данной таблицы).

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

T [14] = 3, и первым символом декодируемой строки является символ «н» (см. последний символ в строке 3 столбца 2). Затем определяется номер строки в векторе Т под номером 3.

T [3] = 24, и вторым символом декодируемой строки является символ «а» (см. последний символ в строке 24 столбца 2). Сумма двух символов — «на».

Далее по аналогии:

T [24] = 10 — «_»; T [10] = 9 — «д»; T[9]=17 — «в»; T [17] = 20 — «о»;

T [20] = 13 — «р»; T [13] = 27 — «е»; T [27] = 22 — «_»; T [22] = 18 — «т»; T [18] = 0 - «р»; T [0] = 7 — «а»; T [7] = 4 — «в»; T [4] = 26 — «а»;

T [26] = 15 — «_»; T [15] = 5 — «н»; T [5] = 28 — «а»; T [28] = 23 — «_»; T [23] = 19 — «т»; T [19] = 1 — «р»; T [1] = 8 — «а»; T [8] = 12 — «в»;

T [12] = 25 — «е»; T [25] = 11 — «_»; T [11] = 21 — «д»; T [21] = 16 — «р»; T [16] = 6 — «о»;T [6] = 2 — «в»; T [2] = 14 — «а».

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

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

–предварительное алгоритмическое преобразование с формированием различного вида спектров сигналов.

4.3.1. Кодирование с предсказанием

Широкое применение имеют методы кодирования с предсказанием (так называемая дифференциальная импульсно-кодовая модуляция ДИКМ).

ДИКМ очень близко связана с условным кодированием. Однако в данном случае вместо кодирования и передачи значения N -го пиксела bN , передается

ранее переданных пикселов b1, b2, ..., bN −1 (рис. 4.6).

Это означает, что предсказываемое значение N -го пиксела вычисляется на передаче с использованием формулы, включающей линейную комбинацию значений нескольких предыдущих пикселов [2.4, 2.56, 2.65–2.70].

4.3. Кодирование с преобразованием

Рис. 4.6. Структура системы кодирования с предсказанием

Результатом вычисления является некая оценка («предсказание») значения N -го пиксела, которое, естественно, отличается от его истинного значения.

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

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

предсказанное значение -го пиксела ˆN , используя значения нескольких преды-

N b

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

-го пиксела N −ˆN , полученное им из канала от передатчика, и сформировать

N b b

таким образом истинное значение N -го пиксела.

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

Энтропия такого дифференциального сигнала мала, и, следовательно, мал битовый поток, необходимый для кодирования информации.

Например, эффективным является предсказатель, вычисляющий ˆN

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

4.3. Кодирование с преобразованием

Обычно применяется линейное преобразование [4, 56, 65, 70–72]:

N

где bm — коды, характеризующие исходный блок пикселов изображения, cj — коды, характеризующие преобразованные величины, tmj = T — матрица преобразования.

В матричной форме это преобразование и обратное преобразование можно записать в виде:

c = Т × b, b = Т−1 × c.

Главная цель преобразования — сделать как можно больше преобразованных величин cj настолько малыми, чтобы они стали несущественными и не требовали бы кодирования и передачи.

Другой целью такого преобразования является минимизация статистических зависимостей между ci и cj (i = j), что обеспечивает само по себе устранение избыточности информации.

Если обратная матрица T−1 равна транспонированной T (T−1 = T ), то преобразование является ортонормированным, или унитарным.

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

Унитарное преобразование сохраняет энергию сигнала, т. е.

Это соотношение известно как равенство Парсеваля [2.4].

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

H(b) = H(c) бит/блок.

К тому же, если преобразование устраняет статистическую зависимость между преобразованными величинами {c1, . . . , cN }, то

N

H(c) = H(cm)бит/блок.

m=1

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