基于Min-Cut点云分割
一、基于Min-Cut的点云分割
在本节中，我们将学习如何使用在pcl::MinCutSegmentation类中实现的基于min-cut的分割算法。该算法对给定的输入点云进行二值分割。根据对象的中心及其半径，算法将云分为两组:前景点和背景点(属于对象的点和不属于对象的点)。
二、Min-Cut原理剖析
该算法的思想需要图论知识，如下：
1. 对于给定的点云算法，它构造了一个图，其中包含云中的每一个点作为一组顶点，以及另外两个称为源和汇聚的顶点。图中每个与该点对应的顶点都与源连接，与边连接汇聚。除此之外，每个顶点(源和汇除外)都有连接对应点与其最近邻居的边。
2. 算法为每条边分配权重。有三种不同类型的权重。让我们来研究一下
① 首先，它给点云之间的边赋予权重。这个权重被称为平滑成本，由公式计算
s
m
o
o
t
h
C
o
s
t
=
e
−
(
d
i
s
t
σ
)
2
smoothCost=e^{-(\frac{dist}{ \sigma })^2}
smoothCost=e−(σdist)2
这里的dist是点与点之间的距离。距离越远的点，边缘被切割的概率越大。
②下一步，算法设置数据开销。它由前景惩罚和背景惩罚组成。第一个是那些连接点云和源顶点的边的权值，这些边具有用户定义的常量值。第二个分配给连接点与汇聚顶点的边，并由公式计算
b
a
c
k
g
r
o
u
n
d
P
e
n
a
l
t
y
=
(
d
i
s
t
a
n
c
e
T
o
C
e
n
t
e
r
r
a
d
i
u
s
)
backgroundPenalty=(\frac{distanceToCenter}{radius})
backgroundPenalty=(radiusdistanceToCenter)
这里的distanceToCenter是物体在水平面上与期望中心的距离
d
i
s
t
a
n
c
e
T
o
C
e
n
t
e
r
=
(
x
−
c
e
n
t
e
r
X
)
2
+
(
y
−
c
e
n
t
e
r
Y
)
2
distanceToCenter=\sqrt{(x-centerX)^2+(y-centerY)^2}
distanceToCenter=(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库及其相关数学知识以备使用。谨此将自学过程与君共享。
博主才疏学浅，尚不具有指导能力，如有问题还请各位在评论处留言供大家共同讨论。