Поиск кропнутых дубликатов изображений с помощью перцептуальных хешей

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





    Предисловие


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

    Расследование


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

    Интуитивно хотелось бы выделить какие-то признаки у картинки, на подобие SIFT/SURF дескрипторов, но с возможностью быстрой проверки на совпадение.

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

    Вкратце, перцептуальный хеш — это свертка каких-то признаков, которые описывают картинку.

    Основное достоинство таких хешей в том, что их просто сравнивать с другими хешами с помощью расстояния Хэмминга.

    Идеально если расстояние хешей двух картинок равно нулю. Тогда значит, что эти картинки (скорее всего) идентичны.
    Особенно подкупало, что это расстояние можно было считать с помощью не сильно сложного SQL запроса:

    SELECT * FROM image_hash WHERE BIT_COUNT( 0x2f1f76767e5e7f33 ^ hash ) <= 10

    Осталось разобраться каким образом лучше получать такие хеши.

    В последующей статье было дано описания трех способов выделения такого типа хешей.

    Кроме самого простого алгоритма проверки на среднее значение, которое было названо aHash (Average Hash) и наиболее актуального варианта реализованного в проекте с открытым исходным кодом pHash (Perceptual Hash), было дано еще одно описание — dHash (Difference Hash), предложенный David Oftedal, а именно сравнение не со среднем значением пикселей, а с предыдущем.

    После некоторых тестов выяснилось, что
    aHash неработоспособный и дает огромное количество ложных срабатываний,
    dHash работает на порядок лучше, но все равно неудовлетворительно много ошибок,
    pHash показал себя лучше всех с наиболее актуальными результатами, но больше чувствителен к модификациям картинки.

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

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

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

    Попытка решения


    После небольшого анализа ситуации, пришел к выводу, что вряд ли пользователи будут добавлять картинки с модификациями содержания.
    Например, дорисовывать цветочек, огромную мокрую метку или менять фотографию как-то по-другому.

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

    Один хеш на одну картинку целесообразно неспособен решить подобную задачу.

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

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

    Но как нам узнать где и как резать картинку?
    Вот тут и пригодилось получение локальных признаков с помощью SURF.

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


    рис 1. Найденные точки с запрашиваемого изображения


    рис 2. Найденные точки из сохраненного изображения

    Так как нам требуется порезать картинку таким образом, чтобы совпали (хотя бы немного) похожие области, была испробована k-means кластеризация ключевых точек (фич).

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

    Это и есть основная идея данного подхода.


    рис 3. Точкой показан центр одного кластера


    рис 4. Точки описывают центры трех кластеров. Если присмотреться, то верхний центроид почти совпадает с центром из рис 3.

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

    И резать можно было по крайним точкам каждого кластера.

    При пределе в 20 кластеров получается 21*20/2 = 210 центроидов. И всего хешей на одну картинку 210 + хеш полной картинки = 211 хешей.
    Но мы отбрасываем вырезки меньше чем 32 пикселя и в итоге получается, например, 191 хешей.

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

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

    Методом тыка подобрал, что бы координата вырезаемой картинки была кратна восьми.


    рис 5. Вырезанные совпадающие картинки методом кластеризации

    Прототип


    Далее необходимо было проверить работоспособность подобной модели на практике.
    Быстренько было все перенесено в могильничек с картинками и проиндексирована вся база.
    Получилось 1 235 картинок и 194 710 хешей в базе.

    И тут оказалось, что BIT_COUNT( hash1 ^ hash2 ) довольно дорогая операция и требует дополнительного внимания.
    И выполнять 200 запросов занимает больше времени нежели выполнить один большой запрос со всеми 200 хешами сразу.

    На моем слабеньком сервере такой большой запрос выполняется не меньше 2 секунд.

    Всего на поиск одной картинки требуется 200 * 194 710 = 38 942 000 операций по подсчету расстояния Хэмминга.

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

    Ради интереса попробовал реализовать поиск по коллекции хешей на C++.
    Где идея до невозможности проста: получить весь список хешей из базы и пройтись по ним, раcсчитав расстояние вручную.

    Пример расчета расстояния Хэмминга на С++
    typedef unsigned long long longlong;
    inline longlong hamming_distance( longlong hash1, longlong hash2 )
    {
        longlong x = hash1 ^ hash2;
        const longlong m1  = 0x5555555555555555ULL;
        const longlong m2  = 0x3333333333333333ULL;
        const longlong h01 = 0x0101010101010101ULL;
        const longlong m4  = 0x0f0f0f0f0f0f0f0fULL;
    
        x -= (x >> 1) & m1;
        x = (x & m2) + ((x >> 2) & m2);
        x = (x + (x >> 4)) & m4;
    
        return (x * h01)>>56;
    }
    



    И такая идея отрабатывает в два раза быстрее, чем через SQL запрос.

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

    Например, если совпал один хеш из двухсот, считать картинку дубликатом? Наверное нет.
    Также нашлись случаи когда больше 20% хешей совпало, но картинка точно не является дубликатом.
    А бывает и 10% совпадений, но является дубликатом.
    Так что количество только найденных хешей к общему числу не является гарантией проверки.

    Чтобы отфильтровать заведомо неверные совпадения было использовано вычисление SURF дескрипторов найденных картинок и подсчет количества совпадений с запрашиваемой.
    Что позволило показывать актуальные результаты, но требует дополнительного времени обработки. Скорее всего есть более оптимальные варианты.

    Эпилог


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

    Ссылки

    habrahabr.ru/post/120562 — Описание хешей, перевод
    ru.wikipedia.org/wiki/Расстояние_Хэмминга — Расстояние Хэмминга
    en.wikipedia.org/wiki/SURF — SURF ключевые точки
    ru.wikipedia.org/wiki/K-means — Кластеризация
    phash.org — pHash проект
    www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html — Сравнение видов хешей
    01101001.net/differencehash.php — Difference Hash
    github.com/valbok/img.chk/blob/master/bin/example.py — Мой вариант реализации выделения хешей из изображения
    github.com/valbok/leie/blob/master/classes/image/leieImage.php — Еще один мой вариант хешей, но на PHP
    Share post

    Similar posts

    Comments 39

      +24
      Блин, а я уж подумал что пятница сегодня. Ан нет, только понедельник.
        0
        ~ deleted joke about bad test example ~
          +7
          Было трудно, но…
            0
            То, что оппик немного вульгарный это я с Вами согласен. Насчет красивости сложно сказать, слишком субъективна будет тут чья-либо оценка. Сама фотография вроде хорошая.
              +4
              Очень не люблю девушку с цигаркой в зубах. А у этой еще и с грудью на первом фото что-то не то… Потом понял, что это просто не мой фломастер.
                +17
                Тут должна была быть Ленна, она в таких статьях привычнее.
                  +2
                  Ну вообще то это портрет Мадонны, довольно известный — goo.gl/yCof63
                  Но на вкус и цвет, как тут правильно заметили…
                +1
                ru.wikipedia.org/wiki/Лена_(изображение)
              +20
              Я бы добавил в конце опрос.
              Я сюда зашел потому что:
              — Понравилась дама
              — Я знаю что такое «перцептуальный»
              — Я хотел бы узнать что такое «перцептуальный»
              — Интересна тема топика

              Прошу не воспринимать всерьез ;)
                +4
                Только после Вашего поста обнаружил у девушки сигарету…
                Наверное ответ "-Понравилась дама".
                  +4
                  — Ой, там еще и какие-то буквы написаны вокруг фото?
                  +6
                  Титьки на Хабре! o_O
                    +16
                    Меня иногда посещает мысль, что все эти умные статьи по обработке графики машинным путем пишутся только для того, чтобы протащить сиськи на главную. И это прекрасно!
                      +1
                      Согласен, титьки — это прекрасно, если это классные сиськи ;)

                      Где-то даже идеальную формулу встречал…
                        +23
                        Нашел: image
                        Конечно функцию можно немного подправить, но в целом — неплохо.
                      +5
                      :) ага… Сисьтема раскрыта
                      +1
                      А есть оценка процента ложных срабатываний и пропуска правильных изображений? Просто без труда придумываются классы изображений, на которых это не будет работать. Любопытно проценты работы по большой базе. Хотя, конечно, там будет много ручного труда.
                        +1
                        Живая база сейчас не содержит дубликатов вообще. И подобный способ определения дубликатов нужен, чтобы не допустить их появления. Хотя в планах было прогнать все изображения и сравнить со всеми, но думаю там не будет совпадений и найдет только себя, (или будет не много, но проверю).
                        Потому что похожих картинок не так много, если есть вообще.

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

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

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

                        Возможно более актуальная база изображений показала бы, что требуется серьезная дороботка получения хешей, может более жесткие правила к формату нарезков, может увеличить разрядность кластеризации, может проверять не просто хеши, а строить последовательности и проверять совпадение очередности, ну и так далее. Пока стояла задача облегчить жизнь при модерации.
                          0
                          Прогнал по своей небольшой базе. Всего 1 250 фотографий. Плюс в том, что визуально мало похожих и нет дубликатов, поэтому найденные дубликаты — это гарантировано ложное срабатывание.
                          Началось все с ~2 % дубликатов. Пересмотрел выделения хешей, удалил дубли, вместо 191 хеша стало 50, при этом актуальные совпадения остались. Это дало ~0,75 % ложных результатов.
                          Решил покрутить критерии оценки. Было, например, расстояние Хэмминга не больше 11, что довольно много. Изменил на 8.
                          Снизил порог отношения найденных хешей к общему числу. И убрал проверку дескрипторов.

                          Это дало 0% ложных срабатываний.

                          И, конечно, не факт, что такое соотношение параметров будет давать 100% результат для любого изображения. Возможно требуется корректировка под частные случаи.
                          +2
                          Мне припомнился алгоритм шинглов, который применяют в поисковых машинах и для борьбы с плагиатом.
                          1. В качестве «слова» использовать ключевые точки картинки, которые у Вас уже есть. Если точки могут «гулять» в пределах нескольких пикселей, нужно это учесть.
                          2. Придумать хеш-функцию с параметром от такой ключевой точки.
                          3. Для каждого изображения рассчитать для каждой точки N хешей (с разными значениями параметра).
                          4. Для каждого изображения для каждого значения параметра (от 1 до N) выбрать точку, для которой соответствующий хеш минимален.
                          5. Искать совпавшие хеши среди отобранных: сортировка и проход.
                          Если из изображения вырезали часть, то велик шанс, что хотя бы одна точка совпадёт и пара дупликатов будет отобрана. Затем каждую подозрительную пару нужно прогнать через более точный алгоритм. Например, перебирать все варианты расположения одного изображения внутри другого. Если находится положение, при котором изображения хорошо накладываются — передавать для проверки человеческим глазом.
                            +1
                            А что здесь будет «параметром»? Масштаб? Или что-то другое?
                            Наверное, лучше сохранить точки с минимальными хешами для кусочков изображения — чтобы при вырезании было больше шансов, что одна из минимальных точек останется. Правда, тогда придётся хранить ещё в 10 раз больше информации, и вырастет шанс ложных срабатываний.
                              +1
                              Параметр — это просто число, заложенное в алгоритм вычисления хеша. К примеру, для строк это число можно учитывать, дополнив исходный текст строчным представлением числа: md5(text + X). Иными словами, нам нужно N разных хеш-функций.

                              Эффективность алгоритма шинглов зависит от выбора «слов». Действительно, можно рассмотреть каждый возможный квадрат 50x50 пикселей, входящий в изображение. Это подход «в лоб». Если он будет работать нормально, можно на нём и остановиться. Если нет, можно рассматривать только ключевые точки.
                              0
                              -3. Для каждого изображения рассчитать для каждой точки N хешей (с разными значениями параметра).
                              Это считай и есть дескрипторы: берется 16 блоков, по 4*4, вокруг точки и получают 8 чисел ориентиров. 16*8 = 128 чисел на точку.
                              Совпадение считают поиском ближайших точек.
                              И если будет 1000 точек, получается 128 000 чисел на картинку. Если картинок 1000, то хранить надо 128 млн чисел.
                              А проверить на совпадение 128 000 числа с первой картинки * 128 млн всего = 1,63*10^13 чтобы найти одну картинку полным перебором.

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

                              habrahabr.ru/post/143667/ — Вон Яндекс отсеивает за 2 минуты дубликаты из коллекции в миллион изображений на ноутбуке.

                              И вариантов поиска изображений по признакам очень много, начиная от гистограмм и до мд5 хешей.
                              • UFO just landed and posted this here
                              • UFO just landed and posted this here
                                +1
                                Как на счёт поворотов? Ну скажем на 11.5'?
                                  0
                                  В очень незначительных пределах. И такие хеши не годятся для проверки на такие геометрические преобразования. Возможно есть вариант проверки на последовательность хешей и каждый нарезок будет немного повернут, но в итоге совпадут с не повернутым вариантом.
                                    +2
                                    А если как-нибудь нормализовать геометрию по локальным признакам (наверное даже после кластеризации), например, вписывать фигуру, задаваемую центроидами кластеров (или их крайними точками), в какую-нибудь заранее заданную фигуру (квадрат или треугольник), и хэшировать уже такие нормализованные изображения? Тогда по идее хэш будет инвариантен к масштабированию и поворотам. Правда, все-равно непонятно, как быть с кропами, когда отрезается часть точек кластера, и центр «съезжает».
                                      0
                                      -хэшировать уже такие нормализованные изображения
                                      Примерно так сейчас я и делаю. В кластере нахожу минимальные и максимальные координаты, а потом смотрю и изменяю координаты так, чтобы были кратны расстоянию к центру кластера.
                                      Это позволяет получать пропорциональные картинки и их легче сравнивать.
                                      Думал что можно обойтись фиксированным размером вырезаемых картинок, но такое не годится. Думал может резать вокруг центра кластера как-то, тоже особо мало результатов. Даже проверял возможность сохранить отношения расстояний от центров кластеров. Т.е. пропорции расстояния, как примерно делатется в SIFT. Но так получается очень много чисел и их сложно сравнивать, чтобы получить адекватные результаты.
                                      Ну и думал, что можно очистить вырезанные изображения и нарисовать там карту точек кластера, и уже делать хеш такой картинки. И еще много чего, но это все не работало.

                                      На счет повороты, то тут они критичны, и если повернуть Лену на 180, то 39% только совпадет, pHash дает 39 расстояние.
                                      Если на 90 градусов, то на 50% совпадет.

                                      А вот масштабы тут не важны.

                                        +1
                                        Спасибо за ответ. Про кратность расстояния в кластере из статьи я не понял, теперь вроде сообразил.

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

                                        Если фигура, в которую вписываются точки локальных признаков, — квадрат, то да, нужно будет делать 4 сравнения (а то и 8 для поддержки зеркального отражения картинки). Скорее всего количество сравнений можно уменьшить, договорившись, что центр масс всех вписанных точек должен оказаться, скажем, в первом квадранте квадрата.

                                        Немного сумбурно описал, но надеюсь, сумел передать идею.
                                  +1
                                  Решал около года назад подобную задачку, но попроще. Была файлопомойка(~10 000 000 файлов) с оригиналами и кропами(делали реальные люди), нужно было избавиться от кропаных файлов(ввиду прогресса стали слишком малы), но записать координаты кропа в sql базу.

                                  Написал скриптик под opencv на c++ и использовал его из php. Просто выводит в консоль x, y, width и height

                                  #include
                                  #include

                                  #include «opencv2/core/core.hpp»
                                  #include «opencv2/features2d/features2d.hpp»
                                  #include «opencv2/highgui/highgui.hpp»
                                  #include «opencv2/calib3d/calib3d.hpp»

                                  #include «opencv2/nonfree/features2d.hpp»

                                  using namespace cv;

                                  void readme();

                                  /** function main */
                                  int main( int argc, char** argv )
                                  {
                                  if( argc != 3 )
                                  { readme(); return -1; }

                                  Mat img_object = imread( argv[1], CV_LOAD_IMAGE_GRAYSCALE );
                                  Mat img_scene = imread( argv[2], CV_LOAD_IMAGE_GRAYSCALE );

                                  if( !img_object.data || !img_scene.data )
                                  { std::cout max_dist ) max_dist = dist;
                                  }

                                  //-- Draw only «good» matches (i.e. whose distance is less than 3*min_dist )
                                  std::vector good_matches;

                                  for( int i = 0; i < descriptors_object.rows; i++ )
                                  { if( matches[i].distance < 3*min_dist )
                                  { good_matches.push_back( matches[i]); }
                                  }

                                  if (good_matches.size() == 0)
                                  {
                                  std::cout
                                    0
                                    Это была моя первая попытка. Просто использовать SURF и BFMatcher:
                                        cv = cv2.SURF( 400 )
                                        kp1,desc1 = cv.detectAndCompute( img1, None )
                                        kp2,desc2 = cv.detectAndCompute( img2, None )
                                    
                                        matcher = cv2.BFMatcher( cv2.NORM_L2 )
                                        matches = matcher.knnMatch( desc1, trainDescriptors = desc2, k = 2 )
                                        pairs = filterMatches( kp1, kp2, matches )
                                    


                                    Сложность была в том, что каждый раз, при загрузке новой картинки, приходилось бы проходить так по базе (сохраненных точек и дескрипторов) и делать проверку на совпадение. Слишком было бы толсто. Думал, что есть возможность сделать легче.
                                  • UFO just landed and posted this here
                                      +2
                                      Каюсь, не уделил должного внимания, просто эта картинка была удобна для тестов и была проблемной при поиске по базе.
                                        0
                                        Отличная аватарка, к слову.
                                        • UFO just landed and posted this here
                                        +1
                                        Характерно, что автор искал лицо.

                                        Напомнило анекдот про поручика, где тот критикует голую девушку, ссылаясь, что что-то во взгляде не понравилось ;)
                                          0
                                          Я сперва тестировал на Харламове:
                                          image
                                          А Мадонна попалась потом, случайно. Потому что много резанных копий существует этой картинки и как раз на ней были проблемы.
                                          +2
                                          Хорошая статья и титьки, всегда лучше чем просто хорошая статья!

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