基于誤差熵的點云簡化方法

馬國正

1 華東交通大學土木建筑學院，南昌市雙港路808號，330013

近年來三維激光掃描技術(shù)得到了廣泛的應(yīng)用，但大量的點云會造成計算機運算的負擔，在不影響數(shù)據(jù)整體使用效率的情況下，需要對點云進行簡化。衡量點云簡化算法的優(yōu)劣，并不能只看精簡速度或精簡率［1］，而要看簡化后點的利用效率。因此，應(yīng)該從精度、簡度和速度等方面來衡量點云精簡的質(zhì)量。

對點云精簡的研究有很多，如利用三角網(wǎng)提出的Delaunay三角化點云簡化［2］。文獻［3］提出非均勻網(wǎng)格方法的點云簡化，文獻［4］提出保留邊界點的點云簡化方法，文獻［5］提出在設(shè)定數(shù)據(jù)重采樣間隔的情況下可以對其進行直接縮減。根據(jù)曲率變化的情況也可對點云進行精簡，即曲率變化大的區(qū)域保留的點較多，曲率變化小的區(qū)域保留的點較少［1］。由于曲率變化決定了目標表面的特征狀況，因此可根據(jù)曲率狀況來實現(xiàn)點云的自適應(yīng)精簡［6］。文獻［7］給出僅適用于樣條曲面模型重建的點云精簡算法，張有亮等［8］提出扇形網(wǎng)格法點云精簡算法，但點云簡化很難完全保證精度、簡化率和速度上都達到最優(yōu)。本文在三者達到平衡的前提下，提出了自適應(yīng)點云簡化方法，即在突變區(qū)域簡化得少，近似平面區(qū)域簡化得多。為了在保證簡化速度的前提下，減小表面特征表示的誤差，同時又不影響表面特征的描述，本文將通過計算法向量夾角的熵來評價表面突變狀況。熵越大，局部曲面變化越明顯；熵越小，局部曲面變化越不明顯。因此，可使用法向量夾角的熵來描述表面的特征狀況，根據(jù)不同的表面設(shè)置不同的簡化率，從而實現(xiàn)自適應(yīng)的點云簡化。

1 法向量夾角的熵

基于誤差熵點云簡化的基本原理是對基于點云法向量夾角熵的計算，具體計算流程如圖1所示。

圖1 局部熵算法流程圖Fig.1 The flow chart of the local entropy algorithm

1.1 法向量估計準則

法向量計算方法有很多種，包括主元分析法［9］、加權(quán)PCA 方法［10］、基于移動最小二乘重建局部參考平面的法向量估計［11］、基于魯棒移動最小二乘（RMLS）重建局部參考平面的法向量估計［12］和基于三角網(wǎng)和PCA 組合的法向量估計［13］等。本文利用經(jīng)典的PCA 方法來估計點的法向量。假設(shè)采樣點P的鄰近點為Pi＝［xi yizi］，采樣點P的3×3協(xié)方差矩陣為：

其中，為P的鄰近點Pi的均值，即為鄰近點的重心，如圖2（a）所示，協(xié)方差矩陣的分析如圖2（b）所示。

圖2 鄰近點的重心及協(xié)方差分析Fig.2 Neighboring nodes’center，and analysis of covariance

對式（1）進行特征值分解，得到特征值λ0、λ1、λ2對應(yīng)的特征向量為V0、V1、V2。特征值表示的是鄰近點Pi（i∈m）遠離重心的情況：

假設(shè)λ0＜λ1＜λ2，則采樣點P的切平面T（X）表示為：

式中，V0近似于采樣點P的法向量。

1.2 法向量夾角的計算

通過法向量與法向量之間的角度差來評價表面法向量的差異性。假設(shè)點云為X＝［xj yjzj］，利用正交整體最小二乘得到參考平面為：

計算法向量與參考平面的夾角。如果采樣點較多，則相鄰點的法向量接近平行，區(qū)域點的法向量與參考平面的夾角近似相等，無法實現(xiàn)對特征面的探測。為了避免該影響，本文采用分級聚類的方法，即首先搜索初級鄰近點，計算該鄰近點重心區(qū)域的法向量；再進行二次鄰近點搜索，利用第二次區(qū)域鄰近點重心的法向量進行夾角的計算。如圖3所示，對所掃描的點云進行初級鄰近點的搜索，搜索每個球形區(qū)域內(nèi)的點云。假設(shè)第1個球形區(qū)域為C0，第2個球形區(qū)域為C1，第3個球形區(qū)域為C2，球形半徑（搜索半徑）為r，r的大小根據(jù)包圍的點數(shù)決定，每個球形區(qū)域包圍的點數(shù)設(shè)置為40。

圖3 初級鄰近點搜索Fig.3 The searching of the primary adjacent point

假設(shè)每個球形區(qū)域內(nèi)的點表示為Ck＝［xi yizi］，則每個球形區(qū)域的重心為zi］。對于球形區(qū)域之外的點，根據(jù)點到重心的就近原則進行歸屬，如圖3所示。假設(shè)P0、P1、P2為球形外部的點，周邊球形區(qū)域的重心分別為。分別計算P0、P1、P2到每個球形區(qū)域重心的距離，得到P0到為最短距離，則將P0歸屬為C0；P1到為最短距離，則將P1歸屬為C1；P2到為最短距離，則將P2歸屬為C0，從而完成球形外點的歸屬。然后重新計算每個球形區(qū)域的重心，并計算得到每個球形區(qū)域重心的法向量nk。為了確定法向量的方向，需要對法向量進行定向。文獻［9］給出了法向量定向的方法。該方法雖然可以實現(xiàn)法向量的定向，但要耗費大量的運算時間，因此并不合適。由于目標物總是正對著掃描儀，即掃描點到坐標原點的方向向量與該點的法向量之間的夾角存在著全部大于等于90°或小于等于90°，為了實現(xiàn)法向量的定向，將法向量與掃描點到坐標原點的方向向量之間的夾角確定為小于等于90°，即滿足α≤90°。α由式（5）得到：

如果αk≥90°，則nk轉(zhuǎn)化為－nk，從而完成法向量的定向。根據(jù)初級聚類重心進行二次鄰近點的搜索，并計算鄰近點的法向量與式（4）平面的夾角θk：

1.3 基于法向量夾角的熵

如果法向量夾角滿足θk＝θ1＝θ2＝…＝θm′，則HC（θk，θm′）＝Hmax，即當所有法向量方向達到一致時，局部熵達到最大?；诜ㄏ蛄繆A角的局部熵反映了表面的特征狀況，局部熵越大，特征表面越趨向于平面；局部熵越小，特征表面變化越明顯。由于局部熵是分級聚類多個鄰近點的共同貢獻，對少數(shù)點噪聲不敏感，所以基于分級聚類的局部熵具有一定的濾波效果。在設(shè)置一定的分級聚類點數(shù)的情況下，利用局部熵可實現(xiàn)表面特征狀況的描述，同時利用該算法可實現(xiàn)表面特征的提取。

2 基于法向量夾角熵的點云簡化

傳統(tǒng)的點云簡化是對所有的點進行均勻抽稀，該方法雖然可以達到降低點數(shù)的目的，但沒有考慮表面的特征狀況，造成凸凹區(qū)域簡化得較多，不能很好地表現(xiàn)該區(qū)域的特征狀況。因此，比較好的點云簡化原則為：在凸凹區(qū)域簡化得少，在近似平面或光滑區(qū)域簡化得多，這樣既保留了表面的特征狀況，又降低了平面區(qū)域數(shù)據(jù)的冗余，達到了自適應(yīng)點云簡化的目的。本文采用基于法向量夾角局部熵的方法來對表面的特征狀況進行分析，通過對不同的表面狀況設(shè)置合理的簡化率來實現(xiàn)簡化。

根據(jù)式（7），可以得到每個初級聚類區(qū)域的信息熵HC（θk，θm′）。該信息熵如果滿足HC（θk，θm′）≈log（m′），則該鄰近區(qū)域為平面。根據(jù)表面的特征狀況設(shè)置不同的簡化區(qū)間，假設(shè)特征表面凸凹區(qū)域變化比較明顯，則可設(shè)置較小的區(qū)間；如果變化不明顯，則設(shè)置較大的區(qū)間，從而得到適宜的簡化效果。

3 實例分析

為對本文點云簡化方法進行評價，采用Riegl－VZ400掃描儀對具有平面特征的木板和具有曲面特征的球進行掃描，如圖4所示。

圖4 平面和球面的灰色圖像Fig.4 The gray image of plane and sphere

提取圖4中的平面和球面點云，平面點數(shù)為116 251，球面點數(shù)為25 741，總點數(shù)為141 992，設(shè)置平面特征區(qū)域的簡化率為90%，球面特征區(qū)域的簡化率為75%。將該簡化效果與傳統(tǒng)的基于法向量計算的曲率法、格網(wǎng)法、包圍球法進行對比分析，設(shè)置總簡化率為87%，簡化效果如圖5所示，簡化過程中所耗費的時間如表1所示。

圖5 不同方法簡化效果Fig.5 The simplification effect of different method

表1 不同方法簡化時間Tab.1 The time of simplification result with different method

由圖5可知，在曲面特征區(qū)域，本文方法和曲率法保留了較多的點，而格網(wǎng)法和包圍球法簡化得較多，球面出現(xiàn)了零星的空洞，特別是圖5（c）的格網(wǎng)法，球面區(qū)域的空洞現(xiàn)象非常明顯。從表1可以看出，本文方法的簡化速度最快，曲率法雖然也保留了較多的曲面點，但其簡化速度最慢。計算簡化后不同特征區(qū)域的點數(shù)，結(jié)果如表2所示。

表2 不同方法簡化結(jié)果Tab.2 The simplification result of different method

由表2可知，簡化后的總點數(shù)基本相同，本文方法和曲率法保留了較多的球面區(qū)域點、較少的平面區(qū)域點。格網(wǎng)法保留的球面區(qū)域點最少，平面特征區(qū)域點最多。因此，本文方法和曲率法的簡化結(jié)果能夠較好地突出曲面的特征區(qū)域，細節(jié)保留較多。而格網(wǎng)法對于球面特征區(qū)域簡化較多，不利于曲面特征的描述；平面特征區(qū)域保留的點較多，容易造成數(shù)據(jù)冗余。因此，基于表1的簡化速度及基于表2的簡化效果進行綜合考慮，本文方法簡化效果較好，保留了較多的曲面特征點，同時對平面區(qū)域影響不大。

4 結(jié) 語

本文通過分析法向量夾角之間的差別來實現(xiàn)表面特征狀況的歸屬，計算表面法向量夾角的熵，并通過該方法提取不同的特征表面，通過設(shè)置特征表面不同的簡化率來實現(xiàn)自適應(yīng)的點云簡化。

利用適合于大量點云的法向量計算方法，采用分級聚類的方法對區(qū)域點云的法向量進行估計，并對法向量的方向進行定向，根據(jù)法向量方向確定了不同法向量之間的夾角。根據(jù)信息熵的定義，計算法向量夾角的熵，通過計算法向量夾角的熵實現(xiàn)自適應(yīng)點云簡化。通過采集不同特征狀況的點云進行實例分析，證明了本文提出的點云簡化方法效率高、效果好。

［1］孫肖霞，孫殿柱，李延瑞，等.反求工程中測量數(shù)據(jù)的精簡算法［J］.機械設(shè)計與制造，2006（8）：37－38（Sun Xiaoxia，Sun Dianzhu，Li Yanrui，et al.Algorithm of Point Data Direct Reduction in Reverse Engineering［J］.Machinery Design ＆Manufacture，2006（8）：37－38）

［2］張飛飛.點云數(shù)據(jù)簡化及三維曲面重構(gòu)［D］.長春：吉林大學，2012（Zhang Feifei.Simplication and 3DSurface Reconstruction for Point Cloud Data［D］.Changchun：Jilin University，2012）

［3］Lichti D D，Gordon S J.Error Propagation in Directly Georeferenced Terrestrial Laser Scanner Point Clouds for Cultural Heritage Recording［C］.FIG Working Week，Athens，Greece，2004

［4］黃文明，肖朝霞，溫佩芝，等.保留邊界的點云簡化方法［J］.計算機應(yīng)用，2010，30（2）：348－352（Huang Wenming，Xiao Zhaoxia，Wen Peizhi，et al.Point Cloud Simplification with Boundary Points Reservation［J］.Journal of Computer Application，2010，30（2）：348－352）

［5］鄭德華.點云數(shù)據(jù)直接縮減方法及縮減效果研究［J］.測繪工程，2006，15（4）：27－30（Zheng Dehua.The Data Reduction of Point Cloud and Analysis of Reduction Effect［J］.Engineering of Surveying and Mapping，2006，15（4）：27－30）

［6］馬振國.利用KD＿tree索引實現(xiàn)曲率自適應(yīng)點云簡化算法［J］.測繪科學，2010，35（6）：67－69（Ma Zhenguo.A Point Cloud Simplification Algorithm Based on KD＿Tree and Curvature Sampling［J］.Science of Surveying and Mapping，2010，35（6）：67－69）

［7］Sareen K K，Knopf G K，Canas R.Contour－Based 3D Point Cloud Simplification For Modeling Freeform Surfaces［C］.2009IEEE Toronto International Conference，2009

［8］張有亮，劉建永，付成群，等.新的點云數(shù)據(jù)精簡存儲方法［J］.計算機應(yīng)用，2011，31（5）：1 255－1 257（Zhang Youliang，Liu Jianyong，F(xiàn)u Chengqun，et al.New Method for Point Cloud Data Reduction［J］.Journal of Computer Application，2011，31（5）：1 255－1 257）

［9］Hoppe H，DeRose T，Duchamp T，et al.Surface reconstruction from unorganized points［C］.ACM Siggraph，1992

［10］Gross M，Pfister H.Point－Based Graphics［A］／／The Morgan Kaufmann Series in Computer Graphics［M］.San Francisco：Morgan Kaufmann Publishers Inc，2007

［11］Pauly M，Keiser R，Kobbelt L P，et al.Shape Modeling with Point Sampled Geometry［J］.ACM Trans Graph，2003，22（3）：641－650

［12］Fleishman S，Cohen－Or D，Silva C T.Robust Moving Least－Squares Fitting with Sharp Features［J］.Acm Transactions on Graphics，2005，24（3）：544－552

［13］Alliez P，Cohen－Steiner D，Tong Y，et al.Voronoi－Based Variational Reconstruction of Unoriented Point Sets［C］.The Fifth Eurographics Symposium on Geometry Processing，2007