Раздел: Документация
0 ... 29 30 31 32 33 34 35 ... 122 ющихся элемента имеют код переменной длины, а всем остальным элементам присваиваются коды фиксированной длины. 3.5.2.3. Другие коды переменной длины Наряду с кодами Хаффмана существует множество других семейств кодов VLC, которые могут быть полезными в приложениях кодирования видео. Серьезным недостатком кодов, построенных на основе схемы Хаффмана, является их чувствительность к ошибкам. Искажение в одном бите последовательности этих кодов может привести к полной потери синхронизации при декодировании и к невозможности дальнейшего правильного декодирования последовательности. Обратимые коды VLC (RVLC, Reversible Variable Length Codes), которые можно успешно декодировать в прямом и обратном направлении, способны исправить такую ошибку (см. § 5.3). Недостаток предварительно вычисленных кодов (см. табл. 3.6 и 3.7) состоит в том, что и кодер, и декодер должны хранить эти таблицы в какой-то подходящей форме. Альтернативный подход заключается в использовании кодов, генерируемых автоматически («на лету»), если известен входной символ. Экспоненциальные коды Голомба (Ехр-Golomb), попадающие в эту категорию, будут описаны в гл. 6. 3.5.3. Арифметическое кодирование Схема кодирования с переменной длиной кода, описанная в § 3.5.2, имеет главный недостаток, который заключается в том. что символам приписываются фиксированные кодовые слова, имеющие целую длину бит. Такой метод может быть только подоптимальным, так как число бит. обеспечивающее наилучший теоретический результат, зависит от информационной емкости, которая часто бывает нецелым числом. Степень сжатия, достигаемая кодами переменной длины, становится особенно малой при работе с символами, имеющими вероятность больше 0,5, так как в этом случае наименьшая допустимая длина кода равна 1 биту. Арифметическое кодирование является весьма эффективной альтернативой кодам Хаффмана. С их помощью можно плотнее приблизиться к теоретически наилучшим границам сжатия статистических данных [8]. Арифметический кодер преобразует исходную последовательность символов в одно-единственное действительное число, которое приближается к теоретическому оптимальному нецелому числу бит, необходимому для представления каждого символа последовательности. 3.5. Энтропийный кодер Пример- В табл. 3.8 приведены 5 векторов движения (—2. —1,0.1,2) вместе с их вероятностями из примера 1 в § 3.5.2. Каждому вектору приписывается подынтервал в пределах от 0.0 до 1,0, длина которого совпадает с вероятностью появления данного вектора. В зтом примере вектор (—2) имеет вероятность 0,1, и ему приписан подннтервал (0;0.1) (т.е. 10% от обшей длины интервала (0,0; 1,0)). Вектор (-1) имеет вероятность 0,2, и ему отведено 20% от общего интервала — подннтервал (0.1;0.3). После назначения подынтервалов каждому вектору весь интервал (0.0:1.0) оказывается разделенным между символами данных (векторами в нашем случае) в соответствии с их вероятностями (рис. 3.48). Весь интервал Ы-1-1—ь- (-2) (-1)(0)(И) <*2) Рис. 3.48. Разбиение на подынтервалы. Процедура кодирования длл последовательности векторов (0,-1,0.2).
После кодирования очередного символа интервал (L. Н) постепенно уменьшается. В конце процедуры кодирования (четыре шага в этом примере) у нас остается некоторый конечный интервал. Вся исходная последовательность сим- Декод. Процедура декодированияИнтервал Подынтервал символ
Таблица 3.8. Векторы движения, вероятности и подынтервалы (последовательность №1). Вектор Вероятность р log2(l/p) Подынтервал
волов может быть закодирована любым числом из этого интервала. В предыдущем примере достаточно передать любое число из интервала от 0,3928 до 0,396, например, 0,394. На рис. 4.49 изображен процесс последовательного разделения исходного интервала иа все более мелкие интервалы по мере обработки символов исходной последовательности. После кодирования первого символа (вектора 0) новым интервалом стал (0,3; 0,7). Следующий символ (вектор —1) выбирает новый интервал (0,34; 0,42) и т.д. Последний символ (вектор -2) выбирает интервал (0,3928; 0,396), и передаваемое число 0,394 попадает в этот интервал. Число 0,394 можно представить в виде десятичного числа с фиксированной десятичной точкой, для чего потребуется 9 бит. В итоге исходная последовательность (0, —1,0,2) будет закодирована в сжатом виде кода из 9 бит. Процедура декодирования. 0 ... 29 30 31 32 33 34 35 ... 122
|
