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

Статья будет несколько короче предыдущей т.к. расскажу только об отличиях двух алгоритмов. Поэтому желательно прочесть предыдущею статью, что бы «быть в теме».

Детектор ключевых точек

Первое, на чем хочу отдельно акцентировать внимание это то, что в моем алгоритме можно использовать любой детектор ключевых точек, который лучше подходит под ваши задачи и конкретные изображения. Подбирать наилучший детектор можно эмпирически, а можно использовать алгоритм для автоматического выбора, как это делают создатели алгоритма MODS (спасибо devpony за наводку).

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

Нам понадобится всего 10 самых значимых точек!

Дескриптор

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

Дескриптором будет являться ряд из длин трех сторон треугольника, записанные от большей к меньшей. А, В, С, где А>В>С.

Хэш

Из 10 точек можно построить 10*9*8/6=120 треугольников. Значит наш хэш будет состоять из 120 рядов по 3 числа А1, В1, С1; А2, В2, С2;...; А120, В120, С120.

Сравнение хэшей

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

В соответствии с третьим признаком подобия треугольников:

Если три стороны одного треугольника соответственно пропорциональны трем сторонам другого, то такие треугольники подобны.

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

Сравнить нужно все треугольники одного хэша, со всеми треугольниками второго. Если подобный треугольник нашелся, то эти 2 треугольника исключаются из дальнейшего сравнения (для увеличения скорости сравнения). Если подобный треугольник не нашелся, то увеличиваем счетчик ошибок на 1. После сравнения всех треугольников со всеми, получаем количество ошибок или т.н. расстояние двух хэшей Р.

Результат сравнения

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

Как вам такой вариант алгоритма? Жду комментариев!

Ссылки

В дополнении к материалам использованных в прошлой статье.

> Страница разработчиков MODS алгоритма