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

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

Введение

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

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

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

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

1. Обзор и анализ современных стегонографических систем

.1 Основные понятия и определения стеганографии

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

Позднее, на конференции «Information Hiding: First Information Workshop» в 1996 году было предложено использовать единую терминологию и обговорены основные термины. Стеганографическая система или стегосистема - совокупность средств и методов, которые используются для формирования скрытого канала передачи информации. При построении стегосистемы должны учитываться следующие положения: противник имеет полное представление о стеганографической системе и деталях ее реализации. Единственной информацией, которая остается неизвестной потенциальному противнику, является ключ, с помощью которого только его держатель может установить факт присутствия и содержание скрытого сообщения; если противник каким-то образом узнает о факте существования скрытого сообщения, это не должно позволить ему извлечь подобные сообщения в других данных до тех пор, пока ключ хранится в тайне; потенциальный противник должен быть лишен каких-либо технических и иных преимуществ в распознавании или раскрытии содержания тайных сообщений. [1] Обобщённая модель стегосистемы представлена на рисунке 1.1.

Рисунок 1.1 - Обобщенная модель стегосистемы

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

В стегосистеме с секретным ключом используется один ключ, который должен быть определен либо до начала обмена секретными сообщениями, либо передан по защищенному каналу. [3]

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

1.2 Цифровые водяные знаки

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

Цифровые водяные знаки могут применяться, в основном, для защиты от копирования и несанкционированного использования. В связи с бурным развитием технологий мультимедиа остро встал вопрос защиты авторских прав и интеллектуальной собственности, представленной в цифровом виде. Примерами могут являться фотографии, аудио и видеозаписи и т.д. Преимущества, которые дают представление и передача сообщений в цифровом виде, могут оказаться перечеркнутыми легкостью, с которой возможно их воровство или модификация. Поэтому разрабатываются различные меры защиты информации, организационного и технического характера. Один из наиболее эффективных технических средств защиты мультимедийной информации и заключается во встраивании в защищаемый объект невидимых меток - водяных знаков[2]. Разработки в этой области ведут крупнейшие фирмы во всем мире. Так как методы цифровых водяных знаков начали разрабатываться совершенно недавно, то здесь имеется много неясных проблем, требующих своего разрешения.

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

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

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

Наиболее существенное отличие постановки задачи скрытой передачи данных от постановки задачи встраивания ЦВЗ состоит в том, что в первом случае нарушитель должен обнаружить скрытое сообщение, тогда как во втором случае о его существовании все знают[5]. Более того, у нарушителя на законных основаниях может иметься устройство обнаружения ЦВЗ (например, в составе DVD-проигрывателя).

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

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

Рисунок 1.2 - Структурная схема типичной стегосистемы ЦВЗ

Прежде, чем осуществить вложение цифрового водяного знака в контейнер, водяной знак должен быть преобразован к некоторому подходящему виду. Например, если в качестве контейнера выступает изображение, то и последовательность ЦВЗ зачастую представляется как двумерный массив бит. Для того, чтобы повысить устойчивость к искажениям нередко выполняют его помехоустойчивое кодирование, либо применяют широкополосные сигналы. Первоначальную обработку скрытого сообщения выполняет показанный на рис. 1.2 прекодер. В качестве важнейшей предварительной обработки цифрового водяного знака (а также и контейнера) назовем вычисление его обобщенного преобразования Фурье. Это позволяет осуществить встраивание ЦВЗ в спектральной области, что значительно повышает его устойчивость к искажениям. Предварительная обработка часто выполняется с использованием ключа для повышения секретности встраивания. Далее водяной знак «вкладывается» в контейнер, например, путем модификации младших значащих бит коэффициентов. Этот процесс возможен благодаря особенностям системы восприятия человека. Хорошо известно, что изображения обладают большой психовизуальной избыточностью. Глаз человека подобен низкочастотному фильтру, пропускающему мелкие детали. Особенно незаметны искажения в высокочастотной области изображений. Эти особенности человеческого зрения используются, например, при разработке алгоритмов сжатия изображений и видео[1].

Процесс внедрения цифровых водяных знаков также должен учитывать свойства системы восприятия человека. Стеганография использует имеющуюся в сигналах психовизуальную избыточность, но другим, чем при сжатии данных образом. Приведем простой пример. Рассмотрим полутоновое изображение с 256 градациями серого, то есть с удельной скоростью кодирования 8 бит/пиксел. Хорошо известно, что глаз человека не способен заметить изменение младшего значащего бита. Еще в 1989 году был получен патент на способ скрытого вложения информации в изображение путем модификации младшего значащего бита. В данном случае детектор стего анализирует только значение этого бита для каждого пиксела, а глаз человека, напротив, воспринимает только старшие 7 бит. Данный метод прост в реализации и эффективен, но не удовлетворяет некоторым важным требованиям к ЦВЗ.

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

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

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

1.3 Атаки на стегосистемы

стеганографии дискретный вейвлет кодирование

Для осуществления той или иной угрозы нарушитель применяет атаки.

