C++ - Поиск ближайшего соседа с использованием opencv flann

Question

У меня есть два набора точек (cv :: Point2f): setA и setB. Для каждой точки в setA я хочу найти ближайшего соседа в setB. Итак, я попробовал два метода:

1. Линейный поиск: для каждой точки множества А, просто сканировать через все точки SETB найти ближайший один.

2. Использование OpenCV кД-дерево:

   _ Сначала я построил KD-дерево для SETB с использованием OpenCV Flann:

   cv::flann::KDTreeIndexParams indexParams; 
   cv::flann::Index kdTree(cv::Mat(setB).reshape(1), indexParams); 
   

   _ Тогда для каждой точки множества А я запрос, чтобы найти ближайший сосед:

   kdTree.knnSearch(point_in_setA, indices, dists, maxPoints); 
   

Примечание: Я установил maxPoints 1, потому что мне нужен только ближайший к вам.

я немного исследование, и выйти с некоторой временной сложности для каждого случая:

1. Линейный поиск: O (M * N)

2. Kd-Tree: NlogN + MlogN = > первый термин для построения KD-дерево, второй член для запроса

где М обозначает число точек в множестве а и Н для SETB. И диапазон N: 100 ~ 1000, диапазон M: 10000 ~ 100000.

Таким образом, kd-дерево должно работать намного быстрее, чем метод линейного поиска. Однако, когда я запускаю настоящий тест на своем ноутбуке, результатом является метод kd-tree медленнее, чем линейный поиск (0,02-0,03 с против 0,4 ~ 0,5 с).

Когда я делаю профилирование, я получил горячую точку в функции knnSearch(), это занимает 20,3% времени процессора, сравнивается с 7,9% линейного поиска.

Ум, я прочитал некоторые онлайн-статьи, они сказали, что запрашивают kd-дерево, которое обычно принимает logN. Но я не уверен, как это реализовать.

Кто знает, что здесь не так? Есть ли какой-либо параметр, который я должен настроить в kd-дереве, или я сделал ошибку где-то в коде или вычислении?

Answer 1

Взято из Flann documentation. Для низкоразмерных данных вы должны использовать KDTreeSingleIndexParams.

KDTreeSingleIndexParams 

При прохождении объекта этого типа индекс будет содержать одну KD-дерево, оптимизированное для поиска более низких данных размерности (для облаков Примера 3D точки), в вашем случае 2D точек. Вы можете играть с параметрами leaf_max_size и профилировать свои результаты.

struct KDTreeSingleIndexParams : public IndexParams 
{ 
    KDTreeSingleIndexParams(int leaf_max_size = 10); 
}; 

max leaf size: The maximum number of points to have in a leaf for not 
branching the tree any more 

Answer 2

O (log (N)) не обязательно означает, что он быстрее, чем O (N). Это справедливо только для достаточно больших N. Ваш N - довольно небольшое число. Если ваше kd-дерево содержит миллионы элементов, вы, вероятно, увидите разницу между линейным сканированием и логарифмическим поиском.

Итак, я предполагаю, что вы тратите много времени с накладными расходами, например, на строительство дерева, которое медленнее для небольшого N, чем просто сканирование этого небольшого списка без каких-либо накладных расходов.