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

Фаустов Богдан Андреевич

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

В данной работе рассматриваются теоретические основы методов MinHash и Locality-sensitive hashing (LSH), применяемых для решения задач поиска похожих изображений. С помощью оценок вероятностей обосновано использование этих методов. Описаны общие классы локально-чувствительных хэш-функций, изучена реализация метода LSH для векторов локальных дескрипторов изображений Google VisualRank. В среде Wolfram Mathematica 10.4.1 реализованы алгоритмы сравнения эскизов изображений как матриц цветов и с использованием множественного представления на основе цветов. Получены значения параметров, при которых LSH уменьшает время работы метода MinHash с сохранением качества определения похожих изображений.

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

Дипломы

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

ID: 587d364c5f1be77c40d58bf0

UUID: ddffd412-62e7-4322-86c6-e13cb89dafdb

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

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

Просмотры: 43

Фаустов Богдан Андреевич

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

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

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

Скачать - 844405 bytes

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

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

Содержание Введение......................................................................................................... 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 2

Введение Различные алгоритмы поиска похожих изображений широко применяются в средствах массовой информации, поисковых системах, социальных сетях, букинговых системах и т. п. С помощью поиска похожих изображений эффективно решаются задачи классификации изображений, удаления дубликатов, отслеживания нарушений авторских прав. Для сравнения изображений различных размеров можно использовать приведение размеров к некоторому эталонному разрешению, например, 16 × 16 пикселей. С помощью сравнения получаемых эталонов можно быстро найти класс вероятно похожих изображений, среди которых можно провести более детальный анализ, например, сравнить их по эталонам других размеров. Сравнение эталонов можно проводить с помощью простых процедур, таких как вычисление нормы разности матриц, состоящих из закодированных числами цветов пикселей изображений. Однако подобные подходы требуют значительных затрат времени и по этой причине не приспособлены для решения задач классификации изображений. Эффективным подходом к сравнению эталонных изображений является использование представления изображений в виде неупорядоченных множеств некоторых заранее выделенных элементов. Например, можно разбить все возможные цвета на несколько групп, и построить по заданному изображению множество всех групп цветов его пикселей. Для оценки близости множественных представлений изображений применяются различные коэффициенты сходства множеств, например, коэффициент Жаккара. Данный подход можно использовать также для сравнения похожести других объектов, допускающих представление в виде множеств, таких как текстовые документы, видеозаписи, популяции организмов, химические вещества и т. п. Вычисление коэффициентов сходства изображений напрямую является достаточно трудоемкой задачей. Для быстрого приближенного вычисления коэффициента Жаккара можно использовать метод MinHash. При применении 3

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

Постановка задачи В данной работе были поставлены следующие задачи. 1. Обосновать использование метода MinHash. 2. Обосновать использование LSH для сигнатур метода MinHash. 3. Рассмотреть общие классы локально-чувствительных хэш-функций, которые можно использовать для понижения размерности данных. 4. Изучить и обосновать реализацию LSH для Google VisualRank. 5. Реализовать в виде программы в среде Wolfram Mathematica 10.4.1 методы определения похожих изображений, изучить их варианты для различных параметров и сравнить время их работы. 5.1. Методы, основанные на сравнении представлений изображений в виде упорядоченных векторов, состоящих из закодированных числами цветов пикселей. 5.2. Методы, основанные на сравнении представлений изображений в виде множеств с использованием коэффициента Жаккара. 5.3. Методы, основанные на сравнении представлений изображений в виде множеств с использованием MinHash. 5.4. Методы, использующие LSH сигнатур метода MinHash. 5

Обзор литературы Первые понятия, относящиеся к LSH, были предложены Уди Манбером в 1994 году в работе, посвященной поиску похожих файлов в большой файловой системе [1]. Он предложил идею шинглов – выделенных из текста для проверки схожести последовательностей идущих друг за другом слов. Наряду с этим были использованы также контрольные суммы. Сами понятия шинглов и «похожести» двух документов были сформулированы позднее в 1997 году Андреем Бродером в работе о сходстве и локализации документов [2]. Под 𝑘-шинглами для документа понимается последовательность, состоящая из 𝑘 подряд идущих токенов, которыми могут быть символы или слова, встречающиеся в документе. Документы, которые состоят из большого числа одинаковых шинглов, считаются похожими, даже если текст встречается в другом порядке. Затем Аристид Гионис, Петр Индик и Раджив Мотвани в своих работах 1997–98 годов [3, 4] предложили поиск сходства посредством использования хэширования, т. е. преобразования по определенному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Они предложили применение алгоритма LSH к задаче приближенного поиска ближайшего соседа. Позднее А. Андони и П. Индик показали, что приближенный поиск можно считать достаточно точным в задачах, где ближайший сосед находится проверкой всех приближенных соседей [5]. Также в 1998 году A. Broder, M. Charikar, A. Frieze и M. Mitzenmacher представили метод MinHash, использующий взаимно однозначные независимые (minwise independent) функции [6]. Эти концепции были разработаны в результате работы авторов над алгоритмом поисковой системы AltaVista, который был использован для обнаружения дубликатов веб-страниц и устранения их из результатов поиска. LSH может использоваться для идентификации и поиска видео. В этом случае векторы признаков строятся из видеокадров с использованием определенных цветовых гистограмм. В работе [7] авторы рассматривают недостатки 6

