基于自适应椭圆距离的点云分区精简算法

吴禄慎　俞　涛　陈华伟

(南昌大学机电工程学院　江西 南昌 330031)



基于自适应椭圆距离的点云分区精简算法

吴禄慎俞涛陈华伟

(南昌大学机电工程学院江西 南昌 330031)

摘要利用传统点云精简算法进行散乱点云简化会导致点云模型部分细节特征的丢失或模糊以及影响非平面区域的光顺性。针对这些问题，提出基于自适应椭圆距离的点云分区精简算法。首先，通过对邻域点集进行微切平面与局部曲面的拟合，计算出各点的法矢及曲率等；其次，利用所得几何特征信息，提取点云边界特征以及完成点云平面区域与非平面区域的划分；最后，采用改进后的精简算法对不同区域进行简化。实验结果表明，该算法不但能够快速完成符合要求精简率的数据简化，还能保护点云模型的细节特征以及保证模型非平面部分的光顺性。经过软件分析得出，精简后模型与原始模型的距离误差的标准偏差为0.015 mm。

关键词点云精简四元数最小距离法点云分区边界提取

REDUCTION ALGORITHM OF POINT CLOUD SEGMENTATION BASED ON ADAPTIVE ELLIPTICAL DISTANCE

Wu LushenYu TaoChen Huawei

(School of Mechanical and Electrical Engineering, Nanchang University, Nanchang 330031,Jiangxi, China)

AbstractApplying traditional point cloud reduction algorithm to reducing scattered point cloud will lead to missing or fuzzy of some detail features of the point cloud model and affecting the smoothness of non planar region. Aiming at these problems, we put forward the adaptive elliptical distance-based point cloud segmentation reduction algorithm. First, by fitting the tangent plane and local surface on neighbourhood set, it calculates the normal vector and curvature of each point; secondly, it uses the derived geometric feature information to extract point cloud boundary characteristics and to complete the partition of planar regions and non planar regions of point cloud; finally, it uses the improved reduction algorithm to simplify different regions. Experimental results show that the algorithm can not only rapidly accomplish data simplification in accord with the required reduction rate, but can also protect the detail characteristics of point cloud model and ensure the smoothness of non planar portion of model. Through software analysis, it is found that the standard deviation between the reduced model and the original model is 0.015 mm.

KeywordsPoint cloud reductionQuaternionMinimum distance methodSegmentation of point cloudBoundary extraction

0引言

逆向工程中，光学三维扫描设备被广泛用于精确、快速地获取物件表面坐标信息，但会生成大量的冗余数据，且点云数据一般散乱无序、十分密集。若将全部点云都用于曲面重构，不仅占用大量的计算机资源，操作效率低，而且庞大的数据不便于后续的存储、显示及传输等。因此，在保证精度的前提下对数据进行有效地精简显得尤为重要。目前，许多学者对点云精简做了大量研究，邵正伟[1]等先使用八叉树法对散乱点云进行点云空间划分，然后采用包围盒法[2]完成点云的均匀精简，能够快速完成精简，适合应用平面区域。李凤霞[3]等提出采用邻域点与采样点法矢夹角平均值作为采样点特征信息，对采样点进行划分成多个类别，然后对每一类按规定的精简率完成点云数据简化。徐亚军[4]等提出采用最小曲面距离法，即用曲面距离代替欧式距离，对点云进行精简。葛源坤[5]等通过计算所得点云高斯曲率，设定阈值，将点云划分为平坦区域和突变区域，然后分别对不同区域采用包围盒法和最小距离法进行点云精简。朱煜[6]等采用邻域点与采样点距离的Hausdorff距离代替点云曲率对点云进行分段，然后在每段设定不同的Hausdorff距离阈值完成点云精简。

本文考虑点云模型的诸多细节特征都关系到点云边界特征和数据精简直接影响到特征区域的光顺性。因此根据所得点云曲率法矢信息完成点云边界提取，以及点云平面区域与非平面区域的划分，然后对边界特征进行强制保留，对其附近数据进行保护性精简，并且对非平面区域提出采用变化的椭圆距离作为阈值完成点云简化，最终通过实验验证该算法的有效性。

1点云曲率、法矢的计算

1.1估算点云法矢

1.2计算点云曲率及法矢修正

全局坐标转换为局部坐标的方法步骤为：

(1) 将全局坐标原点平移至于局部坐标原点(即pi)重合，则有平移向量为vi(xi,yi,zi)；

