Новый метод встраивания цифровых водяных знаков в векторные картографические данные

НОВЫЙ МЕТОД ВСТРАИВАНИЯ ЦИФРОВЫХ ВОДЯНЫХ ЗНАКОВ В ВЕКТОРНЫЕ КАРТОГРАФИЧЕСКИЕ ДАННЫЕ

Ю.Д. Выборнова 1, В.В. Сергеев 1,2 1 Самарский национальный исследовательский университет имени академика С.П. Королева, Самара, Россия, 2 Институт систем обработки изображений РАН - филиал ФНИЦ «Кристаллография и фотоника» РАН, Самара, Россия

Аннотация

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

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

Цитирование: Выборнова, Ю.Д. Новый метод встраивания цифровых водяных знаков в векторные картографические данные / Ю.Д. Выборнова, В.В. Сергеев // Компьютерная оптика. -2017. - Т. 41, № 6. - С. 913-919. - Б01: 10.18287/2412-6179-2017-41-6-913-919.

Введение

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

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

Одним из подходов к аутентификации и защите авторских прав на цифровые мультимедийные данные (изображения, видео, аудио и т.д.) является использование цифровых водяных знаков (ЦВЗ), т.е. встраивание в данные некоторой защитной информации, не ощутимой для обычного пользователя, но предоставляющей техническую возможность проследить и доказать несанкционированное копирование и распространение данных и тем самым защитить интересы законных владельцев [2]. К сожалению, векторные карты предоставляют гораздо меньше возможности для встраивания ЦВЗ, нежели другие виды мультимедийных данных, поскольку имеют сравнительно малый объем и низкую избыточность. Тем не менее, по мере распространения ГИС активизируются

исследования в области технологий встраивания ЦВЗ и в этот вид данных.

На сегодня уже известно довольно много методов встраивания ЦВЗ в векторные данные ГИС [3]. Во всех известных методах встраивание ЦВЗ осуществляется путем небольшого (допустимого с точки зрения точности картографических материалов) изменения данных векторной карты: координат вершин полигонов, углов полилиний, локальных статистических характеристик объектов карты и т.д. При этом ЦВЗ - битовый вектор определенной длины - либо непосредственно задает такие изменения (в методах встраивания в пространственной области [4 - 17]), либо вносится в коэффициенты дискретного спектрального разложения (Фурье, косинусного, вейвлет) последовательности координат вершин или других характеристик (в методах встраивания в частотной области [18 - 24]). Используемые подходы к встраиванию ЦВЗ предопределяют недостатки известных методов:

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

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

3. Не все методы являются «слепыми», т.е. в них для извлечения ЦВЗ требуется исходная цифровая карта с неискаженной координатной информацией.

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

1. Предлагаемый принцип встраивания ЦВЗ

Графические объекты векторной карты ГИС можно подразделить на три основных типа: точка, полилиния и полигон. Мы предлагаем в качестве контейнера для встраивания ЦВЗ использовать данные типа «полигон», т.е. объекты, представляющие собой многоугольники.

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

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

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

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

N

Рис. 1. Иллюстрация встраивания в полигон 4-разрядного двоичного числа

Так, при внесении числа 0011 список должен начинаться с вершины В. При извлечении ЦВЗ вер-

шине В, стоящей первой в списке, будет поставлено в соответствие именно внесенное двоичное число. Однако вершина В останется первой в списке и при внесении «соседних» чисел 0010 и 0100, при этом извлечется всё равно 0011, т.е. восстановление элемента ЦВЗ будет осуществлено с погрешностью.

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

2. Выбор вида ЦВЗ для встраивания

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

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

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

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

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

3. Алгоритмы встраивания и извлечения ЦВЗ

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

1) определяется центр тяжести полигона;

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

3) это число встраивается в полигон путем назначения соответствующей вершины первой в циклическом списке вершин полигона (рис. 1).

Алгоритм извлечения изображения-ЦВЗ из карты:

1) на анализируемую векторную карту накладывается «пустое» растровое изображение с достаточно мелким шагом между пикселями;

2) на карте выделяются все присутствующие на ней полигональные объекты;

3) для каждого полигона определяется центр тяжести и пространственная ориентация первого элемента циклического списка вершин полигона;

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

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

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

На изображении, извлеченном из векторной карты, должны быть визуально различимы участки с ЦВЗ, что и требуется для аутентификации защищаемых векторных данных ГИС.

4. Пример реализации

Рассмотрим простейший случай встраивания бинарного изображения-ЦВЗ (рис. 2) в слой векторной карты - фрагмента плана городской застройки, содержащий 8589 полигонов (рис. 3). Примем и = 1, т.е. в каждый полигон будет встраиваться один бит, соответствующий бинарному пикселю изображения.

