padeoe的小站

计算机图形学课两个课题之一，我的第一个选题其实就已经把第二次选题（图形分割）做完了，老师问我，那你还用第一次选题的RANSAC算法吧，结果脑子一热装了把逼“不不，我做最小割算法分割吧，学习新知识嘛”。

1.与其他分割算法的不同：

目标：不是将点云分成多个部分，而是将前景对象从背景点中分离出来

特点：

• 不关心细粒度特征例如曲率，而是只依赖点间距和点密度来分割。

• 非数据驱动的。某些算法使用特定对象实例的集合去分割新的点云中的特定对象，即数据驱动。

2.算法的直觉出发点：

一个好的分割应该包含相互连通性很好的点，而与背景点的连通性则很差。

3.最小割点云分割的算法步骤

(1)将点云构造k-临近图(KNN)。k如何取值？k越大，计算复杂度越高，精度越高

(2)根据点与点之间的距离给边赋予距离权重

权重 wi=expr(-(di/o)),即

o为点距标准差，dist(di)为点距

为何使用该公式？使用正态分布来分配距离权重

(3).用户输入对象预期参数应用于损失函数。参数包括预期的对象的中心坐标(X,Y）和范围Radius，则

(4).对图执行Min-Cut分割，分割出前景点(Foreground Point)和背景点(Background Point)。

4.PCL实现

一个例子

5.执行结果展示

KNN k=20时的分割结果

k=14时