Наиболее простая атака - субъективная. Злоумышленник внимательно рассматривает изображение (слушает аудиозапись), пытаясь определить «на глаз», имеется ли в нем скрытое сообщение. Ясно, что подобная атака может быть проведена лишь против совершенно незащищенных стегосистем. Тем не менее, она, наверное, наиболее распространена на практике, по крайней мере, на начальном этапе вскрытия стегосистемы. Первичный анализ также может включать в себя следующие мероприятия:

Первичная сортировка стего по внешним признакам.

Выделение стего с известным алгоритмом встраивания.

Определение использованных стегоалгоритмов.

Проверка достаточности объема материала для стегоанализа.

Проверка возможности проведения анализа по частным случаям.

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

Выделение стего с известными алгоритмами встраивания, но неизвестными ключами и т.д.

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

атака с использованием только шифртекста;

атака с использованием открытого текста;

атака с использованием выбранного открытого текста;

адаптивная атака с использованием открытого текста;

атака с использованием выбранного шифртекста;

По аналогии с криптоанализом в стегоанализе можно выделить следующие типы атак.

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

Атака на основе известного встроенного сообщения. Этот тип атаки в большей степени характерен для систем защиты интеллектуальной собственности, когда в качестве водяного знака используется известный логотип фирмы. Задачей анализа является получение ключа. Если соответствующий скрытому сообщению заполненный контейнер неизвестен, то задача крайне трудно решаема.

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

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

Атака на основе выбранного заполненного контейнера. Этот тип атаки больше характерен для систем ЦВЗ. Стегоаналитик имеет детектор стего в виде «черного ящика» и несколько стего. Анализируя детектируемые скрытые сообщения, нарушитель пытается вскрыть ключ.

У злоумышленника может иметься возможность применить еще три атаки, не имеющие прямых аналогий в криптоанализе.

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

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

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

1.4 Атаки на стегосистемы водяных знаков

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

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

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

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

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

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

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

1.5 Математическая модель стегосистемы

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

Стегосистема может быть рассмотрена как система связи. Общая модель стегосистемы в виде блок-схемы представлена на рисунке 1.3

Рисунок 1.3 - модель стегосистемы как системы связи

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

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

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

Данный тип стеганосистем предполагает наличие безопасного (защищенного) канала обмена стеганоключами.

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

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

Стеганосистемы с открытым ключом

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

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

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

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

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

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

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

В этой модели кодер и декодер имеют доступ, кроме ключа, еще и к информации о канале (то есть о контейнере и о возможных атаках). В зависимости от положения переключателей А и Б выделяют четыре класса стеганосистем (при этом считается, что ключ всегда известен кодеру и декодеру) [3].

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

2 класс. Информация о канале известна только кодеру (ключ А замкнут, Б разомкнут). Особенностью схемы является то, что, будучи «слепой», она имеет ту же теоретическую пропускную способность, что и схема с наличием контейнера - оригинала в декодере. К недостаткам стеганосистем класса II можна отнести высокую сложность кодера (необходимость построения кодовой книги для каждого контейнера), а также отсутствие адаптации системы к возможным атакам. В последнее время предложен ряд практических подходов, которые устраняют эти недостатки. В частности, для снижения сложности кодера предлагается использовать структурированные кодовые книги, а декодер рассчитывать на случай наихудшей атаки.

класс. Дополнительная информация известна только декодеру (переключатель А разомкнут, Б замкнут). Декодер строится с учетом возможных атак. В результате получают устойчивые к геометрическим атакам системы. Один из методов достижения этой цели - использование так называемого опорного встроенного сообщения (аналог пилот-сигнала в радиосвязи). Опорное сообщение - небольшое количество бит, встроенных в инвариантные к преобразованиям коэффициенты сигнала. Например, можно выполнить встраивание в амплитудные коэффициенты преобразования Фурье, которые являются инвариантными к афинным (геометрическим) преобразованиям. Тогда опорное сообщение укажет, какое преобразование выполнил над контейнером нарушитель. Другим назначением пилотного сообщения является борьба с замираниями, по аналогии с радиосвязью. Замираниями в данном контексте можно считать изменение значений отсчетов сигнала при встраивании данных, атаках, добавлении негауссовского шума и т.д. В радиосвязи для борьбы с замираниями используется метод разнесенного приема (по частоте, во времени, пространстве, по коду), а в стеганографии используется разнесение встроенных сообщений в пространстве контейнера. Пилотное сообщение генерируется в декодере на основании ключа.

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

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

.1 Дискретное вейвлет-преобразование

В последнее десятилетие в мире наблюдается значительный интерес к сжатию изображений. Это вызвано стремительным развитием вычислительной техники, графических мониторов, цветных принтеров, а также цифровой техники связи. Изображение представляется в цифровом виде достаточно большим количеством бит. Так, цветная картинка размером 512х512 требует для своего хранения 768 кБайт. Если передавать видеопоследовательность таких картинок со скоростью 25 кадров в секунду, требуемая скорость составит 188.7 Мбит/с.

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

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

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

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

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

