激光雷達數據的Delaunay三角網格簡化算法研究進展分析

侯競夫

（諾丁漢大學，英國諾丁漢，NG7 2RD）

0 引言

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

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

1 激光雷達數據的Delaunay三角網格簡化算法的研究意義

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

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

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

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

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

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

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

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

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

2 常用網格簡化算法

2.1 體數據簡化法

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

2.2 頂點刪除法

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

圖1 頂點刪除法頂點分類

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

圖2 頂點刪除法

2.3 頂點聚類法

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

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

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

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

2.4 包絡法

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

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

圖5 基于投影網格的雷達包絡融合算法

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

2.5 漸進網格法

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

圖6 邊收縮與點分裂操作

上述過程可以表述如下：

邊收縮過程：

點分裂過程：

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

2.6 重新布點法

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

2.7 小波方法

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

3 網格簡化的準則介紹

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

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

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

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

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

4 激光雷達數據Delaunay三角網格簡化算法的發展展望

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

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

4.2 提高簡化后的實時性

激光雷達數據的處理對于實時性有較高要求。可以考慮優化模型數據結構和存儲方式，提高數據存儲與索引的速度，減少耗時。也可進一步提高簡化模型的壓縮率，略去次要細節，采用漸進顯示的方式，提高簡化模型的實時性。

4.3 提高簡化后的通用性

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

5 結束語

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