Рис. 2. Бинарное изображение-ЦВЗ

Рис. 3. Векторный слой карты с полигонами -контейнер для ЦВЗ

Извлеченное изображение-ЦВЗ (до интерполяции) представлено на рис. 4а. Здесь черным цветом обозначены пиксели, которым было присвоено значение «0», белым - пиксели, которым было присвоено значение «1». Серым цветом обозначены пиксели, которым в результате процедуры извлечения значение не присвоено.

Рис. 4. Изображение-ЦВЗ, извлеченное из векторной карты: а) до интерполяции, б) после интерполяции

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

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

5. Стойкость ЦВЗ к геометрическим преобразованиям

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

1) Сдвиг и масштабирование

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

2) Поворот

На рис. 5 приведены результаты извлечения изоб-ражения-ЦВЗ при повороте карты (здесь и далее рассматривается тот же пример, что и в предыдущем пункте).

в)\

д)

Рис. 5. Результат извлечения ЦВЗ при повороте карты а) 10°, б) 25°, в) 45°, г) 90°, д) 180°, е) 270°

Приведенные рисунки позволяют сделать вывод о том, что при повороте карты изображение-ЦВЗ поворачивается вместе с картой. При достаточно большом угле поворота ЦВЗ может выглядеть искаженным или даже визуально неразличимым. Так, в рассмотренном примере при повороте на 180° ЦВЗ визуализируется в негативе (рис. 5д), а при повороте на 90° и 270° - разрушается (рис. 5г, е).

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

3) Кадрирование

На рис. 6 приведен результат извлечения ЦВЗ после кадрирования (обрезки краев) карты.

Рис. 6. Результат кадрирования карты со встроенным ЦВЗ: а) до интерполяции, б) после интерполяции

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

Заключение

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

Дальнейшие исследования метода предполагается

направить:

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

- уточнение требований к растровому изображению, вносимому в карту в качестве ЦВЗ;

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

- анализ устойчивости ЦВЗ к изменению содержимого карты (добавлению/удалению вершин, объектов, слоев);

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

- оценку предельной информационной емкости ЦВЗ, вносимого в векторные данные ГИС предложенным методом и его модификациями.

Литература

1. Капралов, Е.Г. Геоинформатика: в 2 кн. Кн. 1: учебник для студ. высш. учеб. заведений / Е.Г. Капралов,

A.В. Кошкарев, В.С. Тикунов [и др.]; под ред.

B.С. Тикунова. - 3-е изд., перераб. и доп. - М.: Издательский центр «Академия», 2010. - 400 с. - ISBN: 57695-1443-4.

2. Федосеев, В. А. Унифицированная модель систем встраивания информации в цифровые сигналы / В.А. Федосеев // Компьютерная оптика. - 2016. - Т. 40, № 1. - С. 87-98. - DOI: 10.18287/2412-6179-2016-40-187-98.

3. Niu, X. A survey of digital vector map watermarking / X. Niu, C. Shao, X. Wang // International Journal of Innovative Computing, Information and Control (ICIC). -2006. - Vol. 2(6). - P. 1301-1316.

4. Ohbuchi, R. Robust watermarking of vector digital maps / R. Ohbuchi, H. Ueda, S. Endoh // IEEE International Conference on Multimedia and Expo. - 2002. - P. 577-580. -DOI: 10.1109/ICME.2002.1035847.

5. Vogit, M. Watermarking 2D-vector data for geographical information systems / M. Vogit, C. Busch // Proceedings of SPIE. - 2002. - Vol. 4675. - P. 621-628. - DOI: 10.1117/12.465322.

6. Vogit, M. Feature-based watermarking of 2D-vector data / M. Vogit, C. Busch // Proceedings of SPIE. - 2003. -Vol. 5020. - P. 359-366. - DOI: 10.1117/12.476815.

7. Li, A. Study on copyright authentication of GIS vector data based on zero-watermarking / A. Li, B. Lin, Y. Chen // The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. - 2008. -Vol. 37, Part B4. - P. 1783-1786.

8. Wang, C. Watermarking geographical data on spatial topological relations / C. Wang, Z. Peng, Y. Peng, L. Yu, J. Wang, Q. Zhao // Multimedia Tools and Applications. -2010. - Vol. 57, Issue 1. - P. 67-89. - DOI: 10.1007/s11042-010-0536-9.

