opencv中的FLANN运行速度太慢

Question

我有一套点cloub(点数cl≈2百万).我想找到点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邻居,因此我从数据的每一行中取出点并执行knnSearch.

Answer 1

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

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

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

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

第四,似乎您一次只搜索一个查询点的邻居.尝试一次运行多个查询点.返回参数"indices"和"dists"将是矩阵,其中每行r表示索引r处的点的邻居(并且每行的第一个元素表示查询点本身).

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