Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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% для типичного непрерывно-тонового изображения. Однако этот метод имеет весьма сложную реализацию по сравнением с методом Хаффмана, поэтому он редко используется в приложениях.

 



<< ПредыдущаяОглавлениеСледующая >>