9. Kim, J. Robust vector digital watermarking using angles and a random table / J. Kim // Advances in Information Sciences and Service Sciences. - 2010. - Vol. 2(4). -P. 79-90. - DOI: 10.4156/aiss.vol2.issue4.9.

10. Yan, H. A key points-based blind watermarking approach for vector geospatial data / H. Yan, J. Li, H. Wen // Computers, Environment and Urban Systems. - 2010. - Vol. 35(6). -P. 485-492. - DOI: 10.1016/j.compenvurbsys.2010.10.004.

11. Huo, X. A watermarking scheme using polyline and polygon characteristic of shapefile / X. Huo, T. Seung, B. Jang, K. Kwon, S. Lee // 3rd International Conference on Intelligent Networks and Intelligent Systems (ICINIS). - 2010. -Vol. 1. - P. 1-3. - DOI: 10.1109/ICINIS.2010.115.

12. Cao, L. Iterative embedding-based reversible watermarking for 2D-vector maps / L. Cao, C. Men, X. Li // 17th IEEE International Conference on Image Processing (ICIP). - 2010. - Vol. 1. - P. 3685-3688. - DOI: 10.1109/ICIP.2010.5652535.

13. Huo, X.J. Protecting GIS vector map using the k-means clustering algorithm and odd-even coding / X.J. Huo, K.S. Moon, S.H. Lee, T.Y. Seung, S.G. Kwon // 17th Korea-Japan Joint Workshop on Frontiers of Computer Vision. - 2011. - Vol. 1. - P. 1-5. - DOI: 10.1109/FCV.2011.5739741.

14. Wang, N. Reversible watermarking for 2-D vector map authentication with localization / N. Wang, C. Men // Computer-Aided Design. - 2012. - Vol. 44(4). - P. 320-330. -DOI: 10.1016/j.cad.2011.11.001.

15. Lee, S.H. Vector watermarking scheme for GIS vector map management / S.H. Lee, K.R. Kwon // Multimedia Tools and Applications. - 2013. - Vol. 63(3). - P. 757790. - DOI: 10.1007/s11042-011-0894-y.

16. Ren, N. Selective authentication algorithm based on semifragile watermarking for vector geographical data / N. Ren, Q. Wang, C. Zhu // 22nd International Conference on Geoinformatics. - 2014. - Vol. 1. - P. 1-6. - DOI: 10.1109/GEOINFORMATICS.2014.6950830.

17. Abubahia, A. A clustering approach for protecting GIS vector data / A. Abubahia, M. Cocea // 27th International Conference on Advanced Information Systems Engineering. - 2015. - Vol. 1. - P. 133-147. - DOI: 10.1007/978-3-319-19069-3_9.

18. Kitamura, I. Copyright protection of vector map using digital watermarking method based on discrete Fourier transform / I. Kitamura, S. Kanai, T. Kishinami // IEEE 2001 International Geosciences and Remote Sensing. - 2001. - Vol. 1. -P. 191-193. - DOI: 10.1109/IGARSS.2001.976788.

19. Solachidis, V. Fourier descriptors watermarking of vector graphics images / V. Solachidis, N. Nikolaidis, I. Pitas // 2000 International Conference On Image Processing. -2000. - Vol. 3. - P. 9-12. - DOI: 10.1109/ICIP.2000.899265.

20. Ohbuchi, R. Watermarking 2D vector maps in the mesh-spectral domain / R. Ohbuchi, H. Ueda, S. Endoh // SMI '03 Proceedings of the Shape Modeling International. - 2003. -Vol. 1. - P. 216-228. - DOI: 10.1109/SMI.2003.1199619.

21. Tao, S. Watermarking GIS data for digital map copyright protection / S. Tao, X. Dehe, L. Chengming, S. Jianguo // 24th International Cartographic Conference. - 2009. -Vol. 1. - P. 1-9.

22. Zhang, L. New robust watermarking algorithm for vector data / L. Zhang, D. Yan, S. Jiang, T. Shi // Wuhan University Journal of Natural Sciences. - 2010. - Vol. 15(5). -P. 403-407. - DOI: 10.1007/s11859-010-0674-y.

23. Wang, C. Watermarking vector maps based on minimum encasing rectangle / C. Wang, L. Zhang, B. Liang, W. Du, Y. Peng // 2011 International Conference on Intelligent Computation Technology and Automation (ICICTA). - 2011. -Vol. 1. - P. 28-29. - DOI: 10.1109/ICICTA.2011.589.

24. Zope-Chaudhari, S. Robust watermarking for protection of geospatial data / S. Zope-Chaudhari, P. Venkatachalam // International Conference on Security Science and Technology. - 2012. - Vol. 1. - P. 34-38.

