散乱点云去噪与简化的统一算法

赵京东,杨凤华,郭英新

(曲阜师范大学 数学科学学院,山东 曲阜 273165) (*通信作者电子邮箱zhaojd@mail.qfnu.edu.cn)

散乱点云去噪与简化的统一算法

赵京东*,杨凤华,郭英新

(曲阜师范大学 数学科学学院,山东 曲阜 273165) (*通信作者电子邮箱zhaojd@mail.qfnu.edu.cn)

针对三维点云去噪和简化很难用同一参数的问题,提出一种基于扩展的曲面变化度局部离群系数(ESVLOF)的散乱点云去噪与简化的统一算法。通过对ESVLOF定义的分析,给出了其性质。利用ESVLOF去噪过程中计算的曲面变化度和预设的相似度系数,构造出随曲面变化度增大而减小的参数γ，并将其作为点云简化的局部阈值,在点云去噪的同时进行点云简化。仿真结果显示，该方法能够保留原始数据的几何特征,与传统的三维点云预处理相比,效率提高近一倍。

散乱点云;曲面变化度;去噪;点云简化

0 引言

激光三维扫描仪获取的三维数据点数量巨大,且往往带有噪声和冗余点,给后续的数据存储和模型重建造成负担。因此必须在保持被测物体几何特征的前提下,对测量点云进行预处理,预处理过程通常分为两步,即先对原始点云数据去噪[1],然后再简化[2]。点云去噪的目标是去掉离群点、保留主体点云,而简化的目标则是去除点云主体中的重复点和冗余点。由于两者的去除目标不同,因而用一种参数选择法很难做到三维点云去噪和简化同时进行。

关于点云的简化算法有很多,如2002年Hur等[3]提出的Delaunay三角化点云简化，2014年李国俊等[4]基于Delaunay三角化的噪声点云非均匀采样,以及Lichti等[5]提出的非均匀网格方法点云简化；2011年张有亮等[6]提出了扇形网格法点云简化算法。这种基于网格的点云简化方法,可以实现较大区域的点云简化,但在边界区域或突变区域简化效果会受到很大的影响。为减少简化对边界点的影响,2004年Oshima[7]提出了基于迭代的非边界点简化法,但由于涉及到迭代,所以影响了简化的速度。郑德华[8]在2005年提出了通过设定数据重采样间隔对点云进行直接缩减,该方法可以快速实现点云的简化,但是均匀简化无法保留突变区域较多的点。黄国珍等[9]将两种非均匀网格方法用于逆向工程点云的简化,实现了突变区域的保留,但没有考虑突变区域点云不一致的影响。对此,2006年Sihvo等[10]对二维(2D)均匀网格法进行了改进,提出了三维(3D)网格简化方法；2007年Wentzlaff等[11]根据曲率对点云进行了简化；2009年Sareen等[12]提出了仅适用于样条曲面模型重建的点云简化算法。这三种方法对曲面区域有比较好的简化效果,但需要消耗较多的时间,在曲面区域比较适用,不过在同时存在曲面和平面的区域简化精度和速度都会受到影响。2012年杜晓晖[13]通过计算点p与其邻域点主曲率的Hausdorff距离作为衡量参数改进了Kim等[14]提出的曲面离散曲率算法,这两个离散曲率算法均需要用二次抛物曲面拟合的方法估算所有点的主曲率,运算量较大。效果较好且运算量适中的是2010年黄文明等[15]的保留边界的点云简化方法,该算法是在点云简化前利用Pauly等[16]提出的一种可以直接从散乱点云计算曲面弯曲程度的度量指标——曲面变分,检测出所有的边界点,简化过程中保留所有边界点, 对非边界点,则根据曲面变分及邻近点保留情况进行散乱点云的简化。该算法判断某一点是否为边界点,只是查看该点处的曲面变分是否大于事先设定的阈值。如果阈值较大,则会将弯曲程度较大的曲面和平面一样进行简化,造成曲面的信息丢失;若阈值较小,又会使弯曲程度较大的曲面得不到简化,使简化率下降。

关于点云的去噪算法同样很多,如2011年聂建辉等[17]借助曲面变化度(即文献[15-16]中的曲面变分)的定义提出了基于曲面变化度的局部离群系数(Surface Variation based Local Outlier Factor, SVLOF),利用SVLOF对散乱点云的近离群点进行识别,去噪效果良好。本文作者在前期研究[18]中发现,SVLOF在曲面变化度很大的地方,特别是在三维实体锐利的棱边和棱角处具有反常现象,因此对SVLOF作了重新定义,称其为扩展的SVLOF(Extended SVLOF, ESVLOF)。利用ESVLOF作为近离群点的识别参数,既能识别平滑曲面上的离群点,又能识别三维实体的棱边或棱角点处的离群点,同时仍然保留SVLOF原有的足够宽泛的阈值选取空间。SVLOF和ESVLOF在离群点的判断上具有很高的灵敏度,但该参数的计算耗时较多,如果对原始点云先作去噪处理再作简化操作,必将增加预处理时间,降低三维模型的重建效率。本文通过对ESVLOF定义的分析,给出了ESVLOF的性质,并利用ESVLOF去噪过程中计算的曲面变化度和预设的相似度系数,构造出了随曲面变化度增大而减小的局部阈值,在利用ESVLOF进行点云去噪的过程中完成了点云的非均匀简化,使三维点云的预处理时间约等于点云的去噪时间。

1 ESVLOF性质及简化条件

1.1 ESVLOF定义[18]

(1)

其中:σ称为曲面变化度[17](或称为曲面变分[15-16]),它被定义为p点及其邻域点构成的协方差矩阵C的最小特征值λ0与所有特征值之和的比值,它表示了该点处曲面的弯曲程度。

1.2 数据点可去掉的条件

远离群点是必须要去掉的,可同文献[17-18]一样通过聚类方式来完成,本文所研究的对象是不包含远离群点的主体点云。

首先,噪声点(即近离群点)是要去掉的。由文献[18]可知,它满足ESVLOF(p)gt;th(th≫1)。由于ESVLOF(p)≥1,所以不含噪声的点云满足1lt;ESVLOF(p)≤th。

其次,对曲面变化度无影响或影响较小的数据点是可去掉的。即可去掉的点应满足ESVLOF(p)lt;1+γ,其中γ≥0是一个设定的误差项。

(2)

其中:ε是一个略大于0的误差项,称为相似系数。若给定一个相似系数ε,则被简化掉的点数将随着曲面突变度的增大而减小。由此可得数据点可去掉的条件是:

(3)

2 去噪与简化过程

1)若mlt;0.7k，表示点p周围rth范围内数据点数已经很少,则不作任何处理。

2)若m≥0.7k，表示点p周围rth范围内数据点较多,需要作适当的简化,则按式(1)计算ESVLOF(p)(其中负指数系数σ按文献[18]选择为-4),并按式(3)处理点p:

a)若ESVLOF(p)gt;th，表示p点为近离群点,则删除p点；

3 实验与分析

本文算法用VC++6.0语言实现, 并在启天M1750商用计算机(Pentium Dual-core CPU,主频3.06 GHz, 内存2 GB)上进行测试。

对于同样的点云数据,三维重建的直观效果与所用的算法有关。Ball Pivoting算法[19]具有较高的运算效率,但自身具有较强的曲面平滑作用,使重建后的三维实体缺少锐利的棱边。Hoppe等[20]根据稠密的散乱点集自动计算法矢信息,用切平面线性逼近待重建曲面的局部形状,然后利用实现等值面抽取的步进立方体算法输出曲面的三角化模型。该算法自动化程度高,能够识别曲面边界,但对于曲面边界以及尖锐棱边部分的重建效果仍不够理想。周儒荣等[21]对Hoppe提出的三角网格面重建算法进行了改进,能更好地进行有界曲面以及带尖锐棱边曲面的重建,且效率较高。因此,实验中均选择周儒荣算法[21]输出三维实体的三角网格。

3.1 仿真验证

首先利用Matlab的peaks函数产生如下仿真数据:在以点(-3, -3, 0)、(3, 3, 0) 为对角线的正方形平面内产生3 721个数据点,然后增加1%,幅度不大于30%的随机噪声,利用随机函数均匀获取2 076个点作为仿真点云数据。取k=15,th=1.5,相似系数度ε取不同值进行实验,统计结果如表1所示,简化后的部分三维点云与三角网格如图1所示。

表1 peaks仿真数据简化统计(点云个数=2 076,k=15, th=1.5)

图1 peaks简化后的点云及网格

图3 本文算法简化后输出的三角网格

3.2 实际数据验证

由于实际数据量比较大,为提高算法效率,可适当减小类k邻域的大小。本文实验中选择k=10,th=2.5,相似度系数取不同值,对bunny点云和horse点云进行简化实验。实验开始前,先用聚类方法将原始点云中的远离群点去掉,实验过程中仅对包含近离群点的原始点云进行简化。bunny简化前后的点云如图2所示,图2(c)是基于两点之间距离的均匀简化的情况。由于在二维空间观察三维点云不够直观,因而后面的简化效果比较不再给出简化后的点云图,只给出简化后重构的三角网格,如图3～4。图4为点数与图3相当的均匀简化后输出的三角网格。对于图2(a)的bunny点云,算法的简化率及耗时统计如表2。horse点云的简化结果如图5所示。

图2 bunny简化前后的点云图

3.3 数据分析

从表1的仿真数据和表2的实测数据统计来看,对于同一种点云数据,相似系数ε越大,简化掉的点数越多,简化率越高,当ε趋近于0时(如ε=0.000 1时),几乎失去了简化效果。实际上当ε=0时,只去掉了点云中的近离群点,本文算法退化为ESVLOF去噪算法。从图1中ε=0.02到0.08的三角网格,可以明显看出几何特征被完整地保留了下来,保留下的数据点主要集中曲面的突变区域,平坦区域的点个数较少,且曲面越平坦保留的点越少;当相似系数很大时(ε=0.08),较为平坦的曲面变为平面,几何特征有所丢失,说明此时点云被过度简化,因而实际应用中,为防点云被过度简化,相似系数不能选择过大。进一步对比图3和图4,明显可以看出本文简化后输出的三角网格图3比较光滑,采用均匀简化的图4则表面有小的凸起,说明本文算法可以滤除点云噪声,去噪和简化可同时进行。同样的问题也出现在图5中,图5(b)的马脖子上方也有小的凸起。对比图3(d)和图4(d),可以发现当精简率过高时,bunny耳朵处的数据出现了问题,图4(d)丢失边缘,而图3(d)的边缘仍能保留,这说明本文算法可以较好地保留模型的边界数据。同时，图5(d)的马耳朵明显比图5(b)真实。表2中的耗时比约等于1,说明本文算法与文献[18]的独立点云去噪算法具有同等的运算效率。这说明本文算法可将点云的预处理(即点云去噪和点云简化)效率提高一倍。

图4 采用均匀简化输出的部分三角网格(bunny)

图5 两种方法对horse点云的简化结果

表2 两种算法对bunny数据简化统计(k=10, th=2.5)

4 结语

References)

[1] WANG J, HAN J, PEI J. CLOSET+: searching for the best strategies for mining frequent closed item sets [C]// KDD 2003: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 236-245.

[2] 陈西江, 章光, 花向红. 于法向量夹角信息熵的点云简化算法[J]. 中国激光, 2015, 42(8): 336-344. (CHEN X J, ZHANG G, HUA X H. Point cloud simplification based on the information entropy of normal vector angle[J]. Chinese Journal of Lasers, 2015, 42(8): 336-344.)

[3] HUR S M, KIM H C, LEE S H. STL file generation with data reduction by the delaunay triangulation method in reverse engineering[J]. The International Journal of Advanced Manufacturing Technology, 2002, 19(9): 669-678.

[4] 李国俊, 李宗春, 侯东兴. 基于Delaunay三角化的噪声点云非均匀采样[J]. 计算机应用, 2014, 34(10): 2922-2924, 2929. (LI G J, LI Z C, HOU D X. Delaunay-based non-uniform sampling for noisy point cloud[J]. Journal of Computer Applications, 2014, 34(10): 2922-2924, 2929.)

[5] LICHTI D D, GORDON S J. Error propagation in directly georeferenced terrestrial laser scanner point clouds for cultural heritage recording[EB/OL]. [2017- 01- 10]. https://www.fig.net/resources/proceedings/fig_proceedings/athens/papers/wsa2/WSA2_6_Lichti_Gordon.pdf.

[6] 张有亮, 刘建永, 付成群, 等. 新的点云数据简化存储方法[J]. 计算机应用, 2011, 31(5): 1255-1257. (ZHANG Y L, LIU J Y, FU C Q, et al. New method for point cloud data reduction[J]. Journal of Computer Applications, 2011, 31(5): 1255-1257.)

[7] OSHIMA T. Modern survey of large bridge and tunnel project for their construction control[EB/OL]. [2017- 01- 10]. https://www.fig.net/resources/proceedings/fig_proceedings/korea/abstracts/pdf/session17/oshima-abs.pdf.

[8] 郑德华. 点云数据直接缩减方法及缩减效果研究[J]. 测绘工程, 2006, 15(4): 27-30. (ZHENG D H. The data reduction of point cloud and analysis of reduction effect[J]. Engineering of Surveying and Mapping, 2006, 15(4): 27-30.)

[9] 黄国珍, 卢章平. 面向逆向工程的点云数据简化方法[J]. 机械设计与研究, 2005, 21(31): 59-61. (HUANG G Z, LU Z P. Method of point cloud data reduction for reverse engineering[J]. Machine Design and Research, 2005, 21(31): 59-61.)

[10] SIHVO T, NIITTYLAHTI J. A low cost solution for 2D memory access[C]// MWSCAS 2006: Proceedings of the 49th IEEE International Midwest Symposium on Circuits and Systems. Piscataway, NJ: IEEE, 2006: 123-127.

[11] WENTZLAFF D, GRIFFIN P. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15-31.

[12] SAREEN K K, KNOPF G K, CANAS R. Contour-based 3D point cloud simplification for modeling freeform surfaces[C]// Proceedings of the 2009 IEEE Toronto International Conference on Science and Technology for Humanity. Piscataway, NJ: IEEE, 2009: 381-386.

[13] 杜晓晖. 一种无记忆点云迭代简化算法[J]. 计算机工程与应用, 2012, 48(3): 182-184. (DU X H. Memoryless iterative point cloud simplification algorithm[J]. Computer Engineering and Applications, 2012, 48(3): 182-184.)

[14] KIM S-J, KIM C-H, LEVIN D. Surface simplification using a discrete curvature norm [J]. Computer amp; Graphics, 2002, 26(5) : 657-663.

[15] 黄文明, 肖朝霞, 温佩芝,等. 保留边界的点云简化方法[J]. 计算机应用, 2010, 30(2): 348-384. (HUANG W M, XIAO Z X, WEN P Z, et al. Point cloud simplification with boundary points reservation[J]. Journal of Computer Applications, 2010, 30(2): 348-384.)

[16] PAULY M, GROSS M, KOBBELT L P. Efficient simplification of point-sampled surfaces [C]// VIS 2002: Proceedings of the 2002 IEEE Conference on Visualization. Washington, DC: IEEE Computer Society, 2002: 163-170.

[17] 聂建辉, 胡英, 马孜.散乱点云离群点的分类识别算法[J]. 计算机辅助设计与图形学学报, 2011, 23(9): 1526-1532. (NIE J H, HU Y, MA Z. Outlier detection of scattered point cloud by classification[J]. Journal of Computer-Aided Design amp; Computer Graphics, 2011, 23(9): 1526-1532.)

[18] 赵京东, 杨凤华, 刘爱晶.散乱点云近离群点识别算法[J]. 计算机应用, 2015, 35(4): 1089-1092, 1128. (ZHAO J D, YANG F H, LIU A J. Near outlier detection of scattered point cloud [J]. Journal of Computer Applications, 2015, 35(4): 1089-1092, 1128.)

[19] BERNARDINI F, MITTLEMAN J, RUSHMEIER H, et al. The ball pivoting algorithm for surface reconstruction [J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4) : 349-359.

[20] HOPPE H, DE ROSE T, DUCHAMP T, et al. Surface reconstruction from unorganized points[J]. Computer Graphics, 1992, 26(2): 71-78.

[21] 周儒荣, 张丽艳, 苏旭, 等.海量散乱点的曲面重建算法研究[J]. 软件学报, 2001, 12(2): 249-255. (ZHOU R R, ZHANG L Y, SU X, et al. Algorithmic research on surface reconstruct ion from dense scattered points [J]. Journal of Software, 2001, 12(2): 249-255.)

Unifiedalgorithmforscatteredpointclouddenoisingandsimplification

ZHAO Jingdong*, YANG Fenghua, GUO Yingxin

(SchoolofMathematicalSciences,QufuNormalUniversity,QufuShandong273165,China)

Since it is difficult to denoise and simplify a three dimensional point cloud data by a same parameter, a new unified algorithm based on the Extended Surface Variation based Local Outlier Factor (ESVLOF) for denoising and simplification of scattered point cloud was proposed. Through the analysis of the definition of ESVLOF, its properties were given. With the help of the surface variability computed in denoising process and the default similarity coefficient, the parameterγwhich decreased with the increase of surface variation was constructed. Then the parameterγwas used as local threshold for denoising and simplifying point cloud. The simulation results show that this method can preserve the geometric characteristics of the original data. Compared with traditional 3D point-cloud preprocessing, the efficiency of this method is nearly doubled.

scattered point cloud; surface variation; denoising; point cloud simplification

2017- 05- 02;

2017- 07- 22。

中国博士后科学基金资助项目(2014M551738)。

赵京东(1962—),男,山东莱州人,教授,主要研究方向:CAD、数字图像处理; 杨凤华(1962—),女,山东新泰人,副教授,硕士,主要研究方向:非线性泛函分析; 郭英新(1969—),男,山东新泰人,副教授,博士,主要研究方向: 控制理论、控制工程、神经网络。

1001- 9081(2017)10- 2879- 05

10.11772/j.issn.1001- 9081.2017.10.2879

TP391.72

A

This work is partially supported by the Postdoctoral Science Foundation of China (2014M551738).

ZHAOJingdong, born in 1962, professor. His research interests include CAD, digital image processing.

YANGFenghua, born in 1962, M. S., associate professor. Her research interests include nonlinear functional analysis.

GUOYingxin, born in 1969, Ph. D., associate professor. His research interests include control theory, control engineering, neural networks.