本文来自点云PCL博主的分享，未经作者允许请勿转载，欢迎各位同学积极分享和交流。
摘要
在图像算法中，无监督的过分割是一种广泛的预处理步骤，将图像分割成具有相似属性的像素区域，称之为超像素分割，该方法减少了之后后期算法计算的的成本，并且信息损失最小，本文提出的是一种新的过分割算法，该算利用点云体素关系生成具有空间一致性的过分割，而不是在三维点云映射或者投影到了二维空间中进行处理。论文是在已经校准的RGB_D相机的数据集上进行试验，并且与2D的处理速度相仿的条件下，保证了分割的高效。
分割算法介绍
分割算法目的是将图像中的像素分成符合对象边界有意义的区域，虽然这些方法最初只考虑图像的底层信息，但是最近的语义分割方法大多是利用了高层的对象信息来帮助消除对象边界的歧义，比如基于图的方法，马尔科夫随机场（MRF）以及条件随机场（CRF）。这些算法将图像中的底层信息与对象级信息相结合而变得更为流行。虽然这些技术已经十分成熟，但是他们的缺点是，对这些图像像素的计算成本随着节点的数目的增加而急剧的上升，这以为这每个像素对应一个节点求解图的方法变得十分困难，这就限制了他们在需要实时分割中的应用。
比较新的算法是，出现了一类速度明显更快的超混合方法——简单线性迭代聚类[1]（SLIC）。这是一种迭代梯度上升算法，它采用局部k均值聚类方法，有效地找到超像素点，将像素点聚类在五维空间的颜色和像素位置。深度自适应Superpixels[2]最近将这种思想扩展到使用深度图像，通过增加深度和点云的法向角的维度来扩展聚类空间。虽然DASP是有效的，并且给出了有希望的结果，但它没有充分利用RGB+D数据，仍然停留在2.5D方法的类中，因为它没有明确考虑三维连通性或几何性质。
点云PCL库中的超体分割是一种基于点云体素的连通性分段算法（Voxel Cloud Connectivity Segmentation VCC）应用在RGBD相机获取的点云数据中，通过使用基于三维空间的播种的方法和使用颜色和几何特征的约束来实现点云的局部约束与聚类。文章还清楚的说明了点云的超体分割与“超体素”没有关系，超体素是二维算法简单的扩展到三维，这种方法是不能应用在三维的无序的空间中的，只能在有规则的体素中起作用。
基于几何约束超体素
点云体素连接性分割（VCCS）是一种从三维点云数据生成超像素和超体素的新方法。VCCS产生的超体素比最新的方法更符合物体边界，同时该方法实时性更好。vcc使用k-means聚类的变体来生成其点的标记，有两个重要的约束：
1.超体素簇的种子是通过分割三维空间而不是投影到图像层面来实现的。这可以确保超体素是根据场景的几何属性均匀分布。
2，迭代聚类算法在考虑聚类点时，对被占用的体素进行严格的空间连通性。这意味着超体素不能在三维空间中连接不相交的边界，即使它们在投影平面上是相连的。
接下来我们将描述相邻体素是如何的有效计算，如何生成种子并进行滤波，并对特征和距离测度进行聚类，最后如何迭代聚类算法加强了空间连通性。
邻接图
邻接性是该方法的一个关键步骤，这一步能够确保各个超体素不会在空间中不相连的边界上有交集，在体素化三维空间中，有三种相邻的定义 6，18，26相邻，他们分别共享一个面，面或者边和定点，在本论文中主要是26个相邻体素，这是算法的初始步骤，构建体素点云的邻接图，一般是通过KD树来有效的实现，所有的26个相邻体素的中心都一定要在根号3 * Rvoxle中，其中Rvoxel是指用于分割的体素分辨率，并且在该分辨率下讲离散的元素称之为体素。如此构建出来的邻接图在算法中能够广泛的使用。
晶体种子的生成与滤波
算法首先若干个种子点云，这个种子点云将用于初始化超体素，所以算法首先将空间点云划分为一个具有选定分辨率Rseed的体素化网格，该Rseed的大小是明显高于Rvoxel,其中种子分辨率与体素分辨率的关系如下图：
Rseed确定超级体素之间的距离，而Rvoxel确定点云量化的分辨率。Rsearch用于确定是否有足够数量的种子占用体素。
根据这个图我们也可以理解初始种子的后选择是如何被选择出来的，通过选择点云中最靠近我们种子体素中心的点作为种子候选点，并且我们知道一旦有了种子的候选对象，就必要要去除候选的噪声点种子，为此算法为每个种子建立一个较小的搜索半径Rsearch,用来删除那些没有被搜索半径的一半覆盖的点云种子，如图的绿色部分，过滤后，我们将剩余的种子归类为搜索体积中梯度最小的连接体素，其中的梯度计算公式：
一旦种子体素被选中，我们通过在特征空间中找到种子体素的中心和两个体素内的连接邻域来初始化超体素特征向量。
超体的特征和距离测度进行聚类
VCCS超体素聚类是在39个维度上进行的：
其中前三者是空间坐标，L,a，b为颜色，FPFH是局部几何特征点特征直方图，FPFH是具有空间不变性的描述局部表面模型的特征，为了计算空间中的距离算法首先是规范化空间中的点的距离这个分量，并且该分量取决于种子的分辨率Rseed, FPFH空间中的距离Df是使用直方图相交核计算的[3]。这就引出了标准化距离D的方程式:
基于约束的迭代聚类（Flow Constrained Clustering）
迭代地将体素点云指定给超体素，显著的区别在于我们在将像素指定给聚类时考虑连通性和流。一般过程如下：
（1）从距离点云簇中心最近的体素开始，我们向外流动到相邻的体素，并使用方程4计算每个体素到超体素中心的距离。如果距离是该体素所看到的最小距离，则设置其标签，并使用邻接图将其距离中心更远的邻居添加到该标签的搜索队列中。
（2）然后迭代下一个超级体素，这样从中心向外的每一层都会同时考虑所有的超级体素。我们反复向外搜索，直到找到每个超级体素的搜索体积的边缘（或者没有更多的邻居可以检查），这相当于邻接图的广度优先搜索，在深入搜索图之前，我们检查所有超级体素的相同级别。重要的是，需要避免了相邻体素的边，当我们到达一个超级体素的邻接图的所有叶节点或者在当前级别中搜索的节点都没有设置为其标签时，搜索就结束了。这个搜索过程下图所示，与现有的相比有两个重要优点。
流约束聚类算法的搜索顺序
1，由于算法只考虑相邻的体素，因此超体素标签不能跨越在三维空间中实际不接触的对象边界
2，超级体素标签在三维空间中往往是连续的，因为标签从每个超级体素的中心向外流动，在空间中以相同的速率扩展。
一旦所有超体素邻接图的搜索结束，我们就通过取其所有成分的平均值来更新每个超体素簇的中心。这是以迭代的方式完成的；要么直到集群中心稳定下来，要么进行固定次数的迭代。实验中发现超体素在5次迭代之后是稳定的。
三维体素分割
所提出的方法直接作用于点云，它比在投影图像平面上操作的现有方法有优势。其中最重要的是能够分割来自多种传感器捕获的点云数据，算法是具有通用性的。
总结与参考文献
Voxel Cloud Connectivity Segmentation - Supervoxels for Point Clouds 文章中提到的超体（supervoxel）是一种集合，集合的元素是“体”。与体素滤波器中的体类似，其本质是一个个的小方块。与之前提到的所有分割手段不同，超体聚类的目的并不是分割出某种特定物体，其对点云实施过分割(over segmentation)，将场景点云化成很多小块，并研究每个小块之间的关系。比如在图像分割中，像素聚类形成超像素，以超像素关系来理解图像已经广为研究。本质上这种方法是对局部的一种总结，纹理，材质，颜色类似的部分会被自动的分割成一块，有利于后续识别工作。比如对人的识别，如果能将头发，面部，四肢，躯干分开，则能更好的对各种姿态的人进行识别。
代码实现部分可参考PCL库中的分割模块中的supervoxel_clustering类具体实现。
参考文献：
（1）Slic superpixels compared to state-of-the-art superpixel methods.
（2）Depth-adaptive superpixels
（3）Histogram intersection kernel for image classification
以上内容如有错误请留言评论，欢迎指正交流。如有侵权，请联系删除
