FLANN-use
为什么用flann
在点集X中存储了大量点，给定一个点y并需要在X中寻找距离点y最近的一个点或者多个点时，通常采用硬查找或者近似最近邻的方式进行查找。而点数越多、维度越高，硬查找的方法将会消耗大量的时间，但是找到的结果精度是较高的。为了提升效率我们可以通过近似最近邻的方法查找最近点。
关于这方面的库主要由ANN（2010），flann（2013），之前一直使用的是ANN，但是觉得效率方面并不是很理想。因此现在对flann进行调研与使用，flann与ann相比方法更加完备，使用起来可选择的方法更多，并且可以调用OPENMP、CUDA等对搜索进行加速，号称比ANN的速度快一个数量级，但用起来稍微麻烦一点。
怎么用flann
在flann的官网中可以下载其源码，可以绑定到C++、C、MATLAB、python，但是自己是使用C++写的。我主要是结合说明手册以及自己在C++中的使用方法与效率对比进行一个测试和使用记录。
多thread支持
可以选择多内核进行搜索，选择的方式是使用参数SearchParams，默认是单核计算的，可以通过设置这个参数的数值来使用内核数，也可以将参数设置为0，表示使用尽可能多的核来计算。
flann使用
我主要是看的C++使用，关于matlab C python的使用可以通过说明书再细看。
头文件
flann.hpp
3.1.1 flann::Index
FLANN的最近邻搜索类，这个类用于适应于不同类型的最近邻索引。这个点用于计算距离函数。
flann::Index::Index 构造函数
参数features，是包含用于构建索引的特征的矩阵；
参数params，是包含索引参数的结构，这个参数选择了搜索的方式，主要包括一下几种：
- LinearIndexParams 线性的、暴力(brute-force)的搜索。
- KDTreeIndexParams kd树构成(randomized kd-trees)，它可以平行地进行搜索。
struct KDTreeIndexParams : public IndexParams
{KDTreeIndexParams( int trees = 4 );
};
- KMeansIndexParams 层次k均值树
struct KMeansIndexParams : public IndexParams
{KMeansIndexParams(int branching = 32,//The branching factor to use for the hierarchical k-means treeint iterations = 11,//If a value of -1,should be iterated
until convergenceflann_centers_init_t centers_init = CENTERS_RANDOM,float cb_index = 0.2 );
};
- CompositeIndexParams 随机kd树与层次k均值树相结合
- KDTreeSingleIndexParams 仅仅是一个k-d树为低维度的搜索（如3D点云数据）
- KDTreeCuda3dIndexParams 运用CUDA的k-d树搜索，这最好用在有大量搜索和查询点的时候
- HierarchicalClusteringIndexParams hierarchical clustering index
- LshIndexParams 该结构使用multi-probe LSH方法创建索引
- AutotunedIndexParams 自动选择最好的以上结构
- SavedIndexParams 从文件中读取索引
centers init
这个参数用来选择在搜索时，选择初始中心的方法。可能之有：
CENTERS RANDOM：随即产生
CENTERS GONZALES：使用Gonzales’的算法
CENTERS KMEANSPP：D. Arthur and S. Vassilvitskii. k-means++中提到的方法。
3.1.2 flann::Index::buildIndex
创建最近邻索引可以使用两种方式：一个是传入点进去，一种是使用构造函数时传入的点。也就是这个借口可以选择不传参数。
void buildIndex();
void buildIndex(const Matrix<ElementType>& points);
3.1.3 flann::Index::addPoints/removePoint
在索引已经建立之后也可以增加和减少点。为了避免索引失衡，addPoints提供了在新增大量数据后的重建索引，参数rebuild threshold=2表示点云增加为size的两倍。removePoint一般不改变索引结构
3.1.5 flann::Index::getPoint
ElementType* getPoint(size_t point_id);不知道这里的point_id指的是什么？
3.1.6 flann::Index::knnSearch
是一个K邻域搜索，可以选择输出类型为matrix或者vector。用vector的话就不需要先限定数组的大小，能够自己扩展。
int Index::knnSearch(const Matrix<ElementType>& queries,//查询点。点数×维度Matrix<int>& indices,//返回的最近点数据 num queries × knnMatrix<DistanceType>& dists, //返回最近点的距离 num_queries×knnsize_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);struct SearchParams
{SearchParams(int checks = 32,float eps = 0,bool sorted = true);int checks;//检测点 CHECKS UNLIMITED CHECKS AUTOTUNEDfloat eps;//KD treebool sorted;//Used only by radius search, specifies if the neighbors returned should be sorted by distance.int max_neighbors;//Used only by radius search, 最多返回的点数tri_type use_heap;//int cores; //内核数 0表示自动选择bool matrices_in_gpu_ram;//
};
3.1.7 flann::Index::radiusSearch
与knn基本相同，只是最近的点数变为了半径大小
3.1.8 flann::Index::save
把索引表存入文件中，
void Index::save(std::string filename);
3.1.9 flann::hierarchicalClustering
使用多层次k均值树
3.1.10 flann::KdTreeCuda3dIndex
提供了CUDA为提升建立和查询速度的三维点云数据。首先需要在安装时候选择上CUDA选项才可以。
时间测试：
LinearIndexParams(): 0.460
KDTreeIndexParams(4): 0.58
KMeansIndexParams(): 0.290
CompositeIndexParams(): 0.280
KDTreeSingleIndexParams(): 0.20
LshIndexParams():error
HierarchicalClusteringIndexParams(): 0.500
AutotunedIndexParams(): 0.850??
搜索时候的配置都是全核： 二维坐标点 点数共有360个，搜索大概1200*180次
flann::SearchParams mypapra(16,0.1,false);mypapra.cores = 0;
// mypapra.checks=flann::CHECKS AUTOTUNED;index_->knnSearch(*query_, *indics_, *dists_, 1, mypapra);
EX:
flann::Matrix<float> *dataset_;flann::Matrix<float> *query_;flann::Matrix<int> *indics_;flann::Matrix<float> *dists_;flann::Index<flann::L2<float> > *index_;void cleanFLANN();
dataset_ = new flann::Matrix<float>(new float[maxPts*dim], maxPts, dim);for(int i=0; i<nsites; ++i){(*dataset_)[i][0]=points[i].x();(*dataset_)[i][1]=points[i].y();}
query_ = new flann::Matrix<float>(new float[k*dim], k, dim);dists_ = new flann::Matrix<float>(new float[k*dim], k, dim);indics_ = new flann::Matrix<int>(new int[k*dim], k, dim);index_ = new flann::Index<flann::L2<float> >(*dataset_,flann::KDTreeSingleIndexParams());index_->buildIndex();void VoronoiDiagramGenerator::cleanFLANN()
{if(dataset_){delete[] dataset_->ptr();delete[] dataset_;dataset_ = NULL;}//TODO:QY 下面这三个可以不清除内存的，反正每次都是寻找一个最近点。if(query_){delete[] query_->ptr();delete[] query_;query_ = NULL;}if(indics_){delete[] indics_->ptr();delete[] indics_;indics_ = NULL;}if(dists_){delete[] dists_->ptr();delete[] dists_;dists_ = NULL;}
}//search*query_[0][0] = x;*query_[0][1] = x;flann::SearchParams mypapra(16,0.1,false);mypapra.cores = 0;index_->knnSearch(*query_, *indics_, *dists_, 1, mypapra);return sqrt(*dists_[0][0]);
insall FLANN with CUDA
FLANN支持GPU并行计算，但是在安装时就需要选择并行。
1.刚开始在flann的发行版上进行安装未成功，因为后期CUDA版本更新，作者对flann进行了修改，但是没有把修改后的发行。因此1.8.4的发行版对cuda8.0不支持。因此我在github上下载了最新的flann-master原文件进行安装。
一直出现如下错误：
2.在cmake后打开CMakeCache.txt，选择CUDA-LIB，并把我不需要的Matlab的勾取消。
3.make
4.sudo make install
ALGLIB use
直接在官网下载源码，将源码放在项目中并进行了测试。
搜索条件：二维坐标点 点数共有360个，搜索大概1200*180次
时间为0.160s，与flann的最快搜索时间基本相同。
ANN-USE
搜索条件：二维坐标点 点数共有360个，搜索大概1200*180次
ANN_KD_STD = 0, // the optimized kd-splitting rule ERROR
ANN_KD_MIDPT = 1, // midpoint split 搜索时间为0.07s
ANN_KD_FAIR = 2, // fair split 搜索时间为0.08s
ANN_KD_SL_MIDPT = 3, // sliding midpoint splitting method 搜索时间为0.08s
ANN_KD_SL_FAIR = 4, // sliding fair split method //搜索时间为0.06s
ANN_KD_SUGGEST= 5}; // the authors’ suggestion for best 搜索时间为0.06ms
ANN_KD_SUGGEST对应下的搜索方式的时间开销：
- annkPriSearch：0.15s
- annkSearch: 0.06s
- annkFRSearch: 按照半径2.5m进行搜索，时间为0.055s ！！ 这种求最短距离的早该想到在固定半径内查找最近点！！