Тема №18. Обзор алгоритма сжатия JPEG2000

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

· особенности и обзор областей применения JPEG2000;

· обзор технологии JPEG2000;

· сравнение технологий сжатия изображений JPEG2000 и JPEG

Изучение материалов лекции поможет ответить на вопрос: «Почему необходимо использовать JPEG2000, хотя есть такие технологии, как JPEG и фрактальное сжатие?»

Вейвлет-преобразование является основой технологии сжатия изображений JPEG2000, разработка которой была начата комитетом JPEG в 1996 году для обеспечения нормальной работы разработанных приложений и приложений, которые будут разработаны в будущем [Rabbani]. Первая технология JPEG (стандарт JPEG), предоставляет набор методов и алгоритмов сжатия данных. Этот набор включает следующие компоненты:

· базовая система сжатия JPEG, которая является простым и эффективным алгоритмом сжатия изображений с потерями, использующим дискретное косинусное преобразование (ДКП) и метод сжатия Хаффмана, работает с 8-ми битными изображениями и только в последовательном режиме;

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

· режим сжатия без потерь, основанный на предсказывающем кодировании и использующий как метод Хаффмана, так и алгоритм арифметического кодирования, но не использует ДКП

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

Технология JPEG2000 описана в международном документе, состоящем из шести частей и названном JPEG2000 «standard».

В первой части (как и в стандарте JPEG) описана основная система кодирования. Во второй части описаны дополнения к первой части (extensions). В третьей части описан алгоритм сжатия видео Motion JPEG2000, предназначенный для использования в цифровых фотоаппаратах со вспышкой, обработке видео в процессе монтажа телевизионных программ, организации цифровых кино- и видеоархивов. В 4 части описаны результаты тестов. В части 5 приводятся доступные на момент разработки стандарта программные реализации базового алгоритма JPEG2000. В части 6 описаны форматы файлов JP2 и JPX для хранения изображений и метаданных. JPEG2000 применяется в следующих областях:

· графические редакторы: Corel Draw, Photoshop (плагин), XnView, GIMP (дополнение) и т.п.;

· устройства обработки мультимедиа: цифровых камерах, устройства обработки данных, в мобильной связи (при передаче данных по сетям 3G, факсимильной связи, принтерах, сканерах…);

· при организации клиент-серверной архитектуры: Интернет-сайты, базы цифровых изображений, видеосвязь, мультимедиа сервер;

· при передаче данных со спутников в HD-качестве, датчиках движения, вычислительных сетях, в системах видеонаблюдения;

· обработка медицинских изображений;

· дистанционное зондирование Земли;

· запись видео высокого разрешения, хранение и редактирование видеофайлов

Известно, что несколько крупных производителей видеопродукции или оборудования для трансляций сигнала использовали JPEG2000 в таких перспективных HD-технологиях, как системы обработки и передачи видео в реальном времени и видео-серверы.

В цифровом кинематографе (Digital Cinema Initiatives LLC) формат JPEG2000 используется как один из основных методов сжатия.

Стандарт JPEG2000 используется и в системах видеонаблюдения (рис.27): кодер JPEG 2000 обеспечивает сжатие, а сервер – возможность просмотра изображения на разных типах устройств (восстановление из кодового потока). Кроме того, JPEG2000 используется в приложениях, обеспечивающие возможность передачи видео через Интернет (broadcasting) и системах видеоконференциях и IP-телефонии.

http://www.slideshare.net/castcores/cast-chip-ex10

Рис.1. Пример использования JPEG2000 в системе видеонаблюдения

Использование технологии JPEG2000 в практических целях обусловлено следующими ключевыми особенностями [Acharya, Tinku 3]:

· более производительное сжатие, чем у JPEG;

· сжатие с потерями и без потерь;

· возможность управления разрешением изображения;

· организация вложенного битового потока, позволяющего осуществлять прогрессивное декодирование и управлять значением отношения SNR;

· разбиение на непересекающиеся прямоугольные блоки, tiling;

· кодирование выбранной области (Region of Interest Coding);

