Сравнение возможностей SIFT, хранящихся в базе данных mysql

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

Каким будет самый быстрый способ сравнить возможности новых изображений с функциями в базе данных?
Обычно выполняется сравнение расчета евклидова расстояния с использованием kd-деревьев, FLANN или с Pyramid Match Kernel, которые я нашел в другом потоке здесь, на SO, но пока не очень заглянули.

Так как я не знаю способа эффективного сохранения и поиска kd-дерева в базе данных, в настоящее время я вижу только три варианта:
* Пусть MySQL вычислит эвклидовое расстояние до каждой функции в базе данных, хотя я уверен, что это займет необоснованное время для более чем нескольких изображений.
* Загрузите весь набор данных в память в начале и создайте kd-tree (s). Вероятно, это будет быстро, но очень интенсивно. Кроме того, все данные необходимо будет перенести из базы данных. * Сохранение сгенерированных деревьев в базу данных и загрузка всех из них было бы самым быстрым методом, но также генерировать большие объемы трафика, так как с новыми изображениями kd-деревья нужно было бы перестроить и отправить на сервер.

Я использую SIFT-реализацию OpenCV, но я не уверен в этом. Если для этой задачи больше подходит функция экстрактора (и примерно одинаково надежная), я рад, если кто-то может предложить ее.

Ответ 1

Итак, я в основном сделал что-то очень похожее на это несколько лет назад. Алгоритм, который вы хотите изучить, был предложен несколько лет назад Дэвидом Нистером, статья: "Масштабируемое распознавание с использованием словарного дерева". Они в значительной степени имеют точное решение вашей проблемы, которое может масштабироваться до миллионов изображений.

Вот ссылка на реферат, вы можете найти ссылку для скачивания, перейдя по заголовку. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018

Основная идея состоит в том, чтобы построить дерево с иерархическим алгоритмом k-средних для моделирования функций, а затем использовать разреженное распределение функций в этом дереве, чтобы быстро найти ближайших соседей... или что-то в этом роде, это было Несколько лет с тех пор, как я работал над этим. Вы можете найти презентацию PowerPoint на веб-странице авторов здесь: http://www.vis.uky.edu/~dnister/Publications/publications.html

Несколько других примечаний:

Я бы не стал беспокоиться о ядре с пирамидой, это действительно больше для улучшения распознавания объектов, чем для обнаружения дублированных/преобразованных изображений.
Я не буду хранить какие-либо из этих свойств в базе данных SQL. В зависимости от вашего приложения иногда более эффективно вычислять ваши функции "на лету", поскольку их размер может превышать размер оригинального изображения при плотном вычислении. Гистограммы признаков или указателей на узлы в лексиковом дереве намного эффективнее.
Базы данных SQL не предназначены для массовых вычислений векторных чисел с плавающей запятой. Вы можете хранить вещи в своей базе данных, но не используйте их как инструмент для вычисления. Я пробовал это один раз с SQLite, и это закончилось очень плохо.
Если вы решите это реализовать, внимательно прочитайте статью и сохраните ее при ее реализации, так как есть много мелких деталей, которые очень важны для эффективного функционирования алгоритма.

Ответ 2

Ключ, я думаю, заключается в том, что это не вопрос SIFT. Речь идет о приближенном поиске ближайшего соседа. Подобно сопоставлению изображений, это тоже проблема открытых исследований. Вы можете попробовать "приблизительный поиск ближайшего соседа" и посмотреть, какие методы доступны. Если вам нужны точные результаты, попробуйте: "поиск ближайшего ближайшего соседа".

Выполнение всех этих геометрических структур данных (таких как kd-деревья) ухудшается по мере увеличения размеров измерений, поэтому ключевым я считаю, что вам может потребоваться представить дескрипторы SIFT в меньшем числе измерений (например, 10 -30 вместо 256-1024), чтобы иметь действительно эффективный поиск ближайшего соседа (например, с помощью PCA).

Как только у вас есть это, я думаю, что он станет вторичным, если данные хранятся в MySQL или нет.

Ответ 3

Я думаю, что скорость здесь не является основной проблемой. Основная проблема заключается в том, как использовать функции для получения желаемых результатов.

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

Кроме того, существуют локальные функции, отличные от SIFT. Например, SURF - это функции, подобные SIFT, но они быстрее извлекаются, и они показали, что они работают лучше для определенных задач.

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

Ответ 4

У меня есть некоторые инструменты в python, которые вы можете играть с здесь. В основном это пакет, который использует преобразованные векторы SIFT, а затем вычисляет ближайшее хеширование решетки каждого 128-мерного вектора просеивания. Хеширование - важная часть, так как она чувствительна к местности, просто означает, что векторы, расположенные вблизи пространства R ^ n, приводят к эквивалентным вероятностям столкновения хэшей. Работа, которую я предоставляю, является расширением Andoni, который обеспечивает адаптивную эвристику запроса для обрезки точных списков поиска LSH, а также оптимизированную CUDA реализация хэш-функции. У меня также есть небольшое приложение, которое выполняет поиск в базе данных изображений с хорошей визуальной обратной связью, все под bsd (исключение - SIFT, который имеет некоторые дополнительные ограничения).