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

Прежде всего обсудим пункт 3 из конца предыдущего параграфа. Каждая матрица 8x8 квантованных коэффициентов DCT содержит коэффициент DC [в позиции (0,0) в левом верхнем углу], а также 63 коэффициента АС. Коэффициент DC равен среднему значению всех 64 пикселов исходной единицы. Наблюдения показывают, что при сжатии непрерывно-тоновых изображений, коэффициенты DC соседних единиц обычно являются коррелированными. Известно, что этот коэффициент равен сумме всех пикселов блока с некоторым общим множителем. Все это указывает на то, что коэффициенты DC близких блоков не должны сильно различаться. Поэтому JPEG записывает первый (закодированный) коэффициент DC, а затем кодирует разности коэффи циентов DC последовательных блоков.

Пример: Если первые три единицы данных размера 8x8 имеют квантованные коэффициенты DC равные 1118, 1114 и 1119, то JPEG записывает для первого блока число 1118 (закодированное по Хаффману, см. далее), за которым следует 63 закодированных коэффициента АС. Для второго блока на выходе будет стоять число  (также кодированное по Хаффману) впереди 63 (кодированных) коэффициента АС этого блока. Третьему блоку будет соответствовать кодированная запись  и следующие 63 коэффициента АС. Этот путь также позволяет меньше беспокоиться о проблемах, связанных с переполнением, так как разности обычно малы.

Кодирование разностей коэффициентов DC совершается с помощью табл. 3.53. В этой таблице записаны так называемые унарные коды, которые определяются следующим образом. Унарный код неотрицательного целого числа  состоит из строки в  единиц, за которыми следует один 0 или, наоборот,  нулей и одна 1. Длина унарного кода целого числа  равна  бит.

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

Табл. 3.53. Кодирование разностей коэффициентов DC.

Первый коэффициент DC из нашего примера, который следует закодировать, равен 1118. Он находится в строке 11 и столбце 930 таблицы (столбцы занумерованы, начиная с нулевого). Тогда оно кодируется последовательностью 111111111110|01110100010 (унарный код строки 11, за которым следует двоичное представление числа 930 из 11 бит). Вторая разность коэффициентов DC, число -4, расположена в строке 3 и столбце 3; она кодируется в виде 1110|011 (унарный код строки 3 и число 3 в виде 3 бит). Третья разность 5 расположена в строке 3, столбец 5, поэтому ее кодом служит 1110|101.

Разберемся теперь с пунктом 2 предыдущего параграфа, когда надо кодировать 63 коэффициента АС. Это сжатие использует кодирование RLE в сочетании с методом Хаффмана или с арифметическим кодированием. Идея заключается в том, что в последовательности коэффициентов АС, как правило, имеется всего несколько ненулевых элементов, между которыми стоят серии нулей. Для каждого ненулевого числа  (1) кодер определяет число Z предшествующих ему нулей; (2) затем он находит число  в табл. 3.53 и готовит номер строки и столбца (R и С); (3) пара пара (R, Z) (не (R, С)!) используется для нахождения соответствующего числа по строке и столбцу в табл. 3.54; (4) наконец, полученный из этой таблицы код Хаффмана присоединяется к С (где С записывается в виде R-битного числа); результатом этих действий служит код, выдаваемый на выход кодером JPEG для этого АС коэффициента  и всех предыдущих нулей. (Можно перевести дух.)

Табл. 3.54. Кодирование коэффициентов АС.

В табл. 3.54 приведен некоторый произвольный код Хаффмана, не тот, который предлагается комитетом JPEG. А стандарт JPEG рекомендует использовать для этих целей коды из табл. 3.55 и 3.56. При этом разрешается использовать до четырех таблиц Хаффмана, за исключением моды базелины, когда можно использовать только две таблицы. Читатель обнаружит код ЕОВ в позиции (0,0) и код ZRL в позиции (0,15). Код ЕОВ означает конец блока, а код ZRL замещает 15 последовательных нулей, когда их число превышает 15. Эти коды рекомендованы для компонентов светимости (табл. 3.55). Коды ЕОВ и ZRL, рекомендованные для коэффициентов АС хроматических компонентов из табл. 3.56 равны 00 и 1111111010, соответственно.

Пример: Еще раз рассмотрим последовательность

Первый АС коэффициент  не имеет перед собой нулей, то есть, для него . Он находится в табл. 3.53 в строке 2 и столбце 2, поэтому, для него , . Код Хаффмана из табл. 3.54 в позиции  равен 01. Значит, окончательный код для  будет 01|10. Следующий ненулевой коэффициент -2 имеет один предшествующий нуль, то есть, для него . Он стоит в табл. 3.53 в строке 2 и столбце 1, тогда , . Код Хаффмана из табл. 3.54 в позиции  равен 11011. В итоге кодом числа -2 будет служить последовательность 11011|01. Последний ненулевой коэффициент АС равен -1, ему предшествует 13 нулей, и . Сам коэффициент расположен в табл. 3.53 в строке 1 и столбце 0, то есть,  , . Пусть в табл. 3.54 в позиции  находится код 1110101. Тогда кодом для -1 будет 1110101|0.

R

Табл. 3.55. Рекомендованные коды Хаффмана для коэффициентов АС светимости.

Наконец, хвост из последних нулей кодируется как 1010 (ЕОВ, конец блока). Значит, выходом для всех коэффициентов АС будет последовательность 01101101110111010101010. Мы ранее установили, что кодом коэффициентом DC станет двоичная последовательность 111111111110|1110100010. Итак, окончательным кодом всего 64-пиксельного блока данных будет 46-битовое числоe

111111111110111010001001101101101111010101010.

Эти 46 бит кодируют одну цветную компоненту единицы данных. Предположим, что две остальные компоненты будут также закодированы 46-битовыми числами. Если каждый пиксел исходно состоял из 24 бит, то получим фактор сжатия равный ; очень неплохой результат!

R

Табл. 3.56. Рекомендованные коды Хаффмана для коэффициентов АС хроматических компонент.

Те же таблицы (3.53 и 3.54) должны быть использованы декодером для восстановления блока данных. Они задаются по умолчанию кодеком JPEG, или могут быть специально построены для данного конкретного изображения на предварительном проходе. Однако сам JPEG не предусматривает алгоритма для построения таких таблиц. Конкретный кодек может самостоятельно сделать это.

Некоторые варианты JPEG предусматривают использование версии с арифметическим кодированием, которая называется кодированием QM. Это кодирование также устанавливается стандартом JPEG. Этот метод является адаптивным и для его работы не требуются таблицы 3.53 и 3.54. Он приспосабливает схему кодирования к статистическим свойствам конкретного изображения по мере его обработки. С помощью арифметического кодирования можно улучшить показатели компрессии метода Хаффмана на 5-10% для типичного непрерывно-тонового изображения. Однако этот метод имеет весьма сложную реализацию по сравнением с методом Хаффмана, поэтому он редко используется в приложениях.