侯競夫

（諾丁漢大學(xué)，英國諾丁漢，NG7 2RD）

0 引言

激光雷達（LIDAR）作為觀測技術(shù)的一種，其可以通過激光掃描得到距離、角度等龐大的數(shù)據(jù)，進而通過算法來分析觀測對象的形狀、結(jié)構(gòu)，構(gòu)建出三維圖形。激光雷達相較于其他的觀測技術(shù)具有較高的自動化程度，可以對地表紋理信息不符合要求的區(qū)域進行數(shù)據(jù)測量[1]。值得注意的是，激光雷達掃描所得數(shù)據(jù)信息量龐大，而且相互交錯，進行算法分析難度較高，目前主要通過Delaunay三角剖分算法來完成激光雷達掃描所得數(shù)據(jù)的分析，這種算法類型構(gòu)建出了三角網(wǎng)格模型，具有“元規(guī)則”、“最大最小角規(guī)則”等基本原理，進行數(shù)據(jù)分析時可以有效避免尖銳內(nèi)角的產(chǎn)生，確保了數(shù)據(jù)分析結(jié)果的準確性，但考慮到激光雷達掃描所得數(shù)據(jù)復(fù)雜程度高等問題，采用這種模型進行數(shù)據(jù)分析的耗時較長，需要積極探索合適的手段進行網(wǎng)格模型的簡化，進一步縮短計算耗時、降低存儲要求[2]。

國內(nèi)外就網(wǎng)格模型的簡化研究已經(jīng)取得不錯進展，如國外學(xué)者ECK就曾提出將小波技術(shù)用于網(wǎng)格模型的簡化，Schroeder提出了刪除頂點進行網(wǎng)格模型優(yōu)化的手段，均取得良好的應(yīng)用效果[3]。頂點是網(wǎng)格模型的重要單位，采用Delaunay三角剖分法進行數(shù)據(jù)分析時，需要搭配一定數(shù)量的頂點，進行網(wǎng)格模型的簡化工作時，可以從頂點去除的角度出發(fā)，即按照相應(yīng)的準則依次將頂點從模型中去除，目前提出并得到應(yīng)用的頂點去除準則有Schroeder的平面準則、Hamann的曲率準則[4]，本文討論了常見的網(wǎng)格簡化算法和網(wǎng)格簡化過程中的部分基本準則，并且展望了針對激光雷達數(shù)據(jù)處理的Delaunay三角網(wǎng)格簡化算法的發(fā)展。

1 激光雷達數(shù)據(jù)的Delaunay三角網(wǎng)格簡化算法的研究意義

網(wǎng)格簡化算法不僅僅局限于激光雷達掃描所得數(shù)據(jù)的簡化，其他計算機圖像學(xué)中也有關(guān)于這方面的應(yīng)用，以至于可以高效率、低成本地呈現(xiàn)出圖像，供給人們了解研究對象，甚至與研究對象之間進行交互。針對目前激光雷達數(shù)據(jù)處理使用到的Delaunay三角網(wǎng)格模型，其目的是對收集到的數(shù)據(jù)進行處理并進行三維實體呈現(xiàn)，但實際激光雷達收集到的數(shù)據(jù)相對較大，利用這種方法進行處理，最終會得到數(shù)十萬個、數(shù)百萬個甚至上億個三角網(wǎng)格，如此龐大的數(shù)據(jù)量，對于進行計算處理的計算機的數(shù)據(jù)分析功能、顯示功能以及存儲功能來說都是巨大的挑戰(zhàn)。就目前關(guān)于三角網(wǎng)絡(luò)算法的研究來看，其帶來的問題主要體現(xiàn)在四個方面：

（1）數(shù)據(jù)分析的耗時較長，繪制三維圖形的速度明顯較低；

（2）大量的數(shù)據(jù)需要通過硬件設(shè)施存儲下來，需要占用相當大的存儲空間；

（3）最終得到三維模型的分析、處理、編輯難度較高；

（4）多數(shù)網(wǎng)格簡化方法以網(wǎng)格模型的幾何特性和屬性為基準，通常不關(guān)注網(wǎng)格模型的感知逼真度、封閉性、用戶需求。