применения LSH для этой цели. В 2005 году S. Hu в своей работе [8] предложил новую схему для идентификации видео с применением LSH. В 2012–2013 годах появились статьи, в которых авторы показывают, что LSH может использоваться в поиске изображения [9, 10]. 7

Глава 1. Алгоритмы поиска похожих изображений Основная цель данной главы – описать и обосновать методы MinHash и LSH. Здесь приводятся основные определения и известные результаты, на которых основан данный алгоритм и которые используются в дальнейшем. Основу изложенного материала составляют лекции Anil Maheshwari [11]. 1.1. Сигнатуры множеств с сохранением сходства Пусть 𝑆 и 𝑇 – два непустых одновременно множества. Определим коэффициент Жаккара для множеств 𝑆 и 𝑇 как отношение числа элементов, входящих в пересечение множеств 𝑆 и 𝑇 к числу элементов, входящих в объединение этих множеств, т. е. по формуле |𝑆 ∩ 𝑇| . |𝑆 ∪ 𝑇| Рассмотрим естественное представление множества. Пусть 𝑈 – универсальное множество, элементы которого произвольно упорядочены. Пусть множество 𝑆 ⊂ 𝑈. Множество 𝑆 может быть представлено вектором длины |𝑈| из нулей и единиц, в котором 1 означает, что соответствующий элемент из универсального множества присутствует в 𝑆, и 0 означает отсутствие этого элемента в 𝑆. С конечным числом множеств из 𝑈 можно связать характеристическую матрицу, где каждый столбец представляет собой вектор, соответствующий определенному множеству и каждая строка соответствует элементу 𝑈. 𝑆1 𝑆2 𝑆3 𝑆4 Круиз 1 0 0 1 Лыжи 0 0 1 0 Курорты 0 1 0 1 Сафари 1 0 1 1 Остаться дома 0 0 1 0 Таблица 1.1. Характеристическая матрица 8

Например, рассмотрим таблицу 1.1. Здесь четыре множества 𝑆𝑖 (представляющие семьи) и универсальное множество 𝑈, состоящее из пяти элементов (варианты отдыха). Из характеристической матрицы следует, что множество 𝑆1 предпочитает круиз и сафари, а 𝑆2 любит посещать только курорты. Одним из эффективных способов нахождения сигнатуры для набора множеств является применение метода MinHash: сначала строки характеристической матрицы случайным образом переставляются, затем для каждого множества 𝑆𝑖 (столбец в характеристической матрице), можно найти MinHashзначение ℎ как номер (начиная с 0) первой строки, в которой есть 1 (если в столбце нет единиц, в качестве значения ℎ можно взять |𝑈|) . Используя предыдущий пример, предположим, что результат перестановки строк представлен в таблице 1.2. 𝑆1 𝑆2 𝑆3 𝑆4 Лыжи 0 0 1 0 Сафари 1 0 1 1 Остаться дома 0 0 1 0 Курорты 0 1 0 1 Круиз 1 0 0 1 Таблица 1.2. Характеристическая матрица после перестановки строк Тогда значения MinHash для соответствующих множеств ℎ(𝑆1 ) = 1, ℎ(𝑆2 ) = 3, ℎ(𝑆3 ) = 0 и ℎ(𝑆4 ) = 1. Следующая лемма показывает, что значение коэффициента Жаккара двух множеств совпадает с вероятностью того, что после случайной перестановки строк характеристической матрицы их значения MinHash окажутся равными. Лемма 1.1. Для любых двух множеств 𝑆𝑖 и 𝑆𝑗 вероятность того, что ℎ(𝑆𝑖 ) = ℎ(𝑆𝑗 ) равна коэффициенту Жаккара этих множеств. Доказательство. Представим множества 𝑆𝑖 и 𝑆𝑗 в виде столбцов перед случайной перестановкой. Тогда строки можно разделить на три типа: (a) строки имеют в обоих столбцах 0; 9

