Сжатие изображений: JPEG и JPEG2000. Разновидности схем сжатия JPEG. JPEG сжимает лучше, чем GIF

Помощь 15.05.2019

Помощь

Tutorial

UPD. Был вынужден убрать моноширинное форматирование. В один прекрасный день хабрапарсер перестал воспринимать форматирование внутри тегов pre и code. Весь текст превратился в кашу. Администрация хабра не смогла мне помочь. Теперь неровно, но хотя бы читабельно.

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

Сразу предупреждаю, что описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.

Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.
- маркер начала. Он всегда находится в начале всех jpg-файлов.
Следом идут байты . Это маркер, означающий начало секции с комментарием. Следующие 2 байта - длина секции (включая эти 2 байта). Значит в следующих двух - сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

Немного теории

Очень кратко по шагам:

Давайте подумаем, в каком порядке могут быть закодированы эти данные. Допустим, сначала полностью, для всего изображения, закодирован канал Y, затем Cb, потом Cr. Все помнят загрузку картинок на диал-апе. Если бы они кодировались именно так, нам бы пришлось ждать загрузки всего изображения, прежде чем оно появится на экране. Так же будет неприятно, если потерятся конец файла. Вероятно, существуют и другие весомые причины. Поэтому закодированные данные располагаются поочередно, небольшими частями.

Напоминаю, что каждый блок Y ij , Cb ij , Cr ij - это матрица коэффициентов ДКП, закодированная кодами Хаффмана. В файле они располагаются в таком порядке: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20

Чтение файла

После того, как мы извлекли комментарий, будет легко понять, что:

Файл поделен на секторы, предваряемые маркерами.
Маркеры имеют длину 2 байта, причем первый байт .
Почти все секторы хранят свою длину в следующих 2 байта после маркера.

Для удобства подсветим маркеры:
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78

FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00 AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9

Маркер : DQT - таблица квантования.

FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF

Заголовок секции всегда занимает 3 байта. В нашем случае это . Заголовок состоит из:
Длина: 0x43 = 67 байт
Длина значений в таблице: 0 (0 - 1 байт, 1 - 2 байта)
[_0] Идентификатор таблицы: 0
Оставшимися 64-мя байтами нужно заполнить таблицу 8x8.

Приглядитесь, в каком порядке заполнены значения таблицы. Этот порядок называется zigzag order:

Маркер : SOF0 - Baseline DCT

Этот маркер называется SOF0, и означает, что изображение закодировано базовым методом. Он очень распространен. Но в интернете не менее популярен знакомый вам progressive-метод, когда сначала загружается изображение с низким разрешением, а потом и нормальная картинка. Это позволяет понять что там изображено, не дожидаясь полной загрузки. Спецификация определяет еще несколько, как мне кажется, не очень распространенных методов.

FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01

Длина: 17 байт.
Precision: 8 бит. В базовом методе всегда 8. Как я понял, это разрядность значений каналов.
Высота рисунка: 0x10 = 16
Ширина рисунка: 0x10 = 16
Количество компонентов: 3. Чаще всего это Y, Cb, Cr.

1-й компонент:
Идентификатор: 1
Горизонтальное прореживание (H 1): 2
[_2] Вертикальное прореживание (V 1): 2
Идентификатор таблицы квантования: 0

2-й компонент:
Идентификатор: 2
Горизонтальное прореживание (H 2): 1
[_1] Вертикальное прореживание (V 2): 1

3-й компонент:
Идентификатор: 3
Горизонтальное прореживание (H 3): 1
[_1] Вертикальное прореживание (V 3): 1
Идентификатор таблицы квантования: 1

Теперь посмотрите, как определить насколько прорежено изображение. Находим H max =2 и V max =2 . Канал i будет прорежен в H max /H i раз по горизонтали и V max /V i раз по вертикали.

Маркер : DHT (таблица Хаффмана)

Эта секция хранит коды и значения полученные кодированием Хаффмана .

FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02

длина: 21 байт.
класс: 0 (0 - таблица DC коэффициэнтов, 1 - таблица AC коэффициэнтов).
[_0] идентификатор таблицы: 0
Длина кода Хаффмана: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Количество кодов:
Количество кодов означает количество кодов такой длины. Обратите внимание, что секция хранит только длины кодов, а не сами коды. Мы должны найти коды сами. Итак, у нас есть один код длины 1 и один - длины 2. Итого 2 кода, больше кодов в этой таблице нет.
С каждым кодом сопоставлено значение, в файле они перечислены следом. Значения однобайтовые, поэтому читаем 2 байта.
- значение 1-го кода.
- значение 2-го кода.

Построение дерева кодов Хаффмана

Мы должны построить бинарное дерево по таблице, которую мы получили в секции DHT. А уже по этому дереву мы узнаем каждый код. Значения добавляем в том порядке, в каком указаны в таблице. Алгоритм прост: в каком бы узле мы ни находились, всегда пытаемся добавить значение в левую ветвь. А если она занята, то в правую. А если и там нет места, то возвращаемся на уровень выше, и пробуем оттуда. Остановиться нужно на уровне равном длине кода. Левым ветвям соответствует значение 0 , правым - 1 .
Замечание:
Не нужно каждый раз начинать с вершины. Добавили значение - вернитесь на уровень выше. Правая ветвь существует? Если да, идите опять вверх. Если нет - создайте правую ветвь и перейдите туда. Затем, с этого места, начинайте поиск для добавления следующего значения.

