opencv - opencv 中的 FLANN 运行速度太慢

Question

我有一组点云(点云数≈200万)。我想为点群中的每个点找到最近的 k 邻居。我做了这样的事情

flann::Index flann_index(data_m, flann::KDTreeIndexParams(),cvflann::FLANN_DIST_EUCLIDEAN);// create the object of flann
    for (int i = 0; i < numberOfPointsInPointCloub; i++){
    flann_index.knnSearch(data_m.row(i), indices, dists,num_of_knn); //each row is a new set of point in 3D
    ..//save the results "dist" and "indices" in somewhere else
}

但这运行起来很慢。在 for 循环中，它运行 1000 次，持续 20 秒，这非常慢。我用错了吗？或者有什么方法可以加快速度吗？

更新:我需要搜索的查询点正是用于构建树的点，我需要为树中的每个点找到最近的 k 个邻居，因此我从数据的每一行中获取点并执行 knnSearch。

Answer 1

我最近遇到了类似的问题。以下是一些想法:

首先，确保您处于 Release模式。未经优化的代码会严重影响性能。我最近的测试表明，在从调试代码切换到发布代码后，性能提高了 70 倍。

其次，您正在使用 flann::KDTreeIndexParams() 的默认值，即 4 棵树。为了提高速度，您可以将其降低到 1。这可能会降低准确性，但有助于提高性能。

第三，至少在最新版本的 OpenCV 中，knnSearch 函数有第五个参数，即 SearchParams()。它的构造函数的第一个参数“指定索引中的树应该被递归遍历的次数”，可以修改以平衡性能和准确性。查看OpenCV documentation了解详情。

第四，您似乎是在一次搜索一个查询点的邻居。尝试使用一次运行多个查询点。返回参数“indices”和“dists”将是矩阵，其中每一行 r 代表索引 r 处的点的邻居(每行的第一个元素代表查询点本身)。

最后，如果这仍然不够快，也许可以查看 VCG ibrary 中的 KdTree 实现。 .到目前为止，我已经看到 Release模式的性能比 OpenCV 的 FLANN 提高了 2 倍以上。您也可以尝试并行化，但我只会在您从非并行版本中获得尽可能多的性能后才走这条路。