利用超体素中心点连线可见性的图像分割算法

陈十力，罗双奇，刘冠峰

（广东工业大学机电工程学院，广东 广州 510006）

1 引言

机器人对周围环境的感知与理解是其执行任务的基础，而视觉是获取环境数据的主要手段。近年来，随着文献[1]，文献[2]结构小巧、价格低廉、能实时获取可视范围内环境的深度与彩色图像设备的推出，深度信息作为特征可以用来提高图像分割的精确度，其生成的点云场景图已经逐渐应用到许多领域，例如机器人物体抓取[3]、场景识别[4]、机器人导航[5]等任务中。

图像分割一直是计算机视觉领域广泛研究的课题，其中基于颜色特征的图像分割算法受到广大学者的青睐。但当目标和背景颜色相似，或图像中存在低对比度边缘时，易产生过分割结果。利用深度信息可以正确区分各个目标物体和背景。目前，点云图分割问题已有深入研究，主要有基于边，基于面以及基于聚类[6]等分割方法。

在基于边的处理方法中，文献[7]对点云数据进行空间栅格划分，依据边长阈值合并边长小的栅格并识别棱边，从而达到点云的区域分割。此类方法的优点是处理速度快，对尖锐边缘识别能力强，其不足之处在于对边界的判断仅利用其局部点云，受噪声影响较大。

在基于面的处理方法中，比较经典的方法是一种自底向上的区域生长法[8]。文献[9]通过雷达获取的点云数据作为种子点，利用相邻表面中心点对应的向量差在法方向的投影作为区域生成准则进行分割，而文献[10]先过分割点云作为种子点，再用向量间的夹角关系作为区域生成准则进行分割。不足之处在于单一结合法向量判断，对测量噪声的鲁棒性不足，且对被遮挡物体的分割效果较差。

在基于聚类的处理方法中，业内比较具有代表性的方法有文献[11]提出的直接依据点云之间的欧式距离来进行聚类，进而达到点云的分割，其方法简单易懂，执行效率高，但点云需要满足在空间上有较大间隔，常需要事先移除物体下方的平面，使其目标点云处于悬浮状态，这样才能保证算法的成功。

基于上述问题中法向量估计的噪声干扰、物体遮挡场景以及单一判断的合并方法不足，文章以盒状、柱状物体为研究对象，提出了一种基于超体素中心点连线可见性的室内场景分割算法。本算法合理利用超体素中心点连线可见性准则来判断相邻超体素的合并情况，避免了法向量因为噪声带来的误差；不仅如此，考虑到物体被遮挡情况，提出了一种常见分离平面的合并准则。两种不同的准则共同作用，比单一结合法向量判断效果更好，鲁棒性更强。

2 算法框架

图1 整体流程图Fig.1 Flow Diagram of the Algorithm

本算法整体流程，如图1 所示。具体思路如下：

（1）利用体素云联通分割算法（Voxel Cloud Connectivity Segmentation，VCCS）[12]对整个场景点云进行过分割，得到过分割超体素，效果过分割结果，如图1（b）所示；

（2）利用相邻超体素中心点法向量的平行准则和中心点连线可见性准则共同判断是否合并相邻超体素，合并结果，如图1（c）所示；

（3）过滤掉噪声超体素团体，得到的合并结果，如图1（d）所示；

（4）针对同一物体被遮挡情况作融合处理，得到最终物体分割结果，效果如图1（e）所示。

使用体素云联通分割算法，将点云图过分割为许多小点云块，称其为超体素（Supervoxels），用符号Pi=（pi，ni，Ni）表示，其中pi表示超体素中心，ni表示超体素中心法单位向量，以及具有相邻关系的其它超体素e∈Ni。VCCS 算法实际上是一种利用Kmeans 聚类变体的区域生长法来生成单个的超体素，和无限制的生长不同，VCCS 算法首先需要有规律的布置区域生长“晶核”，晶核在空间中是均匀分布的；并指定晶核距离（Rseed），粒子距离（Rvoxel）和最小晶粒（MOV），过小的晶粒需要融入最近的大晶粒。Rseed和Rvoxel是VCCS 分割的两个重要的参数，对文章算法分割的好坏有着重要影响。

3 合并方法

