C++ - 使用OpenCV FLANN查找最近邻

Question

我有两组点（cv::Point2f）：setA和setB。对于setA中的每个点，我想在setB中找到其最近的邻居。因此，我尝试了两种方法：

1. Linear search: for each point in setA, just simply scan through all points in setB to find nearest one.

2. Using opencv kd-tree:

   _ First I built a kd-tree for setB using opencv flann:

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

   _ Then, for each point in setA I do query to find nearest neighbor:

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

注：我将maxPoints设置为1，因为我只需要最近的点。 我进行了一些研究，并为每种情况提出了一些时间复杂度: 1.线性搜索:O(M*N) 2.Kd-Tree:NlogN + MlogN=>第一项用于构建kd-tree，第二项用于查询 其中M是集合A中点的数量，N是集合B中点的数量。 N的范围是100〜1000，M的范围是10000〜100000。 因此，kd-tree应该比线性搜索方法运行得快得多。然而，当我在笔记本电脑上运行真实测试时，结果是kd-tree方法比线性搜索慢(0.02~0.03秒与0.4~0.5秒)。 当我进行分析时，我在knnSearch()函数处发现了热点，它占用了20.3%的CPU时间，而线性搜索只有7.9%。 嗯，我阅读了一些在线文章，他们说查询kd-tree通常需要logN。但是我不确定opencv如何实现它。 有人知道这里的问题吗？在kd-tree中是否有任何参数需要调整或者我在代码或计算方面犯了错误？

- OhMyGosh

Answer 1

这段内容来自于Flann文档。对于低维数据，你应该使用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

- Kirell

---

哇，太棒了！我在文档中没有看到这个，感谢你指出来。我会尝试一下，并很快向你更新。 - OhMyGosh

Answer 2

O(log(N))并不一定比O(N)更快。这只有在N足够大的情况下才成立。你的N是一个相当小的数字。如果你的kd树包含数百万个元素，你可能会看到线性扫描和对数搜索之间的差异。

所以我猜想你花了很多时间来建立树这样的开销，对于小的N来说，这比没有任何开销地扫描这个相当小的列表要慢。

- Ben

---

是的，你的观点很有道理，我也考虑过这个问题。这就是为什么我进行了分析，结果显示瓶颈来自于kd-tree查询，而不是构建kd-tree。这让我感到困惑！谢谢你的意见。 - OhMyGosh

你是对的，我刚做了一个测试。建树不是问题。但是，假设你在kd树中有100个条目。现在假设knnSearch()仅比100个条目的线性搜索多花费一点时间，因为它更复杂。这将与查询数量呈线性关系。如果你有100000个条目在kd树中，线性搜索对于一个查询可能会比较慢，因此也会对于许多查询慢。为了从kd树的对数搜索中受益，您必须在其中存储许多数据。 - Ben

嗯，我也是这么想的。现在，我正在尝试另一种方法，将图像分成小网格，在点所属的网格内进行局部搜索。如果网格中没有点，则在相邻的网格中进行搜索。 - OhMyGosh

@OhMyGosh 你可以使用二进制空间分割（如KD树或四叉树）或者使用空间哈希。它们都有不同的优缺点，具体取决于你的使用情况。 - Micka