· коррекция ошибок;

· произвольный доступ к элементам кодового потока и их обработка;

· более гибкий формат файлов

Проанализируйте преимущества, позволяющие говорить о JPEG2000 как о преемнике JPEG.

Приведем схему базовой системы сжатия JPEG2000 [3, 9]

Рис.2. Базовый алгоритм JPEG2000

Базовая система сжатия JPEG2000 (сравните с базовым алгоритмом JPEG и найдите различия в схемах кодирования изображения) позволяет получить на выходе декодера изображение высокого качества и осуществлять доступ к произвольным фрагментам изображения [Acharya, Tinku 3, 10]. Сжатие изображения в JPEG2000 осуществляется в три этапа (рис.1):

· препроцессинг изображения

· сжатие (вейвлет-преобразование, квантование и энтропийное кодирование)

· организация кодового потока

Перейдем к описанию системы сжатия JPEG2000.

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

На первом шаге входное изображение разбивается на ранее заданное число прямоугольных непересекающихся блоков (если изображение большого размера). Каждый из этих блоков называется тайл (tile). В первой части стандарта JPEG2000 тайл определяется как «двумерный массив указателей на координатной сетке с зафиксированной длиной и шириной». Изображение представляется в виде плитки, которая покрывает изображение. Тайл может быть большим, как целое изображение, так и маленьким, как отдельный пиксель изображения. Сжатие каждого тайла осуществляется отдельно с использованием собственных значений параметров сжатия. Такое разбиение обычно используется в тех приложениях, для которых количество используемой памяти ограничено по сравнению с размером изображения.

В случае цветного изображения (как и JPEG) обрабатываются три цветовых плоскости (R, G и B). Для полутонового изображения каждый тайл состоит из одного элемента.

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

Далее осуществляется сдвиг по уровню (DC level shifting) осуществляется для того, чтобы все значения яркости пикселей входного изображения принадлежали одному и тому же динамическому диапазону яркостей. Сдвиг осуществляется путем вычитания из каждого беззнакового компонента тайла (или изображения) постоянной 2^B-1 для того, значение каждого элемента (сэмпла) было около нуля. Операция сдвига не применяется к знаковым элементам.

После этого выполняется цветовое преобразование элементов изображения (если изображение полутоновое, то преобразование не выполняется). JPEG2000 позволяет выбрать, какое преобразование выполнить: необратимое (ICT, irreversible color transform) и обратимое преобразования (RCT, revercible color transform). Необратимое преобразование – это обычное цветовое преобразование из пространства RGB в цветоразностное пространство, используемое в базовом JPEG.

Другой тип преобразования может быть использован как сжатия без потерь, так и с потерями. Преобразование записывается следующим образом [Rabbani]:

Рис.3. Прямое и обратное RCT

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

Рис.4. Этапы препроцессинга

После операции препроцессинга осуществляется собственно сжатие изображения, состоящее из трех этапов: дискретное вейвлет-преобразование, квантование, энтропийное кодирование.

Сначала к каждому тайлу применяется дискретное вейвлет-преобразование (ДВП), позволяющее обрабатывать изображение целиком, а не по блокам, как в базовом алгоритме JPEG (проанализируйте материалы по JPEG2000 и выясните, почему было выбрано ДВП?).

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

Рис.5. Банк фильтров

Низкочастотный фильтр пропускает низкие частоты входного сигнала, а высокие частоты не обрабатывает. В результате фильтрации на выходе получается размытая версия входного сигнала. С другой стороны, высокочастотный фильтр обрабатывает высокие частоты сигнала, такие как углы, текстуры и детали, пропуская низкие частоты сигнала (достраивается весь спектр) [Д.С.Ватолин, Rabbani].

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

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

В стандарте JPEG2000 для выполнения ДВП можно использовать один из двух банков фильтров: Daubechi(7, 9) и LeGall(5, 3). У первого банка фильтров 7 компонентов в высокочастотном фильтре и 9 – в низкочастотном. Этот банк фильтров используется для сжатия с потерями. У второго банка фильтров 5 высокочастотных и 3 низкочастотных компонента. В обоих случаях сигнал расширяется симметрично в обе стороны.

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

