Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


6.4.13. Энтропийное кодирование

Синтаксические элементы выше уровня слоев кодируются двоичными кодами фиксированной или переменной длины. Элементы слоев и последующие элементы кодируются или с помощью кодов переменной длины VLC, или по схеме контекстно-адаптивного кодирования переменной длины CAVLC. Все остальные единицы переменной длины кодируются с использованием экспоненциальных кодов Голомба. Параметры, которые необходимо закодировать и передавать, представлены в табл. 6.8.

Таблица 6.9. Экспоненциальные коды Голомба.

code_num

Кодовое слово

0

1

1

010

2

011

3

00100

4

00101

5

00110

6

00111

7

0001000

8

...

0001001

6.4.13.1. Кодирование экспоненциальными кодами Голомба

Экспоненциальные коды Голомба [5] представляют собой коды переменной длины весьма регулярной конструкции. Изучив первые несколько кодовых слов (табл. 6.9), становится ясно, что эти коды строятся следующим образом:

,

где INFO — поле из M бит, несущих информацию. Первое кодовое слово не имеет нулей в начале и в конце. Кодовые слова 1 и 2 имеют однобитовое поле INFO, кодовые слова 3 - 6 имеют двухбитовое поле INFO и т.д. Длина каждого кодового слова экспоненциального кода Голомба равна (2М + 1) бит, и каждое кодовое слово может быть построено кодером на основе его индекса code_num по правилу:

Кодовое слово декодируется следующим образом.

1. Сосчитать М начальных нулей идущих до 1.

2. Прочитать поле INFO длины М.

3. .

(Для кодового слова 0 переменные INFO и М равны нулю.)

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

Тип

Описание

ue

Прямое отображение без знака, code_num = k. Используется для типа макроблока, индекса ссылочного кадра и для других кодов

te

Вариант таблицы кодовых слов экспоненциального кода Голомба, в которой обрезаны короткие кодовые слова

se

Отображение со знаком, которое используется для разности векторов движения, дельты PQ и для других кодов. Число k отображается в code_num по правилу (см. табл. 6.10):

code_num = 2|k| (k < 0),

 code_num = 2|k| - 1 (k > 0)

me

Табличное задание: число k отображается в code_num по правилу, предписанному стандартом. В табл. 6.11 приведена часть таблицы кодов coded_block_pattern для прогноза макроблоков в моде inter, указывающих, какой блок 8x8 содержит ненулевые коэффициенты

Таблица 6.10. Отображение со знаком se.

k

code_num

0

0

1

1

-1

2

2

3

-2

4

3

5

Таблица 6.11. Часть таблицы для coded_block_pattern.

coded_block_pattern (прогноз inter)

code_num

0 (нет ненулевых блоков)

0

16 (блок хроматических коэфф. DC ненулевой)

1

1 (верхний левый блок яркости 8x8 ненулевой)

2

2 (верхний правый блок яркости 8x8 ненулевой)

3

4 (нижний левый блок яркости 8x8 ненулевой)

4

8 (нижний правый блок яркости 8x8 ненулевой)

5

32 (хроматические блоки DC и АС ненулевые)

6

3 (верхние левый и правый блоки яркости 8x8 ненулевые)

7

Каждое из этих отображений (ue, te, se и me) разработано в целях построения коротких кодовых слов для часто возникающих значений параметров и более длинных для более редких. Например, типу inter-макроблока P_L0_16х16 (прогноз блока яркости 16x16 по предыдущему снимку) присваивается code_num 0, поскольку он встречается весьма часто; типу макроблока P_L0_8x8 (прогноз блока яркости 8x8 по предыдущему снимку) присваивается code_num 3, так как он встречается реже. Часто возникающее значение 0 разности векторов движения (MVD) отображается в code_num 0, а более редкому значению MVD = -3 ставится в соответствие code_num 6.

6.4.13.2. Контекстно-адаптивные коды переменной длины (CAVLC)

Этот метод используется при кодировании остаточных блоков 4x4 (или 2x2) коэффициентов преобразования, просканированных по зигзагу. Схема кодирования CAVLC (Context-Based Adaptive Variable Length Coding) разработана с учетом нескольких характеристик квантованных блоков 4x4.

1. Обычно после прогноза, преобразования и квантования блоки становятся весьма разреженными (в них содержится много нулевых коэффициентов). CAVLC использует схему кодирования "серия-значение» для компактного представления серий нулевых коэффициентов.

2. При сканировании зигзагом завершающими ненулевыми элементами часто выступают числа ±1. Поэтому CAVLC подает сигналы о количестве таких элементов («остаточных единиц» Trailing Ones) в сжатом виде.

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

4. Амплитуда (Level) ненулевых коэффициентов обычно является высокой только в начале переупорядоченного массива (около коэффициентов DC), а далее она снижается в области высоких частот. CAVLC учитывает это свойство, приспосабливая выбор поисковой таблицы VLC для амплитуды параметров в зависимости от недавно закодированных амплитуд соседних блоков.

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

coeff_token

Кодируется число ненулевых коэффициентов (TotalCoeff) н TrailingOnes (по одному на блок)

erailing_ones_sign_flag

Знак величины TrailingOne (по одному на остаточную единицу)

level-prefix

Первая часть кода ненулевого коэффициента

(по одной на коэффициент, исключая «остаточные

единицы»)

level_suffix

Вторая часть кода ненулевого коэффициента (присутствует не всегда)

total_zeros

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

run-before

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

1. Кодирование числа коэффициентов и "серий единиц» (coeff_token). Первый код VLC, coeff_token, одновременно кодирует общее число ненулевых коэффициентов (TotalCoeff) и число остаточных единиц ±1 (TrailingOnes). Переменная TotalCoeff может принимать любое значение от 0 (нет ни одного коэффициента в блоке 4 х 4) до 16 (16 ненулевых коэффициентов). Переменная (TrailingOnes) может быть любой от 0 до 3. Если имеется более трех элементов ±1, то лишь последние три из них рассматриваются в этом виде, а все прочие кодируются как обычные коэффициенты.

Таблица 6.12. Выбор поисковой таблицы для coeff_token.

N

Таблица для coeff_token

0, 1

Таблица 1

2, 3

Таблица 2

4, 5, 6, 7

Таблица 3

8 и более

Таблица 4

Всего имеется четыре способа выбора поисковой таблицы, которая используется при кодировании coeff_token для блоков 4x4: три таблицы кодов переменной длины и одна таблица кодов фиксированной длины. Выбор таблицы зависит от числа ненулевых коэффициентов ( и ), ранее закодированных, блоков слева и выше (А и В соответственно) от текущего блока С. Параметр  вычисляется по следующему правилу. Если блоки А и В оба доступны (т.е. находятся в том же слое), то . Если доступен только верхний блок, то , если только левый, то , и, наконец, если оба недоступны, то .

Параметр  выбирает таблицу кодов VLC (см. табл. 6.12) в зависимости от числа закодированных коэффициентов соседних блоков (в этом заключается контекстная адаптация метода). Таблица 1 смещена в сторону малого числа коэффициентов так, чтобы малым значениям TotalCoeff присваивались короткие коды, а большим — длинные. Таблица 2 построена из расчета промежуточного числа коэффициентов (величинам TotalCoeff в районе 2 - 4 присваиваются короткие коды). Таблица 3 применяется для кодирования большого числа коэффициентов, а таблица 4 присваивает фиксированный код длины 6 каждой паре значений TotalCoeff и TrailingOnes.

2. Кодирование знака каждой переменной TrailingOne. Для каждого TrailingOne (элемент ±1), указанного в coeff_token, его знак кодируется единственным битом (0 = +, 1 = -) в обратном порядке, начиная с самого высокочастотного TrailingOne.

3. Кодирование амплитуды остальных ненулевых коэффициентов. Амплитуда (знак и модуль) каждого из оставшихся ненулевых коэффициентов блока кодируется в обратном порядке, начиная с высоких частот и двигаясь назад в сторону коэффициента DC. Код для каждого значения состоит из префикса (level-prefix) и суффикса (level_suffix). Длина суффикса (suffixLength) может быть от 0 до 6 бит, suffixLength выбирается в зависимости от амплитуды каждого последующего кодового уровня («адаптация к контексту»). Малая suffixLength подходит для уровней с низкой амплитудой, а большая величина suffixLength приспособлена для высокой амплитуды. Выбор suffixLength делается по следующим правилам.

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

