C++ - 使用 opencv flann 寻找最近邻

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

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

使用 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，因为我只需要最近的一个。

我做了一些研究，并为每个案例得出了一些时间复杂度:

线性搜索:O(M*N)

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 中调整任何参数还是我在代码或计算中的某个地方犯了错误？

最佳答案

取自 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

关于C++ - 使用 opencv flann 寻找最近邻，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29488832/