Рассмотрим основные проблемы, возникающие при сжатии изображения при помощи вейвлет-преобразования, и возможные пути их решения.

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

Пусть имеется некоторая непрерывная функция  Наш дискретный сигнал  представим как последовательность коэффициентов при масштабирующих функциях, по которым раскладывается :

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

Согласно концепции кратномасштабного анализа функция  декомпозируется на две функции  и :

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

Итак, концепция DTWS определена. Однако вычисления пока зависят от непрерывных функций . Поэтому покажем, как вычисления

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

Так что оказывается возможным итеративное вычисление коэффициентов  и  без непосредственного использования функций  По аналогии можно записать для произвольного j

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

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

Длина последовательности  вдвое больше длинны последовательности  или .

Подставляя получаем следующие ограничения на фильтры и :

Выражение (2.48) для временной области эквивалентно выражениям (2.26) и (2.36) для частотной. Равенства (2.49) и (2.50) уже появлялись ранее, но в менее общей форме ((2.24) и (2.34), соответственно).

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

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

2.2 Матричное описание DWT

Обозначим через вектор  последовательность конечной длины  для некоторого j. Этот вектор преобразуется в вектор , содержащий последовательности  и каждая из которых половинной длины. Преобразование может быть записано в виде матричного умножения , где матрица М - квадратная и состоит из нулей и элементов , умноженных на . В силу свойств  матрица М является ортонормированной, и обратная ей матрица равна транспонированной. В качестве иллюстрации рассмотрим следующий пример. Возьмем фильтр длиной L=4, последовательность длиной N=4, а в качестве начального значения о=0. Последовательность  получим  по формуле где t=L/(2-1)=4. Тогда операция матрично-векторного умножения будет представлена в виде

Обратное преобразование есть умножение  на обратную матрицу

Таким образом, выражение - это один шаг DWT. Послное DWT заключается в итеративном умножении верхней половины вектора  на квадратную матрицу , размер которой . Этот вектор может повторяться d раз, пока длина вектора не станет равна 1.

В четвертой и восьмой строках матрицы последовательность  циркулярно сдвинута: коэффициенты, выходящие за пределы матрицы справа, помещены в ту же строку слева. Это означает, что DWT есть точно один период длины N DTWS сигнала  получаемого путем бесконечного периодического продолжения . Так что DWT, будучи определенным таким образом, использует периодичность сигнала, как и в случае с DFT.

Матричное описание DWT кратко и ясно. Однако при обработке сигналов DWT чаще всего описывается посредством блок-диаграммы, аналогичнойдиаграмме системы анализа-синтеза

2.3 Описание DWT посредством блоков фильтров

Так как в данном случае имеется два фильтра  и , то банк фильтров - двухполосный и может быть изображен, как показано на рис. 2.5.

Фильтры F и E означают фильтрацию фильтрами  и , соответственно. В нижней ветви схемы выполняется низкочастотная фильтрация. В результате получается некоторая аппроксимация сигнала, лишенная деталей низкочастотная (НЧ) субполоса. В верхней части схемы выделяется высокочастотная (ВЧ) субполоса. Отметим, что при обработке сигналов константа всегда выносится из банка фильтров и сигнал домножается на 2

Итак, схема рис. 2.5 делит сигнал уровня j = 0 на два сигнала уровняj = 1. Далее, вейвлет-преобразование получается путем рекурсивного применения данной схемы к НЧ части. При осуществлении вейвлетпреобразования изображения каждая итерация алгоритма выполняется вначале к строкам, затем - к столбцам изображения (строится так называемая пирамида Маллата). В видеокодеках ADV6xx применена модифицированная пирамида Маллата, когда на каждой итерации не обязательно выполняется преобразование и по строкам, и по столбцам. Это сделано для более полного учета зрительного восприятия человека.

Рис. Схема двухполосного банка фильтров

Получившееся преобразование аналогично (2.51). Однако существуют некоторые различия. При фильтрации сигнала конечной длины мы сталкиваемся с проблемой его продолжения на границе. Матричное выполнение DWT эквивалентно периодическому продолжению сигнала на границе. Этот тип продолжения является обязательным для ортогональных фильтров. В случае применения биортогональных фильтров появляются некоторые другие возможности в силу симметричности их характеристик. Подробнее этот вопрос будет рассматриваться в главе 3. Схему, выполняющую DWT, можно представить еще и как показано на рис. 2.6. Здесь рекурсивная фильтрация и прореживание заменены одной операцией фильтрации и одной операцией прореживания на каждую субполосу. Определение итерационных фильтров и  легче всего дать в частотной области:

Рис. Эквивалентная схема вейвлет-преобразования

В пределе итерационный фильтр сходится к  в соответствии с:

Во временной области это означает, что график последовательности , построенной против , сходится к ф(х) при jБ стремящемся к бесконечности. На ри это изображено для фильтра Добеши длиной 4

Определение DWT может быть дано по аналогии с DFT. Предположим, что сигнал, подвергаемый преобразованию, имеет длину . Периодически продолжим его. Получим периодический сигнал  с периодом N. Тогда

 при

 при

