面向地形數據的點云簡化算法

葉珉呂 花向紅

1 佛山市城市規劃勘測設計研究院，佛山市嶺南大道北62號，528000

2 武漢大學測繪學院，武漢市珞瑜路129號，430079

三維激光掃描技術獲得的點云數據量越大、點位越密集，對掃描物體的描述則越精確。然而，龐大的點云數據會給后續處理及存儲、傳輸與顯示等造成不利影響，因此需要對原始點云數據進行簡化處理。目前，基于離散點云數據的簡化方法主要分為兩類：均勻簡化方法與基于曲率的簡化方法。均勻簡化方法［1－3］簡單、高效，但是簡化過程沒有顧及點云表面特征，容易造成點云特征信息丟失，因此不適用于特征復雜的點云數據的簡化。基于曲率的簡化方法能夠較好地保留點云特征，但是簡化效率較低，且對于特征簡單和曲率變化較小的區域容易過度簡化，使得簡化后的點云數據出現分布不均勻的現象。對于數據量少、特征簡單規則的模型、零件、建筑物等點云數據，上述傳統簡化方法能夠獲得較好的簡化效果，但是對于海量的、表面特征復雜多樣的地形點云數據，目前并沒有高效的、高精度的簡化方法。對此，本文提出了面向地形數據的點云簡化算法，在高保真、高精度的前提下快速對點云數據進行簡化，并利用定量的評價方法，通過實例驗證算法的可行性。

1 點云簡化算法

1.1 地形數據簡化原則

實用的點云簡化算法應在保證失真較小的前提下，最大限度地壓縮點云數量，且點云的簡化結果能滿足應用的精度要求，同時算法需簡潔，執行效率高。

1.2 點云數據曲率計算

點云數據法向量、曲率等幾何信息能夠很好地反映點云的表面特征，為了使簡化結果能夠較好地保留點云特征，首先需要計算點云數據的幾何信息。點云幾何信息是在點集拓撲結構的基礎上，通過曲面擬合的方法計算得到，點集的拓撲結構一般通過K－D Tree、八叉樹等方法搜索各點K鄰域而建立。點云數據中任意一點P的K鄰域為到該點的歐氏距離最近的K個點所組成的點集，K－D Tree這種數據結構能夠很好地提高空間搜索鄰近點的效率，適用于海量的、空間分布不均勻的離散點集。因此，本文基于K－D Tree進行K鄰域搜索。尋找任意一點P的鄰域的基本流程如下：

1）如果是根結點，從根結點開始搜索。

2）如果是葉子結點，采用遞歸法返回所有與點P鄰近的點，并計算最小距離值。

3）判斷是否分割面另一邊上有點更接近點P，它是通過判斷以點P為球心、最小距離值為半徑的球體與分割平面是否相交來判定的。如果相交，分割面另一邊上可能有鄰近點，那么算法必須向P點所在區域的上層區域回溯，從當前節點所在K－D Tree分支移動到另一分支上去搜尋更近點；如果不相交，那么算法繼續沿著當前K－D Tree分支運行，當前節點的分割平面另一邊整個分支則被淘汰。

4）完成所有節點的搜尋，點P的鄰域點集建立。

所有點的鄰域點集構建完成后，選取移動最小二乘法計算點云數據的曲率信息［4］。移動最小二乘法屬于一種超平面估算方法，通過給定一個局部高階多項式，為采樣點提供一個逼近或插值參考平面，以這個超平面上該點處的曲率作為當前采樣點的曲率。具體步驟包括［5］：

1）向量場估算。法向量是構建點云移動最小二乘曲面的前提。設Q為散亂點云數據，任意一點i∈Q，向量場n（x）可由下式給出：

其中，vi為點i法向量，為高斯加權函數，h是與點間距離相關的一個常數。

2）移動最小二乘曲面投影。移動最小二乘法通過擬合為采樣點提供一個參考曲面，并將采樣點投影到曲面上。以曲面上該點處的曲率作為當前采樣點的曲率，MLS曲面隱式公式為［4］：

