В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок. Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра 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 байта представить в виде матрицы 16x16 бит. А потом эту матрицу пропустить через перцептивный хеш PHash. Результатом должно было оказаться как раз 64 битное число.
Теперь мы подошли к полному описанию концепта.
Как работает индексация
1. Получаем ключевые точки и дескрипторы ORB, выбираем количество требуемых точек на изображении.
2. Полученные дескрипторы по 32 байта представляем в виде битовой матрицы 16x16.
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 хешей в базе. И полный перебор всех изображений в базе занимает полторы минуты.
Для сравнения, в своем докладе krainov Александр Крайнов поясняет, что поиск дубликатов из 1 млн изображений у них занимает около двух минут.
Ссылки
[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 Мой прототип поиска по фрагментам
Автор: valbok