Деревья для всех таблиц этого примера:

UPD (спасибо ): В узлах первого дерева (DC, id =0) должны быть значения 0x03 и 0x02

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

Маркер : SOS (Start of Scan)

Байт в маркере означает - «ДА! Наконец-то то мы перешли непосредственно к разбору секции закодированного изображения!». Однако секция символично называется SOS.

FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00

Длина заголовочной части (а не всей секции): 12 байт.
Количество компонентов сканирования. У нас 3, по одному на Y, Cb, Cr.

1-й компонент:
Номер компонента изображения: 1 (Y)
Идентификатор таблицы Хаффмана для DC коэффициэнтов: 0
[_0] Идентификатор таблицы Хаффмана для AC коэффициэнтов: 0

2-й компонент:
Номер компонента изображения: 2 (Cb)

[_1]

3-й компонент:
Номер компонента изображения: 3 (Cr)
Идентификатор таблицы Хаффмана для DC коэффициэнтов: 1
[_1] Идентификатор таблицы Хаффмана для AC коэффициэнтов: 1

Данные компоненты циклически чередуются.

На этом заголовочная часть заканчивается, отсюда и до конца (маркера ) закодированные данные.

Нахождение DC-коэффициента.
1. Читаем последовательность битов (если встретим 2 байта , то это не маркер, а просто байт ) . После каждого бита сдвигаемся по дереву Хаффмана (с соответствующим идентификатором) по ветви 0 или 1, в зависимости от прочитанного бита. Останавливаемся, если оказались в конечном узле.
10 1011101110011101100001111100100

2. Берем значение узла. Если оно равно 0, то коэффициент равен 0, записываем в таблицу и переходим к чтению других коэффициентов. В нашем случае - 02. Это значение - длина коэффициента в битах. Т. е. читаем следующие 2 бита, это и будет коэффициент.
10 10 11101110011101100001111100100

3. Если первая цифра значения в двоичном представлении - 1, то оставляем как есть: DC_coef = значение. Иначе преобразуем: DC_coef = значение-2 длина значения +1 . Записываем коэффициент в таблицу в начало зигзага - левый верхний угол.

Нахождение AC-коэффициентов.
1. Аналогичен п. 1, нахождения DC коэффициента. Продолжаем читать последовательность:
10 10 1110 1110011101100001111100100

2. Берем значение узла. Если оно равно 0, это означает, что оставшиеся значения матрицы нужно заполнить нулями. Дальше закодирована уже следующая матрица. Первые несколько дочитавших до этого места и написавших об этом мне в личку, получат плюс в карму. В нашем случае значение узла: 0x31.
Первый полубайт: 0x3 - именно столько нулей мы должны добавить в матрицу. Это 3 нулевых коэффициэнта.
Второй полубайт: 0x1 - длина коэффициэнта в битах. Читаем следующий бит.
10 10 1110 1 110011101100001111100100

3. Аналогичен п. 3 нахождения DC-коэффициента.

Как вы уже поняли, читать AC-коэффициенты нужно пока не наткнемся на нулевое значение кода, либо пока не заполнится матрица.
В нашем случае мы получим:
10 10 1110 1 1100 11 101 10 0 0 0 1 11110 0 100
и матрицу:

Вы заметили, что значения заполнены в том же зигзагообразном порядке?
Причина использования такого порядка простая - так как чем больше значения v и u, тем меньшей значимостью обладает коэффициент S vu в дискретно-косинусном преобразовании. Поэтому, при высоких степенях сжатия малозначащие коэффициенты обнуляют, тем самым уменьшая размер файла.

