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

И снова здравствуйте! Я нашел эту статью, написанную еще мае 2019-ого года. Это — продолжение серии статей о WAVE и JPEG, Вот первая. Эта публикация включит в себе информацию об алгоритме кодирования изображений и о самом формате в целом.

Щепотку истории

Столовую ложку статьи из Википедии:

JPEG (Joint Photographic Experts Group) — один из популярных растровых графических форматов, применяемый для хранения фотоизображений и подобных им изображений.

Разработан этот стандарт был Объединенной группой экспертов по фотографии еще в 1991 году для эффективного сжатия изображений.

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

Некоторые считают, что JPEG-картинки — сжатые методом Хаффмана сырые данные, но это не так. Перед контрольным сжатием данные проходят длинный путь.

Сначала цветовую модель меняют с RGB на YCbCr. Для этого даже есть специальный алгоритм — здесь. Y не трогают, так как он отвечает за яркость, и его изменение будет заметно.

Первое, что делают с изображением — это «прореживание» (subsampling). Понять это просто: берется 2х2 массив пикселей, далее берутся Cb и Cr — средние значения каждого из компонентов YCbCr этих 4 пикселей. И так, мы выиграли 6 байт, вместо 4 Y, 4 Cb, 4 Cr мы получили 4 Y и одинаковые для каждого из них Cb и Cr (4 + 4 + 4 = 12; 4 + 1 + 1 = 6; 12 — 6 = 6). В масштабах даже 2×2 сжатие с потерей с коэффициентом сжатия 2:1 звучит солидно. Это применяется ко всему изображению. И так — сбросили половину размера. А такой прием мы можем использовать благодаря нашему цветовому восприятию. Человек с легкостью заметит разницу в яркости, но не в цвете, если он усредненный в маленьком блоке пискелей. Также прореживание может выполняться в линию, 4 пикселя по горизонтали и вертикали. Первый вариант используется чаще. Если важно качество изображения, то прореживание не выполняется вообще.
Наглядная иллюстрация прореживания (Хабр не дал вставить гифку) — https://i.ibb.co/Rg5Th9H/150953010617579181.gif

Основная часть подготовки

ДКП

Теперь самая сложная и необходимая часть. Вся картинка разбивается на блоки 8×8 (используют заполнение в случае, если разрешение не кратно стороне блока).

Теперь к каждому блоку применяют ДКП (Дискретно-косинусное преобразование). В этой части из картинки вынимают все лишнее. Используя ДКП надо понять, описывает ли данный блок (8×8) какую-нибудь монотонную часть изображения: неба, стены; или он содержит сложную структуру (волосы, символы и т.д.). Логично, что 64 похожих по цвету пикселей можно описать всего 1-им, т.к. размер блока уже известен. Вот вам и сжатие: 64 к 1.

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

Квантование

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

Квантование делают для создания возможности еще большего сжатия. Вот как это выглядит на примере квантования графика y = sin(x):

Сжатие

Сначала проходим по матрице зиг-загом:

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

Где используется

Везде. Как и PNG, JPEG используется в фотокамерах, OS’ях (в качестве логотипов компании, иконок приложений, thumbnail’ов) и во всех возможных сферах, где нужно эффективно хранить изображения.

Вывод

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

Источники

Статья про YCbCr на Википедии
Статья о JPEG на Википедии
Немного про ДКП с поста Пикабу
Статья о ДКП на Википедии