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

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

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

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


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

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

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

    Дескриптор


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

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

    Хэш


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

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


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

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

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

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

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

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


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

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

    Ссылки


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

    Страница разработчиков MODS алгоритма
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 10

      +2
      Так кэш или хэш?
        –1
        Конечно Хэш!
        Оговорка по Фрейду ))
        0
        А вы друзья как не садитесь…

        Вы хотите получить набор из 120*3 double(?) которые не только все всегда выбирать из базы надо, но еще и пересчитывать между собой? 120*3*8 = 2880 байт. если искать хотя бы среди 1 млн картинок, размер данных которые нужно будет обработать для поиска всего одной картинки будет не меньше 2.7 Gb…
        и даже если вруг вы нормализуете все значения в базе, что бы хоть как то уменьшить расчеты, то выборка все равно будет всегда вестись по всей базе, подобных треугольников будет очень много, выхлоп будет низкий, а затраты и время на обработку огромны.
          0
          Для оптимизации сравнения хэшей будет создан отдельный алгоритм на основе HEngine, который подробно описан в статье https://habrahabr.ru/post/211264/ пользователя valbok.
            0
            Удачи вам ребята, потом вы обнаружите те же VP деревья, но для данной задачи это все не подходит. Сейчас я для этой задачи уже 5ый алгоритм тестирую, нужной скорости достигнуть так и не удалось.
          +4
          Начну с похвал. Вы молодец что:
          — не пустились в эвристический маразм с нейронными сетями,

          кстати может стоит объединиться с автором интеллектуальной системы Э.Л.И.С.?
            –1
            Собственно вот мой вариант такого алгоритма
            Работает все реалтайм. Позволяет детектить кучу объектов одновременно. Так что идея с подобием треугольников вполне рабочая.
              0
              Итог вижу, а алгоритм нет.
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Ни один детектор блобов / углов на практике не гарантирует, что N характерных объектов с максимальными весами одного снимка предмета и N аналогично взятых объектов второго снимка того же предмета (с измененными параметрами съемки / предмета) будут являться одноименными. Поэтому обычно стремятся обеспечить избыточность координатных пар возможно одноименных объектов и далее найти истинно одноименные статистическими методами и (или) геометрическими методами с привлечением модели съемки

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое