Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Алгоритм JPEG 2000

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

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

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

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

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

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

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

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

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

Идея алгоритма

Базовая схема JPEG 2000 очень похожа на базовую схему JPEG. Отличия заключаются в следующем:

■ вместо дискретного косинусного преобразования (DCT) используется дискретное wavelet -преобразование (DWT);

■ вместо кодирования по Хаффману используется арифметическое сжатие;

■ в алгоритм изначально заложено управление качеством областей изо­бражения;

■ не используется явно дискретизация компонент U и V после преобразо­вания цветовых пространств, поскольку при DWT можно достичь того же результата, но более аккуратно.

Рассмотрим алгоритм по шагам (рис. 2.8).



Рис. 2.8. Конвейер операций, используемый в алгоритме JPEG 2000

Шаг 1. В JPEG 2000 предусмотрен сдвиг яркости (DC level shift) каждой компоненты (RGB) изображения перед преобразованием в YUV. Это дела­ется для выравнивания динамического диапазона (приближения к нулю гис­тограммы частот), что приводит к увеличению степени сжатия. Формулу преобразования можно записать как:

I\x,y) = I{x,y)-2ST-x.

Значение степени ST для каждой компоненты R, G и В свое (определяет­ся при сжатии компрессором). При восстановлении изображения выполня­ется обратное преобразование:

Г(х,у) = 1(х,у) + 2-1.

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

-2G + B

Обратное преобразование осуществляется с помощью обратной матрицы:

Шаг 3. Дискретное wavelet-преобразование (DWT) также может быть двух видов - для случая сжатия с потерями и для сжатия без потерь. Его ко­эффициенты задаются табл. 2.1 и 2.2.

Таблица 2.1. Коэффициенты для сжатия с потерями

Коэффициенты при упаковке

i

Низкочастотные

коэффициенты hL{i)

Высокочастотные

коэффициенты hd.1)

0

1.115087052456994

0.6029490182363579

±1

0.5912717631142470

-0.2668641184428723

±2

-0.05754352622849957

-0.07822326652898785

±3

-0.09127176311424948

0.01686411844287495

±4

0

0.02674875741080976

Другие i

0

0

Коэффициенты при распаковке

i

Низкочастотные

коэффициенты gL(i)

Высокочастотные

коэффициенты дн(0

0

0.6029490182363579

1.115087052456994

±1

-0.2668641184428723

0.5912717631142470

±2

-0.07822326652898785

-0.05754352622849957

±3

0.01686411844287495

-0.09127176311424948

±4

0.02674875741080976

0

Другие /'

0

0

Таблица 2.2. Коэффициенты для сжатия без потерь

При упаковке

При распаковке

i

Низкочастотные коэффициенты

Высокочастот­ные коэффици­енты /)«(/)

Низкочастотные коэффициенты

Высокочастот­ные коэффици­енты £Гн0)

0

6/8

1

1

6/8

±1

2/8

-1/2

1/2

-2/8

±2

-1/8

0

0

-1/8

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

/V -1

УошРи, (2«) = Е Х*Р«> < ■/") " ,11- < У " 2") '

У„„„„„(2л + 1) = X *„„„„ (У) • «я (У- 2л - 1).

у-о

Поскольку большинство hL{i), кроме окрестности /=0, равны нулю, то можно переписать приведенные формулы с меньшим количеством опера­ций. Для простоты рассмотрим случай сжатия без потерь.


7о«(2п) =


-х„(2И-2) + 2-х„(2и-1) + 6-х,,(2И) + 2-*Л2П + 1)--д:,„(2я + 2)


*,„(2п) ,„ ,х х„(2л + 2)
уш(2п + \) = —а!-1+*41(2л + 1)—^------- '-.