25. Глумов, Н.И. Алгоритм поблочного встраивания стойких ЦВЗ в крупноформатные изображения / Н.И. Глумов, В.А. Митекин // Компьютерная оптика. -2011. - Т. 35, № 3. - С. 368-372.

Сведения об авторах

Выборнова Юлия Дмитриевна, 1993 года рождения, в 2015 году окончила Самарский государственный аэрокосмический университет по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», работает младшим научным сотрудником в НИЛ-55 Самарского национального исследовательского университета имени академика С.П. Королёва. Область научных интересов: криптография, цифровые водяные знаки, обработка изображений. E-mail: vybornovamail@gmail.com .

Сергеев Владислав Викторович, родился в 1951 году. В 1974 году окончил Куйбышевский авиационный институт. В 1993 году защитил диссертацию на соискание степени доктора технических наук. Основное место работы - директор института информатики, математики и электроники Самарского национального исследовательского университета имени академика С.П. Королёва (Самарский университет). По совместительству работает заведующим лабораторией математических методов обработки изображений в Институте систем обработки изображений РАН (ИСОИ РАН) - филиале ФНИЦ «Кристаллография и фотоника» РАН. Круг научных интересов: цифровая обработка сигналов, анализ изображений, распознавание образов, геоинформатика. E-mail: vserg@geosamara.ru .

ГРНТИ: 81.96.00.

Поступила в редакцию 15 июня 2017 г. Окончательный вариант - 13 ноября 2017 г.

A NEW WATERMARKING METHOD FOR VECTOR MAP DATA

Y.D. Vybornova', V.V. Sergeev1,2 'Samara National Research University, Samara, Russia, 2Image Processing Systems Institute оf RAS - Branch of the FSRC "Crystallography and Photonics " RAS, Samara, Russia

Abstract

In this paper, we propose a new digital watermarking method for protecting of vector data in geographic information systems. The method is based on a combination of two novel approaches. Firstly, the watermark information is embedded into the polygon map objects by cyclically shifting the list of vertices of each polygon. Secondly, instead of a bit vector, a raster image superimposed on the map is considered as a watermark. The major advantage of this method is that it does not distort the map by altering the coordinate values. A simple example demonstrates the method efficiency, as well as the robustness of the embedded watermark against geometric transformations usually performed when working with map data: translation, scaling, rotation and cropping.

Keywords: digital watermarking, geographic information systems, GIS, vector map, raster image, data protection.

Citation: Vybornova YD, Sergeev VV. A new watermarking method for vector map data. Computer Optics 2017; 41(6): 913-919. DOI: 10.18287/2412-6179-2017-41-6-913-919.

References

[1] Kapralov EG, Koshkarev AV, Tikunov VS. Geoinformat-ics [In Russian]. Moscow: "Academia" Publisher; 2010. ISBN: 5-7695-1443-4.

[2] Fedoseev VA. A unified model for information hiding systems [In Russian]. Computer Optics 2016; 40(1): 87-98. DOI: 10.18287/2412-6179-2016-40-1-87-98.

[3] Niu X, Shao C, Wang X. A survey of digital vector map watermarking. International Journal of Innovative Computing, Information and Control (ICIC) 2006; 2(6): 1301-1316.

[4] Ohbuchi R, Ueda H, Endoh S. Robust Watermarking of Vector Digital Maps. IEEE International Conference on Multimedia and Expo 2002: 577-580. DOI: 10.1109/ICME.2002.1035847.

[5] Vogit M, Busch C. Watermarking 2D-vector data for geographical information systems. Proc SPIE 2002; 4675: 621-628. DOI: 10.1117/12.465322.

[6] Vogit M, Busch C. Feature-based Watermarking of 2D-Vector Data. Proc SPIE 2003; 5020: 359-366. DOI: 10.1117/12.476815.

[7] Li A, Lin B, Chen Y. Study on copyright authentication of GIS vector data based on zero-watermarking. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 2008; 37(B4): 1783-1786.

[8] Wang C, Peng Z, Peng Y, Yu L, Wang J, Zhao Q. Watermarking geographical data on spatial topological relations. Multimed Tools Appl 2010; 57(1): 67-89. DOI: 10.1007/s11042-010-0536-9.

[9] Kim J. Robust vector digital watermarking using angles and a random table. Advances in Information Sciences and Service Sciences 2010; 2(4): 79-90. DOI: 10.4156/aiss.vol2.issue4.9.

[10] Yan H, Li J, Wen H. A key points-based blind watermarking approach for vector geospatial data. Computers, Envi-

