Сжатие изображений с потерей качества. Алгоритм JPEG. Оценка потерь и способы их регулирования. Построение дерева кодов Хаффмана

• Tutorial

Вы правильно поняли из названия, что это не совсем обычное описание алгоритма JPEG (формат файла я подробно описывал в статье «Декодирование JPEG для чайников»). В первую очередь, выбранный способ подачи материала предполагает, что мы ничего не знаем не только о JPEG, но и о преобразовании Фурье, и кодировании Хаффмана. И вообще, мало что помним из лекций. Просто взяли картинку и стали думать как же ее можно сжать. Поэтому я попытался доступно выразить только суть, но при которой у читателя будет выработано достаточно глубокое и, главное, интуитивное понимание алгоритма. Формулы и математические выкладки - по самому минимуму, только те, которые важны для понимания происходящего.

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

Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.

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

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

Векторное представление

Для начала проверим насколько зависимы два соседних пикселя. Логично предположить, что скорее всего, они будут очень похожи. Проверим это для всех пар изображения. Отметим их на координатной плоскости точками так, что значение точки по оси X - значение первого пикселя, по оси Y - второго. Для нашего изображения размером 256 на 256 получим 256*256/2 точек:

Предсказуемо, что большинство точек находится на или рядом с прямой y=x (а их там еще больше, чем видно на рисунке, так как они многократно накладываются друг на друга, и, к тому же, они полупрозрачные). А раз так, то было бы проще работать, повернув их на 45°. Для этого нужно выразить их в другой системе координат.

Базисные вектора новой системы, очевидно, такие: . Вынуждены делить на корень из двойки, чтобы получить ортонормированную систему (длины базисных векторов равны единичке). Здесь показано, что некоторая точка p = (x, y) в новой системе будет представлена как точка (a 0 , a 1). Зная новые коэффициенты, мы легко можем получить старые обратным поворотом. Очевидно, первая (новая) координата является средним, а вторая - разностью x и y (но деленные на корень из 2). Представьте, что вам предложено оставить только одно из значений: либо a 0 , либо a 1 (то есть другое приравнять нулю). Лучше выбрать a 0 , так как значение a 1 и так, скорее всего, будет около нуля. Вот, что получится, если мы восстановим изображение только по a 0:

Увеличение в 4 раза:

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

Это один и тот же график, но с разных точек зрения. Красные линии - оси, которые напрашивались сами собой. Им соответствуют вектора: . Напоминаю, что приходится делить на некоторые константы, чтобы длины векторов стали равны единице. Таким образом, разложив по такому базису, мы получим 3 значения a 0 , a 1 , a 2 , причем a 0 важнее a 1 , а a 1 важнее a 2 . Если мы выбросим a 2 , то график «сплющится» в направлении вектора e 2 . Этот и так довольно не толстый трехмерный лист станет плоским. Он потеряет не так много, зато мы избавимся от трети значений. Сравним изображения, восстановленные по тройкам: (a 0 , 0, 0), (a 1 , a 2 , 0) и (a 0 , a 1 , a 2). В последнем варианте мы ничего не выбросили, поэтому получим оригинал.

Увеличение в 4 раза:

Второй рисунок уже хорош. Резкие участки немного сгладились, но в целом картинка сохранилась очень неплохо. А теперь, точно так же поделим на четверки и визуально определим базис в четырехмерном пространстве… А, ну да. Но можно догадаться, каким будет один из векторов базиса, это: (1,1,1,1)/2. Поэтому можно посмотреть проекцию четырехмерного пространства на пространство, перпендикулярное вектору (1,1,1,1), чтобы выявить другие. Но это не лучший путь.
Наша цель - научиться преобразовывать (x 0 , x 1 , ..., x n-1) к (a 0 , a 1 , ..., a n-1) так, что каждое значение a i все менее важно, чем предыдущие. Если мы сможем так делать, то, возможно, последние значения последовательности вообще можно будет выбросить. Вышеприведенные опыты намекают, что можно. Но без математического аппарата не обойтись.
Итак, нужно преобразовать точки к новому базису. Но сначала необходимо найти подходящий базис. Вернемся к первому эксперименту разбиения на пары. Будем считать обобщенно. Мы определили базисные векторы:

Выразили через них вектор p :

или в координатах:

Чтобы найти a 0 и a 1 нужно спроецировать p на e 0 и e 1 соответственно. А для этого нужно найти скалярное произведение

аналогично:

В координатах:

Часто бывает удобнее проводить преобразование в матричной форме.

Тогда A = EX и X = E T A. Это красивая и удобная форма. Матрица E называется матрицей преобразования и является ортогональной, с ней мы еще встретимся.

Переход от векторов к функциям.

С векторами малых размерностей работать удобно. Однако мы хотим находить закономерности в бОльших блоках, поэтому вместо N-мерных векторов удобнее оперировать последовательностями, которыми представлено изображение. Такие последовательности я буду называть дискретными функциями, так как следующие рассуждения применимы и к непрерывным функциям.
Возвращаясь к нашему примеру, представим такую функцию f(i), которая определена всего в двух точках: f(0)=x и f(1)=y. Аналогично зададим базисные функции e 0 (i) и e 1 (i) на основе базисов e 0 и e 1 . Получим:

Это очень важный вывод. Теперь во фразе «разложение вектора по ортонормированным векторам» мы можем заменить слово «вектор» на «функция» и получить вполне корректное выражение «разложение функции по ортонормированным функциям». Не беда, что мы получили такую куцую функцию, так как такие же рассуждения работают и для N-мерного вектора, который можно представить как дискретную функцию с N значениями. А работа с функциями нагляднее, чем с N-мерными векторами. Можно и наоборот, представить такую функцию как вектор. Более того, обычную непрерывную функцию можно представить бесконечномерным вектором, правда уже не в евклидовом, а гильбертовом пространстве. Но мы туда не пойдем, нас будут интересовать только дискретные функции.
А наша задача нахождения базиса превращается в задачу нахождения подходящей системы ортонормированных функций. В следующих рассуждениях предполагается, что мы уже как-то определили набор базисных функций, по которым и будем раскладывать.
Допустим, у нас есть некоторая функция (представленная, например, значениями), которую мы хотим представить в виде суммы других. Можно представлять этот процесс в векторном виде. Для разложения функции нужно «спроецировать» ее на базисные функции по очереди. В векторном смысле вычисление проекции дает минимальное сближение исходного вектора к другому по расстоянию. Помня о том, что расстояние вычисляется с помощью теоремы Пифагора, то аналогичное представление в виде функций дает наилучшее среднеквадратичное приближение функции к другой. Таким образом, каждый коэффициент (k) определяет «близость» функции. Более формально, k*e(x) - лучшее среднеквадратичное приближение к f(x) среди l*e(x).
В следующем примере показан процесс приближения функции только по двум точкам. Справа - векторное представление.

