Сжатие изображений: JPEG и JPEG2000. Алгоритм JPEG является алгоритмом сжатия данных с потерями

Алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group) специально для сжатия 24-битных и полутоновых изображений в 1991 году. Этот алгоритм не очень хорошо сжимает двухуровневые изображении, но он прекрасно обрабатывает изображения с непрерывными тонами, в которых близкие пикселы обычно имеют схожие цвета. Обычно глаз не в состоянии заметить какой-либо разницы при сжатии этим методом в 10 или 20 раз.

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

Рассмотрим работу алгоритма подробнее. Предположим, что сжимается полноцветное 24-битное изображение. В этом случае получаем следующие этапы работы.

Шаг 1. Переводим изображение из пространства RGB в пространство YCbCr с помощью следующего выражения:

Отметим сразу, что обратное преобразование легко получается путем умножения обратной матрицы на вектор , который по существу является пространством YUV:

.

Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП – по 8 бит отдельно для каждой компоненты. При больших степенях сжатия блок 8х8 раскладывается на компоненты YCbCr в формате 4:2:0, т.е. компоненты для Cb и Cr берутся через точку по строкам и столбцам.

Шаг 3. Применение ДКП к блокам изображения 8х8 пикселей. Формально прямое ДКП для блока 8х8 можно записать в виде

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

.

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

Здесь - результат ДКП, для вычисления которого требуется операций умножения и почти столько же сложений, что существенно меньше прямых вычислений по формуле выше. Например, для преобразования изображения размером 512х512 пикселей потребуется арифметических операций. Учитывая 3 яркостных компоненты, получаем значение 12 582 912 арифметических операций. Количество умножений и сложений можно еще больше сократить, если воспользоваться алгоритмом быстрого преобразования Фурье. В результате для преобразования одного блока 8х8 нужно будет сделать 54 умножений, 468 сложений и битовых сдвигов.

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

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

.

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

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

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

Шаг 5. Переводим матрицу 8х8 в 64-элементный вектор при помощи «зигзаг»-сканирования (рис. 2).

Рис. 2. «Зигзаг»-сканирование

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

Шаг 6. Преобразовываем вектор с помощью модифицированного алгоритма RLE, на выходе которого получаем пары типа (пропустить, число), где «пропустить» является счетчиком пропускаемых нулей, а «число» - значение, которое необходимо поставить в следующую ячейку. Например, вектор 1118 3 0 0 0 -2 0 0 0 0 1 … будет свернут в пары (0, 1118) (0,3) (3,-2) (4,1) … .

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

Шаг 7. Свертываем получившиеся пары с помощью неравномерных кодов Хаффмана с фиксированной таблицей. Причем для DC и AC коэффициентов используются разные коды, т.е. разные таблицы с кодами Хаффмана.

Рис. 3. Схема упорядочения DC коэффициентов

Рис. 4. Структурная схема алгоритма JPEG

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

При разработке данного стандарта руководствовались тем, что данный алгоритм должен был сжимать изображения довольно быстро – не более минуты на среднем изображении. Это в 1991 году! А его аппаратная реализация должна быть относительно простой и дешевой. При этом алгоритм должен был быть симметричным по времени работы. Выполнение последнего требования сделало возможным появление цифровых фотоаппаратов, снимающие 24 битные изображения. Если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат «перезарядится» - сожмет изображение.

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

«Реализация алгоритмов

JPEG и JPEG2000»

Выполнил:

студент группы 819

Угаров Дмитрий

Принципы работы алгоритмов JPEG и JPEG2000

1. Алгоритм JPEG

JPEG (англ. Joint Photographic Experts Group - объединённая группа экспертов в области фотографии) - является широко используемым методом сжатия фотоизображений. Формат файла, который содержит сжатые данные обычно также называют именем JPEG; наиболее распространённые расширения для таких файлов.jpeg, .jfif, .jpg, .JPG, или.JPE. Однако из них.jpg самое популярное расширение на всех платформах.

Алгоритм JPEG является алгоритмом сжатия с потерей качества .

Область применения

