Сравнение изображений-быстрый алгоритм

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

http://phash.org/

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

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

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

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

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

• file-hash based (md5,sha1 и т. д.) для точных дубликатов
• перцептивное хэширование (phash) для масштабированных изображений
• функция на основе (просеять) для измененных изображений

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

действительно хорошая вещь о phash заключается в том, что как только вы создадите свою хэш-базу данных (которая для меня составляет около 1000 изображений/сек), поиск может быть очень, очень быстрым, в частности, когда вы можете хранить всю хэш-базу данных в памяти. Это довольно практично, так как хэш составляет всего 8 байт.

например, если у вас есть 1 миллион изображений, для этого потребуется массив из 1 миллиона 64-битных хэш-значений (8 МБ). На некоторых процессорах это вписывается в кэш L2/L3! В практическом использовании я видел, что corei7 сравнивается с более чем 1 Гига-Хамм/сек, это только вопрос пропускной способности памяти для процессора. База данных с 1 миллиардом изображений практична на 64-битном процессоре (требуется 8 ГБ оперативной памяти), и поиск не будет превышать 1 секунды!

для модифицированных / обрезанных изображений, казалось бы, инвариантная к преобразованию функция / детектор ключевых точек, такой как SIFT путь. Просеивание даст хорошие ключевые точки, которые будут обнаруживать обрезку / поворот / Зеркало и т. д. Однако сравнение дескрипторов очень медленно по сравнению с расстоянием Хэмминга, используемым phash. Это серьезное ограничение. Существует много сравнений, так как существует максимальный дескриптор IxJxK, сравниваемый с поиском одного изображения (I=num Haystack images, J=целевые ключевые точки на изображение стога сена, K=целевые ключевые точки на изображение иглы).

чтобы обойти проблему скорости, я попытался использовать phash вокруг каждого найденного ключевая точка, используя размер/радиус объекта для определения суб-прямоугольника. Трюк, чтобы сделать эту работу хорошо, состоит в том, чтобы увеличить/уменьшить радиус для создания различных уровней субрект (на изображении иглы). Как правило, первый уровень (без масштаба) будет соответствовать, однако часто это занимает еще несколько. Я не уверен на 100%, почему это работает, но я могу себе представить, что это позволяет использовать функции, которые слишком малы для работы phash (phash масштабирует изображения до 32x32).

еще одна проблема заключается в том, что SIFT не будет распространять ключевые точки оптимально. Если есть участок изображения с большим количеством краев, ключевые точки будут группироваться там, и вы не получите их в другой области. Я использую GridAdaptedFeatureDetector в OpenCV для улучшения распределения. Не уверен, что размер сетки лучше, я использую небольшую сетку (1x3 или 3x1 в зависимости от ориентации изображения).

вы, вероятно, хотите масштабировать все изображения стога сена (и иглы) до меньшего размера до обнаружения объекта (я использую 210px вдоль максимального размера). Это уменьшит шум в изображении (всегда проблема для алгоритмов компьютерного зрения), также сфокусирует детектор на более видных особенностях.

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

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

изображение иглы может иметь меньше ключевых точек, чем изображения стога сена, и по-прежнему получать хорошие результаты. Добавление большего количества не обязательно дает вам огромную прибыль, например, с J=400 и K=40 моя скорость попадания составляет около 92%. При J=400 и K=400 скорость попадания доходит только до 96%.

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

У меня есть идея, которая может работать, и это скорее всего будет очень быстрой. Вы можете суб-образец изображения, чтобы сказать 80x60 разрешение или сопоставимые, и преобразовать его в серую шкалу (после подвыборки это будет быстрее). Обработайте оба изображения, которые вы хотите сравнить. Затем запустите нормализованную сумму квадратов разностей между двумя изображениями (изображение запроса и каждое из БД), или даже лучше нормализованная взаимная корреляция, которая дает ответ ближе к 1, Если оба изображения похожи. Тогда, если изображения похожи на вас можно переходить к более сложным техникам чтобы убедиться, что это те же изображения. Очевидно, этот алгоритм является линейным с точки зрения количества изображений в базе данных так что даже если это будет очень быстро до 10000 кадров в секунду на современном оборудовании. Если вам нужна инвариантность к вращению, то можно вычислить доминирующий градиент для этого небольшое изображение, а затем и всю систему координат можно повернуть на каноническую ориентация, однако, будет медленнее. И нет, нет никакой инвариантности чтобы масштабировать здесь.

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

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

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

Я считаю, что уменьшение размера изображения до размера почти значка, скажем 48x48, затем преобразование в оттенки серого, а затем взятие разницы между пикселями или Дельта, должно хорошо работать. Поскольку мы сравниваем изменение цвета пикселя, а не фактический цвет пикселя, не имеет значения, будет ли изображение немного светлее или темнее. Большие изменения будут иметь значение, так как пиксели становятся слишком светлыми / темными будут потеряны. Вы можете применить это через одну строку, или столько, сколько вам нравится, чтобы увеличить точность. В лучшем случае у вас будет 47x47=2,209 вычитания, чтобы сформировать сопоставимый ключ.

выбор 100 случайных точек может означать, что похожие (или иногда даже непохожие) изображения будут помечены как одинаковые, что я предполагаю, это не то, что вы хотите. Хэши MD5 не работали бы, если бы изображения были разных форматов (png, jpeg и т. д.), имели разные размеры или имели разные метаданные. Уменьшение всех изображений до меньшего размера-это хорошая ставка, выполнение сравнения пикселей на пиксель не должно занимать слишком много времени, пока вы используете хорошую библиотеку изображений / быстрый язык, а размер невелик достаточно.

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

Если у вас есть большое количество изображений, смотрите в Bloom filter, который использует несколько хэшей для вероятностного, но эффективного результата. Если количество изображений не огромно, то криптографического хэша, такого как md5, должно быть достаточно.