Применение дискретных вейвлет преобразований в кодировании цифровых изображений

Известно, что в человеческом глазу выполняется операция многомасштабного представления изображений. Глаз более чувствителен к искажениям в низкочастотной области. Отсюда существует возможность улучшения визуального качества реконструированного изображения путем взвешивания СКО субполос в соответствии с чувствительностью глаза в различных частотных диапазонах. Веса для наиболее часто используемого фильтра 7/9 были вычислены А. Ватсоном.

Базовый вейвлет-кодер, описанный выше, использует общие

принципы кодера с преобразованием, то есть основан на эффектах декорреляции и перераспределения энергии. Математическая теория вейвлетпреобразования позволяет создавать совершенно новые и эффективные методы сжатия. Эти методы лежат в основе алгоритмов, описываемых в разделах 10.3 и 10.5. В данном разделе покажем главные идеи этих методов.

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

Пусть Y[n] - случайный вектор длинной N, определенный как



Здесь P есть случайная целая величина, равномерно распределенная от 0 до N-1, а Х-случайная величина, с равной вероятностью принимающая значения 1 и -1. Х и Р независимы. Вектор Y имеет нулевое среднее и ковариационную матрицу с элементами

Ковариационная матрица является циркулянтной, так что преобразованием Карунена-Лоэва для нее является просто преобразование Фурье. Однако преобразование Фурье вектора Y очень неэффективно с точки зрения кодирования. Энергия на частоте k будет равна Это означает, что энергия Y распределена по всей низкочастотной половине базиса Фурье и частично - по высокочастотной половине. Таким образом, преобразование Карунена-Лоэва «упаковало» энергию двух ненулевых коэффициентов в примерно 2/N коэффициентов. Конечно, было бы выгоднее кодировать Y в исходном виде, без всякого преобразования.

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

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

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

Решетчатое квантование коэффициентов гораздо ближе по своей сути к векторному квантованию, чем к кодированию с преобразованием.

Таблица. Сравнение кодеров по отношению сигнал/шум

Итак, развитие идей кодирования с преобразованием заключается в основном во введении некоторого оператора выбора. Информация о выборе должна быть передана декодеру, как дополнительная информация. Она может быть в виде нульдеревьев или в виде обобщенных классов энергии. Метод «обратного оценивания распределения», предложенный К. Рамчандраном, основан на другом подходе. Считается, что дополнительная информация является избыточной и может быть получена декодером непосредственно из данных. Использование данного метода приводит к хорошим показателям кодирования.

В табл представлены сравнения пикового отношения сигнал/шум для кодеров, которые будут обсуждаться далее. В качестве тестовых использовались полутоновые портретные изображения размером 512х512.

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

2.4 Решетчатое квантование

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

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

Пусть k=1 Скалярная кодовая книга из символов делится на четыре субкниги из каждая. Пусть R=2 (рис. 10.5). Субкниги строятся так, чтобы каждая из них представляла уровни реконструкции более грубого квантователя с (R-1) бит/отсчет. Четыре субкниги обозначены D₀, D₁, D₂ и D₃ Также обозначим и где S₀ и S₁ называются суперкнигами.

Как было сказано, ограничение на скорость не позволяет выбирать произвольный символ из символов. Однако существует возможность выбирать символы одной из суперкниг. Если известно, какая из суперкниг используется, то для каждого отсчета требуется один бит для обозначения субкниги и R-1 бит для обозначения кодового слова в ней. Выбор субкниги определяется состоянием автомата с конечным числом состояний, описываемого соответствующей решеткой.

Пример решетки с восемью состояниями приведен на рис. 10.6. Субкниги {D₀, D_1,D₂, D₃} используется для пометки ребер решетки, так что бит, обозначающий субкнигу, определяет следующее состояние решетки. Кодирование осуществляется путем посылки одного бита на отсчет для обозначения пути по решетке и 1 ? R бит для обозначения кодового слова. Может показаться, что мы вернулись к неоптимальному квантователю со скоростью R. К чему же все старания? Ответ заключается в том, что мы получили большее количество кодовых слов, так как существует некоторая свобода выбора символов из S₀ или S₁. Конечно, эта свобода неполная: решение по каждому символу принимается с учетом прошлого и будущего решений, то есть допустимых путей по решетке. Однако и эта гибкость приводит к эффективному кодированию. Доступность в каждый момент времени S₀ и S₁ означает, что уровни квантователя являются «скользящими» и настраиваются на данные, с учетом возможных путей по решетке.