Заметим, что в действительности суммы конечные, так как итерируемые фильтры имеют конечную длину. Ряд DTWS может быть записан аналогично выражению:

2.3 Базовый вейвлет-кодер изображения

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

Выбор оптимального базиса вейвлетов для кодирования изображения является трудной и вряд ли решаемой задачей. Известен ряд критериев построения «хороших» вейвлетов, среди которых наиболее важными являются: гладкость, точность аппроксимации, величина области определения, частотная избирательность фильтра. Тем не менее, наилучшая комбинация этих свойств неизвестна. Простейшим видом вейвлет-базиса для изображений является разделимый базис, получаемый сжатием и растяжением одномерных вейвлетов. Использование разделимого преобразования сводит проблему поиска эффективного базиса к одномерному случаю, и почти все известные на сегодняшний день кодеры используют его. Однако неразделимые базисы могут быть более эффективными, чем разделимые. Прототипами базисных функций для разделимого преобразования являются функции ф(х) ф(у), ф(х) (у), (ч) ф(у) и (х) (у) На каждом шаге преобразования выполняется два разбиения по частоте, а не одно. Предположим, имеем изображение размером N Х N. Сначала каждая из N строк изображения делится на низкочастотную и высокочастотную половины. Получается два изображения размерами NX2 / N. Далее, каждый столбец делится аналогичным образом. В результате получается четыре изображения размерами N/2xN/2 низкочастотное по горизонтали и вертикали, высокочастотное по горизонтали и вертикали, низкочастотное по горизонтали и высокочастотное по вертикали и высокочастотное по горизонтали и низкочастотное по вертикали. Первое из вышеназванных изображений делится аналогичным образом на следующем шаге преобразования, как показано на рис. 10.1. Известно, что для кодирования изображений хорошо подходят сплайновые вейвлеты. Эксперименты, проведенные рядом исследователей, показывают важность гладкости базисных функций для сжатия. Практически столь же большое значение имеет число нулевых моментов вейвлетов, которое тесно связано с гладкостью. Несмотря на это, некоторые исследователи считают, что важность гладкости для приложений цифровой обработки сигналов остается открытым вопросом. Наиболее широко на практике используют базисы, имеющие от одной до двух непрерывных производных. Увеличение гладкости не приводит к увеличению эффективности кодирования.

Рис. Два уровня вейвлет-преобразования изображения

Д. Вилласенор систематически протестировал все биортогональные блоки фильтров минимального порядка с длиной фильтров 36 ≤. В дополнение к вышеперечисленным критериям учитывалась также чувствительность аппроксимации с низким разрешением к сдвигам функции f(x). Наилучшим фильтром, найденным в этих экспериментах, оказался сплайновый фильтр 7/9. Этот фильтр наиболее часто используется в вейвлет-кодерах изображений. В частности, в видеокодеках семейства ADV6xx применяются именно эти фильтры.

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

Для биортогонального преобразования квадрат ошибки в области преобразования не равен квадрату ошибки в восстановленном изображении. В результате проблема минимизации ошибки становится намного более трудной, чем в ортогональном случае. Можно уменьшить ошибку в области изображения путем применения схемы взвешенного распределения бит, рассматриваемой в пункте 10.1.3. Тогда целый ряд фильтров по своей эффективности становится равным фильтру 7/9. Один из таких базисов - интерполирующий вейвлет Деслаури-Дубук порядка 4, преимуществом которого является то, что коэффициенты фильтра - рациональные числа, кратные степени 2. Оба этих вейвлета имеют 4 нулевых момента и две непрерывные производные.

Семейство многообещающих фильтров было разработано И. Баласингамом и Т. Рамстадом. Процедура разработки заключалась в комбинировании классических методов разработки фильтров с идеями теории вейвлетов. Получившиеся фильтры значительно превосходят популярные фильтры 7/9.

Осуществление преобразования на границах изображения

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

Квантование

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

На практике обычно применяется намного более простой равномерный квантователь с «мертвой» зоной. Как показано на рис. 10.2, интервалы квантования квантования имеют размер ∆, кроме центрального интервала (возле нуля), чей размер обычно выбирается ∆ 2.

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

Рис. Равномерный квантователь с «мертвой» зоной

Энтропийное кодирование

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

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

На практике зачастую вместо арифметического кодера используют кодер Хаффмана. Причина этого заключается в меньшем требующемся объеме вычислений, а также в том, что алгоритмы арифметического кодирования запатентованы. Так, только фирма IBM обладает более чем 90 патентами различных вариаций этого кодера. В силу этого в видеокодеках ADV6xx применен кодер Хаффмана.

Распределение бит

Итак, последним вопросом, на который необходимо ответить при создании алгоритма сжатия, является следующий: как точно квантовать каждую из субполос? На этот вопрос дает ответ алгоритм распределения бит. Общая идея заключается в определении такого числа бит  отводимых для кодирования j субполосы, при котором суммарное искажение  было бы минимальным с условием ограничения . Если известен точный вид функции  проблема решается с использованием условий Куна-Тукера. Одно из решений заключается в аппроксимации функции  функцией скорость-искажение для гауссовского источника. Однако при низких скоростях кодирования эта аппроксимация будет неточна. Лучшие результаты могут быть получены путем измерения  в диапазоне изменения R и решения проблемы ограниченной оптимизации с применением метода целочисленного программирования. Данная задача была решена И. Шохамом и А. Гершо.

