Point cloud segmentation method combining supervoxels and PFCM

随着激光雷达与微软Kinect^[1-2]设备的快速普及，3维点云技术日渐成熟，已经广泛应用于3-D打印、自动驾驶、机器人、自主导航、工程测量、曲面重建等领域。3维点云数据处理已经成为国内外研究重点。点云分割是点云数据处理的重要基础，其目的是对点云数据进行有效地划分，将具有相似属性的点云划分为同一类。目前点云分割方法主要分为基于边缘的方法^[3-6]、基于区域生长的方法^[7-12]、基于特征聚类的方法^[13-17]以及基于机器学习的方法^[18-20]。

基于边缘分割的算法主要是找出表面特征剧烈变化的点，利用边缘信息实现点云的划分。BHANU^[5]等人提出一种边缘检测算法，通过计算梯度、拟合3维曲线来检测物体表面单位法向量的变化情况。DING等人^[6]依据k维树空间拓扑结构, 根据k邻域点的法线的夹角阈值进行边界点提取。此类方法原理简单且速度快，但受噪声影响较大且无法分割复杂场景。基于区域生长的算法主要研究点云之间的相似性，由初始种子点搜索邻域，将达到相似条件的点云划分为一类。BESL^[7]在1988年首次提出区域增长算法，主要包括两个步骤：确定种子曲面；根据相似性进行区域生长。STEIN等人^[8]在2014年提出了一种基于凹凸性的点云分割算法，由超体素算法对点云数据聚类得到超体数据，利用超体之间的凹凸性完成划分。LIN等人^[11]将超体分割问题形式化为一个子集选择问题。利用各点的局部信息，提出了一种有效优化该问题的启发式方法。该算法原理简单高效，可应用于大场景分割，然而这类算法存在过分割与欠分割的缺陷。基于特征聚类的方法通过研究点云之间的特征关系得到点云之间的相似性，并对其进行划分。BIOSCA等人^[16]提出使用无监督聚类方法和模糊算法来分割地面激光点云数据，将模糊算法的参量与聚类方法相结合，得到良好的分割结果。虽然这类方法不易受到噪声干扰，且较为稳定，但点云密度的变化对其有明显的影响。近年来，基于机器学习的分割算法发展迅速，其基于网络学习点云数据的语义信息或其它的特征进行分类。2016年，SHU等人^[20]提出一种通过深度学习进行无监督的3-D形状分割和协同分割的算法，该算法依赖Princeton分割基准，可以在COSEG数据集上表现出良好的分割性能。尽管基于机器学习的方法可以得到较好的分割结果，但其需要花费大量数据以及时间。

针对以上算法的不足，作者提出一种结合超体素与粒子群优化模糊C均值(particle swarm optimization fuzzy C-means, PFCM)的聚类分割算法。该算法去除点云平面，由超体素算法生成超体。为便于后续的划分，计算得到点云的快速点特征直方图(fast point feature histogram, FPFH)，FPFH是点特征直方图在速度上的优化扩展，其考虑局部范围内所有点之间的位置影响和法线关系。FPFH是描述局部范围内数据的几何特征，具有位置信息不变性的特点。采用PFCM算法对超体进行初步划分，对独立的物体组合分类结果。根据距离、曲率以及FPFH特征对粘连的点云进行再划分，弥补了PFCM算法对堆叠物体无法分割以及较大物体过分割的缺陷。本文中算法不仅能分割出独立简单的物体，对于复杂场景也有较好的表现。

模糊C均值(fuzzy C-means，FCM)聚类算法与k均值聚类算法类似，是一种基于划分的聚类算法。该算法的核心思想是将具有相似属性的点云划分为一类，使被划分到一类的点云之间的相似度最大，不同类之间的相似度最小。不同于与其它硬性划分算法，FCM算法是模糊划分，其并不会明确规定一个点一定属于某一类。在实际聚类中，存在无法清晰地划分出这些点属于某一类的情况，因此FCM算法引入隶属度对点云进行模糊划分，用隶属度描述点云属于不同类的不确定性，能够客观地反映现实情况, 但该算法采用爬山法在局部空间内寻找最优解，容易陷入局部最优，并且受初始点和噪声点的影响较大。针对以上缺陷，采用粒子群优化(particle swarm optimization，PSO)算法对其进行优化。PSO算法来源于对鸟类(鱼类)捕食模型的研究，与遗传算法相同，是一种基于群体迭代的算法。该算法使用粒子在解空间中追随最优粒子进行搜索，具有参量少、操作简单等优势。将两种算法结合，可以避免FCM算法陷入局部最优，并且分割速度更快、效率更高。

定义一个1维c列行向量A ={a₁, a₂, …, a_c}表示聚类中心，即一个粒子。其中a_i表示第i类聚类。最终希望求得A的最优解。

PFCM算法的具体流程如下：

(1) 给定各个参量，包括点云的类别数c、算法的模糊指数m、种群规模n、学习因子e₁和e₂、惯性权重w以及迭代次数b。

