Алгоритм сжатия файлов формата jpeg

Обновлено: 04.07.2024

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

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

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

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

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

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

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

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

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

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

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

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

Квантование

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

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

Сжатие

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

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

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

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

Вывод

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

Авторизуясь в LiveJournal с помощью стороннего сервиса вы принимаете условия Пользовательского соглашения LiveJournal

Живущая в Испании, или как можно больше из жизни в Испании. То, что фотография до бесконечности воспроизводит, имело место всего один раз. Алгоритм JPEG является алгоритмом сжатия данных с потерями.

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

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

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

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

После преобразования 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-файла.

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

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

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

Маркер	Байты	Длина	Назначение	Комментарии
SOI	0xFFD8	нет	Начало изображения
SOF0	0xFFC0	переменный размер	Начало фрейма (базовый, ДКП)	Показывает что изображение кодировалось в базовом режиме с использованием ДКП и кода Хаффмана. Маркер содержит длину, высоту, количество компонентов, число бит на компонент и соотношение компонентов (например, 4:2:0).
SOF2	0xFFC2	переменный размер	Начало фрейма (прогрессивный, ДКП, код Хаффмана)	Показывает что изображение кодировалось в прогрессивном режиме с использованием ДКП и кода Хаффмана. Маркер содержит длину, высоту, количество компонентов, число бит на компонент и соотношение компонентов (например, 4:2:0).
DHT	0xFFC4	переменный размер	Содержит таблицы Хаффмана	Задает одну или более таблиц Хаффмана.
DQT	0xFFDB	переменный размер	Содержит таблицы квантования	Задает одну или более таблиц квантования.
DRI	0xFFDD	4 байта	Указывает интервал повторений	Задает интервал между маркерами RST n, в макроблоках.
SOS	0xFFDA	переменный размер	Начало сканирования	Начинает сканирование изображение сверху вниз. Если использовался базовый режим кодирования, используется один скан. При использовании прогрессивных режимов используется несколько сканов. Маркер SOS является разделяющим между информативной и закодированной частью изображения.
RSTn	0xFFDn	нет	Перезапуск	Вставляется в каждом r макроблоке, где r — интервал перезапуска DRI маркера. Не используется при отстутствии DRI маркера. n, младшие 3 бита маркера кода, циклы от 0 до 7.
APPn	0xFFEn	переменный размер	Задается приложением	Например, в Exif JPEG файле используется APP1 маркер для хранения метаданных, расположены в структуре, основанной на TIFF.
COM	0xFFFE	переменный размер	Комментарий	Содержит текст комментария.
EOI	0xFFD9	нет	Конец закодированной части изображения.

Достоинства и недостатки

К недостаткам формата следует отнести то, что при сильных степенях сжатия дает знать о себе блочная структура данных, изображение «дробится на квадратики» (каждый размером 8x8 пикселей). Этот эффект особенно заметен на областях с низкой пространственной частотой (плавные переходы изображения, например, чистое небо). В областях с высокой пространственной частотой (например, контрастные границы изображения), возникают характерные «артефакты» — иррегулярная структура пикселей искаженного цвета и/или яркости. Кроме того, из изображения пропадают мелкие цветные детали. Не стоит также забывать и о том, что данный формат не поддерживает прозрачность.

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

Читайте также: