散亂點云去噪與簡化的統一算法

趙京東,楊鳳華,郭英新

(曲阜師范大學 數學科學學院,山東 曲阜 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.