Восстановление сигнала из вейвлет-коэффициентов осуществляет другая пара низкочастотного и высокочастотного фильтров (g₀, g₁), называемая банком фильтров синтеза. Согласно рис.4, сначала выполняется обратная субдискретизация путем добавления нулей через каждые два элемента сигнала, обработанного фильтром банка анализа. Результат обрабатывается фильтром синтеза g₀(n). К выходному сигналу высокочастотного фильтра h₁(n) также применяется обратная субдискретизация и фильтрация h₁(n). Для получения восстановленного сигнала x’(n) результат работы фильтров суммируется. Сигнал может быть восстановлен либо полностью, либо с нужной точностью.

Заметим, что после того, как одномерный сигнал был разложен на две полосы (band), низкочастотная полоса может быть еще раз подана на фильтр анализа и разложена на две подполосы. Этот процесс может продолжаться до нужной пользователю точности. В большинстве случаев далее обрабатывается только низкочастотный результат фильтрации. Такое разложение называется двумерным преобразованием (dyadic decomposition). Базовый алгоритм JPEG2000 поддерживает только такой вариант вейвлет-разложения, в то время как вторая часть стандарта позволяет применять разложение и к высокочастотным подполосам (subband).

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

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

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

На иллюстрации показана схема ДВП с применением вейвлета Хаара (2 и 3 уровня):

à à

Рис.7. Пример 2-мерного ДВП (вейвлет Хаара): разрешение 0, 1, 2

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

На рис.8. показано разложение исходного изображения до уровня 3.

Рис.8. Результат ДВП

(с использованием вейвлета Хаара, разложение до уровня 3 и схематичное изображение подполос)

Из рис.7. видно, что каждая подполоса по-своему индексируется. В общем случае обозначение kHL означает, что горизонтальный высокочастотный фильтр (H), был применен к строкам изображения, в то время как вертикальный низкочастотный фильтр (L) был применен к столбцам изображения на k-том уровне разложения.

В процессе разработки стандарта JPEG большое внимание было уделено степени сложности реализации кодера и декодера [Rabbani]. Прорабатывались такие вопросы, как количество памяти, количество операций на элемент, программная и аппаратная реализация кодера и декодера: точность преобразований и параллельная обработка элементов изображения. Выбор размера блока ДКП, равного 8x8, наилучшим образом удовлетворял указанным требованиям. В тоже время, применение ДВП требует хранение обрабатываемого изображения в памяти. Использовании при кодировании тайлов небольшого размера уменьшает количество требуемой памяти без существенного влияния на производительность сжатия. Кроме того, были предложены альтернативные схемы реализации ДВП. Например, учеными I.Daubeshi (Ингрид Добеши) и W.Sweldens (Швелденс) была разработана схема реализации ДВП, получившая название схемы лифтинга (lifting scheme, «подъем»). Применение схемы лифтинга позволяет уменьшить количество задействованной памяти и увеличить скорость вычисления вейвлет-коэффициентов благодаря перезаписи ячеек, содержащих значения входного сигнала.

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

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

(1)

Приведем пример. Пусть у нас входной сигнал записывается массивом чисел: x_n = [2 1 2 3 7 10 15 12 9 10 5]. Сначала периодически расширим сигнал на два значения на границах (для примера), а затем применим вейвлет-преобразованию (фильтрацию). Сначала определяются нечетные отсчеты по индексам, а затем вычисляются значения при четных индексах. Последовательность y (последняя строка таблицы) однозначно представляет исходный сигнал (виден эффект сдвига – крайние слева и справа значения не заполнены).

Таблица 1.Пример фильтрации

Если же к последовательности y_out применить субдискретизацию, то получится следующее множество элементов y₁ = [3 -1 -1 -1 0 17 17].

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

(2)

