OpenCV——KD Tree（介绍完整的flann邻近搜索）

完整的flann邻近搜索）"/>

OpenCV——KD Tree（介绍完整的flann邻近搜索）

写在前面

关于KD-Tree搜索的文章不多，其实在opencv中，所谓kd-tree搜索，只是flann“Fast Approximate Nearest Neighbor Search”中索引的一种。即kd-tree搜索，指的是在建立索引这一步骤中建立的是kd-tree索引。

所以本文实质介绍的是：OpenCV与FLANN库的接口。 FLANN（近似近邻的快速搜素库）是一个工具库，其中包含针对大数据集中的快速最近邻搜索和高维度特征优化的算法集合。

环境： 笔者使用的是OpenCV 2.49 （3.0以后可能有变化）
需要引用的头文件： #include “opencv2//flann/miniflann.hpp”

正文

使用flann的搜索，整体来说分为两步，一是建立索引，二是搜索。

索引建立

flann::Index_::Index_(const Mat& features, const IndexParams& params)
Parameters:

• features – Matrix of containing the features(points) to index. The
  size of the matrix is num_features x feature_dimensionality and the
  data type of the elements in the matrix must coincide with the type
  of the index.
• params – Structure containing the index parameters. The type of index that will be constructed depends on the type of this parameter. See the description.

其实就是要两部分参数，一是数据也就是mat矩阵，二是一些具体参数，这个参数要根据建立的索引类型来设置。而有哪些索引类型呢？
共有：线性索引、KD-Tree索引、K均值索引、复合索引、LSH方法索引、自动索引 六种，下面详细介绍每种索引及其相应参数：

• LinearIndexParams //线性索引

  struct LinearIndexParams : public IndexParams
  {
  };
  没什么要设置的参数

• KDTreeIndexParams //KD-Tree索引

  struct KDTreeIndexParams : public IndexParams
  {
  KDTreeIndexParams( int trees = 4 );
  };

  • trees The number of parallel kd-trees to use. 范围： [1-16]

  知道不同的索引该设置对应的参数，那么具体应该怎么设置呢？刚好以kd-tree索引为例：
  如何建立KD-Tree索引：

  /** 建立kd树索引 **/
  /* features */
  Mat source = cv::Mat(m_pOriPtXY).reshape(1); //vector<Point2d> m_pOriPtXY
  //即m_pOriPtXY是Point2d类型的vector数组，由于建立索引需要mat类型，就直接用m_pOriPtXY去生成一个mat对象
  source.convertTo(source,CV_32F);