В случае применения биортогональных вейвлетов возникает дополнительная трудность, заключающаяся в неравенстве среднеквадратической ошибки (СКО) области изображения и области трансформанты. П. Мулином был сформулирован алгоритм кратномасштабного ослабления, который дает приближенное решение этой проблемы. Данный алгоритм значительно эффективнее обычной минимизации СКО в области трансформанты. Более простым методом является аппроксимация СКО изображения взвешенной суммой СКО субполос. Вес  для субполосы j находится сле-дующим образом: устанавливаем один коэффициент этой полосы в 1, а остальные - в 0. Затем выполняем обратное преобразование. Вес  равен сумме квадратов получившихся значений. Распределение бит производится с целью минимизации взвешенной суммы  Процедура взвешивания дает хорошие результаты, когда используются неортогональные вейвлеты, например вейвлеты Деслари-Дубук, ставшие популярными благодаря лифтинговой схеме. Для фильтра 7/9 веса  близки к 1, поэтому взвешивание в данном случае нецелесообразно.

Меры искажения, взвешенные с учетом восприятия человеком

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

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

При сохранении изображения в 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. Устойчивость алгоритма к ошибкам канала связи при передаче сжатого изображения. Здесь видна нацеленность нового стандарта на мобильные приложения, на передачу изображений по радиоканалу.

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

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

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

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

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

Рассмотрим основные блоки, входящие в структурную схему алгоритма сжатия 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.      Поддержка кодирования отдельных областей с лучшим качеством. Известно, что отдельные области изображения критичны для восприятия человеком (например, глаза на фотографии), в то время как качеством других можно пожертвовать (например, задний план). При «ручной» оптимизации увеличение степени сжатия проводится до тех пор, пока не будет потеряно качество в какой-то важной части изображения. Сейчас появляется возможность задать качество в критичных областях, сжав остальные области сильнее, т.е. мы получаем еще большую окончательную степень сжатия при субъективно равном качестве изображения.

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

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

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

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

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

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

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

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

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

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

. Не используется явно дискретизация компонент 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 Коэффициенты для сжатия с потерями

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

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

                                        (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].

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

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

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

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

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

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

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

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

.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, в которых только несколько битовых плоскостей модифицируются для устранения видимых искажений.

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

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

Инверсное встраивание

Лучший путь выбора подходящих значений улучшений для стеганографии это рассматривать важность этих значений для общего качества сжатого изображения. Кодирование второго этапа достигает масштабируемости через множественные слои качества. Каждый шаг кодирования привязан к одному из слоев или обрезан в соответствии с заданным соотношением сигнал\шум, которое рассчитывается на первом этапе кодирования и проходит на второй этап для организации потока. Кодирование проходящее с большим значением сигнал/шум включается ранее в нижние слои, в то время как кодирование с меньшим соотношением сигнал/шум включается в слой на позднем этапе. Наша задача спрятать как можно больше информации с минимальным влиянием на качество изображения. Очевидно, что процесс встраивания должен функционировать в противоположном порядке кодирования второго этапа выбирая менее значимые шаги ранее для модифицирования. Таким образом, предлагается идея обратного встраивания с учетом важности шагов для общего качества изображения. После второго этапа кодирования определяются шаги, которые будут включены в кодовый поток, еще одна процедура встраивает информацию в обратном порядке начиная с последнего включенного обработанного шага. С одной стороны модифицирование этих незначительных шагов может быть приравнено к отбрасыванию их что не сильно повлияет на качество изображения сравнимо с теми шагами что были включены ранее. С другой стороны длинна этих массивов может быть больше и в них соответственно можно встроить больше информации. Процедура встраивания может проводится до тех пор, пока не будут заметны искажения в несущем изображении [8]. Протокол остановки может быть необходим для сигнализации декодеру об окончании извлечения информации.

4.5 Проблемы инверсного встраивания

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

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

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

Если использовать MSE как количественную оценку качества, то самый точный путь для вычисления вносимого искажения в домен изображения. Тем не менее сложность этого подхода очень высока так как нам необходимо расширять битовый поток несколько раз после каждого встраивания на каждом этапе. Более практичный путь для измерения вносимого искажения в вейвлет домен в то время когда мы генерируем битовый поток. В JPEG2000 общее искажение сжатого изображения и оригинального изображения в понятии MSE может быть определено прямо в вейвлет домене. Для каждого кодового блока В встроенный битовый поток усекается до значения где n степень обрезания.

Вклад В в усиление искажения в восстановленном изображении определяется как  Общее искажение D может быть вычислено по формуле:

,                           (4.1)

