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 documentation .对于低维数据，您应该使用KDTreeSingleIndexParams。

KDTreeSingleIndexParams 

当传递这种类型的对象时，索引将包含一个针对搜索低维数据(例如 3D 点云)优化的单个 kd 树，在您的情况下是 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