JPEG-сжатие

JPEG

Формат файла JPEG (Joint Photographic Experts Group - Объединенная экспертная группа по фотографии, произносится “джейпег”) был разработан компанией C-Cube Microsystems как эффективный метод хранения изображений с большой глубиной цвета, например, получаемых при сканировании фотографий с многочисленными едва уловимыми (а иногда и неуловимыми) оттенками цвета. Самое большое отличие формата JPEG от других рассмотренных здесь форматов состоит в том, что в JPEG используется алгоритм сжатия с потерями (а не алгоритм без потерь) информации. Алгоритм сжатия без потерь так сохраняет информацию об изображении, что распакованное изображение в точности соответствует оригиналу. При сжатии с потерями приносится в жертву часть информации об изображении, чтобы достичь большего коэффициента сжатия. Распакованное изображение JPEG редко соответствует оригиналу абсолютно точно, но очень часто эти различия столь незначительны, что их едва можно (если вообще можно) обнаружить.

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

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

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

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

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

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

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

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

Алгоритм JPEG можно разделить на несколько этапов

0. Подготовка

1. ДКП (Дискретно Косинусоидальное Преобразование)

2. Квантование

3. Вторичное сжатие

-----------------------------------------------------------------------------

Этап 0. Подготовка

-----------------------------------------------------------------------------

Чувствительность человеческого глаза к яркостному Y-компоненту и цветностным компонентам Cb и Cr неодинакова, поэтому вполне допустимым представляется выполнение этого преобразования с прореживанием (интерливингом) Cb и Cr компонентов, когда для группы из четырех соседних пикселов (2x2) вычисляются Y-компоненты, а Cb и Cr используются общие (схема 4:1:1). Более того, пре- и постфильтрация в плоскостях Cb и Cr позволяет использовать прореживание по схеме 16:1:1 без сколько-нибудь значительной потери качества! Нетрудно подсчитать, что уже схема 4:1:1 позволяет сократить выходной поток вдвое (вместо 12 байтов для четырех соседних пикселов достаточно шести). Схема 16:1:1 обеспечивает сокращение потока в 2,67 раза.

Нужно преобразовать изображение в вид яркость/цветность, можно использовать цветовую схему YCbCr (YUV), вот формулы перевода:

Y = 0.299*R + 0.578*G + 0.114*B

Cb = 0.1678*R - 0.3313*G + 0.5*B

Cr = 0.5*R - 0.4187*G + 0.0813*B

Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери данных.

Теперь объясним, как сжать Cb и Cr

-----------------------------------------------------------------------------

Этап 1. ДКП

-----------------------------------------------------------------------------

Следует создать ДКП матрицу, используя эту формулу

DCT = 1/sqr(N), если i=0

ij

DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0

ij

N = 8, 0 < i < 7 , 0 < j < 7

в результате имеем:

|.353553 .353553 .353553 .353553 .353553 .353553 .353553 353553|

|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -490246|

|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 461366|

DCT = |.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -414486|

|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 351435|

|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -274673|

|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 187195|

|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -092414|

например, нам нужно сжать следующий фрагмент изображения:

| 95 88 88 87 95 88 95 95|

|143 144 151 151 153 170 183 181|

|153 151 162 166 162 151 126 117|

IMG = |143 144 133 130 143 153 159 175|

|123 112 116 130 143 147 162 189|

|133 151 162 166 170 188 166 128|

|160 168 166 159 135 101 93 98|

|154 155 153 144 126 106 118 133|

|-33 -40 -40 -41 -33 -40 -33 -33|

| 15 16 23 23 25 42 55 53|

| 25 23 34 38 34 23 -2 -11|

IMG = | 15 16 5 2 15 25 31 47|

| -5 -16 -12 2 15 19 34 61|

| 5 23 34 38 42 60 38 0|

| 32 40 38 31 7 -27 -35 -30|

| 26 27 25 16 -2 -22 -10 5|

T

вот формула, по которой производится ДКП: RES*IMG*DCT

T

для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT

|-103 -3 1 2 4 0 -1 5|

| 89 -40 12 -2 -7 5 1 0|

| 57 31 -30 6 2 0 5 0|

TMP = | 55 -28 24 1 0 -8 0 0|

| 32 -60 18 -1 14 0 -8 1|

| 84 -11 -37 17 -24 4 0 -4|

| 19 81 -16 -20 8 -3 4 0|

| 22 40 11 -22 8 0 -3 2|

затем умножаем ее на ДКП матрицу: RES = TMP*DCT

| 91 3 -5 -6 2 0 1|

|-38 -57 9 17 -2 2 2|

|-80 58 0 -18 4 3 4|

RES = |-52 -36 -11 13 -9 3 0|

|-86 -40 44 -7 17 -6 4|

|-62 64 -13 -1 3 -8 0|

|-16 14 -35 17 -11 2 -1|

|-53 32 -9 -8 22 0 2|

_____________________________________________________________

Этап 2. Квантование

-----------------------------------------------------------------------------

На этом этапе мы посчитаем матрицу квантования, используя этот псевдокод:

for(i=0;i<8;i++)

{

for(j=0;j<8;j++)

Q[i][j] = 1+((1+i+j)*q);

}

где q - это коэффициент качества, от него зависит степень потери качества сжатого изображения

для q = 2 имеем матрицу квантования:

| 3 5 7 9 11 13 15 17|

| 5 7 9 11 13 15 17 19|

| 7 9 11 13 15 17 19 21|

Q = | 9 11 13 15 17 19 21 23|

|11 13 15 17 19 21 23 25|

|13 15 17 19 21 23 25 27|

|15 17 19 21 23 25 27 29|

|17 19 21 23 25 27 29 31|

теперь нужно каждое число в матрице квантования разделить на число в соответствующей позиции в матрице RES, в результате получим:

| 30 0 0 0 0 0 0 0|

| -7 8 1 1 0 0 0 0|

|-11 6 0 1 0 0 0 0|

A = | -5 -3 0 0 0 0 0 0|

| -7 -3 2 0 0 0 0 0|

| -4 4 0 0 0 0 0 0|

| -1 0 1 0 0 0 0 0|

| -3 1 0 0 0 0 0 0|

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

+----+----+----+----+----+----+----+----+

| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |

+----+----+----+----+----+----+----+----+

| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |

+----+----+----+----+----+----+----+----+

| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |

+----+----+----+----+----+----+----+----+

| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |

+----+----+----+----+----+----+----+----+

| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |

+----+----+----+----+----+----+----+----+

| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |

+----+----+----+----+----+----+----+----+

| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |

+----+----+----+----+----+----+----+----+

| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |

+----+----+----+----+----+----+----+----+

итак у нас получилась последовательность:

30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0

0 0 0 0 0 0 0 -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

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

к примеру у нас есть следующая последовательность (Cb или Cr)

11 42 200 123 56 32 125 234 12 24 34 78 145 134 245 101

если будем использовать субдискретизацию 4:1:1, результирующая последовательность будет:

11 123 125 24 145 101

а если использовать 4:2:2

11 234 245

Для восстановления последовательности нужно интерполировать

-----------------------------------------------------------------------------

Этап 3. Вторичное сжатие

_____________________________________________________________

На этом этапе можно применить следующие алгоритмы

a) 7bit RLE

b) LZW с кодом переменной длины

c) Адаптированное кодирование Хаффмана

_____________________________________________________________