[PCL]3欧式距离分类EuclideanClusterExtraction EuclideanClusterExtraction这个名字起的很奇怪，欧式距离聚类这个该如何理解？欧式距离只是⼀种距离测度的⽅法呀！有了⼀个Cluster在⾥⾯，我以为是某⼀种聚类算法，层次聚类？k-NN聚类？K-Means？还是模糊聚类？感觉很奇怪，看下代码吧。
找⼀个实例cluster_extraction.cpp的main⼊⼝函数。
找到computer函数，该⽅法中定义了⼀个pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec；对象，接着就是参数赋值。
具体的算法执⾏在ec.extract (cluster_indices)中。因此进⼊EuclideanClusterExtraction查看具体的⽅法。
1void compute (const pcl::PCLPointCloud2::ConstPtr &input, std::vector<pcl::PCLPointCloud2::Ptr> &output,
2int min, int max, double tolerance)
3 {
4// Convert data to PointCloud<T>
5 PointCloud<pcl::PointXYZ>::Ptr xyz (new PointCloud<pcl::PointXYZ>);
6 fromPCLPointCloud2 (*input, *xyz);
7
8// Estimate
9 TicToc tt;
10 tt.tic ();
笔架峰11
12 print_highlight (stderr, "Computing ");
13
14// Creating the KdTree object for the arch method of the extraction
15 pcl::arch::KdTree<pcl::PointXYZ>::Ptr tree (new pcl::arch::KdTree<pcl::PointXYZ>);
16 tree->tInputCloud (xyz);
17
18 std::vector<pcl::PointIndices> cluster_indices;
19 pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec;
20 ec.tClusterTolerance (tolerance);
21 ec.tMinClusterSize (min);
22 ec.tMaxClusterSize (max);
23 ec.tSearchMethod (tree);
24 ec.tInputCloud (xyz);
25 ec.extract (cluster_indices);
26
27 print_info ("[done, "); print_value ("%g", tt.toc ()); print_info (" ms : "); print_value ("%d", cluster_indices.size ()); print_info (" clusters]\n");
28
29 ve (cluster_indices.size ());
30for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin (); it != d (); ++it)
31 {
32 pcl::ExtractIndices<pcl::PCLPointCloud2> extract;
33 extract.tInputCloud (input);
34 extract.tIndices (boost::make_shared<const pcl::PointIndices> (*it));
35 pcl::PCLPointCloud2::Ptr out (new pcl::PCLPointCloud2);
36 extract.filter (*out);
37 output.push_back (out);
38 }
39 }
可以在pcl_gmentation项⽬下的extract_clusters.h⽂件中查看EuclideanClusterExtraction的定义，可知这是⼀个模板类。
1 template <typename PointT> 2class EuclideanClusterExtraction: public PCLBa<PointT>
实现⽂件在项⽬下的extract_clusters.hpp中，（还有⼀个extract_clusters.cpp⽂件），查看其中的extract⽅法：
1 template <typename PointT> void pcl::EuclideanClusterExtraction<PointT>::extract (std::vector<PointIndices> &clusters)
2 {
3if (!initCompute () ||
4 (input_ != 0 && input_-&pty ()) ||
5 (indices_ != 0 && indices_->empty ()))
6 {
7 clusters.clear ();
8return;
9 }
10
11// Initialize the spatial locator
12if (!tree_)
13 {
14if (input_->isOrganized ())
15 tree_.ret (new pcl::arch::OrganizedNeighbor<PointT> ());
16el
17 tree_.ret (new pcl::arch::KdTree<PointT> (fal));
18 }
19
20// Send the input datat to the spatial locator
21 tree_->tInputCloud (input_, indices_);
22 extractEuclideanClusters (*input_, *indices_, tree_, static_cast<float> (cluster_tolerance_), clusters, min_pts_per_cluster_, max_pts_per_cluster_);
23
24//tree_->tInputCloud (input_);
25//extractEuclideanClusters (*input_, tree_, cluster_tolerance_, clusters, min_pts_per_cluster_, max_pts_per_cluster_);
26
27// Sort the clusters bad on their size (largest one first)
28 std::sort (clusters.rbegin (), d (), comparePointClusters);
29
30 deinitCompute ();
system权限31 }
注意在extract_clusters.h中定义了四个
1 template <typename PointT> void
2 extractEuclideanClusters (
3const PointCloud<PointT> &cloud, const boost::shared_ptr<arch::Search<PointT> > &tree,
4float tolerance, std::vector<PointIndices> &clusters,
5 unsigned int min_pts_per_cluster = 1, unsigned int max_pts_per_cluster = (std::numeric_limits<int>::max) ());
1 template <typename PointT> void
2 extractEuclideanClusters (
3const PointCloud<PointT> &cloud, const std::vector<int> &indices,
4const boost::shared_ptr<arch::Search<PointT> > &tree, float tolerance, std::vector<PointIndices> &clusters,
5 unsigned int min_pts_per_cluster = 1, unsigned int max_pts_per_cluster = (std::numeric_limits<int>::max) ());
1 template <typename PointT, typename Normal> void
2 extractEuclideanClusters (
3const PointCloud<PointT> &cloud, const PointCloud<Normal> &normals,
4float tolerance, const boost::shared_ptr<KdTree<PointT> > &tree,
5 std::vector<PointIndices> &clusters, double eps_angle,
6 unsigned int min_pts_per_cluster = 1,
7 unsigned int max_pts_per_cluster = (std::numeric_limits<int>::max) ())
1 template <typename PointT, typename Normal>
2void extractEuclideanClusters (
3const PointCloud<PointT> &cloud, const PointCloud<Normal> &normals,
4const std::vector<int> &indices, const boost::shared_ptr<KdTree<PointT> > &tree,
5float tolerance, std::vector<PointIndices> &clusters, double eps_angle,
6 unsigned int min_pts_per_cluster = 1,
处女座和什么座最配对
秋天景色的诗句7 unsigned int max_pts_per_cluster = (std::numeric_limits<int>::max) ())
前两个的⽅法实现在⽂件extract_clusters.hpp中，后两个直接在头⽂件中就以内联函数的形式实现了，两个⼤同⼩异。择其中第⼀个加点注释，发现其实是采⽤的区域⽣长算法实现的分割。理解错误了，区域⽣长需要种⼦点，这⾥应该叫层次聚类⽅法。
1 template <typename PointT, typename Normal> void
2 extractEuclideanClusters (
3const PointCloud<PointT> &cloud, const PointCloud<Normal> &normals,
4float tolerance, const boost::shared_ptr<KdTree<PointT> > &tree,
5 std::vector<PointIndices> &clusters, double eps_angle,
6 unsigned int min_pts_per_cluster = 1,
7 unsigned int max_pts_per_cluster = (std::numeric_limits<int>::max) ())
8 {
9if (tree->getInputCloud ()->points.size () != cloud.points.size ())
10 {
11 PCL_ERROR ("[pcl::extractEuclideanClusters] Tree built for a different point cloud datat (%lu) than the input cloud (%lu)!\n", tree->getInputCloud ()->points.size (), cloud.points.size ()); 12return;
豪华的近义词13 }
14if (cloud.points.size () != normals.points.size ())
15 {
16 PCL_ERROR ("[pcl::extractEuclideanClusters] Number of points in the input point cloud (%lu) different than normals (%lu)!\n", cloud.points.size (), normals.points.size ());
17return;
18 }
19
20// Create a bool vector of procesd point indices, and initialize it to fal
21 std::vector<bool> procesd (cloud.points.size (), fal);
22
23 std::vector<int> nn_indices;
24 std::vector<float> nn_distances;
25// Process all points in the indices vector
26for (size_t i = 0; i < cloud.points.size (); ++i)//遍历点云中的每⼀个点
27 {
28if (procesd[i])//如果该点已经处理则跳过
29continue;
牛奶品牌
30
31 std::vector<unsigned int> ed_queue;//定义⼀个种⼦队列
32int sq_idx = 0;
33 ed_queue.push_back (static_cast<int> (i));//加⼊⼀个种⼦
34
35 procesd[i] = true;
36
37while (sq_idx < static_cast<int> (ed_queue.size ()))//遍历每⼀个种⼦
38 {
39// Search for sq_idx
40if (!tree->radiusSearch (ed_queue[sq_idx], tolerance, nn_indices, nn_distances))//没找到近邻点就继续
41 {澳门景点排行榜前十名
42 sq_idx++;
43continue;
44 }
45
46for (size_t j = 1; j < nn_indices.size (); ++j) // nn_indices[0] should be sq_idx
47 {
48if (procesd[nn_indices[j]]) // Has this point been procesd before ?种⼦点的近邻点中如果已经处理就跳出此次循环继续
49continue;
50
51//procesd[nn_indices[j]] = true;
52// [-1;1]
53double dot_p = normals.points[i].normal[0] * normals.points[nn_indices[j]].normal[0] +
54 normals.points[i].normal[1] * normals.points[nn_indices[j]].normal[1] +
55 normals.points[i].normal[2] * normals.points[nn_indices[j]].normal[2];
治疗气喘的方法56if ( fabs (acos (dot_p)) < eps_angle ) //根据内积求夹⾓，法向量都是单位向量，种⼦点和近邻点的法向量夹⾓⼩于阈值，
57 {
58 procesd[nn_indices[j]] = true;
59 ed_queue.push_back (nn_indices[j]);//将此种⼦点的临近点作为新的种⼦点。
60 }
61 }
62
63 sq_idx++;
64 }
65
66// If this queue is satisfactory, add to the clusters
67if (ed_queue.size () >= min_pts_per_cluster && ed_queue.size () <= max_pts_per_cluster)
68 {
69 pcl::PointIndices r;
70 size (ed_queue.size ());
71for (size_t j = 0; j < ed_queue.size (); ++j)
72 r.indices[j] = ed_queue[j];
73
74// The two lines should not be needed: (can anyone confirm?) -FF
75 std::sort (r.indices.begin (), d ());
76 a (std::unique (r.indices.begin (), d ()), d ());
77
78 r.header = cloud.header;
79 clusters.push_back (r); // We could avoid a copy by working directly in the vector
80 }
81 }
82 }
