как прочитать код jpeg

Декодируем JPEG-изображение с помощью Python

Всем привет, сегодня мы будем разбираться с алгоритмом сжатия JPEG. Многие не знают, что JPEG — это не столько формат, сколько алгоритм. Большинство JPEG-изображений, которые вы видите, представлены в формате JFIF (JPEG File Interchange Format), внутри которого применяется алгоритм сжатия JPEG. К концу статьи вы будете гораздо лучше понимать, как этот алгоритм сжимает данные и как написать код распаковки на Python. Мы не будем рассматривать все нюансы формата JPEG (например, прогрессивное сканирование), а поговорим только о базовых возможностях формата, пока будем писать свой декодер.

Введение

Зачем писать ещё одну статью про JPEG, когда об этом написаны уже сотни статей? Обычно в таких статьях авторы рассказывают лишь о том, что собой представляет формат. Вы не пишете код распаковки и декодирования. А если и напишете что-то, то на С/С++, и этот код будет недоступен широкому кругу людей. Я хочу нарушить эту традицию и показать вам с помощью Python 3, как работает базовый декодер JPEG. В его основе будет этот код, разработанный MIT, но я его сильно изменю ради удобочитаемости и понятности. Изменённый для этой статьи код вы найдёте в моём репозитории.

Разные части JPEG

Начнём с картинки, сделанной Ange Albertini. На ней перечислены все части простого JPEG-файла. Мы разберём каждый сегмент, и по мере чтения статьи вы не раз будете возвращаться к этой иллюстрации.

Почти каждый двоичный файл содержит несколько маркеров (или заголовков). Можете считать их своего рода закладками. Они крайне важны для работы с файлом и используются такими программами как file (на Mac и Linux), чтобы мы могли узнать подробности о файле. Маркеры указывают, где именно в файле хранится определённая информация. Чаще всего маркеры размещаются в соответствии со значением длины ( length ) конкретного сегмента.

Начало и конец файла

Мы будем работать с этим изображением:

Давайте напишем код для поиска маркеров начала и конца файла.

После раздела Start of Scan сразу идут данные сканированного изображения, у которых нет определённой длины. Они продолжаются до маркера «конец файла», так что пока мы вручную «ищем» его, когда находим маркер Start of Scan.

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

Кодирование JPEG

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

Иллюстрация ниже пока что для вас непонятно, однако я буду давать вам подсказки по мере изучения процесса кодирования и декодирования. Здесь показаны этапы JPEG-кодирования (источник):

Цветовое пространство JPEG

Согласно спецификации JPEG (ISO/IEC 10918-6:2013 (E), раздел 6.1):

Как в RGB каждый пиксель кодируется тремя байтами цветов (красного, зелёного и синего), так и в YUV используется три байта, однако их значение другое. Компонент Y определяет яркость цвета (luminance, или luma). U и V определяют цвет (chroma): U отвечает за долю синего цвета, а V — за долю красного.

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

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

JPEG преобразует изображение в блоки 8×8 пикселей (называются MCU, Minimum Coding Unit — минимальные единицы кодирования), меняет диапазон значений пикселей так, чтобы в центре было значение 0, затем применяет к каждому блоку дискретное косинусное преобразование и сжимает результат с помощью квантования. Давайте разберёмся, что всё это означает.

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

Матрица выглядит так:

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

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

Я нашёл отличное видео по этой теме. Посмотрите, если не понимаете смысла ДКП:

Все мы знаем, что JPEG — алгоритм сжатия с потерями. Но пока что мы ничего не потеряли. У нас есть только блоки 8х8 YUV-компонентов, преобразованные в блоки 8х8 косинусных функций без потери информации. Этап потери данных — это квантование.

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

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

Рассмотрим пример. Допустим, есть такая ДКП-матрица:

А вот обычная матрица квантования:

Квантованная матрица будет выглядеть так:

Хотя человек и не видит высокочастотную информацию, если вы удалите слишком много данных из блоков 8х8 пикселей, изображение станет выглядеть слишком грубо. В такой квантованной матрице самое первое значение называется DC-значением, а все остальные — AC-значениями. Если бы мы взяли DC-значения всех квантованных матриц и сгенерировали новую картинку, то получили бы превьюшку с разрешением в 8 раз меньше исходного изображения.

Также хочу отметить, что поскольку мы применяли квантование, нужно убедиться, что цвета попадают в диапазон [0,255]. Если они из него вылетают, то придётся вручную привести их к этому диапазону.

Зигзаг

После квантования алгоритм JPEG использует зигзаг-сканирование для преобразования матрицы к одномерному виду:

Пусть у нас такая квантованная матрица:

Тогда результат зигзаг-сканирование будет таким:

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

Кодирование длин серий и дельта-кодирование

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

После кодирования длин серий получим вот что:

Мы сжали 7 байтов в 2 байта.

Дельта-кодирование используется для представления байта относительно байта до него. Проще будет объяснить на примере. Пусть у нас такие данные:

С помощью дельта-кодирования их можно представить так:

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

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

Кодирование Хаффмана

Это метод сжатия информации без потерь. Однажды Хаффман задался вопросом: «Какое наименьшее количество битов я могу использовать для хранения произвольного текста?». В результате был создан формат кодирования. Допустим, у нас есть текст:

Обычно каждый символ занимает один байт пространства:

Это принцип двоичной кодировки ASCII. А если нам изменить сопоставление?

Теперь нам нужно гораздо меньше битов для хранения того же текста:

Всё это хорошо, но что если нам нужно ещё сильнее сэкономить пространство? Например, так:

Кодирование Хаффмана позволяет использовать такое сопоставление переменной длины. Берутся входные данные, чаще всего встречающиеся символы сопоставляются с более маленьким сочетанием битов, а менее частые символы — с более крупными сочетаниями. А затем получившееся сопоставления собираются в двоичное дерево. В JPEG мы сохраняем ДКП-информацию с помощью кодирования Хаффмана. Помните, я упоминал, что дельта-кодирование DC-значений облегчает кодирование Хаффмана? Надеюсь, вы теперь понимаете, почему. После дельта-кодирования нам нужно сопоставить меньше «символов» и размер дерева уменьшается.

У Тома Скотта есть прекрасное видео, поясняющее работу алгоритма Хаффмана. Посмотрите, прежде чем читать дальше.

В JPEG содержится до четырёх таблиц Хаффмана, которые хранятся в разделе «Define Huffman Table» (начинается с 0xffc4 ). ДКП-коэффициенты хранятся в двух разных таблицах Хаффмана: в одной DC-значения из зигзаг-таблиц, в другой — АС-значения из зигзаг-таблиц. Это означает, что при кодировании нам нужно объединить DC- и АС-значения из двух матриц. ДКП-информация для каналов яркости и хроматичности хранится отдельно, так что у нас два набора DC- и два набора AC-информации, в сумме 4 таблицы Хаффмана.

Если изображение представлено в оттенках серого, то у нас только две таблицы Хаффмана (одна для DC и одна для AC), потому что нам не нужен цвет. Как вы уже могли понять, два разных изображения могут иметь очень разные таблицы Хаффмана, поэтому важно хранить их внутри каждого JPEG.

Теперь мы знаем основное содержимое JPEG-изображений. Переходим к декодированию.

Декодирование JPEG

Декодирование можно разделить на этапы:

Извлечение таблиц Хаффмана

Мы уже знаем, что JPEG содержит четыре таблицы Хаффмана. Это последний кодирования, поэтому декодировать мы начнём с него. В каждом разделе с таблицей содержится информация:

После вызова GetHuffmanBits список root будет содержать такие данные:

Декодирование таблицы квантования

Раздел Define Quantization Table содержит такие данные:

Если вывести матрицы квантования для нашей картинки, то получим вот что:

Декодирование начала кадра

Раздел Start of Frame содержит такую информацию (источник):

Здесь нам интересно не всё. Мы извлечём ширину и высоту картинки, а также количество таблиц квантования для каждого компонента. Ширину и высоту будем использовать для начала декодирования фактических сканов изображения из раздела Start of Scan. Поскольку мы будем работать по большей части с YCbCr-изображением, то можно предположить, что компонентов будет три, а их типы будут 1, 2 и 3 соответственно. Напишем код для декодирования этих данных:

Декодирование Start of Scan

Это «мяско» JPEG-изображения, оно содержит данные самой картинки. Мы дошли до самого важного этапа. Всё, что мы декодировали до этого, можно считать картой, которая помогает нам расшифровать само изображение. В этом разделе содержится сама картинка (в закодированном виде). Мы считаем раздел и расшифруем с помощью уже декодированных данных.

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

BuildMatrix возьмёт таблицу квантования и добавит параметры, создаст матрицу обратного дискретного косинусного преобразования и даст нам матрицы Y, Cr и Cb. А функция DrawMatrix преобразует их в RGB.

Если вы модифицируете зигзаг-таблицу в подобный вид:

то получите такой результат (обратите внимание на маленькие артефакты):

А если наберётесь храбрости, то можете ещё больше модифицировать зигзаг-таблицу:

Тогда результат будет таким:

Завершим наш метод BuildMatrix :

Мы начинаем с создания класса инвертирования дискретной косинусной трансформации ( IDCT() ). Затем считываем данные в битовый поток и декодируем с помощью таблицы Хаффмана.

self.huffman_tables[0] и self.huffman_tables[1] ссылаются на DC-таблицы для яркости и хроматичности соответственно, а self.huffman_tables[16] и self.huffman_tables[17] ссылаются на AC-таблицы для яркости и хроматичности соответственно.

Затем повторим ту же процедуру декодирования с AC-значениями в матрице квантования. Значение кода 0 говорит о том, что мы дошли до маркера окончания блока (End of Block, EOB) и должны остановиться. Более того, первая часть АС-таблицы квантования говорит нам, сколько у нас начальных нулей. Теперь вспоминаем про кодирование длин серий. Обратим этот процесс вспять и пропустим все эти многочисленные биты. В классе IDCT им явно присваиваются нули.

Метод BuildMatrix вернёт инвертированную ДКП-матрицу и значение DC-коэффициента. Помните, что это будет матрица только для одной минимальной единицы кодирования размером 8×8. Проделаем это для всех остальных MCU нашего файла.

Вывод изображения на экран

Теперь сделаем так, чтобы наш код в методе StartOfScan создавал Tkinter Canvas и рисовал каждый MCU после декодирования.

Заключение

Кто бы мог подумать, что для показа моего лица придётся написать объяснение более чем 6000 слов. Удивительно, насколько умны были авторы некоторых алгоритмов! Надеюсь, вам понравилась статья. Я очень многому научился, пока писал этот декодер. Не думал, что в кодировании простого JPEG-изображения используется столько математики. В следующий раз можете попробовать написать декодер для PNG (или другого формата).

Дополнительные материалы

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

Источник

Декодирование JPEG для чайников

[FF D8]

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

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

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

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

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов «:» и «)», т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

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

Закодированные данные располагаются поочередно, небольшими частями:

Каждый блок Y_ij, Cb_ij, Cr_ij — это матрица коэффициентов ДКП (так же 8×8), закодированная кодами Хаффмана. В файле они располагаются в таком порядке: Y₀₀Y₁₀Y₀₁Y₁₁Cb₀₀Cr₀₀Y₂₀.

Чтение файла

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

Маркер [FF DB]: DQT — таблица квантования

Оставшимися 64-мя байтами нужно заполнить таблицу 8×8.

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

Маркер [FF C0]: SOF0 — Baseline DCT

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

Находим H_max=2 и V_max=2. Канал i будет прорежен в H_max/H_i раз по горизонтали и V_max/V_i раз по вертикали.

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

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

Следующие 16 значений:

Количество кодов означает количество кодов такой длины. Обратите внимание, что секция хранит только длины кодов, а не сами коды. Мы должны найти коды сами. Итак, у нас есть один код длины 1 и один — длины 2. Итого 2 кода, больше кодов в этой таблице нет.
С каждым кодом сопоставлено значение, в файле они перечислены следом. Значения однобайтовые, поэтому читаем 2 байта:

Далее в файле можно видеть еще 3 маркера [FF C4], я пропущу разбор соответствующих секций, он аналогичен вышеприведенному.

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

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

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

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

Маркер [FF DA]: SOS (Start of Scan)

Байт [DA] в маркере означает — «ДА! Наконец-то то мы перешли к финальной секции!». Однако секция символично называется SOS.

[00], [3F], [00] — Start of spectral or predictor selection, End of spectral selection, Successive approximation bit position. Эти значения используются только для прогрессивного режима, что выходит за рамки статьи.

Отсюда и до конца (маркера [FF D9]) закодированные данные.

Закодированные данные

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

Нахождение DC-коэффициента

1) Читаем последовательность битов (если встретим 2 байта [FF 00], то это не маркер, а просто байт [FF]). После каждого бита сдвигаемся по дереву Хаффмана (с соответствующим идентификатором) по ветви 0 или 1, в зависимости от прочитанного бита. Останавливаемся, если оказались в конечном узле.

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

Нахождение AC-коэффициентов

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

2) Берем значение узла. Если оно равно 0, это означает, что оставшиеся значения матрицы нужно заполнить нулями. Дальше закодирована уже следующая матрица. В нашем случае значение узла: 0x31.

Читать AC-коэффициенты нужно пока не наткнемся на нулевое значение кода, либо пока не заполнится матрица.
В нашем случае мы получим:

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

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

Но! Закодированные DC-коэффициенты — это не сами DC-коэффициенты, а их разности между коэффициентами предыдущей таблицы (того же канала)! Нужно поправить матрицы:

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

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

Вычисления

Квантование

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

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

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

Формула не должна доставить сложностей. S_vu — наша полученная матрица коэффициентов. u — столбец, v — строка. C_x = 1/√2 для x = 0, а в остальных случаях = 1. s_yx — непосредственно значения каналов.

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

Ко всем полученным значениям нужно прибавить по 128, а затем ограничить их диапазон от 0 до 255:

Например: 138 → 266 → 255, 92 → 220 → 220 и т. д.

YCbCr в RGB

4 матрицы Y, и по одной Cb и Cr, так как мы прореживали каналы и 4 пикселям Y соответствует по одному Cb и Cr. Поэтому вычислять так: YCbCrToRGB(Y[y,x], Cb[y/2, x/2], Cr[y/2, x/2]):

Вот полученные таблицы для каналов R, G, B для левого верхнего квадрата 8×8 нашего примера:

Конец

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

Источник