3

我有一套积分cloub（积分cloub的数量≈200万）。我想为点 cloub 中的每个点找到最近的 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 个邻居，因此我从数据的每一行中获取点并执行knn搜索。

4

1 回答 1

11

我最近也有类似的问题。这里有一些想法：

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

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

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

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

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

于 2016-03-10T17:11:56.510 回答