C++ - 使用opencv flann查找最近邻居

Question

我有两组点(cv :: Point2f):setA和setB.对于setA中的每个点,我想在setB中找到它的最近邻居.所以,我尝试了两种方法:

1. 线性搜索:对于setA中的每个点,只需扫描setB中的所有点即可找到最近的点.

2. 使用opencv kd-tree:

   _首先,我使用opencv flann为setB构建了一个kd-tree:

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

   _然后,对于setA中的每个点,我都会查询以找到最近的邻居:

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

注意:我将maxPoints设置为1,因为我只需要最近的一个.

我做了一些研究,并为每个案例提出了一些时间复杂性:

1. 线性搜索:O(M*N)

2. Kd-Tree:NlogN + MlogN =>构建kd-tree的第一个术语,第二个术语用于查询

其中M是setA中的点数,N是setB的点数.并且范围N:100~1000,范围M:10000~100000.

因此,kd-tree应该比线性搜索方法运行得快得多.但是,当我在笔记本电脑上运行真正的测试时,结果是kd-tree方法比线性搜索慢(0.02~0.03s vs 0.4~0.5s).

当我进行性能分析时,我在knnSearch()函数中得到了热点,它占用了20.3%的CPU时间,而线性搜索则为7.9%.

嗯,我读了一些在线文章,他们说要查询kd-tree它通常需要logN.但我不确定opencv如何实现它.

谁知道这里有什么问题？是否有任何参数我应该在kd-tree中调整,或者我在代码或计算中的某处出错？

Answer 1

取自Flann文档.对于低维数据,您应该使用KDTreeSingleIndexParams.

KDTreeSingleIndexParams 

传递此类型的对象时,索引将包含一个kd-tree,该kd-tree已针对搜索较低维度数据(例如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