Таким образом, схема лифтинга (прямое преобразование) состоит из двух шагов: прогноз (prediction step) – представление каждого нечетного компонента сигнала в виде линейной комбинации четных компонентов сигнала и вычитании результата из ошибки прогноза. Шаг обновления (update step) заключается в изменении четных компонентов путем добавления к ним уже измененных нечетных компонентов сигнала.

При восстановлении сначала происходит обратная субдискретизация, то есть дописываются нули (восстанавливается длина последовательности): y₁’ = [3 0 -1 0 -1 0 -1 0 0 0 17 0 17]. Затем происходит пересчет по формулам (2). В результате фильтрации и субдискретизации в изображение вносятся первичные искажения.

Следующим этапом сжатия в JPEG2000 является квантование (сравните с квантованием в базовом алгоритме JPEG и выявите главные отличия). В стандарте применяется однородное квантование (скалярное квантование) с центральной «мертвой зоной» (uniform quantization with central dead-zone). «Мертвая зона» – центральный интервал прямой линии с длиной, в два раза большей, чем шаг квантования (квантователь на рис.9.).

Рис.9. Квантователь, использующийся в JPEG2000.

Квантователь можно представить в виде функции Q, которая ставит в соответствие анализируемому коэффициенту некоторое множество на прямой действительных чисел [Marcellin]. Для данного вейвлет-коэффициента x квантователь выдает индекс (целое число со знаком) q, определяемое следующим образом:

(3)

Индекс определяет интервал на прямой линии, в который попадает коэффициент x и передается декодеру. Обратное квантование записывается как:

(4)

То есть, по индексам восстанавливается значение входного сигнала.

Вид функций (3) и (4) может отличаться в зависимости от метода квантования, в базовой части стандарта JPEG2000 по умолчанию принято следующее соотношение:

(5)

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

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

(6)

Здесь значение выбирается пользователем из интервала от 0 до 1 (обычно 1/2). Параметр выбирается для достижения лучшего качества восстановленного сигнала или изображения. В первой части JPEG2000 длина «мертвой зоны» фиксирована, в то время как вторая часть стандарта позволяет использовать в некоторых приложениях переменную длину мертвой зоны. Кроме того, в стандарте JPEG2000 используется вложенное скалярное квантование (рассмотрите самостоятельно), что позволяет создавать вложенный кодовый поток.

При кодировании в JPEG2000 квантователь сопоставляет вейвлет-коэффициентам y_b(u,v) в подполосе b квантованные индексы q_b(u,v) как показано на рис.9. и используя соотношение:

(7)

Шаг квантования представлен в виде двухбайтового числа: первый байт – 11-битное значение мантиссы , и второй байт – 5-битное значение экспоненты , значения которых определяются по формуле:

(8)

Значение R_b – количество бит, выделяемых на представление динамического диапазона подполосы b.

В случае, если используется сжатие с потерями (банк фильтров (9,7)), обратное квантование задается следующим соотношением [Rabbani]:

(9)

Здесь значение параметра произвольно выбирается декодером. Если =0.5, то декодирование происходит также, как и при использовании стандарта JPEG.

В JPEG2000 каждый уровень разрешения вейвлет-разложения разбивается на зоны (precincts) и кодовые блоки (codeblocks). Каждый из кодовых блоков обрабатывается независимо друг от друга, в том числе и квантуется. Зоны являются одними из важнейших компонентов, позволяющих уменьшить размер используемой при кодировании рабочей памяти. Зоны также позволяют осуществлять произвольный доступ к компонентам изображения. Сжатые данные из зон объединяются в более крупные образования, называемые пакетами (packet).

Рис.10. Кодовые блоки и зоны на третьем уровне

разложения изображения

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

Рис.11. Обход кодовых блоков

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

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