(b) строки имеют в обоих столбцах 1; (c) строка имеет в одном столбце 1, в другом столбце – 0. Пусть 𝑋 – число строк типа (b), 𝑌 – число строк типа (c). Заметим, что коэффициент Жаккара множеств 𝑆𝑖 и 𝑆𝑗 равен 𝑋 𝑋+𝑌 , так как 𝑋 – размер пересе- чения 𝑆𝑖 ∩ 𝑆𝑗 , 𝑋 + 𝑌 – размер объединения 𝑆𝑖 ∪ 𝑆𝑗 . Теперь рассмотрим вероятность того, что ℎ(𝑆𝑖 ) = ℎ(𝑆𝑗 ). Пусть строки переставляются в случайном порядке. Затем будем просматривать строки сверху вниз. Тогда вероятность встретить тип (b) перед типом (c) равна 𝑋 𝑋+𝑌 . Но если первая строка сверху, кроме (а) строк является типом (b), то, очевидно, что ℎ(𝑆𝑖 ) = ℎ(𝑆𝑗 ). С другой стороны, если первая строка будет типа (c), то множество с 1 получает эту строку в качестве MinHash, а множество с 0 в этой строке, имеет 1 в другой строке, идущей дальше. Следовательно, ℎ(𝑆𝑖 ) ≠ ℎ(𝑆𝑗 ), если первая строка будет типа (c). Таким образом, показано, что вероятность того, что ℎ(𝑆𝑖 ) = ℎ(𝑆𝑗 ) равна 𝑋 𝑋+𝑌 , что совпадает с коэффициентом Жаккара для множеств 𝑆𝑖 и 𝑆𝑗 . Лемма до- казана. Рассмотрим MinHash-сигнатуры, которые имеют меньшие размеры матрицы, полученные путем неоднократного применения метода MinHash к характеристической матрице. Пусть 𝑀 обозначает характеристическую матрицу для множества системы 𝑆 универсального множества 𝑈. Выберем набор 𝑛 случайных перестановок строк характеристической матрицы. Для каждого множества в 𝑆 можно вычислить его ℎ-значение по отношению к каждому набору из 𝑛 перестановок. Это приводит к сигнатурной матрице – матрице, состоящей из |𝑆| столбцов и 𝑛 строк, где (𝑖, 𝑗)-му элементу соответствует сигнатура 𝑗-го множества относительно 𝑖-й хэш-функции. Обычно сигнатурная матрица должна быть значительно меньшего размера, чем 𝑀. Приведем пример минимальной хэш-сигнатуры, полученной из таблицы 10

1.1 с помощью перестановок 𝑛=2 (задающихся функциями ℎ1 (𝑟) = 𝑟 + 1 mod 5, и ℎ2 (𝑟) = 3𝑟 + 1 mod 5, где 𝑟 – номер строки таблицы 1.1, начиная с 0). 𝑆1 𝑆2 𝑆3 𝑆4 ℎ1 1 3 0 1 ℎ2 0 2 0 0 Таблица 1.3. Сигнатурная матрица для четырех множеств Вычисление сигнатурной матрицы должно быть сделано в электронном виде: используя описанный метод, необходимо провести 𝑛 случайных перестановок характеристической матрицы 𝑀 достаточно большого размера, и это является трудоемкой задачей. Можно использовать 𝑛 случайных хэш-функций, переставляющих строки из 𝑀. Будем считать, что отображение из |𝑈| элементов на себя не вызовет много совпадений, однако некоторые совпадения могут быть. Таким образом, ℎ(𝑟) для строки с номером 𝑟 (начиная с 0) из матрицы 𝑀 обозначает новый номер строки после перестановки. Ниже приведено краткое описание алгоритма для вычисления сигнатурной матрицы. Шаг 1. Выбрать 𝑛 случайных хэш-функций ℎ1 , … , ℎ𝑛 . Шаг 2. Создать массив 𝐻 из 𝑛 строк и |𝑆| столбцов для хранения сигнатурной матрицы и заполнить его ∞. Шаг 3. Выполнить следующие шаги для каждой строки с номером 𝑟 из матрицы 𝑀. 1. Вычислить значения ℎ1 (𝑟), … , ℎ𝑛 (𝑟). 2. Для каждого 𝑐 = 1, … , |𝑆|, если 𝑀[𝑟, 𝑐] = 1, то присвоить 𝐻[𝑖, 𝑐] = min(𝐻[𝑖, 𝑐], ℎ𝑖 (𝑟)) для 𝑖 = 1, … , 𝑛. Заметим, что для каждого ненулевого элемента из 𝑀, проводится 𝑂(𝑛) вычислений, и, кроме памяти для сохранения 𝑛 хэш-функций, никакая дополнительная память не требуется. 11

Несмотря на то, что сигнатурная матрица имеет меньший размер по сравнению с характеристической матрицей, ее размер по-прежнему может быть достаточно большим. К тому же, если документы сравниваются попарно, то это займет большое количество времени. Для быстрого попарного сравнения можно применить LSH-метод хэширования, увеличивающий вероятность коллизии объектов, которые имеют шансы быть схожими. 1.2. LSH для MinHash-сигнатур LSH – вероятностный метод понижения размерности многомерных данных. Основная идея состоит в таком подборе хэш-функций для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину. Документы должны хэшироваться многократно для увеличения вероятности совпадений или различий. Ключевым моментом является то, что только документы, которые попадают в одну и ту же корзину, рассматриваются как потенциально похожие. Если два документа не отображаются в одну и ту же корзину при любом хэшировании, то они больше не рассматриваются по этой методике. Очевидно, нужно минимизировать количество разнородных документов, которые могут попасть в одну корзину. В то же время подобные документы по крайней мере один раз должны хэшироваться в одну и ту же корзину. Пусть найдена MinHash-сигнатурная матрица для множества документов, как показано в предыдущем параграфе. Разделим строки этой матрицы на 𝑛 𝑏 = групп, где каждая группа имеет 𝑟 последовательных строк (таблица 1.4). 𝑟 Будем считать, что 𝑛 делится на 𝑟. … 1 0 Группа 1 … 3 2 … 0 1 0 0 2 … 1 2 2 … 3 1 1 … Группа 2 … … … Группа 3 … … … 12

Группа 4 … … … Таблица 1.4. Сигнатурная матрица, разделенная на четыре группы из трех строк каждая Для каждой группы определим хэш-функцию ℎ: ℝ𝑟 → 𝑍, которая векторстолбец длины 𝑟 отображает в целое число (т. е. корзину). Можно выбрать одну и ту же хэш-функцию для всех групп, но корзины должны быть различны для каждой группы. Теперь, если два вектора длины 𝑟 в некоторой группе хэшфункцией отображаются в одну и ту же корзину, то соответствующие документы потенциально похожи. Покажем это. Лемма 2.1. Пусть 𝑠 – коэффициент Жаккара для двух документов. Вероятность того, что MinHash-сигнатурная матрица совпадает во всех строках по крайней мере одной из групп для этих двух документов (того, что они будут похожи после хэширования и разбиения на группы) равна 1 − (1 − 𝑠 𝑟 )𝑏 . Доказательство. Из леммы 1.1 следует, что вероятность того, что MinHash для этих двух документов совпадают в какой-либо конкретной строке сигнатурной матрицы, равна 𝑠. Таким образом, вероятность того, что сигнатуры совпадают во всех строках одной конкретной группы, есть 𝑠 𝑟 . Вероятность того, что сигнатуры не совпадут, по крайней мере, одной из строк такой группы, равна 1 − 𝑠 𝑟 . Теперь вычислим вероятность того, что в каждой группе сигнатуры нет совпадений, по крайней мере, в одной из строк. Так как имеется 𝑏 групп, эта вероятность равна (1 − 𝑠 𝑟 )𝑏 . Следовательно, вероятность того, что сигнатуры совпадут, по крайней мере, в одной из групп есть 1 − (1 − 𝑠 𝑟 )𝑏 . Лемма доказана. Можно построить график функции 1 − (1 − 𝑠 𝑟 )𝑏 , откладывая по оси абсцисс значения 𝑠, а по оси ординат – значения функции с фиксированными значениями 𝑏 и 𝑟 (рисунок 2). График этой функции имеет форму 𝑆-образной кривой. На самом деле, кривая будет иметь такую форму независимо от значений 𝑏 и 𝑟. Из графика видно, что если коэффициент Жаккара 𝑠 приближается к 1, то значение этой функции – вероятность попадания входных элементов в одну 13

и ту же корзину – также приближается к 1. Несмотря на это одним из важных аспектов этой кривой есть то, что самый крутой наклон происходит для значе− 1 𝑟 ния 𝑠, приблизительно равного 𝑡 = 𝑏 . Другими словами, если коэффициент Жаккара для двух документов превышает порог 𝑡, то вероятность быть похожими c помощью LSH очень высока. Вероятность стать кандидатами Коэффициент Жаккара Рисунок 1.1. S-кривая Таким образом, использование LSH позволяет сравнить документы (или их MinHash-сигнатуры) и выяснить, являются ли они на самом деле похожими. 1.3. Локально-чувствительные функции В этом параграфе рассматривается семейство LS-функций (локально-чувствительных функций), которое обозначается 𝐹. Например, MinHash-функции образуют семейство таких функций. Напомним, что мера расстояния (метрика) является неотрицательной симметричной функцией, удовлетворяющей неравенству треугольника. Этим свойствам удовлетворяют, например, евклидово расстояние между точками в пространстве, расстояние Жаккара и расстояние Хэмминга. Определение 3.1. Пусть 𝑑 – мера расстояния и пусть для двух расстояний 𝑑1 и 𝑑2 этой меры выполняется 𝑑1 < 𝑑2 . Семейство функций 𝐹 называется 14

(𝑑1 , 𝑑2 , 𝑝1 , 𝑝2 )-чувствительным, если для любой функции 𝑓 ∈ 𝐹 выполняются следующие два условия: 1) если 𝑑(𝑥, 𝑦) ≤ 𝑑1 , то вероятность 𝑃[𝑓(𝑥) = 𝑓(𝑦)] ≥ 𝑝1 ; 2) если 𝑑(𝑥, 𝑦) ≥ 𝑑2 , то вероятность 𝑃[𝑓(𝑥) = 𝑓(𝑦)] ≤ 𝑝2 . Если два элемента находятся близко друг к другу по отношению к функции расстояния, то вероятность того, что они хэшируются в одну и ту же корзину, будет высокой. И наоборот, если эти два элемента являются далекими друг от друга, то вероятность того, что они хэшируются в одну и ту же корзину, будет низкой. В качестве примера рассмотрим расстояние Жаккара для двух множеств, которое определяется как 1 минус коэффициент Жаккара этих множеств. Пусть 0 ≤ 𝑑1 < 𝑑2 ≤ 1. Заметим, что семейство MinHash-сигнатур является (𝑑1 , 𝑑2 , 1 − 𝑑1 , 1 − 𝑑2 )-чувствительным. Предположим, что коэффициент Жаккара для двух документов не меньше, чем 𝑠. Тогда их расстояние не может быть большим чем 𝑑1 = 1 − 𝑠. По лемме 1.1 вероятность того, что MinHash-сигнатуры будут равны, не может быть меньше 𝑠 = 1 − 𝑑1 . Предположим, что мера расстояния между двумя документами больше или равна 𝑑2 . Отсюда их коэффициент Жаккара самое большее равен 𝑠 = 1 − 𝑑2 , и вероятность того, что MinHash-сигнатуры совпадут, не может быть больше чем 𝑠 = 1 − 𝑑2 . Рассмотрим (𝑑1 , 𝑑2 , 𝑝1 , 𝑝2 )-чувствительное семейство функций 𝐹. Можно построить новое семейство 𝐺 следующим образом. Каждая функция 𝑔 ∈ 𝐺 формируется из множества 𝑟 независимо выбранных функций из 𝐹, например 𝑓1 , 𝑓2 , … , 𝑓𝑟 для некоторого фиксированного значения 𝑟, и 𝑔(𝑥) = 𝑔(𝑦) тогда и только тогда, когда для всех 𝑖 = 1, … , 𝑟 выполняется 𝑓𝑖 (𝑥) = 𝑓𝑖 (𝑦). Это семейство называют AND-семейством. Предложение 3.1. AND-семейство является (𝑑1 , 𝑑2 , 𝑝1𝑟 , 𝑝2𝑟 )-чувствительным семейством функций. 15

