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

На правах рукописи

л

005539120

г '

Кузнецов Андрей Владимирович

Метод обнаружения искусственных искажений данных дистанционного зондирования Земли

05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание учёной степени кандидата технических наук

г л -оя 2013

САМАРА-2013

005539120

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)» на кафедре геоинформатики и информационной безопасности и в федеральном государственном бюджетном учреждении науки Институте систем обработки изображений Российской академии наук.

Научный руководитель: доктор физико-математических наук, доцент

Мясников Владислав Валерьевич

Официальные оппоненты: Лабунец Валерий Григорьевич, доктор технических

наук, профессор, ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина», заведующий кафедрой теоретических основ радиотехники;

Попов Сергей Борисович, доктор технических наук, доцент, профессор кафедры технической кибернетики ФГБОУ ВПО «Самарский государственный аэрокосмический университет имени академика С.П.Королёва (национальный исследовательский университет)».

Ведущая организация: ФГБОУ ВПО «Ульяновский государственный техниче

ский университет»

Защита состоится "13" декабря 2013 г. в 12 часов на заседании диссертационного сове Д 212.215.07, созданном на базе федерального государственного бюджетного образовател ного учреждения высшего профессионального образования «Самарский государственнь аэрокосмический университет имени академика С.П. Королёва (национальный исследовател ский университет)» (СГАУ), по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан "12" ноября 2013 г.

Учёный секретарь

диссертационного совета /, __ ,

доктор технических наук, профессор И.В. Белоконов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы

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

Первые научные публикации, посвященные разработке алгоритмов обнаружения искусственных искажений или фальсификаций цифровых изображений, появились в 20042005 гг. (Н. Fand, A.C. Popescu). Наиболее известным примером фальсификации является сокрытие части изображения (фрагмента) путём копирования фрагмента из другой части того же изображения (наложение дубликата). Пример такой фальсификации приведён на рисунке 1. Задачей обнаружения искусственных искажений в этом случае является выявление факта и, в идеале, способа внесения такого искажения (нахождение положений дубликата-прототипа).

Рисунок 1. Пример исходного изображения (слева) и его искусственного искажения

(справа)

После первых публикаций по указанной тематике в материалах различных международных конференций стали появляться работы авторов S. Prasad, В. Mahdian, S. Saic, J. Fridrich, M. Sridevi, С. Mala и других, продолжавших исследование данной области знаний. Поскольку большая часть работ отмеченных зарубежных авторов опубликована с 2005 по 2012 гг., а на русском языке публикации фактически отсутствуют, то можно говорить о безусловной актуальности выбранной темы исследований. Особенно следует отметить постоянный рост количества зарубежных публикаций на тему обнаружения дубликатов на изображениях (S. Bayram, H. Farid, В. Mahdian, S. Saic).

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

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

Большинство известных работ (S. Prasad, В. Mahdian, A.C. Popescu и др.) в области обнаружения искусственных искажений изображений сосредоточено на разработке алгоритмов, направленных на решение задач обнаружения совершенно конкретных искажений в изображениях - атак. Примерами атак могут быть: копирование и вставка фрагментов изображения, геометрические преобразования фрагментов изображения и т.п. Для каждой атаки разрабатывается алгоритм, далее называемый элементарным, направленный на её обнаружение: алгоритм обнаружения дубликатов, алгоритм обнаружения межпиксельных корреляций и т.п. Не ставя под сомнение важность этого направления исследований, следует всё же отметить его недостатки:

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

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

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие задачи:

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

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

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

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

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

Поставленные задачи определяют структуру работы и содержание её разделов.

Методы исследований

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

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

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

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

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

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

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

6. Предложены новые алгоритмы обнаружения искусственных искажений данных ДЗЗ, основанные на проверке соответствия изображения ДЗЗ условиям съёмки, указанным в метаданных ДЗЗ.

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

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

Реализация результатов работы Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН, проектов РФФИ № 13-07-12103-офи-м, 13-01-12080-офи-м, 12-07-00021-а, программы фундаментальных исследований Президиума РАН «Фундаментальные проблемы информатики и информационных технологий» (проект 2.12), работ по договору для Министерства образования и науки Российской Федерации (в рамках постановления Правительства Российской Федерации от 09.04.2010 г. № 218: договор № 02.Г36.31.0001 от 12.02.2013).

Апробация работы

Основные результаты диссертации были представлены на 9 научных конференциях: международной конференции по автоматизации, управлению и информационным технологиям (ACIT-ICT, Новосибирск, 2010); международной конференции «Перспективные информационные технологии для авиации и космоса» (ПИТ, Самара, 2010); 10-ой и 11-ой международных конференциях «Распознавание образов и анализ изображений: новые информационные технологии» («РОАИ», Санкт-Петербург, 2010 и Самара, 2013); 8-ой и 9-ой международных конференциях «Интеллектуализация обработки информации» (ИОИ, Кипр, Пафос, 2010 и Черногория, Будва, 2012); региональной научно-практической конференции, посвященной 50-летию первого полёта человека в космос (Самара, 2011); научно-технической международной молодёжной конференции «Системы,

методы, техника и технологии обработки медиаконтента» (Москва, 2011); 16-ой Всероссийской конференции «Математические методы распознавания образов 2013» (ММРО, Казань, 2013).

Публикации

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

Структура диссертации Диссертация состоит из четырёх разделов, заключения, списка использованных источников из 154 наименований; изложена на 155 страницах машинописного текста, содержит 38 рисунков, 6 таблиц, 4 приложения.

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

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

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

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

4. Новые признаки спектра гистограммы коэффициентов ДКП в задаче обнаружения на изображениях фрагментов, подвергавшихся сжатию JPEG. Зависимость между значениями этих признаков и коэффициентом сжатия JPEG.

5. Алгоритмы проверки данных ДЗЗ на соответствие условиям съёмки, разработанные с использованием модельно-ориентированных дескрипторов изображения.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В первом разделе диссертации приводится описание проблемы обнаружения искусственных искажений цифровых изображений, анализируются существующие математические методы и алгоритмы (В. Mahdian, A.C. Popescu, M. Sridevi, С. Mala и др.). Показано, что в настоящее время существуют два основных подхода к обнаружению искусственных искажений цифровых изображений, в рамках которых производится разработка конкретных методов и алгоритмов: активный и пассивный. Основным элементом активного подхода к обнаружению искусственных искажений изображений являются цифровые водяные знаки, которые встраивает поставщик цифрового изображения во время его формирования, записи или передачи получателю. Основным недостатком такого подхода является необходимость внесения изменений в первоначальное, исходное изображение. В отличие от активного, пассивный подход не предполагает каких-либо предварительных изменений изображения. Он основан на допущении, что любое искусственное изменение (синонимы: фальсификация, атака) исходного изображения может быть обнаружено путём компьютерного анализа самого изображения.

В первом разделе проведён анализ существующих вариантов атак, и соответствующих им алгоритмов обнаружения, существующих в рамках пассивного подхода: поиск дубликатов (В. Mahdian, S. Saic, J. Fridrich), обнаружение следов ресэмплирования (C.S. Fillion, G. Sahrma, A. Gallagher, M. Kirchner), выявление фрагментов, отличающихся параметрами сжатия (Н. Farid, A.C. Popescu, T. Pevny) и т.п. Каждый алгоритм направлен на выявление изме-

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

В первом разделе также проведён анализ специфики задачи обнаружения искусственных искажений изображений, решаемой в рамках пассивного подхода, применительно к данным дистанционного зондирования Земли (ДЗЗ). Показано, что данные ДЗЗ, получаемые с космических аппаратов (КА), включают в себя два элемента: собственно цифровое изображение и соответствующие ему метаданные (данные, содержащие информацию об условиях регистрации). В такой ситуации, изменениям могут подвергаться как изображение, так и метаданные ДЗЗ. Для определения типового состава информации, полезного с точки зрения задачи обнаружения искусственных искажений данных ДЗЗ, проведён анализ метаданных ряда современных КА: (ЗшскВш!, Оеоеуе-1, \\'огЫУ1е\у-1,2, СайозаМД, Егоэ-А,В, Эро!-5.

Центральным результатом проведённого в первом разделе анализа является конкретизация задач исследования, проводимого в диссертации.

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

Под данными ДЗЗ будем понимать пару Д = (/,3), где / - цифровое изображение, а 3 - соответствующие ему метаданные (информация об условиях съёмки). Определим цифровое изображение как отображение / (или функция яркости) вида:

где А/, N е N - линейные размеры изображения по вертикали и горизонтали соответственно, N и с N - целые числа до М, К - множество значений функции яркости изображения, характеризующее способ получения изображения, /? - количество спектральных каналов изображения. В рамках настоящей диссертационной работы в качестве Г могут выступать множества вещественных чисел И ,бинарное множество В = {(),]} или множество целых чисел на интервале [0,2'"]- Z,..

Под элементарным алгоритмом (ЭА) а обнаружения искусственных искажений данных ДЗЗ понимается вычислительная процедура, которая на основании конкретных данных ДЗЗ указывает факт наличия в них искусственных искажений: «1» - неискаженные, «0» -искаженные. Иными словами, а осуществляет однозначное отображение:

а: А —> В

Параметром ЭА будем понимать функцию, реализующую отображение вида:

р: А-> Я, 7

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

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

2. показатели качества ЭА р10(а),р0,(а), характеризующие ошибки первого (ложное обнаружение фальсификации) и второго (пропуск фальсификации) рода;

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

4. количество запусков ЭА са„(а), характеризующее, сколько раз алгоритм запускался для обнаружения искусственных искажений анализируемых данных;

5. частота срабатывания ЭА /г{а) = характеризующая, как часто алгоритм обнаруживает искусственные изменения среди общего количества его запусков.

Последовательной вычислительной процедурой обнаружения искусственных искажений данных ДЗЗ назовём алгоритм обнаружения искусственных искажений, в основе которого лежит последовательное выполнение ЭА обнаружения искусственных искажений: а а -...-а, :Д —>В;

О 'I 'КЧ ' ^ | ^

е Ак, 4 *(к * у), (4 е О, К -1; где АК с А - множество ЭА, используемых при построении вычислительной процедуры. Специфика последовательной вычислительной процедуры обнаружения заключается в том, что последовательность выполнения ЭА (1) заканчивается в том случае, если текущий (для определённости, у'-ый) ЭА определил анализируемые данные ДЗЗ как «искаженные»: а, (Д) = 0. Существенным моментом является то, что состав множества используемых при

построении алгоритмов АК определяется составом и типом анализируемых (входных) данных ДЗЗ.

Задача построения последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ заключается в определении оптимальной в смысле некоторого критерия последовательности ЭА (1), обеспечивающей обнаружение факта искажения данных ДЗЗ. В качестве показателей или ограничений критерия оптимальности могут выступать следующие параметры последовательной вычислительной процедуры: ее вычислительная сложность, вероятности ошибок первого и второго рода. В частности, вычислительная сложность последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ, вычисляемая на основании значений вычислительной сложности входящих в её состав ЭА, записывается следующим образом: С, = и{а. )+ (1-/^))• („(а. )+... + (1-/г(а,^ ))/(*,и))

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

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

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

алгоритмов, что требует рассмотрения К\ вариантов. Если для малых К указанная переборная задача не представляет серьёзной вычислительной сложности, то при больших значениях К поиск оптимального решения может оказаться затруднительным или вовсе невыполнимым ввиду значительных затрат времени и ресурсов. Поэтому в диссертации предлагается два способа решения задачи построения последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ (поиска оптимальной последовательности ЭА): точный и приближённый.

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

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

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

— приближённый алгоритм позволяет строить вычислительную процедуру для К >25 (точный не позволяет выполнять построение за приемлемое время);

— приближённый алгоритм даёт несущественную потерю в выбранном показателе критерия по сравнению с точным алгоритмом (е < 0.5%).

Третий раздел диссертации посвящён вопросам разработки новых ЭА обнаружения искусственных искажений цифровых изображений, входящих в состав последовательной вычислительной процедуры обнаружения искусственных искажений и предназначенных для обнаружения фальсификаций типа встраивания «дубликата» (ниже, алгоритмы обнаружения дубликатов). Этот раздел содержит решения двух различных задач обнаружения дубликатов: в случае, когда копируемые области не подвергаются изменениям (алгоритмов обнаружения неискажённых дубликатов) и когда копируемые области подвергаются геометрическим искажениям.

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

Пусть /(т,п) - анализируемое изображение. Определим координатный шаблон как конечное множество координат {(0,0),...,(от,/г)}, обладающее следующими свойствами:

- координатный шаблон содержит координату (0,0);

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

- координатный шаблон является четырёхсвязным.

Введём также в рассмотрение специальный вид координатного шаблона, обозначаемый далее к(Л,а,б)и задаваемый следующим образом:

N(A,a,&) = U U{a,b,m,n),

где множество координат Tl(a,b,m,n) задаётся в виде:

1(т,п),(т,п

+ 1),...,{т,п + Ь-1), ) >,

(т + а — 1, п),..., (т + а — 1, п + b — 1) J а конечное множество неотрицательных координат Л может быть достаточно произвольным, но гарантирующим выполнение для

свойств координатного шаблона (совпадающие пары координат считаем одним элементом множества).

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

f{m' + m,n' + n) = f(m"+ т,п"+ п), V(m,/j)e к(Л,а,й).

Приведённая система равенств по сути означает поэлементное совпадение фрагментов изображения, расположенных в позициях (т',п) и (т",п") и имеющих «форму», определяемую координатным шаблоном К(Л,а,б).

Под поиском дубликатов по шаблону К(Л,а,б) будем понимать задачу указания для каждого отсчёта (т,п) цифрового изображения, определяющего начало фрагмента изображения с «формой», определяемой координатным шаблоном

н(л

,a,b), уникального номера

t(m,n)e N, характеризующего фрагмент следующим образом:

, ч ГО, нет дубликата, t(m,n) = {

[> 0, номер "типа" дубликата.

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

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

Следующая предлагаемая хэш-функция основана на модулярном представлении фрагмента изображения, соответствующего прямоугольному шаблону (для простоты рассмотрим одномерный шаблон К({(0,0)},1,А/)). Рассматривая отсчёты фрагмента совместно, мы можем взаимно-однозначно связать их со значением следующей хэш-функции: Н(т,п,/) = /(ш,л)- 2*'"_|> + f(m,n + l)-2t(ll~2) + ... + f{m,n + M-1)-2°. Тогда функция вида:

Hh (т, п, /) = Н(т, n,f) mod b, где b - простое число, может использоваться в качестве хэш-функции. Важным свойством такой хэш-функции является возможность рекурсивной реализации ее вычислений по мере «движения» шаблона по изображению:

H{m,n,f) = 2>{H(m,n-\,f)-2Ht-"f(m,n))+f(m,n + b-1).

Третьим вариантом построения хэш-функции является метод, основанный на использовании линейных локальных признаках (JIJ111), предложенных руководителем соискателя Мясниковым В.В. в 2007 г. Линейным локальным признаком (ЛЛП) длины Л/ над простым полем Галуа GF(p) называется пара ({/г(ш)}"="(|',/|), где {/г(/и)},"~' - конечная импульсная характеристика (КИХ) линейного фильтра, задаваемая в виде конечной последовательности над GF(p) и удовлетворяющая ограничению h(m) * 0,h(M — l) ф 0, а А - алгоритм вычисления свёртки произвольного входного сигнала над GF(p) с КИХ {/г(т)}"^'. Поскольку отсчеты КИХ-фильтра {/'¡{т)}"^ задаются как решение системы линейных алгебраических уравнений (СЛАУ) следующего вида:

й(о) = 1, акИ(М-\) + ф{М + К-\) = 0,

h{m)-Y^akh{m-k) = Q,m& [l,A/-l]/0,

k=1

Yath{m-k) = 0,me [M,M + K-\]/Q,

k=l

h{m)-Yiath(m-k)-p(m) = 09 me [l,M-l]n©, *=i

^ akh(m — k)+(p{m ) = 0, me [M,M + K-2]C\Q,

k=1

вычисление отклика КИХ-фильтра, являющегося в данном случае хэш-значением соответствующей хэш-функции

Н{т, п, /) = f(m, п)■ /г(0) + /(от, и +1) • /г(1)+... + f{m, n + М-1) • /г(М-1) modp,

может быть эффективным образом вычислено рекурсивно:

к _

у{") = ~Yjaky{n~^)+ ~ n = Q,N-\.

1 «кО

Оптимальные отсчеты КИХ-фильтра, и соответствующая им оптимальная хэш-функция, вычисляются в ходе решения различных СЛАУ, отличающихся положениями отсчетов неоднородности <р(т). Для каждого решения производится вычисление числа коллизий (фактов обнаружения ложных дубликатов) на анализируемой выборке данных ДЗЗ с целью нахождения хэш-функции, дающей минимальное число коллизий. Это позволяет настраивать хэш-функцию на конкретный тип изображений (например, на конкретный продукт ДЗЗ, на конкретный спутник, сенсор и т.п.).

На базе описанных выше хэш-функций в диссертационной работе также предложены два алгоритма поиска дубликатов. Построение алгоритма обнаружения неискажённых дубликатов на основе хэш-функции, проецирующей биты изображения, основано на выборе структурного элемента, в рамках которого производится выбор бит для формирования хэш-значений. Вначале формируется массив для хранения результирующего поля t(i,j)e В. На первом шаге при г = 0 строится хэш-таблица значений хэш-функцииНа(от,n,f): позиции бит изображения, используемых для построения хэш-значения, вычисляются в рамках выбранного структурного элемента. Одновременно с заполнением хэш-таблицы, производится заполнение значениями поля t{i,j). На следующем шаге при г = 1 производится анализ только тех положений окна обработки, в которых возможно могут находиться дубликаты, то есть с учётом вычисленных значений l(i,j) при г = О. На каждой итерации алгоритма

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

Для решения задачи обнаружения неискажённых дубликатов на основе хэш-функций на базе модулярной арифметики и ЛЛП был разработан алгоритм, который предполагает последовательный анализ всех возможных положений фрагментов Tl{a,b,m,n) выбранного координатного шаблона К (А ,a,b) изображения вида в режиме «скользящего окна». Очевидно, что поскольку в представлении шаблона используется несколько «прямоугольных» шаблонов П(в,Ъ,т,и), анализируемый в позиции (т',п) фрагмент изображения по шаблону К(А,йг,й) может оказаться дубликатом только в том случае, если все |А| фрагментов вида

П(а, b,m +т,п +п), (m, п) е А оказались дубликатами. Таким образом, решающее правило отнесения фрагмента к определённому типу дубликата имеет вид:

, , Л ГО, Э(ю,и)е Л Н{Т(т' + т,п+п))<\; t{m,n) = \ ,

[Дот,« ) + 1, иначе.

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

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

Вторая часть третьего раздела посвящена разработке алгоритма обнаружения геометрически искажённых дубликатов. Для поиска дубликатов предложенный алгоритм использует известный в литературе метод разбиения на частично перекрывающиеся области с последующим парным их сравнением с использованием признакового описания. Признаковое описание предложено формировать с использованием преобразования Фурье-Меллина. При вычислении признаков, гарантирующих строгую инвариантность для случая непрерывного изображения, в дискретном случае возникают интерполяционные погрешности изображений, вследствие чего инвариантность обеспечивается в ограниченном диапазоне угла поворота и коэффициента масштабирования дубликата. В результате исследований получены следующие ограничения на значения коэффициента масштабирования дублицируемого фрагмента: 0.83-1.17. Результаты исследований также показали преимущество разработанного алгоритма по сравнению с известным решением на базе дискретного косинусного преобразования: он позволяет обнаруживать дубликаты, подвергавшиеся повороту на любой угол, в то время, как известное решение обнаруживает только такие дубликаты, которые были повёрнуты на угол, не превышающий 10-15°.

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

- разработаны и исследованы новые признаки спектра гистограммы коэффициентов ДКП в задаче обнаружения на изображениях фрагментов, подвергавшихся сжатию JPEG;

— разработаны и исследованы алгоритмы проверки данных ДЗЗ на соответствие указанным в метаданных ДЗЗ условиям съёмки, основанные на использовании мо-дельно-ориентированных дескрипторов изображения.

Ниже указанные результаты представлены подробнее.

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

В качестве локальных признаков изображения при вычислении основного сдвига и последующей кластеризации блоков предлагаются следующие характеристики спектра гистограммы РеакН выбранного коэффициента ДКП (ниже D - оператор дисперсии): 1 ) признак периодичности - Ft= D\arg(PeakH J-arg[РеакНм )};

2) признак монотонности - F, =,/У -—

f , {РеакН,_J

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

В ходе исследований была также получена новая зависимость между качеством однократного сжатия JPEG q от значений признака периодичности (рисунок 2).

О 10 20 30 40 50 60 70 80

q,%

Рисунок 2. Зависимость качества сжатия JPEG q от значений признака периодичности Вторая часть четвёртого раздела посвящена разработке алгоритмов проверки данных ДЗЗ на соответствие указанным в метаданных ДЗЗ условиям съёмки. Проверка основана на сопоставлении значений параметров, полученных в ходе компьютерного анализа цифрового изображения, с информацией из соответствующих ему метаданных, характеризующих условия получения этого изображения. Для выявления несоответствий производится сравнение расположения теней от прямоугольных объектов (например, зданий) на изображении с их расположением, вычисленным на основе значений параметров метаданных. В качестве анализируемых космических снимков используются снимки высокого разрешения (0,5 м).

Метод сравнения основан на использовании модельно-ориентированных дескрипторов (МОД) изображения, предложенных руководителем соискателя Мясниковым В.В. в 2012 г. и вычисляемых в данной работе по формуле: у п ^о&{лщё{п„п2)-(Р{п1,пг))+\

0 =<«">> " _I_. (2)

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

Рисунок 3. Результат выделения границы тени Задача выявления несоответствий решается двумя способами: при наличии и при отсутствии априорной векторной карты о территории съёмки. В случае наличия векторной карты местности формирование области границы тени производится путем прямого вычисления по векторной модели анализируемого объекта (рисунок 3), для которой затем вычисляется значение МОД по формуле (2) и выносится решение о соответствии/несоответствии данных и изображения.

При отсутствии векторной карты территории съёмки требуемая векторная модель автоматически достраивается. Для этого на изображении (рисунок 4а) обнаруживаются границы объектов с использованием детектора границ Canny. Далее на границах обнаруживаются прямые углы, лежащие на расстоянии, ограниченном максимально допустимой высотой здания (рисунок 46), а также протяжённые участки, которые лежат вдоль прямой наклона теней и соответствуют границам тени объектов анализа (рисунок 4в). Совмещая полученные данные, формируется область границы тени высотного объекта и для нее вычисляется значение МОД по формуле (2) и выносится решение о соответствии/несоответствии данных и изображения.

Рисунок 4. Выделение соответствующих прямых углов и границ тени высотных объектов на КС

Проведённые экспериментальные исследования предложенных в четвёртом разделе ЭА показали их работоспособность и эффективность в решении задачи обнаружения искусственных искажений данных ДЗЗ.

ЗАКЛЮЧЕНИЕ

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

В диссертационной работе получены следующие основные результаты:

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

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

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

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

5. Предложены новые признаки спектра гистограммы коэффициентов ДКП в задаче обнаружения на изображениях фрагментов, подвергавшихся сжатию JPEG.

6. Разработаны и исследованы алгоритмы проверки данных ДЗЗ на соответствие указанным в метаданных ДЗЗ условиям съёмки, основанные на использовании модельно-ориенти-рованных дескрипторов изображения.

Публикации по теме диссертации Статьи в изданиях, входящих в перечень ВАК:

1. Глумов Н.И., Кузнецов A.B. Обнаружение на изображениях искусственных изменений локального происхождения // Автометрия. 2011. С. 3-11.

2. Glumov N.I., Kuznetsov А. V. Analysis of images for local artificial changes with JPEG compression properties // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. 2011. Vol. 21. No. 2. pp. 244-246.

3. Глумов Н.И., Кузнецов A.B. Обнаружение дубликатов на изображениях // Компьютерная оптика. 2011. Т. 35. №4. С. 508-512.

4. Glumov N.I., Kuznetsov A.V. The analysis of images with JPEG embeddings // Pattern Recognition and Image Analysis. Advances in Mathematical Theory and Applications. 2012. Vol. 22. No. 1. pp. 210-214.

5. КузнецовА.В., МясниковВ.В. Построение вычислительной процедуры комплексной проверки подлинности данных ДЗЗ // Компьютерная оптика. 2013. Т. 37. № 2. С. 245-254.

6. Глумов Н.И., Кузнецов A.B., Мясников В.В. Поиск дубликатов на цифровых изображениях // Компьютерная оптика. 2013. Т. 37. № 3. С. 361-368.

7. Кузнецов A.B., Мясников В.В. Алгоритм обнаружения дубликатов на цифровых изображениях с использованием эффективных линейных локальных признаков // Компьютерная оптика. 2013. Т. 37. № 4.

Материалы и тезисы конференций, статьи в сборниках:

1. Glumov N.I., Kuznetsov A.V. Local artificial image's changes detection // Proceedings of the IASTED International Conference on Automation, Control, and Information Technology (ACIT-2010). Novosibirsk, Russia. 2010. pp. 40-46.

2. Кузнецов A.B. Анализ изображений на наличие локальных искусственных изменений со свойствами JPEG сжатия // Избранные труды Международной конференции с элементами научной школы для молодёжи «Перспективные информационные технологии для авиации и космоса». Самара. 2010. С. 489-493.

3. Глумов Н.И., Кузнецов А.В. Обнаружение локальных искусственных изменений на крупноразмерных изображениях // Доклады 8-й Международной конференции «Интеллектуализация обработки информации». Пафос, Кипр. 2010. С. 375-379.

4. Glumov N.I., Kuznetsov A.V. The analysis of images with JPEG compressed local embeddings // Proceedings of the 10th International Conference on Pattern Recognition and Image Analysis: new information technologies (PRIA-10-2010). Saint-Petersburg. 2010. Vol. 1. pp. 281-283.

5. Кузнецов A.B. Обнаружение на цифровых изображениях областей, подвергавшихся искусственному изменению // Труды региональной научно-практической конференции, посвященной 50-летию первого полёта человека в космос. Самара. 2011. С. 223-224.

6. Глумов Н.И., Кузнецов А.В. Обнаружение дубликатов на космических изображениях земной поверхности // Труды научно-технической международной молодёжной конференции «Системы, методы, техника и технологии обработки медиаконтента». Москва. 2011.

7. Глумов Н.И., Кузнецов А.В. Выявление "следов" применения алгоритмов цифровой обработки на изображениях // Доклады 9-й Международной конференции «Интеллектуализация обработки информации». Будва, Черногория. 2012. С. 316-320.

8. Kuznetsov A.V. Copy-move regions detection algorithm, based on Fourier-Mellin transform // Доклады 9-й Международной конференции «Интеллектуализация обработки информации». Будва, Черногория. 2012. pp. 354-358.

9. Kuznetsov A.V., Myasnikov V.V. On constructing a computational procedure for remote sensing data complex authentication // Proceedings of the 11-th International Conference on Pattern Recognition And Image Analysis (PRIA-11). Samara, Russia. 2013. Vol. 2. pp. 627-631.

10. Glumov N.I., Kuznetsov A.V., and Myasnikov V.V. Plain copy-move detection on digital images // Proceedings of the 11-th International Conference on Pattern Recognition And Image Analysis (PRIA-11). Samara, Russia. 2013. Vol. 2. pp. 555-559.

11. Кузнецов A.B., Мясников В.В. Построение вычислительной процедуры комплексной проверки подлинности данных ДЗЗ // Тезисы докладов 16-й Всероссийской конференции «Математические методы распознавания образов» (ММРО-16). Казань, Россия. 2013 С. 97

Подписано в печать 08.11.20!3 Формат60х84 1/16. Тираж 100 экз. Отпечатано с готового оригинал-макета СГАУ 443086, Самара, Московское шоссе, 34

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ имени академика С.П. КОРОЛЁВА (национальный исследовательский университет)»

На правах рукописи

042014^625 Кузнецов Андрей Владимирович

Метод обнаружения искусственных искажений

данных дистанционного зондирования земли

Специальность 05.13.17 - Теоретические основы информатики

Диссертация на соискание учёной степени кандидата технических наук

САМАРА 2013

Научный руководитель д.ф.-м.н. Мясников В.В.

Оглавление

СПИСОК СОКРАЩЕНИЙ И ОБОЗНАЧЕНИЙ....................................................5

ВВЕДЕНИЕ................................................................................................................6

1 ИСКУССТВЕННЫЕ ИЗМЕНЕНИЯ ДАННЫХ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ И МЕТОДЫ ИХ ОБНАРУЖЕНИЯ: СОВРЕМЕННОЕ СОСТОЯНИЕ...................................................................................................................14

1.1 Описание проблемы, активная и пассивная безопасность цифровых изображений. Обзор вариантов данных ДЗЗ.............................................................14

1.2 Основные типы атак и алгоритмы их обнаружения..................................27

1.2.1 Дублирование фрагментов на космическом снимке..........................28

1.2.2 Вставка фрагмента другого космического снимка.............................29

1.2.3 Совмещение космических снимков.....................................................32

1.2.4 Генерирование текстур на космическом снимке................................33

1.2.5 Компрессия космических снимков.......................................................35

1.2.6 Атаки, приводящие к нарушению межканальных зависимостей.....36

1.2.7 Атаки, приводящие к несоответствию освещённости объектов на космическом снимке................................................................................................37

1.2.8 Добавление шума...................................................................................38

1.2.9 Использование хроматических аберраций изображения для обнаружения атак.....................................................................................................39

1.2.10 Атаки с применением простейших алгоритмов обработки изображений.............................................................................................................40

1.2.11 Атаки с применением операций размытия и повышение резкости41

1.2.12 Нарушение смыслового содержания на космическом снимке как способ обнаружения атак........................................................................................42

1.2.13 Атаки с изменением семантических данных космических снимков ....................................................................................................................................42

1.2.14 Специфика обнаружения атак различными алгоритмами...............42

1.3 Выводы и результаты первого раздела.......................................................43

2 МЕТОД ОБНАРУЖЕНИЯ ИСКУССТВЕННЫХ ИСКАЖЕНИЙ ДАННЫХ ДИСТАНЦИОННОГО ЗОНДИРОВАНИЯ ЗЕМЛИ....................................................45

2.1 Основные определения и элементарные алгоритмы обнаружения искусственных искажений данных ДЗЗ.....................................................................45

2.2 Последовательная вычислительная процедура обнаружения искусственных искажений данных ДЗЗ.....................................................................52

2.3 Алгоритм построения последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ.............................................54

2.3.1 Построение последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ при наличии статистики ....................................................................................................................................54

2.3.2 Построение последовательной вычислительной процедуры обнаружения искусственных искажений данных ДЗЗ при отсутствии статистики.................................................................................................................64

2.4 Выводы и результаты второго раздела.......................................................64

3 ПОИСК ДУБЛИКАТОВ ФРАГМЕНТОВ ИЗОБРАЖЕНИЯ КАК СРЕДСТВО

ОБНАРУЖЕНИЯ ИСКУССТВЕННЫХ ИСКАЖЕНИЙ ДАННЫХ ДЗЗ..................66

3.1 Постановка задачи, существующие решения и направления исследований................................................................................................................66

3.1.1 Постановка задачи поиска дубликатов................................................66

3.1.2 Существующие решения.......................................................................67

3.1.3 Направления актуальных исследований..............................................73

3.2 Координатный шаблон и хэш-функция фрагмента изображения по шаблону.........................................................................................................................74

3.3 Хэш-функции и алгоритмы поиска неискажённых дубликатов..............76

3.3.1 Разработанные хэш-функции................................................................76

3.3.2 Экспериментальные исследования разработанных хэш-функций ...81

3.3.3 Разработанные алгоритмы обнаружения дубликатов........................84

3.3.4 Экспериментальные исследования разработанных алгоритмов.......87

3.4 Поиск дубликатов с использованием линейных локальных признаков..91

3.4.1 Построение оптимальной хэш-функции с использованием линейных локальных признаков...............................................................................................91

3.4.2 Экспериментальные исследования.......................................................92

3.5 Алгоритм поиска геометрически-преобразованных дубликатов.............97

3.5.1 Выбор размера блока.............................................................................97

3.5.2 Выбор схемы разбиения изображения на блоки.................................98

3.5.3 Алгоритм сравнения блоков.................................................................99

3.5.4 Вычисление векторов-признаков......................................................100

3.5.5 Алгоритм обнаружения дубликатов..................................................101

3.5.6 Исследование разработанного алгоритма........................................103

3.6 Выводы и результаты третьего раздела...................................................106

4 НЕКОТОРЫЕ ЭЛЕМЕНТАРНЫЕ АЛГОРИТМЫ ПРОВЕРКИ ДАННЫХ ДЗЗ...................................................................................................................................107

4.1 Проверка признаков JPEG сжатия............................................................107

4.2 Проверка пролёта космического аппарата..............................................117

4.3 Проверка соответствия условиям съёмки................................................118

4.3.1 Проверка соответствия условиям съёмки при наличии векторной карты местности....................................................................................................118

4.3.2 Проверка соответствия условиям съёмки при отсутствии векторной карты местности....................................................................................................126

4.4 Выводы и результаты четвёртого раздела...............................................130

ЗАКЛЮЧЕНИЕ.....................................................................................................132

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

Приложение А Использование результатов диссертации................................148

Приложение Б Вывод вероятностей ошибок первого и второго рода для

последовательной вычислительной процедуры обнаружения искусственных

искажений данных ДЗЗ.................................................................................................150

Приложение В Эффективные линейные локальные признаки.........................152

Приложение Г Модельно-ориентированные дескрипторы изображения.......155

список сокращений и обозначений

Основные сокращения

КС - Космический снимок

КА - Космический аппарат

ДЗЗ - Дистанционное зондирование Земли

ПЭВМ - Персональная электронно-вычислительная

машина

СК - Система координат

ЭА - Элементарный алгоритм

ХФ - Хэш-функция

ДКП - Дискретное косинусное преобразование

ДВП - Дискретное вейвлет преобразование

КИХ - Конечная импульсная характеристика

СЛАУ - Система линейных алгебраических уравнений

ПФ - Передаточная функция

ЛЛП - Линейный локальный признак

Основные обозначения

0 - Пустое множество или отсутствие значений

n - Множество натуральных чисел

= N и {О} ~ Множество натуральных чисел с нулем

В=В, ~ Множество {о,1}

В" - Множество ВхВх . хВ

V_к,_,/

V

п

Ъ - Множество целых чисел

^ - Множество целых чисел на интервале

М-1]

И. - Множество вещественных чисел

^ - Множество вещественных чисел на

интервале [0,1]

Кр - Множество векторов размерности р с

вещественными компонентами

с - Множество комплексных чисел

к - Коммутативное кольцо с единицей

СР(/?) - Простое поле Галуа

ВВЕДЕНИЕ

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

Актуальность темы

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

Первые научные публикации, посвящённые разработке алгоритмов обнаружения искусственных искажений или фальсификаций цифровых изображений, появились в 2004-2005 гг. (Н. Farid, A.C. Popescu). Наиболее известным примером фальсификации является сокрытие части изображения (фрагмента) путём копирования фрагмента из другой части того же изображения (наложение дубликата). Пример такой фальсификации приведён на рисунке 1.

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

Рисунок 1 — Пример исходного изображения (слева) и его искусственного

искажения (справа)

После первых публикаций по указанной тематике в материалах различных международных конференций стали появляться работы авторов S. Prasad, В. Mahdian, S. Saic, J. Fridrich, M. Sridevi, С. Mala и других, продолжавших исследование данной области знаний. Поскольку большая часть работ отмеченных зарубежных авторов опубликована с 2005 по 2012 гг., а на русском языке публикации фактически отсутствуют, то можно говорить о безусловной актуальности выбранной темы исследований. Особенно следует отметить постоянный рост количества зарубежных публикаций на тему обнаружения дубликатов на изображениях (S. Bayram, H. Farid, В. Mahdian, S. Saic).

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

Большинство известных работ (S. Prasad, В. Mahdian, A.C. Popescu и др.) в области обнаружения искусственных искажений изображений сосредоточено на разработке алгоритмов, направленных на решение задач обнаружения совершенно конкретных искусственных искажений (фальсификаций) в изображениях - атак. Примерами атак могут быть: копирование и вставка фрагментов изображения, геометрические преобразования фрагментов изображения и т.п. Для каждой атаки разрабатывается алгоритм, далее называемый элементарным, направленный на её обнаружение: алгоритм обнаружения дубликатов, алгоритм обнаружения межпиксельных корреляций и т.п. Не ставя под сомнение важность этого направления исследований, следует всё же отметить его недостатки:

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

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

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

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

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

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

Для достижения поставленной цели в диссертации решаются следующие задачи:

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

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

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

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

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

Поставленные задачи определяют структуру работы и содержание её разделов.

Методы исследований

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

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

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

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

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

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

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

6. Предложены новые алгоритмы обнаружения искусственных искажений данных ДЗЗ, основанные на проверке соответствия изображения ДЗЗ условиям съёмки, указанным в метаданных ДЗЗ.

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

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

Реализация результатов работы Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН, проектов РФФИ № 13-07-12103-офи-м, 13-01-12080-офи-м, 12-07-00021-а, программы фундаментальных исследований Президиума РАН «Фундаментальные проблемы информатики и информационных технологий» (проект 2.12), работ по договору для Министерства образования и науки Российской Федерации (в рамках постановления Правительства Российской Федерации от 09.04.2010 г. № 218: договор № 02.Г36.31.0001 от 12.02.2013).

Апробация работы

Основны