где si[k] определяет выборки подобластей в кодовом блоке Bi, [k] определяет представление индексов квантования выборки связанной с точкой урезания  и определяет норму L2 базисной вейвлет функции для подобласти  к которой принадлежит кодовый блок. Это приближение верно для ортогональных вейвлет базисов и ошибок квантования в каждом из образцов, которые не коррелируют. Хотя ни одно предложение не идеально, решение приемлемо для случая с компрессией.

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

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

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

Приведём краткий пример. Если оригинальное значение 44 (101100) и значение после встраивания 55 (110010). Каждое позитивное изменение и негативное случилось дважды. Сумма позитивных изменений будет 1x 2⁴ +1 x 2¹ = 18 и сумма негативных изменений будет 1x 2³ + 1x 2² = 12 то есть разница будет 6. Этот путь расчета прямолинеен, и выгоды в его адаптации к структуре битовых плоскостей. Тем не менее, точное определение искажения приходит вместе с несколькими недостатками которые увеличивают сложность реализации. В первую очередь процесс встраивания информации происходит на втором этапе обработки. На этом этапе все, что содержит кодер это битовый поток. Он ничего более не знает кроме позиции битовых плоскостей и кодовых блоков, к которым применяется трансформация. Когда в процедуре происходит проскальзывание бита мы можем не знать какой именно коэффициент был задействован. Эта проблема может быть решена Передачей большей информации из первого этапа во второй. Так как только встраивание происходит только в несжатые области, кодер первого этапа должен послать дополнительную информацию, в кодер второго этапа показывающую соответствие между битами и их коэффициентами

Для блока 64 на 64 дополнительная информация может быть длинной в 64 на 64 для каждого этапа, где 1 обозначает, что шаг несет в себе встроенную информацию, а 0 обозначает нулевую информацию. Декодер должен иметь возможность сканировать в таком же порядке определять какой коэффициент был подвержен проскальзыванию, что бы измерить искажение. Тем не менее, существуют и другие проблемы. Нам нужно хранить значение искажения для каждого коэффициента в каждом кодовом блоке что увеличивает потребление памяти значительно и противоречит требованию эффективного расходования памяти на втором этапе кодирования. Далее представляется два метода грубой оценки которые просто оперируют на уровне битовых плоскостей и нам необходимо проверить их точность сравнивая их с таким же приблизительным искажением. Первый метод измерения искажения суммированием MSE битового проскальзывания в каждой итоговой плоскости. Если проскальзывание случается то оно добавляется к общему искажению без учета коэффициентов. Дополнительное искажение D с одним проскальзыванием описывается формуле:

                                      (4.2)

где  норма L-2 базисной функции вейвлет коэффициента,  размер шага квантования, ассоциируемый с подмножеством b и p это позиция битовой плоскости.

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

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

4.6 Стегоанализ предложенной схемы скрытия данных

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

Первый шаг, который может предпринять прослушивающий, это анализ структуры битового потока. Минус предложенной схемы в том что процесс встраивания оперирует специальным режимом Jpeg2000, режимом lazy mode. Атакующий может подозревать существование определенной скрытой информации в битовом потоке JPEG2000, если он сжат в lazy mode варианте. Эта проблема зависит от того как популярен будет режим lazy mode. Эта опция очень полезна для компрессии изображения с высоким битрейтом. Сложность может быть устранена введением lazy mode кодированием, потому что вычислительно дорогие MQ этапы кодирования обходятся, в то время как эффективность кодирования не будет сильно затронута, тем более при кодировании с высоким битрейтом, который является возможным вариантом для скрытия информации. Кодирование ROI единственный случай, в котором lazy mode не может быть применен. Таким образом, нет смысла отбрасывать lazy mode при применении в приложениях [7].

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

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

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

5. Реализация алгоритма встраивания информации в изображения стандарта JPEG2000

.1 Описание алгоритма

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

.

Данная формула представленна для изображения в градациях серого, тесть значение цвета пикселя изменяется в пределах от 0 до 255. Необходимым минимум PSNR является значение в 40дБ. Исходя из этого можно приблезительно оценить пропускную способность стегоканала по следующей формуле:

.

Полагая что шум обработки =0 можно сказать что при заданном PSNR в 40 дБ пропускная способность С будет равна 0.0022 бита на пиксел. Однако для встраивания цифрового водяного знака допускаются визуальные искажения исходя из особенностей человеческого восприятия соответственно пропускная способность будет варьироваться в зависимости от самого ЦВЗ.

В данной программной реализации рассматривается встраивание информации на этапе вейвлет-преобразования, а конкретнее - манипуляции с вейвлет-коэфициентами. Рассмотрим двухуровневую декомпозицию изображения lena:

Рисунок 5.1 - Изображение lena и двухуровневая декомпозиция вейвлет-коэфициентов

На данной схеме: {0,0} - нижняя частотная область второго порядка, {0,1} - верхняя и нижняя частотная область второго порядка, {0,2} - нижняя и верхняя частотная область второго порядка, {0,3} - верхняя частотная область второго порядка, {1} - верхняя и нижняя частотная область первого порядка, {2} - нижняя и верхняя частотная область первого порядка, {3} - верхняя частотная область первого порядка. Как видно области второго порядка содержат более значимую информацию нежели области первого порядка. Тогда целесообразным будет проводить встраивание в области первого порядка дабы избежать значительных визуальных искажений изображения-хоста.

