Вы правы, наивный алгоритм будет O(n^2), потому что вы делаете попарное сравнение по всему вашему набору данных n-размера.
Существует методика, называемая blocking , реализация которой - кластеризация навеса , которая может обойти парные сравнения путем разбиения размера окна сравнения на набор «блоков». которые потенциально похожи.
Вы можете кластеризовать свои изображения, извлекая и сортируя по вектору объектов (что я не знаю, как делать с изображениями).
Затем определите окно сравнения w, такое, что w
Затем примените технику, называемую методом отсортированной окрестности , которая последовательно перемещает окно фиксированного размера w по отсортированным записям. Каждое изображение в окне затем соединяется со своим «соседом» и включается в список пар записей кандидатов.
Это в основном уменьшает сложность сравнения до O(w * n), в результате чего получается линейный алгоритм с постоянной w.
После того, как вы выполнили сравнения, вы должны взять транзитивное замыкание для совпадающих пар.
Ваши получившиеся пары - это то, что будет считаться similar изображениями.
Обратите внимание, этот алгоритм смущающе параллелен .