В своей первой статье на Хабре, я рассказал о своем алгоритме для поиска похожих изображений. Сегодня я хочу рассказать о второй (улучшенной) версии своего алгоритма.
Статья будет несколько короче предыдущей т.к. расскажу только об отличиях двух алгоритмов. Поэтому желательно прочесть предыдущею статью, что бы «быть в теме».
Первое, на чем хочу отдельно акцентировать внимание это то, что в моем алгоритме можно использовать любой детектор ключевых точек, который лучше подходит под ваши задачи и конкретные изображения. Подбирать наилучший детектор можно эмпирически, а можно использовать алгоритм для автоматического выбора, как это делают создатели алгоритма MODS (спасибо devpony за наводку).
Для своего алгоритма и своей ситуации я буду использовать угловой детектор Харриса. Детектор Харриса инвариантен к поворотам, частично инвариантен к аффинным изменениям интенсивности, прост, достаточно точен и имеет такой показатель меры отклика, по которому можно оценить значимость ключевых точек.
Нам понадобится всего 10 самых значимых точек!
А отличии от прошлого варианта мы будем строить не отрезки, а треугольники, вершинами которых будут найденные нами ключевые точки.
Дескриптором будет являться ряд из длин трех сторон треугольника, записанные от большей к меньшей. А, В, С, где А>В>С.
Из 10 точек можно построить 10*9*8/6=120 треугольников. Значит наш хэш будет состоять из 120 рядов по 3 числа А1, В1, С1; А2, В2, С2;...; А120, В120, С120.
Сравнение двух изображений сводится к поиску подобных треугольников, построенных через их ключевые точки.
В соответствии с третьим признаком подобия треугольников:
Т.к. наши хэши состоят из длин сторон треугольников записанных в порядке уменьшения, то поиск подобных треугольников сводится к делению чисел и сравнению результатов.
Сравнить нужно все треугольники одного хэша, со всеми треугольниками второго. Если подобный треугольник нашелся, то эти 2 треугольника исключаются из дальнейшего сравнения (для увеличения скорости срав��ения). Если подобный треугольник не нашелся, то увеличиваем счетчик ошибок на 1. После сравнения всех треугольников со всеми, получаем количество ошибок или т.н. расстояние двух хэшей Р.
Как и в прошлом варианте алгоритма для интерпретации результатов, нужно сравнить полученное расстояние Р с неким оценочным значением.
Как вам такой вариант алгоритма? Жду комментариев!
В дополнении к материалам использованных в прошлой статье.
→ Страница разработчиков MODS алгоритма
Статья будет несколько короче предыдущей т.к. расскажу только об отличиях двух алгоритмов. Поэтому желательно прочесть предыдущею статью, что бы «быть в теме».
Детектор ключевых точек
Первое, на чем хочу отдельно акцентировать внимание это то, что в моем алгоритме можно использовать любой детектор ключевых точек, который лучше подходит под ваши задачи и конкретные изображения. Подбирать наилучший детектор можно эмпирически, а можно использовать алгоритм для автоматического выбора, как это делают создатели алгоритма MODS (спасибо devpony за наводку).
Для своего алгоритма и своей ситуации я буду использовать угловой детектор Харриса. Детектор Харриса инвариантен к поворотам, частично инвариантен к аффинным изменениям интенсивности, прост, достаточно точен и имеет такой показатель меры отклика, по которому можно оценить значимость ключевых точек.
Нам понадобится всего 10 самых значимых точек!
Дескриптор
А отличии от прошлого варианта мы будем строить не отрезки, а треугольники, вершинами которых будут найденные нами ключевые точки.
Дескриптором будет являться ряд из длин трех сторон треугольника, записанные от большей к меньшей. А, В, С, где А>В>С.
Хэш
Из 10 точек можно построить 10*9*8/6=120 треугольников. Значит наш хэш будет состоять из 120 рядов по 3 числа А1, В1, С1; А2, В2, С2;...; А120, В120, С120.
Сравнение хэшей
Сравнение двух изображений сводится к поиску подобных треугольников, построенных через их ключевые точки.
В соответствии с третьим признаком подобия треугольников:
Если три стороны одного треугольника соответственно пропорциональны трем сторонам другого, то такие треугольники подобны.
Т.к. наши хэши состоят из длин сторон треугольников записанных в порядке уменьшения, то поиск подобных треугольников сводится к делению чисел и сравнению результатов.
Сравнить нужно все треугольники одного хэша, со всеми треугольниками второго. Если подобный треугольник нашелся, то эти 2 треугольника исключаются из дальнейшего сравнения (для увеличения скорости срав��ения). Если подобный треугольник не нашелся, то увеличиваем счетчик ошибок на 1. После сравнения всех треугольников со всеми, получаем количество ошибок или т.н. расстояние двух хэшей Р.
Результат сравнения
Как и в прошлом варианте алгоритма для интерпретации результатов, нужно сравнить полученное расстояние Р с неким оценочным значением.
Как вам такой вариант алгоритма? Жду комментариев!
Ссылки
В дополнении к материалам использованных в прошлой статье.
→ Страница разработчиков MODS алгоритма
