基于改进随机抽样一致的点云分割算法

赵夫群， 马 玉， 戴 翀

(1.西安财经大学信息学院， 西安 710100； 2.西北大学信息科学与技术学院， 西安 710127)

点云是三维图形数据的常见存在形式之一，它能够立体高效地存储三维物体的详细属性信息。点云分割是将三维空间中点云通过一系列算法，将散乱的点云数据划分为更加连贯的子集的过程。分割后的点云数据按照点云属性被划分为同一组别，从而方便进行下一步的数据处理。对三维点云模型的合理分割是后续数据分析的基础，便于后续的特征提取、目标识别、三维重建和虚拟现实等操作的处理。目前，点云分割已经在逆向工程、文物虚拟复原、医学研究等领域得到了广泛的应用[1-4]。

对于点云分割的研究，国内外学者提出了很多的相关算法。代璐等[5]提出一种点云分割神经网络NEPN(non-equivalent point network)，可以有效解决点云分割中的非等效性，提高分割精度； 张坤等[6]利用点云形状相关的特征参数实现了基于形状分割的点云分割方法，该方法提高了点云分割的精度和速度，并且具有较强的稳健性；李仁忠等[7]针对点云分割准确度低的问题，提出一种基于骨架点和外部特征点的点云分割算法，可以实现点云表面小范围内凸面体的有效分割，提高分割精度；傅欢等[8]提出基于八叉树和局部凸性的分割算法方，有效减少了分割的曲面数量同时提升了曲面质量；周炳南等[9]基于点云库，通过对比欧式距离点云分割算法、区域生长点云分割算法以及SegmenterLight分割算法的优缺点，对算法的优化提出相应的改进策略；Charles等[10]采用深度学习算法实现了三维点云的有效分类和分割，可以有效提高分割的精度；Schnabel等[11]使用随机抽样一致算法(RANSAC)实现点云分割，对于异常点云和噪声点云具有较高的鲁棒性，但必须提前指定合适的误差阈值和迭代次数；Biosca等[12]提出一种基于模糊聚类的点云分割算法，该算法准确性较高，但耗时较长；Wu等[13]提出一种基于标签传播的交互式形状分割方法，可以实现点云模型的快速精确分割，但对噪声数据不敏感；Bertolotto等[14]提出一种基于改进区域生长算法的点云的快速分割算法，可以实现基于语义的特征标准的精度和高适应度分割。

对于点云分割算法的改进，一直以来都是一个复杂的问题，虽然已有算法已经在一定程度上提高了分割精度和分割效率，但是仍然存在一些问题。例如，算法容易受到噪声点和异常点的影响；算法大多依赖点的法向量、曲率和颜色等信息，容易造成分割过少或分割过度的问题，从而无法获取完整的分割模型和光滑分割边界。针对如上问题，现采用一种改进的RANSAC算法，通过改进原始点云的选取方式、优化分割面片的合并等方式，提高点云分割质量和分割精度，实现点云精准分割。

1 RANSAC点云分割算法

1.1 RANSAC算法原理

点云分割目的是将原始点云中不同的物体提取成独立的单元，后续可以针对不同的物体特征进行有效的处理。在点云数据获取之前，需要对被采集的物体所处场景中有一定的先验信息。例如：地面、墙面以及屋顶大多都是大平面，长方体往往是某种盒子。对于类似于房间这样的复杂场景中的物体，大部分物体的形状可以划分到简单的几何形状，这样可以为点云分割带来很大的便利性。对于常见的几何形状可以通过数学方式进行表示，使用部分参数来表示复杂物体的特征，RANSAC算法可以从点云数据中将具有几何特征物体分割出来。

RANSAC算法最早由Fischler等[15]在1987年共同提出，起初是作为数据处理的算法，该算法的主要作用是在源数据包含众多噪声的情况下提取出源数据中符合某些特征的数据。该算法可以在一定的概率区间保证最终结果的合理性，提升迭代次数可以提高概率，保证在某个置信区间内最小抽样数N与一个良好概率P满足如下关系：

P=1-(1-εk)N

(1)

式(1)中：ε为局内点和总体数据集的比值；k为模型参数的最小值；P一般取值为0.9～0.99。

对式(1)变形，可得

(2)

RANSAC算法可以将指定的数据集作为输入，总体数据中包括局内点、局外点和可以用于解释数据集的参数模型，参数模型中包含部分可靠参数。RANSAC算法通过迭代的方式每次随机选择一部分数据集作为参数模型的参数，被选取的子数据集为局内点，通过下面5个步骤完成模型验证：①有被选取的局内点适用于该参数模型，即可以通过该局内点计算出参数模型中其他的未知参数；②将其他数据拟合到步骤①中得出的模型中，若其中某些点适用于该模型，则认为这些符合条件的点也为局内点；③如果有大量的子数据集被认定成为局内点，则说明此参数模型合理；④将所有局内点作为输入重新拟合参数模型，因为参数模型只被初始选取的局内点拟合过；⑤最终通过估计获取的局内点的数量和参数模型的误差来改进模型。

