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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

Взгляните на

• Извлечение функции

• SIFT , другой сайт

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

• Функция извлечения и обработки изображений

Answer 3

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

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

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

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

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

Answer 4

http://tineye.com/faq#how

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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