Требование, заключающееся в необходимости организации вложенного битового потока, определило возможность использования кодирования битовых плоскостей индексов, полученных на этапе квантования. В стандарте JPEG2000 под битовой плоскостью понимается двумерный массив битов. В битовую плоскость включают все биты одинаковой величины рассматриваемой совокупности коэффициентов. Таким образом, к битовой плоскости можно отнести компонент, компонент тайла, кодовый блок или регион интереса изображения. В JPEG2000 каждая подполоса кодируется независимо от других подполос, кроме того, JPEG2000 использует подход, называемый EBCOT[Taubman] (embedded block coding with optimized truncation, вложенное блочное кодирование с оптимизированным усечением). Сравните с энтропийным кодированием в JPEG. При использовании данного подхода каждая подполоса разбивается на небольшие прямоугольники, называемые кодовыми блоками, каждый кодовый блок кодируется отдельно. Для достижения более высоких показателей производительности сжатия кодируются битовые плоскости кодовых блоков.

Рис.12.Кодирование блока в JPEG2000

Символы, представляющие коэффициенты после квантования, кодируются по одному биту за единицу времени, начиная со наиболее значимого бита (MSB) и заканчивая наименее значимым битом (LSB). Квантованные вейвлет-коэффициенты называются незначимыми (insignificant), если соответствующий индекс квантователя равен нулю. Пример представления битовых плоскостей приведен на иллюстрации 13 [Rabbani]. Два первых бита равны нулю, поэтому они считаются незначимыми.

Рис.13. Кодирование битовых плоскостей квантованных

вейвлет-коэффициентов

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

Вспомните отличия арифметического кодирования от метода Хаффмана?

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

В общем случае при кодировании распределение вероятностей каждого символа в двоичном представлении квантованного коэффициента ДВП зависит от всех ранее закодированных битов ближайших соседей коэффициента (порядок обхода на рис.10). В JPEG2000 вероятность двоичного символа определяется из контекста, формируемого как из текущего состояния значимости символа, так и из состояния значимости его ближайших восьми соседей из предыдущей и из текущей битовой плоскости, основанного на закодированной информации до обрабатываемой точки [Taubman, Rabbani]. В части 1стандарта JPEG2000 контекст определяется как функция, аргументом которой являются закодированные ранее коэффициенты и используемая для кодирования обрабатываемого элемента.

Рис.14. Формирование контекстов битов

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

Каждая битовая плоскость кодируется в три прохода [Д.С.Ватолин, Rabbani,Taubman]:

· кодирование старших бит (significance propagation pass).Выполняя этот проход, кодируются незначимые коэффициенты, у которых высокая вероятность стать значимыми. Данные в кодовых блоках сканируются в порядке, изображенном на рис.10, и кодируется каждый элемент, у которого есть хотя бы один значимый сосед (состояние основано на анализе уже закодированной информации). После того, как коэффициент закодирован, его состояние значимости обновляется. Поскольку кодовые блоки кодируются независимо друг от друга, то если обрабатываемый элемент расположен на границе кодового блока, то рассматриваются только те соседи, которые расположены внутри текущего кодового блока, а состояние значимости необработанных соседей обнуляется. Если коэффициент признан значимым, то его знак также кодируется. Значение знака кодируется с использованием пяти контекстов, определяемых из состояний значимости и знаков четырех соседей по вертикали и по горизонтали.

· уточняющий проход (refinement pass).В процессе выполнения этого прохода, кодируется коэффициент (magnitude bit), который уже стал значимым в предыдущей битовой плоскости. Для этого используется три контекста.

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

Отметим, что контекстная модель, используемая в JPEG2000, использует 18 кодовых контекстов. Контексты с 0 по 8 используются для кодирования состояний значимости в процессе выполнения первого и второго проходов, контекст 9 используется в процессе очищающего прохода, контексты 15-17 используются для кодирования знака коэффициента. Для кодирования каждого кодового блока используется собственные параметры MQ-кодера. По умолчанию, начальные значения контекстов инициализируются перед началом процесса кодирования и не меняются до завершения кодирования. Более того, итоговое кодовое слово может быть усечено на границах кодовых проходов для включения различного количества кодовых проходов из каждого кодового блока в итоговый кодовый поток. Кроме того, возможно осуществить параллельное декодирование кодовых потоков для каждого кодового блока.