Применительно к нашему эксперименту разбивания на пары, можно сказать, что эти две точки (0 и 1 по абсцисс) - пара соседних пикселей (x, y).
То же самое, но с анимацией:

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

Дискретные преобразования Фурье (ДПФ)

В предыдущей части мы пришли к выводу, что неплохо было бы разлагать функцию на составные. В начале 19 века Фурье тоже задумался над этим. Правда картинки с енотом у него не было, поэтому ему пришлось исследовать распределение тепла по металлическому кольцу. Тогда он выяснил, что очень удобно выражать температуру (и ее изменение) в каждой точке кольца как сумму синусоид с разными периодами. «Фурье установил (рекомендую к прочтению , интересно), что вторая гармоника затухает в 4 раза быстрее, чем первая, а гармоники более высоких порядков затухают с ещё большей скоростью».
В общем, вскоре оказалось, что периодичные функции замечательно раскладываются на сумму синусоид. А так как в природе существует много объектов и процессов, описывающимися периодичными функциями, то появился мощный инструмент их анализа.
Пожалуй, один из самых наглядных периодических процессов - это звук.

• 1-й график - чистый тон частотой 2500 герц.
• 2-й - белый шум. Т. е. шум c равномерно распределенными частотами по всему диапазону.
• 3-й - сумма первых двух.

Если бы мне дали значения последней функции на тот момент, когда я не знал про ряды Фурье, и попросили проанализировать их, то я бы точно растерялся и не смог бы сказать ничего путного. Ну, да, какая-то функция, но как понять, что там есть что-то упорядоченное? Но если бы я догадался прослушать последнюю функцию, то ухо уловило бы чистый тон среди шума. Хотя и не очень хорошо, так как я специально при генерации подобрал такие параметры, чтобы на суммарном графике сигнал визуально растворился в шуме. Как я понял, до сих пор точно не уставлено, как слуховой аппарат делает это. Однако, недавно стало ясно, что он не раскладывает звук на синусоиды. Возможно, когда-нибудь мы поймем как это происходит, и появятся более совершенные алгоритмы. Ну, а мы пока по старинке.
Почему бы не попробовать взять синусоиды в качестве базиса? На самом деле мы фактически уже сделали это. Вспомним наше разложение на 3 базисных вектора и представим их на графике:

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


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

Это все та же формула: A = EX с подставленным базисом. Базисные вектора указанного DCT (они же векторы-строки матрицы E) ортогональны, но не ортонормированы. Это следует помнить при обратном преобразовании (не буду останавливаться на этом, но, кому интересно - у inverse DCT появляется слагаемое 0.5*a 0 , так как нулевой вектор базиса больше остальных).
На следующем примере показан процесс приближения промежуточных сумм к исходным значениям. На каждой итерации очередной базис умножается на очередной коэффициент и прибавляется к промежуточной сумме (то есть так же, как и в ранних опытах над енотом - треть значений, две трети).

Но, все-таки, несмотря на некоторые доводы о целесообразности выбора такого базиса, реальных аргументов пока нет. Действительно, в отличие от звука, целесообразность разложения изображения на периодические функции гораздо менее очевидна. Впрочем, изображение действительно может быть слишком непредсказуемым даже на небольшом участке. Поэтому, картинку делят на достаточно маленькие кусочки, но не совсем крохотные, чтобы разложение имело смысл. В JPEG изображение «нарезается» на квадраты 8x8. В пределах такого кусочка фотографии обычно очень однородны: фон плюс небольшие колебания. Такие области шикарно приближаются синусоидами.
Ну, допустим, этот факт более или менее понятен интуитивно. Но появляется нехорошее предчувствие насчет резких цветовых переходов, ведь медленно изменяющиеся функции нас не спасут. Приходится добавлять разные высокочастотные функции, которые справляются со своей работой, но побочно проявляются на однородном фоне. Возьмем изображение 256x256 с двумя контрастными областями:

Разложим каждую строку с помощью DCT, получив, таким образом, по 256 коэффициентов на строку.
Затем оставим только первые n коэффициентов, а остальные приравняем нулю, и, поэтому, изображение будет представлено в виде суммы только первых гармоник:

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

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

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


При изучении DCT может сложиться ложное впечатление, что всегда вполне достаточно всего нескольких первых (низкочастотных) коэффициентов. Это верно для многих кусочков фотографий, тех, чьи значения не меняются резко. Однако, на границе контрастных участков значения будут резво «скакать» и даже последние коэффициенты будут велики. Поэтому, когда слышите о свойстве сохранения энергии DCT, делайте поправку на то, что оно относится ко многим видам встречаемых сигналов, но не ко всем. Для примера подумайте, как будет выглядеть дискретная функция, коэффициенты разложения которой равны нулю, кроме последнего. Подсказка: представьте разложение в векторном виде.
Несмотря на недостатки, выбранный базис является одним из лучших на реальных фотографиях. Чуть позже мы увидим небольшое сравнение с другими.

DCT vs все остальное

Когда я изучал вопрос ортогональных преобразований, то, честно говоря, меня не очень убеждали доводы о том, что все вокруг - это сумма гармонических колебаний, поэтому нужно и картинки раскладывать на синусоиды. А может быть лучше подойдут какие-нибудь ступенчатые функции? Поэтому искал результаты исследований об оптимальности DCT на реальных изображениях. То, что «Именно DCT чаще всего встречается в практических приложениях благодаря свойству «уплотнения энергии»» написано везде. Это свойство означает, что максимальное количество информации заключено в первых коэффициентах. А почему? Нетрудно провести исследование: вооружаемся кучей разных картинок, различными известными базисами и начинаем считать среднеквадратичное отклонение от реального изображения для разного количества коэффициентов. Нашел небольшое исследование в статье (использованные изображения ) по этой методике. В ней приведены графики зависимости сохраненной энергии от количества первых коэффициентов разложений по разным базисам. Если вы просмотрели графики, то убедились, что DCT стабильно занимает почетное… эмм… 3-место. Как же так? Что еще за KLT преобразование? Я восхвалял DCT, а тут…

KLT

Все преобразования, кроме KLT, являются преобразованиями с постоянным базисом. А в KLT (преобразование Карунена-Лоэва) вычисляется самый оптимальный базис для нескольких векторов. Он вычисляется таким образом, что первые коэффициенты дадут наименьшую среднеквадратичную погрешность суммарно для всех векторов. Похожую работу мы проводили ранее вручную, визуально определяя базис. Сначала кажется, что это здравая идея. Мы могли бы, например, разбивать изображение на небольшие секции и для каждой вычислять свой базис. Но мало того, что появляется забота хранения этого базиса, так еще и операция его вычисления достаточно трудоемкая. А DCT проигрывает лишь немного, и к тому же у DCT существуют алгоритмы быстрого преобразования.

DFT

