Метод защиты векторных данных на основе встраивания растровых цифровых водяных знаков тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Выборнова Юлия Дмитриевна

• Выборнова Юлия Дмитриевна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Выборнова Юлия Дмитриевна

ВВЕДЕНИЕ

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

1.1 Характеристика ЦВЗ

1.2 Критерии качества методов встраивания ЦВЗ

1.3 Существующие методы защиты векторных графических данных на основе встраивания ЦВЗ

1.4 О необходимости создания нового подхода к встраиванию ЦВЗ

РАЗДЕЛ 2 ПРЕДЛАГАЕМЫЙ МЕТОД ЗАЩИТЫ ВЕКТОРНЫХ ГРАФИЧЕСКИХ ДАННЫХ

2.1 Метод неискажающего встраивания ЦВЗ в векторные графические данные

2.1.1 Встраивание на основе переназначения первой вершины

2.1.2 Встраивание на основе переназначения направления обхода

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

2.3 Метод синтеза шумоподобного изображения с кольцеобразным спектром

2.3.1 Формирование шумоподобного изображения ЦВЗ

2.3.2 Алгоритм синтеза криптографически стойких псевдослучайных последовательностей

2.3.3 Извлечение ЦВЗ из изображения

2.4 Детектирование закодированной в спектральной плоскости последовательности ЦВЗ

2.4.1 Детектор на основе пороговой обработки

2.4.2 Детектор на основе локальной фильтрации

2.5 Выбор метода восстановления изображения ЦВЗ

2.5.1 Сравнительный анализ методов пространственной интерполяции

2.5.2 Сравнительный анализ алгоритмов формирования опорных точек

2.5.3 Сравнительный анализ методов интерполяции в задаче восстановления шумоподобных ЦВЗ

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

3.1 Алгоритм работы программного комплекса

3.1.1 Процедура встраивания ЦВЗ

3.1.2 Процедура извлечения ЦВЗ

3.2 Исследование информационной емкости контейнера

3.3 Исследование информационной емкости изображения ЦВЗ

3.3.1 Исследование детектора на основе пороговой обработки

3.3.2 Исследование детектора на основе локальной фильтрации

РАЗДЕЛ 4 ИССЛЕДОВАНИЕ КАЧЕСТВА ПРЕДЛОЖЕННОГО МЕТОДА

4.1 Выбор детектора

4.1.1 Исследование детектора на основе пороговой обработки

4.1.2 Исследование детектора на основе локальной фильтрации

4.2 Исследование стойкости предлагаемого метода встраивания ЦВЗ

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

4.2.2 Поворот

4.2.3 Кадрирование

4.2.4 Добавление объектов

4.2.5 Удаление объектов

4.2.6 Добавление вершин

4.2.7 Удаление вершин

4.2.8 Переупорядочение вершин

4.3 Анализ качества метода

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

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

А.1. Методы встраивания в пространственную область

А.2.Методы встраивания в частотную область

ПРИЛОЖЕНИЕ Б МЕТОДЫ ПРОСТРАНСТВЕННОЙ ИНТЕРПОЛЯЦИИ

Б.1. Метод обратных взвешенных расстояний

Б.2. Метод кригинга

Б.3. Триангулированная нерегулярная сеть

ПРИЛОЖЕНИЕ В АКТ ОБ ИСПОЛЬЗОВАНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ В АО «САМАРА-ИНФОРМСПУТНИК»

ВВЕДЕНИЕ

Диссертация посвящена разработке математических методов и алгоритмов встраивания цифровых водяных знаков для решения задачи защиты авторских прав на цифровые векторные данные.

Введение диссертации (часть автореферата) на тему «Метод защиты векторных данных на основе встраивания растровых цифровых водяных знаков»

Актуальность темы исследования

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

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

Типичным примером таких данных являются цифровые векторные карты географических информационных систем (ГИС), настоящее диссертационное исследование проводится, в основном, для них.

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

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

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

Степень разработанности темы исследования

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

Эти методы, в зависимости от уровня стойкости встроенной информации к искажениям, направлены на решение различных задач защиты векторных данных. Методы встраивания стойких ЦВЗ [2-8] направлены на решение проблемы защиты авторских прав (защиты от несанкционированного распространения). Методы защиты от изменений реализуются на основе полухрупких [9,10] и хрупких [11] ЦВЗ, которые обеспечивают контроль, соответственно, подлинности и целостности векторных объектов. Также одним из распространенных подходов к защите от изменений является технология zero-watermarking [12], которая

подразумевает построение ЦВЗ на основе характеристик контейнера (векторной информации, в которую встраивается ЦВЗ). При этом процедура встраивания как таковая отсутствует: ЦВЗ необходим только при процедуре верификации. Комбинированное применение различных технологий ЦВЗ носит название multiple watermarking [13] и позволяет обеспечить комплексную защиту векторных данных от изменений и несанкционированного распространения. Существуют ситуации, когда даже незначительные изменения данных недопустимы. По этой причине возник еще один класс методов защиты векторных данных, reversible watermarking [14-16], обеспечивающий возможность восстановления значений координат после извлечения ЦВЗ. Однако эти методы не демонстрируют достаточной стойкости: случайное искажение контейнера со встроенным ЦВЗ может привести к невозможности корректного восстановления исходных координатных значений.

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

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

Цели и задачи исследования

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

1) разработку метода защиты векторных графических данных с помощью растровых изображений ЦВЗ;

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

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

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

Методология и методы исследования

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

Научная новизна работы

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

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

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

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

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

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

7. Проведено экспериментальное исследование предложенного метода защиты векторных данных применительно к картам ГИС, подтвердившее работоспособность нового метода и демонстрирующее его преимущества перед известными; выработаны рекомендации по рациональному выбору параметров метода.

Теоретическая и практическая значимость работы

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

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

Соответствие специальности

Диссертация соответствует паспорту научной специальности 05.13.17 -«Теоретические основы информатики» и охватывает следующие области исследования, входящие в эту специальность:

3. Исследование методов и разработка средств кодирования информации в виде данных... Разработка и исследование моделей данных и новых принципов их проектирования.

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

7. Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил.

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

Реализация результатов работы

Результаты диссертации были использованы при выполнении ряда госбюджетных и хоздоговорных НИР:

1. Грант РФФИ 19-07-00474 А «Методы защиты векторных карт с помощью растровых цифровых водяных знаков».

2. Грант РФФИ 19-07-00138 А «Разработка и исследование системы обнаружения искусственных искажений данных дистанционного зондирования Земли с использованием методов глубокого машинного обучения».

3. Хоздоговор № 0148200001618000059 от 01.11.2018 «Актуализация геоинформационной базы данных земель сельскохозяйственного назначения Московской области» (заказчик - Министерство сельского хозяйства и продовольствия Московской области, исполнитель - АО «Самара-Информспутник»).

4. Областной конкурс «Молодой ученый 2018» (победитель в номинации «аспирант»). «Новый метод встраивания цифровых водяных знаков в векторные картографические данные».

Степень достоверности и апробация результатов

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

Основные результаты диссертации были представлены на 6 научных конференциях:

3-ей международной конференции «Информационные технологии и нанотехнологии» (ИТНТ-2017, Самара, Россия);

4-ой международной конференции «Информационные технологии и нанотехнологии» (ИТНТ-2018, Самара, Россия);

11-ой международной конференции «International Conference on Machine Vision» (ICMV 2018, Мюнхен, Германия);

5-ой международной конференции «Информационные технологии и нанотехнологии» (ИТНТ-2019, Самара, Россия);

международной научно-технической конференции «Перспективные информационные технологии» (ПИТ-2019, Самара, Россия);

16-й международной конференции «International Conference on Security and Cryptography» (SECRYPT 2019, Прага, Чехия).

Публикации

По теме диссертации опубликовано 11 работ. Из них две работы опубликовано в изданиях, определённых в перечне ведущих рецензируемых научных журналов и изданий ВАК Министерства образования и науки РФ. Четыре работы выполнены без соавторов.

Структура диссертации

Диссертация состоит из четырёх разделов, заключения, списка литературы из 60 наименований; изложена на 126 страницах машинописного текста, содержит 38 рисунков, 21 таблицу, 3 приложения.

На защиту выносятся:

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

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

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

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

5) Алгоритмы детектирования амплитудных всплесков на спектре изображения ЦВЗ.

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

7) Экспериментальное подтверждение работоспособности и эффективности разработанного метода применительно к картам ГИС, рекомендации по рациональному выбору параметров метода.

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

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

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

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

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

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

1.1 Характеристика ЦВЗ

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

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

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

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

1.2 Критерии качества методов встраивания ЦВЗ

Качество метода встраивания ЦВЗ характеризуется степенью выполнения следующих критериев:

1) точность данных контейнера (визуальная неразличимость ЦВЗ);

2) стойкость ЦВЗ;

3) информационная ёмкость контейнера;

4) вычислительная сложность встраивания;

5) безопасность расположения ЦВЗ.

Далее перечисленные критерии определены для области методов встраивания в векторные картографические данные.

Точность данных контейнера или визуальная неразличимость ЦВЗ (fidelity) характеризует относительное сходство между исходной векторной картой и

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

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

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

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

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

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

Атаки на векторные картографические данные можно разделить на две категории:

1) геометрические атаки;

2) атаки на содержимое.

Наиболее известные геометрические атаки - это поворот, сдвиг, масштабирование и кадрирование. Преобразование поворота заключается во вращении векторной карты вокруг некоторой заданной точки на определенный угол. Операция сдвига выполняет перемещение всех объектов карты на заданное расстояние в определенном направлении. Масштабирование представляет собой изменение размера карты по обеим осям на конкретное значение. Кадрирование определяется как процесс выделения некоторого фрагмента карты и удаления всех объектов вне этого фрагмента. Геометрические преобразования сдвига, масштабирования и поворота также называют аффинными преобразованиями. Эти преобразования являются обратимыми и не ведут к потере информации.

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

Емкость (capacity) или вместимость цифровой векторной карты понимается как количество встроенных бит или общее число вершин, которые несут ЦВЗ.

Сложность (complexity) - вычислительная сложность алгоритма: время, требуемое для реализации процедуры встраивания ЦВЗ.

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

1.3 Существующие методы защиты векторных графических данных на основе встраивания ЦВЗ

Существующие методы встраивания ЦВЗ [2-36] детально рассмотрены в приложении А. В основе каждого метода лежит один из следующих подходов.

1) Нулевое встраивание ЦВЗ (Zero watermarking). Согласно данному подходу (используемому, например, в [12, 20]) для формирования ЦВЗ используются ключевые характеристики контейнера, т.е. те характеристики, по которым можно однозначно идентифицировать цифровую карту. При этом сформированный ЦВЗ не встраивается в защищаемые данные, а хранится в качестве эталона: на этапе верификации ЦВЗ формируется заново, после чего сравнивается с эталонным.

2) Адаптивное встраивание ЦВЗ (Adaptive watermarking). Как и в случае нулевого встраивания, ЦВЗ формируется в соответствии с некоторыми локальными характеристиками исходных данных, однако данный подход подразумевает, что сформированный ЦВЗ встраивается в защищаемые данные. Такой подход применяется, например, в [9, 10, 11, 22].

3) Классическое встраивание ЦВЗ (Classic watermarking). Здесь, в отличии от адаптивного подхода, встраиваемый ЦВЗ не зависит от локальных характеристик контейнера и может представлять собой цифровой сигнал заданного вида (например, битовую строку или растровое изображение). Такой подход применяется, например, в [4,5,6,17,18].

4) Составное встраивание ЦВЗ (Multiple watermarking). Данный подход (используемый, например, [13]) подразумевает использование нескольких ЦВЗ, отличающихся по стойкости, что позволяет одновременно решать сразу несколько задач защиты векторных данных, т.е. обеспечивать защиту авторских прав одновременно с защитой подлинности и целостности.

