近似最近鄰搜尋方法FLANN簡介

• AR/VR群：244751474 ，歡迎加入，進行項目讨論！

-----------------------------------------------分割線---------------------------------------------

一、簡介

我們可以用下面的方式定義最近鄰搜尋（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。