Формат является форматом сжатия с потерями, поэтому некорректно считать что JPEG хранит данные как 8 бит на канал (24 бит на пиксель). С другой стороны , так как данные, подвергающиеся компрессии по формату JPEG и декомпрессированные данные обычно представляются в формате 8 бит на канал, иногда используется эта терминология. Поддерживается также сжатие чёрно-белых полутоновых изображений.

При сохранении JPEG-файла можно указать степень качества, а значит и степень сжатия, которую обычно задают в некоторых условных единицах, например, от 1 до 100 или от 1 до 10. Большее число соответствует лучшему качеству, но при этом увеличивается размер файла. Обыкновенно, разница в качестве между 90 и 100 на глаз уже практически не воспринимается. Следует помнить , что побитно восстановленное изображение всегда отличается от оригинала. Распространённым заблуждением является мнение о том, что качество 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

Cr = 0.5*R – 0.4187*G – 0.0813*B.
Во время декодирования можно использовать соответствующее обратное преобразование:
R = Y + 1.402*Cr

G = Y – 0.34414*Cb – 0.71414*Cr

B = Y + 1.772*Cb.
Примечание, связывающее Y,Cb,Cr в человеческой визуальной системе:

Глаз, особенно сетчатка, имеет как визуальные анализаторы два типа ячеек: ячейки для ночного видения, воспринимающие только оттенки серого (от ярко-белого до темно-черного) и ячейки дневного видения, которые воспринимают цветовой оттенок. Первые ячейки , дающие цвет RGB, обнаруживают уровень яркости, подобный величине Y. Другие ячейки, ответственные за восприятие цветового оттенка, - определяют величину, связанную с цветоразностью.

2. Субдискретизация компонентов цветности усреднением групп пикселей;

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

1)тип 4:2:0 (когда изображение разбивается на квадраты 2х2 пикселей и в каждом из них все пиксели получают одинаковые значения каналов Cb и Cr, а яркость Y у остается у каждого своя)

2) тип 4:2:2 (объединение по компонентам цветности происходит только по горизонтали в группах по два пикселя).

3)тип 4: 4: 4 подразумевает, что каждому пикселю в каждой строке соответствует собственное уникальное значение компонентов Y, Cb и Cr. (рис.1 а)

4) тип 4:2:2. Выполнив субдискретизацию сигнала цветности с коэффициентом 2 по горизонтали, мы получим из потока 4: 4: 4 YCbCr поток 4: 2: 2 YCbCr. Запись «4: 2: 2» означает , что в отдельно взятой строке на 2 значения цветности приходятся 4 значения яркости (см. рис.1 б). Сигнал 4: 2: 2 YCbCr очень немного проигрывает по качеству изображения сигналу 4: 4: 4 YCbCr, зато требуемая ширина полосы сокращается на 33% от исходной.

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

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

DCT непосредственно применяемый к блоку (в нашем случае 8х8 пикселей) изображения будет выглядеть так:

где х, y - пространственные координаты пикселя (0..7) ,

f(x,y) - значения пикселей исходного макроблока (допустим, яркость)

u,v - координаты пикселя в частотном представлении (0..7)

w(u) =1/SQRT(2) при u=0, в остальных случаях w(u)=1 (SQRT - квадратный корень)

w(v) =1/SQRT(2) при v=0, в остальных случаях w(v)=1

Или в матричной форме:

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

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

5. Этап Вторичного Сжатия

Заключительной стадией работы кодера JPEG является кодирование полученной матрицы.

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

Так, после того, как мы выполнили DCT-преобразование над блоком величин 8x8, у нас есть новый блок 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

Как Вы видите, сначала - верхний левый угол (0,0), затем величина в (0,1), затем (1,0), затем (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0) и т.п.

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

5.2 RunLength кодирование нулей (RLE)

Теперь у нас есть вектор с длинной последовательностью нулей. Мы можем использовать это, кодируя последовательные нули. ВАЖНО: Вы увидите позже почему, но здесь мы пропускаем кодировку первого коэффициента вектора (коэффициент DC), который закодирован по-другому. Рассмотрим исходный 64 вектор как 63 вектор (это - 64 вектор без первого коэффициента)

Допустим, мы имеем 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, только 0,...,0

Здесь - как RLC JPEG сжатие сделано для этого примера:

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

Как Вы видите, мы кодируем для каждой величины, отличающейся от 0 количество последовательных ПРЕДШЕСТВУЮЩИХ нулей перед величиной, затем мы добавляем величину. Другое примечание: EOB - короткая форма для Конца Блока , это - специальная кодированная величина (маркер). Если мы достигли в позиции на векторе, от которого мы имеем до конца только нули вектора, мы выделим эту позицию с EOB и завершим сжатие RLC квантованного вектора.

[Заметьте, что если квантованный вектор не оканчивается нулями (имеет последний элемент не 0), мы не будем иметь маркер EOB.]

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

Другая ОСНОВНАЯ вещь: Допустим, где-нибудь на квантованном векторе мы имеем:

57, восемнадцать нулей, 3, 0,0 ,0,0 2, тридцать-три нуля, 895, EOB

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

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

(0,57); (15,0) (2,3); (4,2); (15,0) (15,0) (1,895), (0,0)

(15,0) - специальная кодированная величина, которая указывает , что там следует за 16 последовательными нулями.

5.3 Конечный шаг - кодирование Хаффмана

Сначала ВАЖНОЕ примечание: Вместо хранения фактической величины, JPEG стандарт определяет, что мы храним минимальный размер в битах, в котором мы можем держать эту величину (это названо категория этой величины) и затем битно кодированное представление этой величины подобно этому:

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)

45, аналогично , будет закодирован как (6,101101)

30 -> (5,00001)

И теперь, мы напишем снова строку пар:

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

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

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

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

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
Достоинства и недостатки

К недостаткам формата следует отнести то, что при сильных степенях сжатия дает знать о себе блочная структура данных, изображение «дробится на квадратики» (каждый размером 8x8 пикселей). Этот эффект особенно заметен на областях с низкой пространственной частотой (плавные переходы изображения, например, чистое небо). В областях с высокой пространственной частотой (например, контрастные границы изображения), возникают характерные «артефакты» - иррегулярная структура пикселей искаженного цвета и/или яркости. Кроме того, из изображения пропадают мелкие цветные детали. Не стоит также забывать и о том, что данный формат не поддерживает прозрачность.

Однако, несмотря на недостатки, JPEG получил очень широкое распространение из-за высокой степени сжатия, относительно существующих во время его появления альтернатив.

2. Алгоритм JPEG2000

Алгоритм JPEG-2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года.

Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG заключаются в следующем:

1)Лучшее качество изображения при сильной степени сжатия. Или, что то же самое , большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.

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

3)Основной алгоритм сжатия заменен на wavelet. Помимо указанного повышения степени сжатия это позволило избавиться от 8-пиксельной блочности, возникающей при повышении степени сжатия. Кроме того, плавное проявление изображения теперь изначально заложено в стандарт (Progressive JPEG, активно применяемый в Интернет, появился много позднее JPEG).

4)Для повышения степени сжатия в алгоритме используется арифметическое сжатие. Изначально в стандарте JPEG также было заложено арифметическое сжатие, однако позднее оно было заменено менее эффективным сжатием по Хаффману, поскольку арифметическое сжатие было защищено патентами. Сейчас срок действия основного патента истек , и появилась возможность улучшить алгоритм.

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

6)Поддержка сжатия однобитных (2-цветных) изображений. Для сохранения однобитных изображений (рисунки тушью, отсканированный текст и т.п.) ранее повсеместно рекомендовался формат GIF, поскольку сжатие с использованием ДКП весьма неэффективно к изображениям с резкими переходами цветов. В JPEG при сжатии 1-битная картинка приводилась к 8-битной, т.е. увеличивалась в 8 раз, после чего делалась попытка сжимать, нередко менее чем в 8 раз. Сейчас можно рекомендовать JPEG 2000 как универсальный алгоритм.

7)На уровне формата поддерживается прозрачность. Плавно накладывать фон при создании WWW страниц теперь можно будет не только в GIF, но и в JPEG 2000. Кроме того, поддерживается не только 1 бит прозрачности (пиксель прозрачен/непрозрачен), а отдельный канал , что позволит задавать плавный переход от непрозрачного изображения к прозрачному фону.

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

Этапы кодирования

Процесс сжатия по схеме JPEG2000 включает ряд этапов:

1. Преобразование изображения в оптимальное цветовое пространство.
На данном этапе кодирования с помощью соответствующих соотношений цветовая модель RGB преобразуется в YUV:

При декомпрессии применяется соответствующее обратное преобразование:

2. Дискретное вейвлет преобразование.

Дискретное wavelet преобразование (DWT) также может быть двух видов - для случая сжатия с потерями и для сжатия без потерь.

Это преобразование в одномерном случае представляет собой скалярное произведение соответствующих коэффициентов на строку значений. Но т.к. многие коэффициенты нулевые, то прямое и обратное вейвлет преобразование можно записать следующими формулами (для преобразования крайних элементов строки используется ее расширение на 2 пикселя в каждую сторону, значения которых симметричны с значениями элементов строки относительно ее крайних пикселей):
y(2*n + 1) = x(2*n + 1) - (int)(x(2*n) + x(2*n + 2)) / 2

y(2*n) = x(2*n) + (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

и обратное

x(2*n) = y(2*n) - (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

x(2*n + 1) = y(2*n + 1) + (int)(x(2*n) + x(2*n + 2)) / 2.

3. Квантование коэффициентов.

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

4. Этап Вторичного Сжатия

. Как и в JPEG, в новом формате последним этапом алгоритма сжатия является кодирование без потерь. Но, в отличие от предыдущего формата, в JPEG2000 используется алгоритм арифметического сжатия.

Программная реализация

В данной работе реализованы алгоритмы JPEG и JPEG2000. В обоих алгоритмах реализовано прямое и обратное кодирование (отсутствует последний этап вторичного сжатия). Расчет JPEG происходит довольно долго (порядка 30 секунд) в связи «прямым» высчитыванием DCT. Если потребуется увеличить скорость работы , следует изначально вычислить матрицу DCT(изменения производить в классе DCT).

Перейдем к рассмотрению программы:

1. 
   После запуска выводится окно, где

и сможете его сохранить , нажав кнопку (2) и введя желаемое название в диалоговом окне.

При достаточно большом Quality Factor изображение сильно измениться. Если это JPEG алгоритм то будут ярко выражены блоки размера 8x8.(в случае алгоритма JPEG2000, блочного деления не будет)

До:

После:

Сжатие методом JPEG является самым распространенным и эффективным способом сжатия. В 1992 году стал международным стандартом в области ГИ. JPEG – аббревиатура группы экспертов создавших стандарт (Joint Photographic Experts Group).

В основе метода лежит поиск разницы между соседними пикселями. Кодирование осуществляется в несколько этапов.

1. Конвертирование цветовой модели изображения (обычно RGB) в цветовую модель YUV, некоторый аналог модели Lab, где яркостная составляющая отделена от цветовой. В модели RGB изменение любого компонента цвета приводит к изменению яркости пикселя. В модели YUV компонента Y – компонента яркости, а компоненты U, V – хранят информацию о цвете.

Y = 0,299 x R + 0,587 x G + 0,114 x B

U = (B – Y) / 0,433 +128

V = (R – Y) / 0,355 + 128

2. Подвыборка – соседние пиксели группируются попарно в каналах U и V. Разделение яркости и цвета позволяет уделять больше внимание яркости, чем данным о цвете. Этот процесс осуществляется для компонент с различной частотой.

Используется два метода подвыборки 4:1:1 и 4:2:2. Так как каждый цвет кодируется 3 байтами, для передачи цвета 4 пикселей (12 байт в RGB) требуется 6 байт и 8 байт соответственно. Т.е. YUV411 сокращает объем данных в два раза, а YUV422 в 1,5 раз. С точки зрения математики происходит значительная потеря информации, но человеческий глаз ее не воспринимает, ввиду избыточности информации в самом изображении.

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

4. Квантование – удаление малозначительной для глаза информации. Все составляющие делятся на коэффициенты относительной важности и округляются до целого.

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

5. Этап Zig-Zag . Этап назван так вследствие того, что пиксели собираются в последовательность по размерам (сначала располагаются пиксели, отвечающие за более крупные объекты). Кодировщик движется как бы зигзагом.

6. Сжатие методом RLE.

7. Сжатие методом JPEG.

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

Вопросы для самопроверки.

1. Для чего необходимы алгоритмы сжатия данных?

2. Что такое сжатие "без потерь" и сжатие "с потерями"?

3. Опишите основные алгоритмы сжатия графической информации "без потерь".

4. Опишите алгоритм сжатия методом JPEG.

Область применения

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

С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселами приводит к появлению заметных артефактов . Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF , GIF или PNG .

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

JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, однако, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS .

Сжатие

При сжатии изображение преобразуется из цветового пространства RGB в YCbCr (YUV). Следует отметить, что стандарт JPEG (ISO/IEC 10918-1) никак не регламентирует выбор именно YCbCr, допуская и другие виды преобразования (например, с числом компонентов , отличным от трёх), и сжатие без преобразования (непосредственно в RGB), однако спецификация JFIF (JPEG File Interchange Format, предложенная в 1991 году специалистами компании C-Cube Microsystems, и ставшая в настоящее время стандартом де-факто) предполагает использование преобразования RGB->YCbCr.

После преобразования RGB->YCbCr для каналов изображения Cb и Cr, отвечающих за цвет, может выполняться «прореживание» (subsampling ), которое заключается в том, что каждому блоку из 4 пикселов (2х2) яркостного канала Y ставятся в соответствие усреднённые значения Cb и Cr (схема прореживания «4:2:0» ). При этом для каждого блока 2х2 вместо 12 значений (4 Y, 4 Cb и 4 Cr) используется всего 6 (4 Y и по одному усреднённому Cb и Cr). Если к качеству восстановленного после сжатия изображения предъявляются повышенные требования, прореживание может выполняться лишь в каком-то одном направлении - по вертикали (схема «4:4:0») или по горизонтали («4:2:2»), или не выполняться вовсе («4:4:4»).

Стандарт допускает также прореживание с усреднением Cb и Cr не для блока 2х2, а для четырёх расположенных последовательно (по вертикали или по горизонтали) пикселов, то есть для блоков 1х4, 4х1 (схема «4:1:1»), а также 2х4 и 4х2 (схема «4:1:0»). Допускается также использование различных типов прореживания для Cb и Cr, но на практике такие схемы применяются исключительно редко.

Далее яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются на блоки 8х8 пикселов. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП) . Полученные коэффициенты ДКП квантуются (для Y, Cb и Cr в общем случае используются разные матрицы квантования) и пакуются с использованием кодирования серий и кодов Хаффмана . Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования , однако из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно используется редко. В популярную библиотеку libjpeg последних версий включена поддержка арифметического кодирования, но с просмотром сжатых с использованием этого метода изображений могут возникнуть проблемы, поскольку многие программы просмотра не поддерживают их декодирование.

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

При сохранении изображения в JPEG-файле указывается параметр качества, задаваемый в некоторых условных единицах, например, от 1 до 100 или от 1 до 10. Большее число обычно соответствует лучшему качеству (и большему размеру сжатого файла). Однако даже при использовании наивысшего качества (соответствующего матрице квантования, состоящей из одних только единиц) восстановленное изображение не будет в точности совпадать с исходным, что связано как с конечной точностью выполнения ДКП, так и с необходимостью округления значений Y, Cb, Cr и коэффициентов ДКП до ближайшего целого. Режим сжатия Lossless JPEG, не использующий ДКП, обеспечивает точное совпадение восстановленного и исходного изображений, однако его малая эффективность (коэффициент сжатия редко превышает 2) и отсутствие поддержки со стороны разработчиков программного обеспечения не способствовали популярности Lossless JPEG.

Разновидности схем сжатия JPEG

Стандарт JPEG предусматривает два основных способа представления кодируемых данных.

Наиболее распространённым, поддерживаемым большинством доступных кодеков , является последовательное (sequential JPEG) представление данных, предполагающее последовательный обход кодируемого изображения поблочно слева направо, сверху вниз. Над каждым кодируемым блоком изображения осуществляются описанные выше операции, а результаты кодирования помещаются в выходной поток в виде единственного «скана», то есть массива кодированных данных, соответствующего последовательно пройденному («просканированному») изображению. Основной или «базовый» (baseline) режим кодирования допускает только такое представление. Расширенный (extended) режим наряду с последовательным допускает также прогрессивное (progressive JPEG) представление данных.

В случае progressive JPEG сжатые данные записываются в выходной поток в виде набора сканов, каждый из которых описывает изображение полностью с всё большей степенью детализации. Это достигается либо путём записи в каждый скан не полного набора коэффициентов ДКП, а лишь какой-то их части: сначала - низкочастотных, в следующих сканах - высокочастотных (метод «spectral selection» то есть спектральных выборок), либо путём последовательного, от скана к скану, уточнения коэффициентов ДКП (метод «successive approximation», то есть последовательных приближений). Такое прогрессивное представление данных оказывается особенно полезным при передаче сжатых изображений с использованием низкоскоростных каналов связи, поскольку позволяет получить представление обо всём изображении уже после передачи незначительной части JPEG-файла.

Обе описанные схемы (и sequential, и progressive JPEG) базируются на ДКП и принципиально не позволяют получить восстановленное изображение абсолютно идентичным исходному. Однако стандарт допускает также сжатие, не использующее ДКП, а построенное на основе линейного предсказателя (lossless, то есть «без потерь», JPEG), гарантирующее полное, бит-в-бит, совпадение исходного и восстановленного изображений. При этом коэффициент сжатия для фотографических изображений редко достигает 2, но гарантированное отсутствие искажений в некоторых случаях оказывается востребованным. Заметно большие степени сжатия могут быть получены при использовании не имеющего, несмотря на сходство в названиях, непосредственного отношения к стандарту JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) метода сжатия JPEG-LS , описываемого стандартом ISO/IEC 14495-1 (ITU T.87 Recommendation).

Синтаксис и структура

Файл JPEG содержит последовательность маркеров , каждый из которых начинается с байта 0xFF, свидетельствующего о начале маркера, и байта-идентификатора. Некоторые маркеры состоят только из этой пары байтов, другие же содержат дополнительные данные, состоящие из двухбайтового поля с длиной информационной части маркера (включая длину этого поля, но за вычетом двух байтов начала маркера то есть 0xFF и идентификатора) и собственно данных. Такая структура файла позволяет быстро отыскать маркер с необходимыми данными (например, с длиной строки, числом строк и числом цветовых компонентов сжатого изображения).

Основные маркеры JPEG

Маркер	Байты	Длина	Назначение	Комментарии
SOI	0xFFD8	нет	Начало изображения
SOF0	0xFFC0	переменный размер	Начало фрейма (базовый, ДКП)	Показывает что изображение кодировалось в базовом режиме с использованием ДКП и кода Хаффмана. Маркер содержит число строк и длину строки изображения (двухбайтовые поля со смещением соответственно 5 и 7 относительно начала маркера), количество компонентов (байтовое поле со смещением 8 относительно начала маркера), число бит на компонент (байтовое поле со смещением 4 относительно начала маркера), а также соотношение компонентов (например, 4:2:0).
SOF1	0xFFC1	переменный размер	Начало фрейма (расширенный, ДКП, код Хаффмана)	Показывает что изображение кодировалось в расширенном (extended) режиме с использованием ДКП и кода Хаффмана. Маркер содержит число строк и длину строки изображения, количество компонентов, число бит на компонент, а также соотношение компонентов (например, 4:2:0).
SOF2	0xFFC2	переменный размер	Начало фрейма (прогрессивный, ДКП, код Хаффмана)	Показывает что изображение кодировалось в прогрессивном режиме с использованием ДКП и кода Хаффмана. Маркер содержит число строк и длину строки изображения, количество компонентов, число бит на компонент, а также соотношение компонентов (например, 4:2:0).
DHT	0xFFC4	переменный размер	Содержит таблицы Хаффмана	Задает одну или более таблиц Хаффмана.
DQT	0xFFDB	переменный размер	Содержит таблицы квантования	Задает одну или более таблиц квантования.
DRI	0xFFDD	4 байта	Указывает интервал повторений	Задает интервал между маркерами RST n в макроблоках.
SOS	0xFFDA	переменный размер	Начало сканирования	Начало первого или очередного скана изображения с направлением обхода слева направо сверху вниз. Если использовался базовый режим кодирования, используется один скан. При использовании прогрессивных режимов используется несколько сканов. Маркер SOS является разделяющим между информативной (заголовком) и закодированной (собственно сжатыми данными) частями изображения.
RSTn	0xFFDn	нет	Перезапуск	Вставляется в каждом r макроблоке, где r - интервал перезапуска DRI маркера. Не используется при отсутствии DRI маркера. n , младшие 3 бита маркера кода, циклы от 0 до 7.
APPn	0xFFEn	переменный размер	Задаётся приложением	Например, в EXIF JPEG-файла используется маркер APP1 для хранения метаданных, расположеных в структуре, основанной на TIFF .
COM	0xFFFE	переменный размер	Комментарий	Содержит текст комментария.
EOI	0xFFD9	нет	Конец закодированной части изображения.

Достоинства и недостатки

К недостаткам сжатия по стандарту JPEG следует отнести появление на восстановленных изображениях при высоких степенях сжатия характерных артефактов : изображение рассыпается на блоки размером 8x8 пикселов (этот эффект особенно заметен на областях изображения с плавными изменениями яркости), в областях с высокой пространственной частотой (например, на контрастных контурах и границах изображения) возникают артефакты в виде шумовых ореолов. Следует отметить, что стандарт JPEG (ISO/IEC 10918-1, Annex K, п. K.8) предусматривает использование специальных фильтров для подавления блоковых артефактов, но на практике подобные фильтры, несмотря на их высокую эффективность, практически не используются. Однако, несмотря на недостатки, JPEG получил очень широкое распространение из-за достаточно высокой (относительно существовавших во время его появления альтернатив) степени сжатия, поддержке сжатия полноцветных изображений и относительно невысокой вычислительной сложности .

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

Для ускорения процесса сжатия по стандарту JPEG традиционно используется распараллеливание вычислений, в частности - при вычислении ДКП. Исторически одна из первых попыток ускорить процесс сжатия с использованием такого подхода описана в опубликованной в 1993 г. статье Касперовича и Бабкина , в которой предлагалась оригинальная аппроксимация ДКП, делающая возможным эффективное распараллеливание вычислений с использованием 32-разрядных регистров общего назначения процессоров Intel 80386. Появившиеся позже более производительные вычислительные схемы использовали SIMD -расширения набора инструкций процессоров архитектуры x86. Значительно лучших результатов позволяют добиться схемы, использующие вычислительные возможности графических ускорителей (технологии NVIDIA CUDA и AMD FireStream) для организации параллельных вычислений не только ДКП, но и других этапов сжатия JPEG (преобразование цветовых пространств, run-level, статистическое кодирование и т.п.), причём для каждого блока 8х8 кодируемого или декодируемого изображения. В статье была впервые [источник? ] представлена реализация распараллеливания всех стадий алгоритма JPEG по технологии CUDA, что значительно ускорило производительность сжатия и декодирования по стандарту JPEG.

В 2010 году ученые из проекта PLANETS поместили инструкции по чтению формата JPEG в специальную капсулу, которую поместили в специальный бункер в швейцарских Альпах. Сделано это было с целью сохранения для потомков информации о популярных в начале XXI века цифровых форматах.

