Как устроен формат JPEG?⁠⁠

Всем привет! Недавно записал видео о том, как устроен формат mp3. Делаю для Ютюба, но еще выложил на Пикабу. Самый первый комментарий был - зачем делать видео, где достаточно текста и картинок.

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

JPEG - это формат сжатия изображений, который позволяет уменьшить размер файла в 20, 30, 100 раз! В посте НЕ будет описана история создания формата, его плюсы и минусы и самые тонкие технические детали. Это обзорное повествование о том, как происходит сжатие (в очень упрощенном, и от этого более понятном виде) и как работает технология. Пикабушников не удивить шакалами, но здесь как раз объясняется, откуда они берутся.

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

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

Нетрудно посчитать, что такая картинка без сжатия будет весить:

8 х 3 х 1000 х 1000 = 24 000 000 бит, то есть 3 мегабайта.

Но если сохранить ее в джипеге, она может занимать, например, 90 килобайт. То есть в 33 раза меньше! Да, качество чуть-чуть теряется, но не в 30 раз ведь! Как же это работает?

Итак. Алгоритм сжатия джипега можно разбить на несколько основных этапов

1 - Цветовое пространство

Этап первый – перевод в другое цветовое пространство, в котором разделены яркостная и цветовая составляющие. На этом шаге потерь не происходит, ведь каждый пиксель по-прежнему состоит из трех компонентов. Только теперь это яркостная компонента и две цветовых. Короче, если упростить, происходит следующее: создается Ч/Б изображение и цветовая маска к нему, вот и все!

2 - Ресемплинг

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

Это и происходит на втором этапе – ресэмплинге. Каждые 4 цветовых пикселя объединяются в один. Да, происходит потеря некоторых деталей, но… это практически незаметно! И на таком приеме уже удается сжать файл в 2 раза!

3 - Блоки 8х8

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

4 - Дискретное косинусное преобразование

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

Делается такой анализ с помощью дискретного косинусного преобразования. Это разновидность преобразования Фурье, которое, кстати, и в mp3 применяется. Сложная, но очень интересная штука!

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

Дискретное косинусное преобразование производит разложение по спектру пространственных волн. Что же это такое? Любую монохромное изображение 8 на 8 пикселей можно представить как смесь из 64 картинок, на которых посмотрите что изображено:

Вот такие вот периодические плавные переходы! Это и есть пространственные волны разной длины (по горизонтали и вертикали). Есть другая версия отображения этих пространственных волн, трехмерная. Кому как удобнее для понимания:

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

Дискретное косинусное преобразование (DCT) как раз вычисляет коэффициенты для наложения каждой такой базовой картинки. Всего 64 числа:

И обратите внимание! Коэффициент это вес, важность этой составляющей. Здесь есть те, которые отвечают за плавные переходы. И те, которые отвечают за более частые.

Как раз, если деталей мало, то коэффициенты у последних будут практически нулевыми, ведь зачем добавлять такую рябь, если блок почти монотонный? И вот тут и начинается по-настоящему мощное сжатие!

5 - Квантование

Начинается этап квантования! Матрица коэффициентов делится на матрицу квантования, которая зависит от настроек сжатия. Например, если вы сохраняете JPEG со 100% сжатием, каждый коэффициент делится на 1 (то есть остается таким же). Если вы сохраняете с меньшим качеством, то каждый коэффициент делится на определенное число (опять же в зависимости от выбранного качества).

Далее производится округление поделенных коэффициентов до целого значения. И при сильном сжатии многие из них округляются до нуля:

Да, на этом шаге теряется много информации. Да, из-за этих округлений, при прочтении файла и вылезает куча шакалов, артефактов и прочего. Но! Основная суть остается! Ну, а дальше сжать файл, напичканный нулями – дело техники!

6 - Сжатие

Сначала матрица коэффициентов сканируется зиг-загом:

Получается последовательность чисел в конце которой зачастую одни нули:

Затем последовательность пакуется хитрым способом. Если в ней есть длинная череда нулей, НЕ кодируется каждый из них. Вместо этого просто указывается одно число, обозначающее сколько их. Это очень сильно сжимает размер файла! Довольно упрощенно это может выглядеть так:

Ну и в конце сжатая последовательность кодируется кодом Хаффмана.

Каждому символу приваивается определенный код. Например, (опять же упрощенно) так:

Обратите внимание, код присваивается не абы как, а по степени встречаемости в файле. Чем чаще появляется символ, тем короче у него код.

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

Затем все блоки 8 на 8 склеиваются в один файл и получается красивенький, маленький джипег!) Вот кстати портрет шведской модели Лены Сёдерберг из журнала Playboy. Так сложилось исторически, что с 1973 года это изображение используется для проверки практически всех алгоритмов обработки изображений. В то числе и JPEG. Поговаривают даже, что JPEG был оптимизирован как раз для того, чтобы как можно лучше сжать эту картинку)

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

Спасибо всем, кто дочитал до конца! Это мой первый длинопост, не судите строго) Баянометр ругался только на Лену, но это культовое фото!

Полезные ссылки:

Как устроен формат mp3: https://youtu.be/z2EUT4gwkr4

Подробнее о JPEG: https://habrahabr.ru/post/206264/