б) Кодировать самый высокочастотный ненулевой коэффициент.

в) Если амплитуда этого коэффициента больше, чем предопределенный порог, то увеличить suffixLength на 1. (Если это первый уровень кодирования и величина suffixLength была равна 0, то присвоить suffixLength значение 2.)

Таблица 6.13. Пороги для определения, надо ли повышать suffixLength.

Текущий suffixLength

Порог для повышения suffixLength

0

0

1

3

2

6

3

12

 

24

5

48

6

N/А (наибольшая suffixLength)

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

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

5. Кодирование каждой серии нулей. Число нулей, предшествующее каждому ненулевому коэффициенту (run_before), кодируется в обратном порядке. Кодируется параметр run_before для каждого ненулевого коэффициента, начиная с самого старшего (высокочастотного). При этом имеется два исключения:

1. если уже не осталось нулей для кодирования (т.е. выполнено соотношение ), то уже не надо кодировать величины run_before;

2. не нужно кодировать run_before для последнего (самого высокочастотного) ненулевого коэффициента.

Выбор кода VLC для каждой серии нулей делается в зависимости от числа нулей, которые еще не были закодированы (ZerosLeft), и от run_before. Например, если осталось закодировать только два нуля, переменная run_before может принимать только три значения (0, 1 или 2), и, следовательно, длина кода VLC не превышает двух бит. Если осталось закодировать шесть нулей, то run_before может принимать семь значений (от 0 до 6) и таблица VLC не будет, соответственно, длиннее.

Приведем несколько примеров кодирования и декодирования по схеме CAVLC.

Пример

Блок 4x4:

Переупорядоченный массив:

0, 3, 0, 1, -1 ,-1, 0, 1, 0, ...

TotalCoeffs = 5

(ненулевые коэффициенты проиндексированы от 4 до 0, от наибольшей частоты к наименьшей) total_zeros = 3 TrailingOnes = 3

(на самом деле, имеется четыре остаточные единицы, но только три из них можно закодировать «специальным» способом).

Кодирование.

Элемент

Величина

Код

coeff_token

TotalCoeffs = 5.

0000100

 

TrailingOnes = 3 (Таблица 1)

 

TrailingOne sign (4)

+

0

TrailingOne sign (3)

-

1

TrailingOne sign (2)

-

1

Level (1)

+ 1 (suffixLength = 0)

1 (prefix)

Level (0)

+3 (suffixLength = 1)

001 (prefix) 0 (suffix)

total_zeros

3

111

run_before (4)

ZerosLeft = 3; run_before = 1

10

run-before (3)

ZerosLeft = 2; run_before = 0

1

run-before (2)

ZerosLeft = 2; run_before = 0

1

run_before (1)

ZerosLeft = 2; run_before = 1

01

run-before (0)

ZerosLeft = 1; run_before = 1

Код не требуется.

Для этого блока передается поток битов: 000010001110010111101101.

Декодирование.

Код

Элемент

Величина

Выходной массив

0000100

coeff_token

TotalCoeffs = 5,

Пустой

 

 

TrailingOnes = 3

 

0

TrailingOnes sign

+

1

1

TrailingOnes sign

-

-1,1

1

TrailingOnes sign

-

-1,-1,1

1

Level

+1 (suffixLength = 0,

1,-1,-1,1

 

 

увеличить suffixLength

 

 

 

после декодирования)

 

0010

Level

+3 (suffixLength = 1)

3,1,-1,-1,0,1

111

total_zeros

3

3,1,-1,-1,1

10

run_before

1

3,1,-1,-1,2,1

1

run_before

0

3,1,-1,-1,0,1

1

run_before

0

3,1,-1,-1,0,1

01

run_before

1

3,2,1,-1,-1,0,1

Декодер уже вставил два нуля, переменная total_zeros равна 3, в поэтому еще один нуль вставляется перед младшим коэффициентом. В итоге выходной массив имеет вид:

2,3,0,1,-1,-1,0,1.

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

Пример

Блок 4x4:

Переупорядоченный массив:

-2, 4, 3, -3,0, 0, -1, ...

TotalCoeffs = 5

(ненулевые коэффициенты проиндексированы от 4 до 0, от наибольшей частоты к наименьшей)