См. также

Примечания

Ссылки

• Спецификация JFIF 1.02 (текстовый файл)
• Оптимизация JPEG. Часть 1 , Часть 2 , Часть 3 .

Адаптивная генерация матриц квантования в JPEG-подобных схемах

Лужков Юрий Валерьевич,

аспирант Санкт-Петербургского государственного университета информационных технологий, механики и оптики.

Научный руководитель – доктор технических наук, профессор

Тропченко Александр Ювенальевич .

Введение

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

Широкая распространенность формата JPEG (Joint Photographic Experts Group ) [Wallace G. K.] ставит перед исследователями следующий вопрос: возможно ли модифицировать существующую схему компрессии таким образом, чтобы увеличить качество сжатия, не меняя при этом алгоритм декомпрессии? Решение этой задачи позволит внедрять модификации в существующие компрессоры, не заботясь о наличии у пользователей специального (модифицированного) программного обеспечения для декомпрессии изображений.

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

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

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

Адаптивное квантование сигнала

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

Так, пусть дано множество интервалов и множество точек , тогда функция квантования определяется как для . В случае равномерного скалярного квантования множество интервалов можно представить в виде:

где – параметр, или шаг квантования , – базовое смещение интервалов, , – номер интервала, который и является кодируемым объектом. Тогда операция квантования может быть сведена к простому делению с округлением:

.(1)

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

Адаптивное скалярное квантование на основе весового критерия

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

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

Таким образом, процедура квантования выполняется с учетом некоторой статистической информации о сигнале, заданном как , собранной от M блоков и уникальной для элементов каждого индекса n . Функция квантования (1) в этом случае будет обозначаться как , а функция параметра квантования – .

Введём критерий , назвав его весом коэффициента спектра . Величина будет отражать степень значимости соответствующей спектральной позиции n коэффициентов .

Одним из способов вычисления базируется на средних амплитудах:

.(2)

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

.(3)

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

,

где и – минимальное и максимальное значение соответственно (случай рассматривается отдельно).

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

.(4)

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

.(5)

Таким образом, функция шага квантования локализована в диапазоне от a 1 до a 2 .Варьируя её форму, можно в большей или меньшей степени подавлять определённые группы коэффициентов.

Применим теперь предложенный подход для адаптивной генерации матриц квантования в схеме JPEG . В (5) будем использовать линейную корректирующую функцию и критерий максимальных амплитуд (3).

Графики функций по умолчанию шага квантования JPEG приведены на рис. 1, слева. Графики Δ, адаптивно сгенерированные для изображения « Oldman », показаны на рис. 1, справа. В обоих случаях значения упорядочены по возрастанию. Как видно, для первой трети значений аргумента наблюдается резкий рост Δ, что особенно характерно для сгенерированных функций. На этом участке сгенерированные Δ местами значительно превосходят по величине стандартные, что ведет к большему подавлению соответствующих частот.

Рис. 1. Стандартные и сгенерированные функции параметра квантования с упорядоченными

по возрастанию значениями.

График для изображения « Oldman » приведен на рис. 2, слева. Справа показаны результаты компрессии с применением матриц по умолчанию и матриц, сгенерированных в рамках эксперимента. Как видно из результатов, разница в степени сжатия составляет до 20 % в пользу адаптивного подхода при одинаковых значениях PSNR .

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

Заключение

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

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

Литература

1. Fung H. T., Parker K. J. Design of image-adaptive quantization tables for JPEG // Journal of Electronic Imaging. – 1996. – Vol. 4, N. 2. – P. 144 – 150.

2. Gray R.M., Neuhoff D.L. Quantization // IEEE Transactions on Information Theory. – 1998. – Vol. 44, N. 6. – P. 2325 – 2383.

3. Ratnakar V., Livny M. Extending RD -OPT with global thresholding for JPEG optimization // Data Compression Conference. – 1996.

4. Wallace G. K. The JPEG still picture compression standard // IEEE Trans. Consumer Electronics. – 1992. – Vol. 38, N. 1. – P. 18 – 34.