一文详解点云分割算法

作者丨书生意封侯@知乎

来源丨https://zhuanlan.zhihu.com/p/470782623

编辑丨3D视觉工坊

从某种意义上说，地面点剔除（分割）也属于点云分割的一种，但两者技术路线有所不同，因此本节主要是针对地面点剔除后的点云分割。

传统点云分割的方式，通过查阅文档后发现网上文档大都雷同，但由于时间关系且并不是本次学习的重点，因此本次记录暂不详细探究，但对相关论文进行下载。

1.1基于边缘的分割方法

边缘是描述点云物体形状的基本特征，这种方法检测点云一些区域的边界来获取分割区域，这些方法的原理是定位出边缘点的强度变化。论文[1]提出了一种边缘检测技术，通过计算梯度，检测表面上单位法向量方向的变化来拟合线段。论文[2]是基于扫描线的分组进行快速分割。

基于边缘的方法虽然分割速度比较快但是准确度不能保证，因为边缘对于噪声和不均匀的或稀疏的点云非常敏感。

[1]Range data processing:Representation of surfaces by edges. In proc.int. Pattern recognition conf, 1995——范围数据处理：用边界表示表面

[2] Fast range image segmentation using high-level segmentation primitives, In 3rd IEEE Workshop on Applications of Computer Vision, USA, 1996——基础扫描线分组的快速分割

1.2基于区域的分割方法

基于区域的方法使用邻域信息来将具有相似属性的附近点归类，以获得到分割区域，并区分出不同区域之间的差异性。基于区域的方法比基于边缘的方法更准确。但是他们在分割过度或不足以及在如何准确确定区域边界方面存在问题。研究者们将基于区域的方法分为两类：种子区域（自下而上）方法和非种子区域（自上而下）方法。

1.2.1种子区域方法

基于种子的区域分割通过选择多个种子点来开始做分割，从这些种子点为起始点，通过添加种子的邻域点的方式逐渐形成点云区域，算法主要包含了两个步骤（论文[3]）：

（1）基于每个点的曲率识别种子点，

（2）根据预定标准，该标准可以是点的相似度和点云的表面的相似度来生长种子点。

这种方法对噪声点也非常敏感，并且耗时。但后续有很多基于这种方法的改进，比如对于激光雷达数据的区域增长的方法，提出了基于种子点的法向量和与生长平面的距离来生长种子点。种子区域方法高度依赖于选定的种子点。不准确选择种子点会影响分割过程，并可能导致分割不足或过度。选择种子点以及控制生长过程是耗时的。分割结果可能对所选的兼容性阈值敏感。另一个困难是决定是否在给定区域中添加点，因为这种方法对点云的噪声也很敏感。该方法详情由5.2.4介绍。

pcl中提供了基于欧式聚类的区域增长方式，以第一个点为标准作为种子点，候选其周边的点作为它的对比或者比较的对象，如果满足条件就加入到聚类的对象中。其主要的缺点：该算法没有初始化种子系统，没有过度分割或者分割不足的控制，还有就是从主循环运算中调用条件函数时，效率比较低。该方法详情由5.3.2介绍。

1.2.2非种子区域方法

这种方法时基于自上而下的方法。首先，所有点都分为一个区域。然后细分过程开始将其划分为更小的区域。使用这种方法（论文[4]）指导聚类平面区域的过程，以重建建筑物的完整几何形状。该工作引入了基于局部区域的置信率为平面的分割方法。这种方法的局限性在于它也会可能过度分割，并且在分割其他对象（例如树）时它不能很好地执行。非种子区域方法的主要困难是决定细分的位置和方式。这些方法的另一个限制是它们需要大量的先验知识（例如，对象模型，区域数量等），然后这些未知的先验知识在复杂场景中通常是未知的。

[3]P.J. Besl, R.C. Jain, Segmentation through variable order surface fitting, IEEE Transaction on Pattern Analysis and Machine Intelligence 10, 1988.——变阶曲面拟合分割

[4]Architectural Modeling from Sparsely Scanned Range Data——稀疏扫描范围内的建筑建模

1.2.3基于图像区域增长方法

该方法主要是通过将点云转换成二值图像，再通过图像方法中的区域增长进行聚类，再转换成点云。其优点为速度快，而缺点是存在过度分割以及分割不足。

1.将激光点云数据放入栅格中，并生成对应的深度图像，每格图像中的像素值用转换后的高度表示，分别用像素值中的r、g、b中的0-b表示高度最大值，1-g-表示高度最小值，2-r表示有无聚类的标志（0-未聚类，1-255-聚类ID）

/* @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_;
    }
    
    //计算点云所在图像的行数和列数,四舍五入
    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]);
    
    //输入点云高度值转换到图像坐标系下的数值
    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
}

2、判断图像的边界是否越界；

3、对生成的二值图像做形态学滤波操作，进行闭运算，将临近的小目标进行合并，一定程度上优化过分割；

4、采用递归的方式对图像中的任意一个像素值附近的8邻域进行标记操作，即对所有的像素对应的r值进行赋值（ID）；

5、将相同ID（r值）对应的像素和栅格内的点云取出，即可得到不同类簇的点云。

6、滤波操作，滤除点云较少的类簇。

#include "object_segment.h"

namespace front_lidar {

/* @brief:点云分割构造函数,初始化参数

 * @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");//聚类后是否输出原始数据
  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");//最小聚类个数
  max_cluster_size_ = config_parser_ptr_->getDouble("object_detect_max_cluster_size");//最大聚类个数
  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);//区域增长后的图像

}

/* @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* cloud_clusters_ptr)
    {
      cloud_clusters_ptr->clear();

  cluster_num_ = 0;

  //区域增长,图像聚类分割
  pcl::StopWatch regin_grow_timer;
  reginGrowing(in_img, region_growing_img_);
  LOG_Debug()<<"regin_grow time:"<