Арифметическое кодирование битовых плоскостей называется кодером первого уровня. Кодер второго уровня отвечает за организацию сжатого битового потока для предоставления таких дополнительных возможностей, как произвольный доступ к фрагментам изображения, масштабируемость и использование регионов интереса (ROI encoding). Гибкость кодового потока достигается благодаря включению в поток следующих структур: тайлы, подполосы, уровни разрешения и кодовых блоков. Использование такой структуры позволяет выделить в изображении:

· цветовые каналы (через компоненты);

· пространственные регионы (через тайлы);

· частотные регионы (через подполосы и уровни разрешения);

· пространственно-частотные регионы (через кодовые блоки)

Тилинг позволяет получать доступ к данным, содержащимся в небольших компонентах изображения. Кодовые блоки могут быть результатом тилинга вейвлет-коэффициентов. Как было сказано выше, JPEG2000 позволяет осуществлять разбиение изображения на более крупные пространственно-частотные структуры – зоны (рис.9). Зона представляет собой множество соседних кодовых блоков из всех подполос на текущем уровне разрешения (разложения).

Кроме того, JPEG2000 выдает в результате работы кодера второго уровня сжатые данные из кодовых блоков в компонентах, называемых пакетами и слоями. Для каждой зоны сжатые данные из кодового блока сначала группируются в один или более пакетов (packet). Пакет представляет собой непрерывный сегмент в сжатом битовом потоке, который состоит из определенного количества кодовых проходов из каждого кодового блока в зоне [Rabbani].

Рис.15. Структура пакета

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

Затем пакеты из каждой зоне на каждом уровне разложения и из каждого тайла группируются в более крупные единицы, называемые слоями (layer). На иллюстрации показано, как формируется структура кодового потока [V. Sanchez & A. Basu].

Рис.16. Структура битового потока в JPEG2000

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

Рис.17. Результат кодирования с использованием технологии JPEG2000

Порядок, в котором пакеты появляются в битовом потоке, называется прогрессивным (progression order) и контролируется с помощью специальных маркеров. Для обрабатываемого тайла, необходимо задать четыре параметра для однозначного определения пакета: компонент (component), разрешение (resolution), слой (layer) и позиция (зона, precinct).

Базовая часть JPEG2000 предоставляет несколько вариантов появления пакетов:

· слой à разрешение à компонент à позиция (LRCP);

· разрешение àслой à компонент à позиция (RLCP);

· разрешение à позиция àкомпонент à слой (RPCL);

· позицияàкомпонентàразрешениеàслой (PCRL);

· компонентàпозицияàразрешениеàслой (CPRL)

