Защита авторства изображений с использованием цифровых водяных знаков

Размещено на http://www.Allbest.Ru/

Министерство образования Республики Беларусь

Учреждение образования «Гродненский государственный университет им. Янки Купалы»

Физико-технический факультет

Кафедра информационных систем и технологий

Специальность: I-38.02.01 Информационно-измерительная техника

Дипломный проект

Тема:

Защита авторства изображений с использованием цифровых водяных знаков

Разработал: Поведайко А.А.

Руководитель: Ассанович Б.А.

Гродно 2014



Оглавление

• Введение
• 1. Обзор методов поиска особых точек изображения
• 1.1 Сущность и понятие особых точек
• 1.2 Методы поиска особых точек
• 1.3 Дескриптор особых точек
• 1.4 Цифровой водяной знак
• 1.4.1 Жизненный цикл цифровых водяных знаков
• 1.4.2 Свойства цифровых водяных знаков
• 1.4.3 Классификация
• 1.4.4 Применение
• 1.5 Постановка задач дипломного проекта
• 2. Детектор Харриса определения особых точек
• 2.1 Алгоритм работы
• 2.2 Построение минимального остовного графа
• 2.3 Дискретное преобразование Фурье
• 3. Реализация метода записи особых точек
• 3.1 Система Matlab
• 3.2 Алгоритм и блок-схема поиска и записи особых точек
• 3.3 Алгоритм и блок-схема введения ЦВЗ для защиты авторства изображения
• 3.4 Исследование работы программы
• 4. Технико-экономическое обоснование разработки программы
• 5. Техника безапосности и охрана труда при разработки программы
• 5.1 Требования охраны труда перед началом работы
• 5.2 Требования охраны труда во время работы
• 5.3 Требования охраны труда по окончании работы
• 5.4 Требования охраны труда в аварийных ситуациях
• 6. Ресурсо- и энергосберегающие технологии, использованные при разработки программы
• Заключение
• Список использованных источников
• Приложение


Введение

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

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

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

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

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

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

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



1. Обзор методов поиска особых точек изображения

1.1 Сущность и понятие особых точек

Особые точки (в разных источниках - features/characteristic points/local feature points/interest point/локальные особенности) - “хорошо различимые” фрагменты изображения. Это точки (пиксели) с характерной (особой) окрестностью - т.е. отличающиеся своей окрестностью от всех соседних точек. Классический пример локальной особенности - вершина угла (а не какая-то произвольная точка на прямой или на однородном фоне). Описываются вектором признаков, вычисляемых на основе интенсивности/градиентов или других характеристик точек окрестности. Используя особые точки, можно анализировать как изображения целиком, так и объекты на них. Хорошие характерные точки позволяют справиться с изменением масштаба, ракурса и перекрытиями сцены или объекта.

Локальные особенности - краеугольный камень во многих высокоуровневых алгоритмах компьютерного зрения: отслеживание (tracking) и распознавание (recognition) объектов, 3d-реконструкция и навигация (SLAM и loop-closure). Используя характерные точки, можно вычислить сдвиг (disparity) между двумя изображениями, произвести сегментацию на основе сдвига элементов сцены, рассчитать фундаментальную матрицу для калибровки стерео-пары или проиндексировать изображения для поиска.

Локальные особенности должны быть:

- повторяемыми - должны находиться в одном и том же месте сцены независимо от ракурса и освещения

- локальными - (как родинки у человека) - должны быть расположены в малой области и не страдать от перекрытий

- компактными - по сравнению с общим числом пикселей изображения их должно быть в разы меньше

- значимыми - уникальными - каждая особенность должна иметь свое собственное описание (чтобы сложно было перепутать их между собой) [1].

1.2 Методы поиска особых точек

Основными методами поиска особых точек являются:

1) детектор Моравеца;

2) детектор MSER's;

3) детектор FAST;

4) детектор Харриса и Стефана;

5) детектор на основе LoG (Laplacian of Gaussian) и DoG (Difference of Gaussian);

Детектор Моравеца

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

Детектор Моравеца (Moravec) [3] является самым простым детектором углов. Автор данного детектора предлагает измерять изменение интенсивности пикселя (x,y) посредством смещения небольшого квадратного окна с центром в (x,y) на один пиксель в каждом из восьми принципиальных направлений (2 горизонтальных, 2 вертикальных и 4 диагональных). Размер окна обычно выбирается равным 3Ч3, 5Ч5 или 9Ч9 пикселей. Детектор работает в несколько шагов:

Для каждого направления смещения

вычисляется изменение интенсивности:

(1)

где - интенсивность пикселя с координатами в исходном изображении.

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

(2)

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

Отсекаются пиксели, в которых значения оценочной функции ниже некоторого порогового значения.

Удаляются повторяющиеся углы с помощью процедуры NMS (non-maximal suppression). Все полученные ненулевые элементы карты соответствуют углам на изображении.

Основными недостатками рассматриваемого детектора являются отсутствие инвариантности к преобразованию типа «поворот» и возникновение ошибок детектирования при наличии большого количества диагональных ребер. Очевидно, что детектор Моравеца обладает свойством анизотропии в 8 принципиальных направлениях смещения окна.

Детектор Харриса и Стефана

Детектор Харриса (Harris) [4] строится на основании детектора Моравеца и является его улучшением, т.к. для него характерна анизотропия по всем направлениям. Харрис и Стефан (Stephen) вводят в рассмотрение производные по некоторым принципиальным направлениям, раскладывают функцию интенсивности в ряд Тейлора:

(3)

Как следствие, изменение интенсивности в каждом пикселе можно рассматривать как функцию следующего вида:

(4)

(5)

В матрице Харриса (автокорреляционная матрица), как правило, выбирают взвешенную свертку производных c весовыми коэффициентами Гауссова окна (окно размером 33 пикселя с коэффициентами 0.04, 0.12, 0.04, 0.12, 0.36, 0.12, 0.04, 0.12, 0.04 - представление по строкам). Отметим, что матрица Харриса симметричная и положительно полуопределенная. Вычисляя собственные значения полученной матрицы, точки изображения можно классифицировать на ребра и углы:

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

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

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

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

Детектор MSER's

При разработке детектора MSER (Maximally Stable Extremal Regions, Matas и др., 2002) решается проблема инвариантности особых точек при масштабировании изображения. Детектор [5] выделяет множество различных регионов с экстремальными свойствами функции интенсивности внутри региона и на его внешней границе.

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

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

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

- обновление списка точек, входящих в состав компоненты;

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

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

Детектор FAST

Описанные ранее детекторы определяют особых точек на изображении, в частности, углов, применяя некоторую модель или алгоритм напрямую к пикселям исходного изображения. Альтернативный подход состоит в том, чтобы использовать алгоритмы машинного обучения для тренировки классификатора точек на некотором множестве изображений. FAST-детектор (Features from Accelerated Test) [6] строит деревья решений для классификации пикселей.

Для каждого пикселя изображения рассматривается окружность с центром в этой точке, которая вписана в квадрат со стороной 7 пикселей ( см.рис.1). Окружность проходит через 16 пикселей окрестности.

Рис. 1. Рабочая окрестность пикселя при использовании FAST детектора

Каждый окрестный пиксель относительно центрального () может находиться в одном из трех состояний:

(6)

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

Детектор на основе LoG (Laplacian of Gaussian) и DoG (Difference of Gaussian)

В качестве детектора, не чувствительного к масштабу была предложена концепция блобов (Blobe) - каплевидных окрестностей, в центре которых расположена особая точка. Для определения таких окрестностей использовались лапласианы гауссианов (LoG - ЛОГ-фильтром) или разница гауссианов (DoG - DOG-фильтром). Изображение, представляем в виде функции. Лапласиан - сумма вторых частных производных функции в точке.

(7)

Гауссиан - это просто гауссова функция - которой обрабатывают изображение.

(8)

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

1.3 Дескриптор особых точек

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

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

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

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

- Репрезентативность. Количество признаков должно быть достаточным, чтобы разумное число признаков детектировалось даже на небольшом изображении объекта.