ronment and Urban Systems 2010; 35(6): 485-492. DOI: 10.1016/j.compenvurbsys.2010.10.004.

[11] Huo X, Seung T, Jang B, Kwon K, Lee S. A watermarking scheme using polyline and polygon characteristic of shape-file. 3rd International Conference on Intelligent Networks and Intelligent Systems (ICINIS) 2010; 1: 1-3. DOI: 10.1109/ICINIS.2010.115.

[12] Cao L, Men C, Li X. Iterative embedding-based reversible watermarking for 2D-vector maps. 17th IEEE International Conference on Image Processing (ICIP) 2010; 1: 36853688. DOI: 10.1109/ICIP.2010.5652535.

[13] Huo XJ, Moon KS, Lee SH, Seung TY, Kwon SG. Protecting GIS vector map using the k-means clustering algorithm and odd-even coding. 17th Korea-Japan Joint Workshop on Frontiers of Computer Vision 2011; 1: 1-5. DOI: 10.1109/FCV.2011.5739741.

[14] Wang N, Men C. Reversible watermarking for 2-D vector map authentication with localization. Computer Aided Design 2012; 44(4): 320-330. DOI: 10.1016/j.cad.2011.11.001.

[15] Lee SH, Kwon KR. Vector watermarking scheme for GIS vector map management. Multimed Tools Appl 2013; 63(3): 757-790. DOI: 10.1007/s11042-011-0894-y.

[16] Ren N, Wang Q, Zhu C. Selective authentication algorithm based on semi-fragile watermarking for vector geographical data. 22nd International Conference on Geoinformatics 2014; 1: 1-6. DOI: 10.1109/GEOINFORMATICS.2014.6950830.

[17] Abubahia A, Cocea M. A clustering approach for protecting GIS vector data. 27th International Conference on Ad-

vanced Information Systems Engineering 2015; 1: 133147. DOI: 10.1007/978-3-319-19069-3_9.

[18] Kitamura I, Kanai S, Kishinami T. Copyright protection of vector map using digital watermarking method based on discrete Fourier transform. IEEE 2001 International Geo-sciences and Remote Sensing 2001; 1: 191-193. DOI: 10.1109/IGARSS.2001.976788.

[19] Solachidis V, Nikolaidis N, Pitas I. Fourier descriptors watermarking of vector graphics images. 2000 International Conference On Image Processing 2000; 3: 9-12. DOI: 10.1109/ICIP.2000.899265.

[20] Ohbuchi R, Ueda H, Endoh S. Watermarking 2D vector maps in the mesh-spectral domain. SMI '03 2003; 1: 216228. DOI: 10.1109/SMI.2003.1199619.

[21] Tao S, Dehe X, Chengming L, Jianguo S. Watermarking GIS data for digital map copyright protection. 24th International Cartographic Conference 2009; 1: 1-9.

[22] Zhang L, Yan D, Jiang S, Shi T. New robust watermarking algorithm for vector data. Wuhan University Journal of Natural Sciences 2010; 15(5): 403-407. DOI: 10.1007/s11859-010-0674-y.

[23] Wang C, Zhang L, Liang B, Du W, Peng Y. Watermarking vector maps based on minimum encasing rectangle. ICIC-TA 2011; 1: 28-29. DOI: 10.1109/ICICTA.2011.589.

[24] Zope-Chaudhari S, Venkatachalam P. Robust watermarking for protection of geospatial data. International Conference on Security Science and Technology 2012; 1: 34-38.

[25] Glumov NI, Mitekin VA. The algorithm for large-scale images robust watermarking using blockwise processing. Computer Optics 2011; 35(3): 368-372.

Authors' information

Yuliya Dmitrievna Vybornova (b. 1993) graduated from Samara State Aerospace University in 2015, majoring in Information Security. Currently she works as a junior research fellow at Samara University. Research interests are cryptography, steganography, and digital watermarking. E-mail: vybornovamail@gmail.com .

Vladislav Victorovich Sergeev (b. 1951) graduated from Kuibyshev Aviation Institute in 1974. He received his Candidate's degree in Technical Sciences in 1978 and DrSc degree in Mathematics and Physics in 1993. At present, he is director of Institute of Informatics, Mathematics and Electronics at Samara University, also holding a part-time position as the head of a laboratory at the Image Processing Systems Institute оf the RAS - Branch of the FSRC "Crystallography and Photonics" RAS. The areas of research interests include digital signal and image processing, geoinformatics and pattern recognition. E-mail: vserg@geosamara.ru .

Received June 15, 2017. The final version - November 13, 2017.