Как по части фото найти целое

Поиск изображений по фрагменту

В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок. Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра DoG, после чего найти ключевые точки и получить их дескрипторы.
Кластеризация дубликатов сводится к поиску совпадений дескрипторов. Это и есть «цифровой формат» ключевых точек из статьи Кластеризация дубликатов в поиске по картинкам.

Но хотелось бы немного подробнее узнать, что это за дескрипторы и как производить по ним поиск.

Дескрипторы

Ключевые точки — это точки, которые в идеале не должны меняться при изменении или модификации изображения.
Дескрипторы — это, в общем виде, свертка характеристик и представление ключевых точек в формате доступном для проверки на совпадение.

Поиск эффективного выделения ключевых точек, их дескрипторов, а также методов проверки на совпадения, все еще остается на повестке дня.

Но надо с чего-то начинать, поэтому обратимся на помощь к библиотеке OpenCV.

Первое на что бросается взгляд — это дескрипторы SURF.
Которые обещают необычайную точность. Что и подтверждается после тестов.

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

Получается что на изображение с 1 000 ключевых точек, потребуется 128 000 чисел с плавающей точкой.
Кроме того, само обнаружение точек довольно сложная операция и требует значительное время. Что не позволяет эффективно использовать данный алгоритм на небольших устройствах. К тому же сам алгоритм закрытый и запатентован (в США).

После ознакомления с SIFT и SURF, захотелось чего-то простого в реализации с возможностью применить на небольшом сервере либо устройстве.

Перцептивные хеши

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

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

Данный метод рассчитан на поиск полных либо частичных дубликатов изображения. Т.е. при значительном изменении формата изображения либо вмешательство в контент приводит к невозможности проверки на совпадение, так как хеши будут заметно отличаться.

Другими словами перцептивные хеши не годятся для поиска полудубликатов.

Исходя из этого была предпринята попытка объединить SURF дескрипторы и перцептивные хеши с целью решить проблему поиска нечетких полудубликатов.

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

У данного метода есть два с половиной значительных недостатка:
1. низкая скорость проверки на совпадение на большом наборе хешей. Поиск по 1 млн хешей занимало 20 секунд
2. низкая скорость получения ключевых точек
3. низкая точность, множество ложных срабатываний, высокие требование к целевой базе, годится не для всех картинок, требует премодерации и т.д

Сама идея о том, что бы из изображения выделялось некоторое количество отпечатков (fingerprint), которые можно было бы просто сопоставить друг с другом, завораживала.

Поэтому было решено попытаться найти решения данным проблемам.

Низкая скорость выборки

Сложность поиска и подсчета расстояния Хэмминга на большом наборе данных является самостоятельной проблемой и требует независимого подхода.
После некоторых исследований тематики оказалось, что существует множество решений данной проблемы.
Был выбран и реализован наиболее эффективный из имеющихся алгоритм названный HEngine, который позволил в ~60 раз ускорить выборку из базы данных.

SURF и ключевые точки

Так как мы работаем уже с бинарными хешами, или отпечатками, а совпадение считаем расстоянием Хэмминга, то странно использовать такую махину как SURF и стоило бы рассмотреть другие методы получения ключевых точек и дескрипторов.

В общем виде OpenCV предоставляет два типа дескрипторов:

— Дескрипторы с плавающей точкой
— И бинарные дескрипторы

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

ORB: an efficient alternative to SIFT or SURF

OpenCV уже имеет у себя отличную альтернативу SURF, которая мало того, что открытая и без лицензионных ограничений, так еще легче и работает быстрее [1].

ORB — это Oriented FAST and Rotated BRIEF — улучшенная версия и комбинация детектора ключевых точек FAST и бинарных дескрипторов BRIEF.

ORB имеет один существенный нюанс для нас — размер дескрипторов 32 байта на одну точку.
Проверка на совпадение — это сумма расстояний Хэмминга для каждого байта дескриптора (первый сравнивается с первым, второй со вторым и тд).

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

Так как наш хеш это 64битное число, то требуется 32 байта дескриптора ужать в 8 байт и при этом не сильно потерять в точности.

После некоторых тестов было решено попробовать эти 32 байта представить в виде матрицы 16×16 бит. А потом эту матрицу пропустить через перцептивный хеш PHash. Результатом должно было оказаться как раз 64 битное число.

Теперь мы подошли к полному описанию концепта.

Как работает индексация

1. Получаем ключевые точки и дескрипторы ORB, выбираем количество требуемых точек на изображении.
2. Полученные дескрипторы по 32 байта представляем в виде битовой матрицы 16×16.
3. Конвертируем матрицу в 64битное число с помощью PHash.
4. Сохраняем 64битные отпечатки в MySQL.
5. Выбираем требуемое расстояние Хэмминга и запускаем демон HEngine, который будет выполнять поиск.

Как работает поиск

Выполняем идентичные шаги 1 — 3 из индексации, но только на запрашиваемом изображении.
4. Делаем запрос демону HEngine, который возвращает все хеши в заданном пределе.
5. Если требуется, отфильтровать неактуальные результаты.

Рис 1. Предел расстояния Хэмминга 7. Серые точки — это найденные ключевые точки. Зеленые — совпадающие точки. Красные — совпадающие стандартным ORB полным перебором.

А что в итоге?

В итоге удалось решить нескольких проблем:
— найти способ быстрого подсчета расстояния Хэмминга на большом наборе данных
— избавиться от большого и неудобного SURF
— увеличить скорость выделения ключевых точек и их отпечатков
— а также не потерять сильно в точности.

Что позволило находить изображения по их фрагменту, а также нечеткие полудубликаты без больших вычислительных ресурсов.

Рис 2. Сладкое к пятнице

Учитывая то, что в зависимости от настроек, описанный алгоритм через бинарные дескрипторы ORB выдает около 1 000 хешей на картинку.
На базу в 1 000 изображений получается 1 000 000 хешей в базе. Поиск и кластеризация всех дубликатов занимает полторы минуты. Включает в себя полный перебор и поиск совпадающих хешей.

Ссылки

[1] Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary R. Bradski: ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571.
[2] en.wikipedia.org/wiki/SURF
[3] ru.wikipedia.org/wiki/Расстояние_Хэмминга
[4] phash.org
[5] habrahabr.ru/post/143667 Кластеризация дубликатов в Яндекс.Картинках
[6] habrahabr.ru/post/211264 HEngine — алгоритм поиска хешей в пределах заданного расстояния Хэмминга на большом наборе данных
[7] github.com/valbok/img.chk Мой прототип поиска по фрагментам