(2) 随机对点云聚类中心初始化，形成第1代粒子。每个粒子的当前最优位置用p_best表示，种群的最优位置用g_best表示。

(3) 按照下式计算每个聚类中心的隶属度W_ij:

式中, d为欧氏距离, i为1~n的正整数，代表第i个聚类中心，j为1~c的正整数，代表第j个类，k为j中的一个数字。更新W^(b)为W^(b+1)。

(4) 由步骤(3)得到的W^(b+1)计算出c个聚类中心A^(b+1)，其具体计算如下式所示, p_i表示第i个粒子的位置。

(5) 按照下式计算每个粒子的适应度，如果当前粒子的适应度优于该粒子当前最优位置的适应度，则将该粒子的个体最优位置更新为当前位置。如果所有粒子中最优位置的适应度优于当前全局最优位置的适应度，则更新全局最优位置。

式中, Q为常数；W为(1)式中每个聚类中心的隶属度；A为(2)式中更新的聚类中心；J用来评判聚类效果的好坏，J越小，f(p_i)越大，表明聚类效果越好。

(6) 根据下面的公式对每个粒子的速度v_i与位置p_i进行更新。

式中, R()表示随机函数；v_i表示为第i个粒子的速度。

(7) 如果迭代次数超过设定的最大迭代次数，则停止迭代，否则转步骤(3)，继续迭代，直到终止。

PSO算法通过粒子在解空间中追随最优粒子进行搜索，避免了FCM算法陷入局部最优的问题。然而FCM的中心点是加权计算出来的，其只适用于均匀分布的点云，因此对于堆叠的物体，其不能准确分割，会将其混淆。且对于过大物体，会造成不合理的过分割现象。

针对PFCM算法存在的问题，作者提出了一种结合超体素与粒子群优化模糊聚类的点云分割算法(supervoxel particle swarm optimization fuzzy C-means, SPFCM)。该算法对粘连点云进行了再划分，解决了PFCM算法对于堆叠物体无法准确分割，以及对较大物体造成不合理的过分割现象。再划分操作增加了一定的计算量，所以在此基础上，结合了超体素算法，将获得的超体素作为后续划分的输入数据，来达到降低计算复杂度、去除噪声和杂点、提高分割精度的目的。

SPFCM算法首先利用超体素算法，根据点云的空间距离、曲率特征以及FPFH特征共37维特征划分点云得到超体。在后续的划分中使用PFCM算法对超体进行初划分，对粘连点云根据欧氏距离、曲率方差、法向量夹角以及FPFH的特征均差值进行再划分，算法流程图如图 1所示。图中，D为中心点特征距离。

Figure 1.  SPFCM algorithm flow chart

获得点云后，由于点云的平面会干扰超体素算法分割点云的准确性，因此，需要消除点云平面。作者使用随机采样一致性算法检测并去除平面，该算法由3个点确定1个平面，并检测该平面的点云数量。循环以上步骤，把点云数量最多的平面当做整个点云的平面，并去除该平面。使用超体素算法分割去除平面后的点云，超体素算法的目的不是准确地分割点云，而是对点云实行过分割，利用点云的空间距离、曲率特征以及FPFH特征共37维特征来衡量点云之间的相似性，并将相似的点云进行聚类。本质上这种方法是对局部点云的一种总结，点云相似的部分会被自动的分割成一块，有利于后续识别工作，能够降低计算复杂度，去除噪声且提高分割精度。由于点云与图像不同，其不存在像素邻接关系，因此，在使用超体素算法之前，利用八叉树对点云进行体素化处理。

超体素算法具体步骤如下所示：

(1) 定义向量F ={x, y, z, s, H₁, H₂, H₃, …, H₃₃}表示37维特征，其中x, y, z表示点云的空间坐标，s表示点云的曲率，H为点云的快速直方图。FPFH是PFH在速度上的优化扩展，具有姿态不变性的局部几何特征，其计算过程为：计算中心点O与其邻域点O_k法线之间的角度值表示法线偏差，从而得到简化的点特征直方图(simplified point feature histogram，SPFH), 再查找中心点的所有邻域点的邻域范围并计算出其邻域范围内的SPFH，由此可以计算出中心点的FPFH，其计算如下式所示：

式中，H表示FPFH, H ′表示SPFH。

(2) 得到以上特征后，计算出中心点的特征距离，如下式所示：

式中, D_s为空间距离；w_s为D_s的权重；D_c为体素之间的曲率变化值；w_c为D_c的权重；D_h为FPFH的空间距离；w_h为D_h的权重, R_s为空间分辨率。

(3) 以超体素中心向外进行迭代，利用(7)式计算出邻近体素与超体素中心的特征距离，如果特征距离较小，则证明它们之间是相似的，标记该体素属于此超体素，直到达到每个超体素的搜索体积的边缘或者没有其它邻近点可以遍历。

得到超体后，使用PFCM算法对点云进行初步划分，与一般处理流程不同，本文中PFCM算法划分的对象是超体素算法生成的超体，根据超体间的相似性对其进行划分。具体划分原理已经介绍，不再阐述。

由于PFCM算法对堆叠的物体无法准确分割，所以需要再划分。若聚类中心距离小于设定的阈值，则将它们划分为同一类，组合分类结果后加入完成组。若聚类中心距离大于阈值，则需要判断点云是否粘连。对于没有任何连通点、完全无关联的点云，将其划分为一类，并加入到完成组。对于粘连的点云，首先将其合并，以便于再划分，根据法向量夹角、FPFH、距离寻找物体顶点的超体，若顶点超体满足同类条件，则将其加入完成组，否则加入未完成组，其判断条件如下式所示：

式中, d为欧氏距离, d′为超体中心点与相邻超体最近点的欧氏距离, S为曲率方差, θ为法向量夹角, Δ为FPFH的特征均差值。

所有顶点的超体划分结束后，根据特征寻找这些顶点下面的中间超体，并根据(8)式判断这些中间超体是否和已经划分完的顶点超体属于同类，如果满足同类条件，则把中间超体加入完成组，并组合成同一类输出，不满足同类条件则把中间超体加入剩余组，再检测剩余组是否为空，如果为空则结束分割，否则循环以上步骤，直到迭代次数达到阈值。整个流程的原理是模仿人类的认知方式，由顶点开始划分，再根据其它点云和顶点的关系进行划分组合。

本文中使用的数据均来自于object segmentation database(OSD-v0.2)数据集。该数据集是由RICHTSFELD等人^[21]在2012年建立的一个用于对室内场景点云进行分割的一个数据集。该数据集的每组数据都是通过对桌面上杂乱无章的物体进行扫描获得的，共有107组数据，其中学习组43组，测试组64组，测试组中数据从复杂程度上分为简单的单个盒子测试、堆叠箱子测试、遮挡物体测试、对象测试、混合对象测试以及复杂场景测试6个难度等级的测试组。

为了验证本算法的有效性以及分割的效率，将本文中的算法与PFCM算法、局部凸链接打包(locally convex connected patches, LCCP)算法^[8]以及改进的区域生长算法(region growth，RG)^[9]进行对比。

如图 2可知，PFCM算法分割独立的物体，其分割效果尚可，但对堆叠或者结构复杂的物体分割效果较差，容易混淆物体，产生过分割与欠分割现象，并且当物体体积较大时，容易将物体分为两类。例如在对第1组数据进行分割时，PFCM算法产生了混淆现象，其分割出的单个物体包含其它物体的点云，将同一个物体分为多个物体，由此可见PFCM算法对堆叠物体、较大物体不能有效地分割。LCCP算法是基于凹凸性对点云进行分割，其对于均匀平滑的区域有着良好的表现，然而分割线性目标时会出现过分割现象，例如第1组数据以及第3组数据出现了此现象。RG算法基于曲率以及法向量对点云进行划分，存在着过分割与欠分割的现象。本文中的算法不仅能够较好地分割出独立的物体，而且对堆叠的物体也能进行有效分割，可以避免对多个堆叠物体分割时产生的混淆现象。

Figure 2.  Segmentation effect under OSD data set

为了更加客观地评估，本文中使用了准确率P、查全率R以及综合了P与R的F评分，其具体计算如下所示：

式中, T表示算法分割正确的数据, U是算法未分割出正确的数据, V是算法未分割出错误的数据。

本文中抽取了10组数据进行对比，结果如图 3所示。由图中可以看出, 相较于其它3种算法，本文中的算法波动较小，鲁棒性较好。为了更加直观地突出本文中的算法的优越性，利用OSD-v0.2数据集评估本文中的算法、PFCM算法、LCCP算法以及RG算法的性能，其结果如表 1所示。由于本文中算法解决了PFCM算法对堆叠物体以及复杂形状物体无法分割的问题，因此在准确率和查全率方面有了大幅度提升，准确率为86%，查全率为83%，相较于未改进的PFCM算法，分别提升了22%和16%。与近期提出的LCCP算法和RG算法相比，准确率和查全率至少提升了12%和8%。

Figure 3.  Comparison of accuracy of different groups of data

针对PFCM算法对堆叠物体无法划分，较大体积物体容易划分为两类的问题，结合超体素算法提出了SPFCM算法，对粘连的物体进行再划分，克服了PFCM算法的缺陷，并保留了PFCM算法参量少、操作简单的优点。该算法不仅能够准确地分割简单的物体，在面对复杂物体时，也有着良好的表现。同时该算法很好地平衡了准确率与速度。在OSD-v0.2数据集上与PFCM算法、LCCP算法以及RG算法进行对比，实验结果表明，本文中的算法的分割准确率远高于PFCM算法，提高了22%，相较于LCCP算法以及RG算法在有着更快速度的同时，准确率至少提高了12%。