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 начинается с ее номера (слева); в конце стоит унарный код строки, а между ними располагаются некоторые числа. В каждой следующей строке записано больше чисел, чем в предыдущей, но они отличаются от чисел всех предыдущих строк. В строке
находятся числа из интервала
, за вычетом чисел интервала
. Длина строк растет очень быстро, поэтому такие данные не удобно представлять в виде простого двумерного массива. На самом деле, для их хранения не нужна никакая структура данных, поскольку подходящая программа легко определит позицию числа
в таблице, анализируя биты этого числа.
0:
|
0
|
|
|
|
|
|
|
|
|
|
0
|
1:
|
-1
|
1
|
|
|
|
|
|
|
|
|
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
|
11110
|
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) пара пара (R, Z) (не (R, С)!) используется для нахождения соответствующего числа по строке и столбцу в табл. 3.54; (4) наконец, полученный из этой таблицы код Хаффмана присоединяется к С (где С записывается в виде R-битного числа); результатом этих действий служит код, выдаваемый на выход кодером JPEG для этого АС коэффициента
и всех предыдущих нулей. (Можно перевести дух.)
0:
|
1010
|
|
|
11111111001 (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, соответственно.
Пример: Еще раз рассмотрим последовательность

Первый АС коэффициент
не имеет перед собой нулей, то есть, для него
. Он находится в табл. 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
z
|
1
6
|
2
7
|
3
8
|
4
9
|
5
A
|
0
|
00
1111000
|
01
11111000
|
100
1111110110
|
1011
1111111110000010
|
11010 1111111110000011
|
1
|
1100
1111111110000100
|
11011 1111111110000101
|
11110001 1111111110000110
|
111110110 1111111110000111
|
11111110110 1111111110001000
|
2
|
11100
111111110001010
|
11111001 111111110001011
|
1111110111 111111110001100
|
111111110100 111111110001101
|
111111110001001 111111110001110
|
3
|
111010 1111111110010001
|
111110111 1111111110010010
|
111111110101 1111111110010011
|
111 1111110001111 1111111110010100
|
1111111110010000 1111111110010101
|
4
|
111011 1111111110011001
|
1111111000 1111111110011010
|
1111111110010110 1111111110011011
|
1111111110010111 1111111110011100
|
1111111110011000 1111111110011101
|
5
|
1111010 1111111110100001
|
11111110111
1111111110100010
|
1111111110011110 1111111110100011
|
1111111110011111 1111111110100100
|
1111111110100000 1111111110100101
|
6
|
1111011 1111111110101001
|
111111110110 1111111110101010
|
1111111110100110 1111111110101011
|
1111111110100111 1111111110101100
|
111111110101000 1111111110101101
|
7
|
11111010 1111111110110001
|
111111110111 1111111110110010
|
1111111110101110 1111111110110011
|
1111111110101111 1111111110110100
|
1111111110110000 1111111110110101
|
8
|
111111000 1111111110111001
|
111111111000000 1111111110111010
|
1111111110110110 1111111110111011
|
1111111110110111 1111111110111100
|
1111111110111000 1111111110111101
|
9
|
111111001 1111111111000010
|
1111111110111110 1111111111000011
|
1111111110111110 1111111111000011
|
1111111111000000 1111111111000101
|
1111111111000001 1111111111000110
|
A
|
111111010 1111111111001011
|
1111111111000111 1111111111001100
|
1111111111001000 1111111111001101
|
1111111111001001 1111111111001110
|
1111111111001010 1111111111001111
|
В
|
1111111001 1111111111010100
|
1111111111010000 1111111111010101
|
1111111111010001 1111111111010110
|
1111111111010010 1111111111010111
|
1111111111010011 1111111111011000
|
С
|
1111111010 1111111111011101
|
1111111111011001 1111111111011110
|
1111111111011010 1111111111011111
|
1111111111011011 1111111111100000
|
1111111111011100 1111111111100001
|
D
|
11111111000 1111111111100110
|
1111111111100010 1111111111100111
|
1111111111100011 1111111111101000
|
1111111111100100 1111111111101001
|
1111111111100101 1111111111101010
|
E
|
1111111111101011 1111111111110000
|
1111111111101100 1111111111110001
|
1111111111101101 1111111111110010
|
1111111111101110 1111111111110011
|
1111111111101111 1111111111110100
|
F
|
11111111001 1111111111111001
|
1111111111110101 1111111111111010
|
1111111111110110
1111111111111011
|
1111111111110111 1111111111111101
|
1111111111111000 1111111111111110
|
Табл. 3.55. Рекомендованные коды Хаффмана для коэффициентов АС светимости.
Наконец, хвост из последних нулей кодируется как 1010 (ЕОВ, конец блока). Значит, выходом для всех коэффициентов АС будет последовательность 01101101110111010101010. Мы ранее установили, что кодом коэффициентом DC станет двоичная последовательность 111111111110|1110100010. Итак, окончательным кодом всего 64-пиксельного блока данных будет 46-битовое числоe
111111111110111010001001101101101111010101010.
Эти 46 бит кодируют одну цветную компоненту единицы данных. Предположим, что две остальные компоненты будут также закодированы 46-битовыми числами. Если каждый пиксел исходно состоял из 24 бит, то получим фактор сжатия равный
; очень неплохой результат!
R
Z
|
1
6
|
2
7
|
3
8
|
4
9
|
5
А
|
0
|
01
111000
|
100
1111000
|
1010
111110100
|
11000
1111110110
|
11001 111111110100
|
1
|
1011 111111110101
|
111001
111111110001000
|
11110110 111111110001001
|
111110101 111111110001010
|
11111110110 111111110001011
|
2
|
11010 1111111110001100
|
11110111 1111111110001101
|
1111110111 1111111110001110
|
111111110110 1111111110001111
|
111111111000010 1111111110010000
|
3
|
11011 1111111110010010
|
11111000 1111111110010011
|
1111111000 1111111110010100
|
111111110111 1111111110010101
|
1111111110010001 1111111110010110
|
4
|
111010 1111111110011010
|
111110110 1111111110011011
|
1111111110010111 1111111110011100
|
1111111110011000 1111111110011101
|
1111111110011001 1111111110011110
|
5
|
111011 1111111110100010
|
1111111001 1111111110100011
|
1111111110011111 1111111110100100
|
1111111110100000 1111111110100101
|
1111111110100001 1111111110100110
|
6
|
1111001 1111111110101010
|
11111110111 1111111110101011
|
1111111110100111 1111111110101100
|
1111111110101000 1111111110101101
|
1111111110101001 1111111110101110
|
7
|
1111010 1111111110110010
|
11111111000 1111111110110011
|
1111111110101111 1111111110110100
|
1111111110110000 1111111110110101
|
1111111110110001 1111111110110110
|
8
|
11111001 1111111110111011
|
1111111110110111 1111111110111100
|
1111111110111000 1111111110111101
|
1111111110111001 1111111110111110
|
1111111110111010 1111111110111111
|
9
|
111110111 1111111111000100
|
1111111111000000 1111111111000101
|
1111111111000001 1111111111000110
|
1111111111000010 1111111111000111
|
1111111111000011 1111111111001000
|
А
|
111111000 1111111111001101
|
1111111111001001 1111111111001110
|
1111111111001010 1111111111001111
|
1111111111001011 1111111111010000
|
1111111111001100 1111111111010001
|
В
|
111111001 1111111111010110
|
1111111111010010 1111111111010111
|
1111111111010011 1111111111011000
|
1111111111010100 1111111111011001
|
1111111111010101 1111111111011010
|
С
|
111111010 1111111111011111
|
1111111111011011 1111111111100000
|
1111111111011100 1111111111100001
|
1111111111011101 1111111111100010
|
1111111111011110 1111111111100011
|
D
|
11111111001 1111111111101000
|
1111111111100100 1111111111101001
|
1111111111100101 1111111111101010
|
1111111111100110 1111111111101011
|
1111111111100111 11111111111011011
|
Е
|
11111111100000 1111111111110001
|
1111111111101101 1111111111110010
|
1111111111101110 1111111111110011
|
1111111111101111 1111111111110100
|
1111111111110000 1111111111110101
|
F
|
111111111000011 1111111111111010
|
111111111010110 1111111111111011
|
1111111111110111 1111111111111100
|
1111111111111000 1111111111111101
|
1111111111111001 1111111111111110
|
Табл. 3.56. Рекомендованные коды Хаффмана для коэффициентов АС хроматических компонент.
Те же таблицы (3.53 и 3.54) должны быть использованы декодером для восстановления блока данных. Они задаются по умолчанию кодеком JPEG, или могут быть специально построены для данного конкретного изображения на предварительном проходе. Однако сам JPEG не предусматривает алгоритма для построения таких таблиц. Конкретный кодек может самостоятельно сделать это.
Некоторые варианты JPEG предусматривают использование версии с арифметическим кодированием, которая называется кодированием QM. Это кодирование также устанавливается стандартом JPEG. Этот метод является адаптивным и для его работы не требуются таблицы 3.53 и 3.54. Он приспосабливает схему кодирования к статистическим свойствам конкретного изображения по мере его обработки. С помощью арифметического кодирования можно улучшить показатели компрессии метода Хаффмана на 5-10% для типичного непрерывно-тонового изображения. Однако этот метод имеет весьма сложную реализацию по сравнением с методом Хаффмана, поэтому он редко используется в приложениях.