FLANN库介绍及其应用

xiaoxiao2021-03-01  21

原文转自:https://blog.csdn.net/App_12062011/article/details/51987352

-----------------------------------------------分割线---------------------------------------------

一、简介

我们可以用下面的方式定义最近邻搜索(NNS)问题:在一个度量空间X给定一组点P=p1,p2,…,pn,这些点必须通过以下方式进行预处理,给第一个新的查询点q属于X,快速在P中找到距离q最近的点,即最近邻搜索问题。

 

最近邻搜索的问题是在很多应用领域是一个重大问题,如图像识别、数据压缩、模式识别和分类、机器学习、文档检索系统、统计和数据分析等。然而,在高维空间中解决这个问题似乎是一个非常难以执行任务,没有算法明显优于标准的蛮力搜索。因此越来越多的人把兴趣点转向执行近似最近邻搜索的一类算法,这些方法在很多实际应用和大多数案例中被证明是足够好的近似,比精确搜索算法快很大的数量级。

 

FLANN(Fast Library for Approximate Nearest Neighbors)是一个执行快速近似最近邻搜索的库。FLANN使用C++写成。他能够很容易地通过C,MTALAB和Python等绑定提供的库,用在很多环境中。

 

二、使用FLANN

FLANN库的核心部分使用C++写成。为了最大性能和灵活性的使用模版代码,应该尽量使用C++绑定(C++ bindings)。你只要包含库的头文件flann.hpp就能使用C++bindings。

 

下面我们介绍几个公共C++ API。

 

1.flann::Index

这是FLANN最近邻指数类。该类用于抽象的不同类型的最近邻搜索索引。距离函子的类模板用于计算两个特征空间之间的距离。

namespace flann { template<typename Distance> class Index { typedef typename Distance::ElementType ElementType; typedef typename Distance::ResultType DistanceType; public: Index(const IndexParams& params, Distance distance = Distance() ); Index(const Matrix<ElementType>& points, const IndexParams& params, Distance distance = Distance() ); ~Index(); void buildIndex(); void buildIndex(const Matrix<ElementType>& points); void addPoints(const Matrix<ElementType>& points, float rebuild_threshold = 2); void removePoint(size_t point_id); ElementType* getPoint(size_t point_id); int knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, size_t knn, const SearchParams& params); int knnSearch(const Matrix<ElementType>& queries, std::vector< std::vector<int> >& indices, std::vector<std::vector<DistanceType> >& dists, size_t knn, const SearchParams& params); int radiusSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params); int radiusSearch(const Matrix<ElementType>& queries, std::vector< std::vector<int> >& indices, std::vector<std::vector<DistanceType> >& dists, float radius, const SearchParams& params); void save(std::string filename); int veclen() const; int size() const; IndexParams getParameters() const; flann_algorithm_t getType() const; }; }

 

其他API,大家可以通过FLANN手册查找,下载 http://download.csdn.net/detail/eric41050808/9133803 。此次仅介绍knnSearch方法:

 

2.flann::Index::knnSearch

对一组点查询点,该方法执行K最近邻搜索。该方法有两个实现,一个携带预开辟空间的flann::Matrix对象接收返回的找到邻居的索引号和到其距离;另一个是携带std::vector<std::vector>根据需要自动重新调整大小。

 

  int Index::knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, size_t knn, const SearchParams& params); int Index::knnSearch(const Matrix<ElementType>& queries, std::vector< std::vector<int> >& indices, std::vector<std::vector<DistanceType> >& dists, size_t knn, const SearchParams& params);

 

参数:

queries: 承载查询点的矩阵,矩阵大小是:查询点数*纬数;

indices: 将承载所有被找到的K最近邻的索引号( 预开辟的大小应该至少是查询点数*knn);

dists:     将承载到所有被找到的K最近邻的距离只(预开辟大小应该至少是查询点数*knn);

knn:       要找的最近邻的个数;

params: 搜索参数。承载搜索时要使用的参数的结构体,结构体类型是SearchParameters。

SearchParameters struct SearchParams { SearchParams(int checks = 32, float eps = 0, bool sorted = true); int checks; float eps; bool sorted; int max_neighbors; tri_type use_heap; int cores; bool matrices_in_gpu_ram; };

 

其中,checks: 当搜索邻居时用来制定叶子数的最大值。其值越大,搜索精度越高,但是也会消耗更多时间。如果要检索所有叶子,使用宏值CHECKS UNLIMITED。如果在对象index创建时使用自动配置,达到指定精度的需要的检索次数也会被计算出来,这是使用宏值CHECKS_AUTOTUNED。

转载请注明原文地址: https://www.6miu.com/read-4149953.html

最新回复(0)