- Точность. Признаки должны быть точно продетектированными по отношению к масштабу и форме объекта.

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

Дескрипторы ключевых точек. ( см. Приложение 1)

1.4 Цифровой водяной знак

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

Невидимые ЦВЗ внедряются в цифровые данные, но не могут быть восприняты как таковые.

Рис. 2. Пример цифрового водяного знака (слева нормальное изображение, справа помеченное, в центре разница между изображениями с увеличенной яркостью)

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

1.4.1 Жизненный цикл цифровых водяных знаков

Так называемый, жизненный цикл ЦВЗ может быть описан следующим образом (рис. 3).

Рис. 3. Жизненный цикл ЦВЗ

Сначала в сигнал-источник в доверенной среде внедряются водяные знаки при помощи функции . В результате получается сигнал . Следующий этап - распространение через сеть или любым другим способом. Во время распространения на сигнал может быть совершена атака. У получившегося сигнала водяные знаки могут быть потенциально уничтожены или изменены. На следующем этапе функция обнаружения пытается обнаружить водяные знаки , а функция вытащить из сигнала внедрённое сообщение. Этот процесс потенциально может совершать злоумышленник.

1.4.2 Свойства цифровых водяных знаков

ЦВЗ классифицируются по 7 основным параметрам: объём, сложность, обратимость, прозрачность, надёжность, безопасность и верификация.

Объём информации. Различают внедряемый и извлекаемый объём. Внедряемый объём -- это просто размер сообщения , которое внедряется в сигнал. Её можно определить как:

(9)

Рассматривается также относительный внедряемый объём:

(10)

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

(11)

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

(12)

Объём обычно нормируется на длину сообщения. Рассматриваются иногда такие параметры как ёмкость в секунду и емкость, отнесённая к :

(13)

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

(14)

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

(15)

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

Средняя сложность, нормированная на длину сигнала или объём:

(16)

(17)

Максимальная сложность, нормированная на длину сигнала или объём:

(18)

(19)

Минимальная сложность, нормированная на длину сигнала или объём:



(20)

(21)

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

Прозрачность. По данным эталонному и тестовому сигналам, функция прозрачности Т измеряет расхождение между этими сигналами . Результат вычисления заключён в интервале [0,1], где 0 соответствует случаю, когда система не может распознать в версию , и 1, если наблюдатель не может отличить эти два сигнала.

Надёжность. Сначала надо ввести понятие «успешного обнаружения».

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

(22)

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

(23)

Для схем с ненулевым внедрённым сообщением важно знать, что хотя бы одно (в случае множественного внедрения) сообщение расшифровалось успешно. Если, к примеру, сообщение внедряется раз, и извлечённый объём returns, на 10 % восстановима, то непонятно, какие именно из сообщений повреждены. Тем не менее, такое определение бывает полезным, если знать, что хотя бы одно из сообщений не повредилось, что отражено в следующем выражении:

(24)

Отметим, что это не единственное возможное определение. На пример, определение может быть следующем:

(25)

то есть детекция успешна тогда, когда количество успешно извлечённых бит выше некоторого предела (который равен или близок к 1).

Надёжность ЦВЗ. Мера надёжности ЦВЗ -- это число, заключённое в интервале [0,1], где 0 наихудшее возможное значение и 1 наилучшее. Для измерения надёжности используются понятия числа ошибочных байтов и частоты ошибочных битов. Измеряется расстояние между строками извлечённого и внедрённого сообщений или процент совпадений для побитового сравнения. Если строки совпадают, то метод надёжен. ЦВЗ схема считается ненадёжной, если более чем бит повреждены и прозрачность атак выше, чем . Например, для ЦВЗ, подверженный атакам , с сообщением может быть вычислена следующем образом:

(26)

Индекс указывает на то, что вычисляется количество ошибочных байт.

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

Безопасность. Описывает устойчивость ЦВЗ по отношению к определённым атакам.

Верификация. Определяет тип дополнительной информации необходимой функции обнаружения/извлечения для работы.

· Необходим исходный сигнал S.

