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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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