Алгоритм сжатия JPEG

Этот алгоритм появился в конце 1980-х гг. в результате долгих исследований группы специалистов, что и дало ему название JPEG – Joint Photographic Experts Group, т.е. объёдиненная группа экспертов по фотографии. Являясь алгоритмом сжатия с потерями, JPEG даёт очень высокий коэффициент сжатия. Для сложных изображений - до 10 (без заметного ухудшения качества) и более (с заметным ухудшением качества). Для сравнительно простых изображений, имеющих большие области одинакового цвета, коэффициент сжатия может достигать 20-25.

Используя волновую природу света, JPEG представляет изображение как суперпозицию множества гармоник световых волн разных частот. При этом основную энергию несут низкочастотные гармоники, в то время как высокочастотные могут быть отброшены без заметного ухудшения качества изображения. При этом имеется возможность регулировать этот частотный порог, меняя тем самым степень сжатия.

Алгоритм JPEG включает четыре основных этапа:

1) Предварительная подготовка изображения;

2) Дискретное косинусное преобразование;

3) Квантование;

4) Вторичное сжатие.

На 1-м этапе цветное RGB-изображение разделяется на три цветовых плоскости (красную, зеленую и синюю). Затем каждая плоскость разбивается на квадратные участки размером 8x8 пикселей и далее кодируется отдельно.

Примечание. Для достижения лучшего сжатия изображение может переводиться (хотя и не обязательно) в другую цветовую модель – YUV, где Y – яркость, U и V – цветоразностные компоненты:

(4)

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

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

Пусть матрица блока изображения обозначается IMG =[8х8]. Проведём её нормализацию, вычитая из каждого её элемента 128. Дискретное косинусное преобразование осуществляется по формуле

(5)

где

(6)

N=8, i=0..7, j=0..7.

На этапе квантования сначала вычисляется матрица квантования по следующей формуле

, (7)

i,j =0..7

где q – коэффициент качества, регулирующий степень сжатия.

Затем каждое число в матрице RES нужно разделить на соответствующий элемент в матрице Q. В результате получится некоторая матрица A, у всех элементов которой необходимо отбросить дробные части. В итоге матрица A будет содержать много нулевых элементов, преимущественно в правой нижней части.

На этапе вторичного сжатия элементы матрицы А пакуются максимально компактным образом. Для достижения максимального эффекта сжатия применяется предварительное Z-упорядочивание элементов матрицы A(8x8) в линейный вектор A(64x1), выполняемое по следующей схеме:

+----+----+----+----+----+----+----+----+

| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |

+----+----+----+----+----+----+----+----+

| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |

+----+----+----+----+----+----+----+----+

| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |

+----+----+----+----+----+----+----+----+

| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |

+----+----+----+----+----+----+----+----+

| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |

+----+----+----+----+----+----+----+----+

| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |

+----+----+----+----+----+----+----+----+

| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |

+----+----+----+----+----+----+----+----+

| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |

+----+----+----+----+----+----+----+----+

Самым распространенным методом вторичного сжатия является сжатие с применением кодов Хаффмана. В полученном векторе А первый элемент (с индексом 0) называется DC коэффициентом. Он пропорционален средней яркости блока и обычно намного больше других элементов вектора. Остальные 63 элемента вектора называются AC коэффициентами, они пропорциональны интенсивности цветовых переходов в блоке. DC и AC коэффициенты кодируются по-разному, но по схожим принципам.

Код для DC коэффициента состоит из полей РАЗМЕР (число бит, необходимых для представления значения) и ЗНАЧЕНИЕ (биты самого значения).

Код для AC коэффициента состоит из полей ПРОПУСК (количество предшествующих нулевых AC коэффициентов), РАЗМЕР (число бит, необходимых для представления значения) и ЗНАЧЕНИЕ (биты самого значения).

Поле ЗНАЧЕНИЕ для обоих типов коэффициентов кодируется идентичным способом в соответствии с табл.1.