total_zeros = 2

TrailingOnes = 1

Кодирование.

Элемент

Величина

Код

coeff_token

TotalCoeffs = 5, TrailingOnes = 1

0000000110

 

(Таблица 1)

 

TrailingOnes sign (4)

--

1

Level (3)

Посылается как -2

0001(prefix)

 

(см. замечание 1)

 

 

(suffixLength = 0; увеличить

 

 

suffixLength на 1)

 

Level (2)

3 (suffixLength = 1)

001(prefix)0(suffix)

Level (1)

4 (suffixLength = 1; увеличить

0001(prefix)0(suffix)

 

suffixLength на 1

 

Level (0)

-2 (suffixLength = 2)

1(prefix)11(suffix)

total_zeros

2

0011

run_before(4)

ZerosLeft = 2; run_before = 2

00

run_before(3..0)

0

Код не требуется.

Для этого блока передается поток: 000000011010001001000010111001100.

Замечание 1. Величина Level (3) со значением -3 кодируется особым образом. Если имеется менее трех элементов TrailingOnes, то первый элемент (не TrailingOne) не может иметь значения ±1 (в противном случае его кодировали бы как TrailingOne). Поэтому для сохранения битов его величина (Level) увеличивается на 1 для отрицательных значений (соответственно, уменьшается на 1 для положительных). Таким образом, ±2 отображается в ±1, а ±3 отображается в ±2 и т.д. В итоге будут использоваться более короткие коды VLC.

Замечание 2. После кодирования Level (3) номер таблицы для level_VLC увеличивается на 1, так как эта амплитуда выше первого порога (который равен 0). После кодирования Level (1) со значением 4 номер таблицы опять повышается, поскольку Level (1) выше второго порога (равного 3). Заметим, что последний Level (-2) кодируется другим кодом VLC по сравнению с первым закодированным значением (который был тоже равен -2).

Декодирование.

Код

Элемент

Величина

Выходной массив

00000001100

coeff_token

TotalCoeffs = 5, TrailingOnes = 1

Пустой

1

TrailingOnes sign

--

-1

0001

Level

-2 декодируется как -3

-3,1

0010

Level

+3

+3,-3,-1

00010

Level

+4

+4,3,-3,-1

111

Level

-2

-2,4,3,-3,-1

0011

total_zeros

2

-2,4,3,-3,-1

00

run_before

2

-2,4,3, -3,0,0, - 1

Все нули теперь закодированы, и выходной массив имеет вид:

-2, 4, 3,-3 ,0, 0, -1.

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

 

 

Пример

Блок 4x4:

Переупорядоченный массив:

0, 0, 0, 1, 0 ,1, 0, 0, 0, -1, 0...

TotalCoeffs = 3 (ненулевые коэффициенты проиндексированы от 2 до 0)

total_zeros = 7

TrailingOnes = 3

Кодирование.

Элемент

Величина

Код

coeff_token

TotalCoeffs = 3,

00011

 

TrailingOnes = 3 (Таблица 1)

 

TrailingOne sign (2)

-

1

TrailingOne sign (1)

+

0

TrailingOne sign (0)

+

0

total_zeros

7

011

run_before (2)

ZerosLeft = 7; run_before = 3

100

run_before (1)

ZerosLeft = 4; run_before = 1

10

run-before (0)

ZerosLeft = 3; run_before = 3

Код не требуется;

 

 

последний коэфф.

Битовый поток этого блока: 0001110001110010.

Декодирование.

Код

Элемент

Величина

Выходной массив

00011

coeff_token

TotalCoeffs = 3.

Пустой

 

 

TrailingOnes = 3

 

1

TrailingOnes sign

-

-1

0

TrailingOnes sign

+

1, -1

0

TrailingOnes sign

+

1,1,-1

011

total_zeros

7

1,1,-1

100

run_before

3

1,1,0,0,0,1

10

run_before

1

1,0,1,0,0,0,1

Декодер вставил четыре нуля, переменная total_zeros равна 7, и поэтому еще три нуля вставляются перед младшим коэффициентом:

0, 0, 0, 1, 0,1, 0, 0, 0, -1.

 



<< ПредыдущаяОглавлениеСледующая >>