В практической работе исследуем способ появления пакетов, начиная с разрешения (с использованием системы MATLAB). Однако, другие программные средства (например, библиотека OpenJPEG – http://www.openjpeg.org/index.php?menu=samples) предоставляют возможность исследовать другие варианты появления кодовых потоков. Например, введя в FAR Manager строку image_to_j2k -i Rome.ppm -o Rome.jp2 -q 30,35,50 -p LRCP -n 3, мы получим изображение Rome.jp2, которое сможем открыть в программе kdu_show. Обратное декодирование осуществляется с помощью команды j2k_to_image -i Rome.jp2 -o Rome.bmp -q 30,35,50 -p LRCP -n 3. Разобравшись с принципами кодирования/декодирования изображений, заполните таблицу для нескольких изображений и сделайте вывод о производительности JPEG2000:

Таблица 2. Результаты тестирования JPEG2000 в библиотеке OpenJPEG

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

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

Таким образом, если кодирование изображения осуществляется с учетом ROI, то выполняются следующие операции [Christopoulus, 2000]:

1. Выполняется вейвлет-преобразование

2. Если выбрана опция «кодирование с помощью ROI», то определяется маска (ROI-mask), задающая множество коэффициентов, которые необходимо обработать без потерь.

3. Коэффициенты, не попавшие в маску, обрабатываются с меньшей точностью.

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

Рис.18. Фильтр для создания маски ROI

Декодер осуществляет эти операции в обратном порядке.

Кодирование ROI может быть осуществлено с помощью обработки квантованных вейвлет-коэффициентов, соответствующих выделяемому региону, с более высокой точностью, чем вейвлет-коэффициентов остального изображения [Rabbani]. Коэффициенты ROI появляются в кодовом потоке раньше остальных коэффициентов. Существует два метода кодирования ROI: масштабирование (scaling based) и метод максимального сдвига (MAXSHIFT).

При использовании первого метода осуществляются следующие операции. Сначала определяется регион (или регионы) интереса в изображении (image domain) [Rabbani]. Затем создается двоичная маска ROI. Значения элементов в маске ROI равны единице, а значения всех остальных коэффициентов устанавливается равным нулю. Форма маски определяется размерами изображения и используемым банком фильтров. Перед энтропийным кодированием битовые плоскости коэффициентов маски сдвигаются вверх (или битовые плоскости коэффициентов остального изображения сдвигаются вниз) на желаемую величину, значение которой может отличаться в случае разных регионов. Информация о форме региона и коэффициент масштабирования включаются в кодовый поток. В общем случае, регион интереса может быть правильной формы, то есть прямоугольником или кругом, при этом регион можно изменять. При декодировании форма региона и коэффициент масштабирования декодируются, а затем происходит восстановление значений коэффициентов в регионах интереса (или остального изображения) до прежних значений.

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

При использовании данного метода маска генерируется путем анализа вейвлет-коэффициентов (wavelet domain), исследуются все вейвлет-коэффициенты остальной части изображения, при этом определяется коэффициент с максимальной величиной. Затем, определяется значение s в 2^s раз больше, чем наибольший коэффициент из неиспользуемых коэффициентов и ко всем битовым плоскостям применяется сдвиг вниз на s бит. Это обеспечивает, что даже небольшие коэффициенты региона больше, чем значения коэффициентов фона изображения.

Наличие регионов интереса передается декодеру, а в битовый поток передается значение коэффициента сдвига s. На иллюстрации показана идея метода MAXSHIFT [Rabbani].

Рис.19. Идея метода MAXSHIFT (из первой части стандарта JPEG2000)

Возможность кодирования областей интереса обеспечивает применение обратного фильтра вейвлет-преобразования c коэффициентами (5,3):

Для осуществления кодирования области интереса в редакторе COREL PHOTO-PAINT необходимо выделить фрагмент изображения (инструмент «Эллиптическое выделение»), а затем сохранить в JPEG2000.

Рис.20. Экспорт JPEG2000 с ROI

При высоких значениях коэффициента «сжатие» (квантование) качество восстановленного изображения будет низким, но размер файла составит 515 байт (файл à вернуть к предыдущей версии после выделения (ALT+нажать ПКМ на выделенный фрагмент)). Если же сохранять файл с низкими значениями коэффициента (как на иллюстрации 14), то размер файла составит 139 Кб. Для ROI также используем сжатие, так как для кодирования создается маска, состоящая из коэффициентов ДВП выделенной области.

Рис.21. Результаты сжатия с использованием ROI

Таблица 3. Сравнение результатов сжатия (исходный размер – 768 Кб, peppers.tiff)

Рис.22. Экспорт в форматах JPEG и JPEG2000

Опишем особенности формата файлов JPEG2000. Для практического использования возможностей разработанной технологии сжатия изображения (прежде всего базового алгоритма JPEG2000) на выходе из компрессора кроме сжатого битового потока должна передаваться информация, описывающая закодированное изображение [Houchin], а для этого необходимо было разработать формат файлов. Удивительно, но в случае JPEG2000 разработчики предложили использовать два файловых формата: JP2 и JPX. Формат JPX позволяет работать с изображениями различных типов: как с фотографиями, так и со сгенерированными изображениями. Файловый формат JP2 является более простым и предназначен для использования в тех приложениях, у которых существуют ограничения на обработку цветных изображений (или же такие приложения могут обрабатывать только полутоновые изображения). Формат JPX позволяет работать с более широким спектром изображений, а также создавать комбинации изображений или анимации. Кратко опишем структуру файлового формата.

В общем случае файл формата JPX и JP2 представляет собой двоичный контейнер, предоставляющий способ объединения сжатых данных и метаданных для описания распакованных данных (например, используемого цветового пространства). Однако, такой контейнер также определяет, каким образом приложения могут использовать данные, записанные в файле. Для обеспечения нормальной работы приложений контейнер должен обеспечивать быстрый доступ к отдельным элементам файла и позволять приложениям добавлять или изменять файл.

Файл формата JP2 является последовательностью структур, называемых боксами (box). В каждом боксе записан один элемент файла, такой как кодовый поток или множество метаданных. Во многих из таких боксов содержатся данные, записанные в файле. В других боксах, называемых супербоксами (superbox), может содержаться более чем один бокс. В таких элементах содержаться группы боксов. Такая структура позволяет:

· запоминать сложные изображения, использую многократное сжатие одного кадра;

· алгоритм Motion JPEG2000 позволяет запоминать последовательность отдельных кадров, например снимки фотокамеры или кадры фильмов

Кроме того, форматы JPX и JP2 определяют порядок кодирования цветовых данных изображения и вывода на экран при декодировании.

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

Мы рассмотрели базовые принципы технологии JPEG2000, на следующих занятиях мы рассмотрим способ программной реализации в MATLAB и исследуем области применения. В заключение еще раз отметим, что из-за следующих особенностей JPEG2000 более востребован, чем JPEG:

1) При использовании JPEG в изображение вносятся искажения и возникает эффект Гиббса (искажения на границах блоков, так как используем ДКП). Благодаря использованию ДВП при кодировании с помощью алгоритма сжатия JPEG2000 искажений не возникает.

2) JPEG2000 предусматривает возможность коррекции ошибок при сжатии, а также ряд дополнительных опций, например, кодирование областей интереса (ROI-encoding)

3) Возможность изменения количества бит на пиксель (битрейт) благодаря тому, что кроме кода передается R-D кривая. JPEG не предусматривает такой возможности

Список использованных материалов:

1) Гонсалес Р., Вудс.Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. Москва: Техносфера, 2006. – 616 с.

2) Д.С.Ватолин. Media Data Compression. Сжатие изображений. URL www.compression.ru/video/

3) Acharya, Tinku. JPEG2000 standard for image compression: concepts, algorithms and VLSI architectures// A John Wiley & Sonc, Inc., Publication. 2005.

4) Charilaos Christopoulos, Athanassios Skodras and Touradj Ebrahimi. The JPEG2000 still image coding system: an overview/IEEE Transactions on Consumer Electronics, Vol. 46, No. 4, pp. 1103-1127, November 2000IEEE, 2000

5) David Taubman, Erik Ordentlich, Marcelo Weinberger, Gadiel Seroussi. Embedded block coding in JPEG 2000/ Signal Processing: Image Communication 17 (2002) 49–72;

6) J. Scott Houchin, David W. Singer. File format technology in JPEG 2000 enables flexible use of still and motion sequences/Signal Processing: Image Communication 17 (2002) 131–144;

7) Michael W. Marcellin, Michael J. Gormish, Ali Bilgin1, Martin P. Boliek. An Overview of JPEG-2000/ IEEE Data Compression Conference,2000

8) Majid Rabbani, Rajan Joshi. An overview of the JPEG2000 still image compression standard/ Signal Processing: Image Communication 17 (2002) 3–48

9) Huakai Zhang, Jason Fritts. EBCOT coprocessing architecture for JPEG2000/ Dept. of Computer Science and Engineering, Washington University, 2003

10) Information technology – JPEG2000 image coding system, ISO/IEC International Standard 15444-1, ITU Recommendation T.800, 2000.

11) V. Sanchez & A. Basu. The JPEG2000 Image Compression Standard (slides)/URL: http://webdocs.cs.ualberta.ca/~anup/Courses/604/NOTES/slide_jpeg2000.pdf