Доказательство. Степень 𝑟 в формулировке предложения появляется потому, что вычисляется вероятность одновременного осуществления 𝑟 независимых событий. Можно также построить 𝐺 как OR-семейство. Тогда каждая функция 𝑔 из 𝐺 строится следующим образом. Из 𝐹 независимо друг от друга выбираются 𝑏 функций 𝑓1 , 𝑓2 , … , 𝑓𝑏 . И 𝑔(𝑥) = 𝑔(𝑦) тогда и только тогда, когда 𝑓𝑖 (𝑥) = 𝑓𝑖 (𝑦) хотя бы для одной из функций из {𝑓1 , 𝑓2 , … , 𝑓𝑏 }. Предложение 3.2. OR-семейство является (𝑑1 , 𝑑2 , 1 − (1 − 𝑝1 )𝑏 , 1 − (1 − 𝑝2 )𝑏 )-чувствительным семейством функций. Доказательство. Формулы преобразования вероятностей в формулировке предложения появляются потому, что вычисляется вероятность осуществления по крайней мере одного из 𝑏 независимых событий. Эта вероятность вычисляется через вероятность того, что ни одно из 𝑏 событий не происходит. Рассмотрим некоторые значения 𝑏 и 𝑟 для того, чтобы увидеть результат таких семейств, которые показаны выше. Можно так же объединить функции этих семейств через композицию. Сначала построим AND-семейство для определенного значения 𝑟, потом – OR-семейство для определенного значения 𝑏, затем – композицию. Рассмотрим таблицу 1.5 вероятностей для различных значений 𝑝. p p5 (F1) 1-(1-p)5 (F2) 1-(1-p5)5 (F3) (1-(1-p)5)5 (F4) 0,2 0,00032 0,67232 0,00159 0,13703 0,4 0,01024 0,92224 0,05016 0,66714 0,6 0,07776 0,98976 0,33285 0,94983 0,8 0,32768 0,99968 0,86263 0,99840 0,9 0,59049 0,99999 0,98848 0,99995 Таблица 1.5. Иллюстрация четырех семейств, полученных при различных значениях 𝑝 Здесь 𝐹1 – AND-семейство для 𝑟 = 5, 𝐹2 – OR-семейство для 𝑏 = 5, 𝐹3 – AND-OR семейство для 𝑟 = 5 и 𝑏 = 5, 𝐹4 – OR-AND семейство для 𝑟 = 5 и 16

𝑏 = 5. Прокомментируем данные таблицы 1.5. Рассмотрим столбцы. Пусть 𝐹 является (0,2; 0,6; 0,8; 0,4)-чувствительной MinHash-функцией семейства. Это означает, что если расстояние между двумя документами 𝑥 и 𝑦 меньше или равно 0,2, то с вероятностью больше или равной 0,8¸ они будут хэшироваться в одну и ту же корзину. Точно так же, если расстояние между 𝑥 и 𝑦 больше или равно 0,6, то маловероятно, что они будут хэшироваться в одну и ту же корзину (вероятность хэширования в ту же самую корзину меньше или равна 0,4). Теперь рассмотрим две строки, соответствующие вероятностям 𝑝2 = 0,4 и 𝑝4 = 0,8. Заметим, что для AND-семейства 𝑝5 существенно меньше, чем 𝑝, но 𝑝25 близко к 0, а 𝑝45 находится далеко от 0. Для OR-семейства 1 − (1 − 𝑝)5 ≥ 𝑝, но все же значение, соответствующее 𝑝4 близко к 1, а значение, соответствующее 𝑝2 , далеко от 1. Обратим внимание на то, что AND-OR семейство (𝐹3 ) соответствует семейству LSH-функций для MinHash-сигнатуры, рассмотренного в параграфе 1.2. В этом случае значение, соответствующее 𝑝4 близко к 1, а значение, соответствующее 𝑝2 , ближе к 0. Отметим, что значения функции 1 − (1 − 𝑝5 )5 образуют 𝑆-образную кривую с неподвижной точкой 𝑝 ≈ 0,7549, которую можно найти из уравнения 𝑝 = 1 − (1 − 𝑝5 )5 . Отсюда следует, что для значений 𝑝, значительно меньших 0,75, AND-OR семейство близко к 0; аналогично, для значений 𝑝, больших чем 0,75, – близко к 1. Отметим, что LS-семейства можно построить не только для меры расстояния Жаккара, но и для евклидова расстояния, расстояния Хэмминга и других метрик. 1.4. Использование LSH в алгоритме Google VisualRank С помощью локально-чувствительного хэширования можно выполнять поиск похожих изображений. Часто изображения обрабатываются с помощью глобальных дескрипторов, таких как цветные гистограммы, для получения 17

