Для каждого пикселя изображения рассматривается окружность с центром в этой точке, которая вписана в квадрат со стороной 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 ) или зашито в . Это обычная схема ЦВЗ с ненулевым сообщением.