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

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 миллионов изображений на листьях. Я надеюсь, у вас есть много оперативной памяти в вашем распоряжении! Если нет, вы можете поместить дерево в файловую систему.

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