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



    В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок. Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра 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 хешей в базе. Поиск и кластеризация всех дубликатов занимает полторы минуты. Включает в себя полный перебор и поиск совпадающих хешей.

    Ссылки

    [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 Мой прототип поиска по фрагментам
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 21

      +14
      Ох, ничоссе, картинки для привлечения внимания!
        +6
        Первая картинка самая классная!
          +10
          Женат? ;)
            +5
            Это в заброшенном ангаре во Флотском под Севастополем.
              +2
              Это Алексей Кислов, художник из Севастополя. У него много еще интересного
                0
                Это вам просто все остальные картинки примелькались ;)
                +3
                Картинки для отвлечения внимания!)
                –12
                Отличная статья, отношение к которой портят идиотские образцы. Это явное неуважение к той аудитории, которой вы пытаетесь донести информацию. Вы полагаете здесь тусуются прыщавые подростки, которых нечем больше завлечь? Уже достало, что на каждом шагу пытаются эксплуатировать сексуальность, что бы что-то впарить.
                  +12
                  Это стандартная картинка для тестов: en.wikipedia.org/wiki/Lenna
                    –8
                    Я никогда на видел, чтобы Lenna применялась в тематических/научных статьях в полном размере. А Вы?
                    Поддерживаю предыдущего оратора. Тестовые картинки на самом деле пошлые. Примеры можно было выбрать из большого количества других общеизвестных изображений.
                      +13
                      А разве хабр — детский сад? С каких пор женское тело стало пошлым? Давайте уничтожим статуи древних греков, они пошлые.
                        –9
                        Причем здесь пошлое — непошлое? Вас не смущает, что ваши естественные инстинкты используется рекламистами, пиарщиками, журналистами и прочими личностями от которых вам что-то нужно для своих корыстных целей без вашего на то разрешения? Им профит, а расплачивается общество разложением морали и развалом института семьи. Кому непонятно о чем я говорю — минусуйте дальше. Хорошо смеется тот, кто смеется последним.
                          +3
                          >разложением морали и развалом института семьи

                          А у меня вот отвращение вызывают регулярные упоминания морали и и ее разложения, к месту и не к месту.
                          Какие-то домашние социологи\психологи\эксперты всегда больше всех знают и о морали, и об обществе, и о том, что для кого хорошо, а что плохо.

                          Мораль так вообще веками уже «разлагается» по чьему-то мнению, и ничего, живем как-то. Даже вперед движемся, в том числе и в области морали.
                            0
                            > Кому непонятно о чем я говорю — минусуйте дальше.

                            Мне непонятно. Но можно я не буду вас минусовать?
                          0
                          Пф. Да вы не в теме. Это как раз картинка для таких статей, на ней всякие тесты в фотками делают. Ну, например, скачайте вот этот софт, посмотрите что внутри: www.geoffdavis.net/dartmouth/wavelet/wavelet.html
                            +1
                            ...the engineers wanted a 512 x 512 image, so they limited the scan to the top 5.12 inches of the picture, effectively cropping it at the subject's shoulders.
                            Может потому, что все остальное не вмещалось в 512 на 512 пикселей?

                            Some people proposed banning the use of this image because of its source.
                            О времена, о нравы. Какая была шумиха только от одной мысли, что скан был сделан с фотографии где не прикрыто.

                            В любом случае, прошло уже 42 года, а мы все еще помним. Бабушке Ленне наверное приятно.
                          • UFO just landed and posted this here
                            +3
                            Завлекал я работой художника Алексея Кислова.
                            0
                            А не кинете ли куском кода для визуализации найденных точек?
                              0
                              $ cd bin; ./bdm.py ../tests/images/lenna_cropped.jpg ../tests/images/lenna.jpg
                              


                              Это нарисует такие какртинки как в статье.
                              В файле bdm.py есть параметр m, количество требуемых точек.
                              0
                              Информация уже обновляется с такой скоростью, что скоро фотографии, созданные искусственно (их уже стало больше оригиналов), через лет 50 станут для потомков оригиналами. Хотите примеры?

                              Only users with full accounts can post comments. Log in, please.