Стандарт и алгоритм сжатия стандарта JPEG 2000

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра Сетей и устройств телекоммуникаций

РЕФЕРАТ

На тему:

«Стандарт и алгоритм сжатия стандарта JPEG 2000»

МИНСК, 2008

Стандарт сжатия JPEG 2000 и система ROI

Одно из успешных применений вейвлетов - их использование для сжатия изображений. Многочисленные исследования в этом направлении вылились в конце концов в принятие нового стандарта - JPEG2000. Пока изображения в этом формате еще не очень распространены, но нет никаких сомнений в том, что он полностью вытеснит нынешний популярный JPEG. Поэтому темой данной курсовой работы является описание и основные параметры алгоритма сжатия JPEG 2000, а так же описания технологии сжатия отдельных частей изображения (Region of Interests, ROI).

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

Объединение в рамках единой технологии сжатия с потерями и без потерь. В дополнениях к JPEG есть режим сжатия без потерь, но эта технология защищена патентами.

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

2. Унифицированная архитектура декодера. В JPEG имеется порядка 44 различных режимов декодирования, в зависимости от приложения. Синтаксис JPEG2000 таков, что в независимости от применяемого способа кодирования используется один и тот же декодер.

3. Масштабируемость. В зависимости от потребности, это может быть масштабируемость по размеру, разрешению, частотному содержанию, количеству цветов.

4. Обработка отдельных областей на изображении (Region Of Interest, смотрите далее). Например, пользователя может интересовать не все изображение улицы, а лишь фото отдельной машины, он выделяет его (мышью), и декодер с высоким качеством восстанавливает этот фрагмент. (Все невозможно "поднять" с высоким качеством из-за ограничений на объем передаваемой информации). Кстати говоря, такой режим имеется в видеокодеке Analog Devices ADV611/ADV613.

5. Сжатие изображений больших размеров.

6. Возможность обработки сжатого изображения без декомпрессии.

Рассмотрим основные блоки, входящие в структурную схему алгоритма сжатия JPEG2000.

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

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

3. Квантование. В первой части стандарта определен равномерный квантователь с мертвой зоной.

4. Энтропийное кодирование. Применяется адаптивный арифметический кодер (в JPEG используется кодер Хаффмана). Ввиду патентных ограничений используется не QM-кодер разработки IBM, а чуть худший MQ-кодер, специально разработанный для JPEG2000. Кодирование ведется не всего изображения в целом и даже не отдельных субполос, а более мелких объектов - кодируемых блоков (КБ). Размер кодируемого блока может быть не более 4096 пикселов, высота не менее 4 пикселов. Такое разбиение хотя и снижает несколько коэффициент сжатия, но повышает устойчивость сжатого потока к ошибкам канала связи: ошибка испортит лишь небольшой блок. Кодирование блоков ведется в три этапа, битовыми плоскостями.

5. Сжатый поток данных упаковывается в пакеты. Именно благодаря гибкой и продуманной структуре пакетов возможно достижение целей разработки стандарта.

2 Алгоритм сжатия JPEG 2000 и его отличия от JPEG

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

Идея алгоритма (базовая схема).

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

1. Вместо дискретного косинусного преобразования (DGT) используется дискретное wavelet-преобразование (DWT).

2. Вместо кодирования по Хаффману используется арифме-тическое сжатие.

3. В алгоритм изначально заложено управление качеством областей изображения.

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

3. Последовательность операций, используемых в алгоритме JPEG-2000

Шаг 1. Сдвиг по яркости (DC level shift).

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

(1)

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

(2)

Шаг 2. Изменение цветового пространства (RGB - YUY).

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

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

Шаг 3. Дискретное wavelet преобразование (DWT).

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

Для сжатия с потерями коэффициенты выглядят как:

Для сжатия без потерь коэффициенты задаются так:

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

3

4

Поскольку большинство h_L(i), кроме окрестности i=0, равны 0, то можно переписать приведенные формулы с меньшим количеством операций.

Для простоты рассмотрим случай сжатия без потерь.

5

6

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

7

8

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

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

по строке вправо и влево

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

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

9

10

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

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

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

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

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

Шаг 4. Квантование.

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

Шаг 5. Арифметическое сжатие.

Для сжатия получающихся массивов данных в JPEG 2000 используется вариант арифметического сжатия, называемый MQ-кодер, прообраз которого (QM-кодер) рассматривался еще в стандарте JPEG, но реально не использовался из-за патентных ограничений. Ввиду этого, используется не QM-кодер разработки IBM, а чуть худший, MQ-кодер, специально разработанный для JPEG2000. Кодирование ведется не всего изображения в целом и даже не отдельных субполос, а более мелких объектов - кодируемых блоков. Размер кодируемого блока может быть не более 4096 пикселов, высота не менее 4 пикселов. Такое разбиение хотя и снижает несколько коэффициент сжатия, но повышает устойчивость сжатого потока к ошибкам канала связи: ошибка испортит лишь небольшой блок. Кодирование блоков ведется в три этапа, битовыми плоскостями.

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

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

Рис. 1 Локальное улучшение качества областей изображения

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

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

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

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

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

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

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

ЛИТЕРАТУРА

1. Шелухин О.И., Лукьянцев Н.Ф. Цифровая обработка и передача речи.- М.: Радио и связь, 2000.

2. Рабинер Л.Р., Шафер Р.В. Цифровая обработка речевых сигналов.-М.: Радио и связь, 2001.

3. Секунов Н.Ю. Обработка звука на PC.- СПб.: БХВ-Петербург, 2001.

4. Нейрокомпьютеры в системах обработки изображений. - М.: Радиотехника, 2003.

5. Назаров М.В., Прохоров Ю.Н. Методы цифровой обработки и передачи речевых сигналов.- М.: Радио и связь, 2005.