3.4.4. Переупорядочение и кодирование нулей

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

3.4.4.1. DCT

Распределение коэффициентов. Значимые коэффициенты преобразования DCT блока изображения или его компенсированного остатка обычно группируются в «низкочастотной области», т.е. в районе коэффициента DC с координатами (0,0). На рис. 3.38 построен график частоты ненулевых коэффициентов DCT в каждой из позиций блока 8 х 8 в остаточном кадре формата QCIF (рис. 3.6). Ненулевые коэффициенты DCT образуют кластер вокруг левого верхнего коэффициента (DC) с примерно симметричным распределением вдоль диагонали блока.

Рис. 3.38. Распределение коэффициентов DCT 8x8 (кадр).

Рис. 3.39. Часть остаточного кадра

Для части остаточного кадра (рис. 3.39) на рис. 3.40 построен такой же график распределения ненулевых коэффициентов DCT. В этом случае ненулевые коэффициенты так же группируются около коэффициента DC, но картина несколько перекошена» т.е. больше ненулевых коэффициентов локализовано у левой стороны блока. Это связано с тем, что рассмотренная часть изображения имеет большую высокочастотную компоненту по вертикальной оси (в силу подсэмплирования в вертикальном направлении), и в результате образуются большие значения коэффициентов DCT, отвечающих за вертикальные частоты (см. рис. 3.27).

Сканирование. После квантования коэффициенты DCT блока необходимо переупорядочить в группы ненулевых элементов, эффективно представляя оставшиеся квантованные нулевые коэффициенты. Оптимальное переупорядочение (порядок сканирования) зависит от распределения ненулевых коэффициентов DCT. Для типичного блока изображения с распределением, показанным на рис. 3.38, подходящим порядком является зигзагообразное сканирование с началом в коэффициенте DC верхний левый угол). При таком порядке сканирования все квантованные коэффициенты двухмерного блока располагаются в одномерном массиве, показанном на рис. 3.41. Ненулевые коэффициенты имеют тенденцию группироваться вместе в начале этого массива, за которыми будет следовать длинная последовательность нулевых коэффициентов. Сканирование зигзагом может не быть идеальным порядком для части изображения (например, на рис. 3.39) из-за перекошенности распределения коэффициентов (рис. 3.40). В этом случае больше подходит модифицированный порядок сканирования, например показанный на рис. 3.42, при котором коэффициенты в левой части блока сканируются раньше симметричных им пар в правой части блока.

Рис. 3.40. Распределение коэффициентов DCT 8x8 (часть кадра).

Кодирование серия-значение. На выходе процедуры переупорядочения создается массив, обычно состоящий из одного или нескольких кластеров ненулевых коэффициентов, группирующихся с высокой степенью вероятности в начале массива, за которыми следуют серии нулевых коэффициентов. Длинные серии нулевых элементов можно кодировать компактным образом, если, например, представлять весь массив в виде последовательности пар («серия», «значение»), где «серия» обозначает число последовательных нулей, за которыми следует ненулевой элемент, величина которого задается числом «значение».

Рис. 3.41. Сканирование зигзагом (кадр).

Рис. 3.42. Сканирование зигзагом (часть кадра).

Высокочастотные коэффициенты DCT часто квантуются в нули, поэтому переупорядоченные блоки будут часто заканчиваться сериями из одних нулей. Для этого необходимо предусмотреть специальный символ, указывающий на последний ненулевой элемент переупорядоченного массива. При «двухмерном» кодировании символами вида («серия», «значение») каждая пара кодируется так, как указано выше, и еще используется некоторый выделенный кодовый символ - «конец», указывающий на завершение ненулевых коэффициентов в массиве. При «трехмерном» кодировании каждый символ состоит из трех компонент («серия», «значение», «конец»). В рассмотренном выше примере, если последним ненулевым коэффициентом было число -7, то соответствующие трехмерные символы:

(0,16,0), (2,-3,0), (0,5,0), (0,6,0), (4,-7,1).

Число 1 в последнем коде указывает на завершающий ненулевой коэффициент блока.