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

馬國正

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

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

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

1 法向量夾角的熵

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

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

1.1 法向量估計準則

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

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

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

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

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

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

1.2 法向量夾角的計算

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

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

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

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

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

1.3 基于法向量夾角的熵

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

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

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

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

3 實例分析

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

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

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

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

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

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

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

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

4 結 語

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

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

［1］孫肖霞，孫殿柱，李延瑞，等.反求工程中測量數據的精簡算法［J］.機械設計與制造，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］張飛飛.點云數據簡化及三維曲面重構［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］.計算機應用，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］鄭德華.點云數據直接縮減方法及縮減效果研究［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索引實現曲率自適應點云簡化算法［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］張有亮，劉建永，付成群，等.新的點云數據精簡存儲方法［J］.計算機應用，2011，31（5）：1 255－1 257（Zhang Youliang，Liu Jianyong，Fu 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