Область{3} вероятнее всего будет более всех подвержена компрессии и внешним искажениям, таким образом встраивание будет производится в области {1} и{2} соответственно. Так как значения области {1} немного больше значений в области {2} то целесообразным будет оперировать относительными энергиями данных значений. Взяв значения вейвлет-коэффициентов по модулю и поделив их на максимальное значение из данной области, получим матрицу со значениями от 0 до 1.

Следующим шагом будет формирование матрицы двоичных значений по которым будет производится встраивание информации. Для получения этой матрицы необходимо отнять полученные значения энергий области {1} от значений области {2}. Получив матрицу двоичных значений необходимо выполнить побитовую операцию XOR между полученной матрицей и матрицей двоичных данных ЦВЗ (в данном случае значения монохромного изображения). Результатом данной операции станет промежуточная матрица двоичных значений для дальнейшего преобразования. Схема встраивания такова, что если значения промежуточной матрицы и матрицы исходного изображения отличаются то мы меняем вейвлет-коэфициенты областей {1} и {2} с учетом знака и отношения максимумов.

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

Рисунок 5.2 - Схема встраивания ЦВЗ

Рисунок 5.3 - Схема детектирования ЦВЗ

Данные области представляют собой четверть исходного изображения. Для тестового изображения 512х512 размеры областей {1} и {2} будут по 256х256 вейвлет-коэфициентов. Таким образом максимальный размер монохромного встраиваемого изображения будет 256х256 пикселей каждый из которых принимает двоичные значения. Для улучшения устойчивости встроенной информации целесообразно встраивать ее в области {0,1} {0,2}, но это повлечет за собой большие искажения. Далее будут рассмотрены результаты действия алгоритма с различными входными и выходными параметрами.

5.2 Визуальные результаты

Сравним результаты работы алгоритма с различными параметрами.

Рисунок 5.2 - Стегоконтейнер и ЦВЗ(256х256) без компрессии

На рис 5.2 представлено изображение со встроенной информацией и сама встроенная информация при встраивании в области первого порядка без компрессии. Как видно вносимые искажения в изображение-хост незначительны хотя и заметны (уровень PSNR 33дБ) в то время как встроенная информация значительно зашумлена хотя и распознаваема. С увеличением уровня компрессии зашумленность возрастает и вместо встроенной информации можно увидеть контуры изображения-хоста.

Рисунок 5.3 - ЦВЗ(256х256) при уровнях компрессии 0, 0. 3,0. 5,0. 7,1

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

Рисунок 5.4 - Стегоконтейнер и ЦВЗ(128х128) без компрессии

На рис 5.4 находится изображение с встроенной информацией в областях {0,1} и {0,2}, размер встроенного изображения 128х128 пикселей, PSNR=29дБ. Уровень искажений изображения-хоста стал ощутимо заметен в то время как искажения встроенного изображения субъективно уменьшились по сравнению с предыдущим случаем.

Рисунок 5.5 - ЦВЗ(128х128) при уровнях компрессии 0, 0. 3,0. 5,0. 7,1

Как видно из рис 5.5 устойчивость к компрессии не сильно отличается от предыдущего случая.

Следующим шагом будет встраивание информации на втором уровне вейвлет-декомпозиции но изображения вчетверо меньшего области встраивания. Для области 256х256 возьмем ЦВЗ размера 64х64.

Рисунок 5.6 - Стегоконтейнер и ЦВЗ(64х64) без компрессии

Для рисунка 5.6 размеры ЦВЗ составляют 64х64 при размерах области, в которую производится встраивание 256х256, PSNR=44дБ.

Рисунок 5.7 - ЦВЗ(64х64) при уровнях компрессии 0, 0. 3,0. 5,0. 7,1

Как видно из рисунков 5. 3,5. 5,5.7 устойчивость к компрессии остается на прежнем уровне.

Из данных результатов можно увидеть что для обеспечения уровня в больше чем 40 дБ можно встраивать около 4 килобит данных (изображение 64х64), но для улучшения качества ЦВЗ на выходе необходимо выполнять помехоустойчивое кодирование с исправлением ошибок.

Выводы

В данной дипломной работе было произведено исследование алгоритмов встраивания скрытой информации в изображения стандарта JPEG2000.

Во второй части работы были рассмотрены основные методы обработки изображений с помощью дискретных вейвлет-преобразований и схемы квантования и кодирования данных.

В третьей части работы были рассмотрены алгоритмы кодирования информации, которые применяются в форматах изображения JPEG и JPEG2000. Более подробно внимание было остановлено на формате JPEG2000 и его спецификациях, таких как ROI.

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

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

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

