Поиск дубликатов изображений на примере Instagram

Лехова Ирина Андреевна

Поиск дубликатов изображений на примере Instagram

Целью данной работы является создание прототипа системы поиска дубликатов изображений на примере социальной сети Instagram. В процессе работы был проведен обзор существующих сервисов по поиску похожих изображений и проведены исследования того, какими способами они решают поставленную задачу. Было создано приложение с удобным графическим интерфейсом для работы с алгоритмами и проведения сравнительных экспериментов, в ходе которых был выбран наиболее эффективный алгоритм, gHash, показавший себя не хуже других в плане чувствительности к модификациям изображений и являющийся наименее подверженным коллизиям. Также был создан веб-сервис на платформе Microsoft Azure для поиска дубликатов изображений в инстаграме. Для этого была создана база данных для 11000 фотографий из инстаграма natgeo и был предоставлен интуитивно понятный графический интерфейс.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36515f1be77c40d58c6d

UUID: ce3d7a3e-cb80-477e-ade2-6cd9b424273c

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 2555

Лехова Ирина Андреевна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 1797341 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ Лехова Ирина Андреевна Выпускная квалификационная работа бакалавра “Поиск дубликатов изображений на примере Instagram” Направление 010300 Фундаментальная информатика и информационные технологии Научный руководитель, старший преподаватель Уланов А.В. Санкт-Петербург 2016

Содержание Введение ................................................................................................................... 3 Постановка задачи ................................................................................................... 4 Используемые термины .......................................................................................... 5 Обзор литературы.................................................................................................... 7 Глава 1. Примеры существующих систем поиска дубликатов изображений ... 9 1.1 Google Images ................................................................................................. 9 1.2 Яндекс.Картинки .......................................................................................... 10 1.3 TinEye ............................................................................................................ 11 1.4 ReportStatistics .............................................................................................. 12 Глава 2. Перцептуальные хэш-алгоритмы.......................................................... 13 2.1 aHash (Average hash или простой перцептуальный хэш) ......................... 14 2.2 pHash (Perceptive Hash или Перцептивный хэш) ...................................... 15 2.3 dHash (Difference Hash) ............................................................................... 17 2.4 gHash (Gradient Hash)................................................................................... 17 Глава 3. Реализация алгоритмов .......................................................................... 19 Глава 4. Создание веб-сервиса на базе Microsoft Azure .................................... 24 Выводы ................................................................................................................... 27 Заключение ............................................................................................................ 28 Источники и литература ....................................................................................... 29 Приложение ........................................................................................................... 31 2

Введение В нашем обществе использование чужих идей с указанием источника или официально приобретенных продуктов не запрещается. Но существует проблема нарушения авторских прав, незаконного использования, обусловленная прогрессом современных информационных технологий и широким использованием сети Интернет. Интернет помогает стремительно развиваться не только авторству, но и плагиату. В настоящее время в большинстве стран мира существуют законы, защищающие авторские права. Несоблюдение этих законов может приводить к серьёзным последствиям, вплоть до тюремного заключения. Плагиат фотографий является не меньшей проблемой чем, например, плагиат авторских текстов. Данная проблема весьма насущна для Instragram социальной сети для обмена фотографиями и видеозаписями, которая достигла огромной популярности за последние 5 лет. Кража и повторная публикация чужих фотографий в Instagram является не только нарушением авторских прав, но и кражей личной собственности. Целью данной выпускной квалификационной работы является создание прототипа системы поиска дубликатов изображений на примере социальной сети Instagram. Подобная система будет полезна людям, которые беспокоятся о том, что кто-то присваивает их авторство себе, и людям, которые хотят получить информацию о первоисточнике фотографии. Также она окажет большое содействие в борьбе со спамом – навязчивой нежелательной рекламой. 3

Постановка задачи Для достижения цели, указанной в введении ВКР, были поставлены задачи: 1. Ознакомиться с уже существующими системами поиска дубликатов изображений и провести их обзор. 2. Рассмотреть возможные способы решения задачи и описать алгоритмы, наиболее подходящие для ее решения. 3. Реализовать рассмотренные алгоритмы, провести сравнительные тесты. 4. Выбрать наиболее эффективный алгоритм для дальнейшей работы 5. Создать веб-сервис по поиску похожих изображений на базе Microsoft Azure 4

