JPEG (Joint Photographic Experts Group)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 01:59, 20 апреля 2017.

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


Сжатие

На рис. 1 представлен процесс сжатия изображения JPEG, который состоит из следующих этапов:

Рис. 1. Этапы сжатия изображения

Преобразование цветового пространства

На этапе преобразования цветового пространства осуществляется преобразование изображения из цветового пространства RGB в YCbCr:

где 8-битовые величины без знака.

Величина называется яркостью. Это величина используется монохромными мониторами, чтобы представить цвет RGB. Физиологически, передает интенсивность цвета RGB, воспринятого глазом.

Формула для подобна средневзвешенному значению с разным весом для каждого спектрального компонента: глаз наиболее чувствителен к зеленому цвету (G), затем следует красный компонент (R), в последнюю очередь — синий (B).

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

Дискретизация

Стандарт JPEG принимает во внимание то, что глаз более чувствителен к яркости цвета, чем к оттенку этого цвета. (Черно-белые ячейки вида имеют больше влияния, чем ячейки дневного видения).

Так, для большинства JPG, яркость взята для каждого пикселя, тогда как цветоразность – как средняя величина для блока 2x2 пикселей, что позволяет достичь хороших результатов сжатия, с незначительным убытком в визуальном восприятии нового обработанного изображения [1].

Сдвиг уровня

Все 8-битовые величины без знака (Y,Cb,Cr) в изображении - "смещенные по уровню": они преобразовываются в 8-битовое знаковое представление вычитанием 128 из их величины.

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

Изображение делится на блоки 8x8 пикселей, затем для каждого блока 8x8 применяется DCT-преобразование. Если размер X исходного образа не делится на 8, шифратор должен сделать его делимым, дополняя остальные правые столбцы (пока X не станет кратным 8). Аналогично, если размер Y не делится на 8, шифратор должен дополнить строки.

Блоки 8x8 обрабатываются слева направо и сверху вниз.

Поскольку каждый пиксель в блоке 8x8 имеет 3 компонента (Y,Cb,Cr), DCT приложен отдельно в трех блоках 8x8:

  • Первый блок 8x8 является блоком, который содержит яркость пикселей в исходном блоке 8x8;
  • Второй блок 8x8 является блоком, который содержит величины Cb;
  • И, аналогично, третий блок 8x8 содержит величины Cr.

Таким образом, DCT-преобразование работает с пространством частот изменения яркости и оттенка. Эти частоты тесно связаны с уровнем детализации изображения. Высокие частоты соответствуют высокому уровню детализации.

DCT-трансформация очень похожа на 2-мерное преобразование Фурье, которое получает из временного интервала (исходный блок 8x8) частотный интервал (новые коэффициенты 8x8=64, которые представляют амплитуды проанализированного частотного пространства).

Прямое DCT-преобразование (FDCT):

где
, когда
- в остальных случаях.

Обратное DCT-преобразование (IDCT):

где .

Применение этих формул непосредственно в вычислительном отношении дорого, особенно, когда имеются разработанные более быстрые алгоритмы для прямого или обратного DCT. Один, названный AA&N, имеет только 5 операций умножения и 29 операций сложения [2].

Зигзагообразная перестановка DCT коэффициентов

После выполнения DCT-преобразования над блоком величин 8x8, получается новый блок 8x8, который просматривается по зигзагу, подобно этому (числа в блоке 8x8 указывают порядок, в котором просматривается 2-мерная матрица 8x8):

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

В результате получается вектор с 64 коэффициентами. Смысл этого зигзагообразного вектора заключается в том, что коэффициенты DCT просматриваются в порядке повышения пространственных частот. Первая величина в векторе (индекс 0) соответствует самой низкой частоте в изображении – она обозначается термином DC. Остальная часть коэффициентов DCT обозначается AC. Величина с индексом 63 соответствует амплитуде самой высокой частоты в блоке 8x8.

Квантование

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

для (i = 0; i<=63; i++)
         вектор[i] = (округлить) (вектор[i] / таблица_квантования[i] + 0.5)

Ниже приведен пример таблицы квантования для яркости (Y), которая указана в приложении стандарта JPEG (дается в форме блока 8x8, полученного из 64 векторных величин зигзагообразным преобразованием):

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

Процесс квантования играет ключевую роль в JPEG сжатии и основывается на "психовизуальном эффекте". Глаз более чувствителен к низким частотам, поэтому на этапе квантования происходит деление элементов матрицы (Y, Cb или Cr), которые находятся ближе к правому нижнему углу (высокие частоты), на соответствующие значения в таблице квантования (большие значения), что приводит к удалению высоких частот (в результате деления матрица содержит огромное количество нулей в правом нижнем углу).

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

Большинство существующих шифраторов используют приведенный пример таблицы квантования, причем величины не оптимизируются. Таблица определяется в JPEG файле с DQT-маркером (англ. Define Quantization Table — определение таблицы квантования). Обычно присутствует одна таблица для Y, и другие для оттенка (Cb и Cr).

Run-Length кодирование нулей (RLE)

RLE (англ. Run-Length Encoding — кодирование по длинам серий) кодирует последовательность нулей в полученном квантованном векторе, причем первый коэффициент в векторе не кодируется.

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

57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0

Тогда в результате RLE-кодирования получится:

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); EOB

Таким образом, для каждой величины, отличающейся от 0, кодируется количество последовательных предшествующих перед этой величиной нулей, а затем добавляется данная величина. Если после величины, отличной от 0, до конца вектора следуют только нули, то в результат кодирования записывается EOB (англ. End Of Block — конец блока) — специальная кодированная величина (маркер).

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

Вместо хранения фактической величины, стандарт JPEG хранит минимальный размер в битах, необходимый для представления величины (категория величины), а также битно кодированное представление данной величины:

Величина Категория Биты для величины
0 0 -
-1,1 1 0,1
-3,-2,2,3 2 00,01,10,11
-7,..,-4,4,..,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,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)

кодируется только правая величина этих пар, кроме пар, которые являются специальными маркерами подобно (0,0) или (15,0):

  • число 57 находится в категории 6 и в битах кодируется как 111001, в результате записывается (6,111001),
  • 45, аналогично, будет закодирован как (6,101101),
  • 23 -> (5,10111),
  • -30 -> (5,00001),
  • -8 -> (4,0111),
  • 1 -> (1,1).

Тогда результат будет записан в следующем виде:

(0,6), 111001; (0,6), 101101; (4,5), 10111; (1,5), 00001; (0,4), 0111; (2,1), 1; (0,0)

Пары 2 величин, заключенные в скобки, могут быть представлены в байте, так как фактически каждая из 2 величин может быть представлена 4 битами (счетчик предшествующих нулей всегда меньше 15 так же, как и категория). Тогда в этом байте старшие разряды будут представлять число предшествующих нулей, а младшие - категорию новой величины, отличной от 0.

Конечный шаг кодировки состоит в кодировании Хаффмана этого байта, и затем записи в файл JPG данного результата, а также битового представления числа.

Например, для байта 6 (эквивалент (0,6)) код Хаффмана представляет собой последовательность 111000;

для байта 69 = (4,5) — 1111111110011001;

21 = (1,5) — 11111110110;

4 = (0,4) — 1011;

33 = (2,1) — 11011;

0 = EOB = (0,0) — 1010.

Тогда конечный поток битов, записанных в файле JPG, для 63 коэффициентов будет иметь следующий вид:

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001 1011 0111 11011 1 1010

Кодирование первого коэффициента вектора (DC)

DC является первым коэффициентом в квантованном векторе, соответствующим самой низкой частоте в образе. Он содержит много энергии, присутствующей в исходном изображении блока 8x8 (обычно, это большая величина). Поэтому кодирование DC-коэффициента значительно отличается от кодирования остальных коэффициентов AC (в файле JPG есть 2 таблицы Хаффмана для каждого компонента изображения: для DC и для AC). Поскольку коэффициенты DC последовательных блоков тесно связаны между собой, авторы стандарта JPEG решили кодировать в файле JPG различие между DC двух последовательных блоков 8x8:

Тогда DC текущего блока равен: .

Декодирование JPG начинается с 0, т.е. первым коэффициентом рассматривается . Затем к текущей величине добавляется величина Diff, декодированная из JPG.

Результат кодирования величины Diff записывается в следующем виде:

Diff = (код_Хаффмана (категория), битно кодированное представление)

Например, Diff равняется -511. Это соответствует категории 9 и битно кодированному представлению 000000000. Число 9 имеет код Хаффмана, равный 1111110. Тогда в результате кодирования Diff будет записано как: 1111110 000000000.

Таким образом, в файле JPG конечный поток битов для вектора с 64 величинами будет записан в виде:

1111110 000000000 111000 111001 111000 101101 1111111110011001 10111 11111110110 00001 1011 0111 11011 1 1010

Как видно, в файле JPG сначала закодирован DC, затем AC.

Потеря данных при сжатии

При сжатии методом JPEG потеря информации происходит на этапе квантования, когда коэффициенты округляются до целых чисел в пределе -2048 ... 2047. Гистограмма на рис. 2 показывает дискретное распределение частоты появления коэффициентов. На рисунке видно, что с увеличением абсолютного значения частота появления коэффициента уменьшается[3].

Рис. 2. Гистограмма для коэффициентов JPEG после квантования

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

Поскольку в квантованной матрице отсутствует значительная доля высокочастотной информации, имеющейся в исходной матрице, первая часто сжимается до половины своего первоначального размера или даже еще больше. Реальные фотографические изображения часто совсем невозможно сжать с помощью методов сжатия без потерь, поэтому 50%-ное сжатие следует признать достаточно хорошим. С другой стороны, применяя методы сжатия без потерь, можно сжимать некоторые изображения на 90%. Такие изображения плохо подходят для сжатия методом JPEG.

Примечания

  1. Стандарт JPEG определяет, что для каждого компонента образа (например, Y) должны быть определены 2 коэффициента дискретизации: один – для горизонтальной дискретизации, другой – для вертикальной дискретизации. Эти коэффициенты дискретизации определяются в файле JPG относительно максимального коэффициента дискретизации.
  2. Больше информации и реализацию этого алгоритма можно найти в свободном программном обеспечении для JPEG кодировщиков от Независимой JPEG Группы (IJG), их C-источники могут быть найдены на сайте www.ijg.org.
  3. Эта особенность не сохраняется после использования JSteg.

См. также