FLANN库介绍及其应用

傷城~ 2022-05-13 03:24 484阅读 0赞

原文转自：[https://blog.csdn.net/App\_12062011/article/details/51987352][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手册][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_blog.csdn.net_App_12062011_article_details_51987352]: https://blog.csdn.net/App_12062011/article/details/51987352
[FLANN]: http://download.csdn.net/detail/eric41050808/9133803