Используемые термины Instagram - социальная сеть для обмена фотографиями и видеозаписями Спам - массовая рассылка коммерческой и иной рекламы или подобных коммерческих видов сообщений лицам, нежелающим их получать. Веб-сервис - услуги, предоставляемые в интернете Хэш-функция - алгоритм, преобразующий строку произвольной длины в битовую строку фиксированной длины. Хэш изображения - битовая строка фиксированной длины, полученная в результате преобразования изображения по определенному алгоритму. Расстояние Хэмминга - число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны. [6] Пиксель - наименьший элемент 2D-изображения в растровой графике Градации серого - отображение изображения в оттенках серого цвета. Цветовой баланс - соотношение цветов в изображении. Гамма-коррекция - коррекция яркости цифрового изображения. Гистограмма изображения - график распределения элементов изображения с различной яркостью, в котором по горизонтали располагается яркость, а по вертикали - число пикселей с заданным значением яркости. Шум - дефект изображения, ухудшающий его качество. Размытие - смешивание двух цветов из палитры для имитирования третьего. Яркость - количество белого цвета на изображении. Контрастность - разница между разными, расположенными близко цветами. Масштабирование - изменение размера изображения. 5

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

Обзор литературы При написании данной работы были использованы статьи из материалов международных конференций (Intelligent Robotics and Applications: 8th International Conference, IEEE International Conference on Image Processing), статьи из интернета и магистерская диссертация Christoph Zauner. В процессе поиска литературы, которая могла бы быть полезной для данной работы, автор столкнулся с проблемой отсутствия достойного материала об алгоритмах перцептуального хэширования на русском языке. Это обусловлено тем, что данная тема не пользуется популярностью среди российских ученых, нежели в других странах. Тем не менее, в рунете доступен поверхностный материал в виде статей на ресурсе, посвященном IT-технологиям, Habrahabr1, но данная информация полезна лишь в целях ознакомления с базовыми понятиями хэширования изображений, так как она не подкреплена никакими практическими результатами или ссылками на научные труды. Статьи Neal Krawetz ”Kind of Like That” [1] и ”Looks Like IT” [2], доступные в блоге The Hacker Factor Blog2 часто цитируются в научных трудах других людей. В этих публикациях достаточно подробно и понятно изложены фундаментальные основы перцептуальных хэшей и принципы работы алгоритмов aHash, pHash DCT и dHash. Несмотря на то, что данный сайт подобен вышеописанному Habrahabr, у этих статей есть большое преимущество – в них читателя впервые знакомят с алгоритмом перцептуального хэширования dHash, разработанным David Oftedal, который посодействовал написанию статьи “Kind of Like That”. 1 2 https://habrahabr.ru/ http://www.hackerfactor.com/blog 7

Еще одним из основных источников литературы является магистерская диссертация Christoph Zauner Implementation and Benchmarking of Perceptual Image Hash Functions [5], которая также часто цитируема. В своей работе автор достаточно подробно рассказывает о том, что такое перцептуальные хэш-функции, как они применимы к задаче сравнения изображений, проводит достаточно подробный обзор возможных модификаций алгоритма pHash и описывает работу по созданию собственного фрэймворка Rihamark, который предоставляет возможность проводить анализ хэш-функций с помощью встроенных инструментов для модификаций изображений и проведения тестов. Также было подмечено, что в большинстве научных публикаций и статьях в интернете не различают понятия Perceptual(Перцептуальный) и Perceptive(Перцептивный). Это является достаточно грубой ошибкой, так как изначально первое понятие относилось к названию класса изучаемых в этой работе алгоритмов, а второе – к конкретному алгоритму, pHash (Perceptive hash или Перцептивный хэш). 8

Глава 1. Примеры существующих систем поиска дубликатов изображений На сегодняшний день существует множество систем поиска похожих изображений, имеющих определенные возможности и основанных на различных алгоритмах. Рассмотрим некоторые из них. 1.1 Google Images Рисунок 1.1 - Логотип Google Images и его интерфейс Google Images - специальный сервис одной из крупнейших поисковых систем Google. Он использует обратный поиск изображения и позволяет пользователям найти похожие изображения просто путем загрузки изображения или его прямой ссылки. Google решает эту задачу путем анализа представленного изображения и построения его математической модели с помощью современных алгоритмов. Далее происходит сравнение с миллиардами других изображений в базах данных Google и выбираются похожие. Точность поиска выше, если искомое изображение является популярным, т.е. его уже искали до этого. Кроме того, Google Images будет предлагать "лучшее предположение” для этого изображения на основе описательных метаданных результатов. 9

