趙京東,楊鳳華,郭英新

(曲阜師范大學 數(shù)學科學學院,山東 曲阜 273165) (*通信作者電子郵箱zhaojd@mail.qfnu.edu.cn)

散亂點云去噪與簡化的統(tǒng)一算法

趙京東*,楊鳳華,郭英新

(曲阜師范大學 數(shù)學科學學院,山東 曲阜 273165) (*通信作者電子郵箱zhaojd@mail.qfnu.edu.cn)

針對三維點云去噪和簡化很難用同一參數(shù)的問題,提出一種基于擴展的曲面變化度局部離群系數(shù)(ESVLOF)的散亂點云去噪與簡化的統(tǒng)一算法。通過對ESVLOF定義的分析,給出了其性質(zhì)。利用ESVLOF去噪過程中計算的曲面變化度和預(yù)設(shè)的相似度系數(shù),構(gòu)造出隨曲面變化度增大而減小的參數(shù)γ，并將其作為點云簡化的局部閾值,在點云去噪的同時進行點云簡化。仿真結(jié)果顯示，該方法能夠保留原始數(shù)據(jù)的幾何特征,與傳統(tǒng)的三維點云預(yù)處理相比,效率提高近一倍。

散亂點云;曲面變化度;去噪;點云簡化

0 引言

激光三維掃描儀獲取的三維數(shù)據(jù)點數(shù)量巨大,且往往帶有噪聲和冗余點,給后續(xù)的數(shù)據(jù)存儲和模型重建造成負擔。因此必須在保持被測物體幾何特征的前提下,對測量點云進行預(yù)處理,預(yù)處理過程通常分為兩步,即先對原始點云數(shù)據(jù)去噪[1],然后再簡化[2]。點云去噪的目標是去掉離群點、保留主體點云,而簡化的目標則是去除點云主體中的重復點和冗余點。由于兩者的去除目標不同,因而用一種參數(shù)選擇法很難做到三維點云去噪和簡化同時進行。

關(guān)于點云的簡化算法有很多,如2002年Hur等[3]提出的Delaunay三角化點云簡化，2014年李國俊等[4]基于Delaunay三角化的噪聲點云非均勻采樣,以及Lichti等[5]提出的非均勻網(wǎng)格方法點云簡化；2011年張有亮等[6]提出了扇形網(wǎng)格法點云簡化算法。這種基于網(wǎng)格的點云簡化方法,可以實現(xiàn)較大區(qū)域的點云簡化,但在邊界區(qū)域或突變區(qū)域簡化效果會受到很大的影響。為減少簡化對邊界點的影響,2004年Oshima[7]提出了基于迭代的非邊界點簡化法,但由于涉及到迭代,所以影響了簡化的速度。鄭德華[8]在2005年提出了通過設(shè)定數(shù)據(jù)重采樣間隔對點云進行直接縮減,該方法可以快速實現(xiàn)點云的簡化,但是均勻簡化無法保留突變區(qū)域較多的點。黃國珍等[9]將兩種非均勻網(wǎng)格方法用于逆向工程點云的簡化,實現(xiàn)了突變區(qū)域的保留,但沒有考慮突變區(qū)域點云不一致的影響。對此,2006年Sihvo等[10]對二維(2D)均勻網(wǎng)格法進行了改進,提出了三維(3D)網(wǎng)格簡化方法；2007年Wentzlaff等[11]根據(jù)曲率對點云進行了簡化；2009年Sareen等[12]提出了僅適用于樣條曲面模型重建的點云簡化算法。這三種方法對曲面區(qū)域有比較好的簡化效果,但需要消耗較多的時間,在曲面區(qū)域比較適用,不過在同時存在曲面和平面的區(qū)域簡化精度和速度都會受到影響。2012年杜曉暉[13]通過計算點p與其鄰域點主曲率的Hausdorff距離作為衡量參數(shù)改進了Kim等[14]提出的曲面離散曲率算法,這兩個離散曲率算法均需要用二次拋物曲面擬合的方法估算所有點的主曲率,運算量較大。效果較好且運算量適中的是2010年黃文明等[15]的保留邊界的點云簡化方法,該算法是在點云簡化前利用Pauly等[16]提出的一種可以直接從散亂點云計算曲面彎曲程度的度量指標——曲面變分,檢測出所有的邊界點,簡化過程中保留所有邊界點, 對非邊界點,則根據(jù)曲面變分及鄰近點保留情況進行散亂點云的簡化。該算法判斷某一點是否為邊界點,只是查看該點處的曲面變分是否大于事先設(shè)定的閾值。如果閾值較大,則會將彎曲程度較大的曲面和平面一樣進行簡化,造成曲面的信息丟失;若閾值較小,又會使彎曲程度較大的曲面得不到簡化,使簡化率下降。

關(guān)于點云的去噪算法同樣很多,如2011年聶建輝等[17]借助曲面變化度(即文獻[15-16]中的曲面變分)的定義提出了基于曲面變化度的局部離群系數(shù)(Surface Variation based Local Outlier Factor, SVLOF),利用SVLOF對散亂點云的近離群點進行識別,去噪效果良好。本文作者在前期研究[18]中發(fā)現(xiàn),SVLOF在曲面變化度很大的地方,特別是在三維實體銳利的棱邊和棱角處具有反?，F(xiàn)象,因此對SVLOF作了重新定義,稱其為擴展的SVLOF(Extended SVLOF, ESVLOF)。利用ESVLOF作為近離群點的識別參數(shù),既能識別平滑曲面上的離群點,又能識別三維實體的棱邊或棱角點處的離群點,同時仍然保留SVLOF原有的足夠?qū)挿旱拈撝颠x取空間。SVLOF和ESVLOF在離群點的判斷上具有很高的靈敏度,但該參數(shù)的計算耗時較多,如果對原始點云先作去噪處理再作簡化操作,必將增加預(yù)處理時間,降低三維模型的重建效率。本文通過對ESVLOF定義的分析,給出了ESVLOF的性質(zhì),并利用ESVLOF去噪過程中計算的曲面變化度和預(yù)設(shè)的相似度系數(shù),構(gòu)造出了隨曲面變化度增大而減小的局部閾值,在利用ESVLOF進行點云去噪的過程中完成了點云的非均勻簡化,使三維點云的預(yù)處理時間約等于點云的去噪時間。

1 ESVLOF性質(zhì)及簡化條件

1.1 ESVLOF定義[18]

(1)

其中:σ稱為曲面變化度[17](或稱為曲面變分[15-16]),它被定義為p點及其鄰域點構(gòu)成的協(xié)方差矩陣C的最小特征值λ0與所有特征值之和的比值,它表示了該點處曲面的彎曲程度。

1.2 數(shù)據(jù)點可去掉的條件

遠離群點是必須要去掉的,可同文獻[17-18]一樣通過聚類方式來完成,本文所研究的對象是不包含遠離群點的主體點云。

首先,噪聲點(即近離群點)是要去掉的。由文獻[18]可知,它滿足ESVLOF(p)gt;th(th?1)。由于ESVLOF(p)≥1,所以不含噪聲的點云滿足1lt;ESVLOF(p)≤th。

其次,對曲面變化度無影響或影響較小的數(shù)據(jù)點是可去掉的。即可去掉的點應(yīng)滿足ESVLOF(p)lt;1+γ,其中γ≥0是一個設(shè)定的誤差項。

(2)

其中:ε是一個略大于0的誤差項,稱為相似系數(shù)。若給定一個相似系數(shù)ε,則被簡化掉的點數(shù)將隨著曲面突變度的增大而減小。由此可得數(shù)據(jù)點可去掉的條件是:

(3)

2 去噪與簡化過程

1)若mlt;0.7k，表示點p周圍rth范圍內(nèi)數(shù)據(jù)點數(shù)已經(jīng)很少,則不作任何處理。

2)若m≥0.7k，表示點p周圍rth范圍內(nèi)數(shù)據(jù)點較多,需要作適當?shù)暮喕?則按式(1)計算ESVLOF(p)(其中負指數(shù)系數(shù)σ按文獻[18]選擇為-4),并按式(3)處理點p:

a)若ESVLOF(p)gt;th，表示p點為近離群點,則刪除p點；

3 實驗與分析

本文算法用VC++6.0語言實現(xiàn), 并在啟天M1750商用計算機(Pentium Dual-core CPU,主頻3.06 GHz, 內(nèi)存2 GB)上進行測試。

對于同樣的點云數(shù)據(jù),三維重建的直觀效果與所用的算法有關(guān)。Ball Pivoting算法[19]具有較高的運算效率,但自身具有較強的曲面平滑作用,使重建后的三維實體缺少銳利的棱邊。Hoppe等[20]根據(jù)稠密的散亂點集自動計算法矢信息,用切平面線性逼近待重建曲面的局部形狀,然后利用實現(xiàn)等值面抽取的步進立方體算法輸出曲面的三角化模型。該算法自動化程度高,能夠識別曲面邊界,但對于曲面邊界以及尖銳棱邊部分的重建效果仍不夠理想。周儒榮等[21]對Hoppe提出的三角網(wǎng)格面重建算法進行了改進,能更好地進行有界曲面以及帶尖銳棱邊曲面的重建,且效率較高。因此,實驗中均選擇周儒榮算法[21]輸出三維實體的三角網(wǎng)格。

3.1 仿真驗證

首先利用Matlab的peaks函數(shù)產(chǎn)生如下仿真數(shù)據(jù):在以點(-3, -3, 0)、(3, 3, 0) 為對角線的正方形平面內(nèi)產(chǎn)生3 721個數(shù)據(jù)點,然后增加1%,幅度不大于30%的隨機噪聲,利用隨機函數(shù)均勻獲取2 076個點作為仿真點云數(shù)據(jù)。取k=15,th=1.5,相似系數(shù)度ε取不同值進行實驗,統(tǒng)計結(jié)果如表1所示,簡化后的部分三維點云與三角網(wǎng)格如圖1所示。