基于以上問題，進行激光雷達掃描所得數(shù)據(jù)算法分析時，需要積極探索合適的手段，對算法處理的流程進行簡化，確保其處理所得圖像保持較高的真實感。正常情況下虛擬空間中的三維模型都基于多邊形網(wǎng)絡(luò)模型，為了提升其真實度和準確性，都盡可能地希望其組成部分擁有更多的多邊形面片，但構(gòu)成對象的多邊形數(shù)據(jù)越多，數(shù)據(jù)處理時間也就越長，因此對必要的網(wǎng)格模型進行保留，用于計算機的分析計算，其他網(wǎng)格模型則可以予以刪除，激光雷達數(shù)據(jù)的Delaunay三角網(wǎng)格模型也應(yīng)當遵循這一原則進行簡化。其意義主要體現(xiàn)在在[5]：

（1）提高了算法的實時性，特別對于部分情況下的實時動態(tài)顯示；可以通過選擇性地忽略部分細節(jié)，保證前期計算速度，當計算能力足夠時，再逐步補充細節(jié)模型；

（2）減少了計算量，節(jié)約了儲存空間；

（3）可以實現(xiàn)對算法的加速，提高曲面處理和碰撞檢測的能力。

2 常用網(wǎng)格簡化算法

2.1 體數(shù)據(jù)簡化法

體數(shù)據(jù)，又稱格點數(shù)據(jù)。體數(shù)據(jù)與面數(shù)據(jù)的最大差別在于是否包含體細節(jié)，而體素則是體數(shù)據(jù)的最小單元，使用空間體素數(shù)據(jù)緩存的好處是可以直接通過刪除小體積體素來減少數(shù)據(jù)量。因為體數(shù)據(jù)間隔區(qū)域內(nèi)的值可以用距該值最近的格點數(shù)值近似表示，也可使用數(shù)學(xué)方法模擬生成，而小體積體素的信息熵更低，刪除小體積體素所獲得的簡化網(wǎng)格模型更加貼近原網(wǎng)格模型。但是該方法局限性較強，僅適合用于以體素形式儲存的網(wǎng)格模型；如果用于處理非體素網(wǎng)格模型，效率較低，數(shù)據(jù)處理速度較慢。此外，體數(shù)據(jù)簡化法最終獲得的簡化網(wǎng)格質(zhì)量受刪除標準的影響較大。

2.2 頂點刪除法

該方法最早由Schroeder提出，通過遍歷網(wǎng)格模型內(nèi)的所有頂點，選擇重要程度較低的點和三角形刪除，然后重新三角化。具體操作時，首先根據(jù)幾何結(jié)構(gòu)和拓撲結(jié)構(gòu)，將網(wǎng)格模型內(nèi)的所有頂點分為五類：簡單形、復(fù)雜形、邊界形、內(nèi)部邊形和角點形。[16]除復(fù)雜形頂點外，其他類型頂點都可在需要的情況下刪去。圖1展示了五類頂點的基本特征：

圖1 頂點刪除法頂點分類

頂點刪除法計算速度較快，產(chǎn)生的網(wǎng)格質(zhì)量較好。但頂點刪除法只適合于流形網(wǎng)格。因為非流形網(wǎng)格中復(fù)雜頂點的刪除不產(chǎn)生一個空洞，即不可進行重新三角化。而且這種方法改變了原網(wǎng)格的拓撲特征[6]。圖2展示的即是頂點刪除法：

圖2 頂點刪除法

2.3 頂點聚類法

頂點聚類法的基本思路與體素降采樣的思路類似，此方法用一個包圍盒來包圍網(wǎng)格模型，包圍盒的形狀可以是長方體或者球形，將包圍盒分割成若干個區(qū)域并賦予權(quán)值，盡可能地使相似的原始網(wǎng)格模型元素位于同一區(qū)域，而不相似的原始網(wǎng)格模型元素則劃分到不同區(qū)域。然后使用一個特定的代表頂點表示特定區(qū)域內(nèi)的所有點，該代表頂點與所代表區(qū)域內(nèi)所有點的權(quán)值近似等價，使用代表頂點構(gòu)建新的簡化網(wǎng)格模型，減少了點的數(shù)量，從而簡化了原始網(wǎng)格模型。頂點聚類法的優(yōu)點在于可以一次性處理大量頂點，效率較高，而且對于任意網(wǎng)格模型都有不錯的簡化效果。但是該方法將原網(wǎng)格模型分割，改變了原始網(wǎng)格模型的連接結(jié)構(gòu)，其簡化模型可能丟失部分拓撲特征信息[11]。面片聚類法與頂點聚類法的思路和優(yōu)缺點大體相同，只是面片聚類法是選擇相似多邊形進行合并，從而減少面片數(shù)量，達到簡化網(wǎng)格模型的目的。

圖3和圖4分別展示了兩個由頂點聚類法得出的簡化網(wǎng)格模型。圖3中的簡化網(wǎng)格模型未丟失拓撲特征信息；而圖4中的簡化網(wǎng)格模型的拓撲特征發(fā)生了明顯變化。

圖3 拓撲特征信息未丟失的頂點聚類法

圖4 拓撲特征信息丟失的頂點聚類法

2.4 包絡(luò)法

在建立簡化網(wǎng)格后，定義誤差度量，即簡化網(wǎng)格頂點與原網(wǎng)格的距離，設(shè)置需要的距離誤差，構(gòu)造兩個包絡(luò)網(wǎng)格，一個向外偏移，一個向內(nèi)偏移，然后使用兩個包絡(luò)網(wǎng)格作為基準進行簡化。但是包絡(luò)法因為要構(gòu)造兩個額外的包絡(luò)網(wǎng)格，極大地增加了計算量。

而且，在處理多雷達問題時，包絡(luò)法存在信息冗余的問題，因為不同雷達包絡(luò)可能在空間相交，不利于形成統(tǒng)一的雷達網(wǎng)探測態(tài)勢。如果想要解決這個問題，那么就需要依次分析所有的雷達包絡(luò)采樣點，判斷是否有雷達包絡(luò)采樣點同時位于多個雷達包絡(luò)網(wǎng)格模型內(nèi)，必然會極大地增加計算時間和難度，尤其是在三維空間中，雷達包絡(luò)數(shù)據(jù)量更大，采樣點更多，結(jié)構(gòu)更為復(fù)雜，加之可能出現(xiàn)的干擾問題，會使對于雷達包絡(luò)采樣點的判定更加困難。劉彥君等人針對這一問題，提出了基于投影網(wǎng)格的雷達包絡(luò)融合方法，在雷達包絡(luò)相交區(qū)域構(gòu)建小面積網(wǎng)格，對每組相交雷達包絡(luò)對做豎投影和側(cè)投影，過濾得到重疊區(qū)探測點和非重疊區(qū)探測點，從而實現(xiàn)包絡(luò)融合，進而使用包絡(luò)法處理原始網(wǎng)格模型，獲得簡化網(wǎng)格模型。因為投影算法對于構(gòu)建的小面積網(wǎng)格的網(wǎng)格長度和投影策略比較敏感，所以采用標準重疊區(qū)探測點對比庫方式得到最優(yōu)的網(wǎng)格長度，使用成對投影降低計算復(fù)雜度[17]。雖然劉彥君等人的方法受網(wǎng)格長度影響較大，最終得到的包絡(luò)網(wǎng)格質(zhì)量可能并不理想，但該方法可以滿足一般情況下的需求，并且為多雷達包絡(luò)法的進一步優(yōu)化奠定了基礎(chǔ)。圖5展示了基于投影網(wǎng)格的雷達包絡(luò)融合算法的基本思路。

圖5 基于投影網(wǎng)格的雷達包絡(luò)融合算法

此外，在實際應(yīng)用中，往往存在大量的自交網(wǎng)格模型，但是包絡(luò)法處理自交網(wǎng)格模型的能力較弱。針對包絡(luò)法無法處理自交網(wǎng)格模型的問題，張明敏等人提出了一種基于超包絡(luò)的網(wǎng)格簡化算法[19]，可以處理任意類型的網(wǎng)格模型，包括自交網(wǎng)格模型，而且張明敏等人的算法還簡化了包絡(luò)構(gòu)造，減少了計算量。

