OpenCV中的FLANN运行速度太慢。

Question

OpenCV中的FLANN运行速度太慢。

3

我有一组点云（点云数量约为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。

- Carl

1

k-NN算法可能会遭受所谓的“维度灾难”，并且最坏情况下的时间复杂度为*O(kN^(1-1/k))*。如果您的点云几乎是随机的，那么您可能无法加速搜索。当您遍历每个大约200万个点并执行knnSearch时，您正在创建一个将以超线性时间运行的嵌套循环。没有看到所有代码，很难确定可以对代码进行哪些优化以加快速度。 - callyalater

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- qdin · Accepted Answer

我最近也遇到了类似的问题，以下是一些想法：

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

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

第三，至少在OpenCV的最新版本中，knnSearch函数有一个第五个参数，即SearchParams()。它的构造函数的第一个参数 "指定应递归遍历索引中的树的次数"，可以修改以平衡性能和准确性。详见OpenCV文档。

第四，看起来您正在一次搜索一个查询点的邻居。尝试使用多个查询点运行。返回参数 "indices" 和 "dists" 将成为矩阵，其中每行r表示索引为r的点的邻居（每行的第一个元素表示查询点本身）。

最后，如果这仍然不够快，也许可以看看VCG库中的KdTree实现。到目前为止，我已经看到了比OpenCV的FLANN高出2倍以上的发布模式性能提升。您还可以尝试并行化，不过我建议只有在从非并行版本中尽可能获取更多性能之后再考虑这条路。