这是2022年的第一篇博客，新年好！
最近做课题的时候需要写一个对高维度的向量（维度>3，采用欧几里得距离）进行k近邻搜索的函数。之前只用过PCL里面封装好的kd树对三维点云数据做k近邻搜索，当输入数据的维度大于三的时候，用PCL里现成的类和函数就不太好使了。又懒得自己写代码，于是想借助flann库里的函数来对高维的数据进行最近邻查找。flann的全名是Fast Library for Approximate Nearest Neighbors，是一个用于最近邻查找的库。（PCL中已经包含了flann库，pcl的kd树也是基于flann做成的。）
我上网下了个flann的使用指南，看了看各个类和函数的介绍。以下是我个人的理解，不一定对：
flann库中有一个Index类，文档中提到它的作用是：This class is used to abstract different types of nearest neighbor search indexes. 它的构造函数是Index(const Matrix<ElementType>& points, const IndexParams& params, Distance distance = Distance() );。其中points是一个用于存放数据的矩阵，其大小为：点的数量×点的维度；params是一个用来存放参数的结构体，与想要采用的搜索方式有关，可选的有KDTreeIndexParams，KMeansIndexParams，LinearIndexParams等等；而distance是定义两个点之间的距离的计算方式的结构体，常用的有欧几里得距离，曼哈顿距离，等等。
我想要用kd树来实现knn搜索，那么首先需要初始化一个Index对象，指定用kd树来存储。然后再使用Index类中的knnSearch函数来进行搜索。函数的声明如下：
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存放了用于查询的点（可以同时查询多个点，所以queries，indices和dists都是二维矩阵），indices存放的是查询点的k个近邻点索引，dists存放的是近邻点到查询点的距离，knn是近邻点的个数，param是一个存放参数的结构体，其定义如下：
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是查询过程中访问的叶子节点的最大个数（值越大，查询精度越高，但是耗时越长）。sorted和max_neighbors是用于基于半径的邻域搜索，前者指定返回的结果是否需要按照距离的长短来排序，后者指定返回的最大的点数。
我用Eigen::MatrixXf类型的矩阵作为输入数据，需要注意的是Eigen和flann中对于矩阵的存储方式不同，所以开始的时候需要转换一下（用了最傻的方式，把矩阵遍历了一遍，其他方法可以参考这里)。
//将eigen的矩阵转换为flann中的矩阵类型
flann::Matrix<float> convert_matrix(Eigen::MatrixXf mat)
{
int r = mat.rows();
int c = mat.cols();
//flann用矩阵存储数据时，每一行代表一个数据点，这里输入的mat是默认用列存储的，所以行和列需要翻转一下
flann::Matrix<float> mat2(new float[r*c], c, r);
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
mat2[j][i] = mat(i, j);
}
}
return mat2;
}
//D:存放点数据，pts:存放查询点，k:近邻点的个数，idx:近邻点的索引
void knn_search(Eigen::MatrixXf D, Eigen::MatrixXf pts, int k, vector<vector<int>>& idx)
{
//Eigen::MatriXf 和 flann的Matrix对数据的存储方式不一样，前者是列优先的，后者是行优先的
flann::Matrix<float> D_mat = convert_matrix(D);
flann::Matrix<float> query = convert_matrix(pts);
//flann::L2<float>指定了使用欧几里得距离
flann::Index<flann::L2<float>> index(D_mat, flann::KDTreeIndexParams());
//用来存放结果的idx和dst的大小应该事先指定
vector<vector<float>> dst(idx.size(), vector<float>(k));
index.buildIndex();
//使用knn查询，将check的值设为32
index.knnSearch(query, idx, dst, k, flann::SearchParams(32));
return;
}
然而把每个函数的文档都看了一遍，自己写出代码之后才发现flann指南的开头就有一段现成的示例。。。。不过多看文档有助于理解代码，还是学到了很多东西的。