DFT (Discrete Fourier Transform) - дискретное преобразование Фурье. Под этим названием иногда упоминается не только конкретная трансформация, но и весь класс дискретных трансформаций (DCT, DST...). Посмотрим на формулу DFT:

Как вы догадываетесь, это ортогональное преобразование с каким-то комплексным базисом. Так как подобная комплексная форма встречается чуть чаще, чем всегда, то имеет смысл изучить ее вывод.
Может сложится впечатление, что любой чистый гармонический сигнал (с целой частотой) при DCT разложении будет давать только один ненулевой коэффициент, соответствующий этой гармонике. Это не так, поскольку помимо частоты, важна и фаза этого сигнала. Например, разложение синуса по косинусам (подобным образом и в дискретном разложении) будет таким:

Вот вам и чистая гармоника. Она наплодила кучу других. На анимации показаны коэффициенты DCT синусоиды в разных фазах.


Если вам показалось, что столбики вращаются вокруг оси, то вам не показалось.
Значит теперь будем раскладывать функцию на сумму синусоид не просто разных частот, но еще и смещенных по какой-то фазе. Будет удобнее рассмотреть сдвиг фаз на примере косинуса:

Простое тригонометрическое тождество дает важный результат: сдвиг по фазе заменяется суммой синуса и косинуса, взятых с коэффициентами cos(b) и sin(b). Значит, можно раскладывать функции на сумму синусов и косинусов (без всяких фаз). Это распространенная тригонометрическая форма. Однако, гораздо чаще используется комплексная. Для ее получения нужно воспользоваться формулой Эйлера . Просто подставим производные формулы для синуса и косинуса, получим:


Теперь небольшая замена. Верхнее подчеркивание - сопряженное число.

Получим итоговое равенство:

c - комплексный коэффициент, действительная часть которого равна косинусному коэффициенту, а мнимая - синусному. А множество точек (cos(b), sin(b)) является окружностью. В такой записи каждая гармоника входит в разложение и с положительной и с отрицательной частотой. Поэтому в различных формулах Фурье-анализа обычно происходит суммирование или интегрирование от минус до плюс бесконечности. Производить вычисления часто бывает удобнее именно в такой комплексной форме.
Преобразование раскладывает сигнал на гармоники с частотами от одного до N колебаний на области сигнала. Но частота дискретизации составляет N на области сигнала. А по теореме Котельникова (aka теорема Найквиста - Шеннона) частота дискретизации должна по крайней мере в два раза превышать частоту сигнала. Если это не так, то получается эффект появления сигнала с ложной частотой:

Пунктирной линий показан неверно восстановленный сигнал. С таким явлением вы часто сталкивались в жизни. Например, забавное движение колес автомобиля на видео, или муаровый эффект.
Это приводит к тому, что вторая половина из N комплексных амплитуд как будто состоит из других частот. Эти ложные гармоники второй половины являются зеркальным отображением первой и не несут дополнительной информации. Таким образом, у нас остается N/2 косинусов и N/2 синусов (образующих ортогональный базис).
Ладно, базис есть. Его составляющие - гармоники с целым числом колебаний на области сигнала, а значит, крайние значения гармоник равны. Точнее почти равны, так как последнее значение берется не совсем с края. Более того - каждая гармоника почти зеркально симметрична относительно своего центра. Все эти явления особенно сильны на низких частотах, которые нам и важны при кодировании. Это плохо еще и тем, что на сжатом изображении будут заметны границы блоков. Проиллюстрирую DFT-базис с N=8. Первые 2 ряда - косинусные составляющие, последние - синусные:

Обратите внимание на появление дублей составляющих при повышении частоты.

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


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

DST

Что если вместо косинусов в DCT использовать синусы? Мы получим Discrete Sine Transform (DST). Но для нашей задачи все они неинтересны, так как и целые и половинки периодов синусов близки к нулю на границах. То есть мы получим примерно такое же неподходящее разложение, как и у DFT.

Возвращаясь к DCT

Как у него дела на границах? Хорошо. Есть противофазы и нет нулей.

Все остальное

Не-Фурье преобразования. Не буду описывать.
WHT - матрица состоит только из ступенчатых составляющих со значениями -1 и 1.
Haar - по совместительству ортогональное вейвлет-преобразование.
Они уступают DCT, но легче для вычислений.

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

1. Базис должен быть ортогонален.
2. С фиксированным базисом вы не сможете превзойти KLT по качеству сжатия. Между тем, на реальных фотографиях DCT почти не уступает.
3. На примере DFT и DST нужно помнить про границы.
4. И помнить, что у DCT есть еще хорошее преимущество - вблизи границ составляющих их производные равны нулю, а значит, переход между соседними блоками будет довольно плавным.
5. У преобразований Фурье существуют быстрые алгоритмы со сложностью O(N*logN), в отличие от вычисления в лоб: O(N 2).

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

Двумерные преобразования

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

Его 3D график:

Пройдемся DCT(N=32) по каждой строке:

Теперь я хочу, чтобы вы пробежались глазами по каждому столбцу полученных коэффициентов, т. е. сверху вниз. Вспомните, что наша цель - оставить как можно меньше значений, убрав малозначащие. Наверняка вы догадались, что значения каждого столбца полученных коэффициентов можно разложить точно так же, как и значения исходного изображения. Никто не ограничивает нас в выборе ортогональной матрицы преобразования, но мы сделаем это опять с помощью DCT(N=8):

Коэффициент (0,0) получился слишком большим, поэтому на графике он уменьшен в 4 раза.
Итак, что получилось?
Левый верхний угол - самые значащие коэффициенты разложения самых значащих коэффициентов.
Левый нижний угол - самые незначащие коэффициенты разложения самых значащих коэффициентов.
Правый верхний угол - самые значащие коэффициенты разложения самых незначащих коэффициентов.
Правый нижний угол - самые незначащие коэффициенты разложения самых незначащих коэффициентов.
Понятно, что значимость коэффициентов уменьшается, если двигаться по диагонали из левого верхнего угла в правый нижний. А какой важнее: (0, 7) или (7, 0)? Что они вообще означают?
Сначала по строкам: A 0 = (EX T) T = XE T (транспонировали, так как формула A=EX для столбцов), затем по столбцам: A=EA 0 = EXE T . Если аккуратно посчитать, то получится формула:

Таким образом, если вектор раскладывается на синусоиды, то матрица на функции вида cos(ax)*cos(by). Каждый блок 8x8 в JPEG представляется в виде суммы 64-х функций вида:


В Википедии и других источниках такие функции представлены в более удобной форме:

Поэтому коэффициенты (0, 7) или (7, 0) одинаково полезны.
Впрочем, фактически это обычное одномерное разложение на 64 64-мерных базиса. Все вышесказанное применимо не только к DCT, но и к любому ортогональному разложению. Действуя по аналогии, в общем случае получаем N-мерное ортогональное преобразование.
А вот уже 2-мерное преобразование енота (DCT 256x256). Опять же с обнуленными значениями. Числа - количество необнуленных коэффициентов из всех (оставлялись самые значимые значения, находящиеся в треугольной области в левом верхнем углу).