3）曲率計算。MLS曲面確定后，在投影曲面上利用隱式曲面的曲率計算公式計算采樣點的曲率：

1.3 簡化算法實現步驟

在獲取點云曲率信息后，首先通過設置一定閾值（本文選取曲率平均值）將其劃分為平緩區域與突變區域。曲率小于閾值，則為平緩區域；反之，則為突變區域。

對于特征簡單的平緩區域，其所包含的特征信息較少，可簡單地根據距離原則進行簡化，無需顧及曲率信息，提高效率的同時避免了過度簡化。兩點空間距離計算公式為：

對于突變區域，特征信息較為豐富，具有各種類型的地形特征點，其共同特點是與周圍鄰近點的曲率差別較大，可以根據此特點進行簡化，保留點云的特征信息。兩點曲率差值計算公式為：

其中，Ci表示點i的曲率，Cj表示點i鄰近點j的曲率。

綜上所述，本文簡化算法的基本原理為：在平緩區域按距離進行簡化，保證整個算法的效率；在突變區域根據曲率簡化，確保曲率變化大的關鍵特征信息不丟失。其具體實現步驟如下：

1）基于K－D Tree搜索各點K鄰域，構建點集空間拓撲關系；

2）在點集拓撲結構的基礎上，通過移動最小二乘法計算各點曲率；

3）根據閾值判斷某點曲率的劃分，如為平緩區域，則執行步驟4）；如為突變區域，則執行步驟5）；

4）計算某點與其鄰域內K個鄰近點的距離，刪除與其距離最近的點；

5）計算某點與其鄰域內K個鄰近點的曲率差值，刪除與其曲率差值最小的點；

6）遍歷每個點，輸出簡化后的點云數據，算法結束。

2 簡化結果定量評價方法

目前，點云數據簡化結果一般通過簡化前后的圖像對比定性地進行評價，簡化精度無法定量分析，評價結果具有較大的主觀性。文獻［6］通過熵理論描述點云數據的特征信息，指出某點熵越大，該點所在局部區域的無序程度越高，該點提供的信息量越大，越能精確反映掃描目標的細節。因此，可以通過計算點云數據的熵值，定量評價簡化結果。曲率能夠很好地反映點云的表面特征信息，結合熵理論及點云數據曲率信息，計算某點熵值的公式為［6－10］：

其中，Ci表示點i的曲率，Cj表示點i鄰近點j的曲率，pi與pj分別為點i及j的曲率概率分布。則點云數據熵值等于各點所含的熵值之和：

點云數據熵值越大，其所含特征信息量越大，對掃描物體的描述越精確。

3 實例與結果分析

使用三維激光掃描儀獲取一地形點云數據，經過去噪、拼接等預處理后如圖1 所示，共由35 282個點組成。

圖1 原始點云數據Fig.1 The original point cloud data

分別使用本文簡化方法與傳統的基于曲率的簡化方法對原始數據進行簡化處理，并設置同一簡化率使得簡化結果具有同樣的點云數目，簡化效果如圖2、3所示。簡化后的點云數據用§2提出的評價方法計算后，結果如表1所示。

圖2 本文方法簡化結果Fig.2 Result of paper’s method

圖3 傳統方法簡化結果Fig.3 Result of traditional method

表1 不同方法簡化結果Tab.1 Results of different methods

通過圖2、3與圖1的對比可以看出，本文方法與傳統方法在大量降低點云數據冗余性的同時，簡化結果整體上都能夠較好地保留點云特征，都具有較高的精度。但是通過圖2、3的對比可以看出，傳統簡化方法在突出明顯特征的同時，對于特征簡單和曲率平緩的區域過度簡化，使得簡化后的點云數據出現了分布不均勻的現象（見圖3（b）方框數據）。而本文方法通過曲率的劃分，不僅提高了簡化效率，而且避免了曲率平緩區域的過度簡化，簡化結果呈均勻分布，較好地保持了數據的完整性。