Для DC коэффициента поле РАЗМЕР кодируется в соответствии с табл. 2.

Для АC коэффициента поля ПРОПУСК и РАЗМЕР рассматриваются как один составной символ вида (ПРОПУСК, РАЗМЕР), который кодируется в соответствии с табл. 3. Причем символ (0,0) называется признаком конца блока и означает, что с текущего места и до конца вектор содержит только нулевые AC коэффициенты.

Таблица 1. Кодирование поля ЗНАЧЕНИЕ в DC и AC коэффициентах

Поле ЗНАЧЕНИЕ в DC и AC коэффициентах
Величина (значение)	Число бит	Биты (в выходном потоке)
		-
-1,1		0,1
-3,-2, 2, 3		00,01,10,11
-7,-6,-5,-4, 4, 5, 6, 7		000,001,010,011,100,101,110,111
-15..-8, 8..15		0000..0111,1000..1111
-31..-16, 16..31		00000..01111,10000..11111
-63..-32, 32..63		000000..011111,100000..111111
-127..-64, 64..127		0000000..1111111
-255..-128, 128..255		00000000..11111111
-511..256, 256..511		000000000..111111111
-1023..-512, 512..1023		0000000000..1111111111
-2047..-1024, 1024..2047		00000000000..11111111111
-4095..2048, 2048..4095		000000000000..111111111111
-8191..-4096, 4096..8191		0000000000000..1111111111111
-16383..-8192, 8192..16383		00000000000000..11111111111111
-32767..-16384, 16384..32767		000000000000000..111111111111111

Таблица 2. Коды Хаффмана для поля РАЗМЕР в DC коэффициентах

Поле РАЗМЕР в DC коэффициенте
Десятичный вид	Двоичный вид	Код Хаффмана
	0000	00
	0001	010
	0010	011
	0011	100
	0100	101
	0101	110
	0110	1110
	0111	11110
	1000	111110
	1001	1111110
	1010	11111110
	1011	111111110

Таблица 3. Коды Хаффмана для составного символа в AC коэффициентах

Составной символ = (ПРОПУСК, РАЗМЕР) для АC коэффициентов
(ПРОПУСК, РАЗМЕР)	Код Хаффмана
[конец блока]=(0,0)
(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(0,6)
(0,7)
(1,1)
(1,2)
(1,3)
(1,4)
(2,1)
(2,2)
(3,1)
(3,2)
(4,1)
(5,1)
(6,1)
(7,1)
(8,1)
(9,1)

Полученные биты кодовых значений DC и AC коэффициентов записываются в выходной поток, и JPEG переходит к сжатию следующего блока данных, и т.д. Распаковка сжатых данных из полученного битового потока и восстановление изображения осуществляется в строго обратном порядке.

Пример

Блок 8x8 (фрагмент) исходного изображения (размер 64*8=512 бит)

Матрица DCT коэффициентов

Матрица квантованных DCT коэффициентов

Кодовая последовательность в десятичном виде

(2)(3) (1,2)(-2) (0,1)(-1) (0,1)(-1) (0,1)(-1) (2,1)(-1) (0,0)

Кодовая последовательность в двоичном виде с учетом кодов Хаффмана

(011)(11) (11011)(01) (00)(0) (00)(0) (00)(0) (11100)(0) (1010)

Результирующая битовая последовательность (31 бит)

Коэффициент сжатия

Контрольные вопросы

1. В чем отличие растровых и векторных форматов хранения данных?

2. Что такое палитра и в каких случаях она применяется?

3. Что такое информационная избыточность и каких видов она бывает?

4. В каких случаях коэффициент сжатия оказывается меньше единицы?

5. Что необходимо для эффективного сжатия по алгоритму LZW?

6. Может ли кодирование по Хаффману дать ? Почему?

7. Чем объясняется высокая степень сжатия, которую обеспечивает алгоритм JPEG?