3.5.2.2. Кодирование Хаффмана с предварительными вычислениями

Кодирование Хаффмана имеет два недостатка, которые проявляются при его реализации на практике в видеокодеках. Во-первых, декодер должен использовать то же самое семейство кодов. Передача информации, содержащейся в таблице вероятностей, потребует дополнительных битов, что сокращает степень сжатия, особенно при кодировании коротких видеофрагментов. Во-вторых, таблицу вероятностей для длинной видеопоследовательности (необходимую для построения дерева Хаффмана) можно определить только после просмотра всей видеопоследовательности. Это может привести к недопустимой задержке процесса кодирования, передачи и воспроизведения видео на приемном конце. По этим причинам современные стандарты кодирования изображений и видео определяют множества кодовых слов, исходя из распределения вероятностей для некоторого «обобщенного» видеоматериала. Следующие два примера таблиц кодов VLC с предварительным вычислением взяты из стандарта MPEG-4 Video (простой профиль).

Таблица 3.6. Коды VLC для коэффициентов преобразования в MPEG-4 Video (TCOEF) (приведены все коды <9 бит).

Конец	Серия	Значение Код
0	0	1 10s
0	1	1 110s
0	2	1 1110s
0	0	2 1111s
1	0	1 0111s
0	3	1 01101s
0	4	1 01100s
0	5	1 01011s
0	0	3 010101s
0	1	2 010100s
0	6	1 010011s
0	7	1 010010s
0	8	1 010001s
0	9	1 010000s
1	1	1 001111s
1	2	1 001110s
1	3	1 001101s
1	4	1 001100s
0	0	4 0010111s
0	10	1 0010110s
0	11	1 0010101s
0	12	1 0010100s
1	5	1 0010011s
1	6	1 0010010s
1	7	1 0010001s
1	8	1 0010000s
ESCAPE ...		0000011s

Коэффициенты преобразования (TCOEF). Стандарт MPEG-4 Video использует трехмерное кодирование квантованных коэффициентов, при котором каждый элемент представляется комбинацией («серия», «значение», «конец»). Всего имеется 102 такие комбинации, и первый 26 кодовых слов VLC для них показаны в табл. 3.6.

Остальные 76 кодовых слов VLC имеют длину до 13 бит. В конце каждого кодового слова стоит бит s, обозначающий знак декодируемого коэффициента (0 — положительный, 1 — отрицательный). Если комбинация («серия», «значение», «конец») отсутствует в этом списке, то ее кодируют с помощью ESCAPE-последовательиости, т.е. ставится специальный код ESCAPE (0000011), за которым следует 13 битовый код фиксированной длины, описывающий эту тройку («серия», «значение», «конец»).

Некоторые коды из табл. 3.6 представлены в форме дерева на рис. 3.47. Кодовые слова, содержащие более восьми подряд идущих нулей, не допускаются, поэтому любое слово, начинающееся на 000000000, указывает на ошибку в потоке битов (или, возможно, на стартовый код, который начинается длинной последовательностью нулей и может появиться в любом месте последовательности). Все остальные последовательности битов могут быть корректно декодированы. Отметим, что самые короткие коды присвоены коротким сериям и малым значениям (например, код 10s соответствует серии 0 и значению ±1), поскольку такие элементы встречаются чаще всего.

Таблица 3.7. Коды VLC для разностей векторов движения в MPEG-4.

MVD	Код
0	1
+0,5	010
-0,5	011
+1	0010
-1	0011
+ 1,5	00010
-1,5	00011
+2	0000110
-2	0000111
+2,5	00001010
-2,5	00001011
+3	00001000
-3	00001001
+3,5	00000110
-3,5 ...	00000111 ...

Разность векторов движения (MVD). Разностные векторы компенсации движения кодируются в виде пары VLC: первый код для -компоненты и второй — для компоненты . Часть этих кодов приведена в табл. 3.7. Остальные 49 кодов (с длиной бит от 8 до 13) здесь не приводятся. Отметим, что самые короткие коды отвечают малым разностям векторов движения (например, вектор MVD=0 представлен кодом в один бит 1).

Рис. 3.47. Коды VLC MPEG-4 TCOEF (часть кодов).

Коды этой таблицы весьма близки к «истинным» кодам Хаффмана, так как каждому символу присвоен единственный код, часто встречающимся элементам приписаны более короткие коды и никакой код из таблицы не является префиксом другого кода этой же таблицы. Главное отличие этих кодов от «истинных» кодов Хаффмана заключается в том, что они построены на основе предварительных вычислений с использованием «обобщенных» распределений вероятностей и в случае TCOEF только 102 наиболее часто встречающихся элемента имеют код переменной длины, а всем остальным элементам присваиваются коды фиксированной длины.