散货料堆快速点云分割和降噪算法研究

韩晓龙 王为民 金 鑫 杨志远 王贡献

1 青岛港口装备制造有限公司 2 武汉理工大学交通与物流工程学院

1 引言

自经济全球化以来，我国进出口贸易日益繁荣，散装货物的运输量也逐年递增，加强散货码头堆取料作业自动化建设，提高散货码头运输效率迫在眉睫。三维重构技术可获取料堆表面位置信息，以位置信息作为自动控制指令依据是实现散货堆场自动化的关键。散货料堆的三维重构通常是通过传感设备采集料堆表面点云，然后对点云进行三维建模来实现，但在点云采集中会由于设备、工作环境等因素引入一些噪声点和地面干扰点云，因此需要对散货料堆点云进行降噪和分割地面处理。

目前针对点云分割和降噪的研究有很多，其中点云分割方法可分为基于边缘分割[1-2]、基于特征聚类分割[3-4]和基于随机采样一致性(RANSAC)分割[5-7]。Woo等用法向量偏差细分网格作为特征描述，提取物体边缘相邻点[1]。莫堃等通过构造符号距离函数估算点云的平均曲率值，实现点云模型快速分割[2]。Yamauchi等采用均值平移法对网格法线进行聚类分割[3]。吴燕雄等在欧式聚类算法基础上增加平滑度约束，加快了算法分割速度[4]。RANSAC(Random Sample Consensus)算法于1981年由Fischler和Bolles提出[5]。Awwad等基于随机采样一致性算法提出Seq-NV-RANSAC分割算法，解决随机采样一致性算法可能检测到虚假平面的问题[6]。刘闯等用法向量夹角为约束条件对点云进行分类，再结合RANSAC分割算法完成点云的分割[7]。

在点云降噪研究方面，Zhang等通过对空间域和特征域的权值调整控制点云的平滑程度和特征保持程度，具有较好的降噪效果，但是不能很好地去除离散点[8]。肖国新等在双边滤波基础上提出自适应空间方差和灰度方差参数的滤波算法，保留了更多的边缘特征[9]。Taubin等首次将Laplacian算法应用到网格处理中[10]。Lange等在前者的基础上提出各向异性几何平均曲率流降噪方法[11]。孙正林等改进Mean Shift算法，提高移动到核密度估计函数的最大值点的速度[12]。Alexa等运用移动最小二乘法(Moving Least Squares,MLS)拟合曲面，光滑点云[13]。Jia等针对目前市场流行的RGB-D相机，提出一种将彩色图像与深度图像对齐去除离散噪声点的方法[14]。

2 散货料堆地面分割和降噪算法

算法框架见图1。首先利用下采样算法精简散货料堆点云数目，加快点云后续处理速度；再结合基于采样一致性(RANSAC)分割算法与欧式聚类分割算法弥补了前者分割不彻底、后者速度慢的问题；最后结合统计分析法和移动最小二乘法去除离散点和点云表面细小噪声点。

图1 散货料堆提取与滤波算法过程

2.1 地面分割

下采样算法原理如下：首先对整幅点云进行栅格划分，划分后的每个小立方体称为体素，将体素中所有的点由重心点代替，删除其他点完成点云精简。

随机采样一致性算法(RANSAC)将点云看作一个样本集合，并设定一个判断准则，根据判断准则将整个点集合分为局内点(inliers)和局外点(outliers)。其分割地面的具体步骤如下：

(1)从样本集合中随机选取1个子集，把子集中的点设为局内点。

(2)使用估计算法计算此局内点的模型参数，然后计算其他子集与这个数学模型的偏差。三维空间中的地面模型可由式(1)表示：

axw+byw+czw+d=0

(1)

偏差用点q(xw,yw,zw)到平面的欧式距离D表示。根据实际需求设定1个偏差阈值σ，当偏差D小于阈值σ时，将该样本点归于局内点，否则归于局外点。

(3)记录当前局内点的个数，如果个数足够多就认为模型足够合理；把当前局内点作为初始选取的子集，重复上述步骤不断扩充模型。

(4)最后，通过估计局内点个数与模型的错误率来评估模型。整个过程记作一次迭代，每次迭代都选择更优的模型。算法迭代次数k可以根据式(2)计算获得：

1-p=(1-wn)k

(2)

对式(2)两边取对数，得

(3)

式中，p为算法产生有用结果的概率，取值0.99；w为每次从数据集中选取1个局内点的概率，取0.5；n为估计模型需要的最小数据量，平面需要至少3个点确定，假设这n个点的选取是相互独立的，选中的点可能被后续迭代重新选择，这样求得的k值一定是迭代次数的上限值。

由于料堆地面不平整，RANSAC分割算法会将料堆和地面分割成多个分离的点云块，结合欧式聚类算法可完成散货料堆点云提取，欧式聚类算法的过程如下：

(1)确定某一采样点qi，创建一个空集Q*，设定阈值t。

(2)用k-d树算法搜索qi最近邻的k个点，计算这k个点到qi的距离，将采样点qi和距离小于t的点qi1，qi2，qi3…放在Q*中。

(3)在Q*/qi(集合Q*中除qi点外的其他点)里找到qi1，重复操作(2)。

(4)在Q*/qi,qi1中找一点，重复操作(2)。

(5)当Q*中不在加入新的点时，完成一次聚类搜索。

2.2 点云降噪

采用近邻统计分析法去除离散点，算法的步骤如下：

(1)利用k-d树法搜索集合Q中每一个点qi的k邻域。

(4)

(5)

滤除离散点后的点云还存在细微的噪声点，通过曲面拟合可以将这些噪声点滤除。曲面拟合常用的方法有多项式拟合和分段拟合，多项式拟合需要较高次数才能达到较好效果，计算复杂；分段拟合影响拟合的光滑性。为了解决这2种方法的不足，运用移动最小二乘法(Moving Least Square，MLS)引入紧支撑权函数和基函数。紧支撑权函数决定拟合曲线、曲面的光滑度，基函数决定拟合曲线、曲面的误差大小。

在待拟合的区域里，拟合函数φ(x)表示为

(6)

式中，η(x)=[η1(x),η2(x),…,ηm(x)]T称为基函数，它是n次完全多项式，m是基函数的项数；a(x)=[a1(x),a2(x),…,am(x)]T为待求的系数，它是坐标x的函数。点云的线性基和二次基分别为：

线性基：η(x)=[1,x,y]T，m=3。

二次基：η(x)=[1,x,y,x2,xy,y2]T，m=6。

(7)

式中，J是选定节点邻域点数目；φ(x)是拟合函数；f(xI)是x=xI处的节点值，w(x-xI)是节点xI的权函数。为确定系数a(x)，计算式(7)的极小值，并对a求导得

(8)

其中

(9)

Q(x)=[w(x-x1)η(x1),w(x-x2)η(x2),

…,w(x-xk)η(xk)]

(10)

f=[f(x1),f(x2),…,f(xk)]T

(11)

令(8)式为0，得

a(x)=P-1(x)Q(x)f

(12)

将式(12)代入(6)，就可以得到MLS拟合函数

φ(x)=ηT(x)P-1(x)Q(x)f

(13)

紧支撑权函数是移动最小二乘法的核心，权函数只影响支撑域内的数据，因此，权值在支撑域内大于零，并且随‖x-xI‖的增大而减小，在支撑域边界和外界处等于零。另外，权函数应该光滑连续，这样可以使得继承权函数特性的拟合函数也光滑连续。常用的权函数是多次样条函数，如式(14)所示。

(14)

3 实验结果与分

用白色塑料颗粒模拟散货，用Kinect深度相机采集点云，获取的料堆点云见图2。体素栅格下采样精简算法耗时1.64s，精简后点的数目为32 672(精简前为216 237)，精简程度为84.9%，结果见图3。

图2 散货料堆初始点云图 图3 精简后点云图

RANSAC算法分割地面后的效果见图4。平面偏离阈值σ影响局内点的选取，当σ值过小时，大量地面点被错误当作外点，地面和散货料堆分离模糊，(见图4a)；当σ值过大时，部分料堆点被错误当作局内点，散货料堆被过度分割，(见图4c)所示。根据实验结果，σ取0.008 m到0.012 m之间的值的效果较好，为保证精度σ值取0.008，分割结果(见图4b)。

图4 不同分割阈值下的分割效果

去除地面点云后的点云中仍然存在大量的离散点，采用邻域统计分析法去除离散点云。取标准差倍数ξ为1，邻域k越大，算法的鲁棒性越好，但是算法使用的时间也越长。为了针对散货料堆选择合适的k值，设计了k=2,4…24共12组实验，得出算法计算时间T和滤除点数目M与k的对应关系(见图5)。从图5中可以看出k值为8时，滤波时间和滤除点数目综合效果最佳，因此，邻域大小取为8。

图5 算法用时、滤除效果与邻域大小关系图

离散点去除后，点云大致分为4个集群(见图6a)，用欧式聚类将4个集群划分出来，再提取点数最多(13109个点)的散货料堆点云(见图6b)。

图6 欧式聚类分割示意图

采用MLS光滑点云，用k-d树搜索法加速邻域搜索，取二次基函数η(x)=[1,x,y,x2,xy,y2]T。根据实验结果，支撑域半径r值取0.012 m以上平滑效果达到最好，但是随着r值增大，算法处理时间增大，因此，取r=0.012 m为本算法研究参数，最终实验结果见图7。

图7 点云MLS光滑处理效果对比图

4 结语

提出一种应用在散货料堆点云的高效率预处理算法框架，该算法主要完成散货料堆的地面分割和降噪。在经典RANSAC分割算法前增加点云精简处理，提高地面分割速度，并通过欧式聚类分割算法解决RANSAC分割算法分割不彻底问题。结合统计分析法和移动最小二乘法去除离散点和点云表面细小噪声点，并在欧式聚类前完成离散点去除，提高料堆点云分割提取的稳定性。