5) Встраивание ЦВЗ без потерь / обратимое встраивание ЦВЗ (Reversible/Lossless watermarking). В рамках такого подхода (используемого, например, в [15, 16, 25, 27]) обеспечивается возможность восстановления

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

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

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

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

Подходы, основанные на встраивании в пространство декартовых координат (например, [9, 17, 18, 27]) реализуются за счет внесения изменений непосредственно в значения координат вершин. Как правило, для добавления битов ЦВЗ в значении координаты выбираются младшие разряды, чтобы сохранить приемлемую точность объектов карты.

Непосредственное встраивание ЦВЗ может также осуществляться за счет задания пространства встраивания через полярные координаты, например, как предложено в [22].

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

Подходы, основанные на встраивании в топологию карты (например, как предложено в [5, 21]), реализуются за счет изменения топологических отношений векторных объектов (например, расстояние между вершинами объектов), что обеспечивает сохранение качества данных ГИС при преобразованиях сдвига и поворота. Среднее расстояние является наиболее известным примером пространства встраивания в топологического отношения.

Когда пространственная область задана блоками или кластерами, новые значения координат (например, как предложено в [17]) или топологические отношения (например, как предложено в [2, 4, 10, 25, 26]) вычисляются уже по предварительно сгруппированным данным. Разделение векторной карты на блоки обеспечивает достижение большей устойчивости к добавлению шума и удалению объектов, а также сохранение точности карты со встроенным ЦВЗ в допустимых пределах.

К преимуществам подходов, реализующих встраивание в пространственную область можно отнести следующие:

1) простота реализации;

2) низкая вычислительная сложность;

Список литературы диссертационного исследования кандидат наук Выборнова Юлия Дмитриевна, 2019 год

СПИСОК ЛИТЕРАТУРЫ

1. Abubahia, A. Advancements in GIS map copyright protection schemes - a critical review / A. Abubahia, M. Cocea // Multimedia Tools and Applications. -2017. - Vol. 76(10) . - P. 12205-12231.

2. Abubahia, A. A clustering approach for protecting GIS vector data / A. Abubahia, M. Cocea // Advanced Information Systems Engineering: 27th International Conference. - 2015. - Vol.1.- P. 133-147.

3. Abubahia, A. Exploiting vector map properties for GIS data copyright protection / A. Abubahia, M. Cocea // Proceedings of the 27th IEEE International Conference on Tools with Artificial Intelligence. - 2015. - Vol.1.- P. 575-582.

4. 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. 757-790.

5. Peng, Z. Blind watermarking scheme for polylines in vector geo-spatial data / Z.g Peng, M. Yue, X. Wu, Y. Peng // Multimedia Tools And Applications. - 2015. -Vol. 74. - P. 11721-11739.

6. Wang, Y. A multiple watermarking algorithm for vector geographic data based on coordinate mapping and domain subdivision / Y. Wang, C. Yang, C. Zhu // Multimedia Tools And Applications. - 2017. - P. 1-19.

7. Yan, H. A normalization-based watermarking scheme for 2D vector map data / H.Yan, L. Zhang, W. Yang // Earth Science Informatics. - 2017. - Vol. 10(4). -P. 471-481

8. Zope-Chaudhari, S. Copyright protection of vector data using vector watermark / S. Zope-Chaudhari, P. Venkatachalam, K. Buddhiraj // Geoscience and Remote Sensing Symposium. - 2017. - Vol. 1. - P. 6110-6113.

9. Ren N. Selective authentication algorithm based on semi-fragile watermarking for vector geographical data / N. Ren, Q. Wang, C. Zhu // 22nd International Conference on Geoinformatics. - 2014. - Vol. 1. - P. 1-6.

10.Da, Q. A Novel Hybrid Information Security Scheme for 2D Vector Map / Q. Da, J. Sun, L. Zhang, L. Kou, W. Wang, Q. Han, R. Zhou // Mobile Networks and Applications. - 2018. - Vol.1. - P. 1-9.

11.Wang, N. RST Invariant Fragile Watermarking for 2D Vector Map Authentication / N. Wang, J. Bian, H. Zhang // International Journal of Multimedia and Ubiquitous Engineering. - 2015.- Vol.10(4). - P. 155-172.

12.Peng, Y. A Zero-Watermarking Scheme for Vector Map Based on Feature Vertex Distance Ratio / Y. Peng, M. Yue // Journal of Electrical and Computer Engineering. - 2015. - Vol. 2015. - P. 1-6.

13.Peng, Y. Multipurpose watermarking for vector map protection and authentication / Y. Peng, H. Lan, M. Yue, Y. Xue // Multimedia Tools and Applications. - 2017. - Vol. 77(1). - P. 1-21.

14.Cao, L. High-capacity reversible watermarking scheme of 2D-vector data / L. Cao, C. Men, R. Ji // Signal, Image and Video Processing. - 2015. - Vol. 9. -P. 1387-1394.

15.Peng, F. A Reversible Watermarking for 2D Vector Map Based on Triple Differences Expansion and Reversible Contrast Mapping / F. Peng, Z.J. Yan, M. Long // International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage. - 2017. - Vol.1. - P. 147-158.

16.Wang, N. RST Invariant Reversible Watermarking for 2D Vector Map / N. Wang, X. Zhao, C. Xie // International Journal of Multimedia and Ubiquitous Engineering. - 2016. - Vol.11(2). - P. 265-276.

17.Ohbuchi, R., Ueda, H., Endoh, S.: Robust Watermarking of Vector Digital Maps / R.Ohbuchi, H. Ueda, S.Endoh, // Proceedings of IEEE International Conference on Multimedia and Expo. - 2002. - Vol. 1. - P. 577-580.

18.Voigt, M. Watermarking 2D-vector data for geographical information systems/ M. Voigt, C. Busch // Proceedings of the SPIE, security and watermarking of multimedia content. - 2002. - Vol. 4675. - P. 621-628.

19.Voigt M. Feature-based Watermarking of 2D-Vector Data // M. Voigt, C. Busch. In: Proc. of the SPIE, security and watermarking of multimedia content. - 2003. -Vol. 5020. - P. 359-366.

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

21.Wang C. Watermarking geographical data on spatial topological relations / Z. Peng, Y. Peng, L. Yu, J. Wang, Q. Zhao //. Multimed Tools Appl. - 2010. - Vol. 57(1). - P. 67-89.

22.Kim, J. Robust Vector Digital Watermarking Using Angles and a Random Table / J. Kim // Advances in Information Sciences and Service Sciences. - 2010. - 2(4)

23.Yan, H. A key points-based blind watermarking approach for vector geospatial data / H. Yan, J. Li, H. Wen // Comput Environ Urban Syst. - 2010. - Vol. 35(6). - P. 485-492.

24.Huo, X. A Watermarking Scheme Using Polyline and Polygon Characteristic of Shapefile / X. Huo, T. Seung, B. Jang, K. Kwon, S. Lee // Proceedings of 3rd International Conference on Intelligent Networks and Intelligent Systems (ICINIS). - 2010. - Vol. 1. - P. 1-3.

25.Cao, L. Iterative Embedding-Based Reversible watermarking for 2d-Vector Maps / L. Cao, C. Men, X. Li // Proceedings of 17th IEEE International Conference on Image Processing (ICIP). - 2010. - Vol. 1. - P. 3685-3688.

26.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 // Proceedings of 17th Korea-Japan Joint Workshop on Frontiers of Computer Vision . - 2011 . - Vol. 1. - P. 1-5.

27.Wang, N. Reversible Watermarking for 2-D Vector Map Authentication with Localization / N. Wang, C. Men // Computer Aided Design Journal. - 2012 . -Vol. 44(4). - P. 230-330.

28.Muttoo, S.K.Watermarking digital vector map using graph theoretic approach / S.K. Muttoo, V. Kumar //. Annals of GIS. - 2012. - Vol.18(2). - P. 135-146.

29.Chou, C.M. Affine-transformation-invariant public fragile watermarking for 3D model authentication / C. M. Chou, D. C.Tseng // IEEE Computer Graphics and Application. - 2009 . - Vol. 29(2). - P. 72-79.

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

31. Solachidis, V. Pitas Fourier descriptors watermarking of vector graphics images / V. Solachidis, N. Nikolaidis, I. Pitas // Proceedings of the International Conference On Image Processing. - 2001. - Vol.3. - P. 9-12.

32.Ohbuchi, R. Watermarking 2D vector maps in the mesh-spectral domain / R. Ohbuchi, H. Ueda, S. Endoh // Proceedings of International conference on shape modeling and applications. - 2003. - Vol. 1. - P. 216-228.

33.Tao, S. Watermarking Gis Data For Digital Map Copyright Protection / S. Tao, X. Dehe, L. Chengming, S. Jianguo // Proceedings of 24th International Cartographic Conference . - 2009 . - Vol. 1. - P. 1-9.

34.Zhang, L. New robust watermarking algorithm for vector data / L. Zhang, D. Yan, S. Jiang, T. Shi // Wuhan Univ J Nat Sci . - 2010 . - Vol. 15(5). - P. 403407.

35.Wang, C. Watermarking Vector Maps Based on Minimum Encasing Rectangle / C. Wang, L. Zhang, B. Liang, H. Z., W. Du and Y. Peng // Proceedings of International Conference on Intelligent Computation Technology and Automation (ICICTA) . - 2011 . - Vol. 1. - P. 28-29.

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

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

38.Rhoad, R. Geometry for Enjoyment and Challenge / R. Rhoad — McDougal Littell, 1991. - 784 p.

39.Выборнова, Ю.Д. Метод защиты векторных карт с использованием изображения ЦВЗ как вторичного контейнера / Ю.Д. Выборнова, В.В. Сергеев // Компьютерная оптика. - 2019. - Т. 43, № 3.

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

41.Сойфер, В.А. Теоретические основы цифровой обработки изображений: / В.А. Сойфер, В.В. Сергеев, С.Б. Попов, В.В. Мясников // Учебное пособие. - 2000. - Самара: Самарский государственный аэрокосмический университет имени академика С.П.Королева. - 256 с.

42.Blum, L. A simple unpredictable pseudo-random number generator/ L. Blum, M. Blum, M.Shub // SIAM Journal on Computing. - 1986. - Vol. 15(2). - P. 364383.

43.Стасев, Ю. В., Потий, А.В., Избенко, Ю.А. Исследование методов криптоанализа поточных шифров [Электронный ресурс]. - Режим доступа: http: //www.nrjetix.com/fileadmin/doc/publications/articles/stasev_potiy_izbenko _ru.pdf (10.11.2016).

44.Vybornova, Y.D. Password-based key derivation function as one of Blum-BlumShub pseudo-random generator applications / Y.D. Vybornova // Procedia Engineering. - 2017. - Vol. 201. - P. 428-435.

45.Gonzalez, R.C. Digital Image Processing / R. C. Gonzalez, R. E. Woods - New Jersey: Prentice Hall, 2002.- 943 p.

46.Fadnavis, S. Image interpolation techniques in digital image processing: an overview / S. Fadnavis // Int. Journal of Engineering Research and Applications. - 2014.- Vol. 4(10). - P.70-73.

47.Vybornova, Y.D. Application of spatial interpolation methods for restoration of partially defined images / Y.D. Vybornova // CEUR Workshop Proceedings. -2018. - Vol. 2210. - P. 89-95.

48.Watson, D. F. A refinement of inverse distance weighted interpolation / D. F. Watson, G. M. Philip // Geo- Processing. -1985.- Vol.2.- P.315-327.

49.Mitas, L. Spatial interpolation / L. Mitas, H. Mitasova // Geographical Information Systems: Principles, Techniques, Management and Applications. -1999.- P. 481-492.

50.Jassim, F.A. Image interpolation using kriging technique for spatial data / F. A. Jassim , F.H. Altaany // Canadian Journal on Image Processing and Computer Vision.-2013.- Vol. 4(2). - P. 91-96.

51.Panagiotopoulou, A. Super-resolution image reconstruction employing Kriging interpolation technique / A. Panagiotopoulou, V. Anastassopoulos // Proceedings of IEEE Int. Workshop Syst., Signals and Image Processing.- 2007.- Vol.1.- P. 144-147.

52.Ruiz-Alzola, J. Kriging filters for multidimensional signal processing / J. Ruiz-Alzola, C. Alberola-Lopez, C.F. Westin // Signal Processing.- 2005. - Vol. 85.-P. 413-439.

53.Panggabean, M. Chroma interpolation using windowed kriging for color-image compression-by-network with guaranteed delay / M. Panggabean, L. R0nningen // Proceedings of IEEE EURASIP 17th International Conference on Digital Signal Processing (DSP).- 2011.- Vol.1.- P. 1-6.

54.Dumitru, P.D. Comparative study regarding the methods of interpolation / P. D. Dumitru, M. Plopeanu, D. Badea // Recent Advances in Geodesy and Geomatics Engineering.- 2013.- Vol.1.- P. 45-52.

55.Гашников, М.В. Методы компьютерной обработки изображений, под ред. В.А. Сойфера - 2 изд., испр. / М.В. Гашников, Н.И. Глумов, Н.Ю. Ильясова, В.В. Мясников, С.Б. Попов, В.В. Сергеев, В.А. Сойфер, А.Г. Храмов, А.В. Чернов, В.М. Чернов, М.А. Чичева, В.А. Фурсов. - М.: Физматлит, 2003. -784 с.

56.Candra, R. The Implementation of an Efficient Zigzag Scan / R. Candra, S. Madenda, S.A. Sudiro, M. Subali // Journal of Telecommunication, Electronic and Computer Engineering. - 2017. - № 9 (2). - P.95-98.

57.Сергеев, В.В. Обработка изображений с использованием развертки Гильберта-Пеано / В.В. Сергеев // Автометрия. - 1984. - №2. - С.30-36.

58.Lee, D.T. Two algorithms for constructing a delaunay triangulation / D.T. Lee, B.J. Schachter // International Journal of Computer and Information Sciences.-1980.- Vol. 9(3).- P. 219-242.

59.Waterloo Greyscale set 2 [Электронный ресурс] Repository - Waterloo Fractal -University of Waterloo — Режим доступа: URL: http://links.uwaterloo.ca/Repository.html (11.05.19).

60.Ahuja, N. Dot pattern processing using Voronoi neighborhoods / Ahuja, N. // IEEE Transactions on Pattern Analysis and Machine Intelligence. -1982. - Vol. 4(3). - P. 336-343.

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

А. 1. Методы встраивания в пространственную область

Первые схемы встраивания в пространственную область [17-19] заключались в изменении координат вершин с учетом контроля географического положения, допустимых отклонений и точности данных, однако они не топологию объектов, чем и обусловлена их низкая стойкость к преобразованиям.

Ohbuchi [17] предложил следующий алгоритм встраивания цифровых водяных знаков в векторные карты: бит ЦВЗ встраивается путем замены среднего значения координат множества вершин, находящихся в прямоугольной области, созданной на карте путем адаптивного разбиения карты. Безопасность и надежность ЦВЗ были повышены за счет использования в процессе встраивания последовательностей псевдослучайных чисел. Бинарный водяной знак длиной 185-708 бит повторно встраивался в зависимости от плотности или размера данных карты. Однако, данная схема требует наличия исходной векторной карты для извлечения ЦВЗ. Это означает, что данный метод не является слепым. Также данный метод не является стойким к аффинным и топологическим преобразованиям, поскольку не учитывает геометрические свойства цифровой карты.

Busch и Vogit [18] представили высокопроизводительный алгоритм встраивания ЦВЗ для цифровых карт. В данном алгоритме ЦВЗ встраивается путем замены координат x и y в пределах допустимого отклонения данных. В алгоритме также используется блочный код для восстановления недостающих данных в процессе детектирования. Однако, данная схема является стойкой только к атакам, изменяющим координаты в пределах допустимого отклонения.

Также авторами Busch и Vogit [19] была представлена следующая схема встраивания на основе признаков. Выбираются два дизъюнктивных множества элементов сетки, каждый из которых разделяется на две части, затем изменяется расстояние точек линий внутри каждой части относительно опорного элемента,

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

Современные схемы встраивания в пространственную область рассматривают топологию вершин, географические свойства объектов и структуру слоев.

Li et al. [20] предложили следующую схему нулевого встраивания ЦВЗ в векторные карты: ЦВЗ вычисляется на основе топологических характеристик исходных данных и затем регистрируется органами власти для нотариального засвидетельствования и аутентификации. ЦВЗ вычисляется следующим образом: карта делится на треугольные области в зависимости от топологических характеристик, затем для каждой треугольной области вычисляются топологические характеристики. Поскольку ЦВЗ никуда не встраивается, точность исходных данных не меняется и, соответственно, их качество сохраняется. Таким образом, данный метод может одновременно обеспечить решение проблемы визуальной неразличимости ЦВЗ и обеспечить требуемую стойкость. Однако, здесь возникает проблема защищенного хранения и передачи такого ЦВЗ.

Wang et al. [21] представили схему встраивания на основе топологических связей полигонов. Во время встраивания ЦВЗ вычисляется минимальный ограничивающий прямоугольник (МОП) для векторных данных. МОП — это прямоугольник минимальной площади, который полностью покрывает все вершины карты. МОП применяется для того, чтобы сохранить синхронизацию во время встраивания и извлечения. После вычисления МОП вычисляется метрика измерения пространственных топологических связей пар полигонов, и бит ЦВЗ встраивается в метрическую меру путем масштабирования области полигона. Данная схема является стойкой к аффинным преобразованиям, удалению вершин, интерполяции данных и добавлению шума. Однако, данная схема не является стойкой к кадрированию, поскольку множество пар полигонов, используемое для

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

