6.1. Аддитивные алгоритмы.

6.1.1. Обзор алгоритмов на основе линейного встраивания данных.

В аддитивных методах внедрения ЦВЗ представляет собой последовательность чисел w_i длины N, которая внедряется в выбранное подмножество отсчетов исходного изображения f. Основное и наиболее часто используемое выражение для встраивания информации в этом случае.

(6.1).

Где - весовой коэффициент, а — модифицированный пиксел изображения.

Другой способ встраивания водяного знака был предложен И.Коксом [11]:

(6.2).

Или, при использовании логарифмов коэффициентов.

(6.3).

При встраивании в соответствии с (6.1) ЦВЗ в декодере находится следующим образом:

. (6.4).

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

. (6.5).

Эта величина варьируется в интервале [-1; 1]. Значения, близкие к единице, свидетельствуют о том, что извлеченная последовательность с большой вероятностью может соответствовать встроенному ЦВЗ. Следовательно, в этом случае делается заключение, что анализируемое изображение содержит водяной знак.

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

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

Обычно легче первоначально сгенерировать равномерно распределенную последовательность. Известен алгоритм преобразования такой последовательности в гауссовскую (алгоритм Бокса-Мюллера). Псевдокод этого алгоритма приведен ниже. Здесь ranf() — датчик равномерно распределенных случайных чисел, mean, deviation — среднее значение и СКО последовательности.

Алгоритм 6.1. Полярная форма алгоритма Бокса-Мюллера.

Double x1, x2, w;

Do {

 x1 = 2.0 * ranf() — 1.0;

 x2 = 2.0 * ranf() — 1.0;

 w = x1 * x1 + x2 * x2;

} while (w >= 1.0);

W = sqrt((-2.0 * log(w)) / w);

Double y1 = mean + x1 * w * deviation;

Double y2 = mean + x2 * w * deviation;

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

Рядом авторов [22, 4, 34] были предложены слепые методы извлечения ЦВЗ, вычисляющие корреляцию последовательности w со всеми N коэффициентами полученного изображения f*:

. (6.6).

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

. (6.7).

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

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

Наиболее ярким представителем алгоритмов внедрения ЦВЗ на основе использования широкополосных сигналов является алгоритм Кокса, представленный ниже.

А17 (Cox, [8-10]).

ЦВЗ представляет собой последовательность псевдослучайных чисел, распределенных по гауссовскому закону, длиной 1000 чисел.

Для модификации отбираются 1000 самых больших коэффициентов дискретного косинусного преобразования (ДКП).

Встраивание информации выполняется в соответствии с выражением (6.2), а извлечение ЦВЗ в соответствии с выражением (6.4).

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

Вместе с тем алгоритм уязвим для атак, предложенных Гравером в [1,2,3]. Кроме того, операция вычисления двумерного ДКП трудоемка.

А18 (Barni, [4]).

ЦВЗ представляет собой последовательность бинарных псевдослучайных чисел . Длина последовательности определяется размерами исходного изображения M и N, где i= 0,…,.

При встраивании информации вначале выполняется четырехуровневое (l = 4) вейвлет-преобразование с использованием фильтров Добеши-6. Для внедрения водяного знака используются только детальные поддиапазоны первого подуровня разложения. При этом в качестве кандидатов для модификации выбираются все коэффициенты детальных поддиапазонов (LH, HL, HH), которые изменяются с учетом локальной чувствительности к шумам:

, (6.8).

Где.

.

Множитель в этом выражении определяется поддиапазоном и уровнем разрешения:

, (6.9).

Второй множитель определяется локальной яркостью:

, (6.10).

И последний множитель определяется локальной дисперсией или степенью текстурированности.

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

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

А19 (G.Nicchiotti [7, 21]).

ЦВЗ представляет собой массив псевдослучайных чисел, распределенных по гауссовскому закону, размером 32*32 = 1024 числа.

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

Для внедрения ЦВЗ отбираются все коэффициенты LL поддиапазона.

Встраивание информации в эти коэффициенты выполняется в соотвествии с выражением.

, (6.11).

Где — среднее значение выборки коэффициентов.

Извлечение информации выполняется по (6.4).

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

А20 (R.Dugad [35]).

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

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

Выражение для встраивания информации имеет вид.

. (6.12).

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

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

А21 (J.Kim [12]).

ЦВЗ представляет собой последовательность псевдослучайных действительных чисел, распределенных по гауссовскому закону, длиной 1000 чисел.

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

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

Встраивание информации выполняется в соответствии с (6.2), но при этом коэффициент масштаба для каждого уровня — свой. Для уровня LL коэффициент масштаба равен 0.04, так как значения коэффициентов этого уровня достаточно велики. Для 3, 2 и 1 уровней декомпозиции используются соответственно коэффициенты 0.1, 0.2 и 0.4.

При извлечении ЦВЗ по (6.4) также учитывается адаптивный коэффициент масштаба..

Как отмечается в [12], данный алгоритм является робастным ко многим атакам.

А22 (Y.Kim [13]).

ЦВЗ представляет собой последовательность псевдослучайных действительных чисел, распределенных по гауссовскому закону. Длина последовательности для LL поддиапазона 500 чисел, для остающихся поддиапазонов 4500 чисел.

Предлагается использовать трехуровневую декомпозицию изображения. Водяной знак добавляется к наибольшим коэффициентам в каждом из поддиапазонов за исключением поддиапазонов наивысшего уровня разрешения (HL₁, LH₁, HH₁). Количество элементов водяного знака w_i в каждом из поддиапазонов пропорционально энергии этого поддиапазона. Энергия e_s определяется по формуле.

(6.14).

Где М, N — размеры поддиапазона.

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

(6.15).

Для LL поддиапазона используется сравнительно малый коэффициент , составляющий приблизительно 1/100 от используемого для других поддиапазонов. Визуальный весовой коэффициент w_s определяется для каждого поддиапазона и вводится в формулу для достижения гарантии незаметности водяного знака.

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

А23 (P.Loo [16]).

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

Для модификации выбираются 1000 наибольших коэффициентов (рис. 6.1).

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

(6.16).

Где и — весовые коэффициенты, зависящие от уровня и предназначенные для достижения робастности и незаметности водяного знака, U(m,n) — среднее значение по окрестности 3*3 вокруг данного коэффициента.

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

Рис 6.1. Отбор коэффициентов.

А24 (С.Lu [19, 20, 17, 18]).

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

Для декомпозиции изображения используется трехуровневое ВП.

Для модификации выбираются вейвлет-коэффициенты, амплитуда которых выше некоторого порога [JND — just noticeable difference].

Перед встраиванием информации вейвлет-коэффициенты сортируются в порядке возрастания их амплитуд. Таким же образом переупорядочиваются элементы гауссовской последовательности. На каждой итерации отбираются пара вейвлет-коэффициентов (f_{положит}, f_отриц) из «верха» упорядоченной последовательности вейвлет-коэффициентов исходного изображения и пара элементов последовательности ЦВЗ (w_верх w_нижн) из верхней и нижней части последовательности w.

При положительной модуляции правило.

(6.17).

При отрицательной модуляции правило.

(6.18).

Применяется к отобранным вейвлет-коэффициентам для внедрения водяного знака. J обозначает JND-значение отобранного вейвлет-коэффициента, вычисленное на основе модели человеческого зрения, описанной в [31]. Весовой коэффициент определяет максимально возможное изменение и выбирается различным для аппроксимационного и детального поддиапазонов.

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

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

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

А25 (С.Podilchuk [23, 24, 32]).

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

В алгоритме используется четырехуровневая декомпозиция ВП с использованием 7/9 биортогональных фильтров.

Для внедрения ЦВЗ отбираются только вейвлет-коэффициенты f(m,n), амплитуда которых выше некоторого порога (JND).

Встраивание информации выполняется в соответствии с (6.2), но с учетом порога JND:

(6.19).

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

Этот алгоритм можно рассматривать как модификацию алгоритма И.Кокса [11]. Модификация заключается в добавлении масштабирующего коэффициента масштаба, зависящего от мощности исходного сигнала. Весовой коэффициент вычисляется, исходя из модели зрения, основанной на парадигме JND. Этот подход применяется для достижения верхней границы возможной интенсивности ЦВЗ. Поэтому алгоритм позволяет незаметно внедрить достаточно робастный водяной знак. Важно отметить, что построение модели человеческого зрения гораздо проще осуществить при ДВП, чем при ДКП.

Предлагаемая схема может быть применена не только при ДВП, но и при ДКП, что позволяет встраивать информацию в данные сжатые как по стандарту JPEG2000, так и по стандарту JPEG [37].

А26 (X-G.Xia[33]).

Водяной знак представляет собой последовательность псевдослучайных действительных чисел, распределенных по Гауссовскому закону.

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

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

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

, (6.21).

Где от значения зависит энергия ЦВЗ, а от значения - значение больших коэффициентов.

Для извлечения используется инверсная формула, аналогичная (6.4).

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

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

А27 (H.-J. Wang [27–30]).

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

Для встраивания выполняется пятиуровневое вейвлет-преобразование и отбираются значимые коэффициенты всех поддиапазонов. Поиск таких коэффициентов основан на принципах многопорогового вейвлет-кодера (MTWC) [25, 26]. Решение о значимости коэффициентов выносится на основании их сравнения с порогом данной субполосы T_Si. После встраивания водяного знака порог делится на два. Начальное значение порога T_Si определяется по формуле.

(6.22).

Где — весовой коэффициент данного поддиапазона.

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

Внедрение выполняется в соответствии с формулой.

. (6.23).

Для извлечения информации используется инверсная формула, аналогичная (6.4).

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

А28 (H.-J. Wang [28]).

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

Пусть f_s(m,n) — значимый коэффициент из поддиапазона s. То есть . Тогда коэффициент модифицируется согласно формуле.

(6.24).

Где sign — знак отобранного коэффициента, а определяется как.

(6.25).

Целое число p выбирается таким образом, чтобы расстояние между исходным и квантованным значением коэффициента было минимальным.

При извлечении ЦВЗ вслепую вместо исходного коэффициента используется его аппроксимация . Таким образом, получим.

(6.26).

Слепая схема извлечения оказывается намного менее помехоустойчивой, как это отмечено в [29].

6.1.2. Обзор алгоритмов на основе слияния ЦВЗ и контейнера.

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

У таких алгоритмов есть два преимущества.

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

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

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

А29 (J.Chae [4,5]).

В алгоритме внедряется черно-белое изображение (логотип), размером до 25 % от размеров исходного изображения. Перед встраиванием выполняется одноуровневая декомпозиция как исходного изображения, так и эмблемы с применением фильтров Хаара. Вейвлет-коэффициенты исходного изображения обозначаются, как f(m,n), а вейвлет-коэффициенты логотипа — w(m,n).

Модификации подвергаются все коэффициенты преобразования, как это показано на рис. 6.2.

Рис 6.2. Схема встраивания ЦВЗ.

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

Обозначим, через А, В, и С соответственно, старший, средний и младший байты 24-битного представления логотипа. На рис. 6.2 показано формирование трех 24-битных чисел А′, В′ и С′. Старший байт каждого из этих чисел представляет собой соответственно А, В, или С, два других байта заполняются нулями.

Затем формируется расширенный вчетверо блок коэффициентов логотипа. После чего он поэлементно складывается с 24-битной версией исходного изображения.

. (6.27).

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

Для извлечения ЦВЗ используется инверсная формула, аналогичная (6.4).

Данный алгоритм позволяет скрыть довольно большой объем данных в исходном изображении: до четверти от размеров исходного изображения.

А30 (D.Kundur [14]).

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

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

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

, (6.28).

Где S — коэффициент масштаба, вычисляемый по формуле.

, (6.29).

C(u,v) — взвешивающая матрица, определяющая частотную чувствительность системы зрения человека, Т — оператор ДПФ.

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