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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:15, 18 ноября 2016.

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


Принцип работы

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

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

Примеры стохастических алгоритмов

Стохастическая модуляция

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

Введение

Вначале необходимо заметить, что если — нормально-распределенная последовательность Гаусса и, если - произвольная переменная, равномерно-распределенная между {-1, 1}, то — тоже является . Другими словами, гауссова последовательность с произвольными знаками остается гауссовой. Это утверждение является верным для любой произвольной переменной с распределением, симметричным относительно нуля.

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

Паритетная функция

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

для

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

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

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

Процесс встраивания

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

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

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

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

Извлечение сообщения

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

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

Чтобы получить ожидаемую емкость , которая измеряется количеством битов на пиксель (bpp), нужно вычесть вероятность появления 0 в последовательности стегошума из максимального соотношения 1 бит на пиксель:

где – статистическая функция ошибки .

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

где – обратная функция ошибки.

Усовершенствованная стохастическая модуляция

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

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

где .

Если обозначить значения пикселей стегоизображения как , процесс встраивания можно выразить формулой

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

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

для всех и

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

- целое

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

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

Улучшение в емкости можно увидеть из графика на рис. 1 (штриховая линия – один шум, сплошная - два):

Рис. 1. Зависимость емкости от отклонения

См. также

Литература

  1. Digital image steganography using stochastic modulation / J. Fridrich, M. Goljan


См. также