векторов, которые затем сравниваются с использованием различных мер расстояния. Одним из очевидных приложений сходства изображений является веб-поиск. Однако большинство поисковых систем не используют сходство изображений в поиске; вместо этого они полагаются на информацию, собранную из окружающего изображение текста на веб-странице вместе с метаданными изображения. В этом параграфе покажем, как Google в алгоритме VisualRank использует для поиска похожих изображений метод LSH вместе с несколькими локально-чувствительными семействами функций, которые были предложены в качестве меры сходства изображений. В алгоритме VisualRank наряду с LSH используются методы компьютерного зрения. Рассмотрим поиск изображения с помощью текстового запроса. Существующий метод поиска получает первоначальные изображения-кандидаты, которые наряду с другими изображениями группируются согласно их сходству. Далее в каждой группе производится измерение «важности» изображений, что приводит к наиболее подходящим запросу результатам. При этом требуется достигнуть соглашения между пользователями интернета о том, что считать похожими изображениями. Мера сходства изображений имеет решающее значение для VisualRank, так как она определяет структуру используемого графа. Изображения считают схожими, если их локальные признаки хэшируются в одну и ту же корзину хэш-таблицы. В качестве примера рассмотрим рисунок 1.2. В этом примере синие и зеленые круги – корзины, в которые хэшируются признаки; B подобно (схоже с) C, и C подобно D. Вначале система VisualRank извлекает из изображений векторы локальных дескрипторов (признаков) с использованием масштабно-инвариантной функции преобразования (SIFT). Вместо цветовых гистограмм, о которых говорилось выше, используются локальные дескрипторы, так как они позволяют рассматривать сходство изображений с потенциалом вращения, масштаба и преобразований. Затем к векторам признаков применяется LSH с использованием 𝑝-устойчивого распределения. 18

Изображения Признаки Хэш-функции Совпадающие признаки Схожие множества Рисунок 1.2. Пример схемы хэширования признаков изображений Определение 4.1. Распределение 𝐷 называется 𝑝-устойчивым при 𝑝 > 0, если для любых 𝑛 вещественных чисел 𝑣1 , 𝑣2 , … , 𝑣𝑛 и независимых одинаково распределенных случайных величин 𝑋1 , 𝑋2 , … , 𝑋𝑛 с распределением 𝐷 случайная величина 𝑣1 𝑋1 + 𝑣2 𝑋2 +. . . +𝑣𝑛 𝑋𝑛 имеет такое же распределение, как вели1 чина (|𝑣1 |𝑝 + |𝑣2 |𝑝 + ⋯ + |𝑣𝑛 |𝑝 )𝑝 𝑋, где 𝑋 является случайной величиной с распределением 𝐷. Заметим, что значение случайной величины 𝑣1 𝑋1 + 𝑣2 𝑋2 +. . . +𝑣𝑛 𝑋𝑛 может быть получено как скалярное произведение вектора 𝑣 на вектор 𝑎, полученный из 𝑝-устойчивого распределения 𝑋. Из определения следует, что эта случайная величина имеет такое же распределение, как 𝑝-норма вектора 𝑣, умноженная на случайную величину из того же распределения. Суть метода эскизов состоит в том, что для оценки ‖𝑣‖𝑝 .вычисляется скалярное произведение 𝑣𝑎. Нормальное распределение с нулевым математическим ожиданием является 2-устойчивым. В рамках применяемой схемы используется нормальное 19

распределение. LSH использует устойчивые распределения для того, чтобы применить метод эскизов к векторам признаков большой размерности. Однако вместо того, чтобы использовать его для оценки нормы векторов, метод эскизов используется для получения значений хэш-функций от них. Эти значения отображают каждый вектор в точку на вещественной оси, которая разделена на равные по ширине сегменты длиной 𝑟, представляющие корзины. Определим каждую хэш-функцию из семейства следующим образом: 𝑣𝑎 + 𝑏 ℎ(𝑣) = ⌊ ⌋, 𝑟 где 𝑣 – исходный 𝑑-мерный вектор локальных признаков, 𝑎 – 𝑑-мерный случайный вектор с элементами, независимо выбранными из 𝑝-устойчивого распределения, 𝑏 – случайное число, которое выбирается из равномерного распределения на отрезке [0, 𝑟]. Обозначим через 𝑓𝑝 (𝑡) функцию плотности вероятности абсолютного значения рассматриваемого устойчивого распределения, и пусть 𝑐 = ‖𝑢 − 𝑣‖𝑝 для двух векторов 𝑢 и 𝑣. Так как случайный вектор 𝑎 из 𝑝-устойчивого распределения, 𝑢𝑎 − 𝑣𝑎 имеет распределение 𝑐𝑋, где 𝑋 является случайной величиной из устойчивого распределения. Поэтому вероятность совпадения значений хэш-функции 𝑟 1 𝑡 𝑡 𝑝(𝑐) = 𝑃[ℎ(𝑢) = ℎ(𝑣)] = ∫ (1 − ) 𝑓𝑝 ( ) 𝑑𝑡. 𝑐 𝑟 𝑐 0 Если два вектора 𝑢 и 𝑣 близки, то они будут иметь небольшую 𝑝-норму разности 𝑐 и должны попасть в одну корзину с высокой вероятностью. При фиксированном 𝑟 вероятность коллизий 𝑝(𝑐) монотонно убывает по 𝑐. Таким образом, семейство хэш-функций является (𝑑1 , 𝑑2 , 𝑝(𝑑1 ), 𝑝(𝑑2 ))-чувствительным. Заметим, что для каждого 𝑐 можно выбирать конечное 𝑟 так, чтобы сделать 𝑝 как можно меньше. 20

Глава 2. Реализация и тестирование алгоритмов Цель данной главы – описать программную реализацию различных методов определения похожих изображений и сравнить результаты их работы. Была рассмотрена база из 5586 изображений в формате JPEG с размерами по ширине от 112 до 1000 пикселей и высоте от 38 до 1000 пикселей включительно. Средняя ширина изображения составила 571 пиксель, а средняя высота – 459 пикселей. Среди данных изображений были группы изображений, отличающиеся друг от друга только различной обрезкой, надписями и по небольшим фрагментам. Параметры алгоритмов, такие как количество диапазонов значений компонент цветов, выбирались таким образом, чтобы такие похожие изображения успешно находились. Для сравнения изображений различных размеров использовалось приведение размеров к эталонному разрешению (получение эскизов). Опытным путем было установлено, что для определения похожих изображений в данной базе хорошо подходит эталонное разрешение 16 × 16 пикселей. Цвет каждого пикселя полученного эскиза кодировался методом TrueColor (24 бит на пиксель). По этому методу цвет пикселя представляется с использованием 256 уровней для каждой из трех компонент модели RGB: красного (R), зеленого (G) и синего (B), что в результате позволяет закодировать 16 777 216 (224 ) различных цветов. Таким образом, каждое изображение описывалось массивом целых чисел от 0 до 255 включительно с размерами 16 × 16 × 3 (цветовой матрицей). Такое описание одного изображения занимает 768 байт. Система Wolfram Mathematica 10.4.1 была выбрана для реализации алгоритмов потому, что она содержит удобные встроенные функции для работы с изображениями, обработки, анализа и визуального представления данных. Также стоит отметить, что используемый высокоуровневый мультипарадигмальный язык программирования Wolfram Language и удобная система встроенных функций позволяют получать очень короткий и интуитивно понятный 21

код, что уменьшает время разработки и облегчает понимание работы программы. 2.1. Сравнение цветовых матриц Пусть задано изображение (образец), для которого требуется найти наиболее похожие изображения из имеющейся базы. Представим данное изображение описанным выше методом в виде цветовой матрицы размером 16 × 16 × 3. Для решения задачи поиска похожих изображений нужно обеспечить хранение таких матриц для всей имеющейся базы изображений. После этого для поиска похожих на образец изображений достаточно обойти в цикле все цветовые матрицы в базе, для каждой вычислить норму разности между этой матрицей и цветовой матрицей образца и найти в этом цикле изображение из базы, на котором достигается наименьшее значение нормы. В качестве нормы была использована сумма модулей всех компонент цветовой матрицы, так как она вычисляется наиболее просто и учитывает отклонения всех компонент. Рисунок 2.1. Время работы алгоритма сравнения норм разности цветовых матриц в зависимости от количества изображений в базе 22

На рисунке 2.1 с помощью синих точек, соответствующих запускам программы с различным размером базы со случайными образцами, взятыми из нее, представлено измеренное время (в секундах) работы программы в зависимости от количества изображений в базе (от 1 до 5586). Очевидно, время работы цикла поиска наименьшего значения нормы разности цветовых матриц в среднем прямо пропорционально количеству изображений в базе. 2.2. Коэффициент Жаккара Теперь представим эскиз данного изображения-образца в виде множества цветов, состоящего из 16 × 16 цветов его пикселей. В качестве цвета пикселя будем использовать 3-мерный вектор целых чисел – компонент RGB, причем будем использовать числа от 0 до 15, разбив диапазон чисел от 0 до 255 из цветовой матрицы на 16 групп для увеличения вероятности совпадения цветов в изображениях. Рисунок 2.2. Время работы алгоритма сравнения цветовых множеств с помощью коэффициента Жаккара в зависимости от количества изображений в базе Тогда для поиска похожих на образец изображений можно обойти в цикле все множества цветов в базе, вычислить коэффициент Жаккара между каждым 23