В шестой части работы рассматривались вопросы безопасности жизнедеятельности человека Изучение условий труда выполнялось на основе анализа системы «Человек-Машина-Среда» в лаборатории информационных систем. При выполнении раздела «Охрана труда и безопасность в чрезвычайных ситуациях» были выявлены ОВПФ и рассмотрено их влияние на человека. Опасный фактор - возможность прохождения через тело человека электрического тока. Разработаны организационные и технические мероприятия, уменьшающие или исключающие влияние ОВПФ на человека, создания комфортных и безопасных условий работы. В качестве защитных мер предлагается зануление системы на автомат с током в пределах 100-140 Ампер а так же повторное заземление корпусов техники. Определен класс пожаро - взрывоопасности помещения - П-IIа, разработаны организационные и технические мероприятия, направленные на профилактику пожара, разработан план эвакуации при пожаре, рассмотрены вопросы промышленной санитарии и гигиены труда, определена наиболее вероятная чрезвычайная ситуация(пожар).

Перечень ссылок

1. Конахович Г.Ф. Пузыренко А.Ю. Компьютерная стеганография. теория и практика. - К.; «МК-Пресс», 2006.-288 с.

. Артёхин Б.В. Стеганография Журнал «Защита информации. Конфидент». 1996. - №4, - С. 47-50.

. Барсуков B.C., Романцов А.П. Компьютерная стеганография: вчера, сегодня, завтра. Технологии информационной безопасности XXI века. - материалы Internet-pecypca «Специальная техника». - Режим доступа: http://st.ess.ru/.

. Грибуиин В.Г., Оков И.Н., Туринцев И.В. Цифровая стеганография. - М.: Солон-Пресс, 2002. - 272 с

. Хорошко B.O. Азаров О.Д., Шелест M.C. Яремчук Ю.О. Основы компьютерної' стеганографії: Навчальний посібник для студентів та аспірантів. - Вінниця: ВДТУ, 2003. - 143 с.

6. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования-ВУС, 1999-204 с.

7. W. Bender, D. Gruhl, N. Morimoto and A. Lu, «Techniques for data hiding,» IBM System Journal, vol. 35, no. 3, pp. 313-336, 1996.

8. F. Hartung and M. Kutter, «Multimedia watermarking techniques,» Proc IEEE, vol. 87, no. 2, pp. 1079-1107, 1999.

9. M. Holliman, N. Memon, B.-L. Yeo and M. Yeung, «Adaptive public watermarking of DCT-based compressed images,» in Proc. SPIE Photonics West, Security and Watermarking of Multimedia Contents, San Jose, CA, Jan. 1998.

10. C.I. Podilchuk and W. Zeng, «Watermarking of the JPEG bit-stream,» in Proc. International Conference Image Science, Systems and Technology, Las Vegas, NV, June 1997.

. M.D. Adams, «The JPEG-2000 still image compression standard,» ISO/IEC JTC 1/SC 29/WG 1, Tech. Rep., Sep. 2001.

12. Po-Chyi Su and C.-C. Jay Kuo Steganography in JPEG2000 Compressed Images IEEE Transactions on Consumer Electronics, Vol. 49, No. 4, NOVEMBER 2003

. Методичні вказівки до виконання розділу «Охорона праці та безпека в надзвичайних ситуаціях» в атестаційних роботах ОКР «магістр» /Упоряд.: Б.В. Дзюндзюк, В.А. Айвазов, Т.Є. Стиценко - Харків: ХНУРЕ, 2011.

14. Охрана труда в електроустановках / Под ред. Князевского Б.А.-М..Энергия, 1982.-319 с.

. Сибаров Ю.Г. и др. Охрана труда в вычислительных центрах.-М/ Машиностроение, 1985. - 185 с.

. Долин П.А. Справочник по технике безопасности. - 5-е изд., перераб. и доп - М.: Энергоиздат, 1985. - 800 с.

. Дзюндзюк Б.В., Іванов В.Г., Охрана труда. Сборник задач.-Х.: НВП центр ХНУРЕ, 2006.-242 с.

. ДСН 3.3.6.037-99. Санітарні норми виробничого шуму, ультразвуку та інфразвуку.

. ГОСТ 12.1.004-91. ССБТ. Пожарная безопасность. Общие требования.

. ДСН 3.3.6.042-99. Санітарні норми мікроклімату виробничих приміщень.

. ГОСТ 12.1.009-76.ССБТ. Электробезопасность. Термины и определения.

. ГОСТ 12,1.019-79 ССБТ. Электробезопасность. Общие требования.

. ГОСТ 12.2.032-78. ССБТ. Рабочее место при выполнении работ сидя. Общие эргономические требования.

. ДСан ПиН 3.3.2-007-98. Государственные санитарные правила и нормы работы с визуальными дисплейными терминалами электронно-вычислительных машин.

25. ДБН В.2.5-13-98. Інженерне обладнання будинків і споруд. Пожежна автоматика будинків і споруд.

26. Закон України «Про цивільну оборону».

27. НПАОП 40.1-1.21-98. Правила безпечної експлуатації електроустановок споживачів. (ПУЭ-85).

28. ГОСТ 12.4.113-82 ССБТ. Работы учебные лабораторные. Общие требования безопасности.