Алгоритм преобразования графического изображения JPEG состоит из нескольких этапов, выполняемых над изображением последовательно, один за другим:
– преобразования цветового пространства,
– субдискретизации,
– дискретного косинусного преобразования (ДКП),
– квантования,
– кодирования.
На этапе преобразования цветового пространства осуществляется преобразование изображения из цветового пространства RGB в YCbCr (где Y - яркость, а Cb и Cr - цветоразностные компоненты точки изображения):
Применение пространства YCbCr вместо привычного RGB объясняется физиологическими особенностями человеческого зрения, а именно тем, что нервная система человека обладает значительно большей чувствительностью к яркости (Y ) , чем к цветоразностным составляющим (в данном случае Cb и Cr ). Обратное преобразование цветового пространства (из YCrCb в RGB ) имеет вид:
Алгоритм сжатия JPEG позволяет сжимать изображения с различными размерами цветовых плоскостей. Обозначим через x i и y i ширину и высоту i -й цветовой плоскости изображения. Пусть X = max (x i ), Y = max (y i ), определим для каждой плоскости коэффициенты H i = X / x i и V i = Y / y i . Наибольшее значение для X и Y согласно алгоритму JPEGравно 2 16 , а для H i и V i – 2 2 . Таким образом, ширина и высота цветовых плоскостей может быть от 1 до 4 раз меньше, размеров наибольшей плоскости. Для обычных RGB изображений размеры всех цветовых плоскостей равны.
Субдискретизация состоит в уменьшении размеров плоскостей Cr и Cb . Наиболее распространено уменьшение в 2 раза по ширине и в 2 раза по высоте (см. рисунок 1). Для этого Cr и Cb плоскости изображения разбиваются на блоки с размером 2 на 2 точки, и блок заменяется одним отсчетом цветоразностных компонент (на место имевшихся 4 отсчетов ставится их среднее арифметическое для каждого блока, что позволяет уменьшить размер исходного изображения в 2 раза).
Рисунок 1 – Распространенные типы субдискретизации
Затем, отдельно для каждого компонента цветового пространства Y , Cb и Cr , осуществляется прямое дискретное косинусное преобразование. Для этого изображение делится на блоки с размером 8 на 8 точек и каждый блок преобразуется согласно формуле:
Применение дискретного косинусного преобразования позволяет перейти от пространственного представления изображения к спектральному. Обратное дискретное косинусное преобразование имеет вид:
После этого можно переходить к квантованию полученной информации. Идея квантования состоит в отбрасывании некоторого объема информации. Известно, что глаз человека менее восприимчив к высоким частотам (особенно к высоким частотам цветоразностных компонент), большинство фотографических изображений содержит мало высокочастотных составляющих. Кроме того, появление высоких частот является следствием процесса оцифровки, т.е. вследствие появления сопутствующих дискретизации и квантования шумов. На этом этапе используются так называемые таблицы квантования - матрицы состоящие из целых положительных чисел с размером 8 на 8, на элементы которых делятся соответствующие частоты блоков изображения, результат округляется до целого числа:
.
В процессе деквантования используются те же таблицы, что и при квантовании. Деквантование состоит в умножении квантованных частот на соответствующие элементы таблицы квантования:
Таким образом, при увеличении коэффициента квантования увеличивается объем отбрасываемой информации. Рассмотрим это подробнее на примере.
Блок до квантования:
3862, –22, –162, –111, –414, 12, 717, 490,
383, 902, 913, 234, –555, 18, –189, 236,
229, 707, –708, 775, 423, –411, –66, –685,
231, 34, –928, 34, –1221, 647, 98, –824,
–394, 128, –307, 757, 10, –21, 431, 427,
324, –874, –367, –103, –308, 74, –1017, 1502,
208, –90, 114, –363, 478, 330, 52, 558,
577, 1094, 62, 19, –810, –157, –979, –98
Таблица квантования (качество 90):
24, 16, 16, 24, 40, 64, 80, 96,
16, 16, 24, 32, 40, 96, 96, 88,
24, 24, 24, 40, 64, 88, 112, 88,
24, 24, 32, 48, 80, 136, 128, 96,
32, 32, 56, 88, 112, 176, 168, 120,
40, 56, 88, 104, 128, 168, 184, 144,
80, 104, 128, 136, 168, 192, 192, 160,
112, 144, 152, 160, 176, 160, 168, 160
Блок после квантования:
161, –1, –10, –5, –10, 0, 9, 5,
24, 56, 38, 7, –14, 0, –2, 3,
10, 29, –30, 19, 7, –5, –1, –8,
10, 1, –29, 1, –15, 5, 1, –9,
–12, 4, –5, 9, 0, 0, 3, 4,
8, –16, –4, –1, –2, 0, –6, 10,
3, –1, 1, –3, 3, 2, 0, 3,
5, 8, 0, 0, –5, –1, –6, –1
3864, –16, –160, –120, –400, 0, 720, 480,
384, 896, 912, 224, –560, 0, –192, 264,
240, 696, –720, 760, 448, –440, –112, –704,
240, 24, –928, 48,–1200, 680, 128, –864,
–384, 128, –280, 792, 0, 0, 504, 480,
320, –896, –352, –104, –256, 0,–1104, 1440,
240, –104, 128, –408, 504, 384, 0, 480,
560, 1152, 0, 0, –880, –160,–1008, –160
Таблица квантования (качество 45):
144, 96, 88, 144, 216, 352, 456, 544,
104, 104, 128, 168, 232, 512, 536, 488,
128, 112, 144, 216, 352, 504, 616, 496,
128, 152, 192, 256, 456, 776, 712, 552,
160, 192, 328, 496, 600, 968, 912, 680,
216, 312, 488, 568, 720, 920, 1000, 816,
432, 568, 696, 776, 912, 1072, 1064, 896,
640, 816, 840, 872, 992, 888, 912, 880
Блок после квантования:
27, 0, –2, –1, –2, 0, 2, 1,
4, 9, 7, 1, –2, 0, 0, 0,
2, 6, –5, 4, 1, –1, 0, –1,
2, 0, –5, 0, –3, 1, 0, –1,
–2, 1, –1, 2, 0, 0, 0, 1,
2, –3, –1, 0, 0, 0, –1, 2,
0, 0, 0, 0, 1, 0, 0, 1,
1, 1, 0, 0, –1, 0, –1, 0
Блок после обратного преобразования:
3888, 0, –176, –144, –432, 0, 912, 544,
416, 936, 896, 168, –464, 0, 0, 0,
256, 672, –720, 864, 352, –504, 0, –496,
256, 0, –960, 0,–1368, 776, 0, –552,
–320, 192, –328, 992, 0, 0, 0, 680,
432, –936, –488, 0, 0, 0,–1000, 1632,
0, 0, 0, 0, 912, 0, 0, 896,
640, 816, 0, 0, –992, 0, –912, 0
Как видно, в первом случае изменение DC коэффициента в результате сжатия равно 2, а во втором 26, при этом квантованный DC коэффициент во втором случае в 6 раз меньше чем в первом.
Кодирование является заключительным этапом сжатия, во время него блоки изображения преобразуются в векторную форму по правилу, задаваемому блоками вида:
0, 1, 5, 6, 14, 15, 27, 28,
2, 4, 7, 13, 16, 26, 29, 42,
3, 8, 12, 17, 25, 30, 41, 43,
9, 11, 18, 24, 31, 40, 44, 53,
10, 19, 23, 32, 39, 45, 52, 54,
20, 22, 33, 38, 46, 51, 55, 60,
21, 34, 37, 47, 50, 56, 59, 61,
35, 36, 48, 49, 57, 58, 62, 63
где в качестве элементов блока указаны векторные индексы соответствующих компонентов матрицы. При этом нулевой элемент кодируется как разница с нулевым элементом предыдущего блока. Нулевые элементы обозначают DC , в них содержится постоянная составляющая блока (все остальные АС элементы принято обозначать AC ).
Затем полученные данные сжимаются с использованием арифметического кодирования или модификации алгоритма Хаффмана. Этот этап не представляет большого интереса с точки зрения стеганографии в графических изображениях, поэтому он выходит за рамки нашего рассмотрения.
Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:
Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.
В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.
Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.