一文詳解點云分割算法

1.1基于邊緣的分割方法

1.2基于區(qū)域的分割方法

1.2.1種子區(qū)域方法

1.2.2非種子區(qū)域方法

1.2.3基于圖像區(qū)域增長方法

/* @brief:將點云轉換為vector,俯視圖柵格化

 * @param [in]: in_cloud,輸入點云
 * @param [out]: out_cloud,轉換的點云vector
 * @return NONE
   */
   void FrontLidarAlg::convetCloudToVector(pcl::PointCloud::Ptr in_cloud, \
                                       cv::Mat& out_img, \
                                       std::vector>* out_cloud)
   {
     out_img = cv::Mat::zeros(cv::Size(img_width_,img_height_), CV_8UC3);

  volatile int row;
  volatile int col;

  for(int i=0;isize();i++)
  {
    //將橫向在檢測范圍之外的去掉
    if(in_cloud->points[i].x <= cloud_x_min_ || in_cloud->points[i].x >= cloud_x_max_)
    {
      continue;
    }
    //將縱向在檢測范圍之外的去掉
    if(in_cloud->points[i].y >= cloud_y_max_ || in_cloud->points[i].y <= 0)
    {
      continue;
    }

    //限制最高和最低點大小
    if(in_cloud->points[i].z < min_dect_height_)//高度低于最低點,則賦值為最低點
    {
      in_cloud->points[i].z = min_dect_height_;
    }
    
    if(in_cloud->points[i].z > max_dect_height_)//高度高于最高點,則賦值最高點
    {
      in_cloud->points[i].z = max_dect_height_;
    }
    
    //計算點云所在圖像的行數(shù)和列數(shù),四舍五入
    col = int((in_cloud->points[i].x - cloud_x_min_)/img_res_);
    row = int(in_cloud->points[i].y/img_res_);
    out_cloud->at(col+row*img_width_).points.push_back(in_cloud->points[i]);
    
    //輸入點云高度值轉換到圖像坐標系下的數(shù)值
    int value = (int)((in_cloud->points[i].z - min_dect_height_)/dect_height_res_);
    
    if(out_img.at(row,col)[0] < value)//b-最大高度
    {
      out_img.at(row,col)[0] = value;
      if(0 == out_img.at(row,col)[1])
      {
        out_img.at(row,col)[1] = value;
      }
    }
    else if(out_img.at(row,col)[1] > value)//b-最小高度
    {
      out_img.at(row,col)[1] = value;
    }

  }//for in_cloud->size
}

#include "object_segment.h"

namespace front_lidar {

/* @brief:點云分割構造函數(shù),初始化參數(shù)

 * @param [in]: NONE
 * @param [out]: NONE
 * @return NONE
   */
   ObjectSegment::ObjectSegment(string config_file_str)
   {
     config_parser_ptr_.reset(new ConfigParser(config_file_str));

  use_seg_raw_cloud_ = config_parser_ptr_->getInt("use_seg_raw_cloud");//聚類后是否輸出原始數(shù)據(jù)
  img_res_ = config_parser_ptr_->getDouble("img_res");//圖像分辨率
  cloud_x_min_ = config_parser_ptr_->getDouble("cloud_x_min");//x軸最小值
  cloud_x_max_ = config_parser_ptr_->getDouble("cloud_x_max");//x軸最大值
  cloud_y_min_ = config_parser_ptr_->getDouble("cloud_y_min");//y軸最小值
  cloud_y_max_ = config_parser_ptr_->getDouble("cloud_y_max");//y軸最大值
  min_cluster_size_ = config_parser_ptr_->getDouble("object_detect_min_cluster_size");//最小聚類個數(shù)
  max_cluster_size_ = config_parser_ptr_->getDouble("object_detect_max_cluster_size");//最大聚類個數(shù)
  cell_size_ = config_parser_ptr_->getDouble("cell_size");//聚類臨域尺寸

  min_dect_height_ = -10;//最小檢測高度
  max_dect_height_ = 10;//最大檢測高度
  dect_height_res_ = (max_dect_height_ - min_dect_height_)/255;//檢測高度分辨率

  region_growing_clusters_.clear();
  region_growing_img_.resize(0);//區(qū)域增長后的圖像

}

/* @brief:點云分割處理,將點云分割為不同障礙物點云

  * @param [in]: in_img,輸入圖像柵格, in_vector-輸入柵格化的點云
  * @param [out]: cloud_clusters_ptr,輸出聚類結果
  * @return NONE
    */
    void ObjectSegment::process(const std::vector>* in_vector, \
                          const cv::Mat& in_img, \
                          std::vector::Ptr>* cloud_clusters_ptr)
    {
      cloud_clusters_ptr->clear();

  cluster_num_ = 0;

  //區(qū)域增長,圖像聚類分割
  pcl::StopWatch regin_grow_timer;
  reginGrowing(in_img, region_growing_img_);
  LOG_Debug()<<"regin_grow time:"<
  //將圖像轉換為點云
  pcl::StopWatch vector_to_cloud_timer;
  if(1 == use_seg_raw_cloud_)
  {
    convetVectorToCloud(in_vector, region_growing_img_, ®ion_growing_clusters_);
  }
  else
  {
    convetImageToCloud(region_growing_img_, ®ion_growing_clusters_);
  }
  LOG_Debug()<<"vector_to_cloud time:"<
  //濾除聚類點數(shù)少于設定閾值的類別
  pcl::StopWatch filter_timer;
  filterObjectsCloud(region_growing_clusters_, cloud_clusters_ptr);
  LOG_Debug()<<"filter time:"<
}


/* @brief:區(qū)域增長,8鄰域聚類

 * @param [in]: in_img-輸入圖像
 * @param [out]: out_img,轉換的圖像,0-b-最大值,1-g-最小值,2-r-有無聚類標志(0-未聚類,1-255-已聚類ID)
 * @return NONE
   */
   void ObjectSegment::reginGrowing(const cv::Mat &in_img, cv::Mat &out_img)
   {
     unsigned short class_id = 0;
     unsigned short element_class_id = 0;
     out_img = in_img.clone();

  for(int row = 1; row < out_img.rows -1; row++)
  {
    for(int col = 1; col < out_img.cols - 1; col++)
    {
      //像素的高度最大值為0,則該像素為空,無效像素
      if(0 == out_img.at(row,col)[0])
      {
        continue;
      }
      //像素的類別標記為空,即為未標記類別的像素,則分配類別ID
      if(0 == out_img.at(row,col)[2])
      {
        if(class_id > 250)//超出限定類別總數(shù),則返回
        {
          return;
        }
        out_img.at(row,col)[2] = ++class_id;//給該像素賦值類別ID
      }
      element_class_id = out_img.at(row,col)[2];
      //根據(jù)輸入種子像素,遞歸區(qū)域增長
      elementReginGrowing(out_img, row, col, element_class_id);
    }//col
  }//row
  cluster_num_ = class_id;
}

/* @brief:單個元素區(qū)域增長,cell_size_鄰域聚類

 * @param [in]: 輸入圖像-in_img,當前元素的r和c,輸出圖像-in_img
 * @param [out]: out_img,轉換的圖像,0-b-最大值,1-g-最小值,2-r-有無聚類標志(0-未聚類,1-255-聚類ID)
 * @return NONE
   */
   void ObjectSegment::elementReginGrowing(cv::Mat &in_img, int row, int col, unsigned short class_id)
   {
     int start_row;//起始行
     int end_row;//截止行

  int start_col;//起始列
  int end_col;//截止列

  //判斷起始行 截止行 起始列 截止列,防止越界
  start_row = row - cell_size_;
  end_row = row + cell_size_;
  start_col = col - cell_size_;
  end_col = col + cell_size_;

  if(start_row < 0) 
    start_row = 0;
  if(end_row > in_img.rows - 1)
    end_row = in_img.rows - 1;
  if(start_col < 0)
    start_col = 0;
  if(end_col > in_img.cols - 1)
    end_col = in_img.cols - 1; 

  for(int m = start_row; m <= end_row; m++)
  {
    for(int n = start_col; n <= end_col; n++)
    {
      //該像素對應最大高度為0,則為無效像素
      if(0 == in_img.at(m,n)[0])
      {
         continue;
      }
      //該元素為初始輸入,已經(jīng)標記過
      if(m==row && n==col)
      {
        continue;
      }
      //未標記過的元素,標記該元素,以該元素為種子,進行區(qū)域增長
      if(0 == in_img.at(m,n)[2])
      {
         in_img.at(m,n)[2] = class_id;//標記元素
         elementReginGrowing(in_img, m, n, class_id);//以該元素為初始值,進行區(qū)域增長
      }
    }//for col
  }//for row
}

/* @brief:將vector轉化為聚類結果,2D到3D

 * @param [in]: in_img,輸入的柵格圖像
 * @param [out]: out_cloud_ptr,轉換的聚類結果
 * @return NONE
   */
   void ObjectSegment::convetImageToCloud(const cv::Mat& in_img, \
                                     std::vector::Ptr>* out_cloud_ptr)
   {
     out_cloud_ptr->clear();
     pcl::PointXYZI point;
     int class_id = 0;//類ID,1開始遞增

  //根據(jù)類別分配向量空間
  out_cloud_ptr->resize(cluster_num_);//擴充輸出向量大小
  //分配點云空間
  for(int i=0;i  {
    out_cloud_ptr->at(i).reset(new pcl::PointCloud);
  }
  //將圖像轉換為點云
  for(int row=0;row  {
    for(int col=0;col    {
      //如果分類標記為0,則為無效數(shù)據(jù)
      if(0 == in_img.at(row,col)[2])
      {
        continue;
      }

      class_id = in_img.at(row,col)[2];//獲取該區(qū)域的類別ID
      
      //圖像坐標轉換為點云坐標
      point.x = (col+0.5)*img_res_ + cloud_x_min_;
      point.y = (row+0.5)*img_res_;
    
      //點云坐標高度最大值
      point.z = in_img.at(row,col)[0]*dect_height_res_ + min_dect_height_;
      out_cloud_ptr->at(class_id-1)->points.push_back(point);
    
      //點云坐標高度最小值
      point.z = in_img.at(row,col)[1]*dect_height_res_ + min_dect_height_;
      out_cloud_ptr->at(class_id-1)->points.push_back(point);
    }

  }
}

/* @brief:將vector轉化為聚類結果,2D到3D

 * @param [in]: in_vector,輸入的柵格化后點云，in_img,輸入的聚類標志位的圖像
 * @param [out]: out_cloud_ptr,轉換的聚類結果
 * @return NONE
   */
   void ObjectSegment::convetVectorToCloud(const std::vector>* in_vector, \
                                       const cv::Mat& in_img, \
                                       std::vector::Ptr>* out_cloud_ptr)
   {
     out_cloud_ptr->clear();

  int class_id = 0;//類ID,1開始遞增

  //根據(jù)類別分配向量空間
  out_cloud_ptr->resize(cluster_num_);//擴充輸出向量大小
  //分配點云空間
  for(int i=0;i  {
    out_cloud_ptr->at(i).reset(new pcl::PointCloud);
  }
  //將圖像轉換為點云
  for(int row=0;row  {
    for(int col=0;col    {
      //如果分類標記為0,則為無效數(shù)據(jù)
      if(0 == in_img.at(row,col)[2])
      {
        continue;
      }

      class_id = in_img.at(row,col)[2];//獲取該區(qū)域的類別ID
      
      int count = in_vector->at(col+row*in_img.cols).points.size();
      if(count > 25)
        count = 25;
    
      for(int j = 0; j < count; j++)
      {
        out_cloud_ptr->at(class_id-1)->points.push_back(in_vector->at(col+row*in_img.cols).points[j]);
      }
    }

  }
}

/* @brief:濾除聚類后點云數(shù)量小于設定值的類別

 * @param [in]: in_objects_cloud-聚類后的目標點云
 * @param [out]: out_objects_cloud_ptr-濾除類別中點數(shù)量少于設定閾值的類別
 * @return NONE
   */
   void ObjectSegment::filterObjectsCloud(const std::vector::Ptr> in_objects_cloud, \
                                         std::vector::Ptr> *out_objects_cloud_ptr)
   {
     out_objects_cloud_ptr->clear();

  for(int i=0;i  {
    if(in_objects_cloud[i]->size() < min_cluster_size_)
    {
      continue;
    }

    out_objects_cloud_ptr->push_back(in_objects_cloud[i]);

  }
}

}//namespace front_lidar

1.2.4基于點云區(qū)域增長方法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

int
main (int argc, char** argv)
{ 
  //點云的類型
  pcl::PointCloud::Ptr cloud (new pcl::PointCloud);
  //打開點云
  if ( pcl::io::loadPCDFile  ("region_growing_tutorial.pcd", *cloud) == -1)
  {
    std::cout << "Cloud reading failed." << std::endl;
    return (-1);
  }
 //設置搜索的方式或者說是結構
  pcl::search::Search::Ptr tree = boost::shared_ptr > (new pcl::search::KdTree);
   //求法線
  pcl::PointCloud ::Ptr normals (new pcl::PointCloud );
  pcl::NormalEstimation normal_estimator;
  normal_estimator.setSearchMethod (tree);
  normal_estimator.setInputCloud (cloud);
  normal_estimator.setKSearch (50);
  normal_estimator.compute (*normals);
   //直通濾波在Z軸的0到1米之間
  pcl::IndicesPtr indices (new std::vector );
  pcl::PassThrough pass;
  pass.setInputCloud (cloud);
  pass.setFilterFieldName ("z");
  pass.setFilterLimits (0.0, 1.0);
  pass.filter (*indices);
  //聚類對象<點，法線>
  pcl::RegionGrowing reg;
  reg.setMinClusterSize (50);  //最小的聚類的點數(shù)
  reg.setMaxClusterSize (1000000);  //最大的
  reg.setSearchMethod (tree);    //搜索方式
  reg.setNumberOfNeighbours (30);    //設置搜索的鄰域點的個數(shù)
  reg.setInputCloud (cloud);         //輸入點
  //reg.setIndices (indices);
  reg.setInputNormals (normals);     //輸入的法線
  reg.setSmoothnessThreshold (3.0 / 180.0 * M_PI);  //設置平滑度
  reg.setCurvatureThreshold (1.0);     //設置曲率的閥值

  std::vector  clusters;
  reg.extract (clusters);

  std::cout << "Number of clusters is equal to " << clusters.size () << std::endl;
  std::cout << "First cluster has " << clusters[0].indices.size () << " points." << endl;
  std::cout << "These are the indices of the points of the initial" <<
    std::endl << "cloud that belong to the first cluster:" << std::endl;
 
 int counter = 0;
  while (counter < clusters[0].indices.size ())
  {
    std::cout << clusters[0].indices[counter] << ", ";
    counter++;
    if (counter % 10 == 0)
      std::cout << std::endl;
  }
  std::cout << std::endl;
  
  //可視化聚類的結果
  pcl::PointCloud ::Ptr colored_cloud = reg.getColoredCloud ();
  pcl::visualization::CloudViewer viewer ("Cluster viewer");
  viewer.showCloud(colored_cloud);
  while (!viewer.wasStopped ())
  {
  }

  return (0);
}

1.2.5基于顏色區(qū)域增長方法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

int
main (int argc, char** argv)
{
  pcl::search::Search ::Ptr tree = boost::shared_ptr > (new pcl::search::KdTree);

  pcl::PointCloud ::Ptr cloud (new pcl::PointCloud );
  if ( pcl::io::loadPCDFile  ("region_growing_rgb_tutorial.pcd", *cloud) == -1 )
  {
    std::cout << "Cloud reading failed." << std::endl;
    return (-1);
  }
  //存儲點云的容器
  pcl::IndicesPtr indices (new std::vector );
  //濾波
  pcl::PassThrough pass;
  pass.setInputCloud (cloud);
  pass.setFilterFieldName ("z");
  pass.setFilterLimits (0.0, 1.0);
  pass.filter (*indices);
  
 //基于顏色的區(qū)域生成的對象
  pcl::RegionGrowingRGB reg;
  reg.setInputCloud (cloud);
  reg.setIndices (indices);   //點云的索引
  reg.setSearchMethod (tree);
  reg.setDistanceThreshold (10);  //距離的閥值
  reg.setPointColorThreshold (6);  //點與點之間顏色容差
  reg.setRegionColorThreshold (5);  //區(qū)域之間容差
  reg.setMinClusterSize (600);       //設置聚類的大小

  std::vector  clusters;
  reg.extract (clusters);

  pcl::PointCloud ::Ptr colored_cloud = reg.getColoredCloud ();
  pcl::visualization::CloudViewer viewer ("Cluster viewer");
  viewer.showCloud (colored_cloud);
  while (!viewer.wasStopped ())
  {
    boost::this_thread::sleep (boost::posix_time::microseconds (100));
  }

  return (0);
}

1.3基于屬性的分割方法

1.3.1歐式聚類

pcl::extractEuclideanClusters (const PointCloud &cloud,
                               const typename search::Search::Ptr &tree,
                               float tolerance, std::vector &clusters,
                               unsigned int min_pts_per_cluster,
                               unsigned int max_pts_per_cluster)
{
  if (tree->getInputCloud ()->points.size () != cloud.points.size ())   // 點數(shù)量檢查
  {
    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 ());
    return;
  }
  // Check if the tree is sorted -- if it is we don't need to check the first element
  int nn_start_idx = tree->getSortedResults () ? 1 : 0;
  // Create a bool vector of processed point indices, and initialize it to false
  std::vector processed (cloud.points.size (), false);
  std::vector nn_indices;
  std::vector nn_distances;   // 定義需要的變量


  // Process all points in the indices vector
  for (int i = 0; i < static_cast (cloud.points.size ()); ++i)   //遍歷點云中的每一個點
  {
    if (processed[i])   //如果該點已經(jīng)處理則跳過
      continue;

    std::vector seed_queue;   //定義一個種子隊列

    int sq_idx = 0;
    seed_queue.push_back (i);  //加入一個種子


    processed[i] = true;

    while (sq_idx < static_cast (seed_queue.size ()))    //遍歷每一個種子
    {
      // Search for sq_idx  kdtree 樹的近鄰搜索
      if (!tree->radiusSearch (seed_queue[sq_idx], tolerance, nn_indices, nn_distances))  
      {
        sq_idx++;
        continue;   //沒找到近鄰點就繼續(xù)
      }

      for (size_t j = nn_start_idx; j < nn_indices.size (); ++j)             // can't assume sorted (default isn't!)
      {
        if (nn_indices[j] == -1 || processed[nn_indices[j]])        // Has this point been processed before ?
          continue;   // 種子點的近鄰點中如果已經(jīng)處理就跳出此次循環(huán)繼續(xù)

        // Perform a simple Euclidean clustering
        seed_queue.push_back (nn_indices[j]);   //將此種子點的臨近點作為新的種子點。入隊操作
        processed[nn_indices[j]] = true;  // 該點已經(jīng)處理，打標簽
      }

      sq_idx++;
    }

    // If this queue is satisfactory, add to the clusters    最大點數(shù)和最小點數(shù)的類過濾
    if (seed_queue.size () >= min_pts_per_cluster && seed_queue.size () <= max_pts_per_cluster)
    {
      pcl::PointIndices r;
      r.indices.resize (seed_queue.size ());
      for (size_t j = 0; j < seed_queue.size (); ++j)
        r.indices[j] = seed_queue[j];

      // These two lines should not be needed: (can anyone confirm?) -FF
      std::sort (r.indices.begin (), r.indices.end ());
      r.indices.erase (std::unique (r.indices.begin (), r.indices.end ()), r.indices.end ());

      r.header = cloud.header;
      clusters.push_back (r);   // We could avoid a copy by working directly in the vector
    }
  }
}

// Creating the KdTree object for the search method of the extraction
  pcl::search::KdTree::Ptr tree (new pcl::search::KdTree);
  tree->setInputCloud (cloud_filtered);
 
  std::vector cluster_indices;
  pcl::EuclideanClusterExtraction ec;
  ec.setClusterTolerance (0.02); //設置近鄰搜索的搜索半徑為2cm
  ec.setMinClusterSize (100);    //設置一個聚類需要的最少點數(shù)目為100
  ec.setMaxClusterSize (25000);  //設置一個聚類需要的最大點數(shù)目為25000
  ec.setSearchMethod (tree);     //設置點云的搜索機制
  ec.setInputCloud (cloud_filtered); //設置原始點云 
  ec.extract (cluster_indices);  //從點云中提取聚類
 
                                 // 可視化部分
  pcl::visualization::PCLVisualizer viewer("segmention");
  // 我們將要使用的顏色
  float bckgr_gray_level = 0.0;  // 黑色
  float txt_gray_lvl = 1.0 - bckgr_gray_level;
  int num = cluster_indices.size();
 
  int j = 0;
  for (std::vector::const_iterator it = cluster_indices.begin (); it != cluster_indices.end (); ++it)
  {
    pcl::PointCloud::Ptr cloud_cluster (new pcl::PointCloud);
    for (std::vector::const_iterator pit = it->indices.begin (); pit != it->indices.end (); pit++)
      cloud_cluster->points.push_back (cloud_filtered->points[*pit]); //*
    cloud_cluster->width = cloud_cluster->points.size ();
    cloud_cluster->height = 1;
    cloud_cluster->is_dense = true;
 
    std::cout << "PointCloud representing the Cluster: " << cloud_cluster->points.size () << " data points." << std::endl;
    std::stringstream ss;
    ss << "cloud_cluster_" << j << ".pcd";
    writer.write (ss.str (), *cloud_cluster, false); //*
 
    pcl::visualization::PointCloudColorHandlerCustom cloud_in_color_h(cloud,
        color_bar[j][0],
        color_bar[j][1],
        color_bar[j][2]);//賦予顯示點云的顏色
    viewer.addPointCloud(cloud_cluster, cloud_in_color_h, std::to_string(j));
 
    j++;
  }

1.3.2條件歐式聚類

#include 
#include 

#include 

// 如果這個函數(shù)返回的是真，這這個候選點將會被加入聚類中
bool
customCondition(const pcl::PointXYZ& seedPoint, const pcl::PointXYZ& candidatePoint, float squaredDistance)
{
    // Do whatever you want here.做你想做的條件的篩選
    if (candidatePoint.y < seedPoint.y)  //如果候選點的Y的值小于種子點的Y值（就是之前被選擇為聚類的點），則不滿足條件，返回假
        return false;

    return true;
}

int
main(int argc, char** argv)
{
    pcl::PointCloud::Ptr cloud(new pcl::PointCloud);

    if (pcl::io::loadPCDFile(argv[1], *cloud) != 0)
    {
        return -1;
    }

    pcl::ConditionalEuclideanClustering clustering;
    clustering.setClusterTolerance(0.02);
    clustering.setMinClusterSize(100);
    clustering.setMaxClusterSize(25000);
    clustering.setInputCloud(cloud);
        //設置每次檢測一對點云時的函數(shù)
    clustering.setConditionFunction(&customCondition);
    std::vector clusters;
    clustering.segment(clusters);

    int currentClusterNum = 1;
    for (std::vector::const_iterator i = clusters.begin(); i != clusters.end(); ++i)
    {
        pcl::PointCloud::Ptr cluster(new pcl::PointCloud);
        for (std::vector::const_iterator point = i->indices.begin(); point != i->indices.end(); point++)
            cluster->points.push_back(cloud->points[*point]);
        cluster->width = cluster->points.size();
        cluster->height = 1;
        cluster->is_dense = true;

        if (cluster->points.size() <= 0)
            break;
        std::cout << "Cluster " << currentClusterNum << " has " << cluster->points.size() << " points." << std::endl;
        std::string fileName = "cluster" + boost::to_string(currentClusterNum) + ".pcd";
        pcl::io::savePCDFileASCII(fileName, *cluster);

        currentClusterNum++;
    }
}

1.3.3密度聚類

#ifndef DBSCAN_H
#define DBSCAN_H

#include 

#define UN_PROCESSED 0
#define PROCESSING 1
#define PROCESSED 2

inline bool comparePointClusters (const pcl::PointIndices &a, const pcl::PointIndices &b) {
    return (a.indices.size () < b.indices.size ());
}

template 
class DBSCANSimpleCluster {
public:
    typedef typename pcl::PointCloud::Ptr PointCloudPtr;
    typedef typename pcl::search::KdTree::Ptr KdTreePtr;
    
    virtual void setInputCloud(PointCloudPtr cloud) {
        input_cloud_ = cloud;
    }

    void setSearchMethod(KdTreePtr tree) {
        search_method_ = tree;
    }

    void extract(std::vector& cluster_indices) {
        std::vector nn_indices;
        std::vector nn_distances;
        std::vector is_noise(input_cloud_->points.size(), false);
        std::vector types(input_cloud_->points.size(), UN_PROCESSED);
        for (int i = 0; i < input_cloud_->points.size(); i++) {
            if (types[i] == PROCESSED) {
                continue;
            }
            int nn_size = radiusSearch(i, eps_, nn_indices, nn_distances);
            if (nn_size < minPts_) {
                is_noise[i] = true;
                continue;
            }
            std::vector seed_queue;
            seed_queue.push_back(i);
            types[i] = PROCESSED;
            for (int j = 0; j < nn_size; j++) {
                if (nn_indices[j] != i) {
                    seed_queue.push_back(nn_indices[j]);
                    types[nn_indices[j]] = PROCESSING;
                }
            } // for every point near the chosen core point.
            int sq_idx = 1;
            while (sq_idx < seed_queue.size()) {
                int cloud_index = seed_queue[sq_idx];
                if (is_noise[cloud_index] || types[cloud_index] == PROCESSED) {
                    // seed_queue.push_back(cloud_index);
                    types[cloud_index] = PROCESSED;
                    sq_idx++;
                    continue; // no need to check neighbors.
                }
                nn_size = radiusSearch(cloud_index, eps_, nn_indices, nn_distances);
                if (nn_size >= minPts_) {
                    for (int j = 0; j < nn_size; j++) {
                        if (types[nn_indices[j]] == UN_PROCESSED) {
                            
                            seed_queue.push_back(nn_indices[j]);
                            types[nn_indices[j]] = PROCESSING;
                        }
                    }
                }
                types[cloud_index] = PROCESSED;
                sq_idx++;
            }
            if (seed_queue.size() >= min_pts_per_cluster_ && seed_queue.size () <= max_pts_per_cluster_) {
                pcl::PointIndices r;
                r.indices.resize(seed_queue.size());
                for (int j = 0; j < seed_queue.size(); ++j) {
                    r.indices[j] = seed_queue[j];
                }
                // These two lines should not be needed: (can anyone confirm?) -FF
                std::sort (r.indices.begin (), r.indices.end ());
                r.indices.erase (std::unique (r.indices.begin (), r.indices.end ()), r.indices.end ());

                r.header = input_cloud_->header;
                cluster_indices.push_back (r);   // We could avoid a copy by working directly in the vector
            }
        } // for every point in input cloud
        std::sort (cluster_indices.rbegin (), cluster_indices.rend (), comparePointClusters);
    }

    void setClusterTolerance(double tolerance) {
        eps_ = tolerance; 
    }

    void setMinClusterSize (int min_cluster_size) { 
        min_pts_per_cluster_ = min_cluster_size; 
    }

    void setMaxClusterSize (int max_cluster_size) { 
        max_pts_per_cluster_ = max_cluster_size; 
    }
    
    void setCorePointMinPts(int core_point_min_pts) {
        minPts_ = core_point_min_pts;
    }

protected:
    PointCloudPtr input_cloud_;
    double eps_ {0.0};
    int minPts_ {1}; // not including the point itself.
    int min_pts_per_cluster_ {1};
    int max_pts_per_cluster_ {std::numeric_limits::max()};
    KdTreePtr search_method_;

    virtual int radiusSearch(
        int index, double radius, std::vector &k_indices,
        std::vector &k_sqr_distances) const
    {
        return this->search_method_->radiusSearch(index, radius, k_indices, k_sqr_distances);
    }
}; // class DBSCANCluster

#endif // DBSCAN_H

pcl::search::KdTree::Ptr tree(new pcl::search::KdTree);    
tree->setInputCloud(point_cloud_input);    
std::vector cluster_indices;   

DBSCANKdtreeCluster ec;    
ec.setCorePointMinPts(20);     
ec.setClusterTolerance(0.05);    
ec.setMinClusterSize(100);    
ec.setMaxClusterSize(25000);    
ec.setSearchMethod(tree);    
ec.setInputCloud(point_cloud_input);    
ec.extract(cluster_indices);

1.4基于模型的分割方法

1.5基于圖割的分割方法

1.6關于pcl中提供的關于點云分割的模塊

1.6.1最小分割算法

//生成分割器
pcl::MinCutSegmentation seg;
//分割輸入分割目標
seg.setInputCloud(cloud);
//指定打擊目標（目標點）
pcl::PointCloud::Ptr foreground_points(new pcl::PointCloud ());
pcl::PointXYZ point;
point.x = 68.97;
point.y = -18.55;
point.z = 0.57;
foreground_points->points.push_back(point);
seg.setForegroundPoints(foreground_points);
//指定權函數(shù)sigma
seg.setSigma(0.25);
//物體大概范圍
seg.setRadius(3.0433856);
//用多少生成圖
seg.setNumberOfNeighbours(14);
//和目標點相連點的權值(至少有14個）
seg.setSourceWeight(0.8);
//分割結果
std::vector  clusters;
seg.extract(clusters);

1.6.2超體聚類

#include 
#include 
#include 
#include 
#include 
#include 

//VTK include needed for drawing graph lines
#include 

// 數(shù)據(jù)類型
typedef pcl::PointXYZRGBA PointT;
typedef pcl::PointCloud PointCloudT;
typedef pcl::PointNormal PointNT;
typedef pcl::PointCloud PointNCloudT;
typedef pcl::PointXYZL PointLT;
typedef pcl::PointCloud PointLCloudT;

//可視化
void addSupervoxelConnectionsToViewer (PointT &supervoxel_center,
                                       PointCloudT &adjacent_supervoxel_centers,
                                       std::string supervoxel_name,
                                       boost::shared_ptr & viewer);


int
main (int argc, char ** argv)
{
//解析命令行
  if (argc < 2)
  {
    pcl::console::print_error ("Syntax is: %s  \n "
                                "--NT Dsables the single cloud transform \n"
                                "-v \n-s \n"
                                "-c  \n-z  \n"
                                "-n \n", argv[0]);
    return (1);
  }

  //打開點云
  PointCloudT::Ptr cloud = boost::shared_ptr  (new PointCloudT ());
  pcl::console::print_highlight ("Loading point cloud...\n");
  if (pcl::io::loadPCDFile (argv[1], *cloud))
  {
    pcl::console::print_error ("Error loading cloud file!\n");
    return (1);
  }


  bool disable_transform = pcl::console::find_switch (argc, argv, "--NT");

  float voxel_resolution = 0.008f;  //分辨率
  bool voxel_res_specified = pcl::console::find_switch (argc, argv, "-v");
  if (voxel_res_specified)
    pcl::console::parse (argc, argv, "-v", voxel_resolution);

  float seed_resolution = 0.1f;
  bool seed_res_specified = pcl::console::find_switch (argc, argv, "-s");
  if (seed_res_specified)
    pcl::console::parse (argc, argv, "-s", seed_resolution);

  float color_importance = 0.2f;
  if (pcl::console::find_switch (argc, argv, "-c"))
    pcl::console::parse (argc, argv, "-c", color_importance);

  float spatial_importance = 0.4f;
  if (pcl::console::find_switch (argc, argv, "-z"))
    pcl::console::parse (argc, argv, "-z", spatial_importance);

  float normal_importance = 1.0f;
  if (pcl::console::find_switch (argc, argv, "-n"))
    pcl::console::parse (argc, argv, "-n", normal_importance);

//如何使用SupervoxelClustering函數(shù)
  pcl::SupervoxelClustering super (voxel_resolution, seed_resolution);
  if (disable_transform)//如果設置的是參數(shù)--NT  就用默認的參數(shù)
  super.setUseSingleCameraTransform (false);
  super.setInputCloud (cloud);
  super.setColorImportance (color_importance); //0.2f
  super.setSpatialImportance (spatial_importance); //0.4f
  super.setNormalImportance (normal_importance); //1.0f

  std::map ::Ptr > supervoxel_clusters;

  pcl::console::print_highlight ("Extracting supervoxels!\n");
  super.extract (supervoxel_clusters);
  pcl::console::print_info ("Found %d supervoxels\n", supervoxel_clusters.size ());

  boost::shared_ptr viewer (new pcl::visualization::PCLVisualizer ("3D Viewer"));
  viewer->setBackgroundColor (0, 0, 0);

  PointCloudT::Ptr voxel_centroid_cloud = super.getVoxelCentroidCloud ();//獲得體素中心的點云
  viewer->addPointCloud (voxel_centroid_cloud, "voxel centroids");
  viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_POINT_SIZE,2.0, "voxel centroids");     //渲染點云
  viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_OPACITY,0.95, "voxel centroids");

  PointLCloudT::Ptr labeled_voxel_cloud = super.getLabeledVoxelCloud ();
  viewer->addPointCloud (labeled_voxel_cloud, "labeled voxels");
  viewer->setPointCloudRenderingProperties (pcl::visualization::PCL_VISUALIZER_OPACITY,0.8, "labeled voxels");

  PointNCloudT::Ptr sv_normal_cloud = super.makeSupervoxelNormalCloud (supervoxel_clusters);

  //We have this disabled so graph is easy to see, uncomment to see supervoxel normals
  //viewer->addPointCloudNormals (sv_normal_cloud,1,0.05f, "supervoxel_normals");

  pcl::console::print_highlight ("Getting supervoxel adjacency\n");

  std::multimap supervoxel_adjacency;
  super.getSupervoxelAdjacency (supervoxel_adjacency);
  //To make a graph of the supervoxel adjacency, we need to iterate through the supervoxel adjacency multimap
  //為了使整個超體形成衣服圖，我們需要遍歷超體的每個臨近的個體
  std::multimap::iterator label_itr = supervoxel_adjacency.begin ();
  for ( ; label_itr != supervoxel_adjacency.end (); )
  {
    //First get the label
    uint32_t supervoxel_label = label_itr->first;
    //Now get the supervoxel corresponding to the label
    pcl::Supervoxel::Ptr supervoxel = supervoxel_clusters.at (supervoxel_label);

    //Now we need to iterate through the adjacent supervoxels and make a point cloud of them
    PointCloudT adjacent_supervoxel_centers;
    std::multimap::iterator adjacent_itr = supervoxel_adjacency.equal_range (supervoxel_label).first;
    for ( ; adjacent_itr!=supervoxel_adjacency.equal_range (supervoxel_label).second; ++adjacent_itr)
    {
      pcl::Supervoxel::Ptr neighbor_supervoxel = supervoxel_clusters.at (adjacent_itr->second);
      adjacent_supervoxel_centers.push_back (neighbor_supervoxel->centroid_);
    }
    //Now we make a name for this polygon
    std::stringstream ss;
    ss << "supervoxel_" << supervoxel_label;
    //This function is shown below, but is beyond the scope of this tutorial - basically it just generates a "star" polygon mesh from the points given
//從給定的點云中生成一個星型的多邊形，
    addSupervoxelConnectionsToViewer (supervoxel->centroid_, adjacent_supervoxel_centers, ss.str (), viewer);
    //Move iterator forward to next label
    label_itr = supervoxel_adjacency.upper_bound (supervoxel_label);
  }

  while (!viewer->wasStopped ())
  {
    viewer->spinOnce (100);
  }
  return (0);
}

//VTK可視化構成的聚類圖
void
addSupervoxelConnectionsToViewer (PointT &supervoxel_center,
                                  PointCloudT &adjacent_supervoxel_centers,
                                  std::string supervoxel_name,
                                  boost::shared_ptr & viewer)
{
  vtkSmartPointer points = vtkSmartPointer::New ();
  vtkSmartPointer cells = vtkSmartPointer::New ();
  vtkSmartPointer polyLine = vtkSmartPointer::New ();

  //Iterate through all adjacent points, and add a center point to adjacent point pair
  PointCloudT::iterator adjacent_itr = adjacent_supervoxel_centers.begin ();
  for ( ; adjacent_itr != adjacent_supervoxel_centers.end (); ++adjacent_itr)
  {
    points->InsertNextPoint (supervoxel_center.data);
    points->InsertNextPoint (adjacent_itr->data);
  }
  // Create a polydata to store everything in
  vtkSmartPointer polyData = vtkSmartPointer::New ();
  // Add the points to the dataset
  polyData->SetPoints (points);
  polyLine->GetPointIds  ()->SetNumberOfIds(points->GetNumberOfPoints ());
  for(unsigned int i = 0; i < points->GetNumberOfPoints (); i++)
    polyLine->GetPointIds ()->SetId (i,i);
  cells->InsertNextCell (polyLine);
  // Add the lines to the dataset
  polyData->SetLines (cells);
  viewer->addModelFromPolyData (polyData,supervoxel_name);
}

1.6.3基于凹凸性的點云分割

1.6.3.1lccp方法

//生成LCCP分割器
pcl::LCCPSegmentation::LCCPSegmentation LCCPseg;
//輸入超體聚類結果
seg.setInputSupervoxels(supervoxel_clusters,supervoxel_adjacency);
//CC效驗beta值
seg.setConcavityToleranceThreshold (concavity_tolerance_threshold);
//CC效驗的k鄰點
seg.setKFactor (k_factor_arg)
//
seg.setSmoothnessCheck (bool_use_smoothness_check_arg,voxel_res_arg,seed_res_arg,smoothness_threshold_arg = 0.1);
//SC效驗
seg.setSanityCheck (bool_use_sanity_criterion_arg);
//最小分割尺寸
seg.setMinSegmentSize (min_segment_size_arg)

seg.segment();
seg.relabelCloud (pcl::PointCloud &labeled_cloud_arg);

1.6.3.2cpc方法

//生成CPC分割器
pcl::CPCSegmentation::CPCSegmentation seg;
//輸入超體聚類結果
seg.setInputSupervoxels(supervoxel_clusters,supervoxel_adjacency);
//設置分割參數(shù)
setCutting (max_cuts = 20,
                 cutting_min_segments = 0,
                 cutting_min_score = 0.16,
                 locally_constrained = true,
                 directed_cutting = true,
                 clean_cutting = false)；
seg.setRANSACIterations (ransac_iterations);
seg.segment();
seg.relabelCloud (pcl::PointCloud &labeled_cloud_arg);

1.6.4基于形態(tài)學的點云分割

//生成形態(tài)濾波器
  pcl::ProgressiveMorphologicalFilter pmf;
  pmf.setInputCloud (cloud);
  //設置窗的大小以及切深，斜率信息
  pmf.setMaxWindowSize (20);
  pmf.setSlope (1.0f);
  pmf.setInitialDistance (0.5f);
  pmf.setMaxDistance (3.0f);
  //提取地面
  pmf.extract (ground->indices);

  // 從標號到點云
  pcl::ExtractIndices extract;
  extract.setInputCloud (cloud);
  extract.setIndices (ground);
  extract.filter (*cloud_filtered);

1.7總結