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

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

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