Поиск похожих изображений

Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Алгоритмы поиска похожих изображений 8
1.1. Сигнатуры множеств с сохранением сходства 8
1.2. LSH для MinHash-сигнатур 12
1.3. Локально-чувствительные функции 14
1.4. Использование LSH в алгоритме Google VisualRank 17
Глава 2. Реализация и тестирование алгоритмов 21
2.1. Сравнение цветовых матриц 22
2.2. Коэффициент Жаккара 23
2.3. Метод MinHash 24
2.4. Метод LSH для сигнатур метода MinHash 25
Выводы 26
Заключение 27
Список литературы 28
Купить

Различные алгоритмы поиска похожих изображений широко применя­ются в средствах массовой информации, поисковых системах, социальных се­тях, букинговых системах и т. п. С помощью поиска похожих изображений эффективно решаются задачи классификации изображений, удаления дубли­катов, отслеживания нарушений авторских прав.
Для сравнения изображений различных размеров можно использовать приведение размеров к некоторому эталонному разрешению, например, 16x16 пикселей. С помощью сравнения получаемых эталонов можно быстро найти класс вероятно похожих изображений, среди которых можно провести более детальный анализ, например, сравнить их по эталонам других размеров.
Сравнение эталонов можно проводить с помощью простых процедур, та­ких как вычисление нормы разности матриц, состоящих из закодированных числами цветов пикселей изображений. Однако подобные подходы требуют значительных затрат времени и по этой причине не приспособлены для реше­ния задач классификации изображений.
Эффективным подходом к сравнению эталонных изображений является использование представления изображений в виде неупорядоченных мно­жеств некоторых заранее выделенных элементов. Например, можно разбить все возможные цвета на несколько групп, и построить по заданному изобра­жению множество всех групп цветов его пикселей. Для оценки близости мно­жественных представлений изображений применяются различные коэффици­енты сходства множеств, например, коэффициент Жаккара. Данный подход можно использовать также для сравнения похожести других объектов, допус­кающих представление в виде множеств, таких как текстовые документы, ви­деозаписи, популяции организмов, химические вещества и т. п.
Вычисление коэффициентов сходства изображений напрямую является достаточно трудоемкой задачей. Для быстрого приближенного вычисления коэффициента Жаккара можно использовать метод MinHash. При применении этого метода множество, соответствующее изображению, описывается с по­мощью вектора, каждая компонента которого представляет собой минималь­ное значение хэш-функции среди ее значений для всех элементов множества. Каждой компоненте вектора соответствует своя хэш-функция. Векторы, полу­чаемые с помощью метода MinHash, как правило, имеют большую размер­ность.
Locality-sensitive hashing (LSH, локально-чувствительное хэширование) - вероятностный метод понижения размерности многомерных данных. Этот ме­тод позволяет строить структуру для быстрого приближенного (вероятност­ного) поиска п-мерных векторов, «похожих» на искомый шаблон. Он часто используется, когда имеются чрезвычайно большие объемы данных, которые должны быть сравнены. LSH имеет большое количество применений. Он ис­пользуется в таких областях, как распознавание образов, вычислительная гео­метрия и сжатие данных, в классификации и кластеризации, в поисках плаги­ата, в работе с большими системами документооборота, в электронных биб­лиотеках и т. д.
В данной работе обосновывается использование метода MinHash и LSH для сигнатур, получаемых с помощью этого метода. Рассматриваются общие классы хэш-функций, которые можно использовать для понижения размерно­сти данных. Изучается реализация LSH для Google VisualRank. Реализованы в виде программы в среде Wolfram Mathematica 10.4.1 некоторые методы опре­деления похожих изображений и проведено сравнение времени их работы.
Купить