葉珉?yún)?花向紅

1 佛山市城市規(guī)劃勘測設(shè)計研究院，佛山市嶺南大道北62號，528000

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

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

1 點云簡化算法

1.1 地形數(shù)據(jù)簡化原則

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

1.2 點云數(shù)據(jù)曲率計算

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

1）如果是根結(jié)點，從根結(jié)點開始搜索。

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

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

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

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

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

其中，vi為點i法向量，為高斯加權(quán)函數(shù)，h是與點間距離相關(guān)的一個常數(shù)。

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

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

1.3 簡化算法實現(xiàn)步驟

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

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

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

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

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

1）基于K－D Tree搜索各點K鄰域，構(gòu)建點集空間拓?fù)潢P(guān)系；

2）在點集拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，通過移動最小二乘法計算各點曲率；

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

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

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

6）遍歷每個點，輸出簡化后的點云數(shù)據(jù)，算法結(jié)束。

2 簡化結(jié)果定量評價方法

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

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

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

3 實例與結(jié)果分析

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

圖1 原始點云數(shù)據(jù)Fig.1 The original point cloud data

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

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

圖3 傳統(tǒng)方法簡化結(jié)果Fig.3 Result of traditional method

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

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

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

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

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

表2 建模耗時統(tǒng)計Tab.2 Time of modelings

圖4 簡化數(shù)據(jù)建模效果Fig.4 DTM of the simplified data

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

4 結(jié) 語

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

［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］鄭德華.點云數(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）

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

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

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

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

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

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

［10］賀美芳.基于散亂點云數(shù)據(jù)的曲面重建關(guān)鍵技術(shù)研究［D］.南京：南京航空航天大學(xué)，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）