2.5 漸進網(wǎng)格法

漸進網(wǎng)格法首先使用邊折疊的方式將原始網(wǎng)格模型變?yōu)橐粋€分辨率極低的基網(wǎng)格模型。之后進行頂點分裂操作，即根據(jù)在邊折疊操作中獲得的細節(jié)信息，逐步更新基網(wǎng)格。頂點分裂操作在某種程度上可以視為之前進行的邊折疊操作的逆操作。如果將所有細節(jié)信息用于基網(wǎng)格模型，即可將基網(wǎng)格模型回復(fù)為原始網(wǎng)格模型；如果只使用部分細節(jié)信息，便可以得到一個簡化后的網(wǎng)格模型。圖6展示了邊收縮與點分裂操作。

圖6 邊收縮與點分裂操作

上述過程可以表述如下：

邊收縮過程：

點分裂過程：

這種方法可以有效降低網(wǎng)格模型對儲存空間的需求，實現(xiàn)層次細節(jié)模型。但是漸進網(wǎng)格法在邊收縮過程中，每次都需要搜索選擇刪除的邊，計算時間較長。針對這一問題，谷東東[20]等人優(yōu)化了邊收縮過程中的權(quán)值公式，使?jié)u進網(wǎng)格法可以更加高效地搜索選擇需要刪除的邊。顧耀林等人則在生成基網(wǎng)格時，記錄所有三角形的權(quán)值和細節(jié)，在邊收縮過程中搜索選擇需要刪除的邊時，可以直接根據(jù)之前的記錄讀出最小權(quán)值三角形[21]進行刪除。雖然顧耀林等人的方法需要在每一次邊收縮后修正收縮邊的相鄰三角形權(quán)值，并用權(quán)值重新為三角形排序，但相比于使用全局搜索搜尋需要刪除的邊，這種這種局部調(diào)整耗時較少。

2.6 重新布點法

重新布點法是一種最小誤差簡化算法，該算法的優(yōu)點在于可以根據(jù)需要設(shè)置簡化模型的頂點數(shù)量。該方法在原始網(wǎng)格模型上隨機生成一定數(shù)量的頂點，生成的頂點將作為基準最終生成簡化網(wǎng)格模型，簡化網(wǎng)格模型頂點數(shù)量可自行指定。然后根據(jù)頂點斥力重新劃分原始網(wǎng)格模型上的頂點和生成的簡化網(wǎng)格模型頂點，并進行三角剖分生成過渡網(wǎng)格模型。最終刪除過渡網(wǎng)格模型中的所有原始網(wǎng)格模型頂點，對簡化網(wǎng)格模型頂點進行三角剖分，生成簡化網(wǎng)格模型。但該方法步驟較為繁瑣。Taosong He等人將重新布點法與體數(shù)據(jù)簡化法結(jié)合，提出了一種自適應(yīng)表面生成算法用于網(wǎng)格簡化，但是該方法可能會改變原始網(wǎng)格模型的拓撲結(jié)構(gòu)[17]。

2.7 小波方法

一般情況下，小波方法將原始網(wǎng)格模型分解為兩個部分，第一個部分是只包含原始網(wǎng)格模型最基本要素的極簡網(wǎng)格模型，另一個部分為從極簡網(wǎng)格模型中剔除的原始網(wǎng)格模型細節(jié)，然后通過兩部分的合成生成相應(yīng)的簡化模型。但是小波方法的每個曲面都需要通過小波表達式進行構(gòu)建，這種算法復(fù)雜度較高，而且只可用于具有細分連續(xù)性的網(wǎng)格。雖然改進后地ECK算法可以使用小波表達式構(gòu)建任意網(wǎng)格模型，但是該算法通常只會保留連續(xù)特征區(qū)域，而且因為需要使用調(diào)和映射，計算量很大。但該算法所生成的模型可以在保證過渡和網(wǎng)格質(zhì)量的前提下保持較高的壓縮率，是某些情況下的理想選擇。

3 網(wǎng)格簡化的準則介紹

