Алгоритм внедрения водяных знаков в изображение на основе ортогональных моментов Цернике

ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

УДК 681.323

А. П. Бахрушин, Г. И. Бахрушина

АЛГОРИТМ ВНЕДРЕНИЯ ВОДЯНЫХ ЗНАКОВ В ИЗОБРАЖЕНИЕ НА ОСНОВЕ ОРТОГОНАЛЬНЫХ МОМЕНТОВ ЦЕРНИКЕ

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

Ключевые слова: цифровые водяные знаки, геометрические атаки, моменты Цернике.

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

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

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

Бахрушин Александр Петрович — кандидат технических наук, доцент, доцент (Приамурский государственный университет имени Шолом-Алейхема, Биробиджан); e-mail: stripylife@yahoo.com

Бахрушина Галина Ивановна — кандидат физико-математических наук, доцент (Тихоокеанский государственный университет, Хабаровск); e-mail: gal_bah@mail.ru

© Бахрушин А. П., Бахрушина Г И., 2014

72

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

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

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

Для получения инвариантных к геометрическим атакам признаков в работах [2—5] было предложено использовать моменты изображения, такие как суммарная интенсивность, геометрический центр, ориентация, инерция. Однако наибольший научный интерес при разработке алгоритмов, инвариантных к геометрическим атакам, представляет идея использования моментов Цернике, благодаря их помехоустойчивости, независимости от контекста исходного изображения и инвариантности к аффинным преобразованиям [5, 6].

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

V (д:,у) = г (р, в) = г (р)езтв,

пт V ' У ' пт ^г^' ' пт ^ '

ще X, у и р, 0 представлены в декартовой и полярной системах координат соответственно; г (р) — радиальный полином Цернике;

р = 4х 2+У 2;

в=агсг°(.г .V). 6>Е[0.2.Т];

п — порядок момента (порядок радиальной координаты), п> 0; т — множитель угловой координаты, причем п - |н/| — четно и | т | < п

Радиальный полином Цернике определяется следующим образом:

73

, ч (-1)4 (П-8)\Р П~2 4 Г ( О ) = > -:-:-:-:-

Ы з\((п + \т\)/2-з)\((п-\т\)/2-э)\

Значения комплексных ортогональных моментов Цернике можно вычислить согласно выражению:

я1Я1

*г=0 г = 0

где функция V*,,т(хк,у() комплексно сопряжена с функцией Vпш(хк,V,) • Функция /(хк, у ) представляет исходное изображение размера ЖхЖ, причем:

+ 1 2/-ЛГ + 1

ХА- = -Гт-' У> = '

k,t =0,N-l.

N " N

По известным моментам Цернике &пт можно восстановить исходное изображение:

^ "тих П

7

и—0 т--п

где ^ — максимальный порядок момента.

Моменты Цернике являются комплексными функциями и поэтому могут быть представлены в виде амплитудно-частотного (АЧС) и фазо-частотного спектров (ФЧС).

Важно отметить, что вычисляемые таким образом моменты Цернике в строгом смысле слова не являются точными. В работах [8—10] отмечается, что в данном случае возможны два вида ошибок, получивших названия геометрической ошибки аппроксимации и численной ошибки аппр оксимации.

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

Инвариантность к повороту изображения

Благодаря этому свойству моменты Цернике широко используются при разработке систем распознавания образов, при создании систем машинного зрения и во многих других приложениях, связанных с проблемой цифровой обработки изображений. Пусть исходное изображение представлено моментами а . Тогда изображение, повернутое на угол ОС градусов, можно представить моментами а'"} =апте1"ш  Очевидно, что

\а(а)\ = \а I.

пт пт I

74

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

Устойчивость к атаке в виде отражения изображения

Другим важным свойством моментов Цернике является устойчивость к атаке в вице отражения изображения (image flipping) по горизонтали или по вертикали. Отражение изображения f (x, y) по горизонтали можно записать, как: f'h)(x,y) = f(—x,y), а по вертикали — flv)(x,v) = f(x-v).

Обозначим через a^m моменты Цернике при отражении по горизонтали, а

через a^ m — при отражении по вертикали. Тогда несложно показать, что:

aw =(-\)та и a(v)=a

пт V / пт 1 тп пт"

Таким образом, значения моментов Цернике не изменяются, т. е.

,

a(А}

nm

-\апт\ И

a

nm

= \а

72/72

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

Кроме того, моменты Цернике обладают большей помехоустойчивостью по сравнению с другими моментами [2 — 5]. Однако их значения не инвариантны к атакам в виде изменения масштаба изображения и его сдвига.

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

Внедрение ЦВЗ

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

Допустим, что ЦВЗ представляет собой псевдослучайную последовательность 17" = {и?(1), и'(2), ... ,IV(М)I, состоящую из м элементов, таких что м?(г)е{0,1). Основная идея состоит в том, что каждому элементу ЦВЗ ставится в соответствие бинарный код:

75

W-

(1), м> (2),... ,МГ (£)} дттины К = 2к, где к задано, определяемый следующим образом:

1, / = О

w (г) =

w (i) =

-1, i = (к +1), 2k -1, i = Гк

1, i = (к +1), 2к

если w(i) =1;

если w(i)=0.

Не теряя общности, для упрощения рассуждений сначала рассмотрим одномерный случай. Предположим, что необходимо внедрить в начало некоторой исходной последовательности v

£(/') = !</') + , = 1КГ

где 2 — масштабный коэффициент.

В результате сложения формируется последовательность \>(г), содержащая бинарный код V (I), как показано на рис. 1с. Извлечение бинарного кода V (I) может быть произведено посредством процедуры центрирования последовательности у(1), которая позволяет извлечь бинарный код и1'(7), совпадающий с бинарным кодом и-' (?), как показано на рис. 1с1.

Рис. 1. Внедрение кода V/ (I) в v(i) с последующим его извлечением

Мы рассмотрели идеальный случай, когда все элементы исходной последовательности v(i) имеют одинаковые значения. Однако в общем случае они могут иметь разные значения. Поэтому над последовательностью v(i) предлагается выполнить процедуру выравнивания значений ее элементов. Пусть, например, в исходную последовательность V (I), представленную на рис. 2, необходимо внедрить бинарный код V (I) .

76

Рис. 2. Исходная последовательность

Очевидно, что после такого внедрения нечего будет извлекать. Поэтому перед внедрением бинарного кода предлагается выполнить процедуру модификации значений элементов последовательности v(i) .

Сначала последовательность v(i) делится на две подпоследовательности одинаковой длины, для которых определяются средние значения их элементов ^ и . Затем вычисляется разница между ^ и

d =S\-S2

и производится выравнивание ще символ | — функция пола.

5*2 — *S*2

d +1

Предположим, что ЦВЗ представлен случайным преобразованным бинарным кодом И'(7) — +1 длины к  М , как показано на рис. 3.

Рис. 3. Преобразованный случайный бинарный код И'(7) = +1 длины к  М = 8, представляющий ЦВЗ

Пусть к = 1. Тогда, перед внедрением ЦВЗ, представим каждое значение (7) бинарным двухразрядным кодом, определяемым следующим образом:

если м>0) = 1,то I ^2'"1)=1;ес.ли =0,то I ^2'"1) = _1,где / = Ш. [ ч\И)=-\ \ м>(2/)=1

В результате формируется последовательность УУ (/') длины 2М, состоящая из двухразрядных бинарных кодов, как показано на рис. 4.

2

77

Рис. 4. Последовательность V (I) длины 2М при к = 1

Предположим, что необходимо внедрить последовательность V (I) в исходную последовательность ) длины 2М, представленную на рис. 5.

Рис. 5. Исходная последовательность )

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

Рис. 6. Последовательность у(1) , в которую внедрен ЦВЗ

Рассмотрим процедуру извлечения ЦВЗ. Извлечение ЦВЗ может быть выполнено путем сравнения значений элементов левых и правых частей подпоследовательностей:

w' (i) =

1, если £

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

78

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

/Щ) и т2),

ще \ <п1<Ы, 1 < и2 и 1 <т 1<М1, 1 <т2 <М2 соответственно.

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

1. В соответствии с формулой (1) вычисляются моменты Цернике а .

2. Функция и>(тътг) преобразуется в функцию м> (т1, т2).

В общем случае, при к> 1, данное преобразование вьшолняется согласно выражениям:

м>{тх,(2я?2 -2)к + ]) = м>{т1,т2) т(2 т2 -1) к + ]) = -ч1(т^т2),

ще ] = \,к, тх=\,Мхг тг=\,Мг-

В результате формируется преобразованный ЦВЗ Ж размером

М1 х М2К

3. Перед внедрением ЦВЗ производится копирование АЧС:

А= А.

ЦВЗ Ж внедряется в моменты Цернике а с координатами его левого верхнего угла (ц, р) при следующих ограничениях:

д-1+М, <Ы, р-\+М2К<Ы. Процедура внедрения выполняется следующим образом: а(ц-\+тх,р-\+т2)=а{ц-\+т1,р-\+т2)+2М>{т1.т2),

ще тг= 1, N, т2=\, N К

4. В соответствии с выражением (2) вычисляется обратное преобразование. В результате формируется изображение ¥, в которое внедрен ЦВЗ. Извлечение ЦВЗ

Извлечение ЦВЗ начинается с преобразования изображения ¥, предположительно содержащего ЦВЗ согласно выражению (1). Затем в пределах

полученного спектра производится поиск преобразованного ЦВЗ Ж и формирование функции м>'(т1,т2) , которая, возможно, будет коррелировать с функцией w(m, т2), представляющей ЦВЗ. С этой целью сначала вычисляется функция средних значений подынтервалов (рис. 2):

79

^ a

g(m1,m2) =

j=1

k

ще mx=\,N, т2 =lN/2, j = l,k

В окончательном виде получаем:

1, если g

w '(m, m )=

—1, если g

ще m1 =l,N, m2 =\,N/2.

Для принятия решения относительно соответствия сформированной функции эталонному ЦВЗ производится вычисление нормализованного коэффициента корреляции (НКК) р(1¥, Ж') и его сравнение с некоторым порогом к. Если р(\¥, Цг)>1г, принимается решение, что ЦВЗ извлечен.

Список литературы

1. Potdar V. M., Han S., Chang E. A Survey of Digital Image Watermarking Techniques // In Proceedings of the 3rd IEEE International Conference on Industrial Informatics (INDIN '05). 2005. Pp. 709-716.

2. Мамедов Р. К., Муталлимова А. С., Алиев Т. Ч. Использование моментов инерции изображения для инвариантного к аффинным преобразованиям распознавания // Восточно-Европейский журнал передовых технологий. 2012. № 3(58). T. 4. С. 4-7.

3. Flusser J., Boldy J., Zitov B. Moment forms invariant to rotation and blur in arbitrary number of dimensions // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2003. No. 2. Vol. 25. Pp. 234 - 246.

4. The C., Chin R. T. On image analysis by the methods of moments // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1988. No. 10 (4). Pp. 496-513.

5. Kim H. S., Lee H. K. Invariant Image Watermark using Zernike Moments / / IEEE Transactions on Circuits and Systems for Video Tech. 2003. No. 13(8). Pp. 766 — 775.

6. Singh C., Walia E. Algorithms for Fast Computation of Zernike moments and their Numerical Stability // Image and Vision Computing. 2011. No. 29. Pp. 251—259.

7. Farzam M., Shirani S. A Robust Multimedia Watermarking Technique using Zernike Transform / / IEEE 4th Workshop on Multimedia Signal Processing. 2001. Pp. 529 - 534.

8. Xin Y., Liao S., Pawlak M. Circularly Orthogonal Moments for Geometrically Robust Image Watermarking // Pattern Recognition. 2007. No. 40(12). pp. 3740-3752.

9. Pawlak M., Liao S. X. On the recovery of a function on a circular domain // IEEE Transactions on Information Theory. 2002. Vol. 48(10). Pp. 2736 - 2753.

10. Singh C., Walia E. Fast and Numerically Stable Methods for the Computation of Zernike moments // Pattern Recognition. 2010. Vol. 43. Pp. 2497-2506.

11. Bahrushin A. P., Bahrushina G. I., Tsoy R. I. High Embedding Capacity and Low Distortion Watermarking Scheme / / The First Russia and Pacific Conference on

80

Computer Technology and Applications (RPC 2010). Vladivostok, 2010. Pp. 370 - 373.

12. Бахрушин А. П., Бахрушина Г. И., Цой Р. И. Разработка методов защиты видеопродукции, устойчивых к геометрическим атакам / / Вестник Дальневосточной государственной социально-гуманитарной академии. 2011. № 2(9). С. 18—29.

* * *

Bahrushin Alexander P., Bahrushina Galina I.

THE ALGORITHM FOR IMPLEMENTING A WATERMARK

IN THE IMAGE BASED ON THE ORTHOGONAL ZERNIKE MOMENTS

The article is devoted to the technique of embedding a digital watermark (DWM) in the image to solve the problem of multimedia data copyright protection. As it is known, digital watermark is identification code that may contain some information about the intended recipient, the lawful owner or author of the original data. This code can be embedded into multimedia data in a form of textual file or digital image. For the purpose of effective copyright protection, such as video production, digital watermark must be resistant to a variety of attacks, of which the most dangerous are the geometric attacks. It is clear that even very small geometric distortions can prevent the detection and extraction of the watermarks of the digital images. For solving this problem several types of watermarking algorithms have been developed so far each of which has its own advantages and limitations. This article discusses the possibility of watermark embedding in still digital images based on orthogonal Zernike moments. It is noted that the remarkable property of Zernike moments is their invariance to image rotation. Due to this property it is possible to construct an algorithm of watermark embedding resistant to geometric attacks.

Keywords: digital watermarks, geometric attacks, Zernike moments.

References

1. Potdar V. M., Han S., Chang E. A Survey of Digital Image Watermarking Techniques, in Proceedings of the 3rd IEEE International Conference on Industrial Informatics (INDIN '05), 2005, pp. 709 — 716.

2. Mamedov R. K., Mutallimova A. S., Aliev T. Ch. The Moment of Inertia Use Images for Invariant Recognition to Affine Transformations, Eastern-European Journal of Enterprise Technologies, 2012, no. 3(58), vol. 4, pp. 4—7.

3. Flusser J., Boldy J., Zitov B. Moment Forms Invariant to Rotation and Blur in Arbitrary Number of Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, vol. 25, no. 2, pp. 234 — 246. DOI: 10,1109 / TPAMI.2003.1177154

4. The C., Chin R. T. On Image Analysis by the Methods of Moments, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, no. 10 (4), pp. 496—513. DOI: 10,1109 / 34,3913

5. Kim H. S., Lee H. K. Invariant Image Watermark using Zernike Moments, IEEE Transactions on Circuits and Systems for Video Tech, 2003, no. 13(8), pp. 766 — 775. DOI: 10,1109 / TCSVT.2003.815955

6. Singh C., Walia E. Algorithms for Fast Computation of Zernike moments and their Numerical Stability, Image and Vision Computing, 2011, no. 29, pp. 251 —259.

7. Farzam M., Shirani S. A Robust Multimedia Watermarking Technique using Zernike Transform, IEEE 4th Workshop on Multimedia Signal Processing, 2001, pp. 529 — 534. DOI: 10,1109 / MMSP.2001.962787

8. Xin Y., Liao S., Pawlak M. Circularly Orthogonal Moments for Geometrically Robust Image Watermarking, Pattern Recognition, 2007, no. 40(12), pp. 3740—3752. DOI: 10.1016 / j.patcog.2007.05.004

81

9. Pawlak M., Liao S. X. On the recovery of a function on a circular domain, IEEE Transactions on Information Theory, 2002, vol. 48(10), pp. 2736 — 2753. DOI: 10,1109/TIT.2002.802627

10. Singh C., Walia E. Fast and Numerically Stable Methods for the Computation of Zernike moments, Pattern Recognition, 2010, vol. 43, pp. 2497—2506. DOI: 10.1016/j.patcog.2010.02.005

11. Bahrushin A. P., Bahrushina G. I., Tsoy R. I. High Embedding Capacity and Low Distortion Watermarking Scheme, The First Russia and Pacific Conference on Computer Technology and Applications (RPC 2010), Vladivostok, 2010, pp. 370 — 373.

12. Bakhrushin A. P., Bakhrushina G. I., Tsoy R. I. Developing Methods to Protect Video, Resistant to Geometric Attacks [Razrabotka metodov zashchity video-produktsii, ustoychivykh k geometricheskim atakam] Vestnik Dal'nevostochnoy

gosudarstvennoy sotsial'no-gumanitarnoy akademii, 2011, no. 2(9), pp. 18—29.

* * *

82