EuclideanClusterExtraction这个名字起的很奇怪，欧式距离聚类这个该如何理解？欧式距离只是一种距离测度的方法呀！有了一个Cluster在里面，我以为是某一种聚类算法，层次聚类？k-NN聚类？K-Means？还是模糊聚类？感觉很奇怪，看下代码吧。

找一个实例cluster_extraction.cpp的main入口函数。

找到computer函数，该方法中定义了一个pcl::EuclideanClusterExtraction<pcl::PointXYZ> ec;对象，接着就是参数赋值。

具体的算法执行在ec.extract (cluster_indices)中。因此进入EuclideanClusterExtraction查看具体的方法。

1 void compute (const pcl::PCLPointCloud2::ConstPtr &input, std::vector
     
       &output, 2          int min, int max, double tolerance) 3 { 4   // Convert data to PointCloud
      
        5   PointCloud
       
        ::Ptr xyz (new PointCloud
        
         ); 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 search method of the extraction15   pcl::search::KdTree
         
          ::Ptr tree (new pcl::search::KdTree
          
           );16 tree->setInputCloud (xyz);17 18 std::vector
           
             cluster_indices;19 pcl::EuclideanClusterExtraction
            
              ec;20 ec.setClusterTolerance (tolerance);21 ec.setMinClusterSize (min);22 ec.setMaxClusterSize (max);23 ec.setSearchMethod (tree);24 ec.setInputCloud (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 output.reserve (cluster_indices.size ());30 for (std::vector
             
              ::const_iterator it = cluster_indices.begin (); it != cluster_indices.end (); ++it)31 {32 pcl::ExtractIndices
              
                extract;33 extract.setInputCloud (input);34 extract.setIndices (boost::make_shared
               
                 (*it));35 pcl::PCLPointCloud2::Ptr out (new pcl::PCLPointCloud2);36 extract.filter (*out);37 output.push_back (out);38 }39 }
               
              
             
            
           
          
         
        
       
      
     

可以在pcl_segmentation项目下的extract_clusters.h文件中查看EuclideanClusterExtraction的定义，可知这是一个模板类。

 template <typename PointT> 2 class EuclideanClusterExtraction: public PCLBase<PointT> 

实现文件在项目下的extract_clusters.hpp中，（还有一个extract_clusters.cpp文件），查看其中的extract方法：

1 template 
     
       void pcl::EuclideanClusterExtraction
      
       ::extract (std::vector
       
         &clusters) 2 { 3   if (!initCompute () ||  4       (input_ != 0   && input_->points.empty ()) || 5       (indices_ != 0 && indices_->empty ())) 6   { 7     clusters.clear (); 8     return; 9   }10 11   // Initialize the spatial locator12   if (!tree_)13   {14     if (input_->isOrganized ())15       tree_.reset (new pcl::search::OrganizedNeighbor
        
          ());16     else17       tree_.reset (new pcl::search::KdTree
         
           (false));18   }19 20   // Send the input dataset to the spatial locator21   tree_->setInputCloud (input_, indices_);22   extractEuclideanClusters (*input_, *indices_, tree_, static_cast
          
            (cluster_tolerance_), clusters, min_pts_per_cluster_, max_pts_per_cluster_);23 24 //tree_->setInputCloud (input_);25 //extractEuclideanClusters (*input_, tree_, cluster_tolerance_, clusters, min_pts_per_cluster_, max_pts_per_cluster_);26 27 // Sort the clusters based on their size (largest one first)28 std::sort (clusters.rbegin (), clusters.rend (), comparePointClusters);29 30 deinitCompute ();31 }
          
         
        
       
      
     

 注意在extract_clusters.h中定义了四个

1  template 
     
       void 2   extractEuclideanClusters (3       const PointCloud
      
        &cloud, const boost::shared_ptr
       
        
          > &tree, 4       float tolerance, std::vector
         
           &clusters, 5       unsigned int min_pts_per_cluster = 1, unsigned int max_pts_per_cluster = (std::numeric_limits
          
           ::max) ());
          
         
        
       
      
     

1 template 
     
       void 2   extractEuclideanClusters (3       const PointCloud
      
        &cloud, const std::vector
       
         &indices, 4       const boost::shared_ptr
        
         
           > &tree, float tolerance, std::vector
          
            &clusters, 5 unsigned int min_pts_per_cluster = 1, unsigned int max_pts_per_cluster = (std::numeric_limits
           
            ::max) ());
           
          
         
        
       
      
     

1  template 
     
       void 2   extractEuclideanClusters (3       const PointCloud
      
        &cloud, const PointCloud
       
         &normals, 4       float tolerance, const boost::shared_ptr
        
         
           > &tree, 5       std::vector
          
            &clusters, double eps_angle, 6 unsigned int min_pts_per_cluster = 1, 7 unsigned int max_pts_per_cluster = (std::numeric_limits
           
            ::max) ())
           
          
         
        
       
      
     

1  template 
     
       2   void extractEuclideanClusters (3       const PointCloud
      
        &cloud, const PointCloud
       
         &normals, 4       const std::vector
        
          &indices, const boost::shared_ptr
         
          
            > &tree, 5 float tolerance, std::vector
           
             &clusters, double eps_angle, 6 unsigned int min_pts_per_cluster = 1, 7 unsigned int max_pts_per_cluster = (std::numeric_limits
            
             ::max) ())
            
           
          
         
        
       
      
     

前两个的方法实现在文件extract_clusters.hpp中，后两个直接在头文件中就以内联函数的形式实现了，两个大同小异。择其中第一个加点注释，发现其实是采用的区域生长算法实现的分割。理解错误了，区域生长需要种子点，这里应该叫层次聚类方法。

1  template 
     
       void  2   extractEuclideanClusters ( 3       const PointCloud
      
        &cloud, const PointCloud
       
         &normals,  4       float tolerance, const boost::shared_ptr
        
         
           > &tree,  5       std::vector
          
            &clusters, double eps_angle, 6 unsigned int min_pts_per_cluster = 1, 7 unsigned int max_pts_per_cluster = (std::numeric_limits
           
            ::max) ()) 8 { 9 if (tree->getInputCloud ()->points.size () != cloud.points.size ())10 {11 PCL_ERROR ("[pcl::extractEuclideanClusters] Tree built for a different point cloud dataset (%lu) than the input cloud (%lu)!\n", tree->getInputCloud ()->points.size (), cloud.points.size ());12 return;13 }14 if (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 ());17 return;18 }19 20 // Create a bool vector of processed point indices, and initialize it to false21 std::vector
            
              processed (cloud.points.size (), false);22 23 std::vector
             
               nn_indices;24 std::vector
              
                nn_distances;25 // Process all points in the indices vector26 for (size_t i = 0; i < cloud.points.size (); ++i)//遍历点云中的每一个点27 {28 if (processed[i])//如果该点已经处理则跳过29 continue;30 31 std::vector
               
                 seed_queue;//定义一个种子队列32 int sq_idx = 0;33 seed_queue.push_back (static_cast
                
                  (i));//加入一个种子34 35 processed[i] = true;36 37 while (sq_idx < static_cast
                 
                   (seed_queue.size ()))//遍历每一个种子38 {39 // Search for sq_idx40 if (!tree->radiusSearch (seed_queue[sq_idx], tolerance, nn_indices, nn_distances))//没找到近邻点就继续41 {42 sq_idx++;43 continue;44 }45 46 for (size_t j = 1; j < nn_indices.size (); ++j) // nn_indices[0] should be sq_idx47 {48 if (processed[nn_indices[j]]) // Has this point been processed before ?种子点的近邻点中如果已经处理就跳出此次循环继续49 continue;50 51 //processed[nn_indices[j]] = true;52 // [-1;1]53 double 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];56 if ( fabs (acos (dot_p)) < eps_angle ) //根据内积求夹角，法向量都是单位向量，种子点和近邻点的法向量夹角小于阈值，57 {58 processed[nn_indices[j]] = true;59 seed_queue.push_back (nn_indices[j]);//将此种子点的临近点作为新的种子点。60 }61 }62 63 sq_idx++;64 }65 66 // If this queue is satisfactory, add to the clusters67 if (seed_queue.size () >= min_pts_per_cluster && seed_queue.size () <= max_pts_per_cluster)68 {69 pcl::PointIndices r;70 r.indices.resize (seed_queue.size ());71 for (size_t j = 0; j < seed_queue.size (); ++j)72 r.indices[j] = seed_queue[j];73 74 // These two lines should not be needed: (can anyone confirm?) -FF75 std::sort (r.indices.begin (), r.indices.end ());76 r.indices.erase (std::unique (r.indices.begin (), r.indices.end ()), r.indices.end ());77 78 r.header = cloud.header;79 clusters.push_back (r); // We could avoid a copy by working directly in the vector80 }81 }82 }