網(wǎng)格簡化，即通過近似的方式將多邊形網(wǎng)格模型簡化，簡化模型仍具備原網(wǎng)格模型的基本可視特征，但其數(shù)據(jù)量遠小于原始模型。常用方法是通過賦予權(quán)值、定義誤差等方式來評價原網(wǎng)格模型中的元素，然后選擇性地移除重要程度較低、對模型整體影響較小的元素。而評價元素的方式即是所用算法的簡化準則。下面是部分常用的簡化準則：

（1）通過計算頂點與平均平面的距離。距離越小，則頂點越密集，信息熵越大，頂點的重要性越低。該簡化準則常見于頂點刪除法中。

（2）通過頂點曲率來判斷元素的重要程度。對于曲線曲面造型，曲率越低，則區(qū)分度越低，也就越不重要。

（3）通過特征角判斷元素的重要程度。給定特征角角度后，則該特征角內(nèi)包含最多的原始網(wǎng)格模型信息，相對的，其他非特征邊及頂點中的信息相對較少，所以重要程度偏低，可以刪除。此外，還可以通過定義頂點的特征角進行簡化，其主要特點是在所有包含該頂點的三角面中，該頂點的特征角夾角最大，信息量最豐富。而頂點的特征角越大，說明其包含的信息越豐富，所以可以刪除特征角較小的頂點，實現(xiàn)網(wǎng)格簡化的目的[7]。

（4）使用二次誤差度量評價元素的重要程度。對于一個頂點u，頂點u連接的的邊的集合為S，設(shè)頂點集合T，頂點u與集合T中的頂點都可通過集合S可達，設(shè)頂點集合T中所有頂點的有序三角形環(huán)的集合為N，計算頂點u與集合N中所有有序三角形環(huán)的距離平方和，作為邊折疊簡化的評價方法。該算法時間復(fù)雜度較低，且擁有優(yōu)異的簡化質(zhì)量。

4 激光雷達數(shù)據(jù)Delaunay三角網(wǎng)格簡化算法的發(fā)展展望

4.1 提高簡化后的外觀相似性

網(wǎng)格簡化的目的是通過近似的方式將多邊形網(wǎng)格模型簡化并保留原網(wǎng)格模型的基本可視特征。但現(xiàn)有的多數(shù)網(wǎng)格簡化方法并不是特別關(guān)注外觀相似性，比如頂點聚類法得出的簡化模型就可能發(fā)生變形。若簡化模型與原網(wǎng)格模型的可視特征差異較大，最終會影響激光雷達探測的準確性。

4.2 提高簡化后的實時性

激光雷達數(shù)據(jù)的處理對于實時性有較高要求?？梢钥紤]優(yōu)化模型數(shù)據(jù)結(jié)構(gòu)和存儲方式，提高數(shù)據(jù)存儲與索引的速度，減少耗時。也可進一步提高簡化模型的壓縮率，略去次要細節(jié)，采用漸進顯示的方式，提高簡化模型的實時性。

4.3 提高簡化后的通用性

針對已知的特定網(wǎng)格模型進行簡化處理并不困難，但激光雷達需要面對的環(huán)境較為復(fù)雜、突發(fā)情況較多，往往難以預(yù)測。因此，設(shè)計出可使用于任何網(wǎng)格模型的通用簡化算法有著重要意義。而且，因為數(shù)據(jù)量大且復(fù)雜，又受到計算機硬件技術(shù)的限制，對激光雷達的數(shù)據(jù)處理通常很難在單一設(shè)備上完成，往往需要使用分布式技術(shù)或并行技術(shù)協(xié)同多設(shè)備運作，而開發(fā)通用簡化算法有助于減少設(shè)備間的通信開銷，提高激光雷達數(shù)據(jù)處理的效率，減少數(shù)據(jù)處理時間。

5 結(jié)束語

激光雷達數(shù)據(jù)的Delaunay三角網(wǎng)格分析方法尚存在一定的不足，需要積極研究并探索簡化手段。這對于計算機處理速度的提升、內(nèi)存空間的節(jié)省都具有積極作用，也有利于推動激光雷達測量技術(shù)的革新。