таким множеством и множеством цветов образца и найти в этом цикле изображение из базы, на котором достигается наибольшее значение коэффициента Жаккара. 2.3. Метод MinHash Чтобы ускорить вычисление коэффициентов Жаккара для рассмотренных цветовых множеств, воспользуемся приближенным методом MinHash. Для этого нужно предварительно вычислить матрицу сигнатур. Для ее получения зададим 1000 случайных хэш-функций со значениями от 0 до 163 = 4096 (для имитации перестановки), отображающих цвет (вектор с 3 компонентами от 0 до 15) в число. Далее для каждого изображения из базы применим эти функции к каждому цвету из множества цветов данного изображения, и таким образом найдем наименьшее значение каждой хэш-функции для каждого изображения. Рисунок 2.3. Время работы алгоритма сравнения MinHash-сигнатур в зависимости от количества изображений в базе После этого для поиска похожих на образец изображений достаточно вычислить вектор сигнатур для множества цветов данного образца, и затем найти в цикле изображение из базы, столбец из матрицы сигнатур которого имеет 24

наибольшее количество одинаковых компонент с вектором сигнатур образца. 2.4. Метод LSH для сигнатур метода MinHash Для ускорения работы метода сравнения MinHash-сигнатур используем метод понижения размерности LSH. Для работы с этим методом без перестроения корзин требуется изображение-образец выбирать из базы, по которой были построены корзины. Разобьем матрицу сигнатур на группы по 2 строки. Далее в каждой группе выделим некоторое количество корзин, каждая из которых будет содержать по крайней мере 2 (этот параметр можно увеличивать для получения меньшего количества малозначимых корзин) изображения, которые имеют одинаковое значение хэш-функции от вектора из 2 значений MinHash, находящихся в данной группе. После того, как все корзины построены, для поиска похожих на образец изображений можно выбрать все корзины, содержащие данный образец. Затем можно выполнить поиск наиболее часто встречающихся изображений из этих корзин. Рисунок 2.4. Время работы алгоритма LSH для MinHash-сигнатур в зависимости от количества изображений в базе 25

Выводы После изучения работы программных реализаций описанных алгоритмов и выбора параметров были сформулированы следующие выводы. 1. Использование приведения размеров изображений к эталонным размерам эскизов позволяет быстро сравнивать их с помощью матричных представлений и уменьшает затраты памяти, которая требуется для работы алгоритмов. 2. Сравнение цветовых матриц по норме требует значительных затрат времени на вычисление норм разностей матриц, что не позволяет эффективно использовать данный алгоритм для решения задач классификации изображений. В отличие от других рассмотренных методов, данный метод использует представление изображения в виде упорядоченных элементов и, таким образом, позволяет сравнивать изображения с сохранением их структуры. 3. Прямое вычисление коэффициентов Жаккара для сравнения множественных представлений изображений занимает очень много времени. Метод MinHash представляет собой быстрое и эффективное приближение такого способа и пригоден для решения задач классификации изображений. 4. В случае, если размерность векторов сигнатур высока и время работы алгоритма MinHash неприемлемо, ее можно уменьшить, используя LSH. На время работы алгоритма непосредственно влияет количество построенных корзин. Использование корзин при правильном подборе параметров также позволяет автоматически решать задачи разделения изображений на группы похожих между собой. Метод LSH на имеющихся данных показал лучшее время работы из рассматриваемых алгоритмов. 26

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

Список литературы 1. Udi Manber. Finding similar files in a large file system. In in Proceedings of the USENIX Winter 1994 Technical Conference, pages 1–10, 1994. 2. A.Z. Broder. On the resemblance and containment of documents. In Com- pression and Complexity of Sequences 1997. Proceedings, pages 21–29, 1997. 3. Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. pages 518–529, 1997. 4. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: To- wards removing the curse of dimensionality. pages 604–613, 1998. 5. A. Andoni and P. Indyk. Near-optimal hashing algorithms for approxi- mate nearest neighbor in high dimensions. In Foundations of Computer Science, 2006. FOCS ’06. 47th Annual IEEE Symposium on, pages 459–468, 2006. 6. Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. Journal of Computer and System Sciences, 60:327–336, 1998. 7. Zixiang Kang, Wei Tsang Ooi, and Qibin Sun. Hierarchical, non-uniform locality sensitive hashing and its application to video identification. In Multimedia and Expo, 2004. ICME ’04. 2004 IEEE International Conference on, volume 1, pages 743–746 Vol.1, 2004. 8. S. Hu. Efficient video retrieval by locality sensitive hashing. In Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP ’05). IEEE International Conference on, volume 2, pages 449–452, 2005. 9. B. Kulis and K. Grauman. Kernelized locality-sensitive hashing. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 34(6):1092–1104, 2012. 10. Tanmoy Mondal, Nicolas Ragot, Jean-Yves Ramel, and Umapada Pal. A fast word retrieval technique based on kernelized locality sensitive hashing. In Document Analysis and Recognition (ICDAR), 2013 12th International Conference on, pages 1195–1199, 2013. 28

11. Maheshwari A. Topics in Algorithm Design-Lecture Notes for COMP 5703 [Электронный ресурс]/ A. Maheshwari. – School of Computer Science Carleton University, 2015. – 142 с. – Режим доступа: доступ свободный. http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Notes/editednotes.pdf 29

Рецензии:

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

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

Отзывы:

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