LCCP方法和CPC方法

LCCP方法
LCCP是Locally Convex Connected Patches的缩写，翻译成中文叫做“局部凸连接打包一波带走”。算法大致可以分成两个部分：1.基于超体聚类的过分割。2.在超体聚类的基础上再聚类。超体聚类作为一种过分割方法，在理想情况下是不会引入错误信息的，也就是说适合在此基础上再进行处理。LCCP方法并不依赖于点云颜色，所以只使用空间信息和法线信息，Wc=0,Ws=1,Wn=4。
方法原理
点云完成超体聚类之后，对于过分割的点云需要计算不同的块之间凹凸关系。凹凸关系通过CC（Extented Convexity Criterion）和SC（Sanity Criterion）判据来进行判断。其中CC利用相邻两片中心连线相邻与法向量的夹角来判断两片是凹是凸。显示，如果途中a1>a1则为凹，反之为凸。

考虑到测量噪声等因素，需要在实际使用过程中引入门限值（a1需要比a2大出一定量）来滤除较小的凹凸误判。此外，为去除一些小噪声引起的误判，还需要引入“第三方验证”，如果某块和相邻两块都相交，则其凹凸关系必相同。CC判据最终如CCe:

如果相邻两面中，有一面是单独的，CC判据是无法将其分开的。举个简单的例子，两本厚度不同的书并排放置，视觉算法应该将两本书分割开。如果是台阶，则视觉算法应该将台阶作为一个整体。本质上就是因为厚度不同的书存在surface-singularities。为此需要引入SC判据，来对此进行区分。

如图所示，相邻凉面是否真正连通，是否存在单独面，与θ角有关，角越大，则凉面真的形成凸关系的可能性就越大。据此，可以设计SC判据：

其中S（向量)是两平面法向量的叉积。
最终，两相邻面之间的凸边判据为：

在标记完各个小区域的凹凸关系后，则采用基于区域增长算法将小区域聚类成较大的物体。此区域增长算法受到小区域凹凸性限制，即只允许区域跨越凸边增长。
至此，分割王城，在滤去多余噪声后既获得点云分割结果。此外：考虑到RGB-D图像随深度增加而离散，难以确实八叉树尺寸，故在z方向使用对数变换以提高精度。分割结果如图：

CPC方法的全称为Constrained Planar Cuts，出自论文Constrained Planar Cuts-Object Partitioning for Point Clouds。与LLCP方法不同，此方法的分割对象是Object。此方法能够将物体分成有意义的块：比如人的肢体等。CPC方法可作为AI的前处理，作为RobortVision还是显得有些不合适。但此方法不需要额外训练，自底向上的将三维图像分割成有明确意义部分，是非常admirable的。
方法原理
和其他基于凹凸性的方法相同，本方法也需要先进行超体聚类。在完成超体聚类之后，采用和LCCP相同的凹凸性盘踞获得各个块之间的凹凸关系。在获得凹凸性之后，CPC方法所采取的措施是不同的，其操作称为半全局分割。
在分割之前，首先需要生成EEC（Euclidean edge cloud），EEC的想法比较神奇，因为凹凸性定义在相邻两个“片”上，换言之，定义在相邻两片的edge上。将每个edge抽象成一个点云，则得到了附带凹凸信息的点云。如图所示，左图的普通点云，但附带了邻接和凹凸信息。右边是EEC，对凹边赋权值1，其他为0。
此方法称作weighted RanSac

显而易见，某处如果蓝色的点多，那么就越凹，就越应该切开（所谓切开实际上是用平面划分）。问题就转化为利用蓝点求平面了。利用点云求一个最可能的平面当然需要请出我们的老朋友RanSac。但此处引入一个评价函数，用于评价此次分割的有两程序Sm,Pm是EEC中的点。

单纯的weighted RanSac算法并不够。其会导致对某些图形的错误分割，所以作者对此作了第一次“修补”。错误的分割如下图所示

此修补方法称作directional weighted RanSac
方法的原理很简单，垂直于凹边表面的点具有更高的权重显然，对于EEC中的凹点，只要取其少量邻点即可估计垂直方向。
这种修补后还有一个问题，如果这个分割面过长的情况下，有可能会误伤。如图所示：

于是有了第二章修补方法:Locally constrained cutting
这种修补方法的原理就更加简单粗暴了，对凹点先进行欧式聚类（限制增长上限），之后在分割所得的子域里进行分割。
在修修补补之后，CPC算法终于可以使用了，从测试集结果来看，效果还是很好的。