现将通过改进RANSAC算法的初始点的选取方式，并利用半径空间密度信息和连通性对分割平面进行优化，使原算法对平面分割的准确性和对边缘位置的分割效果得到提高。

1.2 RANSAC算法缺点

RANSAC算法用于室内平面场景下的点云分割时存在如下缺点。

(1)算法效率。根据RANSAC算法的原理当处理数据集比较大的室内平面场景时，若对场景中的点云数据进行简单的提取，那么在某次具体的搜索中，随着最小抽样数N的增加，导致合理概率P降低，算法的耗时增加。

(2)点云错分。使用RANSAC算法只能提取出点云空间中的平面，这与真实场景下的平面有很大不同，点云空间中的平面不会体现出平面边界，在多平面的场景中可能会出现点云错分割现象。

(3)分割尺度。RANSAC算法在计算过程中用一个固定不变的阈值δ，那么会导致这样的问题：若采用相对较大的阈值δ，当小于此值的分割平面会达不到阈值无法提取出来；若采用相对较大阈值δ时，当大于此值的分割平面在迭代过程中会因为多次达到阈值条件，导致平面多次分割，造成完整的平面破损。

2 改进的RANSAC点云分割算法

改进的RANSAC算法基于RANSAC算法，改进了原始种子点的选取方式，在判断准则中加入了对面片标准差的限制，可以有效减少伪平面的出现，并利用半径密度信息对分割后的面片进行优化，增强了分割的精准性和边缘准确度。

2.1 Kd树与半径空间密度

Kd(K-dimensional)树主要用于分割k维数据空间的数据结构，主要应用场景是搜索k维空间的多维数据。与传统二叉搜索树不同的地方在于Kd树的每个节点表示的是k维空间的点，而且Kd树的每一层都可以进行决策分析。Kd树也继承了二叉搜索树的优点可以精确快速的查找某点，可以实现在某个半径空间邻域点的高效查找，在三维空间当中，半径空间密度是指以该点为中心、R为半径的空间球体所包含点云数据的个数。

2.2 改进初始点选取

在点云数据中，两个点云的距离(空间距离)越靠近，那么这两个点云属于同一个物体的概率也就越大。因此，将使用改进选取初始点的方式，在同样的采集次数下提高了对平面分割的可信度。

对复杂场景中大平面进行点云分割是，不同的平面对应不相同的平面方程，对于三维空间的方程可以通过3个不共线的点来进行标识，所以式(1)、式(2)中的k=3。传统的RANSAC算法选取初始点的方式是从原始数据集当中随机选取3个点作为基准点来获取平面方程参数的初始值，然后通过获取到的初始值来寻找其他局内点，这样得到的模型大多都不会满足判断准则，因此在进行同样次数的采样下满足平面模型的数据集也被减少了，最优模型的概率也会随之降低。

采取的方式是随机在数据集中选取一个点，通过Kd树建立索引，然后查找以该点R半径以内的点，将查找到的所有点采用最小二乘法来拟合，根据拟合的结果来确定平面参数的初始值。针对最小二乘法的结果需要设置阈值进行限制，设阈值为δ0，若拟合结果大于δ0，说明以该点R半径范围内的点云分布不规律，差异较大，在同一平面的概率较小，抛弃该值，并以同样的方式来选取直至初始值的确定。通过这种改进后的方式可以在数据处理的开始剔除异常信息过大的点，减少异常点的影响，提供了数据处理效率，在相同采集次数下提高了获得模型的概率。

2.3 判断准则的设计

设定的判断条件为局内点的数据量和拟合平面的标准差。通常情况下，处于同一平面的点满足以下条件：

ax+by+cz=d

(3)

式(3)中：(x,y,z)为平面点的空间坐标；(a,b,c)为平面法向量并且满足a2+b2+c2=1；d为坐标原点到平面的距离。

距离d采用P(x,y,z)到平面PL(a,b,c,d)的欧氏距离计算，计算式为

d(P,PL)=|ax+by+cz-d|

(4)

式(4)中：P(x,y,z)为(x,y,z)确定的平面；PL(a,b,c,d)为(a,b,c)确定的平面。

选取的局内点在平面内，那么理论上到分割平面的距离应该为零，但是因为在点云空间中点云数据存在误差导致平面不会是绝对的平面而是由多个点在一定范围内组成的拟合平面，需要给定一定的阈值δ0作为判断选取的点是否在平面内，阈值δ0过小会导致平面过度分割，造成平面破损，过大则会增加平面腐蚀作用，无法将平面分割出来。

在实际场景当中需要尽可能地包含其中的平面，所以针对场景中平面内细节信息较多的通常采用严格的阈值，对于普通的平面可将阈值的范围设置的宽泛一些。

若选取的点到平面的距离小于δ0，则认为平面该点为平面模型的局内点。计算点云数据中局内点的数量，若大于阈值Pmin，则说明平面分割完成。判断一个平面是否分割的完成的条件为点云数据中局内点的数量和平面的标准差，所以一个完整的分割平面需要平面使用标准差进行约束。

2.4 面片合并

按照以上准则点云分割之后，可能会存在这样的情况：在点云空间中一些面片可能有多个层次但是总体可视为同一个平面，所以需要将这部分面片进行合并和优化。面片合并的条件为：空间中近似面片的法向量夹角θ一般比较小，可以通过θ值来确定是否进行面片的合并。θ的计算式为

θ=arccos-1(n1·n2)

(5)

式(5)中：n1、n2分别为两个面片的法向量。

仅使用θ来判断合并可能会使得具有相似法向量但距离相差较大的面片合并(类似于平行平面)，且分割后的面片由多个面片组成。对此问题，本文研究使用的算法如下。

(1)首先在分割后的面片建立Kd树索引，从中选取初始点P0。

(2)判断面片R半径的密度信息。若R大于阈值Rnum，将在R中的点添加到集合T={P1,P2,…,Pk}当中，否则将P0从索引中删除，并重新选择P0进行以上判断。

(3)以集合T中的点执行步骤(2)，并将得到的点加入集合T中，并进行统计。若总数小于阈值(最小面片的点数)，则认为该点为噪声点，从点云集中剔除。

(4)重复执行以上步骤，直至将面片中所有点判断完为止。

2.5 算法流程

本文改进RANSAC算法对场景大平面点云分割时需要进行反复迭代，每次迭代会将已经分割过的点从原始数据集剔除，直至模型点数小于给定阈值Nmin，具体流程如下。

(1)根据式(2)计算循环次数N。

(2)计算待拟合面片标准差，若标准差大于阈值δ0，则需要重新确定面片的平面参数，否则进行下一步。

(3)统计局内点数量，若大于点数阈值，则计算面片标准差，否则返回上一步。

(4)重复步骤(2)、步骤(3)N次，根据设定的判断准则获得最佳面片。

(5)重复步骤(1)～步骤(4)，直至模型点数小于给定阈值Nmin。

(6)根据优化策略对多层次面片进行合并和优化，获得最后分割平面。

3 实验结果与分析

实验在Windows 10环境下，采用点云库(PCL)框架和C++语言作为开发工具，利用Microsoft Visual studio 2015运行得到。利用提出的该改进RANSAC算法，将两个原始点云模型进行分割，分割结果如图1和图2所示。

在分割中，设定平面的判断阈值δ0=0.09 m，半径密度阈值Rnum=8。利用式(2)设定循环次数N的取值，0.9≤P≤0.99。对于改进RANSAC算法，其主要影响因素为循环次数N和非分割平面模型的数量值Nmin，二者的关系与完整的分割面积有关，所以当确定好完整的分割平面即可实现面片分割。

从图1和图2的分割结果可见，改进的RANSAC算法能够将相关性较低的边缘点剔除，保留较为完整的大平面，实现良好的点云分割效果。为了验证该改进的RANSAC算法的分割性能，对图1(a)和图2(a)的两个点云模型分别采用RANSAC算法和自适应分割算法[16]进行分割，分割结果如表1所示。

图1 改进RANSAC算法对点云模型1的分割结果

图2 改进的RANSAC算法对点云模型2的分割结果

从表1可以看出，对于同一原始点云，改进的RANSAC算法对于分割后平面的边缘更加精准，同时还可以在保留完整的面片的同时剔除了不相关的部分点云，具有良好的点云分割结果。这是由于RANSAC算法只能在一定的概率区间内保证分割结果的合理性，对室内平面场景的分割效率较低，容易出现点云错分的现象；自适应分割算法根据提取的特征自动选择种子点，并采用改进的区域生长算法对种子点进行分割，该算法可以解决与区域增长算法相关的不一致或过度分割等问题，不需要用户干预，具有较好的鲁棒性，但是该算法对噪声不够敏感；而本文提出的改进RANSAC算法利用半径空间密度重新定义初始点的选取方式，通过多次迭代来剔除无特征点，在实现点云分割的同时可以有效去除噪声点，因此改进RANSAC算法的点云特征提取数据量较大，面片分割的准确性较高。

表1 分割算法对比结果

4 结论

点云分割是三维重建的关键技术之一，从三维视图中分割点云可以方便地进行逆向工程处理。主要针对三维点云数据分割算法进行研究，基于RANSAC算法在点云分割中存在的问题，通过改进初始点数据的选取方式和判断准则，使RANSAC算法对点云数据分割的准确度提高。并通过将改进RANSAC算法与RANSAC算法和自适应分割算法进行实验对比，证明改进RANSAC算法的良好分割效果。在今后的研究中，要进一步对阈值设置进行优化，实现基于点云密度信息的自适应阈值选取，减少人工计算量，进一步提高算法的效率和应用范围。