基于八叉树编码的铸件点云融合简化方法*

翟 巍,马 行,,穆春阳,王晓强

(1.北方民族大学 a.电气信息工程学院;b.机电工程学院,银川 750021;2.宁夏智能信息与大数据处理重点实验室,银川 750021)

0 引言

自动化工业生产中铸件的浇冒口切割通常是由工人们手工切割,这样不仅耗费大量人力资源,且人工切割的品控也难以得到保证。近些年,选择三维激光扫描技术对要切割的铸件进行点云数据采集,再使用机械臂进行切割,是目前工业生产中发展的方向之一。实际应用生产中,所采用得高精度的点云设备采集的点云数据量庞大,可能还包含了一些冗余点,在后续三维重建过程中必然会消耗大量的时间和计算机资源[1]。因此,尽可能地减少原始数据,消除冗余数据点和噪声,同时保证点云数据的准确率在一个合适的水平,是基于点云简化实现三维重构的重要步骤。

目前,点云简化方法主要有两类:基于点云数据点的简化方法和基于网格的简化方法[2-4]。基于网格的点云简化方法主要思想是为三维点云构造一个三角形或者是多边形网格,其中的节点是三维的点(不一定是点云原始的数据点),边则为点之间的连线。通过减少节点或边的数量来简化网格,例如将几个节点合并,同时保留局部的结构特征。在HOPPE、ECK等[5-6]的研究中,当被测量表面的点的子区域连续时,可以通过渐进网格算法简化点云。DEY等[7]提出了一种利用样本抽取来消除过采样的算法,这可以保证剩余的点足以重建曲面。此外更多关于基于网格的点云简化方法则可以在ALLIEZ、PENG、MAGLO等[8-10]的综述中找到。正如ZHANG等[11]所指出的,这类方法的缺点是网格构造需要耗费大量的运算,并且网格简化改变了原始点的位置,从而导致原数据失真。

与此相对的,基于点的简化方法已经成为目前点云简化研究的热点。尹星翔等[12]提出了一种基于曲率和均匀精简的点云简化方法。所提方法首先利用包围盒法建立k-邻域集然后根据曲率对点云区域进行分类简化。ECKART等[13]提出了一个概率生成模型来模拟点云的分布,通过一种分层的期望最大化算法,在简化率和模型结构的完整性上取得一个很好的平衡。在铸件浇冒口切割方面,SONG等[14]提出了一种基于八叉树编码和表面曲率特征阈值相结合的点云简化方法。该方法可以保持目标点云的特征,同时也保证了点云简化的处理速度。HAN等[15]提出了一种基于法向量的边的点云简化方法,因此边缘特征被很好的保留下来。基于研究对象的数据属性,上述基于点的简化方法可以进一步细分为:空间分割、几何特征和额外属性[16-17]。

针对工业中铸件浇冒口切割自动化的需求,本文提出了一种基于八叉树编码分区选取不同简化算法的点云简化方法。该方法包含了空间分割和几何特征,首先利用八叉树编码将点云分割,然后采集不同分割区域的曲率特征,利用两种不同的简化算法对3种铸件进行测试,在不损失点云特征的情况下,实现点云数据简化的易操作、高效率和高精度要求。

1 本文所用方法

本文的点云简化方法的主要步骤如图1所示。为了将点云划分为多个区域,本文首先采用了八叉树编码的方法。在这一步骤中构造了原始数据点的包围框,并将其划分为具有相同边长的多个子立方体,以此建立了原始数据点云的拓扑模型;接着,对每个子立方体中的点进行k-邻域搜索,并计算出作为点云特征的曲率;然后,在设置可调的曲率阈值后,根据曲率阈值和所有子立方体的平均曲率识别曲率较大或较小的区域。其中,曲率较小的区域为铸件的平坦区域,曲率较大的区域为铸件的切割区域。

图1 点云数据简化方法步骤图

接下来对曲率较小或较大的区域使用两种不同的简化算法:对于铸件的平坦区域,采用随机抽样的方法,对减少数据量非常有效,而且处理速度也有保障。对于铸件的切割区域,选择了基于区域重心的简化算法。这种方法的处理速度相对较慢,但是用这种方法减少数据量后,点云的结构得以最大程度保留,确保有用信息能够留存。

上述简化方法结合了随机抽样和基于区域重心两种简化算法的优点,并考虑了铸件的点云曲率分布状况。对于铸件来说,曲率较大的区域数量明显远小于曲率较小的区域数量。因此,所提出的铸件点云简化方法在保证了简化速度的同时也使大部分特征信息得以留存。

2 基于邻域搜索的八叉树编码

由于本研究所针对的高精度铸件点云数据量较大,如果使用k-d树(k-维树)对区域进行划分,往往需要的时间较长,并且搜索效率较低。所以考虑到将k-d树应用于铸件点云的邻域搜索的不足,本文采用了八叉树编码算法。这种算法更适合于本研究中铸件点云的三维空间划分。该算法结构简单,搜索效率高。

