Алгоритм поиска похожих изображений с использованием индекса

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

Я только пробовал первый, но все они разработаны для Windows и не являются открытым исходным кодом. Уникальный Filer был выпущен в 2000 году, и, похоже, главная страница исчезла. Это было неожиданно быстро (даже на компьютерах того года), потому что он использовал индекс и сравнивал около 10000 изображений с использованием индекса, необходимого всего на несколько секунд (и обновление индекса было масштабируемым процессом).

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

Я уже проверил вопрос Алгоритм поиска похожих изображений, но все ответы на них решают проблему, сравнивая одно изображение с другим. Для 1000+ изображений это приведет к 1000 ^ 2 сравнению операций, которые просто не то, что я ищу.

+8
источник поделиться
1 ответ

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

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

LSHKIT - это реализация LSH с открытым исходным кодом.

+2
источник

Посмотрите другие вопросы по меткам или Задайте вопрос