Рис. Книги и суперкниги решетчатого вантования



Рис. Решетка РК с 8 состояниями

Перед тем как продолжить рассмотрение применения РК к кодированию вейвлет-коэффициентов отметим, что по своей эффективности и вычислительной сложности РК гораздо ближе к векторному, чем к скалярному квантованию. Почему бы не использовать стандартное векторное квантование? Ответ заключается в рекурсивной структуре РК и существовании простого алгоритма динамического программирования, известного как алгоритм Витерби для нахождения кодовых слов РК. Главное отличие заключается в том, что в случае векторного квантования кодовое слово размером 1 ? N не связано с кодовым словом размером N. Алгоритм РК автоматически решает проблему увеличения размерности, увеличивая длину решетки.

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

3. Представление графических данных в формате JPEG и JPEG2000

3.1 Формат JPEG

JPEG - один из популярных графических форматов, применяемый для хранения фотоизображений и подобных им изображений. Файлы, содержащие данные JPEG, обычно имеют расширения.jpeg.jfif.jpg.JPG, или.JPE. Однако из них.jpg самое популярное расширение на всех платформах. MIME-типом является image/jpeg. Алгоритм JPEG позволяет сжимать изображение как с потерями, так и без потерь (режим сжатия lossless JPEG). Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет. С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселами приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW. JPEG (как и другие методы искажающего сжатия) не подходит для сжатия изображений при многоступенчатой обработке, так как искажения в изображения будут вноситься каждый раз при сохранении промежуточных результатов обработки. JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, к сожалению, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.

При сжатии изображение преобразуется из цветового пространства RGB в YCbCr (YUV). Следует отметить, что стандарт JPEG (ISO/IEC 10918-1) никак не регламентирует выбор именно YCbCr, допуская и другие виды преобразования (например, с числом компонентов, отличным от трёх), и сжатие без преобразования (непосредственно в RGB), однако спецификация JFIF (JPEG File Interchange Format, предложенная в 1991 году специалистами компании C-Cube Microsystems, и ставшая в настоящее время стандартом де-факто) предполагает использование преобразования RGB->YCbCr. После преобразования RGB->YCbCr для каналов изображения Cb и Cr, отвечающих за цвет, может выполняться «прореживание» (subsampling [3]), которое заключается в том, что каждому блоку из 4 пикселов (2х2) яркостного канала Y ставятся в соответствие усреднённые значения Cb и Cr (схема прореживания «4:2:0»). При этом для каждого блока 2х2 вместо 12 значений (4 Y, 4 Cb и 4 Cr) используется всего 6 (4 Y и по одному усреднённому Cb и Cr). Если к качеству восстановленного после сжатия изображения предъявляются повышенные требования, прореживание может выполняться лишь в каком-то одном направлении - по вертикали (схема «4:4:0») или по горизонтали («4:2:2»), или не выполняться вовсе («4:4:4»). Стандарт допускает также прореживание с усреднением Cb и Cr не для блока 2х2, а для четырёх расположенных последовательно (по вертикали или по горизонтали) пикселов, то есть для блоков 1х4, 4х1 (схема «4:1:1»), а также 2х4 и 4х2. Допускается также использование различных типов прореживания для Cb и Cr, но на практике такие схемы применяются исключительно редко. Далее яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются на блоки 8х8 пикселов.

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

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

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

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

3.3 Вейвлет преобразования

