FLANN库介绍及其应用
原文转自：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。