Нужен хороший алгоритм для категоризации 8 ГБ изображений

Я бы попробовал подход, похожий на хэш / отпечаток пальца:

• Создание отпечатка пальца для каждого изображения, содержащего также соответствующие атрибуты изображения, такие как размер и количество компонентов для метафайла или базы данных. Отпечаток пальца может быть вычислен из общего фрагмента изображения, это может быть спектрограмма, сжатая с потерями, простой вектор, содержащий элементы разрешения по частоте БПФ, гистограмма или другой метод (я понятия не имею, что подходит лучше, это больше всего вероятно, очень зависим от содержания).

• Как упоминал Литтлстеви, предварительная группировка с использованием атрибутов изображения, таких как размер и количество цветовых компонентов, значительно сократит количество (бинарных) сравнений, которое будет (n*(n-1))/2 для каждой группы.

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

• OpenCV может сделать финальное совпадение:

  Как обнаружить Солнце из космического неба в OpenCv?

Связанные вопросы относительно сравнения изображений с использованием OpenCV:

• OpenCV / SURF Как сгенерировать хэш изображения / отпечаток пальца / подпись из дескрипторов?

• OpenCV: изображение отпечатка пальца и сравнение с базой данных

Есть изображения, которые различаются по высоте, но в основном это одно и то же изображение, только с несвязанным прямоугольником внизу, который меняет высоту.

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

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

Использование любой формы хеширования здесь действительно бессмысленно, поскольку даже почти идентичные изображения будут давать очень разные хеш-значения. Как было указано в комментариях, два «дублированных» изображения могут немного отличаться (подумайте, например, об эффектах, вызванных сжатием JPEG), поэтому интерес представляет обнаружение почти дублированных изображений. Кроме того, как было указано в комментариях, рассмотрение только изображений одинаковой ширины - это первый шаг к уменьшению квадратичного количества сравнений. Если все изображения одинаковой ширины, улучшения нет.

Первая проблема, которую вы должны решить, - это отказаться от нижнего блока с почти идентичными изображениями разной высоты. Почему эта коробка там? Это равномерный цвет фона? Предварительно обработайте изображения, чтобы удалить такие нижние блоки. Если это проблематично, объясните, почему. Я буду считать, что эти ящики отныне сняты.

SSIM (структурное сходство) может быть хорошим подходом для обнаружения ваших почти дубликатов, но у него нет шансов быть быстрее, чем более простой алгоритм, такой как NRMSE, описанный в Сравнение изображения в URL-адресе с изображением в файловой системе в Python. Таким образом, способ, возможно, ускорить процесс (хотя по своей природе он остается квадратичным), состоит в том, чтобы сначала преобразовать данное изображение в оттенки серого и рассматривать только небольшое центральное окно из него, например 50x50. Примените гауссовский фильтр к этому центральному окну, чтобы незначительные структуры (например, шум) в основном подавлялись. Поскольку у вас есть довольно много изображений для сравнения, я бы применил грубую бинаризацию в этом сглаженном центральном окне в виде: если значение 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 МБ и может легко храниться в памяти. вы можете делать свои отчеты после хеширования. если вы параноик, вы делаете еще одно сравнение изображений на предмет столкновений. если все изображения не получены с одной и той же камеры видеонаблюдения, вероятность ложного срабатывания меньше, чем ошибка чтения с диска.