В численном и функциональном анализе дискретные вейвлет-преобразования (ДВП) относятся к вейвлет-преобразованиям, в которых вейвлеты представлены дискретными сигналами (выборками). Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно для образования следующего уровня разложения. В итоге получается 2n?1 разность и 1 общая сумма. Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование можно выполнить за nlog2 (n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование - возможную альтернативу обычному быстрому преобразованию Фурье. При принятии условия случайности сигнала Х спектральную плотность его амплитуд Y вычисляют на основе алгоритма Ийетса: matrixY=matrix(±X), верно и обратное matrixX=matrix(±Y). Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.

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

3.4 Формат JPEG2000

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

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

Объединение в рамках единой технологии сжатия с потерями и без потерь. В дополнениях к 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. Сжатый поток данных упаковывается в пакеты. Именно благодаря гибкой и продуманной структуре пакетов возможно достижение целей разработки стандарта.

3.5 Алгоритм сжатия 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.6 Последовательность операций, используемых в алгоритме JPEG2000

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

(2.1)

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

(2.2)

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

(2.3)

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

(2.4)

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

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

+\- 3	0.01686411844287495	-0.09127176311424948
+\- 4	0.02674875741080976	0
Другие i	0	0

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

При упаковке	При распаковке
i	Низкочастоные коэффициенты	Высокочастотные коэфициенты	Низкочастотные коэфициенты	Высокочастотные коэфициенты
0	6/8	1	1	6/8
1	2/8	-1/2	1/2	-2/8
2	-1/8	0	0	-1/8

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

 (2.5)

(2.6)

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

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

(2.7)

(2.8)

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

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

Рисунок 2.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.1 - Уровни преобразования JPEG2000

Для корректного сохранения результатов под данные 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) показаны на рис. 2.2. Основная задача, которую мы решаем - повышение степени сжатия изображений. Когда практически достигнут предел сжатия изображения в целом и различные методы дают очень небольшой выигрыш, мы можем существенно (в разы) увеличить степень сжатия за счет изменения качества разных участков изображения.



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

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

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

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

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

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

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

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

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

4. Алгоритмы встраивания в JPEG2000

4.1 Задачи скрытия информации

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

Рисунок 4.1 - Блок-схема алгоритма кодирования JPEG2000

Из структуры, данной в рис. 3.1 рассматривают три позиции. Мы рассмотрим их качества для встраивания информации ниже. После внутри-компонентной трансформации данные изображения трансформируются в вейвлет-коэфициенты. Если мы модифицируем данные в этой части, то схемы будут эквивалентны многим существующим алгоритмам цифровой подписи, базирующихся на вейвлет-преобразовании, которые могут быть уязвимы к атакам другими вейвлет-кодеками. [7] Для цифровых водяных знаков количество информации обычно мало и могут быть применены многочисленное встраивание с основным методом расширения спектра. Встроенная информация, таким образом, может иметь достаточную устойчивость к компрессии с потерями другим кодеком. Тем не менее многочисленное встраивание не подходит приложениям скрытия данных в которых требуемое количество вносимых данных велико и требуется эффективное расходование уже ограниченной полосы пропускания.

Квантование важный шаг в компрессии изображения, который убирает определенную визуальную избыточность для эффективного кодирования. Квантование является первостепенным источником потери информации. Мы можем избежать потери встроенной информации встраивая информацию непосредственно в сами индексы квантования. Это решение работает для JPEG но не очень хорошо для JPEG2000. Следует отметить что основанные на вейвлет преобразованиях кодеры обычно усекают сжатый битовый поток что бы заполнить условленный битрейт. В Jpeg2000 Оптимизационная стратегия применимая к урезающему механизму активируется после того как все изображение было сжато. Если встраивать информацию в этом шаге, то мы не можем точно предсказать который индекс квантования или какая битовая плоскость индексов будет включена в финальный битовый поток. Встроенная информация не будет идеально восстановлена если не был выбран режим кодирования без потерь.

Если информация встраивается на втором уровне кодирования, то есть в кадры JPEG2000, можно гарантировать что вся встроенная информация будет принята без ошибок и в правильном порядке потому что избегаются два основных источника вносимых искажения: квантование и урезание. Тем не менее Мы сталкиваемся с трудностью в модифицировании кардов для встраивания информации так как поток может быть сильно сжат арифметическим кодированием [10]. Небрежная модификация может быть неудачной при развёртывании сжатого изображения.

4.2 Прогрессивное встраивание информации в изображения и его недостатки

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

Ярким примером является прогрессивное преобразование изображения, в котором области низких частот обрабатываются перед высокочастотными областями. В таком случае, нижние области необходимо тщательно сохранять с высоким битрейтом [11]. С другой стороны в некоторых частях встроенной информации могут наблюдаться потери, несущий контейнер может принимать достаточно информации если небольшие части передались успешно. Таким образом если встроенная информация является изображением меньшего размера мы можем передать ее встраиванием в индексы квантования. Это основная идея должна работать в большинстве вейвлет-кодеков.

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

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

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

