Изображение отпечатка пальца для сравнения сходства многих изображений

Question

Мне нужно создать отпечатки многих изображений (около 100 000 существующих, 1000 новых в день, RGB, JPEG, максимальный размер 800x800), чтобы очень быстро сравнивать каждое изображение с любым другим. Я не могу использовать двоичные методы сравнения, потому что также должны распознаваться изображения, которые почти похожи.

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

Answer 1

Обычные алгоритмы хеширования или вычисления CRC плохо работают с данными изображения. Размерный характер информации должен быть принят во внимание.

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

возможны несколько простых решений:

1. Создание гистограммы яркости для изображения в виде отпечатка пальца
2. Создание уменьшенных версий каждого изображения в виде отпечатка пальца
3. Объединение методов (1) и (2) в гибридный подход для улучшения качества сравнения

Гистограмма яркости (особенно та, которая разделена на компоненты RGB) является разумным отпечатком для изображения - и может быть реализована довольно эффективно. Вычитание одной гистограммы из другой создаст новую историограмму, которую вы можете обработать, чтобы решить, насколько похожи два изображения. Гистограммы, потому что единственная оценка распределения и появления информации яркости / цвета достаточно хорошо справляются с аффинными преобразованиями. Если вы квантоваете информацию о яркости каждого компонента цвета до 8-битного значения, 768 байт памяти будет достаточно для отпечатка пальца изображения практически любого разумного размера. Гистограммы яркости дают ложные негативы, когда манипулируют информацией о цвете в изображении. Если вы применяете такие преобразования, как контрастность / яркость, постеризация, смещение цвета, изменение информации о яркости. Ложные срабатывания также возможны с определенными типами изображений ... например, пейзажами и изображениями, где один цвет доминирует над другими.

Использование масштабированных изображений - это еще один способ снизить информационную плотность изображения до уровня, который легче сравнивать. Уменьшение размера менее 10% от исходного размера изображения обычно приводит к потере слишком большого количества информации, которая может быть использована, поэтому изображение с разрешением 800x800 пикселей можно уменьшить до 80x80 и при этом предоставить достаточно информации для проведения достойной дактилоскопии. В отличие от данных гистограммы, вы должны выполнять анизотропное масштабирование данных изображения, когда исходные разрешения имеют различные пропорции. Другими словами, уменьшение изображения размером 300x800 в миниатюру размером 80x80 вызывает деформацию изображения, так что при сравнении с изображением 300x500 (это очень похоже) получаются ложные негативы. Отпечатки пальцев на миниатюрах также часто дают ложные негативы, когда происходят аффинные преобразования. Если вы перевернете или поверните изображение, его эскиз будет сильно отличаться от оригинала и может привести к ложному срабатыванию.

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

Answer 2

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

Возьмите вейвлет Хаара изображения. По сути, вейвлет Хаара представляет собой последовательность различий между изображениями с низким разрешением и каждым изображением с более высоким разрешением, но взвешивается тем, насколько глубоко вы находитесь в «дереве» мип-карт. Расчет прост. Затем, как только вы вейвлет Хаара соответствующим образом взвешены, отбросьте все, кроме k самых больших коэффициентов (в терминах абсолютного значения), нормализуйте вектор и сохраните его.

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

Answer 3

Вы обязательно должны взглянуть на phash .

Для сравнения изображений есть проект php : https://github.com/kennethrapp/phasher

И мой маленький javascript клон: https://redaktorcms.com/dev/phasher/demo_js/index.html

К сожалению, это «битовый счет», но распознает повернутые изображения. Другой подход в javascript состоял в том, чтобы построить гистограмму яркости из изображения с помощью холста. Вы можете визуализировать гистограмму многоугольника на холсте и сравнить этот многоугольник в своей базе данных (например, mySQL пространственный ...)

Это демо для видео гистограмм: https://redaktorcms.com/dev/globetrottr/testHashVideo.php

Answer 4

Давным-давно я работал над системой, которая имела некоторые сходные характеристики, и это приблизительный алгоритм, которому мы следовали:

1. Разделите изображение на зоны. В нашем случае мы имели дело с видео с разрешением 4: 3, поэтому мы использовали 12 зон. Это позволяет получить разрешение исходных изображений вне изображения.
2. Для каждой зоны вычислите общий цвет - среднее значение всех пикселей в зоне
3. Для всего изображения рассчитайте общий цвет - среднее для всех зон

Таким образом, для каждого изображения вы храните n + 1 целочисленные значения, где n - количество отслеживаемых зон.

Для сравнения вам также нужно взглянуть на каждый цветовой канал в отдельности.

1. Для общего изображения сравните цветовые каналы для всех цветов, чтобы увидеть, находятся ли они в пределах определенного порога - скажем, 10%
2. Если изображения находятся в пределах порога, затем сравните каждую зону. Если все зоны также находятся в пределах порога, изображения достаточно сильно совпадают, чтобы вы могли по крайней мере пометить их для дальнейшего сравнения.

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

Answer 5

Аналогично ответу Ic - вы можете попробовать сравнить изображения в разных разрешениях. Таким образом, каждое изображение сохраняется как 1x1, 2x2, 4x4 .. 800x800. Если самое низкое разрешение не соответствует (с учетом порогового значения), вы можете немедленно отклонить его. Если он совпадает, вы можете сравнить их в следующем более высоком разрешении и т. Д.

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

Answer 6

Для сравнения изображений iPhone и развития сходства изображений проверьте: http://sites.google.com/site/imagecomparison/

Чтобы увидеть его в действии, воспользуйтесь визуальным поиском eyeBuy в iTunes AppStore.

Answer 7

Итак, вы хотите выполнить «сопоставление отпечатков пальцев», которое значительно отличается от «сопоставления изображений». Анализ отпечатков пальцев был глубоко изучен в течение последних 20 лет, и было разработано несколько интересных алгоритмов для обеспечения правильной частоты обнаружения (в отношении FAR и FRR мер - Уровень ложного принятия и Уровень ложного отклонения ).

Я предлагаю вам лучше взглянуть на LFA (Local Feature Analysis) класс методов обнаружения, в основном построенных на мелкой проверке. Мелочи являются специфическими характеристиками любого отпечатка пальца и были классифицированы по нескольким классам. Отображение растрового изображения на карте мелочей - это то, что на самом деле делает большинство государственных органов, чтобы зарегистрировать преступников или террористов.

См. здесь для дальнейших ссылок

Answer 8

По состоянию на 2015 год (назад в будущее ... по этому вопросу 2009 года, который в настоящее время занимает первое место в Google) сходство изображений можно вычислить с использованием методов глубокого обучения. Семейство алгоритмов, известных как Auto Encoders, может создавать векторные представления с возможностью поиска по сходству. Здесь есть демо .

Answer 9

Вы буквально хотите сравнить каждое изображение с другими? Какое приложение? Может быть, вам просто нужна какая-то индексация и поиск изображений на основе определенных дескрипторов? Затем, например, вы можете взглянуть на стандарт MPEG-7 для интерфейса описания мультимедийного контента. Затем вы можете сравнить различные дескрипторы изображений, которые будут не такими точными, но намного быстрее.

Answer 10

Один из способов сделать это - изменить размер изображения и значительно уменьшить разрешение (до 200x200, может быть?), Сохранив уменьшенную (усредненную по пикселям) версию для сравнения. Затем определите порог допуска и сравните каждый пиксель. Если RGB всех пикселей находится в пределах допуска, вы получите совпадение.

Ваш начальный прогон O (n ^ 2), но если вы каталогизируете все совпадения, каждое новое изображение представляет собой просто алгоритм O (n) для сравнения (вам нужно только сравнить его с каждым ранее вставленным изображением). Однако в конечном итоге он сломается, так как список изображений для сравнения станет больше, но я думаю, что вы на некоторое время в безопасности.

После 400 дней работы у вас будет 500 000 изображений, что означает (без учета времени на изменение размера изображения вниз) 200(H)*200(W)*500,000(images)*3(RGB) = 60 000 000 000 сравнений. Если каждое изображение точно соответствует, вы будете отставать, но, вероятно, это не так, верно? Помните, что вы можете сделать скидку на изображение как на совпадение, как только одно сравнение выйдет за пределы вашего порога.