Введение 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 некоторые методы определения похожих изображений и проведено сравнение времени их работы.
В данной работе были рассмотрены теоретически основы методов MinHash и LSH и с помощью оценок вероятностей обосновано их использование. Описаны общие классы локально-чувствительных хэш-функций, изучена реализация метода LSH для векторов локальных дескрипторов Google VisualRank.
В среде Wolfram Mathematica 10.4.1 реализованы алгоритмы сравнения эскизов изображений как матриц цветов и с использованием множественного представления на основе цветов. Получены значения параметров, при которых LSH уменьшает время работы метода MinHash с сохранением качества определения похожих изображений.
Таким образом, все поставленные задачи были выполнены.
