Как я могу распознать слегка измененные изображения?

Question

У меня очень большая база изображений JPEG, около 2 миллионов. Я хотел бы сделать нечеткий поиск дубликатов среди этих изображений. Дублирующиеся изображения - это два изображения, у которых много (около половины) пикселей с одинаковыми значениями, а остальные имеют значения +/- 3 в значениях R/G/B. Изображения идентичны невооруженным глазом. Это та разница, которую вы получили бы от повторного сжатия JPEG.

У меня уже есть надежный способ определить, идентичны ли два изображения: я делю дельта-яркость по всем пикселям и сравниваю с пороговым значением. Этот метод оказался на 100% точным, но делать 1 фотографию против 2 миллионов невероятно медленно (часов на фотографию).

Я хотел бы сделать отпечатки пальцев на изображениях так, чтобы я мог просто сравнить отпечатки пальцев в хэш-таблице. Даже если бы я смог достоверно сократить количество изображений, которое мне нужно сравнить, до 100, я был бы в отличной форме, чтобы сравнить от 1 до 100. Каков будет хороший алгоритм для этого?

Answer 1

Посмотрите на О. Чума, Дж. Филбина и А. Циссермана, " Обнаружение почти одинаковых изображений: взвешивание по минимальным хэшам и tf-idf", в материалах Британской конференции машинного зрения, 2008. Они решают вашу проблему и демонстрируют результаты для 146К изображений. Тем не менее, я не имею непосредственного опыта с их подходом.

Answer 2

Наивная идея: создайте небольшую миниатюру (50x50 пикселей), чтобы найти "вероятно идентичные" изображения, затем увеличьте размер миниатюры, чтобы отбросить больше изображений.

Answer 3

Основываясь на идее minHash...

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

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

Мои результаты были очень хорошими. Я могу проиндексировать миллион изображений за 24 часа на одном компьютере и могу просматривать 20 изображений в секунду. Насколько я могу судить, точность поражает.

Answer 4

Также хорошо с хэшем из миниатюр: распознаются масштабированные дубликаты (с небольшими изменениями)

Answer 5

Я не думаю, что эту проблему можно решить с помощью хеширования. Вот в чем сложность: предположим, у вас есть красный пиксель, и вы хотите, чтобы 3 и 5 хэшировали одно и то же значение. Ну, тогда вы также хотите, чтобы 5 и 7 хешировали одно и то же значение, а 7 и 9 и т. Д. Вы можете создать цепочку, которая говорит, что вы хотите, чтобы все пиксели хешировали одно и то же значение.

Вот что я хотел бы попробовать вместо этого:

1. Создайте огромное B-дерево с 32-полосным разветвлением на каждом узле, содержащее все изображения.
2. Все изображения в дереве имеют одинаковый размер, или они не являются дубликатами.
3. Дайте каждому цветному пикселю уникальное число, начинающееся с нуля. Верхний левый может быть пронумерован 0, 1, 2 для компонентов R, G, B, или вам лучше со случайной перестановкой, потому что вы собираетесь сравнивать изображения в порядке этой нумерации.
4. Внутренний узел на глубине n различает 32 пути по значению пикселя n, деленному на 8 (это позволяет получить часть шума в соседних пикселях.
5. Листовой узел содержит небольшое количество изображений, скажем, от 10 до 100. Или, может быть, число изображений является функцией увеличения глубины, так что если у вас есть 500 дубликатов одного изображения, после определенной глубины вы перестанете пытаться различить их,

Все два миллиона узлов вставляются в дерево, два изображения дублируются, только если они находятся в одном узле. Правильно? Неправильно! Если значение пикселя в двух изображениях равно 127 и 128, одно переходит в область выстрела 15, а другое - в область выреза 16. Таким образом, на самом деле, когда вы различаете пиксель, вы можете вставить это изображение в одного или двух дочерних элементов:

• Для яркости Bвставьте в B/8, (B-3)/8, а также (B+3)/8, Иногда все 3 будут равны, и всегда 2 из 3 будут равны. Но с вероятностью 3/8 вы удваиваете количество выемок, на которых появляется изображение. В зависимости от того, насколько глубоки дела, у вас может быть много дополнительных узлов.

Кто-то еще должен будет сделать математику и посмотреть, нужно ли вам делить на что-то большее, чем 8, чтобы избежать дублирования изображений. Хорошей новостью является то, что даже если истинное разветвление составляет всего около 4, а не 32, вам нужно только дерево глубины 10. Четыре дублирования в 10 позволяют получить до 32 миллионов изображений на листьях. Я надеюсь, у вас есть много оперативной памяти в вашем распоряжении! Если нет, вы можете поместить дерево в файловую систему.

Дайте мне знать, как это происходит!