1.2 Яндекс.Картинки Яндекс.Картинки - аналогичный сервис, предоставляемый российской поисковой системой Яндекс. Также специализируется на нахождении не только точных копий изображения, но и просто похожих. Взаимодействия пользователя с сервисом происходит аналогично Google Images. Рисунок 1.2 - Процесс поиска похожих изображений в Яндекс.Картинках Поиск изображений основан на собственной технологии Яндекса Сибирь (от англ. CBIR – Content-based image retrieval, рус. Поиск изображения по содержанию). Поиск практически идентичных изображений (та же картинка, но другого размера, с нанесением небольшого копирайта и пр.) происходит следующим образом: алгоритм разбивает загруженную картинку на визуальные слова и с их помощью сопоставляет её с миллиардами известных ему изображений, отбирая дубликаты. Для поиска похожих изображений, но не практически идентичных, “Сибирь” использует глубокие нейронные сети. [9] 10

1.3 TinEye TinEye - это поисковая система, специализирующаяся на поиске в интернете изображений, похожих на изображение-образец. То есть, фактически, она находит “почти” дубликаты, но не может осуществлять, например, поиск картинок аналогичного содержания. Ресурс TinEye открывает для пользователей ряд различных возможностей. В частности, с его помощью можно: ● Узнать автора изображения или фотографии; ● Отследить, когда изображение появилось впервые в Интернете; ● Найти то же разрешением, изображение/фотографию, но с более высоким либо отредактированное. каким-то образом Рисунок 1.3 - Процесс поиска похожих изображений в TinEye В отличие от большинства поисковых систем, TinEye не использует имена изображений или любые метаданные для выполнения поиска. После того как пользователь загрузил фотографию для поиска, TinEye создает уникальный и компактный цифровой “отпечаток” изображения, а затем сравнивает этот отпечаток с биллионами изображений в индексе TinEye. К сожалению, создатели данного сервиса не раскрывают технологии, которые были использованы для его реализации, но результаты поиска 11

плагиата похожи на результаты тех алгоритмов, о которых рассказывается далее в данной работе. 1.4 ReportStatistics Еще одним примером похожей системы является бот RepostStatistics, работающий на базе Imgur – онлайн-сервиса загрузки, хранения и обмена фотоизображений. Задача ReportStatistics состоит в том, чтобы самостоятельно находить дубликаты фотографий и оставлять комментарии под новыми изображениями с ссылкой на оригинал. В основе его работы лежат реализованные на языке программирования python алгоритмы aHash и dHash, о которых будет рассказано далее. 12

Глава 2. Перцептуальные хэш-алгоритмы Одним из подходов решения задачи распознавания графических образов является использование нейронных сетей. Предварительно сеть обучается с помощью тренировочного множества, далее на вход подаются изображения, которые нужно охарактеризовать как дубликат или не дубликат. Главное преимущество использования нейронных систем в поиске дубликатов в возможности находить не только копии изображений, но и просто похожие (например, фотографии, снятые с другого ракурса или аналогичное содержание). Но, при использовании данного подхода для поиска спама или плагиата, возникает проблема: для каждого типа спамизображения необходимо большое количество обучающих данных, что трудно в плане реализации, потому что невозможно знать заранее, на какой фотографии может появиться спам или плагиат. Также сравнение двух изображений можно осуществить с помощью побитового сравнения двух файлов. Это один из самых первых способов сравнения изображений. В настоящее время он достаточно устаревший, существует огромное количество альтернативных способов решения данной проблемы, но, на момент своего создания, он являлся единственным решением задачи. Его главный недостаток заключается в том, что чем больше файлов для сравнения, тем больше потребуется вычислительных затрат. Более эффективными в решении данной задачи являются алгоритмы перцептуального хэширования. Вкратце, перцептуальный хэш — это свертка каких-то признаков, описывающих картинку. Эти алгоритмы объединяет то, что сперва происходит преобразование изображений (изменение в размере, перевод в градации серого и т.д. – все это зависит от конкретного алгоритма), строятся хэши изображений, а потом хэши двух изображений сравниваются 13

между собой. Основные различия именно в хэш-функциях. Размер хэша равен количеству пикселей преобразованного изображения. Для сравнения хэшей алгоритмы, описываемые в данной работе, используют расстояние Хэмминга, которое достаточно просто для вычисления. Чем меньше это расстояние, тем более вероятно, что изображения одинаковы. И наоборот, чем больше дистанция, тем больше отличие. Таким образом, задача сравнения изображений сводится к вычислению их хэш-значений и нахождению расстояния Хэмминга между хэшами. Алгоритмы этого класса просты как для реализации, так и для поиска похожих изображений по базе данных путем сравнения хэщей. Рассмотрим самые известные из них: 2.1 aHash (Average hash или простой перцептуальный хэш) aHash - самый легкий для реализации из описываемых в этой главе алгоритмов. Его отличительной чертой является то, что его работа основана на проверке на среднее значение по всем точкам изображения. Шаги: 1. Уменьшить размер. Чем больше уменьшенное изображение, тем более точным будет результат, но на это потребуется больше времени. Обычно при реализации этого алгоритма изображение сжимается до 8х8 (здесь и далее в пикселях). Данная операция выполняется для избавления от высоких частот. 2. Убрать цвет. Сжатое изображение переводится в градации серого, в результате чего размер хэша становится в 3 раза меньше. (происходит уменьшения количества цветовых компонент с трех (в модели RGB) до одной уровня серого). Преобразуется по формуле: 𝑖𝑚𝑔[𝑖, 𝑗] = 𝑅 +𝐺 +𝐵 3 , где 𝑖𝑚𝑔[𝑖, 𝑗] − новое значение [i, j] - пикселя изображения, R, G, B - значения цветов пикселя в пространстве RGB. 14

3. Найти среднее. Необходимо вычислить среднее значение по всем 64 точкам изображения. 𝑎𝑣𝑔 = ∑8𝑖=1 ∑8𝑗=1 𝑖𝑚𝑔[𝑖, 𝑗] 8×8 4. Построить битовую цепочку. В зависимости от того, является ли значение пикселя больше среднего или меньше, в конец цепочки записывается 1 или 0. 𝑏[𝑖 ∗ 𝑗] = 1, если 𝑖𝑚𝑔[𝑖, 𝑗] ≥ 𝑎𝑣𝑔 𝑏[𝑖 ∗ 𝑗] = 0, если 𝑖𝑚𝑔[𝑖, 𝑗] < 𝑎𝑣𝑔 5. Построить хэш. Необходимо перевести 64 отдельных бита в одно 64битное значение. Порядок не имеет значения, но принято записывать биты начиная с левого верхнего угла и заканчивая правым нижним. Данный алгоритм достаточно быстрый, чувствителен к операциям, изменяющим среднее значение - изменения цветового баланса или уровней, так как он основан на средних значениях цветов. 2.2 pHash (Perceptive Hash или Перцептивный хэш) pHash во многом повторяет шаги aHash, но кроме того еще выполняется DCT (Discrete Cosine transform) - дискретное косинусное преобразование, которое делит исходное изображение на гармоники дискретного сигнала, влияющие на качество изображения. Шаги: 1. Требуется уменьшить изображение до 32х32. 2. Провести перевод изображения в оттенки серого 3. Провести DCT. Оно разбивает изображение на набор частот и векторов. 1 𝐹(𝑢, 𝑣) = 1 2 2 2 2 𝜋∙𝑢 𝜋∙𝑣 𝑀−1 (𝑁) (𝑀) ∑𝑁−1 𝑖=0 ∑𝑗=0 𝛬(𝑖) ∙ 𝛬(𝑗) ∙ cos [2∙𝑁 (2𝑖 + 1)] ∙ cos [2∙𝑀 (2𝑗 + 1)] ∙ 𝑓(𝑖, 𝑗) где: 𝛬(𝜉) = 1 , если 𝜉 = 0 √2 15 ,

𝛬(𝜉) = 1 , если 𝜉 ≠ 0 ● M, N — определяют размер входной матрицы. (32x32) ● f (i, j) — значение интенсивности пикселя (i, j) ● F (u, v) —коэффициент из матрицы DCT, располагающийся на строке u и столбце v. [3] 4. Сократить DCT. Требуется сохранить только левый верхний блок 8x8. Нам необходимы низкочастотные компоненты изображения. Высокочастотные компоненты, располагающиеся ближе к правому нижнему углу, не несут особой ценности. Рисунок 2.1 - Разбиение изображения на частотные компоненты 5. Вычислить среднее значение. На этом шаге требуется убрать из расчёта самый первый коэффициент, чтобы исключить из описания хэша пустую информацию, например, одинаковые цвета. [3] 6. Присвоить каждому из 64 DCT-значений 0 или 1 в зависимости от того, больше оно или меньше среднего значения. 7. Построить хэш. 64 бита превращаются в 64-битное значение. Такой алгоритм уже способен выдержать изменение гистограммы изображения или его гамма-коррекцию. PHash нечувствителен к изменению контрастности, яркости и к масштабированию. 16

2.3 dHash (Difference Hash) Создателем данного алгоритма является David Oftedal. dHash прост в реализации и обладает высокой скоростью и точностью работы. Основан на отслеживании градиента изображения. Шаги: 1. Уменьшить размер изображения до 9х8 (в общем случае N + 1 x N). 2. Перевести изображение в оттенки серого 3. Вычислить разницу между следующим и предыдущим пикселем. В результате получается матрица 8х8 4. Построить битовую цепочку. Если значение текущего пикселя больше предыдущего, значение хэша принимается 1, в противном случае 0. 5. Построить хэш. Требуется перевести 64 отдельных бита в одно 64битное значение. 2.4 gHash (Gradient Hash) Также была проведена работа по созданию собственного алгоритма перцептуального хэширования – gHash, градиентного хэша. За основу был взят алгоритм dHash. Опытным путем было выявлено, что отслеживание градиента изображения по столбцам и строкам не менее эффективно попиксельного метода, лежащем в основе dHash. Шаги: 1. Уменьшить размер изображения до 32х32. 2. Перевести изображение в оттенки серого 3. Построить битовую цепочку. Каждому столбцу присваивается 1 или 0 в зависимости от того, больше или меньше сумма значений его пикселей в сравнении со следующим столбцом. Далее происходит запись этого значения в конец битовой строки. Аналогичные 17

операции проводятся со строками. В результате получается цепочка из 64 битов. 4. Построить хэш. Требуется перевести 64 отдельных бита в одно 64битное значение. Если допустить, что изображение уменьшается до 𝑛 × 𝑛 пикселей, то, пренебрегая алгоритмов способом aHash, масштабирования pHash, dHash и изображения, gHash, сложности соответственно: 𝑂(𝑛2 ), 𝑂(𝑛4 ), 𝑂(𝑛2 ) и 𝑂(𝑛2 ) . В оценке сложности алгоритма pHash большую роль играют затраты на вычисления DCT. 18

Глава 3. Реализация алгоритмов Для реализации алгоритмов gHash, dHash и aHash был выбран объектно-ориентированный язык программирования C# со встроенной библиотекой для обработки и прорисовки изображений System.Drawing и готовая библиотека pHash3 для алгоритма pHash, так как дискретное косинусное преобразование достаточно сложное для реализации Для анализа и тестирования работы скорости алгоритмов использовалась выборка из 8000 уникальных фотографий из инстаграма natgeo4. Рисунок 3.1 - Пример работы программы На первом этапе для каждого алгоритма был проведен замер времени, необходимого для обработки 8000 фотографий. Результаты представлены в Таблице 3.1. 3 4 http://phash.org/ https://instagram.com/natgeo 19

aHash pHash dHash gHash Общее время обработки всех фотографий 2m 40s 19m 6s 2m 36s 2m 38s Среднее время обработки одной фотографии 0.02s 0.14s 0.019s 0.02s Таблица 3.1 - Время обработки фотографий Учитывая медленную скорость работы алгоритма pHash, на следующем этапе будут рассматриваться только алгоритмы gHash, dHash и aHash. Далее была проведена проверка алгоритмов на коллизии. Опытным путем было выявлено, что расстояние Хэмминга у хэшей похожих изображений меньше 10. Таким образом, если дистанция между хэшами двух уникальных фотографий меньше 10, то алгоритм выдал некорректный результат. Таблица 3.2 - Количество пар изображений с указанным расстоянием Хэмминга Ниже приведены графики коллизий для всех рассматриваемых алгоритмов. По оси OХ указаны значения расстояний Хэмминга, а по OY количество пар изображений, соответствующих этим расстояниям. 20

График 3.1 - aHash График 3.2 - dHash График 3.3 - gHash Для более наглядной демонстрации разницы между работой алгоритмов был построен общий график, где по оси OХ - расстояния 21

Хэмминга (для наглядности - значения от 0 до 5), а по оси OY - количество пар изображений, между хэшами которых получено данное расстояние. График 3.5 - Сравнение корректности алгоритмов По результатам работы алгоритмов можно заметить, что gHash более устойчив к коллизиям чем dHash и aHash, что является несомненным преимуществом. На следующем этапе для 100 изображений из предыдущей коллекции были проведены различные модификации: добавление шумов (noise), размытие (blur), изменения яркости (bright), контрастности (contrast), автоуровень (autolevel), масштабирование (scale), а также была проведена проверка на схожесть оригиналов с их модифицированными версиями. Таблица 3.3 - aHash 22

Таблица 3.4 - dHash Таблица 3.5 - gHash Согласно результатам тестов, приведенных в таблицах 3.4 – 3.6, gHash показывает точность, сопоставимую с точностью работы алгоритмов aHash и dHash. Учитывая, что при этом gHash показал наибольшую устойчивость к коллизиям, для создания системы проверки фотографий на плагиат был выбран именно он. 23

Глава 4. Создание веб-сервиса на базе Microsoft Azure Для реализации веб-сервиса была использована Microsoft Azure облачная платформа Microsoft, предоставляющая возможность разработки и выполнения приложений и хранения данных на серверах, расположенных в распределённых дата-центрах. На базах данной платформы и фрэймворка ASP.NET MVC Framework был развернут проект под названием “Instagram Plagiarism Checker”5 для поиска дубликатов фотографий и была создана база данных для 11000 фотографий из инстаграма natgeo, состоящая из одной таблицы imageHashes вида: Рисунок 4.1 - База данных ImageHashes где ● IMGname - имя изображения ● IMGhash - хэш изображения типа bigint, полученный в результате обработки изображения алгоритмом gHash 5 http://plagiarismsearch.azurewebsites.net 24

● User - имя пользователя в Instagram, на страничке которого фотография появилась впервые Рисунок 4.2 - Интерфейс веб-сайта Пользователю предлагается загрузить изображение, дубликат которого он желает найти в инстаграме. После этого алгоритм gHash вычисляет хэш изображения, и затем происходит поиск похожих изображений по базе данных путем вычисления расстояния Хэмминга между хэшами. В итоге пользователю предоставляются все, удовлетворяющие его фотографии, дубликаты. Необходимо отметить, что фотографии, информация о которых хранится в базе данных, берутся напрямую из инстаграма, так как нецелесообразно хранить бесконечно растущее количество фотографий, например, в облачном хранилище. Таким образом, данный сервис является информационным посредником первого типа. Он лишь предоставляет материал в информационно-телекоммуникационный сети в ответ на запрос пользователя. С примером работы сервиса можно ознакомиться на рисунках 4.3 и 4.4. 25

Рисунок 4.3 - Загружаемое изображение Рисунок 4.4 - Результаты поиска 26

Выводы В процессе работы был проведен обзор существующих сервисов поиска похожих изображений и проведены исследования того, какими способами они решают поставленную задачу. Был проведен обзор перцептуальных алгоритмов и создано приложение с удобным графическим интерфейсом для работы с рассмотренными алгоритмами и проведения сравнительных экспериментов, в ходе которых был выбран наиболее эффективный, gHash – авторский алгоритм, показавший себя не хуже других в плане чувствительности к модификациям изображений и являющийся наименее подверженным к коллизиям. Также создан веб-сервис на платформе Microsoft Azure для поиска дубликатов изображений в инстаграме. Для этого была создана база данных для 11000 фотографий из инстаграма natgeo и был предоставлен интуитивно понятный графический интерфейс. В результате были осуществлены основные функции сервиса, такие как: загрузка фотографий, дубликат которой необходимо отыскать, поиск похожих изображений в базе данных, предоставление результатов пользователю с указанием источника. 27

Заключение Проблема поиска дубликатов изображений в настоящее время остается одной из самых интересных и по-своему сложных задач. На сегодняшний день не существует такого алгоритма, который бы справился с ней на все 100%. Но современные информационные технологии не стоят на месте и постоянно развиваются. И, кто знает, возможно в недалеком будущем такая проблема будет абсолютно разрешима. Автор данной ВКР в полной мере справился с поставленной задачей создания системы поиска дубликатов изображений для социальной сети Instagram. В дальнейшем планируется создать систему автозаполнения и обновления базы данных для фотографий из инстаграма и реализовать гибкий поиск в ней. Также возможно применение алгоритмов перцептуального хэширования не только для фотографий, но и для видео и аудио файлов, о чем рассказывается в работах [11] и [12]. Таким образом, станет возможным поиск не только дубликатов фотографий, но и поиск похожих видеозаписей в инстаграме. 28