[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Ой, я забыл сказать, что закодированные DC-коэффициенты - это не сами DC-коэффициенты, а их разности между коэффициентами предыдущей таблицы (того же канала)! Нужно поправить матрицы:
DC для 2-ой: 2 + (-4) = -2
DC для 3-ой: -2 + 5 = 3
DC для 4-ой: 3 + (-4) = -1

[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………

Теперь порядок. Это правило действует до конца файла.

… и по матрице для Cb и Cr:

[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Так как тут только по одной матрице, DC-коэфициенты можно не трогать.

Вычисления

Квантование

Вы помните, что матрица проходит этап квантования? Элементы матрицы нужно почленно перемножить с элементами матрицы квантования. Осталось выбрать нужную. Сначала мы просканировали первый компонент, его компонента изображения = 1. Компонент изображения с таким идентификатором использует матрицу квантования 0 (у нас она первая из двух). Итак, после перемножения:

[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Аналогично получаем еще 3 матрицы Y-канала…

[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

… и по матрице для Cb и Cr.

[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

Обратное дискретно-косинусное преобразование

Формула не должна доставить сложностей*. S vu - наша полученная матрица коэффициентов. u - столбец, v - строка. s yx - непосредственно значения каналов.

*Вообще говоря, это не совсем правда. Когда я смог декодировать и отобразить на экране рисунок 16x16, я взял изображение размером 600x600 (кстати, это была обложка любимого альбома Mind.In.A.Box - Lost Alone). Получилось не сразу - всплыли различные баги. Вскоре я мог любоваться корректно загруженной картинкой. Только очень огорчала скорость загрузки. До сих пор помню, она занимала 7 секунд. Но это и неудивительно, если бездумно пользоваться приведенной формулой, то для вычисления одного канала одного пикселя потребуется нахождения 128 косинусов, 768 умножений, и сколько-то там сложений. Только вдумайтесь - почти тысяча непростых операций только на один канал одного пиксела! К счастью, тут есть простор для отимизации (после долгих экспериментов уменьшил время загрузки до предела точности таймера 15мс, и после этого сменил изображение на фотографию в 25 раз большей площадью. Возможно, напишу об этом отдельной статьей).

Напишу результат вычисления только первой матрицы канала Y (значения округлены):

[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]

И 2-х оставшихся:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]

О, пойду-ка поем!
Да я вообще не въезжаю, о чем речь.
Раз значение цветов YCbCr получены, осталось преобразовать в RGB, типа так: YCbCrToRGB(Y ij , Cb ij , Cr ij) , Y ij , Cb ij , Cr ij - наши полученные матрицы.
4 матрицы Y, и по одной Cb и Cr, так как мы прореживали каналы и 4 пикселям Y соответствует по одному Cb и Cr. Поэтому вычислять так: YCbCrToRGB(Y ij , Cb , Cr )

Если вы выбрали 1 и 4, то я рад за вас. Либо вы все правильно поняли, либо скоро будете получать удовольствие от еды.

YCbCr в RGB

R = Y + 1.402 * Cr
G = Y - 0.34414 * Cb - 0.71414 * Cr
B = Y + 1.772 * Cb
Не забудьте прибавить по 128. Если значения выйдут за пределы интервала , то присвоить граничные значения. Формула простая, но тоже отжирает долю процессорного времени.

Вот полученные таблицы для каналов R, G, B для левого верхнего квадрата 8x8 нашего примера:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108

231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186

255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134

Конец

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

Алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group) специально для сжатия 24-битных и полутоновых изображений в 1991 году. Этот алгоритм не очень хорошо сжимает двухуровневые изображении, но он прекрасно обрабатывает изображения с непрерывными тонами, в которых близкие пикселы обычно имеют схожие цвета. Обычно глаз не в состоянии заметить какой-либо разницы при сжатии этим методом в 10 или 20 раз.

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

Рассмотрим работу алгоритма подробнее. Предположим, что сжимается полноцветное 24-битное изображение. В этом случае получаем следующие этапы работы.

Шаг 1. Переводим изображение из пространства RGB в пространство YCbCr с помощью следующего выражения:

Отметим сразу, что обратное преобразование легко получается путем умножения обратной матрицы на вектор , который по существу является пространством YUV:

Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП – по 8 бит отдельно для каждой компоненты. При больших степенях сжатия блок 8х8 раскладывается на компоненты YCbCr в формате 4:2:0, т.е. компоненты для Cb и Cr берутся через точку по строкам и столбцам.

Шаг 3. Применение ДКП к блокам изображения 8х8 пикселей. Формально прямое ДКП для блока 8х8 можно записать в виде

где . Так как ДКП является «сердцем» алгоритма JPEG, то желательно на практике вычислять его как можно быстрее. Простым подходом для ускорения вычислений является заблаговременное вычисление функций косинуса и сведения результатов вычисления в таблицу. Мало того, учитывая ортогональность функций косинусов с разными частотами, вышеприведенную формулу можно записать в виде

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

Здесь - результат ДКП, для вычисления которого требуется операций умножения и почти столько же сложений, что существенно меньше прямых вычислений по формуле выше. Например, для преобразования изображения размером 512х512 пикселей потребуется арифметических операций. Учитывая 3 яркостных компоненты, получаем значение 12 582 912 арифметических операций. Количество умножений и сложений можно еще больше сократить, если воспользоваться алгоритмом быстрого преобразования Фурье. В результате для преобразования одного блока 8х8 нужно будет сделать 54 умножений, 468 сложений и битовых сдвигов.

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

Шаг 4. Квантование. На этом шаге происходит отбрасывание части информации. Здесь каждое число из матрицы делится на специальное число из «таблицы квантования», а результат округляется до ближайшего целого:

Причем для каждой матрицы Y, Cb и Cr можно задавать свои таблицы квантования. Стандарт JPEG даже допускает использование собственных таблиц квантования, которые, однако, необходимо будет передавать декодеру вместе со сжатыми данными, что увеличит общий размер файла. Понятно, что пользователю сложно самостоятельно подобрать 64 коэффициента, поэтому стандарт JPEG использует два подхода для матриц квантования. Первый заключается в том, что в стандарт JPEG включены две рекомендуемые таблицы квантования: одна для яркости, вторая для цветности. Эти таблицы представлены ниже. Второй подход заключается в синтезе (вычислении на лету) таблицы квантовании, зависящей от одного параметра , который задается пользователем. Сама таблица строится по формуле

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

С квантованием связаны и специфические эффекты алгоритма. При больших значениях шага квантования потери могут быть настолько велики, что изображение распадется на квадраты однотонные 8х8. В свою очередь потери в высоких частотах могут проявиться в так называемом «эффекте Гиббса», когда вокруг контуров с резким переходом цвета образуется волнообразный «нимб».

Шаг 5. Переводим матрицу 8х8 в 64-элементный вектор при помощи «зигзаг»-сканирования (рис. 2).

Рис. 2. «Зигзаг»-сканирование

В результате в начале вектора, как правило, будут записываться ненулевые коэффициенты, а в конце образовываться цепочки из нулей.

Шаг 6. Преобразовываем вектор с помощью модифицированного алгоритма RLE, на выходе которого получаем пары типа (пропустить, число), где «пропустить» является счетчиком пропускаемых нулей, а «число» - значение, которое необходимо поставить в следующую ячейку. Например, вектор 1118 3 0 0 0 -2 0 0 0 0 1 … будет свернут в пары (0, 1118) (0,3) (3,-2) (4,1) … .

Следует отметить, что первое число преобразованной компоненты , по существу, равно средней яркости блока 8х8 и носит название DC-коэффициента. Аналогично для всех блоков изображения. Это обстоятельство наводит на мысль, что коэффициенты DC можно эффективно сжать, если запоминать не их абсолютные значения, а относительные в виде разности между DC коэффициентом текущего блока и DC коэффициентом предыдущего блока, а первый коэффициент запомнить так, как он есть. При этом упорядочение коэффициентов DC можно сделать, например, так (рис. 3). Остальные коэффициенты, которые называются AC-коэффициентами сохраняются без изменений.

Шаг 7. Свертываем получившиеся пары с помощью неравномерных кодов Хаффмана с фиксированной таблицей. Причем для DC и AC коэффициентов используются разные коды, т.е. разные таблицы с кодами Хаффмана.

Рис. 3. Схема упорядочения DC коэффициентов

Рис. 4. Структурная схема алгоритма JPEG

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать изображения в 10-15 раз без заметных визуальных потерь.

При разработке данного стандарта руководствовались тем, что данный алгоритм должен был сжимать изображения довольно быстро – не более минуты на среднем изображении. Это в 1991 году! А его аппаратная реализация должна быть относительно простой и дешевой. При этом алгоритм должен был быть симметричным по времени работы. Выполнение последнего требования сделало возможным появление цифровых фотоаппаратов, снимающие 24 битные изображения. Если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат «перезарядится» - сожмет изображение.

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

Область применения

Формат является форматом сжатия с потерями, поэтому некорректно считать что JPEG хранит данные как 8 бит на канал (24 бит на пиксел). С другой стороны, так как данные, подвергающиеся компрессии по формату JPEG и декомпрессированые данные обычно представляются в формате 8 бит на канал, иногда используется эта терминология. Поддерживается также сжатие чёрно-белых полутоновых изображений.

При сохранении JPEG-файла можно указать степень качества, а значит и степень сжатия, которую обычно задают в некоторых условных единицах, например, от 1 до 100 или от 1 до 10. Большее число соответствует лучшему качеству, но при этом увеличивается размер файла. Обыкновенно, разница в качестве между 90 и 100 на глаз уже практически не воспринимается. Следует помнить, что восстановленное из формата JPEG изображение не является точной копией оригинала. Распространённым заблуждением является мнение о том, что качество JPEG тождественно доле сохраняемой информации.

Широкая поддержка формата JPEG разнообразным ПО нередко приводит к кодированию в JPEG изображений, для того не предназначенных - безо всякого выигрыша по степени сжатия в сравнении с правильно сделанными PNG или GIF, но с прискорбными последствиями для качества. Например, попытка записать в JPEG изображение, содержащее мелкие контрастные детали (особенно, цветные) приведёт к появлению характерных хорошо заметных артефактов даже при высокой «степени качества».

Сжатие

При сжатии изображение преобразуется из цветового пространства RGB в YCbCr (YUV). Следует отметить, что стандарт JPEG (ISO/IEC 10918-1) никак не регламентирует выбор именно YCbCr, допуская и другие виды преобразования (например, с числом компонентов, отличным от трёх), и сжатие без преобразования (непосредственно в RGB), однако спецификация JFIF (JPEG File Interchange Format, предложенная в 1991 году специалистами компании C-Cube Microsystems, и ставшая в настоящее время стандартом де-факто) предполагает использование преобразования RGB->YCbCr.

После преобразования RGB->YCbCr для каналов изображения Cb и Cr, отвечающих за цвет, может выполняться "прореживание" (subsampling, которое заключается в том, что каждому блоку из 4 пикселов (2х2) яркостного канала Y ставятся в соответствие усреднённые значения Cb и Cr (схема прореживания "4:2:0". При этом для каждого блока 2х2 вместо 12 значений (4 Y, 4 Cb и 4 Cr) используется всего 6 (4 Y и по одному усреднённому Cb и Cr). Если к качеству восстановленного после сжатия изображения предъявляются повышенные требования, прореживание может выполняться лишь в каком-то одном направлении — по вертикали (схема "4:4:0") или по горизонтали ("4:2:2"), или не выполняться вовсе ("4:4:4").

Стандарт допускает также прореживание с усреднением Cb и Cr не для блока 2х2, а для четырёх расположенных последовательно (по вертикали или по горизонтали) пикселов, то есть для блоков 1х4 или 4х1 (схема "4:1:1"). Допускается также использование различных типов прореживания для Cb и Cr, но на практике такие схемы встречаются исключительно редко.

Далее, яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются на блоки 8х8 пикселов. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП). Полученные коэффициенты ДКП квантуются (для Y, Cb и Cr в общем случае используются разные матрицы квантования) и пакуются с использованием кодов Хаффмана. Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования, однако, из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно не используется.

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

Разновидности схем сжатия JPEG

Стандарт JPEG предусматривает два основных способа представления кодируемых данных.

Наиболее распространённым, поддерживаемым большинством доступных кодеков, является последовательное (sequential JPEG) представление данных, предполагающее последовательный обход кодируемого изображения поблочно слева направо, сверху вниз. Над каждым кодируемым блоком изображения осуществляются описанные выше операции, а результаты кодирования последовательно помещаются в выходной поток в виде единственного «скана» (массива кодированных данных). Основной или «базовый» (baseline) режим кодирования допускает только такое представление. Расширенный (extended) режим наряду с последовательным допускает также прогрессивное (progressive JPEG) представление данных.

В случае progressive JPEG сжатые данные записываются в выходной поток в виде набора сканов, каждый из которых описывает изображение полностью с всё большей степенью детализации. Это достигается либо путём записи в каждый скан не полного набора коэффициентов ДКП, а лишь какой-то их части: сначала — низкочастотных, в следующих сканах — высокочастотных (метод «spectral selection» т.е. спектральных выборок), либо путём последовательного, от скана к скану, уточнения коэффициентов ДКП (метод «successive approximation», т.е. последовательных приближений). Такое прогрессивное представление данных оказывается особенно полезным при передаче сжатых изображений с использованием низкоскоростных каналов связи, поскольку позволяет получить представление обо всём изображении уже после передачи незначительной части JPEG-файла.

Обе описанные схемы (и sequential, и progressive JPEG) базируются на ДКП и принципиально не позволяют получить восстановленное изображение абсолютно идентичным исходному. Однако, стандарт допускает также сжатие, не использующее ДКП, а построенное на основе линейного предсказателя (lossless, т.е. «без потерь», JPEG), гарантирующее полное, бит-в-бит, совпадение исходного и восстановленного изображений. При этом коэффициент сжатия для фотографических изображений редко достигает 2, но гарантированное отсутствие искажений в некоторых случаях оказывается востребованным. Заметно большие степени сжатия могут быть получены при использовании не имеющего, несмотря на сходство в названиях, непосредственного отношения к стандарту JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) метода сжатия JPEG-LS, описываемого стандартом ISO/IEC 14495-1 (ITU T.87 Recommendation).

Синтаксис и структура

Файл JPEG содержит последовательность маркеров, каждый из которых начинается с байта 0xFF, свидетельствующего о начале маркера, и байта — идентификатора. Некоторые маркеры состоят только из этой пары байтов, другие же содержат дополнительный данные, состоящие из двухбайтового поля с длиной информационной части маркера (включая длину этого поля, но за вычетом двух байтов начала маркера т.е. 0xFF и идентификатора) и собственно данных.

Основные маркеры JPEG

Маркер	Байты	Длина	Назначение

Фотографии и картинки отличаются друг от друга не только по содержанию, но и по другим «компьютерным» характеристикам. Например, по размеру.

Бывает так, что, вроде бы, два одинаковых рисунка, но у одного размер в три раза больше, чем у другого.

Также изображения отличаются по качеству. Думаю, Вам не раз встречались фото крайне плохого качества. Это видно невооруженным глазом. Например, две одинаковые фотографии, но одна лучшего качества, а другая - худшего.

А бывает так, что рисунку как будто не хватает красок. Вот пример.

И за все это отвечает формат или тип файла.

Вообще-то изображения бывают самых разных форматов. И существует их очень и очень много. Мы не будем рассматривать их все, а поговорим про самые распространенные. Это такие форматы, как bmp, gif, jpg, png, tiff .

Отличаются он друг от друга, в первую очередь, качеством. А качество отличается по количеству (насыщенности) цветов.

Например, я рисую картину, используя разные цвета . И тут вдруг часть из них закончилась, и приходится дорисовывать тем, что есть. Я, конечно, постараюсь сделать всё возможное, чтобы это не сильно отразилось на результате, но все равно картина получится не такая, как хотелось бы - более блеклая, размытая.

Вот так и с форматами изображений. Какой-то оставляет все цвета, другой же обрезает часть. И, бывает, из-за этого картинка портится.

Это довольно грубый пример. На самом деле, там все несколько сложнее, но, думаю, главное Вы уловили.

Распространенные форматы изображений

BMP - формат рисунков, сделанных в программе Paint . Его можно использовать для хранения нарисованных картинок на компьютере. Но вот в Интернете такой тип файлов не используется из-за большого объема. Так что если Вы хотите опубликовать картинку, нарисованную в Paint, в блоге или социальной сети , она должна быть другого типа - gif, jpg или png.

GIF - популярный формат картинок в Интернете. В нем можно сохранять их без потери качества, но с ограниченным количеством цветов - 256. Особую популярность gif получил благодаря тому, что в нем можно создать небольшие анимированные (движущиеся) картинки.

JPG - формат фотографий и картин с большим количеством цветов. В нем можно сохранить изображение как без потери качества, так и с потерей.

PNG - современный формат рисунков. Изображение такого типа получается небольшого размера и без потери качества. Очень удобно: и файл маленький, и качество хорошее. А еще он поддерживает прозрачность.

TIFF - изображения очень хорошего качества, без сжатия.Соответственно, и размер у таких файлов огромный. TIFF используют тогда, когда качество имеет большое значение. Например, при создании визиток, буклетов, журнальных обложек.

Какой формат выбрать

BMP - если это рисунок, сделанный в программе Paint, и Вы собираетесь держать его только в компьютере.
GIF - если анимация или рисунок с небольшим количеством цветов для публикации в Интернете.
PNG - если это рисунок, в котором много цветов или есть какие-то прозрачные части.
JPG (jpeg) - если фотография.
TIFF - изображение для полиграфии (визитки, буклеты, плакаты и т.д.).

Здравствуйте, уважаемые друзья. Сегодня поговорим о том, какой формат изображения лучше использовать на сайте, какие сегодня доступны форматы графических файлов для сайта и нужно ли гнаться за новинками графических форматов.

Таких вопросов я получаю довольно много, многие из моих учеников спрашивают можно ли им использовать новые форматы SVG и WebP, и где лучше применить эти изображения. Разумеется, можно использовать и новые форматы, только нужно понимать какой формат и для чего подходит лучше.

На сегодняшний день изображения на сайте являются неотъемлемой частью. Начиная от графического дизайна и закачивая изображениями в статьях, графика сопровождает большинство сайтов в сети. Но за красоту приходится расплачиваться

Не оптимизированные изображения являются одним из факторов замедления сайта, на что указывают сервисы проверки.

Поэтому вы будете всегда перед выбором, какой формат выбрать для изображения. От этого будет зависеть его размер и качество. А чтобы использовать изображения меньшего размера и без потери качества, вы должны знать некоторые вещи.

Какие изображения для сайтов использую сегодня

Все изображения для сайтов, подразделяются:

растровые (пример - JPG, JPEG, GIF, PNG),
векторные (пример - SVG).

Растровые изображения состоят из пикселей, в которых хранится цвет и значение прозрачности. Такими форматами представлены изображения в статьях, кнопками, иконками и элементами дизайна. Эти изображения популярны среди разработчиков и владельцев сайтов. Основной минус растровых изображений – они плохо масштабируются.

То есть при увеличении размера картинки, идёт потеря качества.

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

Все эти изображения могут и используются на современных сайтах. Только нужно понимать, что перед загрузкой на сайт, !

Описание популярных форматов изображения для сайта

Из описания этих форматов вы поймёте, где и какой формат применять лучше всего на сайте.

JPEG

JPEG или JPG – один из самых популярных форматов изображений для сайтов. Формат поддерживает миллионы цветов, что и даёт ему лидирующую позицию в представлении фотографий и картинок на сайте.

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

Файлы этого формата поддерживаются всем устройствами и браузерами, что ещё раз подтверждает его популярность и позволяет не беспокоиться за проблемы с отображением на сайтах.

Большим недостатком этого формата является отсутствие прозрачности. То есть, комбинировать изображения в таком формате не получится. Для таких задач лучше использовать следующий формат.

PNG

Этот формат использует алгоритм сжатия без потери качества. По количеству цветов и уровню прозрачности доступен в двух видах 8 и 24-бит. Оба поддерживают прозрачность.

8-битный пользуется малой популярностью, а вот 24-битный широко используется для различных изображений на сайте. За счёт прозрачности позволяет создавать комбинированные изображения. Часто используется для создания анимированных кнопок, иконок, где необходим эффект прозрачности.

Изображения в формате PNG можно много раз оптимизировать, редактировать – оно сохранит первоначальное качество.

Формат также поддерживается всеми браузерами и устройствами, что гарантирует его отображение на любом экране.

По качеству изображения выглядят лучше, чем JPG, но вес файла будет больше. Это нужно учитывать при размещении файлов на сайте.

GIF

Это 8-битный формат, поддерживающий 256 цветов, прозрачность и анимацию. За счёт поддержки малого количества цветов, вес файла тоже минимальный.

Формат не подходит для фотографий и изображений с широким диапазоном цветов.

Зато широко используется при создании, баннеров, кнопок, иконок и так далее.

В современных сайтах этот формат используется всё реже.

Далее поговорим об относительно свежих форматах SVG и WebP, которые не так популярны, но набирают популярность и поддержку, и как нельзя лучше подходят под требования скорости загрузки и адаптивности сайтов.

SVG

Это формат векторных файлов на основе XML. Формат стал набирать популярность совсем недавно, так как ранее он слабо поддерживался в браузерах. И из-за проблем отображения никто не торопился его использовать.

На сегодняшний день SVG поддерживается всеми современными браузерами. Но, проблемы с отображением все, же встречаются.

Наиболее часто используют этот формат для простых изображений, таких как логотипы, элементы дизайна и так далее. Неприменим для фотографий.

Формат SVG имеет малый вес, отлично масштабируются, обеспечивая чёткость изображения на любом разрешении экрана, поддерживает анимацию, можно управлять через CSS и размещать в HTML, сокращая количество запросов.

WebP

Формат с открытым исходным кодом, разработан Google специально для интернета. Сегодня YouTube использует преобразование миниатюр для видео в формат WebP.

Формат обеспечивает превосходное сжатие и поддерживает прозрачность. Он сочетает в себе преимущества JPG и PNG форматов без увеличения размера файла.

Но, несмотря на преимущества формата, он поддерживается не всем браузерами, например, IE, Edge, Firefox и Safari.

Существуют способы обхода этих ограничений, но они не дают использовать формат повсеместно.

Заключение

Друзья, надеюсь, объяснил всё понятно, и вы теперь знаете, какой формат изображений лучше использовать на сайте, и почему я не настаиваю на использовании одного какого-то формата, а рекомендую комплексный подход.

Возможно, когда WebP получит широкую поддержку, мы все перейдём на него и заменим jpg и png на своих сайтах.

Давайте обсудим в комментариях, какие вы используете форматы на своих сайтах, что нравится и что не нравится.

На сегодня у меня всё, жду ваших комментариев.

С уважением, Максим Зайцев.

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

Формат файла, в котором хранится изображение - это, по сути, определенный компромисс между качеством изображения и размером файла.

Наверное вы уже знаете о том, что растровое изображение состоит из пикселей. Как организован растровый файл и в каком виде в нем хранится информация о пикселях и определяет формат файла. Качество изображения для растрового файла определяется двумя основными параметрами: размером пикселя (то есть общим количеством пикселей) и точностью передачи реального цвета цветом пикселя. С размером пикселя понятно – чем больше пикселей (или – чем «мельче» пиксель), тем лучше. А точность передачи цвета зависит от количества цветов на пиксель или глубиной цвета.

Глубина цвета (качество цветопередачи, битность изображения) - объём памяти в количестве бит, используемых для хранения и представления цвета при кодировании одного пикселя растровой графики или видеоизображения. Количество бит говорит о количестве градаций (тональных ступеней) в каждой цветовой составляющей или, просто – о количестве цветов. Добавление 1 бита – это добавление еще одного разряда в двоичном коде цветности.

1-битный цвет (21 = 2 цвета) бинарный цвет, чаще всего представляется чёрным и белым цветами (или черный и зелёный)
2-битный цвет (22 = 4 цвета) CGA, градации серого цвета NeXTstation
3-битный цвет (23 = 8 цветов) множество устаревших персональных компьютеров с TV-выходом
4-битный цвет (24 = 16 цветов) известен как EGA и в меньшей степени как VGA-стандарт с высоким разрешением
5-битный цвет (25 = 32 цвета) Original Amiga chipset
6-битный цвет (26 = 64 цвета) Original Amiga chipset
8-битный цвет (28 = 256 цветов) Устаревшие Unix- рабочие станции, VGA низкого разрешения, Super VGA, AGA
12-битный цвет (212 = 4,096 цветов) некоторые Silicon Graphics-системы, цвет NeXTstation-систем, и Amiga- систем HAM-режима.

Например, мы работаем в цветовом пространстве RGB. Значит, есть три канала, из которых образуется итоговый цвет пикселя: красный канал (Rad), зеленый канал (Green), синий канал (Blue). Предположим, каналы четырехбитные. Значит, в каждом канале есть возможность отобразить 16 цветов. В итоге, весь RGB будет 12-битным, а отобразить он сумеет

C=16х16х16=4096 цвета

Глубина цвета в этом случае – 12 бит.

Когда говорят о 24-битном RGB, имеют в виду 8-битные каналы (по 256 цветов) с общим количеством цветовых вариантов на один пиксель

C=256x256x256=16777216 цветов.

Цифра впечатляет. Такое количество цветов для каждого пикселя удовлетворяет требованиям самого взыскательного фотохудожника.

Немного о самих форматах.

Формат TIFF

TIFF расшифровывается как «формат файла размеченного изображения» (Tagged Image File Format) и является стандартом для типографской и печатной индустрии.

В итоге, получается вот что:

1. Если ваша камера настолько проста, что снимает только JPEG, и вы хотите получить максимальное качество, задавайте максимальный размер и минимальное сжатие и не терзайте себя тем, что у вас нет других форматов. В большинстве случаев, кропотливо выведенный вручную снимок из RAW соответствует автоматически сделанному камерой JPEG.

2. Не стоит, пожалуй, фотографировать в TIFF. Запись этого формата идет тяжелее, а заметной разницы по сравнению с качественным JPEG нет.

3. Если у вас есть возможность делать снимки в , поработайте с ним. Вы сами почувствуете, подходит ли он вам. В некоторых случаях только RAW дает возможность сделать уникальное фото для большого увеличения при печати.

Остается еще одно решение, можно сказать универсальное. Есть режим, позволяющий делать кадры в двух форматах одновременно: RAW+ JPEG. Снимайте важные сюжеты в этом режиме. Современные хранилища цифровой информации – и карты памяти, и жесткие диски – позволяют это сделать. В таком случае вы получаете JPEG для использования фотографии сразу, без затрат времени на доработку. А, если понадобится этой – доверите файл RAW специалисту для обработки.

Фотография. Форматы файлов.

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

Алгоритмы сжатия без потерь;
Алгоритмы сжатия с потерями.

Алгоритмы сжатия без потерь

Алгоритм RLE

Словарные алгоритмы

Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.

В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.

Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.

Алгоритмы статистического кодирования

Алгоритм Хаффмана

Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
Выбираются два свободных узла дерева с наименьшими весами
Создается их родитель с весом, равным их суммарному весу
Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0
Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов.

Арифметическое кодирование

Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.

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

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

Цветовая модель

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

Профессионалы используют две цветовые модели: HSL (Hue-Saturation-Lightness) и HSV (Hue-Saturation-Value). Интуитивно понятно, что яркостная компонента (Lightness) модели HSL и яркостная компонента (Value) модели HSV каждая по-своему определяют соотношение света и тени. Насыщенность (saturation) определяет уровень "чистого" цвета. Ненасыщенные цвета часто неформально называют "грязными" (greyish). Оттенок (Hue) - это то, что мы воспринимаем, как цвет предмета, например красный или серовато-зеленый. Здесь важно отметить удивительный факт: человеческое зрение более чувствительно к изменению освещенности, а не цвета как такового!

Различные реализации алгоритма сжатия JPEG используют различные цветовые системы. Используемая форматом JFIF система цветопередачи YCbCr во многом схожа со схемой, разработанной много лет назад для цветного телевидения.

Прореживание

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

С помощью прореживания (subsampling) регулируются цвета изображения цветного телевизора. Обычно в телевидение черно-белое изображение и информация о цвете передаются по отдельности. Причем информация о цвете передается в менее строгом виде, чем информация о яркости изображения.

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

Каждая компонента цвета обрабатывается отдельно, как если бы они были не одним цветным, а тремя полутоновыми изображениями. Если вы посмотрите на детальное изображение с большого расстояния, то вы различите лишь общий тон картины. Например, "главным образом синий" или "преимущественно красный". Чем ближе вы будете подходить к изображению, тем больше деталей сможете различить. Для эмуляции этого эффекта JPEG использует один математический прием, называемый дискретным косинусным преобразованием (DCT). DCT преобразует информацию о пикселах в информацию об изменении пикселов. Первое, что может дать DCT - усредненный цвет области. Затем он все больше и больше уточняет детали.

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

Считается, что потери обусловливаются именно этим этапом. Если вы с помощью DCT закодируете изображение и затем с помощью функции обратного DCT восстановите его, то вы не получите абсолютно такой же набор бит. Однако эта ошибка - ошибка округления. Она возникает при выполнении арифметических действий и обычно не очень велика. Поэтому я предпочитаю думать об этапе DCT, как о действии, происходящем "в основном без потерь".

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

Квантование

Разработчиков JPEG прежде всего интересовали изображения фотографического качества (photographic, contnuous tone). Как правило, эти полутоновые изображения характеризуются мягкими переходами от одного цвета к другому. Для таких изображений низкочастотная (медленно изменяющаяся) компонента DCT важнее высокочастотной (быстро меняющаяся).

Термин квантование (quantization) означает просто "округление". JPEG отбрасывает некоторую графическую информацию за счет округления каждого члена DCT с различными весовыми коэффициентами, опираясь при этом на различные факторы. Высокочастотная компонента округляется сильнее низкочастотной. Например, низкочастотная компонента, которая хранит среднюю величину яркости, может быть округлена до значения, кратного трем, в то время как высокочастотная компонента может быть округлена до значения, кратного ста!

Операция квантования объясняет, почему сжатие JPEG в случае четких контуров приводит к образованию "дрожащих" линий. Контуры определяются высокочастотной (быстро меняющейся) пространственной компонентой. (На первый взгляд может показаться, что вы должны получить размытый контур, однако вспомните, что C в сокращении DCT обозначает косинус.)

Обычно цветовые плоскости квантуются гораздо грубее плоскостей яркости. Здесь правильный выбор цветовой модели помогает выявлять ту информацию, которую можно отбросить.

Сжатие

До сих пор, за исключением того случая, когда рассматривалась частота выборки из двух цветовых каналов, никакого сжатия не происходило. Все рассмотренные выше шаги - преобразование цветовых моделей, DCT и квантование - оставляли размер данных без изменений. Наконец мы добрались до последнего шага, во время которого с помощью стандартной техники сжатия без потерь действительно будет уменьшен размер данных.

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

Изменение цветовой модели позволило проредить информацию каналов и затем более энергично их квантовать.

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

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

Стандарт JPEG предоставляет два различных метода сжатия без потерь, которые могут быть использованы на последнем этапе. Сжатие Хаффмана (Huffman compression - это давно известный незапатентованный, легко программируемый алгоритм. В отличие от него более новый алгоритм арифметического кодирования (arithmetic coding) является объектом многочисленных патентов. (Поэтому не удивительно, что многие программы сжатия JPEG поддерживают только сжатие Хаффмана.)

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