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

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

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

Применение ДВП к двумерному изображению приводит к обработке его двумерными фильтрами по обоим измерениям. Фильтры делят изображение на четыре непересекающихся поддиапазона с большим расширением LL1, LH1, НL1, НН1. Поддиапазон LL1 представляет собой коэффициенты ДВП с грубым приближением, тогда как диапазоны LH1, HL1 и HH1 представляют коэффициенты ДВП с хорошим разрешением. Чтобы получить следующее грубое приближение коэффициентов ДВП, необходимо дальше преобразовать поддиапазон LL1 до тех пор, пока не будет достигнут требуемый уровень N. По достижении уровня N, в результате остается 3N+1 поддиапазона, состоящих из LLX поддиапазонов, LHX, HLX и HHX, где X изменяется от 1 до N. Благодаря свойству хорошей частотной масштабированности при помощи DWT можно легко найти область на изображении, куда наиболее эффективно поместить водяной знак. В частности, это свойство позволяет использовать так называемый «эффект маскировки» человеческой зрительной системы, то есть, если коэффициент ДВП изменяется, то изменятся только тот регион изображения, за который отвечает данный коэффициент. В целом, большинство энергии изображения сосредоточено в поддиапазонах с низкой частотой LLX, поэтому внедрение водяного знака в этих областях может сильно исказить исходное изображение. С другой стороны, поддиапазоны с высокими частотами HHX содержат края и текстуры изображения, изменения в которых человеческий глаз не воспринимает. Это позволяет добавить водяной знак незаметно. В целом, самым подходящим решением является размещение водяного знака в поддиапазонах средних частот HLX и LHX, где достигается удовлетворительная скорость алгоритмов и устойчивость водяного знака к дальнейшим трансформациям изображения. Общую схему трехмерной декомпозиции можно увидеть на рисунке 1.

Р
ис 1.

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

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

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

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

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

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

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

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

Литература:

1. Arnold M., Shumucker M., Wolthusen S. “Techniques and Applications of Digital Watermarking and Content Protection” – Boston: Artech House Publishers., 2003.

2. Goldberg D. “Genetic Algorithms in Search. Optimization and Machine Learning” – USA: Addison Wesley Professional., 1989.

3. Furth B., Kirovski D., “Multimedia Encryption and Authentications: Techniques and Applications” – USA: Auerbach Publications., 2006.