Встраивание влечет за собой определенные договоренности между сторонами передачи. Правило пальца гласит: значение коэффициента, который сравнительно более важен, должен встраиваться более аккуратно. Вдобавок битовые коэффициенты нижней частотной области также должны лучше встраиваться чем те, которые находятся в области высоких. Перестановка может быть применена относительно встраиваемой информации до встраивания что бы усилить неопределённость. Приемная сторона должна иметь возможность перестроить ее обратно правильно что бы корректно восстановить скрытое изображение. Мы не должны встраивать никаких данных в самой нижней области частот что бы избежать видимых артефактов на несущем изображении [8].

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

Кроме того, если скрытая информация присутствует в изображении, то прослушивающий канал атакующий имеет больше шансов детектировать ее присутствие, определив что характеристики изображения отличаются от несущего изображения. Шифрование может быть неприменимо в таком случае так как мы не можем гарантировать того что скрытая информация передается без ошибок из за механизма урезания JPEG2000 и того факта что шифрованный битовый поток обычно не устойчив к любым видам ошибок. Лучшее что мы можем сделать, что бы увеличить уровень безопасности это переставить позиции вейвлет коэффициентов встроенного изображения упомянутого выше. Неясно как эта процедура остановит атакующего от детектирования встроенной информации. Наконец, требование встраивания изображения как скрытого серьезно ограничивает лимит использования данного алгоритма. Встраиваемая информация в основном должна быть двоичной, в любых формах таких как текст, шифрованные битовые потоки, сжатые\несжатые изображения, или другое, что бы достичь практичной сокрытой связи. Выходит что представленный выше метод не удовлетворяет нашим требованиям [7].

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

4.3 Скрытие информации с помощью lazy mode

Как было сказано выше, в соответствии с тем что мы передаем в основном двоичные данные секретно и без ошибок, необходимо встраивать информацию в контейнеры формата JPEG2000. Тем не менее, необходимо избегать модификации битового потока который подлежит энтропийному кодированию для корректного распознавания. В JPEG2000 существует опция кодирования lazy mode, в которой процедура арифметического кодирования полностью пропускается для повышения качества и точности значений. Если быть более точным, кроме наиболее значимых битовых плоскостей, значимость и точность в остальных битовых плоскостях кодируется без потерь. Благодаря опции lazy mode предлагается стегонографическая схема, которая решает все вышеперечисленные проблемы и достегает надежного сокрытия связи в JPEG2000. Этот выбор для предложенной схемы оправдан ниже. Заметно что при высоких битрейтах символы выработанные рамками значимости и точности имеют распределение близкое к равномерному то есть нет никакой существенной пользы от арифметического кодирования. Проходя MQ кодер можно уменьшить сложность и улутшить скорость выполнения без ухудшения качества кодирования. Для скрытия информации изображения которые будут переносить большой обьем информации кодируются при высоких битрейтах.

Поэтому необходимо встраивать информацию в сжатый битовый поток JPEG2000 с включенной опцией lazy mode. Кроме того, спрятанная информация также может быть формально распределена обычными методами шифрования. Выходит что данные в этом случае лучшие кандидаты для скрытия информации с низким шансом того, что их обнаружат [9].

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

4.4 Выбор каналов обработки для встраивания

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

Фиксирование значений в самых нижних битовых плоскостях

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

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

Битовые плоскости ниже самого значимого бита

Более сложный путь принять более значимый бит индекса квантования во внимание. В этом сценарии встраивания значение индекса квантование разрешается модифицировать для встраивания информации если он расположен на битовой плоскости которая расположена ниже самого значимого бита на несколько битовых плоскостей. Эта идея каким-то образом ассоциируется с теми схемами водяных знаков которые используют значение коэффициента носителя что бы масштабировать встроенный ЦВЗ. Если значения носителя велики, мы можем модифицировать с большим масштабом или более сильным ЦВЗ соответственно с маскировочным эффектом. Таким образом пропускная способность стегонографической схемы может быть улучшена без дальнейшего ухудшения визуального качества. В дополнении мы можем намеренно игнорировать некоторые битовые плоскости определённых коэффициентов для встраивания в соответствии с более высокими требованиями визуального качества или защитных качеств. Тем не менее сложность реализации увеличивается так как процесс встраивания и изъятия информации становится направленным вместо простого рассматривания всех битовых плоскостей как группы [11]. Таким образом, кодирование первого уровня должно быть вовлечено в процесс встраивания и распаковки. Кроме того мы сталкиваемся с такими проблемами как варьируемая длинна урезания информации и специальные шаблоны зарезервированные для устойчивости к ошибкам в более осторожной манере.