面向地形數(shù)據(jù)的點(diǎn)云簡(jiǎn)化算法

葉珉?yún)?花向紅

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

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

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

1 點(diǎn)云簡(jiǎn)化算法

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

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

1.2 點(diǎn)云數(shù)據(jù)曲率計(jì)算

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

1）如果是根結(jié)點(diǎn)，從根結(jié)點(diǎn)開(kāi)始搜索。

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

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

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

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

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

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

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

3）曲率計(jì)算。MLS曲面確定后，在投影曲面上利用隱式曲面的曲率計(jì)算公式計(jì)算采樣點(diǎn)的曲率：

1.3 簡(jiǎn)化算法實(shí)現(xiàn)步驟

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

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

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

其中，Ci表示點(diǎn)i的曲率，Cj表示點(diǎn)i鄰近點(diǎn)j的曲率。

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

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

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

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

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

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

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

2 簡(jiǎn)化結(jié)果定量評(píng)價(jià)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

［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］鄭德華.點(diǎn)云數(shù)據(jù)直接縮減方法及縮減效果研究［J］.測(cè)繪工程，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］楊榮華.地面三維激光掃描點(diǎn)云角度分辨率與數(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］武劍潔.基于點(diǎn)的散亂點(diǎn)云處理技術(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］葛源坤.基于曲率特征信息的散亂點(diǎn)云數(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］賀美芳.基于散亂點(diǎn)云數(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）