Какой алгоритм можно использовать для определения того, являются ли изображения "одинаковыми" или похожими, независимо от размера?

TinEye, "поисковая система обратного изображения", позволяет загружать/ссылаться на изображение и выполнять поиск миллиард изображений, которые он просканировал, и он вернет ссылки на найденные ими изображения, которые являются одним и тем же изображением.

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

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

Какой тип алгоритма мог бы использовать TinEye, чтобы он мог сравнивать изображение с другими различными размерами и коэффициентами сжатия и тем не менее все еще точно определить, что они являются "одним и тем же" изображением или множеством?

Ответ 1

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

Просто, чтобы дать вам пример, это (не особенно хорошая) функция отпечатка пальца: измените размер изображения на квадрат 32x32, нормализовать и квантовать цвета, уменьшив количество цветов до примерно 256. Затем у вас есть 1024 -байт-отпечаток для изображения. Просто держите таблицу fingerprint = > [список URL-адресов изображений]. Когда вам нужно искать изображения, похожие на заданное изображение, просто вычислите его значение отпечатка пальца и найдите соответствующий список изображений. Легко.

Что нелегко - быть полезным на практике, функция отпечатка пальца должна быть устойчивой к культурам, аффинным преобразованиям, изменениям контраста и т.д. Построение хороших функций отпечатков пальцев является отдельной темой исследования. Довольно часто их настраивают вручную и используют множество эвристик (т.е. Используют знания о типичном содержании фото, о формате изображения/дополнительных данных в EXIF и т.д.)

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

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

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

ПЕРМУТАЦИОННАЯ ГРУППА: ИНТЕЛЛЕКТУАЛЬНАЯ ПРОГРАММА ФУНКЦИОНАЛЬНОЙ УСТАНОВКИ ДЛЯ АУДИО И ИЗОБРАЖЕНИЙ ИЗОБРАЖЕНИЯ. Информация о локально-чувствительных хешах.

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

Ответ 2

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

Взгляните на

или, если вы ДЕЙСТВИТЕЛЬНО заинтересованы, вы можете выложить около 70 баксов (или, по крайней мере, посмотреть предварительный просмотр Google) для

Отвлечение функций и обработка изображений

Ответ 3

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

http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html

aHash (также называемый Average Hash или Mean Hash). Этот подход подавляет изображение в черно-белое изображение 8x8 и устанавливает 64 бит в хэш на основе того, больше ли значение пикселя, чем средний цвет для изображения.

pHash (также называемый "Perceptive Hash" ). Этот алгоритм похож на aHash, но использует дискретное косинусное преобразование (DCT) и сравнивается на основе на частотах, а не на цветовых значениях.

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

Ответ 4

The Hough Transform - очень старый алгоритм извлечения объектов, который вы считаете интересным. Я сомневаюсь в том, что использует tinyeye, но это хорошее, простое начальное место для изучения возможности выделения.

Есть также слайды к аккуратным разговорам от некоторых людей из Университета Торонто об их работе на astrometry.net. Они разработали алгоритм для сопоставления телескопических изображений ночного неба с локациями в звездных каталогах, чтобы идентифицировать особенности изображения. Это более конкретная проблема, чем то, что tinyeye пытается решить, но я бы ожидал, что многие основные идеи, о которых они говорят, применимы к более общей проблеме.

Ответ 5

http://tineye.com/faq#how

Исходя из этого, ответ Игоря Кривокона, похоже, находится на отметке.

Ответ 6

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

Ответ 7

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

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

Ответ 8

Как изменить размер изображений на стандартный малый размер и проверить значения PSNR для SSIM или только яркость? что я буду делать.