Способ найти нужную картину

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

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

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

Дескрипторы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 хешей в базе. Поиск и кластеризация всех дубликатов занимает полторы минуты. Включает в себя полный перебор и поиск совпадающих хешей.

Источник

Собственный алгоритм поиска похожих изображений. Теория

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

Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа OpenCV. Но если бы задача решалась так просто, то конкуренты уже давно бы этим воспользовались и сделали достойный продукт, но его на рынке нет. В общем, присущие нам перфекционизм, амбициозность и желание быть лучшими, не позволяют нам выводить на рынок продукт «как у всех», нам нужно лучше, быстрее, сильнее. Приняли решение самостоятельно разобраться в вопросе, выработать решение, написать подробное техническое задание и уже отдать на реализацию фрилансеру. Была надежда, что существуют готовые решения, которых просто не заметили конкуренты. Но изучив вопрос (а вместе с ним и алгоритмы ORB, BRIEF, FAST, SIFT, SURF, BRISK, A-KAZE, Viola-Jones и еще несколько) стало понятно, что у всех этих алгоритмов есть свои недостатки. Хотя для решения нашей задачи некоторые из вышеперечисленных алгоритмов и подходили, но как то неожиданно захотелось уникальности и простоты решения. И вот выношу на суд сообщества, алгоритм собственного сочинения.

Любителей покритиковать (конструктивно) прошу под кат.

1. Принцип работы алгоритма

Изначально, и это принципиально, был выбран способ сравнения изображений основанный на поиске и сравнении т.н. ключевых точек.

Как и любой (или практически любой) алгоритм подобного рода, мой состоит из следующих шагов.

Шаг 1. Поиск ключевых точек на изображении.
Шаг 2. Формирование дескриптора.
Шаг 3. Формирование бинарной строки (хэша).
Шаг 4. Сравнение хэшей обрабатываемого изображения с хэшами изображений хранящимися в БД.
Шаг 5. Получение результата в требуемом виде.

2. Описание работы алгоритма

2.1. Поиск ключевых точек на изображении.

Ключевая (особая точка, или особенность) – это точка изображения, удовлетворяющая ряду свойств:

• Определенность (distinctness) – особенность должна выделяться на фоне среди соседних точек.
• Устойчивость (repeatability) – изменение яркости, контрастности и цветовой гаммы не должны влиять на место особой точки на объекте или сцене.
• Стабильность (stability) –зашумленность изображения, не превышающая определенный порог, не должна влиять на работу детектора.
• Интерпретируемость (interpretability) – особые точки должны быть представлены в формате, пригодном для дальнейшей работы.
• Количество (quantity) – количество обнаруженных особых точек должно обеспечивать требуемому их количеству для обнаружения объектов.

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

Далее с помощью «Детектора углов Харриса» отбираем не большое (у меня это 50) количество самых значимых ключевых точек.

* С принципами работы детекторов FAST и Харриса, можно ознакомиться в интереснейшей статье lightsource «Детекторы углов».

2.2. Формирование дескриптора

Дескриптор (от лат. descriptor — описывающий) – описание особой точки, определяющее особенности её окрестности, представляет собой числовой или бинарный вектор определенных параметров. Длина вектора и вид параметров определяются применяемым алгоритмом. Дескриптор позволяет выделить особую точку из всего их множества на изображении, это необходимо для составления ключевых пар особенностей, принадлежащих одному объекту, при сравнении разных изображений.

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

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

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

2.3. Формирование хэша

Хеширование или хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

Как известно через Х точек можно проложить Х*(Х-1)/2 отрезков, т.е. из 50 точек можно составить 50*49/2=1225 отрезков. Т.е. наша строка будет состоять из 1225 целых чисел. Причем эти числа должны иметь одинаковое количество знаков. Требуемое количество знаков, выбирается исходя из разрешения изображения (например, для изображения 500*500 максимальна длина отреза 707 (по диагонали), а значит знаков должно быть 3).

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

Получим строку: А1, А2. А1225, где А1>А2>. >А1225

2.4. Сравнение хэша с БД

Для поиска подобных изображений в БД нужно сравнить полученный нами хэш А1, А2. А1225 с хранящимися в БД.

Для примера сравним хэш А1, А2. А1225, где А1>А2>. >А1225 с В1, В2. В1225 причем пусть дескрипторы А трехзначны, а дескрипторы В четырех. Это может быть в двух случаях, если изображения разные или если одно изображения в разных масштабах.

Для достижения инвариантности к масштабу приведем каждый дескриптор к единому масштабу. Для этого определяем максимальное число М той же разрядности, что и разрядность большего дескриптора (для нашего примера максимальное четырехзначное число М = 9999) и находим коэф. масштабирования К по формуле: Ка=М/А1 (для строки А1, А2. А1225) и Кв=М/В1 (для строки В1, В2. В1225). Далее приведем хаши к единому масштабу, для это перемножим каждый дескриптор хэша А на Ка, а каждый дескриптор хэша В на Кв. Запишем результаты в строки А’1, А’2. А’1225 и В’1, В’2. В’1225, округляя значения до целого числа. В результате получим 2 хэша одного масштаба и одной размерности.

Теперь строки А’1, А’2. А’1225 и В’1, В’2. В’1225 можно сравнивать. Для этого будем использовать модифицированную формулу расстояния Хемминга.

Дело в том, расстояние Хемминга учитывает количество ошибок, как количество не равных значений в строках. Но мы на предыдущем шаге применили округление до целого числа, что может привести к ложным результатам. Поэтому мы не будем считать ошибкой, если значения соответствующих дескрипторов строк А и В, отличаются на Е (т.е. разность Аi и Вi взятая по модулю должна быть больше Е, для того, что бы считать значения в строках не равными). Назовем Е «коэф. лояльности» и в общем случае принимаем Е=1.

Далее простым суммированием считаем количество ошибок. Получаем расстояние Р.

2.5. Получение результатов

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

Источник