· Необходимо внедряемое сообщение m и некоторая дополнительная информация, кроме исходного сигнала.

· Нет необходимости в дополнительной информации.

1.4.3 Классификация

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

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

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

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

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

Объём. Длина внедряемого сообщения определяет две различные схемы ЦВЗ:

· : Сообщение концептуально нулевое. Задача системы лишь зафиксировать присутствие водяного знака в помеченном объекте . Иногда, такой тип ЦВЗ называют 1-битным водяным знаком, так как 1 отвечает за присутствие знака, а 0 за отсутствие.

· : Сообщение в виде n-битного числа (, with ) или зашито в . Это обычная схема ЦВЗ с ненулевым сообщением.

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

1.4.4 Применение

· Защита авторских прав

· Борьба с видеопиратством и ранний доступ к новинкам кино. При сотрудничестве с киностудиями Голливуда операторы телевизионных сетей могут предоставлять своим зрителям платный доступ к премиум-контенту - фильмам, только что появившимся в кинотеатрах и еще не вышедшим на DVD [2]. Обязательным условием студий при этом является встраивание водяного знака, позволяющего обнаружить источник утечки - конкретного зрителя - при попадании фильма в нелегальный оборот [3].

· Получение цифрового отпечатка (различные люди получают копии, помеченные разными водяными знаками).

· Отслеживание трансляций (телевизионные новости часто содержат водяные знаки, оставленные международными информационными агентствами[4]; рекламные агентства используют водяные знаки для контроля выхода своей рекламы в эфир в оговоренном объеме).

· Сокрытие факта обмена информации (Стеганография).

1.5 Постановка задач дипломного проекта

Цель:

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

Задачи:

· Изучить основные методы построения особых точек

· На примере детектора Харриса найти особые точки изображения

· Определить координаты точек и расстояния между ними

· Изучить построение минимального остовного дерева из найденных особых точек

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

программный защита авторство изображение цифровой водяной



2. Детектор Харриса определения особых точек

2.1 Алгоритм работы

Рассмотрим фрагмент U изображения I(x,y) с центром в точке (u,v), и его копии, сдвинутые на величину (х, у). Для каждой точки фрагмента можно вычислить взвешенный квадрат разности между сдвинутым и исходным фрагментом, и рассмотреть функцию:

(1)

Функция I(u+x,v+y) может быть разложена в ряд Тейлора в окрестности центра (u,v), что позволяет перейти к выражению:

(2)

где: Ix и Iy - частные производные яркости в горизонтальном и вертикальном направлениях.

Это выражение можно записать в матричном виде:

(3)

где: M= - матрица локальной структуры.

В качестве весовой функции w(u,v) обычно используется функция Гаусса [13].

Угол характеризуется большими изменениями функции S(x,y) по всем возможным направлениям (x,y), что эквивалентно большим по модулю собственным значениям матрицы M.

Отсюда следует ряд выводов:

1. Если собственные значения л1 и л2 близки к нулю, то пиксель с центром в (x,y) не является точкой интереса, поскольку он лежит в однородной области.

2. Если л1?0, а л2 принимает большое по модулю значение, то пиксель (x,y) принадлежит краю.

3. Если оба собственных значения велики и принимают положительные значения, то пиксель (x,y) является углом.(см рис. 1)

Рис. 1 Характеристика угла большими изменениями функции

Мера отклика угла по Харриса (см рис. 2) :

R=det M - k(trace M)І (4)

det M = л1л2

trace M = л1 + л2

(k = 0.04 - 0.06)

Где det M - определитель матрицы; trace M - след матрицы; л1, л2 - собственные значения матрицы,

Рис. 2 Мера отклика угла по Харрису

Алгоритм работы

1) Вычислить градиент изображения в каждом пикселе

2) Вычислить матрицу вторых моментов по окну вокруг каждого пикселя

3) Вычислить отклик угла

4) Отрезать по порогу

5) Найти локальные максимумы функции отклика по окрестности заданного радиуса

6) Выбор самых сильных локальных максимумов [14].

Результат работы детектора Харриса (см. рис. 3)

Рис. 3. Результат работы детектора Харриса

2.2 Построение минимального остовного графа

Граф -- это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

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

Граф, или неориентированный граф G -- это упорядоченная пара , для которой выполнены следующие условия:

-- это непустое множество вершин или узлов;

-- это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе | | - порядком, число рёбер | | - размером графа.

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины.

Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).

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

Рис. 4. Неориентированный граф



Ориентированный граф (сокращённо орграф) - это упорядоченная пара , для которой выполнены следующие условия:

-- это непустое множество вершин или узлов,

-- это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

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

Смешанный граф -- это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой , где, и определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного [15].

Минимальное остовное дерево в связанном взвешенном неориентированном графе -- это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер (см. рис. 5) [16].

Рис 5. Минимальное остовное дерево

2.3 Дискретное преобразование Фурье

Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) -- это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать частные дифференциальные уравнения и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Формулы преобразований

Прямое преобразование:

(5)

k = 0,..., N-1

Обратное преобразование:

(6)

n = 0,…,N-1

Обозначения:

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

, n = 0,…,N-1 - измеренные значения сигнала (в дискретных временных точках с номерами, которые являются входными данными для прямого преобразования и выходными для обратного;

, k = 0,..., N-1 - комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;

- обычная (вещественная) амплитуда k-го синусоидального сигнала;

- фаза k-го синусоидального сигнала (аргумент комплексного числа);

- индекс частоты. Частота k-го сигнала равна, где - период времени, в течение которого брались входные данные.

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



3. Реализация метода записи особых точек

3.1 Система Matlab

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

Язык, инструментарий и встроенные математические функции позволяют вам исследовать различные подходы и получать решение быстрее, чем с использованием электронных таблиц или традиционных языков программирования, таких как C/C++ или Java.

MATLAB широко используется в таких областях, как:

- обработка сигналов и связь,

- обработка изображений и видео,

- системы управления,

- автоматизация тестирования и измерений,

- финансовый инжиниринг,

- вычислительная биология и т.п.

Более миллиона инженеров и ученых по всем миру используют MATLAB в качестве языка технических вычислений.

MATLAB по сравнению с традиционными языками программирования (C/C++, Java, Pascal, FORTRAN) позволяет на порядок сократить время решения типовых задач и значительно упрощает разработку новых алгоритмов.

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

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

MATLAB cодержит встроенные функции линейной алгебры (LAPACK, BLAS), быстрого преобразования Фурье (FFTW), функции для работы с полиномами, функции базовой статистики и численного решения дифференциальных уравнений; расширенные математические библиотеки для Intel MKL.

Численные вычисления

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

- Интерполяция и регрессия

- Дифференцирование и интегрирование

- Системы линейных уравнений

- Фурье анализ

- Собственные значения и сингулярные числа матриц

- Обыкновенные дифференциальные уравнения

- Разреженные матрицы

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

Доступ к данным

MATLAB позволяет вам получать доступ к данным из файлов, других приложений, баз данных, внешних устройств. Вы можете читать данные из файлов таких популярных форматов как Microsoft Excel, текстовых или двоичных файлов, изображений, аудио и видео файлов, научных форматов (netCDF и HDF). Функции ввода-вывода позволяют работать с файлами данных любых форматов.

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

Анализ данных

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

Программирование и разработка алгоритмов. Язык MATLAB

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

С помощью языка MATLAB можно писать программы и алгоритмы быстрее, чем на традиционных языках программирования, потому что нет необходимости таких низкоуровневых организационных операций как объявление переменных, определение типов и выделение памяти. Во многих случаях переход на векторные и матричные операции избавляет от необходимости использования циклов for. В результате одна строка MATLAB кода часто может заменить несколько строк C/C++ кода.

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

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

Ключевые особенности

- Платформонезависимый высокоуровневый язык программирования ориентированный на матричные вычисления и разработку алгоритмов

- Интерактивная среда для разработки кода, управления файлами и данными

- Функции линейной алгебры, статистики, анализ Фурье, решение дифференциальных уравнений и др.

- Богатые средства визуализации, 2-D и 3-D графика.

- Встроенные средства разработки пользовательского интерфейса для создания законченных приложений на MATLAB

- Средства интеграции с C/C++, наследование кода, ActiveX технологии [17].

3.2 Алгоритм и блок-схема поиска и записи особых точек

Структурная схема программы

Алгоритм программы:

1) Выбираем изображение и загружаем его;

2) Определяем размер изображения;

3) Определяем маски;

4) Вычисляем производные;

5) Фильтрация;

6) Находим меру отклика;

7) Локальный максимум;

8) Устанавливаем пороговое значение;

9) Строим особые точки;

10) Устраняем границы;

11) Получаем координаты точек и расстояния между ними;

12) Строим граф.

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



Рис.1. Блок-схема программы нахождения особых точек и построение графа



3.3 Алгоритм и блок-схема введения ЦВЗ для защиты авторства изображения

Рис. 2. Блок-схема введения ЦВЗ для защиты авторства изображения

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

Алгоритм программы:

1) Выбираем изображение и загружаем его;

2) Определяем размер изображения;

3) Генератор псевдослучайной последовательности

4) Прямое дискретное преобразование Фурье

5) Определяем модуль дискретного преобразования Фурье

6) Определяем фазу дискретного преобразования Фурье

7) Проверяем равен ли коэффициент filter_m «1»

8) Вводим цифровой водяной знак

9) Получаем маркированное изображение

10) Переводим изображение в битовый формат

11) Выводим изображение



4. Технико-экономическое обоснование разработки программы

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

Рассчитаем затраты времени на проектирование и разработку программного продукта. В таблице 4.1. представлена трудозатраты выполненных конструкторских работ.

Таблица 1

Затраты рабочего времени при проведении конструкторской подготовки программы

Наименование этапа конструкторской подготовки программы	Время выполнения, часов
1. Разработка
1.1. Технического задания	1,0
1.2. Рабочего чертежа	25,0
2. Составление спецификаций и технических условий	5,0
3. Разработка программного модуля	30,0
4. Тестирование и исправление ошибок	8,0
5. Опытная эксплуатация	6,0
6. Доработка программы по результатам эксплуатации	6,0
ИТОГО (по данным видам работ)	82,0

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

- оплата труда по отдельным расценкам, тарифным ставкам (окладам) за выполнение работ;

- доплаты и надбавки, предусмотренные законодательством о труде;

-премии за производственные результаты в соответствии с действующими премиальными системами, оплата договоров, контрактов и т.п.

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

Заработная плата работников может быть определена в следующей последовательности:

4.1 Рассчитываем прямой (тарифный) фонд заработной платы как:

,

где Ф_зп.пр. - тарифный фонд заработной платы, руб.,

Т_{ст. р.} - часовая тарифная ставка работника, руб.

Тарифные коэффициенты и тарифные ставки (оклады) Единой тарифной сетки работников Республики Беларусь, утвержденной постановлением Министерства труда и социальной защиты Республики Беларусь от 20 сентября 2002 г. №123, с изменениями и дополнениями от 23 марта 2009 г. Величина тарифной ставки (оклада) может быть определена по следующему выражению:

,

где О_т.р. - тарифная ставка (оклад) работника, руб.,

К_т - тарифный коэффициент соответствующего разряда,

З_п.мин - тарифная ставка 1-го разряда, руб.

Постановления Совета Министров от 25 марта 2014 №256 "Об установлении размера тарифной ставки первого разряда для оплаты труда работников бюджетных организаций и иных организаций, получающих субсидии, работники которых приравнены по оплате труда к работникам бюджетных организаций". Данным документом правительства тарифная ставка первого разряда с 1 мая нынешнего года повышена до Br275 тыс.

Корректирующие коэффициенты к тарифным ставкам (окладам), рассчитанным в соответствии с установленной правительством тарифной ставкой первого разряда и коэффициентами Единой тарифной сетки работников Республики Беларусь (ЕТС), следующие:

с 1-го до 2-го разряда - 3,500;

со 2-го до 3-го разряда - 3,066;

с 3-го до 4-го разряда - 2,660;

с 4-го до 5-го разряда - 2,321;

с 5-го до 6-го разряда - 2,150;

с 6-го до 7-го разряда - 1,990;

с 7-го до 8-го разряда - 1,890;

с 8-го до 9-го разряда - 1,800;

с 9-го до 10-го разряда - 1,710;

с 10-го до 11-го разряда - 1,628;

с 11-го до 12-го разряда - 1,540;

с 12-го до 13-го разряда - 1,458;

с 13-го до 14-го разряда - 1,379;

с 14-го до 15-го разряда - 1,310;

с 15-го до 16-го разряда - 1,250;

с 16-го до 17-го разряда - 1,210;

с 17-го до 18-го разряда - 1,171;

с 18-го до 19-го разряда - 1,131;

с 19-го до 20-го разряда - 1,101;

с 20-го до 21-го разряда - 1,062;

с 21-го до 22-го разряда - 1,032;

с 22-го до 23-го разряда - 1,000;

с 23-го до 24-го разряда - 1,000;

с 24-го до 25-го разряда - 1,000;

с 25-го до 26-го разряда - 1,000;

с 26-го до 27-го разряда - 1,000;

по 27-му разряду - 1,000.

Тарифные ставки (оклады) исчисляются путем последовательного умножения тарифной ставки первого разряда на соответствующие тарифные коэффициенты ЕТС и установленные корректирующие коэффициенты.

В Минтруда и соцзащиты подчеркнули, что увеличится соотношение между зарплатой работников, тарифицируемых 1-м и 27-м разрядами, с 2,18 до 2,43 раза, что в большей степени позволит увязать размеры зарплаты работников в зависимости от степени сложности выполняемых ими работ (обязанностей), ответственности, уровня квалификации.

Тарифный разряд молодого специалиста равен 12, а тарифный коэффициент соответственно 2,84.

Затраты на оплату труда рассчитываются по следующей формуле:

(1)

где З_р - зарплата работника за час;

Отч- отчисления с зарплаты, %;

Т_н- время написания программы, ч.

Заработная плата инженера за час определяется по следующей формуле:

(2)

где Ст_пр - ставка программиста, руб.;

Ф_вм- фонд рабочего времени в месяц, ч.;

Н_доп - процент надбавок и повышений к тарифному окладу.

Заработная плата инженера за время работы над проектом равна:

руб. (257000)

Отчисления на соцстрах и фонд занятости вычисляются по следующей формуле:

(3)

где О_сс - отчисления на соцстрах (0,3% от З_общ), руб.;

О_фз- отчисления в фонд занятости (34% от З_общ), руб.

руб.

При расчете затрат, связанных с выполнением научно-исследовательских и опытно-конструкторских разработок (НИОКР), необходимо учитывать затраты на содержание, эксплуатацию и ремонт научно-исследовательского оборудования, установок, стендов, приборов, приспособлений, инструментов и т.п., а также амортизационные отчисления по каждому из них, которые могут быть рассчитаны в следующей последовательности:

- стоимость малоценных и быстроизнашивающихся предметов;

- затраты на топливо и энергию для технологических целей;

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

- затраты на ремонт оборудования и установок определяем по следующему выражению;

- амортизационные отчисления.

При разработке программного продукта был использован компьютер. Таким образом, рассчитаем затраты, связанные с эксплуатацией ЭВМ:

1. Затраты на электроэнергию;

2. Затраты по техническому обслуживанию и ремонту ЭВМ;

3. Затраты на амортизационные отчисления.

Стоимость электроэнергии рассчитывается по следующей формуле:

,

где М - мощность ЭВМ (0,5 кВт);

к_з - коэффициент загрузки (0,8);

С_кВт.ч. - стоимость 1 кВт час электроэнергии (1330 руб/кВт.ч.).

Ф_вр -фонд времени эксплуатации ЭВМ (82 час):

Таким образом, стоимость электроэнергии составит:

руб.

Техническое обслуживание и ремонт составляют 4% от стоимости компьютера, тогда приняв в качестве стоимости компьютера сумму

...