Запомните, что коэффициент (0, 0) называется DC, остальные 63 - AC.

Выбор размера блока

Товарищ спрашивает : почему в JPEG используется разбиение именно 8x8. Из заплюсованного ответа:

The DCT treats the block as if it were periodic and has to reconstruct the resulting jump at the boundaries. If you take 64x64 blocks, you"ll most likely have a huge jump at the boundaries, and you"ll need lots of high-frequency components to reconstruct that to a satisfactory precision

Мол, DCT работает хорошо только на периодических функциях, и если вы возьмете большой размер, то, скорее всего, получите гигантский скачок на границах блока и понадобится много высокочастотных компонентов для его покрытия. Это неверно! Такое объяснение очень похоже на DFT, но не на DCT, так как оно отлично покрывает такие скачки уже первыми составляющими.
На той же странице приводится ответ из MPEG FAQ, с основными аргументами против больших блоков:

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

Предлагаю самостоятельно исследовать это. Начнем с первого .


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

Большие блоки не показаны, так как визуально почти неотличимы от 32x32. Теперь посмотрим на абсолютную разность с исходным изображением (усиленную в 2 раза, иначе ничего толком не видно):

8x8 дает лучший результат, чем 4x4. Дальнейшее увеличение размера уже не дает хорошо заметного преимущества. Хотя я всерьез бы задумался над 16x16, вместо 8x8: увеличение сложности на 33% (о сложности в следующем абзаце), дает небольшое, но все-таки видимое улучшение при одинаковом количестве коэффициентов. Однако, выбор 8x8 выглядит достаточно обоснованным и, возможно, является золотой серединой. JPEG был опубликован в 1991. Думаю, что такое сжатие являлось очень сложным для процессоров того времени.

Второй аргумент. Нужно помнить, что при увеличении размера блока потребуется больше вычислений. Давайте оценим насколько. Сложность преобразования в лоб, как мы уже вполне умеем: O(N 2), так как каждый коэффициент состоит из N слагаемых. Но на практике используется эффективный алгоритм быстрого преобразования Фурье (БПФ, Fast Fourier Transform, FFT). Его описание выходит за рамки статьи. Его сложность: O(N*logN). Для двумерного разложения нужно воспользоваться им дважды по N раз. Таким образом, сложность 2D DCT - O(N 2 logN). Теперь сравним сложности вычисления изображения одним блоком и несколькими маленькими:

• Одним блоком (kN)x(kN): O((kN) 2 log(kN)) = O(k 2 N 2 log(kN))
• k*k блоками N*N: O(k 2 N 2 logN)

Это значит, что, например, вычисление при разбиении на 64x64 в два раза сложнее, чем на 8x8.

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


Хотя искажения блоков 16x16 простираются дальше, чем у 8x8, но надпись более плавная. Поэтому меня убедили только первые два аргумента. Но мне что-то больше нравится разделение на 16x16.

Квантование

На данном этапе мы имеем кучу матриц 8x8 с коэффициентами косинусного преобразования. Пришло время избавляться от малозначащих коэффициентов. Существует более элегантное решение, чем просто обнулять последние коэффициенты, как мы делали выше. Нас не устраивает этот способ, так как необнуленные значения хранятся с избыточной точностью, а среди тех, кому не повезло, могли оказаться достаточно важные. Выход - нужно использовать матрицу квантования. Потери происходят именно на это этапе. Каждый Фурье-коэффициент делится на соответствующее число в матрице квантования. Рассмотрим на примере. Возьмем первый блок от нашего енота и произведем квантование. В спецификации JPEG приводится стандартная матрица:


Стандартная матрица соответствует 50% качеству в FastStone и IrfanView. Такая таблица была выбрана с точки зрения баланса качества и степени сжатия. Думаю, что значение для DC-коэффициента больше соседних из-за того, что DCT ненормализовано и первое значение получается больше, чем следовало бы. Высокочастотные коэффициенты огрубляются сильнее из-за их меньшей важности. Думаю, сейчас такие матрицы используются редко, так как ухудшение качества хорошо заметно. Никто не запрещает использовать свою таблицу (со значениями от 1 до 255)
При декодировании происходит обратный процесс - квантованные коэффициенты почленно умножаются на значения матрицы квантования. Но так как мы округляли значения, то не сможем точно восстановить исходные коэффициенты Фурье. Чем больше число квантования, тем больше погрешность. Таким образом, восстановленный коэффициент является лишь ближайшим кратным.
Еще пример:

И на десерт, рассмотрим качество 5% (при кодировании в Fast Stone).


При восстановлении этого блока мы получим только усредненное значение плюс вертикальный градиент (из-за сохранившегося значения -1). Зато для него хранится всего два значения: 7 и -1. C другими блоками ситуация не лучше, вот восстановленная картинка:

Кстати, насчет 100% качества. Как вы догадываетесь, в этом случае матрица квантования состоит полностью из единиц, то есть квантования не происходит. Однако, из-за округления коэффициентов до целого, мы не можем в точности восстановить исходную картинку. Например, енот сохранил 96% пикселей точно, а 4% отличались на 1/256. Разумеется, такие «искажения» невозможно заметить визуально.
А можете посмотреть матрицы квантования различных фотоаппаратов.

Кодирование

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

Пример 0 (для разминки)
Представьте такую ситуацию, что ваш знакомый забыл у вас дома листочек со списком и теперь просит продиктовать его по телефону (других способов связи нет).
Список:

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

Как бы вы облегчили свою задачу? Особого желания мучительно диктовать все эти слова у вас нет. Но их всего два и они повторяются. Поэтому вы просто как-нибудь диктуете первые два слова и договариваетесь, что далее «d9rg3» будете называть первым словом, а «wfr43gt» - вторым. Тогда достаточно будет продиктовать: 1, 2, 2, 1, 1, 1, 2, 1.

Подобные слова мы будем обозначать как A, B, C..., и называть их символами. Причем под символом может скрываться что угодно: буква алфавита, слово или бегемот в зоопарке. Главное, что одинаковым символам соответствуют одинаковые понятия, а разным - разные. Так как наша задача - эффективное кодирование (сжатие), то будем работать с битами, так как это наименьшие единицы представления информации. Поэтому, запишем список как ABBAAABA. Вместо «первое слово» и «второе слово» можно использовать биты 0 и 1. Тогда ABBAAABA закодируется как 01100010 (8 бит = 1 байт).

Пример 1
Закодировать ABC.
3-м разным символам (A, B, C) никак нельзя сопоставить 2 возможных значений бита (0 и 1). А раз так, то можно использовать по 2 бита на символ. Например:

• A: 00
• B: 01
• C: 10

Последовательность битов, сопоставленная символу, будем называть кодом. ABC будет кодироваться так: 000110.

Пример 2
Закодировать AAAAAABC.
Использовать по 2 бита на символ A кажется немного расточительным. Что, если попробовать так:

• C: 00

Закодированная последовательность: 000000100.
Очевидно, этот вариант не подходит, так как непонятно, как декодировать первые два бита этой последовательности: как AA или как C? Использовать какой-нибудь разделитель между кодами очень расточительно, будем думать как по-другому обойти это препятствие. Итак, неудача произошла из-за того, что код C начинается с кода A. Но мы полны решимости кодировать A одним битом, пусть даже B и С будут по два. Исходя из такого пожелания, A дадим код 0. Тогда коды B и C не могут начинаться на 0. Но могут на 1:

• B: 10
• C: 11

Последовательность закодируется так: 0000001011. Попробуйте мысленно декодировать ее. Вы сможете сделать это только одним способом.
Мы выработали два требования к кодированию:

1. Чем больше вес символа, тем короче должен быть его код. И наоборот.
2. Для однозначного декодирования код символа не может начинаться с кода любого другого символа.

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

Пример 3
Рассмотрим общий случай для 4-х символов с любыми весами.

• A: pa
• B: pb
• C: pc
• D: pd

Без потери общности, положим pa ≥ pb ≥ pc ≥ pd. Существуют всего два принципиально разных по длинам кодов варианта:


Какое из них предпочтительнее? Для этого нужно вычислить получаемые длины закодированных сообщений:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2*pb + 3*pc + 3*pd
Если W1 меньше W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd) < 0 => pa < pc+pd.
Если C и D вместе встречаются чаще других, то их общая вершина получает самый короткий код из одного бита. В противном случае, один бит достается символу A. Значит, объединение символов ведет себя как самостоятельный символ и имеет вес равный сумме входящих символов.
Вообще, если p - вес символа представленный долей его вхождения (от 0 до 1), то лучшая длина кода s=-log 2 p.
Рассмотрим это на простом случае (его легко представить в виде дерева). Итак, нужно закодировать 2 s символов с равными весами (1/2 s). Из-за равенства весов длины кодов будут одинаковыми. Каждому символу потребуется s бит. Значит, если вес символа 1/2 s , то его длина s. Если вес заменить заменить на p, то получим длину кода s=-log 2 p . Значит, если один символ встречается в два раза реже другого, то длина его кода будет на бит длиннее. Впрочем такой вывод легко сделать, если вспомнить, что добавление одного бита позволяет в два раза увеличить количество возможных вариантов.
И еще одно наблюдение - два символа с наименьшими весами всегда имеют наибольшие, но равные длины кодов. Более того, их биты, кроме последнего, совпадают. Если бы это было неверно, то, по крайней мере, один код можно было бы укоротить на 1 бит, не нарушая префиксности. Значит, два символа с наименьшими весами в кодовом дереве имеют общего родителя уровнем выше. Вы можете видеть это на примере С и D выше.

Пример 4
Попробуем решить следующий пример, по выводам, полученным в предыдущем примере.

1. Все символы сортируются в порядке убывания весов.
2. Два последних символа объединяются в группу. Этой группе присваивается вес, равный сумме весов этих элементов. Эта группа участвует в алгоритме наравне с символами и другими группами.

Шаги повторяются, пока не останется только одна группа. В каждой группе одному символу (или подгруппе) присваивается бит 0, а другому бит 1.
Этот алгоритм называется кодированием Хаффмана.
На иллюстрации приведен пример с 5-ю символами (A: 8, B: 6, C: 5, D: 4, E: 3). Справа указан вес символа (или группы).

Кодируем коэффициенты

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

Обратите внимание - шкала логарифмическая! Сможете объяснить причину появления скопления значений превышающих 200? Это DC-коэффициенты. Так как они сильно отличаются от остальных, то неудивительно, что их кодируют отдельно. Вот только DC:

Обратите внимание, что форма графика напоминает форму графиков из самих ранних экспериментов деления на пары и тройки пикселей
Вообще, значения DC-коэффициентов могут меняться от 0 до 2047 (точнее от -1024 до 1023, так как в JPEG производится вычитание 128 из всех исходных значений, что соответствует вычитанию 1024 из DC) и распределяться довольно равномерно с небольшими пиками. Поэтому кодирование Хаффмана здесь не очень-то поможет. А еще представьте, каким большим будет дерево кодирования! И во время декодирования придется искать в нем значения. Это очень затратно. Думаем дальше.
DC-коэффициент - усредненное значение блока 8x8. Представим градиентный переход (пусть не идеальный), который часто встречается в фотографиях. Сами DC значения будут разными, но они будут представлять арифметическую прогрессию. Значит, их разность будет более-менее постоянна. Построим гистограмму разностей:

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

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

Значений с длинами 4 и 6 больше всего, поэтому им достались самые короткие коды (00 и 01).

Может возникнуть вопрос: почему на примере у значения 9 код 1111110, а не 1111111? Ведь можно смело поднять «9» на уровень выше, рядом с «0»? Дело в том, что в JPEG нельзя использовать код, состоящий только из единиц - такой код зарезервирован.
Есть еще одна особенность. Коды, полученные описанным алгоритмом Хаффмана могут не совпасть по битам с кодами в JPEG, хотя их длины будут одинаковыми. Используя алгоритм Хаффмана, получают длины кодов, а сами коды генерируются (алгоритм прост - начинают с коротких кодов и добавляют их по очереди в дерево как можно левее, сохраняя свойство префиксности). Например, для дерева выше хранится список: 0,2,3,1,1,1,1,1. И, разумеется, хранится список значений: 4,6,3,5,7,2,8,1,0,9. При декодировании коды генерируются таким же способом.

Теперь порядок. Мы разобрались как хранятся DC:
[код Хаффмана для длины DC diff (в битах)]
где DC diff = DC текущее - DC предыдущее

Смотрим AC:

Так как график очень похож на график для разностей DC, то принцип тот же: [код Хаффмана для длины AC (в битах)]. Но не совсем! Так как на графике шкала логарифмическая, то не сразу заметно, что нулевых значений примерно в 10 раз больше, чем значения 2 - следующего по частоте. Это понятно - не все пережили квантование. Вернемся к матрице значений, полученной на этапе квантования (используя матрицу квантования FastStone, 90%).

Так как встречается много групп подряд идущих нулей, то появляется идея - записывать только количество нулей в группе. Такой алгоритм сжатия называется RLE (Run-length encoding, кодирование повторами). Осталось выяснить направление обхода «подряд идущих» - кто за кем? Выписать слева направо и сверху вниз - не очень эффективно, так как ненулевые коэффициенты концентрируются около левого верхнего угла, а чем ближе к правому нижнему - тем больше нулей.