如图2所示,在本研究中,我们基于目标对象的点云的拓扑关系建立了一个根模型。首先,在构造包围框时,将所有的点数据分成8个大小相同的子立方体;其次,用递归方法将每个子立方体均分;最后,重复前面的步骤直到子立方体的最小边长小于指定的点间距。考虑到研究对象的数据点近百万这一因素,因此指定的距离设置为4 mm,以便允许50～100点云数据包含在最小的子立方体中。与此同时,由八叉树编码算法得到的每个子立方体都根据其位置进行编码。

图2 八叉树分区模型

每个子立方体用一个代码表示,该代码对应于八叉树下的根节点。根模型中的子立方体位置可以用八叉树代码Q表示,如式(1)所示:

Q=qn-1…qm…q1q0

(1)

式中:qm是在这一层级节点的数量,m∈{0,1,…,n-1},qm+1是qm父级的节点数。因此从每个子节点到八叉树中根的路径可以用q0到qn-1来表示。

具体的流程如下:

步骤1:确定点云八叉树划分的编号。

d0*2n≥dmax

(2)

式中:d0为点云已知点的距离,dmax为包围框的最长边长,n为八叉树的划分编号,为式(2)中的最小整数。

步骤2:确定点云数据点所在位置的子立方体的编码。假设数据点为P(x,y,z),子立方体的空间索引为(i,j,k),Q为对应节点的八叉树编码。它们之间的关系如式(3)～式(5)所示:

(3)

式中:(xmin,ymin,zmin)是与根节点对应的包围框的最小顶点坐标。将子立方体的空间索引(i,j,k)转换为二进制表示的过程如式(4)所示:

(4)

式中:

im,jm,km∈{0,1},m∈{0,1,…,n-1}
qm=im+jm21+km22

(5)

因此,该立方体对应的八叉树编码可以用式(1)来表示。

如果我们假设经过划分后的一个子立方体的索引是(i,j,k),那么围绕它的26个子立方体的索引可以用(i±δ,j±δ,k±δ)(δ∈{0,1})来表示。

在点云中找到距离子立方体重心最近的点pi后,在子立方体当中均匀选取30个点,确保点pi是这30个点的重心。这30个点也需要尽可能多地覆盖子立方体内的空间。最后,用最小二乘法通过30个点拟合二次曲面。二次曲面拟合公式如式(6)所示:

(6)

式中:ci,j-1为曲面参数。

3 基于曲率特征的点云简化

3.1 曲率特征计算方法

在本文当中,采用了最小二乘法计算拟合表面系数如式(7)所示:

(7)

式中:xk、yk、zk是子立方体中各点的坐标。

为了在式(7)中分别计算系数,使其偏微分为0:

(8)

通过求解方程从而确定了拟合曲面的二次方程。在得到拟合曲面方程后,根据以下一阶和二阶偏微分推导出各点的平均曲率:

(9)

紧接着,曲面的平均曲率就可以表示为:

(10)

(11)

3.2 基于随机采样的简化方法

由于铸件平缓区域的点云数据需要保留相对完整的轮廓特征,对详细特征的要求不是很高。因此,在平缓区域内采用了随机采样的方法进行简化[18]。

第一步先建立一个随机函数,该函数覆盖了原始的点云数据,然后根据随机函数生成随机数,删除相应的点,直到剩余的点云数据量的减少率达到确定的预设值。该随机采样算法操作简单,易于实现,处理速度也很高。然而,随机函数的随机性非常大。在减少原始点云的数据后,可能会丢失一些重要的几何特征。

3.3 基于区域重心的简化方法

当曲率大于给定的阈值时,对于这类区域采用了基于区域重心的简化算法。相对于随机采样的简化算法,基于区域重心的简化方法可以保留更多的信息特征。

首先,当曲率大于阈值时,该区域内的所有点都由一个立方体所包含;其次,将立方体划分成若干个相同大小的小立方体;最后,计算每个小立方体中的平均点(区域重心),并计算离该平均值最近的点。

假设在所选的立方体中有N个点{p1,p2,…,pN},并且有坐标为(pix,piy,piz),i=1,2,…,N,然后将平均点标记为p,其坐标为(px,py,pz),如式(12)所示:

(12)

紧接着,可以计算出子立方体中的点pi(pix,piy,piz)与平均点p之间的距离di,(i=1,2,…,N),如式(13)所示:

(13)

上式同时也计算了其他点与平均点之间的距离。最后,在删除子立方体中的其他点时将保留此点,可确定在子立方体之中离均值点最近的点。具体简化过程如图3所示。

图3 基于区域重新简化方法的过程

4 实验结果及分析

本次实验基于某公司的gocator3200三维激光扫描仪对三种铸件扫描获得,同时通过MATLAB对所提出的简化方法进行了验证。在实验中,数据的简化率定义为剩余点云数据量与总点云数据量的比值。切割区域特征点的保留率定义为切割区域保留点的数据量与切割区域点云数据总量的比值。如图4所示,图4a部分为工件原始图像,图4b部分点云的灰线部分的点云呈现相对陡峭的分布,而其余白色点云的分布则较为平缓。

(a) 点云原始数据 (b) 区域划分后的点云图4 铸件模型点云的区域分布

通过对比图5中原始点云的数据和简化过后可以看出,随着简化率的提高,依然可以观察到整个被测物体的形状。该算法可以保留带切割铸件的重要特征。本实验将原始的点云数据划分为点云特征较为平坦的区域,并且采用随机抽样的方法进行简化。实验结果如图5所示。

(a) 平坦区域点云原始数据 (b) 80%简化率

(c) 60%简化率 (d) 40%简化率

(e) 20%简化率 (f) 5%简化率图5 使用不同简化率的简化结果

可以看出,简化率越小,剩下的点云数据点就越少。在较为平坦的区域,只需要保留原始点云完整的轮廓特征即可。考虑到精简所需要的时间及其效果,采用随机抽样的方法,选取了20%的简化率,相应的整体的减少率为77.80%。

对于点云分布较陡的区域,对区域重心法进行了简化。如图6所示,利用区域重心法进行简化后,区域点云数据得到较好的保存,实验结果如表1所示。

(a) 切割区域原始点云 (b) 设置边长为2 mm

(c) 设置边长为3 mm (d) 设置边长为4 mm图6 设置不同边长的边框下具有不同简化效果

表1 不同边长下的简化效果

从图6和表1中可以看出,所设置的子立方体网格的边长越小,保留的细节特征就越多,但处理速度就越低。

所以综合考虑到简化时间和焊接区特征点的简化率,在采用区域重心简化法时,将子立方体网格的边长设置为3 mm。从图7中可以看出,采用基于八叉树编码和表面特征曲率阈值相结合的点云简化方法,为铸件模型的切割区域保留了重要的特征点。同时,外观轮廓仍然保持良好,对下一步提取关键的几何特征位置有很大帮助。

图7 使用该算法后点云简化的效果

为了分析所提出的铸件切割点云简化方法的性能,并与其他3种简化方法进行了比较。本文的简化方法和3种传统简化算法的实验结果如表2所示,各算法的简化效果如图8所示。

表2 铸件点云数据的4种简化方法的比较结果

(a) 原始点云数据 (b) 本文提出的方法

(c) 随机采样法 (d) 包围盒法

(e) 区域重心法图8 切割铸件的简化方法对比结果图

结果如表2和图8所示,其中这些方法的还原率近似相等。从表2可以看出,当点云的减少率约为20%时,4种方法的处理速度差异很大。随机抽样处理是处理速度最快的方法。然而尽管它所需的处理时间最短,但是由于随机抽样的随机性,该方法可能会丢失许多特征点。

通过表2可知,本文所提出的简化方法的处理速度低于现有的随机采样方法,但特征点的保留效果更好。这是因为该方法采用了基于邻域点搜索的八叉树编码算法,并针对不同曲率的区域选择了两种不同的简化算法。结果表明,该方法可以结合随机抽样算法和区域重心简化算法的优点。将本方法推广至采集的另外两种铸件模型上,简化后效果如图9所示。

(a) 第一组

(b) 第二组图9 其他两种模型使用本方法后的简化效果

可以看到,被简化后的铸件模型在被简化的同时切割区域的特征点也很好的被留存,说明该算法具有较为宽泛的应用场景。

5 结论

考虑到在工业生产过程中采用了机械臂对铸件浇冒口自动切割,有必要减少由激光扫描仪获得的铸件点云的数据量用以增加处理速度。本文提出了一种基于八叉树编码和表面曲率特征阈值的点云简化方法,以减少工业制造中铸件的点云。本研究基于铸件浇冒口的点云特征,采用八叉树编码方法将点云划分为子立方体,然后通过k邻域搜索和曲率计算得到曲率特征。最后通过结合这两种简化算法,用以简化铸件的点云数据。通过本次研究发现,本文所提出的简化方法相对于其他3种传统的简化方法包括包围盒法、区域重心简化方法和曲率抽样方法都要快。当选取的简化率相近时,本文提出的简化方法相对于这3种可以保留更多的特征点。该方法能够很好的结合随机采样与区域重心简化法在不同曲率区域的优点,对保持铸件的表面特征起到良好的作用。本文所提出的简化方法有利于机械厂的自动切割系统的开发。此外,还需要更多具有不同轮廓的铸件的点云数据集来验证所提出的方法。