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

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

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

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

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

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