Кодирование jpeg
Введение
Для работой с jpeg файлами написано множество библиотек. Даже Java по умолчанию поддерживает чтение и запись jpeg файлов. Однако, когда требуется декодировать более сложные типы передачи jpeg, то необходимо понимать как устроен формат и какие алгоритмы используются. В этой статье я постараюсь максимально дотошно разобрать кодирование jpeg.
Типы передачи jpeg
Прежде, чем разбирать кодирование цвета в jpeg, необходимо чётко разделять две вещи: кодирование цвета и передача блоков изображения.
Кодирование цвета - это набор алгоритмов для формирования, так называемых MCU, блоков пикселей 8х8 или 16х16. Именно эти алгоритмы отвечают за сжатие изображения.
Передача или хранение блоков изображения бывает нескольких видов. Файл - наиболее распространённый способ. Вначале файла идёт описание таблиц квантования и всевозможная мета-информация о картинке. После этого идёт список MCU блоков jpeg.
Несмотря на то, что файл используется в 99.999% процентов случаев, существуют и другие способы передачи jpeg картинки. В основном они решают ту или иную проблему, которую нельзя решить с использованием стандартных файлов. Continuous jpeg - способ передачи “бесконечного” jpeg файла. Используется в метеорологических спутниках для передачи полос сканирования Земли. Так как спутник летает вокруг Земли и постоянно шлёт информацию, то и картинка получается как бы “бесконечной” высоты.
SSDV - способ передачи jpeg файла, при котором часть пакетов может потеряться. Используется в спутниках с более узким каналом передачи данных.
Ниже я постараюсь описать только алгоритмы кодирования цвета в jpeg.
Кодирование jpeg
Шаг 1. Преобразование в YCbCr
Изначальный RGB цвет преобразуется в YCbCr с помощью формулы:
Y = 0.299 * R + 0.587 * G + 0.114 * B
Cb = -0.1687 * R - 0.3313 * G + 0.5 * B + 128
Cr = 0.5 * R - 0.4187 * G - 0.0813 * B + 128
Зачем это сделано? Тут важно понять, что всё сжатие jpeg основано на восприятии цвета человеком. Задача алгоритма так уменьшить размер картинки, чтобы человек не заметил большой разницы. Тут важно “не заметил”. Некоторые люди вполне могут заметить, некоторые нет. Алгоритм не делает между ними различия, а работает с усредненным значением “не заметил”. Это значение получено эмпирически путём опроса множества людей.
В данном случае важно знать, что человеческий глаз более чувствителен к зелёному цвету. Так же человеческий глаз более чувствителен к контрасту, чем к оттенкам цветов. Это прежде всего связано с тем, что роговица позволяет различать предметы в темноте.
Зная это, можно преобразовать “компьютерный” формат RGB в более человеческий YCbCr. Уменьшая качество CbCr можно, не теряя в качестве восприятия, сильно уменьшить количество информации. На этом основан следующий шаг.
Шаг 2. Сэмплирование
Компоненты Cb и Cr можно сэмплировать со значительным интервалом, тем самым уменьшая размер изображения. Этот приём называется цветовая субдискретизация (chroma subsampling). Он заключается в том, что для каждого блока Y, блоки Cb и Cr берутся с некоторым интервалом.
Например, на картинке выше, цветовая субдискретизация 4:2:0. Это значит, что для блока пикселей 2х2 Y компоненты, пикселы Cb и Cr усредняются и берутся только один раз. Jpeg поддерживает различные варианты субдискретизации: 4:1:1, 4:2:0.
В данном случае удалось уменьшить с 12 байт ( 3 * 4 * 1 байт ) до 6 байт (4 байт + байт + байт). То есть уменьшить размер в 2 раза!
Шаг 3.
Самый простой шаг - перевод цвета из интервала 0 ~ 255 в знаковый -128 ~ 127.
Шаг 4. Дискретное косинусное преобразование
Следующие шаги позволяют уменьшить размер за счёт отфильтровывания высокочастотных деталей изображения. Этот процесс лучше понять на примере. Но для начала необходимо разбить пикселы изображения на блоки 8х8 пикселей. Немного терминологии jpeg. DU (data unit) - это блок пикселей 8х8 одного компонента. MCU (minimum coding unit) - это несколько или один DU, которые все вместе дают кусочек картинки 8х8 или 16х16 пикселей. Для примера выше, MCU выглядит следующим образом:
MCU состоит из 6 блоков DU. Каждый блок DU состоит из 8х8 пикселей.
После того как картинка разбита на блоки DU, идёт кодирование каждого блока. Дискретное косинусное преобразование применяется для каждого по очереди. Эта операция преобразует матрицу чисел 8х8 в их частотное представление. Это очень похоже на дискретное преобразование фурье. У получившейся матрицы 8х8 есть одна особенность: большая энергия сосредоточена в левом верхнем углу, а наименьшая энергия в правом нижнем.
Это свойство будет использоваться далее.
Шаг 5. Зиг-заг преобразование
Основной целью всех этих преобразований является удаление высокочастотных компонент, которые находятся в правом нижнем углу. Но для этого необходимо представить массив так, чтобы все высокочастотные значения шли последними в массиве. Для этого используется так называемое зиг-заг преобразование. Элементы массива 8х8 берутся в зигзагообразном порядке начиная с левого верхнего угла.
Шаг 6. Квантизация
На этом шаге как раз и удаляются высокочастотные значения. Получившуюся матрицу на прошлом шаге необходимо поэлементно разделить на таблицу квантования. Y компонент имеет свою таблицу квантования, Cb и Cr - свою. Каждая из этих таблиц получена опытным путём на основе опроса множества людей.
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
Из этой таблицы видно, что значения правого нижнего угла имеют наибольшие значения и соответствуют высокочастотным значениям DU. Если поделить соответствующие значения таблиц друг на друга и округлить к ближайшему целому, то с большой вероятностью в правом нижнем углу будут 0.
Например, после выполнения дискретного косинусного преобразования мы имеем таблицу:
364 42 0 0 0 0 0 0
63 20 0 0 0 0 0 0
-24 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
После квантования и зиг-заг преобразования получаем:
13 2 3 -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 0 0 0 0 0 0 0 0 0 0 0 0 0
Шаг 7. Кодирование серий
Первый элемент массива обладает особыми свойствами - он всегда ненулевой. Поэтому в стандарте jpeg получившийся массив разбивают на 2 части и кодируют разными способами. Первый элемент называется DC коэффициент и я дальше опишу как он кодируется. Оставшийся массив называется AC коэффициентами. Их кодируют с помощью серий. Для этого массив записывают следующим образом:
(0,2) (0,3) (0,-1) (0,1) (EOB)
Первое число обозначает количество “0”, которые идут перед вторым числом. EOB (end of block) - это особое число, которое показывает, что блок закончился и дальше идут только 0. Вот ещё один пример кодирования серий:
57,45,0,0,0,0,23,0,-30,-16,0,,,,0
Даст:
(0,57) (0,45) (4,23) (1,-30) (0,-16) (EOB)
Зиг-заг преобразование как раз и нужно было, чтобы поместить все “0” в конце и заменить их на EOB.
Одним из условий кодирования является то, что первое число не может быть больше 0xF. Поэтому 16 и более нулей кодируются в несколько блоков. Например, 57 восемнадцать нулей 45 кодируется как:
(0, 57) (15, 0) (2, 45)
Шаг 8. Кодирование Хаффмана для AC коэффициентов
Прежде, чем переходить к кодированию Хаффмана, необходимо описать, как хранятся числа согласно стандарту jpeg. Обычно, для хранения чисел в программе используют типы данных фиксированной длины: byte, short, int. В jpeg для хранения числа используется минимальное количество бит. Это значит, что для хранения числа “1” используется только 1 бит. Для хранения числа “9” используется 4 бита - 1001. Но так, как длина числа заранее неизвестна, то необходимо также хранить его длину. В стандарте jpeg длина числа называется категорией. Вот список возможных длин и соответствующих им чисел:
| Значения | Категория | Биты |
|---|---|---|
| 0 | 0 | - |
| -1,1 | 1 | 0,1 |
| -3,-2,2,3 | 2 | 00,01,10,11 |
| -7,-6,-5,-4,4,5,6,7 | 3 | 000,001,010,011,100,101,110,111 |
| -15,..,-8,8,..,15 | 4 | 0000,..,0111,1000,..,1111 |
| -31,..,-16,16,..,31 | 5 | 00000,..,01111,10000,..,11111 |
| -63,..,-32,32,..,63 | 6 | - |
| -127,..,-64,64,..,127 | 7 | - |
| -255,..,-128,128,..,255 | 8 | - |
| -511,..,-256,256,..,511 | 9 | - |
| -1023,..,-512,512,..,1023 | 10 | - |
| -2047,..,-1024,1024,..,2047 | 11 | - |
| -4095,..,-2048,2048,..,4095 | 12 | - |
| -8191,..,-4096,4096,..,8191 | 13 | - |
| -16383,..,-8192,8192,..,16383 | 14 | - |
| -32767,..,-16384,16384,..,32767 | 15 | - |
Результат с прошлого шага:
(0,2) (0,3) (0,-1) (0,1) (EOB)
Можно переписать немного в другом виде - (количество нулей, категория, число в двоичной форме):
(0,2,10) (0,2,11) (0,1,0) (0,1,1) (EOB)
Теперь можно заметить, что первые 2 числа не могут превышать байт. Количество нулей не может быть больше 0xF, а количество категорий тоже не может быть больше 0xF. Этот первый байт и кодируется с помощью кода Хаффмана.
В основе кодов Хаффмана лежит достаточно интересная идея: а давайте наиболее часто встречаемые числа будем кодировать наименьшим количеством бит. Например, для последовательности 6 6 4 5 6 4 число “6” заменить на “0”. Тогда вместо 110 оно будет кодироваться как 0. Но этого недостаточно. Необходимо кодировать количество бит в числе. Это делается с помощью префиксного кодирования. То есть зная префикс, можно однозначно определить значение числа. При этом редкие числа будут занимать больше бит. Более формальное описание кода Хаффмана с помощью бинарных деревьев можно почитать в википедии.
Для кодирования АС коэффициентов существует своя таблица Хаффмана. Она может быть определена в файле, либо заранее оговорена. Например, она может выглядеть так:
| Количество нулей / категория | Длина кода | Код |
|---|---|---|
| 0/0 (EOB) | 4 | 1010 |
| 0/1 | 2 | 00 |
| 0/2 | 2 | 01 |
| 0/3 | 3 | 100 |
| 0/4 | 4 | 1011 |
| 1/1 | 4 | 1100 |
| 0/5 | 5 | 11010 |
| ... | ||
| 15/10 | 16 | 1111111111111110 |
Это пример таблицы Хаффмана из стандарта jpeg. Однако, никто не мешает иметь собственную таблицу для каждого файла. На этом, кстати, основаны множество программ оптимизации jpeg файлов. Вместо того чтобы использовать стандартную таблицу, эти программы считают количество наиболее частых чисел и на основе этого строят свои таблицы Хаффмана.
Хранение таблицы Хаффмана, тоже нетривиально. Вместо того чтобы хранить результирующую таблицу, в файле хранятся 2 таблицы: список длин и список значений. По ним можно построить необходимые таблицы.
Итак, используя таблицу Хаффмана, можно закодировать первый байт следующим образом:
(01,10) (01,11) (00,0) (00,1) (1010)
Итого:
011001110000011010
Шаг 9. Кодирование Хаффмана для DC коэффициента
Коэффициент DC особенный и поэтому кодируется отдельно. Алгоритм состоит из двух этапов:
- вычисление разницы с предыдущим DC коэффициентом. Исследователи заметили, что последовательные блоки 8х8 обычно имеют очень похожие DC коэффициенты. Если вычесть один из другого, то разница между ними не большая и как следствие она будет занимать меньше бит при кодировании Хаффмана. Таким образом, кодируется только разница DC коэффициентов:
Разница = DC текущий - DC предыдущий
Если предыдущего нет, то он считается равным “0”.
- На втором шаге число кодируется с помощью кодов Хаффмана. Например, “13” принадлежит 4ой категории: (4,1101). Для DC коэффициентов существует своя собственная таблица Хаффмана:
| Категория | Длина кода | Код |
|---|---|---|
| 0 | 2 | 00 |
| 1 | 3 | 010 |
| 2 | 3 | 011 |
| 3 | 3 | 100 |
| 4 | 3 | 101 |
| 5 | 3 | 110 |
| 6 | 4 | 1110 |
| 7 | 5 | 11110 |
| 8 | 6 | 111110 |
| 9 | 7 | 1111110 |
| 10 | 8 | 11111110 |
| 11 | 9 | 111111110 |
В результате DC коэффициент “13” будет кодирован как (101,1101):
1011101
И финальный результат:
1011101 011001110000011010
Если бы кодировали “в лоб”, то получилось бы (8 * 8) * 8 бит = 512 бит. Однако, с помощью различных алгоритмов, их удалось сократить до 25 бит. Итого, сжатие почти в 20 раз!
Таким же образом кодируются все оставшиеся DU.
Декодирование jpeg
Чтобы декодировать jpeg, необходимо выполнить все шаги в обратном порядке.
Отличительной особенностью декодирования является поиск кодового слова в таблице Хаффмана. Обычно для этих целей создают таблицы поиска со всеми возможными префиксами кодов Хаффмана. После чего, из файла читаются 2 байта и по ним ищется категория, количество нулей и пр.
Бонус
Если внимательно прочитать алгоритмы, то можно заметить, что дискретное косинусное преобразование, квантизация и конвертация из RGB в YCbCr могут давать дробные значения. А так, как цвета хранятся в целом значении, то будет происходить округление. При одноразовом декодировании из jpeg (YCbCr) в RGB это округление не будет давать заметной ошибки. Однако, при многократной конвертации из растра в jpeg и обратно, ошибка будет накапливаться и давать ощутимые результаты.
Некоторые редакторы определяют так называемое “степень сжатия” jpeg. Это реализуется достаточно просто: все коэффициенты матрицы квантования умножаются на некоторое число. Чем больше число, тем больше коэффициент, тем больше вероятность, что в матрице значений цветов будут нули. Это одновременно уменьшает размер изображения и ухудшает его качество.