(2) 计算出Z轴nz(0,0,1)与H轴ni(xi,yi,zi)夹角α，然后绕方向RoAixs(xr,yr,zr)经过一次旋转α角度使两轴重合的；

其中：

cosα=nz·ni

(1)

RoAixs(xr,yr,zr)=nz×ni

(2)

(3) 由求得的旋转参数构造旋转四元数Quat(x,y,z,w)：

(3)

(4) 通过(3)中得到的四元数求取旋转矩阵RoM：

(4)

(5)

将式(1)-式(4)代入式(5)计算可得出坐标系O-XYZ向坐标系pi-HUV变换的旋转矩阵；

(5) 利用上述所求平移向量和旋转矩阵，完成坐标转换：

pm′T=RoM·(pm-vi)T

(6)

其中：m=0,1,…,k-1。

(7)

对于曲率，需要先求出曲面的第一基本量E、F、G和第二基本量L、M、N为:

E=fu·fuF=fu·fvG=fv·fv

(8)

(9)

(10)

(11)

2点云划分及边界提取

2.1点云的区域划分

通过分析曲面曲率的几何意义[6]可知：曲面上某点曲率是该点曲面形状的体现，曲率的大小对应于曲面在该点处的弯曲变化程度。其中高斯曲率K是两主曲率的乘积，根据其数值的大小，可以确定曲面上该点的类型——椭圆点(K>0)、抛物点(K=0)和双曲点(K<0)，而平均曲率H是两主曲率的平均值，其数值的大小表面曲面在该点处的凹凸性质。因此依据高斯曲率与平均曲率不同组合，可以将曲面大致分为表1中的八种类型：平面、脊、谷、峰、阱、鞍形脊、鞍形谷和极小曲面。

表1　曲面类型区分

对于本文中进行的点云精简，只需要区分出平面与非平面，所以平面以外的七种类型的曲面可以统一考虑，全部当作为特征曲面处理。

2.2边界特征提取

进行点云精简时造成细节特征丢失或模糊的很大一部分因素是完成精简后点云的边界特征减少，因此在精简前先对边界特征进行提取保护。在点云中边界特征存在的主要形式包括如图1所示的3种。

图1　三类点云边界特征

对于非封闭边界[8]d3，将目标点pi及K邻域P{p0,q1,…,qk-1}投影到其微切平面上，如图2所示。将所有邻域投影点分别与pi投影点连线，判断相邻连线夹角，如果存在夹角大于夹角阈值(经验值结合曲面重构三角化研究，设定阈值为120°)，则可以判定目标点pi为边界特征点。

(a) pi为非封闭边界点　　　(b) pi不是非封闭边界点图2　pi及其邻域点的微切平面投影

f(pi)=d(p,L)/max{d(qj,L)}

(12)

当f(pi)>ε，点pi为边界点；否则为内部点。其中ε为判定阈值，经过实验总结，一般取为0.8~1.0，即可较好地提取点云模型的突变尖锐边界特征。

对于过渡边界d2，在完成区域划分后，通过判断目标点pi的K邻域P{p0,q1,…,qk-1}中处于不同区域中点数目的比例来进行提取。

3基于分区的点云精简

3.1最小距离法精简算法

对于采样点pi，查找其K邻域点集P{p0,q1,…,qk-1}，并分别计算每一个邻域点到采样点的距离Di(i=1,2,…,k-1)。然后设定用于判断邻域点保留与否的最小距离阈值Dmin：

(13)

则最小距离法的精简原则为：

fi=Di-σ×Dmin

(14)

其中，σ为距离调节系数，最后依次比较每一个邻域点的fi数值，当其小于0时，标记qi点为删除。

3.2自适应最小椭圆距离精简算法

对于任一非平面采样点pi,计算出整个邻域点与pi点法矢的夹角余弦的平均值，法矢夹角精简规定夹角小于平均夹角的邻域点标记为删除。但是往往其中与法矢的夹角小于夹角平均值的邻域点，存在如图3表达的两种可能情况：(1)曲面在邻域点与采样点所构成方向上的弯曲程度较小；(2)曲面在邻域点与采样点所构成方向上有较大的弯曲，但该邻域点距离采样点比较近。

图3　法矢夹角变化示意图

对于情况(1)所属方向上可以适当保留较少数据点，拟合后仍能够很好地接近原始形状；而对于情况(2)，为了能拟合出真实形状，需要保留更多比例的数据点。

针对上述两种情况，为满足邻域中在不同方向上精简步距的不一致，同时考虑到曲面上采样点在任意方向的曲率kn，提出椭圆思想构造变化距离阈值结合最小距离法来实现非平面区域数据简化：

kn=k1·cos2θ+k2sin2θ

(15)

其中椭圆距离的确定方法为：对于每一个采样点，均可以获取两个主曲率方向，以最小主曲率所在方向上确定的距离阈值d1为长轴。以最大主曲率所在方向确定的距离阈值d2为短轴，确定椭圆函数d(θ)，其中θ为任意方向与最小主曲率方向夹角，则在每一不同方向都会有相对应的距离阈值d(θ)：

(16)

在进行精简过程时，首先综合考虑法矢夹角阈值以及最小距离阈值，计算出两主方向上的距离阈值；再求取所有任意邻域点方向与最小主曲率方向的夹角；最后遍历所有邻域点，通过与其所处方向距离阈值比较判断是否删除数据点。

3.3精简实施流程

散乱点云分3类进行处理：平面区域、非平面区域和突变边界。

对于突变边界点，采用强制保留。并且为了更好地保护点云细节特征，凡是距离边界点小于平均邻域点距的点都进行保留。

对于任意未被标记为删除的采样点pi，当pi在平面区域时，采用3.1节中介绍的最小距离法进行点云数据精简。

对于任意未被标记为删除的采样点pi，当pi在非平面区域时，采用3.2节中介绍的改进的非平面区域点云精简算法进行数据简化。但是对于初步判定删除的邻域点，须进一步考察其之前未被当作采样点使用过，否则不作删除处理。

4实例应用

本文采用汽车某挡块零件的一部分原始点云(总共64 418个点)作为对象，采用上述方法进行边界提取与区域划分，以及点云的精简，完成的效果分别如图4-图6所示。

图4　点云边界特征

图5　非平面区域

图6　精简后点云模型

精简完成后，对原始点云模型以及精简后点云(20165个点)进行曲面模型重构，并且对部分具有细节特征的区域进行放大处理，分别生成如图7-图10所示。通过观察可以比较明显地发现精简前后两者模型基本能够保持一致。

图7　原始点云重构模型

图8　精简前局部放大

图9　精简后点云重构模型

图10　精简后局部放大

进一步采用专业逆向软件Geomagic对精简前后模型进行距离误差分析，其结果如图11所示。

图11　Geomagic软件比较精简前后模型误差

经过软件分析得出：精简后模型与原始模型的距离误差的标准偏差为0.015 mm。

5结语

本文通过对邻域点进行局部曲面拟合，计算出点云的曲率法矢信息。接着进一步利用计算所得几何特征信息对点云进行特征边界提取以及平面与非平面区域的划分。最后针对平面区域、非平面区域和两者之间过渡区域点云各自的不同特点，分别采用不同的处理方法进行简化。实例验证表明：该算法不但能够快速地完成符合要求精简率前提的数据简化，还能够保护好点云模型的细节特征以及保证模型非平面部分的光顺性。

参考文献

[1] 邵正伟，席平.基于八叉树编码的点云数据精简方法[J].工程图学学报,2010(4):73-76.

[2] Sun W, Bradley C, Zhang Y F, et al. Cloud data modeling employing a unified non-redundant triangular mesh[J]. Computer-Aided Design,2001,33(2):183-193.

[3] 李凤霞,饶永辉,刘陈,等.基于法向夹角的点云数据精简算法[J].系统仿真学报,2012,24(9):1980-1983.

[4] 葛源坤,黎荣,李海伦．空间分割与曲率相融合的点云精简算法研究[J].计算机应用研究,2012,29(5):1997-2000.

[5] 朱煜，康宝生，李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-524.

[6] 徐亚军，魏永超.基于最小曲面距离的快速点云精简算法[J].光电工程,2013,40(8):59-63.

[7] 肖天姿.散乱点云的数据预处理与曲面重建研究[D].大连：大连海事大学,2012.

[8] 周玉莲.基于法矢信息的点云特征提取技术的研究[D].哈尔滨：哈尔滨工业大学,2012.

[9] 陈义仁.逆向工程中散乱点云预处理相关算法研究[D].合肥：中国科学技术大学,2012.

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.010

收稿日期：2014-09-18。国家自然科学基金项目(51065021，51365037)。吴禄慎，教授，主研领域：逆向工程及光机电一体化，虚拟现实技术。俞涛，硕士生。陈华伟，讲师。