Легко показать, что данную запись можно эквивалентно переписать, уменьшив еще втрое количество операций умножения и деления (однако теперь необходимо будет подсчитать сначала все нечетные у). Добавим также операции округления до ближайшего целого, не превышающего за­данное число а, обозначаемые как [aJ:

ут, (2л + 1) = х,„(2л + 1)

Упражнение. Самостоятельно уменьшите количество операций для случая без потерь.

Рассмотрим на примере, как работает данное преобразование. Для того чтобы преобразование можно было применять к крайним пикселам изобра­жения, оно симметрично достраивается в обе стороны на несколько пиксе­лов, как показано на рисунке ниже. В худшем случае (сжатие с потерями) нам необходимо достроить изображение на 4 пиксела (рис. 2.9).

ЕДГВБ АБВГДЕДГВБА

Рис. 2.9. Симметричное расширение изображения (яркости АБ ...Е) по строке вправо и влево

Пусть мы преобразуем строку из 10 пикселов. Расширим ее значения вправо и влево и применим DWT-преобразование:

п -2 -1

0

1

2

3

4 5

6 7

8 9

10 11

х,п 3 2

1

2

3

7

10 15

12 9

10 5

10 9

Уои, 0

1

0

3

1

11 4

13 -2

8 -5

Получившаяся строка 1, 0, 3, 1, 11, 4, 13, -2, 8, -5 и является цепочкой, однозначно задающей исходные данные. Совершив аналогичные преобра­зования с коэффициентами для распаковки, приведенными выше в таблице, получим необходимые формулы:


^«(2") = >'o„(2/i)-


Л„,(2п-1)+^„,(2л + 1) + 2



х„.,(2п + 1) = у0.,(2п + 1) +


хош(2п) + хои1(2п + 2) 2


Упражнение. Докажите, что во всех случаях округления мы будем получать одинаковые входную и выходную цепочки.

Легко проверить (используя преобразование упаковки), что значения на концах строк в уш также симметричны относительно и=0 и 9. Воспользо­вавшись этим свойством, расширим нашу строку вправо и влево и приме­ним обратное преобразование:

л -2 -1

0

1

2

3

4 5

6 7

8 9

10

11

Уош 0

1

0

3

1

И 4

13 -2

8 -5

8

-2

*out

1

2

3

7

10 15

12 9

10 5

10

Как видим, мы получили исходную цепочку (х,„= y,,).

Упражнение. Примените прямое и обратное DWT-преобразования к цепочке из 10 байт: 121,107,98,102,145,182,169,174,157,155.

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

Уои,

1

0

3

1

11

4

13

-2

8

-5

Уош

1

3

11

13

8

0

1

4

-2

-5

Это преобразование применяется сначала ко всем строкам изображения, а затем ко всем столбцам изображения. В результате изображение делится на 4 квадранта (примеры смотрите в описании рекурсивного сжатия). В первом квадранте будет сформирована уменьшенная копия изображения, а в остальных трех - высокочастотная информация. После чего преобразование повторно применяется уже только к первому квадранту изображения по тем же правилам (преобразование второго уровня) (рис. 2.10).

Рис. 2.10. Вид DWT

Для корректного сохранения результатов под данные 2-го и 3-го квад­рантов выделяется на 1 бит больше, а под данные 4-го квадранта - на 2 бита больше. То есть если исходные данные были 8-битовые, то на 2-й и 3-й квадранты нужно 9 бит, а на 4-й -10, независимо от уровня применения DWT. При записи коэффициентов в файл можно использовать иерархичес­кую структуру DWT, помещая коэффициенты преобразований с большего уровня в начало файла. Это позволяет получить "изображение для предва­рительного просмотра", прочитав небольшой участок данных из начала файла, а не распаковывая весь файл, как это приходилось делать при сжатии изображения целиком. Иерархичность преобразования может также исполь­зоваться для плавного улучшения качества изображения при передаче его посети.

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

Шаг 5. Для сжатия получающихся массивов данных в JPEG 2000 ис­пользуется вариант арифметического сжатия, называемый MQ-кодером, прообраз которого (QM-кодер) рассматривался еще в стандарте JPEG, но реально не использовался из-за патентных ограничений. Подробнее об ал­горитме арифметического сжатия читайте в гл. 1 разд. 1.

Области повышенного качества

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

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

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

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

Такой подход логично применять, если:

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

■ изображение сжимается один раз, а разжимается множество раз.

В качестве примеров приложений, удовлетворяющих этим ограничениям, можно привести практически все мультимедийные продукты на CD-ROM. И для CD-ROM энциклопедий, и для игр важно записать на диск как можно больше информации, а фафика, как правило, занимает до 70% всего объема диска. При этом технология производства дисков позволяет сжимать каждое изображение индивидуально, максимально повышая степень сжатия.

Интересным примером являются WWW-сервер. Для них тоже, как пра­вило, выполняются оба изложенных выше условия. При этом совершенно не обязательно индивидуально подходить к каждому изображению, по­скольку, по статистике, 10% изображений будут запрашиваться 90% раз. То есть для крупных справочных или ифовых серверов появляется возмож­ность уменьшать время зафузки изображений и степень зафуженности ка­налов связи адаптивно.

В JPEG 2000 используется 1-битовое изображение-маска, задающее по­вышение качества в данной области изображения. Поскольку за качество областей у нас отвечают коэффициенты DWT-преобразования во 2, 3 и 4-м квадрантах, то маска преобразуется таким образом, чтобы указывать на все коэффициенты, соответствующие областям повышения качества (рис. 2.12)


*

*

*

Рис. 2.12. Преобразование маски области повышения качества для обработки DWT-коэффициентов

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


Характеристики алгоритма JPEG 2000:

Степень сжатия: 2-200 (задается пользователем). Возможно сжатие ! без потерь.

Класс изображений: полноцветные 24-битовые изображения. Изо-

; бражения в градациях серого без резких переходов цветов (фотографии). ! 1-битовые изображения.

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

Характерные особенности: позволяет удалять визуально неприятные \ эффекты, повышая качество в отдельных областях. При сильном сжатии I появляется блочность и большие волны в вертикальном и горизонтальном \ направлениях.