Поэтому, в JPEG используется порядок, называемый «Zig-zag», он показан на левом рисунке. Такой способ хорошо выделяет группы нулей. На правом рисунке - альтернативный способ обхода, не относящийся к JPEG, зато с любопытным названием (пруф). Он может использоваться в MPEG при сжатии видео с чересстрочной разверткой. Выбор алгоритма обхода не влияет на качество изображения, но может увеличить количество кодируемых групп нулей, что в итоге может отразиться на размере файла.
Модифицируем нашу запись. Для каждого ненулевого AC - коэффициента:
[Количество нулей перед AC][код Хаффмана для длины AC (в битах)]
Думаю, что вы сразу скажете - количество нулей тоже отлично закодируется Хаффманом! Это очень близкий и неплохой ответ. Но можно немного оптимизировать. Представьте, что имеем некоторый коэффициент AC, перед которым было 7 нулей (разумеется, если выписывать в зигзагообразном порядке). Эти нули - дух значений, которые не выдержали квантования. Скорее всего, наш коэффициент тоже сильно потрепало и он стал маленьким, а, значит, его длина - короткой. Значит, количество нулей перед AC и длина AC - зависимые величины. Поэтому записывают так:
[код Хаффмана для (Количество нулей перед AC, длина AC (в битах)]
Алгоритм кодирования остается тем же: те пары (количество нулей перед AC, длина AC), которые встречаются часто, получат короткие коды и наоборот.

Строим гистограмму зависимости количества по этим парам и дерево Хаффмана.


Длинный «горный хребет» подтверждает наше предположение.

Особенности реализации в JPEG:
Такая пара занимает 1 байт: 4 бита на количество нулей и 4 бита на длину AC. 4 бита - это значения от 0 до 15. Для длины AC хватит с избытком, но ведь нулей может быть больше 15? Тогда используется больше пар. Например, для 20 нулей: (15, 0)(5, AC). То есть, 16-й ноль кодируется как ненулевой коэффициент. Так как ближе к концу блока всегда полно нулей, то после последнего ненулевого коэффициента используется пара (0,0). Если она встретится при декодировании, значит оставшиеся значения равны 0.

Выяснили, что каждый блок закодирован хранится в файле так:
[код Хаффмана для длины DC diff ]
[код Хаффмана для (количество нулей перед AC 1 , длина AC 1 ]
…
[код Хаффмана для (количество нулей перед AC n , длина AC n ]
Где AC i - ненулевые AC коэффициенты.

Цветное изображение

Способ представления цветного изображения зависит от выбранной цветовой модели. Простое решение - использовать RGB и кодировать каждый цветовой канал изображения по отдельности. Тогда кодирование не будет отличаться от кодирования серого изображения, только работы в 3 раза больше. Но сжатие изображения можно увеличить, если вспомнить, что глаз более чувствительнее к изменению яркости, чем цвета. Это значит, что цвет можно хранить с бОльшими потерями, чем яркость. У RGB нет отдельного канала яркости. Она зависит от суммы значений каждого канала. Поэтому, RGB-куб (это представление всех возможных значений) просто «ставят» на диагональ - чем выше, тем ярче. Но на этом не ограничиваются - куб немного поджимают с боков, и получается скорее параллелепипед, но это лишь для учета особенностей глаза. Например, он более восприимчив к зеленому, чем синему. Так появилась модель YCbCr.

(Изображение с Intel.com)
Y - компонента яркости, Cb и Cr являются синей и красной цветоразностными компонентами. Поэтому, если хотят сильнее сжать изображение, то RGB переводят в YCbCr, и каналы Cb и Cr прореживают. То есть разбивают на небольшие блоки, например 2x2, 4x2, 1x2, и усредняют все значения одного блока. Или, другими словами, уменьшают размер изображения для этого канала в 2 или 4 раза по вертикали и/или горизонтали.

Каждый блок 8x8 кодируется (DCT + Хаффман), и закодированные последовательности записываются в таком порядке:

Любопытно, что спецификация JPEG не ограничивает в выборе модели, то есть реализация кодировщика может как угодно разделить изображение по цветовым компонентам (каналам) и каждый будет сохранен по отдельности. Мне известно об использовании Grayscale (1 канал), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Первые три поддерживаются почти всеми, а вот с последними 4-канальными бывают проблемы. FastStone, GIMP поддерживают их корректно, а штатные программы Windows, paint.net корректно извлекают всю информацию, но потом выбрасывают 4 черный канал, поэтому (Antelle сказал, что не выбрасывают, читайте его комментарии) показывают более светлое изображение. Слева - классический YCbCr JPEG, справа CMYK JPEG:



Если они различаются по цветам, или видна только одна картинка, то, скорее всего, у вас IE (любой версии) (UPD. в комментариях говорят «или Safari»). Можете попробовать открыть статью в разных браузерах.

И еще кое-что

В двух словах о дополнительных возможностях.

Progressive mode

Разложим полученные таблицы коэффициентов DCT на сумму таблиц (примерно так (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). Сначала закодируем все первые слагаемые (как мы уже научились: Хаффман и обход зигзагом), затем вторые и т. д. Такой трюк полезен при медленном интернете, так как сперва загружаются только DC коэффициенты, по которым строится грубая картинка c «пикселями» 8x8. Затем округленные AC коэффициенты, позволяющие уточнить рисунок. Затем грубые поправки к ним, затем более точные. Ну и так далее. Коэффициенты округляются, так как на ранних этапах загрузки точность не столь важна, зато округление положительно сказывается на длине кодов, так как для каждого этапа используется своя таблица Хаффмана.

Lossless mode

Сжатие без потерь. DCT нет. Используется предсказание 4-й точки по трем соседним. Ошибки предсказания кодируются Хаффманом. По-моему, используется чуть чаще, чем никогда.

Hierarhical mode

По изображению создается несколько слоев с разными разрешениями. Первый грубый слой кодируется как обычно, а затем только разница (уточнение изображения) между слоями (прикидывается вейвлетом Хаара). Для кодирования используется DCT или Lossless. По-моему, используется чуть реже, чем никогда.

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

Алгоритм Хаффмана создает оптимальные коды по весу символов, но это верно только для фиксированного соответствия символов с кодами. Арифметическое не имеет такой жесткой привязки, что позволяет использовать коды как бы с дробным числом бит. Утверждается, что оно уменьшает размер файла в среднем на 10% по сравнению с Хаффманом. Не распространено из-за проблем с патентом, поддерживается не всеми.

Я надеюсь, что теперь вам понятен алгоритм JPEG интуитивно. Спасибо за прочтение!

UPD
vanwin предложил указать использованное ПО. С удовольствием сообщаю, что все доступны и бесплатны:

• Python + NumPy + Matplotlib + PIL(Pillow) . Основной инструмент. Нашелся по выдаче «Matlab free alternative». Рекомендую! Даже если вам не знаком Python, то уже через пару часов научитесь производить расчеты и строить красивые графики.
• JpegSnoop . Показывает подробную информацию о jpeg-файле.
• yEd . Редактор графов.
• Inkscape . Делал в нем иллюстрации, такие как пример алгоритма Хаффмана. Прочитал несколько уроков, оказалось очень здорово.
• Daum Equation Editor . Искал визуальный редактор формул, так как с Latex-ом не очень дружу. Daum Equation - плагин к Хрому, мне показался очень удобен. Помимо мышкотыкания, можно редактировать Latex.
• FastStone . Думаю, его представлять не надо.
• PicPick . Бесплатная альтернатива SnagIt. Сидит в трее, скриншотит что скажут куда скажут. Плюс всякие плюшки, типа линейки, пипетки, угломера и пр.

Теги: Добавить метки

Алгоритм преобразования графического изображения JPEG состоит из нескольких этапов, выполняемых над изображением последовательно, один за другим:

– преобразования цветового пространства,

– субдискретизации,

– дискретного косинусного преобразования (ДКП),

– квантования,

– кодирования.

На этапе преобразования цветового пространства осуществляется преобразование изображения из цветового пространства RGB в YCbCr (где Y - яркость, а Cb и Cr - цветоразностные компоненты точки изображения):

Применение пространства YCbCr вместо привычного RGB объясняется физиологическими особенностями человеческого зрения, а именно тем, что нервная система человека обладает значительно большей чувствительностью к яркости (Y ) , чем к цветоразностным составляющим (в данном случае Cb и Cr ). Обратное преобразование цветового пространства (из YCrCb в RGB ) имеет вид:

Алгоритм сжатия JPEG позволяет сжимать изображения с различными размерами цветовых плоскостей. Обозначим через x i и y i ширину и высоту i -й цветовой плоскости изображения. Пусть X = max (x i ), Y = max (y i ), определим для каждой плоскости коэффициенты H i = X / x i и V i = Y / y i . Наибольшее значение для X и Y согласно алгоритму JPEGравно 2 16 , а для H i и V i – 2 2 . Таким образом, ширина и высота цветовых плоскостей может быть от 1 до 4 раз меньше, размеров наибольшей плоскости. Для обычных RGB изображений размеры всех цветовых плоскостей равны.

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

Рисунок 1 – Распространенные типы субдискретизации

Затем, отдельно для каждого компонента цветового пространства Y , Cb и Cr , осуществляется прямое дискретное косинусное преобразование. Для этого изображение делится на блоки с размером 8 на 8 точек и каждый блок преобразуется согласно формуле:

Применение дискретного косинусного преобразования позволяет перейти от пространственного представления изображения к спектральному. Обратное дискретное косинусное преобразование имеет вид:

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

.

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

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

Блок до квантования:

3862, –22, –162, –111, –414, 12, 717, 490,

383, 902, 913, 234, –555, 18, –189, 236,

229, 707, –708, 775, 423, –411, –66, –685,

231, 34, –928, 34, –1221, 647, 98, –824,

–394, 128, –307, 757, 10, –21, 431, 427,

324, –874, –367, –103, –308, 74, –1017, 1502,

208, –90, 114, –363, 478, 330, 52, 558,

577, 1094, 62, 19, –810, –157, –979, –98

Таблица квантования (качество 90):

24, 16, 16, 24, 40, 64, 80, 96,

16, 16, 24, 32, 40, 96, 96, 88,

24, 24, 24, 40, 64, 88, 112, 88,

24, 24, 32, 48, 80, 136, 128, 96,

32, 32, 56, 88, 112, 176, 168, 120,

40, 56, 88, 104, 128, 168, 184, 144,

80, 104, 128, 136, 168, 192, 192, 160,

112, 144, 152, 160, 176, 160, 168, 160

Блок после квантования:

161, –1, –10, –5, –10, 0, 9, 5,

24, 56, 38, 7, –14, 0, –2, 3,

10, 29, –30, 19, 7, –5, –1, –8,

10, 1, –29, 1, –15, 5, 1, –9,

–12, 4, –5, 9, 0, 0, 3, 4,

8, –16, –4, –1, –2, 0, –6, 10,

3, –1, 1, –3, 3, 2, 0, 3,

5, 8, 0, 0, –5, –1, –6, –1

3864, –16, –160, –120, –400, 0, 720, 480,

384, 896, 912, 224, –560, 0, –192, 264,

240, 696, –720, 760, 448, –440, –112, –704,

240, 24, –928, 48,–1200, 680, 128, –864,

–384, 128, –280, 792, 0, 0, 504, 480,

320, –896, –352, –104, –256, 0,–1104, 1440,

240, –104, 128, –408, 504, 384, 0, 480,

560, 1152, 0, 0, –880, –160,–1008, –160

Таблица квантования (качество 45):

144, 96, 88, 144, 216, 352, 456, 544,

104, 104, 128, 168, 232, 512, 536, 488,

128, 112, 144, 216, 352, 504, 616, 496,

128, 152, 192, 256, 456, 776, 712, 552,

160, 192, 328, 496, 600, 968, 912, 680,

216, 312, 488, 568, 720, 920, 1000, 816,

432, 568, 696, 776, 912, 1072, 1064, 896,

640, 816, 840, 872, 992, 888, 912, 880

Блок после квантования:

27, 0, –2, –1, –2, 0, 2, 1,

4, 9, 7, 1, –2, 0, 0, 0,

2, 6, –5, 4, 1, –1, 0, –1,

2, 0, –5, 0, –3, 1, 0, –1,

–2, 1, –1, 2, 0, 0, 0, 1,

2, –3, –1, 0, 0, 0, –1, 2,

0, 0, 0, 0, 1, 0, 0, 1,

1, 1, 0, 0, –1, 0, –1, 0

Блок после обратного преобразования:

3888, 0, –176, –144, –432, 0, 912, 544,

416, 936, 896, 168, –464, 0, 0, 0,

256, 672, –720, 864, 352, –504, 0, –496,

256, 0, –960, 0,–1368, 776, 0, –552,

–320, 192, –328, 992, 0, 0, 0, 680,

432, –936, –488, 0, 0, 0,–1000, 1632,

0, 0, 0, 0, 912, 0, 0, 896,

640, 816, 0, 0, –992, 0, –912, 0

Как видно, в первом случае изменение DC коэффициента в результате сжатия равно 2, а во втором 26, при этом квантованный DC коэффициент во втором случае в 6 раз меньше чем в первом.

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

0, 1, 5, 6, 14, 15, 27, 28,

2, 4, 7, 13, 16, 26, 29, 42,

3, 8, 12, 17, 25, 30, 41, 43,

9, 11, 18, 24, 31, 40, 44, 53,

10, 19, 23, 32, 39, 45, 52, 54,

20, 22, 33, 38, 46, 51, 55, 60,

21, 34, 37, 47, 50, 56, 59, 61,

35, 36, 48, 49, 57, 58, 62, 63

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

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

Алгоритм JPEG разработан специально для сжатия изображений группой экспертов в области фотографии JPEG (Joint Photographic Expert Group) и разработан на основе ДКП.

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

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

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

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

Q(i,j) = 1 + ((1 + i + j) q);

Где Q(i,j) – матрица делителей,

q - параметр качества.

Путем выбора параметра q можно управлять величинами делителей и регулировать степень сжатия. Например, при q = 2 получится матрица следующего вида (Рис.3.6):

Риунок 3.6. Пример матрицы квантования.

После деления 64 элементов матрицы на элементы матрицы Q(i,j) в качестве результата матрицу, у которой:

Появится большое количество дополнительных нулевых значений,

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

Для экономичной записи требуется изменить порядок обхода полученных значений таким образом, чтобы последовательности нулевых элементов были бы как можно длиннее. Одним из возможных способов изменения порядка обхода является способ зиг-заг (рис3.7).

Рисунок 3.7. Преобразования двумерной матрицы в одномерную последовательность по способу «зигзаг».

Как видно из рисунка, двумерная матрица форматом 8 х 8 элементов преобразуется в одномерную последовательность длиной 64 элемента. Главным свойством такой последовательности будет расположение наиболее значимых коэффициентов в ее начале, а наименее значимых элементов (обычно нулей) в ее конце.

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

Рисунок 3.8. Последовательность операций при реализации алгоритма JPEG.

1. Изображение при необходимости переводится в формат YUV.

2. Производится дискретизация цветоразностных U и V сигналов в соответствии с форматом 4:2:0. Разбиение изображения на фрагменты размером 8 х 8 элементов. Далее обработка сигналов яркости и цветности может производиться независимо и параллельно.

3. Дискретное косинусное преобразование выполняется применительно ко всем блокам размером 8 х 8 элементов.

4. Квантование в соответствии с выбранным параметром качества.

5. Сканирование «зигзаг» для получения одномерной последовательности из 64 элементов.

6. Алгоритм RLE применяется к одномерной последовательности.

7. Алгоритм Хаффмана применяется к уже сжатой с помощью RLE последовательности.

8. П.п. 3 – 7 выполняются для всех блоков форматом 8 х 8 элементов и для всех цветовых плоскостей.

Основные особенности метода JPEG состоят в следующем:

1. Высокий коэффициент сжатия, особенно для изображений, качество которых расценивается как хорошее или отличное.

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

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

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

5. Возможность использования сжатия без потерь информации при не очень высоком коэффициенте сжатия.

JPEG - одни из самых новых и достаточно мощных алгоритмов. Практически, он является стандартом “де-факто” для полноцветных изображений. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам (формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPFG осуществляется за счет плавности изменения цветов в изображении.

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений JPEG - Joint Photographic Expert Group - подразделение в рамках ISO - Международной организации по стандартизации. В целом алгоритм основан на дискретном коcинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование

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

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

Работа алгоритма.

Пусть сжимается 24-битное изображение.

Шаг I.

Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).

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

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить так:

Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу:

Шаг 2.

Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП - по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y - как и в первом случае, а для компонент Сr и Сb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При том, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в два раза. Мы можем поступать так, благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается не сильно.

Шаг 3.

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

В упрощенном виде то преобразование можно представить так:

Шаг 4.

Проводим квантование. В принципе это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования (далее МК).

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

С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma , - потери в нижних частотах могут быть настолько велики, что изображение распадется на квадраты 8x8. Потери в высоких частотах могут проявиться в так называемом "эффекте Гиббса”, когда вокруг контуров с резким переходом цвета образуется своеобразный "нимб"

Шаг 5.

Переводим матрицу 8x8 в 64-элементный вектор при помощи зигзагообразного сканирования, т.е. выбираем элементы с индексами (0.0). (0.1). (1.0). (2.0)...

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце - высоким.

Шаг 6.

Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” - счетчик пропускаемых нулей, а "число" - значение, которое необходимо поставить в следующую ячейку.

Так, вектор будет свернут в пары (0, 42) (0, 3) (3, -2) (4, 1)

Шаг 7.

Свертываем поучившиеся пары кодированием по Хаффману с фиксированной таблицей.

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

Конвейер операций, используемый в алгоритме JPEG.

Существенными положительными сторонами алгоритма является то, что:

• 1) Задается степень сжатия
• 2) Выходное цветное изображение может иметь 24 бита на точку.

Отрицательными сторонами алгоритма является то, что:

• 1) При повышении степени сжатия изображение распадается на отдельные квадраты (8х8). Это связано с тем, что происходят большие потери в низких частотах при квантовании и восстановить исходные данные становится невозможно.
• 2) Проявляется эффект Гиббса - ореолы по границам резких переходов цветов.

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

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

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