表1 peaks仿真數(shù)據(jù)簡化統(tǒng)計(點云個數(shù)=2 076,k=15, th=1.5)

圖1 peaks簡化后的點云及網(wǎng)格

圖3 本文算法簡化后輸出的三角網(wǎng)格

3.2 實際數(shù)據(jù)驗證

由于實際數(shù)據(jù)量比較大,為提高算法效率,可適當減小類k鄰域的大小。本文實驗中選擇k=10,th=2.5,相似度系數(shù)取不同值,對bunny點云和horse點云進行簡化實驗。實驗開始前,先用聚類方法將原始點云中的遠離群點去掉,實驗過程中僅對包含近離群點的原始點云進行簡化。bunny簡化前后的點云如圖2所示,圖2(c)是基于兩點之間距離的均勻簡化的情況。由于在二維空間觀察三維點云不夠直觀,因而后面的簡化效果比較不再給出簡化后的點云圖,只給出簡化后重構(gòu)的三角網(wǎng)格,如圖3～4。圖4為點數(shù)與圖3相當?shù)木鶆蚝喕筝敵龅娜蔷W(wǎng)格。對于圖2(a)的bunny點云,算法的簡化率及耗時統(tǒng)計如表2。horse點云的簡化結(jié)果如圖5所示。

圖2 bunny簡化前后的點云圖

3.3 數(shù)據(jù)分析

從表1的仿真數(shù)據(jù)和表2的實測數(shù)據(jù)統(tǒng)計來看,對于同一種點云數(shù)據(jù),相似系數(shù)ε越大,簡化掉的點數(shù)越多,簡化率越高,當ε趨近于0時(如ε=0.000 1時),幾乎失去了簡化效果。實際上當ε=0時,只去掉了點云中的近離群點,本文算法退化為ESVLOF去噪算法。從圖1中ε=0.02到0.08的三角網(wǎng)格,可以明顯看出幾何特征被完整地保留了下來,保留下的數(shù)據(jù)點主要集中曲面的突變區(qū)域,平坦區(qū)域的點個數(shù)較少,且曲面越平坦保留的點越少;當相似系數(shù)很大時(ε=0.08),較為平坦的曲面變?yōu)槠矫?幾何特征有所丟失,說明此時點云被過度簡化,因而實際應(yīng)用中,為防點云被過度簡化,相似系數(shù)不能選擇過大。進一步對比圖3和圖4,明顯可以看出本文簡化后輸出的三角網(wǎng)格圖3比較光滑,采用均勻簡化的圖4則表面有小的凸起,說明本文算法可以濾除點云噪聲,去噪和簡化可同時進行。同樣的問題也出現(xiàn)在圖5中,圖5(b)的馬脖子上方也有小的凸起。對比圖3(d)和圖4(d),可以發(fā)現(xiàn)當精簡率過高時,bunny耳朵處的數(shù)據(jù)出現(xiàn)了問題,圖4(d)丟失邊緣,而圖3(d)的邊緣仍能保留,這說明本文算法可以較好地保留模型的邊界數(shù)據(jù)。同時，圖5(d)的馬耳朵明顯比圖5(b)真實。表2中的耗時比約等于1,說明本文算法與文獻[18]的獨立點云去噪算法具有同等的運算效率。這說明本文算法可將點云的預(yù)處理(即點云去噪和點云簡化)效率提高一倍。

圖4 采用均勻簡化輸出的部分三角網(wǎng)格(bunny)

圖5 兩種方法對horse點云的簡化結(jié)果

表2 兩種算法對bunny數(shù)據(jù)簡化統(tǒng)計(k=10, th=2.5)

4 結(jié)語

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]. 計算機應(yīng)用, 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] 張有亮, 劉建永, 付成群, 等. 新的點云數(shù)據(jù)簡化存儲方法[J]. 計算機應(yīng)用, 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] 鄭德華. 點云數(shù)據(jù)直接縮減方法及縮減效果研究[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] 黃國珍, 盧章平. 面向逆向工程的點云數(shù)據(jù)簡化方法[J]. 機械設(shè)計與研究, 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]. 計算機工程與應(yīng)用, 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]. 計算機應(yīng)用, 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]. 計算機輔助設(shè)計與圖形學學報, 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]. 計算機應(yīng)用, 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、數(shù)字圖像處理; 楊鳳華(1962—),女,山東新泰人,副教授,碩士,主要研究方向:非線性泛函分析; 郭英新(1969—),男,山東新泰人,副教授,博士,主要研究方向: 控制理論、控制工程、神經(jīng)網(wǎng)絡(luò)。

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.