從表1可看出，在保留相同點數的情況下，本文方法簡化結果的熵值較傳統方法大，說明其細節特征保留較多，對掃描物體的描述更精確。

通過上述實例，驗證了本文提出的面向地形數據的點云簡化方法能夠在大量保留點云特征信息的同時，快速地降低點云數據的冗余性，且算法原理簡單、運行效率高；簡化結果較傳統的簡化方法精度更高，對于海量的、表面特征復雜多樣的地形點云數據具有更好的可行性。

經本文方法簡化后的點云數據可直接應用于建模、成圖等應用，或根據精度、比例尺等要求，對簡化結果再進行多次簡化（表2、圖4），以滿足實際應用的需要。

表2 建模耗時統計Tab.2 Time of modelings

圖4 簡化數據建模效果Fig.4 DTM of the simplified data

由表2、圖4可以看出，利用本文方法簡化后的點云數據建立的數字地面模型都能夠精確反映物體的真實外觀特征，即使經過多次簡化后依然能夠大量保留點云數據的主要特征信息，所建模型依然具有較高的精度，而且簡化后的點云數據大大減少了建模時間，提高了點云數據處理的效率，從另一個角度證明了算法的正確性。

4 結 語

針對地形點云數據量大、表面特征復雜多樣等特點，本文提出面向地形數據的點云簡化算法，并利用基于熵理論的定量評價方法，通過實例驗證該方法能在高保真、高精度的前提下高效地對點云數據進行簡化，具有較高的可行性與普適性。該方法能夠為后續的應用提供有效的數據信息，節約后續工作的處理時間和硬件資源。

［1］Weir D J，Milroy M J，Bradley C，et al.Reverse Engineering Physical Models Employing Wrap－around B－Spline Surfaces and Quadrics［J］.Journal of Engineering Manufacture，1996，210（2）：147－157

［2］Martin R R，Stroud I A，Marshal A D.Data Reduction for Reverse Engineering［R］.Computer and Automation Institute of Hungarian Academy of Science，1996

［3］鄭德華.點云數據直接縮減方法及縮減效果研究［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）

［4］Levin D.Mesh－Independent Surface Interpolation［C］.Geometric Modeling for Scientific Visualization，Berlin，2004

［5］楊榮華.地面三維激光掃描點云角度分辨率與數據處理模型研究［D］.武漢：武漢大學，2011（Yang Ronghua.Research on Point Cloud Angular Resolution and Processing Model of Terrestrial Laser Scanning［D］.Wuhan：Wuhan University，2011）

［6］武劍潔.基于點的散亂點云處理技術的研究［D］.武漢：華中科技大學，2004（Wu Jianjie.Research of Point－Based Techniques on Unorganized Point Cloud［D］.Wuhan：Huazhong University of Science and Technology，2004）

［7］孟慶生.信息論［M］.西安：西安交通大學出版社，1986（Meng Qingsheng.Information Theory［M］.Xi’an：Xi’an Jiaotong University Press，1986）

［8］葛源坤.基于曲率特征信息的散亂點云數據預處理技術研究［D］.成都：西南交通大學，2012（Ge Yuankun.Research on Data Pre－Processing Technology of Scattered Point Cloud Based on Curvatures Feature［D］.Chengdu：Xinan Jiaotong University，2012）

［9］尹婷.三維激光掃描數據處理技術的研究［D］.武漢：武漢理工大學，2010（Yin Ting.Research on 3D Scanning Data Processing Techniques［D］.Wuhan：Wuhan University of Technology，2010）

［10］賀美芳.基于散亂點云數據的曲面重建關鍵技術研究［D］.南京：南京航空航天大學，2006（He Meifang.Research on Key Technologies of Surfaces Reconstruction Based on Scattered Point Cloud Data［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2006）