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

Алгоритм разработан группой экспертов в области фотографии (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 состоит из нескольких этапов, выполняемых над изображением последовательно, один за другим:

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

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

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

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

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

На этапе преобразования цветового пространства осуществляется преобразование изображения из цветового пространства 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 ).

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

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

• Алгоритмы сжатия без потерь;
• Алгоритмы сжатия с потерями.

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

Алгоритмы сжатия без потерь

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.

Словарные алгоритмы

Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:

Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.

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


Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.

Алгоритмы статистического кодирования

Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.

Алгоритм Хаффмана

Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
2. Выбираются два свободных узла дерева с наименьшими весами
3. Создается их родитель с весом, равным их суммарному весу
4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов.

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

Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал

(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 - один из новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений . Опе­рирует алгоритм областями 8x8, на которых яркость и цвет меняются срав­нительно плавно. Вследствие этого при разложении матрицы такой, области в двойной ряд по косинусам (см. формулы ниже) значимыми охазываютоя только первые коэффициенты..Таким образом, сжатие в JPEG осуществяяе ется за счет плавности изменения цветов в изображении.

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

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

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

Как работает алгоритм

Итак, рассмотрим алгоритм подробнее (рис. 2.1). Пусть мы сжимаем 24-битовое изображение.

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

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

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

Шаг 3. В упрощенном виде ДКП при п=8 можно представить так:

nu,v] = ^Hc(i,u)xC(j,v)y

r Y)

Yq = IntegerRound

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

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

Шаг 5. Переводим матрицу 8x8 в 64-элементный вектор при помощи "зиг-заг"-сканирования, т. е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...

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

Шаг 6. Свертываем вектор с помощью алгоритма группового кодирова­ния. При этом получаем пары типа <пропустить, число>, где "пропустить" является счетчиком пропускаемых нулей, а "число" - значение, которое не­обходимо поставить в следующую ячейку. Так, вектор 42 3000-2 00001 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1)....

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

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

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

■ задается степень сжатия;

■ выходное цветное изображение может иметь 24 бита на точку.

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

■ При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании и восстановить исходные данные ста­новится невозможно.

■ Проявляется эффект Гиббса- ореолы по границам резких переходов цветов.

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

Выполнение последнего требования сделало возможным появление та­ких устройств, как цифровые фотоаппараты, снимающие 24-битовые фото­графии на 8-256 Мб флеш-карту." Йвтом эта карта вставляется в разъём на вашем ноутбуке и соответствующая программа позволяет считать изобра­жения. Не правда Ня, если бы алгоритм был несимметричен, было бы не­приятно долго ждать, пока аппарат "перезарядится" - сожмет изображение.

Не очень приятным свойством 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 и на данный момент зани­мает видное место в системах мультимедиа.

Характеристики алгоритма JPEG: o ! ш. ,. Степень сжатия: 2-200 (задается здльзователем). ,ц, :_,. . Класс изображений: полноцветные 2jj.битовые изображения или изо-| бражения в градациях серого без резких переходов цве^о&,(фотографии).

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

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