Kim [22] представил схему слепого встраивания для векторных карт. В основе данного алгоритма лежит использование углов векторной карты и случайной таблицы. Процедура встраивания ЦВЗ осуществляется следующим образом: сначала выбирается произвольно выбираются три смежные вершины, образующие угол, затем целочисленное значение вычисленного угла изменяется при помощи случайной таблицы, после чего измененный угол отображается в точки (координаты), которые использовались при вычислении угла. Другими словами, координаты изменяются согласно значению нового измененного угла. Процедура извлечения ЦВЗ приблизительно такая же, как и процедура встраивания. В этой схеме, после встраивания ЦВЗ топология векторной карты сохраняется. Результаты экспериментов показывают, что предложенная схема является стойкой к сдвигу и масштабированию, а также к удалению вершин и добавлению объектов. Тем не менее, недостатком данной схемы является то, что изменение углов приведет к невозможности извлечения ЦВЗ.

Yan et al. [23] представил стойкий слепой метод встраивания на основе ключевых точек слоев, который заключается в следующем. Для встраивания выбираются слои с наибольшим количеством вершин. На основе диаграммы Вороного [60] вычисляются ключевые точки для встраивания ЦВЗ. При этом учитываются точки пересечения, топологические связи линий в показательных слоях, содержащих линии, и углы отклонения в показательных слоях, содержащих полигоны. Символ ЦВЗ встраивается в наименее значимые биты x или y координаты ключевых точек. Данная схема является стойкой к аффинным преобразованиям и добавлению шума, но не является стойкой к удалению вершин и кадрированию.

Huo et al. [24] предложили слепой метод встраивания для защиты авторских прав векторных карт ГИС, основанный на ESRI шейпфайле. В основе алгоритма лежит использование длин полилиний или периметров полигонов. ЦВЗ

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

Cao et al. [25] предложили реверсивный алгоритм для двумерных векторных карт на основе итеративного встраивания, который состоит из следующих шагов: сначала группируются вершины каждой полилинии, затем в качестве данных для итеративного встраивания выбираются только сильно коррелирующие наборы данных. После этого выполняется итеративное встраивание путем реверсивного изменения координат вершин медиан для каждого выбранного блока встраивания. Первоначальные векторные данные могут быть точно восстановлены путем извлечения встроенной информации. Теоретический анализ и комплексные экспериментальные проверки показали, что данный алгоритм демонстрирует высокие показатели ёмкости и точности.

Huo et al. [26] предложили схему встраивания на основе полигонов типа ESRI с использованием алгоритма кластеризации k-средних (k-means). Данная схема встраивания разбивает множество всех полигонов на кластеры с помощью алгоритма k-средних. Для того, чтобы встроить ЦВЗ длиной k бит необходимо разделить множество полигонов на k кластеров в соответствии с распределением центров полигонов. ЦВЗ встраивается в среднюю длину расстояний всех полигонов в кластере путем odd-even кодирования. Координаты вершин изменяются в соответствии с новыми средними длинами расстояний полигонов со встроенной информацией. Данный метод является стойким к различным геометрическим атакам.

Wang et al. [27] представили реверсивный алгоритм встраивания хрупких ЦВЗ в векторные карты. В данной работе ЦВЗ вычисляется для каждой группы пространственных объектов и встраивается реверсивным способом. При этом исходное положение каждого объекта отмечается с помощью интерполированных вершин. Поскольку использование меток для каждого объекта обеспечивает высокую точность локализации искажений, реверсивный метод встраивания

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

В [28] авторами Muttoo и Kumar концепция дайджеста, используемая для аутентификации сообщений, расширена до встраивания ЦВЗ в цифровую карту. Триплет дайджеста карты создается на основе различных характеристик цифровой карты, кода поставщика и кода клиента. Вычисляются два 160-битных значения хеш-функции с использованием алгоритма защищенного хеширования (SHA1) и один 128-битный дайджест с использованием алгоритма дайджеста сообщения (MD5). Вычисленные значения затем встраиваются в последовательность вершин с использованием теории графов таким образом, что любое изменение в карте изменяет подграф, который является цифровым водяным знаком. На самом деле, ЦВЗ никуда не встраивается: алгоритм создает уникальный дайджест для каждой карты, который ставится в соответствие вершинам карты. Авторы заявляют, что метод может быть использован не только для подтверждения прав собственности, но и для проверки подлинности. Однако, стойкость метода очень слабо обоснована и не подтверждена экспериментальными исследованиями.

Lee and Kwon [4] предложили слепой метод встраивания, стойкий к атакам на данные и на слои, который не нарушает точность данных и обеспечивает визуальную неразличимость ЦВЗ. Алгоритм состоит из следующих шагов: сначала выбираются слои с наибольшей плотностью полилиний и полигонов в качестве целевых слоев. Таким образом обеспечивается стойкость к атакам на слои. Затем полилинии и полигоны в целевых слоях группируются и ЦВЗ встраивается в геометрическое распределение каждой группы полигонов и полилиний. При этом все вершины полигонов и полилиний, участвующих во

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

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

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

Abubahia and Cocea [2] предложили улучшенный алгоритм Huo et al., в основе которого лежит использование ограничивающего прямоугольника (bounding box). Сначала вычисляются центры полигонов с использованием информации об ограничивающем прямоугольнике для каждого полигона. Затем выполняется кластеризация вычисленных центров с помощью алгоритма k-медоидов. От числа кластеров зависит, во сколько полигонов будет встроен ЦВЗ.

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

В [3] авторы Abubahia and Cocea представили аналогичную схему, но здесь кластеризация осуществляется с помощью алгоритма k-means. Результаты исследований показали, что результат встраивания не зависит от алгоритма кластеризации.

В [5] авторами Peng et. Al. предложена слепая схема встраивания ЦВЗ для полилиний. В предложенной схеме отношение расстояний между характерными вершинами элементов (feature vertex distance ratio, FVDR) строится на основе характерных точек полилиний. Что касается заполнения контейнера, FVDR слегка модифицируется методом QIM для встраивания соответствующего бита ЦВЗ. Каждый бит ЦВЗ встраивается сразу в несколько полилиний. Предложенная схема является устойчивой к геометрическим преобразованиям, добавлению шума, а также ко всем типам атак на объекты и вершины. К недостаткам схемы можно отнести пониженную ёмкость (поскольку один и тот же бит ЦВЗ встраивается в несколько полилиний) и отсутствие данных по визуальной неразличимости.

В [12] авторы Peng et. Al. представили схему нулевого встраивания ЦВЗ, реализуемую аналогичным образом. Отсутствие необходимости изменять координаты вершин позволяет сохранить точность векторной карты, однако порождает задачу защищенного хранения/передачи ЦВЗ.

В [11] авторами Wang et. Al предложена схема аутентификации (проверки подлинности) векторных карты, инвариантная к аффинным преобразованиям.

ЦВЗ генерируется на основе сложения результатов хеширования разностей логарифмических радиусов и встраивается согласно инвариантому алгоритму Chou and Tseng [29] . Таким образом предлагаемый метод устойчив к аффинным преобразованиям, но чувствителен к злоумышленным атакам. Поскольку в каждый объект встраивается уникальная метка, указывающая исходное местоположение объекта, алгоритм может точно обнаруживать группы объектов, повергшиеся несанкционированным изменениям. Чтение вершин происходит согласно меткам объектов, что обеспечивает устойчивость схемы к операции переупорядочивания вершин. Однако, метод не демонстрирует достаточной точности.

В [16] авторами Wang et. Al. описан метод встраивания обратимых ЦВЗ, инвариантный к аффинным преобразованиям. Предлагаемый метод позволяет восстанавливать исходное содержимое карты после извлечения ЦВЗ. Встраивание осуществляется путем вычисления евклидовых расстояний от характерной вершины до каждой и разделения их на равные сегменты с использованием нормализованного шага квантования, и последующего перемещения каждой вершины в соответствующем сегменте обратимым образом. Кроме того, степень вносимыхискажений можно контролировать, изменяя параметр встраивания. Кроме того, предлагаемый способ обеспечивает низкую вычислительную сложность. Недостатком схемы является низкая ёмкость.

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

ограничения к некоторым вероятным атакам, таким как добавление / удаление объектов, добавление шума и переупорядочение вершин.

В [13] авторами Peng et. Al. предлагается универсальная схема встраивания ЦВЗ, которая заключается в одновременном встраивании одного стойкого и двух хрупких ЦВЗ. Стойкий ЦВЗ решает задачу защиты авторских прав, тогда как хрупкие ЦВЗ необходимы для определения и локализации несанкционированных изменений. Чтобы избежать пересечения двух видов ЦВЗ, стойкий ЦВЗ встраивается в характерные точки объектов на карте (для полилиний прнименяется модификация алгоритма Дугласа-Пекера и алгоритм углов отклонения для полигонов), в то время как хрупкие ЦВЗ встраиваются в нехарактерные точки. Благодаря независимости характерных и нехарактерных точек, стойкий и хрупкие ЦВЗ могут быть независимо извлечены. Стойкий ЦВЗ сохраняется при геометрических преобразованиях, добавлению и удалению вершин, добавлении шума и переупорядочивании вершин. Хрупкие ЦВЗ позволяют детектировать добавление, удаление и изменение объектов.

В [6] авторами Wang et. Al. предложен алгоритм составного встраивания ЦВЗ в векторные картографические данные. В частности, сначала вершины отображаются в логические области на основе построенной функции преобразования. Затем на основе метода дихотомии каждая область разделяется на блоки в зависимости от количества встраиваемых ЦВЗ, после чего каждый ЦВЗ внедряется в соответствующий блок с использованием операции квантования. Результаты экспериментов показывают, что предлагаемый алгоритм обладает хорошей устойчивостью к добавлению и удалению вершин, удаление объектов и кадрированию. Для достаточно больших карт метод обеспечивает высокую емкость. Однако, следует обратить внимание на то, что процедура обнаружения ЦВЗ представляет собой эвристический алгоритм, поскольку на этапе извлечения количество встроенных ЦВЗ является неопределенным. Кроме того, алгоритм не обеспечивает стойкость к аффинным преобразованиям.

В [7] авторами Yan et. Al. предложен метод защиты авторских прав на векторные карты. Сначала все координаты нормализуются, а пиксели

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

В [10] авторами Рт§ап е1 А1. предложена схема защиты информации для линейных объектов цифровой векторной карты. Сначала полилинии объединяются в непересекающиеся множества. Затем выбираются вершины, которые представляют собой метки, содержащие информацию о локации ключевых объектов и корреляции с соседними группами, что необходимо для достижения определения факта фальсификации. В то же время, метод корреляции групп объектов, основанный на добавлении вершин, разработан, чтобы противостоять атаке удаления объектов. Затем осуществляется переход к полярным координатам для получения аутентификационных данных о соответствующих группах признаков. Аутентификационные ЦВЗ и метки в конечном итоге встраиваются в цифровую карту с помощью стратегии встраивания ЦВЗ, инвариантного к афинным преобразованиям [29]. Данный метод встраивания ЦВЗ наследует свойства инвариантности, а также позволяет обнаруживать добавление, изменение и удаление объектов. Однако для корректной работы метода необходимо, чтобы полилинии содержали хотя бы шесть вершин.

А.2.Методы встраивания в частотную область

Кйашига [30] предложил метод встраивания ЦВЗ в набор полилиний с использованием дискретного преобразования Фурье.

Solachidis [31] предложил извлекать координаты вершин из векторных данных, а затем встраивать информацию в коэффициенты ДПФ этих координат. Однако такой метод может привести к искажению данных.

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

Tao et al. [33] предложили слепую схему встраивания, основанную на дискретном преобразовании Фурье, которая заключается в следующем. Сначала осуществляется ДПФ последовательности вершин, извлеченной из векторной карты. Затем фаза ДПФ делится в соответствии с величиной шага квантования, после чего в фазу встраивается ЦВЗ. Результаты экспериментов демонстрируют стойкость данного алгоритма к повороту и сдвигу векторной карты, а также к изменению формата.

Zhang et al. [34] предложили встраивать бинарный ЦВЗ в коэффициенты одномерного вейвлет-преобразования характерных точек, полученных с использованием алгоритма Дугласа-Пекера.

Wang et al. [35] представили схему слепого встраивания для векторной карты на основе минимального ограничивающего прямоугольника. После разбиения карты на ячейки на основе МОП и построения массива весов элементов сетки, пространственные данные преобразуются в частотную область с помощью ДКП. ЦВЗ встраивается в среднечастотные коэффициенты ДКП. Во время генерации карты со встроенной информацией распределение вершин слегка изменяется. Данный алгоритм является стойким к таким атакам, как сдвиг, масштаб и поворот. Более того, стойкость алгоритма к геометрическим атакам остается инвариантной для различных значений величины сдвига, угла поворота и коэффициента масштабирования.

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

В [8] авторы /оре-СИаиЛап и Уепка1асИа1аш продолжили исследование разработанного метода. В результате экспериментов было установлено, что метод демонстрирует стойкость к сдвигу, масштабированию, добавлению/удалению вершин, кадрированию, добавлению шума, а также к изменению файлового формата. Метод не является стойким к сжатию, а стойкость к преобразованию поворота и добавлению/удалению объектов осталась не исследованной.

ПРИЛОЖЕНИЕ Б МЕТОДЫ ПРОСТРАНСТВЕННОЙ ИНТЕРПОЛЯЦИИ

Б. 1. Метод обратных взвешенных расстояний

Метод обратных взвешенных расстояний (Inverse Distance Weighting, IDW) — это детерминированный алгоритм, в основе которого лежит предположение о том, что значения в ближних точках сильнее оказывают влияние на прогнозируемое значение, нежели значения в точках, которые расположены дальше [48].

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

я К?

Y ( zo) = ( Z ) = -

0, _

м к

i=1

где У (г0) - оцениваемое значение точки в некотором местоположении г0, а У(^), У(^),..., У(гп) - значения опорных точек.

Веса пропорциональны обратному расстоянию, возведенному в степень /. В результате, по мере увеличения расстояния веса быстро уменьшаются. Скорость уменьшения весов зависит от значения /. Так, при /л = 0 веса Я1 будут одинаковы,

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

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

n

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

Б. 2. Метод кригинга

Кригинг [50] - статистический метод интерполяции который может предсказывать неизвестные значения по близлежащим точкам. Аналогично методу ГО', веса присваиваются для каждой точки в соответствии с расстоянием до неизвестного значения. Однако здесь оценка строится с учетом статистических характеристик.

На сегодняшний день опубликовано не так много исследований, связанных с кригингом в задачах обработки изображений [50-53].

Основная формула кригинга:

7 ( z0) = £AY ( ),

t=1

где Y (z ), Y (z2),..Y (zn) - опорные точки, а Y (z0) - точка, значение которой

n

мы хотим оценить. Также, следует учесть, что . = 1.

¿=1

Основная задача заключается в определении весов А таким образом, чтобы минимизировать дисперсию оценки, учитывая требование несмещенности E {Y (zo) - Y (z)} = 0.

Существует несколько методов кригинга, которые различаются способами получения весовых компонент А • Метод обыкновенного кригинга (ordinary

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

Процесс оценки начинается с построения эмпирической вариограммы, для всех пар местоположений, разделенных расстоянием h:

average((Y(zt) - Y(z,,))2)

V (h) =

Для того, чтобы перейти от пространственного описания к прогнозу, необходимо определиться с выбором модели (кривой, накладываемой на эмпирическую вариограмму).

Характеристики, необходимые для описания моделей, представлены на рисунке Б.1. Как видно из рисунка, самородок - это точка пересечения вариограммы с осью ординат, а порог - это значение, в котором модель выравнивается. Расстояние до порогового значения называется диапазоном влияния. Точки, вышедшие за границу диапазона, не будут оказывать влияние на оцениваемое значение.

а

i4 V ------ J L_ о Q. О П. г

4 диапазон >

Рисунок Б.1 - Диапазон, порог и самородок

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

Б.3. Триангулированная нерегулярная сеть

Метод интерполяции на основе триангулированной нерегулярной сети (TIN, Triangulated Irregular Network) использует триангуляцию точек данных для получения двумерной функции, которая используется для оценки неизвестных значений внутри каждого треугольника [49].

Как правило, нерегулярную сеть получают при помощи триангуляции Делоне [58]: точки соединяются отрезками таким образом, чтобы для любого полученного треугольника все точки, за исключением его вершин, лежали вне

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

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

5) любая точка на поверхности расположена максимально близко к опорной;

6) метод не зависит от порядка обработки точек.

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

ПРИЛОЖЕНИЕ В

АКТ ОБ ИСПОЛЬЗОВАНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ В АО «САМАРА-

ИНФОРМСПУТНИК»

об использовании результатов диссертации Ю. Д. Выборновой «Метод защиты векторных данных на основе встраивания растровых цифровых водяных знаков» в акционерном обществе «Самара-Информспутник»

Комиссия в составе ведущего инженера, к. т. н. А, В. Чернова и инженера-математика А. В. Сергеева, рассмотрев диссертацию Ю. Д. Выборновой. представляемую на соискание ученой степени кандидата технических наук по специальности 05.13.17- Теоретические основы информатики, подтверждает, что разработанные в диссертационной работе методы, алгоритмы и программные модули были использованы в составе программного обеспечения, разработанного в рамках хоздоговорной работы № 0148200001618000059 «Актуализация геоинформационной базы данных земель сельскохозяйственного назначения Московской области» от 01.11.2018 (заказчик • Министерство сельского хозяйства и продовольствия Московской области) для обеспечения защиты векторных картографических данных от несанкционированного распространения.

УТВЕРЖДАЮ

АКТ

Инженер-математик

Ведущий инженер, к. т. н.