Кодирование

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

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

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

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

0 1	0 -1	1								0 10
2	-3	-2	2	3						110
3	-7	-6	-5	-4	4	5	6	7		1110
4	-15	-14		-9	-8	8	9	10 ..	15	1111О
5	-31	-30	-29		-17	-16	16	17 ..	31	111110
6	-63	-62	-61		-33	-32	32	33 ..	63	1111110
7	-127	-126	-125		-65	-64	64	65 ..	127	11111110
14	-16383	-16382	-16381		-8193	-8192	8192	8193 . .	. 16383	111111111111110
15	-32767	-32766	-32765		-16385	-16384	16384	16385 ..	. 32767	1111111111111110
16	32768									1111111111111111

Табл. 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) пара пара (Я, Z) (не (R, С)\) используется для нахождения соответствующего числа по строке и столбцу в табл. 3.54; (4) наконец, полученный из этой таблицы код Хаффмана присоединяется к С (где С записывается в виде R-битного числа); результатом этих действий служит код, выдаваемый на выход кодером JPEG для этого АС коэффициента х и всех предыдущих нулей. (Можно перевести дух.)

R	Z: 0:	1	.. 15
0	1010		111100l(ZRL)
1	00	1100	1111111111110101
2	01	11011	1111111111110110
3	100	1111001	1111111111110111
4	1011	111110110	1111111111111000
5	11010	11111110110	1111111111111001

Табл. 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, соответственно.

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

1118,2,0,-2,0,...,0,-1,0,...,0. 1346

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

01 11111000

100

1

11010 1111111110000011

00 11111110000100

11011

11111111

111 111

0001 11 11110000110 11

0110

11110000111

11110110 1111110001000

100 1111110001010

11001 111110001011

10111 11 1110001100 11

1110100 1110001101

111110001001 111110001110

1010 11111110010001

110111 1111110010010

1110101 11 11110010011 11

11110001111 11110010100

1111110010000 1111110010101

1011 11111110011001

1111000 1111110011010

11110010110 11 11110011011 11

11110010111 11110011100

1111110011000 1111110011101

11010 11111110100001

11110111

L111110100010

11110011110 11 11110100011 11

1110011111 1110100100

1111110100000 1111110100101

11011 11111110101001

111110110 1111110101010

1Ш0100110 1 111101010111

11110100111 11110101100

1111110101000 1111110101101

111010 11111110110001

111110111 1111110110010

11110101110 11 11110110011 11

11110101111 11110110100

1111110110000 1111110110101

1111000 11111110111001

11111000000 111110111010

1110110110 11 1110111011 11

11110110111 11110111100

1111110111000 1111110111101

1111001 11111111000010

1111110111110 1111111000011

11110111111 11 11111000100 11

11111000000 11111000101

1111111000001 1111111000110

111010 .1111111001011

1111111000111 1111111001100

11111001000 11 11111001101 11

11111001001 11111001110

1111111001010 1111111001111

11111001 11111111010100

1111111010000 1111111010101

11111010001 11 11111010110 11

11111010010 11111010111

1111111010011 1111111011000

11111010 11111111011101

1111111011001 1111111011110

11111011010 11 11111011111 11

11111011011 11111100000

1111111011100 1111111100001

111111000 11111111100110

1111111100010 1111111100111

11111100011 11 11111101000 11

11111100100 11111101001

111111100101 111111101010

11111111101011 11111111110000

1111111101100 1111111110001

1111101101 11 1111110010 11

11111101110 11111110011

1111111101111 1111111110100

111111001 11111111111001

1111111111110101 1111111111111010

11111110110 11 11111111011 11

1111110111 1111111101

1111111111111000 1111111111111110

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

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

111111111110111010001001101101101111010101010.

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

100 1111000

1010 111110100

11000 1111110110

11001 111111110100

111001 111111110001000

11110110 111111110001001

111110101 111111110001010

11111110110 111111110001011

010 11111110001100

11110111 1111111110001101

1111110111 1111111110001110

111111110110 1111111110001111

111111111000010 1111111110010000

011 11111110010010

11111000 1111111110010011

1111111000 1111111110010100

111111110111 1111111110010101

1111111110010001 1111111110010110

1010 11111110011010

111110110 1111111110011011

1111111110010111 1111111110011100

1111111110011000 1111111110011101

1111111110011001 1111111110011110

1011 11111110100010

1111111001 1111111110100011

1111111110011111 1111111110100100

1111111110100000 1111111110100101

1111111110100001 1111111110100110

11001 11111110101010

11111110111 1111111110101011

1111111110100111 1111111110101100

1111111110101000 1111111110101101

1111111110101001 1111111110101110

11010 11111110110010

11111111000 1111111110110011

1111111110101111 1111111110110100

1111111110110000 1111111110110101

1111111110110001 1111111110110110

111001 11111110111011

1111111110110111 1111111110111100

1111111110111000 1111111110111101

1111111110111001 1111111110111110

1111111110111010 1111111110111111

1110111 11111111000100

1111111111000000 1111111111000101

1111111111000001 1111111111000110

1111111111000010 1111111111000111

1111111111000011 1111111111001000

1111000 11111111001101

1111111111001001 1111111111001110

1111111111001010 1111111111001111

1111111111001011 1111111111010000

1111111111001100 1111111111010001

1111001 11111111010110

1111111111010010 1111111111010111

1111111111010011 1111111111011000

1111111111010100 1111111111011001

1111111111010101 1111111111011010

1111010 11111111011111

1111111111011011 1111111111100000

1111111111011100 1111111111100001

1111111111011101 1111111111100010

1111111111011110 1111111111100011

111111001 11111111101000

1111111111100100 1111111111101001

1111111111100101 1111111111101010

1111111111100110 1111111111101011

1111111111100111 1111111111101100

111111100000 11111111110001

1111111111101101 1111111111110010

1111111111101110 1111111111110011

1111111111101111 1111111111110100

1111111111110000 1111111111110101

1111111000011 11111111111010

111111111010110 1111111111111011

1111111111110111 1111111111111100

1111111111111000 1111111111111101

1111111111111001 1111111111111110

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

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

Некоторые варианты JPEG предусматривают использование версии с арифметическим кодированием, которая называется кодированием QM. Это кодирование также устанавливается стандартом JPEG. Этот метод является адаптивным и для его работы не тре-

200 Глава 3. Сжатие изображений

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