Как вычислить точку на линии в CGAL
В настоящее время я расширяю библиотеку изображений, используемую для категоризации изображений, и хочу найти дубликаты изображений, преобразованные изображения и изображения, которые содержат или содержатся в других изображениях.
Я протестировал реализацию SIFT из OpenCV, и она работает очень хорошо, но будет довольно медленной для нескольких изображений. Слишком быстро, я думал, что смогу извлечь функции и сохранить их в базе данных, так как многие другие метаданные, связанные с изображениями, уже хранятся там.
Какой самый быстрый способ сравнить характеристики новых изображений с объектами в базе данных?
Обычно сравнение выполняется для вычисления евклидова расстояния с использованием kd-деревьев, FLANN или с помощью Пирамидного соответствия Ядро , которое я нашел в другом потоке здесь, на SO, но пока не слишком изучило его.
Поскольку я не знаю, как эффективно сохранить и найти kd-дерево в базе данных, я ' м в данный момент вижу только три варианта:
* Пусть MySQL вычислит евклидово расстояние до каждой функции в базе данных, хотя я уверен, что это займет неоправданное время для нескольких изображений.
* Загрузите весь набор данных в память в начале и постройте kd-tree (s). Это, вероятно, будет быстро, но очень много памяти. Кроме того, все данные необходимо будет перенести из базы данных.
* Сохранение сгенерированных деревьев в базу данных и загрузка всех из них будет самым быстрым способом, но также генерирует большие объемы трафика, так как с новыми изображениями kd-деревья придется перестраивать и отправлять на сервер.
I ' Я использую SIFT-реализацию OpenCV, но я не уверен в этом. Если есть средство извлечения функций, более подходящее для этой задачи (и примерно одинаково надежное), я рад, если кто-то может предложить его.
3 ответа
Итак, несколько лет назад я сделал нечто очень похожее на это. Алгоритм, который вы хотите изучить, был предложен несколько лет назад Дэвидом Нистером, статья гласит: «Масштабируемое распознавание с помощью словарного дерева». У них в значительной степени есть точное решение вашей проблемы, которое можно масштабировать до миллионов изображений.
Вот ссылка на аннотацию, вы можете найти ссылку для скачивания, погуглив заголовок. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1641018
Основная идея состоит в том, чтобы построить дерево с иерархическим алгоритмом k-средних для моделирования функций и затем использовать разреженное распределение функций в этом дереве, чтобы быстро найти ближайших соседей ... или что-то в этом роде, прошло несколько лет с тех пор, как я работал над этим. Вы можете найти презентацию в формате PowerPoint на странице авторов здесь: http://www.vis.uky.edu/~dnister/Publications/publications.html
Еще несколько примечаний:
Я бы не стал возиться с ядром сопоставления пирамиды, это действительно больше для улучшения распознавания объектов, чем обнаружение дублированных / преобразованных изображений.
Я бы не стал хранить эти функции в базе данных SQL. В зависимости от вашего приложения иногда более эффективно вычислять ваши особенности "на лету", поскольку их размер может превышать размер исходного изображения при плотном вычислении. Гистограммы функций или указатели на узлы в словарном дереве намного эффективнее.
Базы данных SQL не предназначены для массовых вычислений векторов с плавающей запятой. Вы можете хранить вещи в своей базе данных, но не использовать ее как инструмент для вычислений. Я однажды попробовал это с SQLite, и все закончилось очень плохо.
Если вы решите реализовать это, прочтите документ подробно и держите копию под рукой при его реализации, так как есть много второстепенных деталей, которые очень важны для обеспечения эффективной работы алгоритма.
Ключевой момент, я думаю, в том, что это не вопрос SIFT. Речь идет о приблизительном поиске ближайшего соседа. Как и сопоставление изображений, это тоже проблема открытых исследований. Вы можете попробовать погуглить "приблизительный поиск ближайшего соседа" и посмотреть, какие типы методов доступны. Если вам нужны точные результаты, попробуйте: «точный поиск ближайшего соседа».
Производительность всех этих геометрических структур данных (таких как kd-деревья) ухудшается по мере увеличения количества измерений, поэтому я думаю, что ключевым моментом является то, что вам может потребоваться представить свои дескрипторы SIFT в меньшем количестве измерений (скажем, 10 -30 вместо 256-1024), чтобы иметь действительно эффективный поиск ближайшего соседа (например, используйте PCA).
Как только вы получите это, я думаю, станет второстепенным, будут ли данные храниться в MySQL или нет.
Я думаю, что скорость здесь не главная проблема. Основная проблема заключается в том, как использовать функции для получения желаемых результатов.
Если вы хотите разделить изображения на категории (например, человек, машина, дом, кошка), то определенно стоит обратить внимание на ядро Pyramid Match. Фактически это гистограмма дескрипторов локальных функций, поэтому нет необходимости сравнивать отдельные функции друг с другом. Существует также класс алгоритмов, известный как «набор слов», которые пытаются сгруппировать локальные особенности для формирования «визуального словаря». Опять же, в этом случае, когда у вас есть «визуальные слова», вам не нужно вычислять расстояния между всеми парами дескрипторов SIFT, а вместо этого определять, к какому кластеру принадлежит каждая функция.С другой стороны, если вы хотите получить точечные соответствия между парами изображений, например, чтобы решить, содержится ли одно изображение в другом, или вычислить преобразование между изображениями, тогда вам действительно нужно найти точных ближайших соседей.
Кроме того, существуют локальные функции, отличные от SIFT. Например, SURF - это функции, похожие на SIFT, но они быстрее извлекаются, и было показано, что они лучше работают для определенных задач.
Если все, что вам нужно, - это найти дубликаты, вы можете значительно ускорить поиск, используя глобальный дескриптор изображения, такой как цветовая гистограмма, для удаления изображений, которые явно отличаются. Сравнение двух цветовых гистограмм на порядки быстрее, чем сравнение двух наборов, каждый из которых содержит сотни функций SIFT. Вы можете создать короткий список кандидатов с помощью цветных гистограмм, а затем уточнить поиск с помощью SIFT.