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

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

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

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

Ответ 1

Взгляните на О. Чума, Дж. Филбина и А. Зиссермана, Рядом с обнаружением двойного изображения: min-hash и tf-idf weighting, в материалах конференции British Machine Vision, 2008. Они решают вашу проблему и демонстрируют результаты для 146k изображений. Однако у меня нет непосредственного опыта их подхода.

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

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

Сообщите мне, как это происходит!

Ответ 5

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