一、基于Min-Cut的点云分割

  在本节中，我们将学习如何使用在pcl::MinCutSegmentation类中实现的基于min-cut的分割算法。该算法对给定的输入点云进行二值分割。根据对象的中心及其半径，算法将云分为两组:前景点和背景点(属于对象的点和不属于对象的点)。

二、Min-Cut原理剖析

  该算法的思想需要图论知识，如下：
  1. 对于给定的点云算法，它构造了一个图，其中包含云中的每一个点作为一组顶点，以及另外两个称为源和汇聚的顶点。图中每个与该点对应的顶点都与源连接，与边连接汇聚。除此之外，每个顶点(源和汇除外)都有连接对应点与其最近邻居的边。
  2. 算法为每条边分配权重。有三种不同类型的权重。让我们来研究一下
① 首先，它给点云之间的边赋予权重。这个权重被称为平滑成本，由公式计算

          $smoothCost=e^{-(\frac{dist}{\sigma }{)}^2}$

  这里的dist是点与点之间的距离。距离越远的点，边缘被切割的概率越大。

②下一步，算法设置数据开销。它由前景惩罚和背景惩罚组成。第一个是那些连接点云和源顶点的边的权值，这些边具有用户定义的常量值。第二个分配给连接点与汇聚顶点的边，并由公式计算

        $backgroundPenalty=(\frac{distanceToCenter}{radius})$

  这里的distanceToCenter是物体在水平面上与期望中心的距离

      $distanceToCenter=\sqrt{(x-centerX{)}^2+(y-centerY{)}^2}$
  公式中出现的半径是算法的输入参数，大致可以认为是物体中心以外没有属于前景的点的范围(物体的水平半径)。
  3. 在所有的准备工作完成后，寻找最小切口。在此基础上，对云进行前景点和背景点的划分。
具体原理可以参考这篇论文来理解。 “Min-Cut Based Segmentation of Point Clouds”.

需要说明的是：这个方法其实效果并没有论文中描述的好，而且参数比较过。适合学习思想，并不适合直接使用。

三、示例代码

#include <iostream>
#include <vector>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/filters/filter_indices.h> // for pcl::removeNaNFromPointCloud
#include <pcl/segmentation/min_cut_segmentation.h>int main ()
{
// 加载pcd文件中的点云pcl::PointCloud <pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud <pcl::PointXYZ>);if ( pcl::io::loadPCDFile <pcl::PointXYZ> ("min_cut_segmentation_tutorial.pcd", *cloud) == -1 ){std::cout << "Cloud reading failed." << std::endl;return (-1);}
// 选择有效的点进行分割pcl::IndicesPtr indices (new std::vector <int>);pcl::removeNaNFromPointCloud(*cloud, *indices);
// pcl::MinCutSegmentation模板类只有一个参数PointT，该参数表示将使用哪种类型的点。pcl::MinCutSegmentation<pcl::PointXYZ> seg;seg.setInputCloud (cloud);seg.setIndices (indices);
// 为算法提供点云中必须分割d的点和索引pcl::PointCloud<pcl::PointXYZ>::Ptr foreground_points(new pcl::PointCloud<pcl::PointXYZ> ());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);
// 如前所述，算法要求已知为物体中心的点。seg.setSigma (0.25);seg.setRadius (3.0433856);seg.setNumberOfNeighbours (14);seg.setSourceWeight (0.8);// 将分割后的点分类std::vector <pcl::PointIndices> clusters;seg.extract (clusters);std::cout << "Maximum flow is " << seg.getMaxFlow () << std::endl;// 显示点云pcl::PointCloud <pcl::PointXYZRGB>::Ptr colored_cloud = seg.getColoredCloud ();pcl::visualization::CloudViewer viewer ("Cluster viewer");viewer.showCloud(colored_cloud);while (!viewer.wasStopped ()){}return (0);
}

分割效果如下：

前辈的这篇文章对该算法做了尝试，结果显示该算法效果并不好。

【博主简介】
  斯坦福的兔子，男，天津大学工学硕士。毕业至今从事光学三维成像及点云处理相关工作。因工作中使用的三维处理库为公司内部库，不具有普遍适用性，遂自学开源PCL库及其相关数学知识以备使用。谨此将自学过程与君共享。
博主才疏学浅，尚不具有指导能力，如有问题还请各位在评论处留言供大家共同讨论。