使用区域生长算法来进行图像的合并。算法的设计主要由以下三点：生长种子点的确定，区域生长的条件以及区域生长停止的条件。文章依据VCCS 过分割结果的特点，选取任意超体素中心点作为种子点；相邻超体素中心点法向量平行准则和中心点连线可见性准则作为区域生长的条件；直到遍历完所有的相邻超体素之后，区域生长就会停止。

3.1 区域生长条件

一个物体的平面被分割成若干超体素，理论上这些超体素的法向量是相互平行且方向相同的，因此将其作为区域生长的条件之一；但是由于摄像机的制造、安装精度以及噪声干扰等影响因素，同一个平面上不同超体素的法向量夹角通常不等于零度。文章通过判断相邻超体素中心点法向量的夹角是否在设定的阈值内作为其合并的条件，如式（1）所示。

式中：N—法向量（Normal）平行判断准则；NThresh—相邻超体素中心点单位法向量n1和n2的夹角阈值。如果式（1）中N为true，则认为两个超体素属于同一个面，合并它们，反之不合并。

上述法向量平行准则只适合同一物体、同一平面的相邻超体素合并，而不能用于同一物体、不同平面。为了解决这一问题，文章在法向量平行准则合并平面的过程中，同时添加相邻超体素中心点连线可见性准则作为另外一种生长条件。三维点云图不同于二维彩色图，它可以很好的表示物体的几何结构关系，文章利用此结构关系，设计判断准则为：如果相邻超体素中心点连线从拍摄视角看去不可见，则认为相邻超体素属于同一个物体，反之，则认为不是同一个物体，具体解释如下。

如图2 左所示，P1、P2分别是相邻超体素的中点，从视角O看连线P1P2不可见，P3是连线P1P2的中点，P4是P3到大面积超体素的垂足，∠P3P4O为θ。对于两个超体素组成的凸形状，在三角形ΔOP4P3中，向量P3P4与P3PO形成的夹角小于90°，θ 为锐角，则认为是同一个物体，将两个相邻超体素合并；同理，如图2 右所示，向量P3P4与P3PO形成的夹角大于90°，θ 为钝角，则认为不是同一个物体，两个相邻超体素不合并。推到公式，如式（2）所示。

图2 超体素中心点连线可见性原理图Fig.2 Principle of the Visibility of Connecting Line between CenterPoints of Two Supervexols

式中：V—中心点连线可见性（Visible）判断准则；VThresh—设定的θ角度阈值。如果式（2）中V为true，则认为两个超体素属于同一个物体，合并它们，反之不合并。

综上所述，设计区域生长法的两个区域生长条件：相邻超体素中心点法向量平行准则以及中心点连线可见性准则，可合并同一物体、同一平面以及同一物体、不同平面的情况。

3.2 噪声过滤

按照上述准则合并得到的结果，还存在一些未被合并的小超体素团体，其原因在于环境干扰、物体的一些特殊结构以及相机拍摄带来的误差。为了改进算法，增强算法的鲁棒性，利用VCCS 过分割的相邻超体素的特点，设计如下合并方法：在上述合并准则得到的超体素团体中找到点云数量小于阈值Sthresh的团体，根据最近邻原理，把它合并到离其最近且大于阈值的超体素团体中即可消除噪声。判断最近的条件，由超体素团体中心在所有团体中心的最小距离求得。根据经验，文章中所有Sthresh设置为1500。

3.3 被遮挡平面合并

图3 同一平面被其他物体遮挡示例Fig.3 Illustration of the Same Plane Occluded by Other Objects

通过两个合并准则以及噪声过滤，可以处理大多数盒状、柱状物体，但对于同一物体，同一平面被遮挡的情况，如图3 左所示被遮挡的书籍，由此方法将会分割为两个物体，效果如图1（d）所示。这是许多同类算法的一大缺点。生活中，具有平面性质的物体随处可见，文章通过研究平面物体被遮挡时的一些性质和特点，提出了如下场景合并方法：从拍摄视角看过去，如果两个超体素平面团体中心EF连线有部分不可见，则有可能是同一物体被其它物体遮挡，合并这两个超体素平面团体；黄色的线在三维空间中有部分被红色的字典遮挡，“穿过”字典不可见，则认为是同一个物体，反之亦然，如图3 左所示。

对于同一物体，被遮挡的同一平面，理论上被分开的表面在空间中应该具有相同的平面参数方程，如式（3）、式（4）所示。

同一平面因为遮挡分成两块，其表面的单位法向量NP1、NP2应该相同，常数DP1，DP2也应该相同。但仅通过NP1、NP2相等，DP1、DP2相等还不足以判断物体被遮挡，有可能是两个一样高的平面，故为了加强算法的鲁棒性，文章对算法作了如下改进，首先判断两个超体素团体单位法向量N的夹角，参数D是否在阈值NP_thresh、Dd_thresh内，如果在，则认为两个超体素团体在同一个平面内，但无法确定其是否属于同一物体。为了解决这一问题，在上述基础上，首先得到两个超体素团体上表面的中心点，再映射到二维图中，以这两点为直线的首末端点，连线，得到直线在二维图中索引，如图3 左所示黄线，E、F为直线的首末端点；其次，将二维图的直线映射回三维图中，这时由于二维图和三维图处于同一视角，映射回三维图中直线得到的点，是落在两个超体素团体中心点E、F和相机原点D组成的平面上，如图3 右所示。其中绿色三角形ΔEFD表示平面，红线代表由二维直线映射回三维空间得到的点；最后利用上述方法，作如下判断。

图3 右中平面E、F、D的俯视图，如图4 所示。EF表示在三维空间中两点的连线，粗深色线表示二维直线映射回三维空间得到的点，作如图所示的辅助线。当存在平面物体被遮挡时，直线EF从拍摄角度D看会有部分不可见，如图中灰色区域所在的线HH′，此时有直线长度DC＜DB，表示物体被遮挡，为了提高算法的鲁棒性，通过遍历II′上所有的C点，比较DC＜DB的个数与总个数来确定。

图4 判断平面是否被遮挡的抽象模型Fig.4 Abstracted Model to Determine Whether the Plane is Occluded

综上所述，定义遮挡物体判别式（5）为：

式中：P—平面（Plane）判断准则；NP1，P2—两个平面法向量的夹角；DP1，P2—两个平面常数的绝对差值；NDC＜DB—DC＜DB的个数；Ns_thresh—数量比例阈值，这里设定为0.3。如果式（5）中P为true，则认为两个平面属于同一物体，合并它们，反之不合并。

结合前两个合并条件，噪声过滤以及被遮挡平面合并条件，最后我们可以得到如下（6）判别总式：

式中：ECC—加强连接标准（Enhanced Connect Criterion），先按区域生长法合并同一物体，同一平面以及同一物体，不同平面的情况，然后过滤掉小的超体素团体，避免环境噪声等带来的干扰，最后再合并同一物体，被遮挡的同一平面，得到最终的合并结果。

4 试验结果与分析

4.1 OSD 数据集分析

文章以OSD-v0.2 数据集[13]中所有点云图作为实验样本，它由Richtsfeld 等人在2012 年提出，包含111 张在桌子上的杂乱场景图，场景具有多个物体，大多是盒子状或圆柱形，图片的种类有彩色图，点云图，深度图等，针对所有数据而言，桌面上的各个物体为场景的主体。

在评价指标方面，按照论文[14]考虑了如下指标：

图5 部分数据集分割结果：左列原图、中间真值、右为文章分割结果Fig.5 Some Segmentation Results for the OSD Dataset：the Left Original Image，the Middle Ground Truth and the Right are Our Results

这里方法分割的部分数据集结果，如图5 所示。分析发现，算法对从简单到复杂的盒状、柱状物体场景均能够进行有效的分割。

文章与LCCP 算法[10]，Richtefed[13]等，Ucke-rmann[14]等，凹凸度[15]等方法比较，利用数据集OSD-v0.2 作为分割对象，通过计算各种方法的fP、fn、Fos、Fus等值，来比较本方法的优劣，得到的实验结果，如表1 所示。其中这里算法的各阈值设为Nthresh=16，Vthresh=0.71，Rseed=0.71，Rvoxel=0.006。

表1 不同分割方法实验结果比较Tab.1 Comparison on Experimental Results Using Different Segmentation Methods

从表1 看出，和其它繁琐复杂的方法相比，这里的方法在性能上有所提高，特别是对漏识别率fn来说，有很明显的降低，其原因在于相邻超体素中心点连线可见性准则以及遮挡平面物体合并的结果，这是其他方法不具备的；同时，四个参数的总体误差，比LCCP 法和凹凸度法更低，效果更好。

4.2 参数分析

图6 Rvoxel、Rseed 变量对fp、fn的影响Fig.6 Influence of Variable Rvoxel and Rseed on fp and fn

论述的运算方法涵盖2 个重要的参数，分别是VCCS 中的晶核距离（Rseed）以及粒子距离（Rvoxel），Rseed表示超体素种子点分辨率，Rvoxel表示超体素邻接图的八叉树叶分辨率，两者会影响初始的过分割超体素，太小的超体素容易漏识别，太大的超体素容易误识别。文章通过OSD-v0.2 数据集对其产生的分割效果展开研究和分析，如图6（a）所示。当Nthresh=16，Vthresh=0.71，Rseed=0.0268，Rvoxel=0.005～0.007，fn+fP整体的变化范围在2%以内；当Nthresh=16，Vthresh=0.71，Rseed=0.025～0.027，Rvoxel=0.006，如图6（b）所示。fn+fP整体的变化范围在3%以内。不难发现，算法的鲁棒性较好，不必刻意的调节参数来达到最好的效果。

也对其中所使用的准则和方法进行了分析，以OSD-v0.2 数据集为研究对象，所使用的参数为Nthresh=16，Vthresh=0.71，Rseed=0.0268，Rvoxel=0.006。通过比较不同方法的组合对fn+fp产生的影响，实验结果，如表2 所示。发现单独使用中心点连线可见性准则或法向量平行准则时，效果很差，组合使用两者，误差有了很大的降低，噪声过滤以及遮挡平面都可以在一定程度上降低误差，可以根据需求来进行方法的选择。

表2 不同准则与方法对误差的影响Tab.2 Influence of Different Criteria and Methods on the Error

4.3 任务场景分析

文章算法也可以用在机器人抓取任务中。机器人抓取物体包括物体的识别、位姿估计以及动作执行，而抓取的一大难点在于物体的位姿估计。当目标物体具有“头”和手柄这一类特征时，将物体过分割为不同的部分，识别可以抓取的部分，估计其位姿，从而让机器人获得更好的抓取效果。

图7 同一物体分成不同部分Fig.7 Segmenting the Same Object to Different Parts

工作台场景图，如图7 左上所示。包含5 种不同的工具；在图像识别的过程中，我们可以用传统的特征点识别、模板匹配，或者时下流行的卷积神经网络等方法来得到像图7 右上中物体的种类（Class）以及包围框（Box），但对于机器人抓取物体不是很友好，很难定义在哪里抓取物体。通过运用文章算法，将提取的目标物体的点云，利用超体素中心点连线可见性准则进一步分割，得到工具的“头”和手柄部分，然后识别手柄，如图7 左下过分割、右下手柄识别，以此计算夹取位姿，机器人便可以很好的抓取物体了。此外，这里算法也存在一些不足之处，比如通过遮挡平面的合并，虽然能降低物体的过分割率，但对于一些体积更大的内凹物体，还是存在过分割现象，这是因为超体素团体中心点连线在此处可见且不是平面，如图8 所示。过分割的盆子，内凹处被过分割为不同的部分；并且，由于融合条件较多，相比其它算法，计算量有所增加，速度较慢，平均每幅图的处理时间在1.7s。此类问题的解决和分析是文章算法以后进行优化的重要方向。

图8 内凹物体的过分割Fig.8 Over-Segmentation Occurs to Concave Objects

5 结论

系统的探讨和分析机器人通过视觉获取环境信息，仅仅通过分割点云来达到室内场景中盒状、柱状物体的分割。提出一种基于超体素中心点连线可见性的方法，同时依据相邻超体素法向量平行准则，噪声过滤以及被遮挡平面超体素中心点连线可见性准则，最后到达较好的物体分割效果。该方法并不复杂，不需要专门的学习与训练，可有效的进行物体分割。实验结果表明，文章方法要比单一结合局部表面凹凸性展开的分割操作方法更为优良，鲁棒性更好；和基于学习以及模型的方法相比，该方法更为简单。在未来的工作中，将着力提升算法的效率以及降低误识别率，如通过预处理彩色图，再结合点云图，作出更好的合并判断。另外，将文章分割算法运用在机器人物体抓取，自动导航，环境感知等实际应用场景中，进一步验证算法的有效性。