flann的接口介绍

FLANN(近似最近邻快速库)是一个用于执行快速近似最近邻搜索的库。FLANN是用c++编程语言编写的。通过库提供的C、MATLAB和Python绑定，FLANN可以在许多上下文中轻松使用。

1、flann::Index

FLANN最近邻索引类。这个类用于抽象不同类型的最近邻搜索索引。

namespace flann
{
template<typename Distance>
class Index
{
typedef typename Distance::ElementType ElementType;
typedef typename Distance::ResultType DistanceType;
public:
Index(const Matrix<ElementType>& features, const IndexParams& params);
~Index();
void buildIndex();
void knnSearch(const Matrix<ElementType>& queries,
Matrix<int>& indices,
Matrix<DistanceType>& dists,
int knn,
const SearchParams& params);
int radiusSearch(const Matrix<ElementType>& query,
Matrix<int>& indices,
Matrix<DistanceType>& dists,
float radius,
const SearchParams& params);
void save(std::string filename);
int veclen() const;
int size() const;
const IndexParams* getIndexParameters();
};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

flann::Index::Index，为给定数据集构造最近邻搜索索引。

Index(const Matrix<ElementType>& features, const IndexParams& params);
1

features：包含要索引的特征(点)的矩阵。矩阵的大小是num个特征的维度。
params：结构，其中包含索引参数。要构造的索引类型取决于此参数的类型。可能的参数类型有:
LinearIndexParams：当传递这种类型的对象时，索引将执行线性的强力搜索。

struct LinearIndexParams : public IndexParams
{
};
1
2
3

KDTreeIndexParams：当传递这种类型的对象时，构建的索引将由一组随机的kd树组成，这些树将被并行搜索。

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

trees：要使用的并行kd树的数量。好的值在[1…16]
**KMeansIndexParams：**当传递这种类型的对象时，构造的索引将是一个分层的k-means树。

struct KMeansIndexParams : public IndexParams
{
KMeansIndexParams( int branching = 32,
int iterations = 11,
flann_centers_init_t centers_init = CENTERS_RANDOM,
float cb_index = 0.2 );
};
1
2
3
4
5
6
7

branching：用于分层k-均值树的分支因子
iterations：在构建k-均值树时，在k-均值聚类阶段使用的最大迭代次数。如果这里使用的值是-1，这意味着k-means聚类应该迭代直到收敛。
centers_init：在进行k均值聚类步骤时，用于选择初始中心的算法。可能的值是CENTERS RANDOM(随机选择初始聚类中心)，CENTERS GONZALES(使用GONZALES算法选择初始中心)和CENTERS KMEANSPP(使用[AV07]中建议的算法选择初始中心)
cb_index： 这个参数(聚类边界索引)影响在分层kmeans树中执行探索的方式。当cb_index为0时，下一个要探索的kmeans域将被选择为具有最近中心的域。大于0的值也会考虑域的大小。
CompositeIndexParams：当使用这种类型的参数对象时，创建的索引结合了随机的kd树和分层的k均值树。

struct CompositeIndexParams : public IndexParams
{
CompositeIndexParams( int trees = 4,
int branching = 32,
int iterations = 11,
flann_centers_init_t centers_init = CENTERS_RANDOM,
float cb_index = 0.2 );
};
1
2
3
4
5
6
7
8

AutotunedIndexParams：当传递这种类型的对象时，创建的索引会自动调优，为提供的数据集选择最佳的索引类型(随机的kd-tree，分层的kmeans，线性)和参数，以提供最佳的性能。

struct AutotunedIndexParams : public IndexParams
{
autotunedindexparams( float target_precision = 0.9,
float build_weight = 0.01,
float memory_weight = 0,
float sample_fraction = 0.1 );
};
1
2
3
4
5
6
7

SavedIndexParams：此对象类型用于从磁盘加载以前保存的索引。

struct SavedIndexParams : public IndexParams
{
SavedIndexParams( std::string filename );
};
1
2
3
4

2、flann::Index::buildIndex

使用提供给构造函数的形参构造最近邻搜索索引(保存的索引类型除外)。

3、flann::Index::knnSearch

使用索引对给定的查询点执行k近邻搜索。

void Index::knnSearch(const Matrix<ElementType>& queries,
Matrix<int>& indices,
Matrix<DistanceType>& dists,
int knn,
const SearchParams& params);
1
2
3
4
5

query ：包含查询点的矩阵。
indices ：矩阵，它将包含找到的k个最近邻居的索引
dists：矩阵包含了到k个最近邻居的距离。。距离值由使用的距离函数计算(参见下面的flann::set distance type)，例如，在欧氏距离函数的情况下，它将包含欧氏距离的平方。
knn ：要搜索的最近邻居的数量。
params ：搜索参数。检查指定索引中的树应该递归遍历的次数。该参数的值越高，搜索精度越高，但花费的时间也越多。如果在创建索引时使用自动配置，则还会计算实现指定精度所需的检查次数，在这种情况下，该参数将被忽略。

4、flann::Index::radiusSearch

对给定的查询点执行半径最近邻搜索。

int Index::radiusSearch(const Matrix<ElementType>& query,
Matrix<int>& indices,
Matrix<DistanceType>& dists,
float radius,
const SearchParams& params);
1
2
3
4
5

参数基本与knnSearch相同，该方法返回找到的最近邻居的数量。

5、flann::Index::save

将索引保存为文件

void Index::save(std::string filename);
1

6、flann::hierarchicalClustering

通过构造一个分层k-均值树，并在树中选择一个切点，使簇的方差最小，对给定的点进行聚类。

template <typename Distance>
int hierarchicalClustering(const Matrix<typename Distance::ElementType>& features,
Matrix<typename Distance::ResultType>& centers,
const KMeansIndexParams& params,
Distance d = Distance())
1
2
3
4
5

features：要聚类的点
centers：得到的簇的中心。这个矩阵中的行数表示所需的集群数。然而，由于选择分层树中的切点的方式，计算的集群数量将是窗体中小于所需集群数量的最大数量，其中分支是树的分支因子(参见KMeansIndexParams的描述)。
params：用于构造分层k-均值树的参数
函数返回计算的集群数量。

	//头文件，main函数需要自己添加，代码可以直接放到main函数中
	pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);

	pcl::io::loadPCDFile("F:\\点云数据\\bunny.pcd", *cloud);//35947

	pcl::DefaultPointRepresentation<pcl::PointXYZ> point_representation_;

	//数组没办法使用变量初始化个数，所以需要使用动态数组
	boost::shared_array<float> cloud_((new float[cloud->points.size() * 3]));

	float* cloud_ptr = cloud_.get();
	//将数据转换为float*
	for (int cloud_index = 0; cloud_index < cloud->points.size(); ++cloud_index)
	{
		point_representation_.vectorize(cloud->points[cloud_index], cloud_ptr);
		cloud_ptr += 3;
	}
	//定义flann对象
	//flann::NNIndex>> ss;抽象类
	flann::Matrix<float> cloud_mat(cloud_.get(), cloud->size(), 3);
	//默认的索引参数为flann::KDTreeIndexParams(),有多种继承类，可以直接使用
	//flann::KDTreeIndex>> index_(cloud_mat);
	//flann::KDTreeSingleIndex>> index_(cloud_mat);

	//flann::L2_Simple dis;
	//flann::NNIndex>* nnIndex= flann::create_index_by_type(flann::FLANN_INDEX_KDTREE_SINGLE, cloud_mat, flann::KDTreeSingleIndexParams(),dis);
	
	//flann::Index>> ii(cloud_mat, flann::KDTreeSingleIndexParams(15));
	boost::shared_ptr<flann::Index<flann::L2_Simple<float>>> flann_index_(
		new flann::Index<flann::L2_Simple<float>>(cloud_mat,flann::KDTreeSingleIndexParams(15)));
	//这个参数的什么意思？
	//flann_index_->knnSearch()
	flann::SearchParams param_k_(-1, 0.0f);


	flann_index_->buildIndex();

	int k=10;
	std::vector<int> k_indices;
	std::vector<float> k_distances;
	k_indices.resize(k);
	k_distances.resize(k);

	std::vector<float> query(3);
	point_representation_.vectorize(static_cast<PointT> (cloud->points[100]), query);

	::flann::Matrix<int> k_indices_mat(&k_indices[0], 1, k);
	::flann::Matrix<float> k_distances_mat(&k_distances[0], 1, k);
	// Wrap the k_indices and k_distances vectors (no data copy)
	flann_index_->knnSearch(::flann::Matrix<float>(&query[0], 1, 3),
		k_indices_mat, k_distances_mat,
		k, param_k_);

	for (int i = 0; i < k; i++) {
		std::cout<<k_indices_mat[0][i] << std::endl;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

以上是直接使用PCL点云数据，利用flann进行最近邻搜索的代码。
参考文献：
FLANN - Fast Library for Approximate Nearest Neighbors （User Manual）