Источники и литература 1. Kind of Like That // The Hacker Factor Blog. URL: http://www.hackerfactor.com/blog/?/archives/529-Kind-of-Like-That.html (дата обращения 11.12.2015). 2. Looks Like IT // The Hacker Factor Blog. URL: http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-LikeIt.html (дата обращения 11.12.2015). 3. Перцептуальные хэши для сравнения изображений // IT Sector Blog von Alexandr M. URL: http://malexit.ru/?p=93 (дата обращения 13.12.2015). 4. Niu Xia-mu, Jlao Yu-hua An Overview of Perceptual Hashing // ACTA ELECTRONICA SINICA. China, Beijing, July, 2008, Vol.36, No. 7, p. 1405-1411. 5. Zauner C. Implementation and Benchmarking of Perceptual Image Hash Functions. Master’s thesis, 2010. 6. Hamming Distance. // Wikipedia. URL: https://en.wikipedia.org/wiki/Hamming_distance (дата обращения 11.12.2015). 7. Сибирь (технология Яндекса) // Wikipedia. URL: https://ru.wikipedia.org/wiki/Сибирь_(технология_Яндекса) (дата обращения 16.04.2016). 8. The Discrete Cosine Transform (DCT) // Cardiff School of Computer Science & Informatics. URL: http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html (дата обращения 11.12.2015). 9. Новый поиск похожих картинок // Блог Яндекса. URL: https://yandex.ru/blog/company/90100 (дата обращения 16.04.2016). 10. R. Venkatesan, S.-M. Koon, M. H. Jakubowski and P. Moulin Robust image hashing // Proc. IEEE ICIP, Vancouver, Canada, September, 2000. 29

11.M. K. Mıhçak and R. Venkatesan A perceptual audio hashing algorithm: a tool for robust audio identification and information hiding // Inf. Hiding 2001, p. 51-65. 12.O. Kjelsrud Using Perceptual Hash Algorithms to Identify Fragmented and Transformed Video Files, Master’s thesis, 2014. 13.Центр документации // Microsoft Azure. URL: https://azure.microsoft.com/ru-ru/documentation/ (дата обращения 22.04.2016). 14. pHash Demo // pHash, the open source perceptual hash library. URL: http://www.phash.org (дата обращения 11.12.2015). 30

Приложение Приложение к главам 3 и 4. Реализация алгоритмов aHash, dHash и gHash. 1. using System; 2. using System.Drawing; 3. using System.Drawing.Drawing2D; 4. using System.Drawing.Imaging; 5. namespace PerceptualHashTester 6. { 7. 8. public static class AHashAdaptiveAlg 9. { 10. 11. public static Int64 Calculate(Image image) 12. { 13. Int64 res = 0; 14. Bitmap bitmap = null; 15. bitmap = ImageUtils.ResizeImage(image, 10, 10); 16. for (int x = 1; x < 9; x++) 17. { 18. for (int y = 1; y < 9; y++) 19. { 20. byte s1 = ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x - 1, y)); 21. byte s2 = ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x - 1, y - 1)); 22. byte s3 = ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x, y - 1)); 23. byte s4 = ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x + 1, y)); 24. byte s5 = ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x + 1, y - 1)); 31

25. byte sa = (byte)((s1 + s2 + s3 + s4 + s5) / 5f); 26. if (ImageUtils.CalculateWeightByAvgOfChanels(bitmap.GetPixel(x, y)) > sa) 27. { 28. res |= ((Int64)1 << ((y - 1) * 8 + (x - 1))); 29. } 30. } 31. } 32. bitmap.Dispose(); 33. return res; 34. } 35. 36. } 37. 38. public static class GHashAlg 39. { 40. static float[] row_buffer = new float[32]; 41. static float[] collumn_buffer = new float[32]; 42. 43. public static Int64 Calculate(Image image) 44. { 45. var b32 = ImageUtils.ResizeImage(image, 32, 32); 46. for (int x = 0; x < 32; x++) 47. { 48. float b = 0; 49. for (int y = 0; y < 32; y++) 50. { 51. b += GetBrith(b32.GetPixel(x, y)); 52. } 53. collumn_buffer[x] = b; 54. } 55. for (int y = 0; y < 32; y++) 56. { 57. float b = 0; 32

58. for (int x = 0; x < 32; x++) 59. { 60. b += GetBrith(b32.GetPixel(x, y)); 61. } 62. row_buffer[y] = b; 63. } 64. Int64 res = 0; 65. for (int i = 0; i < 32; i++) 66. { 67. if (row_buffer[i] > row_buffer[(i + 1) % 32]) res |= (Int64)1 << i; 68. if (collumn_buffer[i] > collumn_buffer[(i + 1) % 32]) res |= (Int64)1 << (i + 32); 69. } 70. b32.Dispose(); 71. return res; 72. } 73. static float GetBrith(Color color) 74. { 75. return (color.R + color.G + color.B) / 3f; 76. 77. } } 78. 79. public static class DHashAlg 80. { 81. public static Int64 Calculate(Image image) 82. { 83. Int64 res = 0; 84. var bitmap = ImageUtils.ResizeImage(image, 9, 8); 85. int i = 0; 86. for (int y = 0; y < 8; y++) 87. { 88. for (int x = 0; x < 8; x++) 89. { 90. Color c1 = bitmap.GetPixel(x, y); 33

91. byte a1 = ImageUtils.CalculateWeightByAvgOfChanels(c1); 92. Color c2 = bitmap.GetPixel(x + 1, y); 93. byte a2 = ImageUtils.CalculateWeightByAvgOfChanels(c2); 94. if (a1 > a2) 95. { 96. res |= ((Int64)1 << i); 97. } 98. i++; 99. } 100. } 101. return res; 102. } 103. 104. } 105. public static class FastFeatures 106. { 107. public struct FPoint 108. { 109. public byte _x; 110. public byte _y; 111. public int _w; 112. } 113. private static int[] offsetX = new int[] { 0, 1, 2, 3, 3, 3, 2, 1, 0, -1, -2, - 3, -3, -3, -2, -1 }; 114. private static int[] offsetY = new int[] { 3, 3, 2, 1, 0, -1, -2, -3, -3, -3, - 2, -1, 0, 1, 2, 3 }; 115. public static Bitmap Do(Bitmap bitmap, FPoint[] res) 116. { 117. 118. Bitmap rBitmap = null; 119. if (bitmap.Width > bitmap.Height) 120. { 121. rBitmap = ImageUtils.ResizeImage(bitmap, 256, (int)((float)bitmap.Height / (float)bitmap.Width * 256)); 34

122. } 123. else 124. { 125. rBitmap = ImageUtils.ResizeImage(bitmap, 256, (int)((float)bitmap.Width / (float)bitmap.Height * 256f)); 126. } 127. for (int x = 3; x < rBitmap.Width - 3; x++) 128. { 129. for (int y = 3; y < rBitmap.Height - 3; y++) 130. { 131. int w = GetPixelWeight(rBitmap, x, y); 132. int maxI = -1; 133. for (int i = 0; i < res.Length; i++) 134. { 135. if (w > res[i]._w) 136. { 137. maxI = i; 138. } 139. } 140. if (maxI != -1) 141. { 142. for (int i = 1; i <= maxI; i++) 143. { 144. res[i - 1] = res[i]; 145. } 146. res[maxI] = new FPoint() { _w = w, _x = (byte)x, _y = (byte)y }; 147. } 148. } 149. } 150. for (int i = 0; i < res.Length; i++) 151. { 152. rBitmap.SetPixel(res[i]._x, res[i]._y, Color.Red); 153. for (int j = 0; j < 16; j++) 154. { 35

155. int oX = offsetX[j]; 156. int oY = offsetY[j]; 157. rBitmap.SetPixel(res[i]._x + oX, res[i]._y + oY, Color.Green); 158. } 159. } 160. return rBitmap; 161. } 162. private static int GetPixelWeight(Bitmap bitmap, int x, int y) 163. { 164. int b = 0; 165. Color currentColor = bitmap.GetPixel(x, y); 166. int currentB = (currentColor.R + currentColor.B + currentColor.G) / 3; 167. for (int i = 0; i < 16; i++) 168. { 169. int oX = offsetX[i]; 170. int oY = offsetY[i]; 171. Color c = bitmap.GetPixel(x + oX, y + oY); 172. var nb = ((c.R + c.G + c.B) / 3 - currentB); 173. b += nb; 174. } 175. return b; 176. 177. } 178. } 179. public static class ImageUtils 180. { 181. public static Bitmap ResizeImage(Image image, int width, int height) 182. { 183. var destRect = new Rectangle(0, 0, width, height); 184. var destImage = new Bitmap(width, height); 185. 186. destImage.SetResolution(image.HorizontalResolution, image.VerticalResolution); 187. 36

188. using (var graphics = Graphics.FromImage(destImage)) 189. { 190. graphics.CompositingMode = CompositingMode.SourceCopy; 191. graphics.CompositingQuality = CompositingQuality.HighQuality; 192. graphics.InterpolationMode = InterpolationMode.HighQualityBicubic; 193. graphics.SmoothingMode = SmoothingMode.AntiAlias; 194. graphics.PixelOffsetMode = PixelOffsetMode.HighQuality; 195. 196. using (var wrapMode = new ImageAttributes()) 197. { 198. wrapMode.SetWrapMode(WrapMode.TileFlipXY); 199. graphics.DrawImage(image, destRect, 0, 0, image.Width, image.Height, GraphicsUnit.Pixel, new ImageAttributes()); 200. } 201. } 202. 203. return destImage; 204. } 205. public static byte CalculateWeightByAvgOfChanels(Color c) 206. { 207. return (byte)((c.R + c.G + c.B) / 3f); 208. 209. } } 210. } 37

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв