Нужен хороший алгоритм для классификации 8ГБ картинок
У меня есть около 150 000 фотографий, и некоторые из них являются дубликатами.
Я понял, что алгоритм SSIM — хороший выбор для сравнения двух картинок и определения, являются ли они дубликатами.
Однако, если я хочу найти дубликаты таким образом, мне придется сравнить 150.000 * 149.999 снимков, которые будут сделаны навсегда.
Поэтому сейчас я ищу быстрый и эффективный алгоритм для создания среднего значения для каждого изображения, а затем сравнивать только те изображения, которые приближаются к их среднему значению.
Короче говоря: я ищу эффективный способ категоризации фотографий!
Я планирую использовать библиотеку C ++ CImg для этой задачи, потому что это быстро.
Спасибо!
Решение
Я бы попробовал подход типа хэша / отпечатка пальца:
-
Создание отпечатка пальца для каждого изображения, содержащего также соответствующие атрибуты изображения, такие как размер и количество компонентов для метафайла или базы данных. Отпечаток пальца может быть вычислен из общего подизображения, это может быть сжатая спектрограмма с потерями, простой вектор, содержащий частотные бины БПФ, гистограмма или другой метод (у меня нет реальной подсказки, что подходит лучше, это наиболее вероятно очень зависит от содержания).
-
Как уже упоминалось, группировка заранее с атрибутами изображения, такими как размер и количество цветовых компонентов, значительно сократит количество (двоичных) сравнений, которое будет
(n*(n-1))/2для каждой группы. -
Сравнение отпечатков пальцев с соответствующим допуском для дальнейшей подгруппы (обратите внимание, чтобы охватить случаи, когда одно изображение имеет совпадения в нескольких группах).
-
OpenCV может сделать финальный матч:
Смежные вопросы, касающиеся сравнения изображений с использованием OpenCV:
Другие решения
Есть изображения, которые различаются по высоте, но в основном это те же изображения, которые имеют несвязанный прямоугольник внизу, который изменяет высоту.
Если верхняя часть изображения всегда одинакова для двух дубликатов, вы можете попытаться вычислить значение хеш-функции на основе N строк пикселей в изображении, которые должны быть достаточно безопасными (т. Е. Ваш блок в нижней части не будет в эти строки).
После того, как вы хэшировали все свои файлы, вы можете отсортировать значения хеш-функции и более точно сравнить только изображения с одинаковым значением хеш-функции.
Использование любой формы хеширования здесь действительно бессмысленно, так как даже почти идентичные изображения будут давать очень разные значения хеш-функции. Как указывалось в комментариях, два «дублирующих» изображения могут быть малейшими (например, эффекты, вызванные сжатием JPEG), поэтому интерес представляет обнаружение почти дублированных изображений. Кроме того, как отмечалось в комментариях, рассмотрение только изображений одинаковой ширины — это первый шаг к уменьшению квадратичного числа сравнений. Если все изображения имеют одинаковую ширину, улучшения не происходит.
Первая проблема, которую вам нужно решить, это сбросить нижний блок почти одинаковых изображений разной высоты. Почему эта коробка там? Это однородный цвет фона? Предварительно обработайте изображения, чтобы удалить такие нижние блоки, если это затруднительно, объясните, почему. Я буду считать, что эти коробки были удалены с этого момента.
SSIM (Структурная SIMilarity) может быть хорошим подходом для обнаружения ваших почти дубликатов, но у него нет шансов быть быстрее, чем более простой алгоритм, такой как NRMSE, описанный в Сравнение изображения в URL с изображением в файловой системе в Python. Таким образом, способ, возможно, ускорить процесс (хотя в природе он остается квадратичным) — сначала преобразовать данное изображение в градации серого и рассмотреть только небольшое центральное окно из него, например, 50×50. Примените гауссов фильтр к этому центральному окну, чтобы второстепенные структуры (например, шум) подавлялись. Поскольку у вас есть довольно много изображений для сравнения, я бы применил грубую бинаризацию в этом сглаженном центральном окне в виде: если значение v больше половины максимально возможного значения, затем превратите его в белый, в противном случае превратите в черный. Теперь у вас есть 2500 бит для каждого изображения. Следующим шагом может быть следующее: вычислить расстояние Хемминга от этих 2500 битов до общей битовой комбинации, здесь будет работать 2500 бит 1. Повторите этот процесс для всех ваших изображений. Для каждого изображения у вас есть расстояние Хэмминга.
Теперь давайте найдем почти идентичные изображения. Сначала рассмотрим биннинг найденных расстояний Хэмминга в k отдельные слоты. Итак, все изображения, попадающие в одну корзину, далее рассматриваются для сравнения. Таким образом, если изображение a приземляется в мусорное ведро k_i и изображение b приземляется в мусорное ведро k_j, i != jмы отбрасываем a как быть похожим на b, Если в одном бине слишком много изображений, описанный выше процесс требует уточнений и / или интервал для каждого бина должен быть уменьшен. Чтобы еще больше ускорить процесс, рассмотрите сначала применение NRMSE между всеми изображениями в одной и той же ячейке, и только те, которые дают высокое значение, будут, наконец, сравниваться с помощью SSIM.
MarvinLabs уже указал на идею хэширования первых N строк.
Если вы используете хороший хеш (например, MD5) для первых N (скажем, 20) строк, вы можете быть совершенно уверены, что коллизии хеша идентифицируют идентичные изображения. поместите хеш вместе с другим уникальным идентификатором изображения (имя файла?) в std :: multimap. Эта мультикарта обойдется вам в зависимости от длины пути от 10 до 100 МБ и может быть легко сохранена в памяти. Вы можете сделать свои отчеты после хеширования. если вы параноик, вы делаете другое сравнение изображений для столкновений. если не все изображения с одной камеры видеонаблюдения, вероятность ложного срабатывания меньше, чем ошибка чтения с диска.