Как найти изображение по кусочку

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

В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок. Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра 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 Мой прототип поиска по фрагментам

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

ORB – бесплатная, быстрая и эффективная альтернатива алгоритмам обнаружения ключевых точек SIFT и SURF. Алгоритм не патентован, а значит, его использование в любых проектах не ограничивается. Входит в состав opencv.

Для задачи поиска изображений по фрагменту на Python необходимы библиотеки numpy и opencv.

Загрузка изображений и перевод в монохром:

Поиск ключевых точек и дескрипторов:

Сравнение дескрипторов ключевых точек и сортировка результатов по расстоянию Хамминга:

matches будет содержать массивы объектов – результатов сравнения дескрипторов. Для каждого такого массива атрибут distance будет содержать значение расстояния Хэмминга.

Иллюстрация сравнения:

Отображение результата, отрисованы и сопоставлены первые 20 ключевых точек:

Для поиска исходного изображения фрагмента среди множества изображений предлагается:

При искажении изображения, в зависимости от способа искажения, качество работы алгоритма может сильно пострадать, например:

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

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

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