Широкое применение JPEG долгое время сдерживалось, пожалуй, лишь тем, что он оперирует 24-битными изображениями. Поэтому для того, чтобы с приемлемым качеством посмотреть картинку на обычном мониторе в 256-цветной палитре, требовалось применение соответствующих алгоритмов и, следовательно, определенное время. В приложениях, ориентированных на придирчивого пользователя, таких, например, как игры, подобные задержки неприемлемы. Кроме того, если имеющиеся у вас изображения, допустим, в 8-битном формате GIF перевести в 24-битный JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях. Тем не менее, выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз!), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным.

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

Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и, на данный момент, занимает видное место в системах мультимедиа.

Характеристики алгоритма JPFG:

Коэффициенты компрессии: 2-200 (Задаётся пользователем).

Класс изображений: Полноцветные 24-битные изображения, или изображения в градациях серого без резких переходов цветов (фотографии).

Симметричность: 1.

Характерные особенности: В некоторых случаях, алгоритм создает "ореол" вокруг pезкиx горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселей.

• 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

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

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

0

Нахождение 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]

1. О, пойду-ка поем!
2. Да я вообще не въезжаю, о чем речь.
3. Раз значение цветов YCbCr получены, осталось преобразовать в RGB, типа так: YCbCrToRGB(Y ij , Cb ij , Cr ij) , Y ij , Cb ij , Cr ij - наши полученные матрицы.
4. 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, поэтому вряд ли смогу ответить на все вопросы. Просто когда я писал свой декодер, мне часто приходилось сталкиваться с различными непонятными проблемами. И когда изображение выводилось некорректно, я не знал где допустил ошибку. Может неправильно проинтерпретировал биты, а может неправильно использовал ДКП. Очень не хватало пошагового примера, поэтому, надеюсь, эта статья поможет при написании декодера. Думаю, она покрывает описание базового метода, но все-равно нельзя обойтись только ей. Предлагаю вам ссылки, которые помогли мне: