一種LiDAR點云生成格網DEM的快速算法

李曉紅

(山西省基礎地理信息院，山西太原030001)

一、引 言

機載激光雷達(light detection and ranging，LiDAR)是一種快速獲取高精度地面和地物三維信息的新技術。隨著機載激光雷達技術的高速發(fā)展，獲取的點云數(shù)據(jù)量越來越大。如何處理海量的點云數(shù)據(jù)，并從中提取有用的地形信息和地物信息，是當前急需解決的問題。

DEM有多種表現(xiàn)形式，其中TIN和規(guī)則格網DEM是兩種重要的表達方式。從表達地形信息的角度而言，TIN模型的優(yōu)點是它能以不同層次的分辨率來描述地形表面。規(guī)則格網則具有存儲量小，數(shù)據(jù)結構簡單，便于存儲、管理及分析計算等優(yōu)點，因此該數(shù)字地形模型得到了廣泛的應用。規(guī)則格網文件結構相對簡單，存儲了格網點坐標的最大值、最小值、格網間距、格網點數(shù)及高程值。規(guī)則格網可以直接從離散采樣點據(jù)插值得到，也可以通過不規(guī)則三角網(TIN)數(shù)據(jù)內插得到。本文提出一種將LiDAR點云數(shù)據(jù)構成TIN后快速內插生成規(guī)則格網DEM的算法。

二、DEM的生成方法

DEM可以通過攝影測量的方式生成[1]，但是通過先獲取離散的高程點，再對均勻分布的格網點高程內插生成DEM的方式更為普遍。

插值可以分為整體插值、分塊插值和逐點插值。整體內插是將整個地區(qū)采用高次多項式來表示。由于實際地形是復雜變化多樣的，單用一個多項式難以表述實際地形，因此DEM內插中一般不采用整體函數(shù)內插。局部分塊內插是將地形按照一定的規(guī)則進行分塊，分塊的大小可以根據(jù)地形的復雜程度來確定。對每一塊區(qū)域采用單獨的函數(shù)模型進行擬合內插，不同的分塊單元可用不同的內插函數(shù)，常用的內插數(shù)函數(shù)有線性內插、雙線性內插、多項式內插、樣條函數(shù)、多層曲面疊加法等。逐點內插的本質也屬于局部內插，但它與局部分塊內插也有所不同，它是以內插點為中心，確定一個指定大小的范圍，并通過這個范圍內的點來選定合適的數(shù)學模型去擬合計算內插點的高程。因此，逐點內插的每個內插點都隨著點的位置而變化，每個內插的數(shù)學模型也不一樣，通常逐點內插比局部分塊內插具有更高的精度。

綜合考慮機載LiDAR點云濾波后數(shù)據(jù)特點、生成效率和精度，本文采用逐點內插方法生成DEM。差值算法采用距離倒數(shù)加權插值法，它的基本原理是：對于每一個插值點，可以設置一個距該點最近的指定半徑的范圍，落在該范圍內的點都被定權參與該點插值的計算，具體的定權方式是與距離成反比，距離插值點越遠的點賦予的權值越小，反之距離越近的點賦予的權值越大，如圖1所示。利用TIN中Delaunay可以快速確定一個點一定鄰域范圍內的點，以提高生成DEM效率。

三、算法流程

LiDAR點云生成DEM算法主要分為3個步驟：

1．將原始點云文件轉換為點云流文件

原始點云文件不能滿足流算法的要求，需要將原始點云文件轉換為點云流文件[2]。可根據(jù)點云數(shù)據(jù)內在的空間拓撲信息，將點云數(shù)據(jù)平均分塊、排序插入標識后重新寫入點云流文件，以便流處理算法能夠應用。

圖1 逐點內插法生成DEM

點云流文件的建立主要有3個步驟：

1)遍歷原始點云文件，計算外包矩形，將外包矩形劃分為2k×2k個分塊矩形，構建四叉樹。

2)遍歷原始點云文件，計算每個分塊中包含點云的數(shù)目。

3)再次遍歷原始點云文件，對點云重新排序，并在每個區(qū)塊的最后一點插入結束標識。

2．構建不規(guī)則三角網

采用改進后的逐點插入法[2]對點云流文件進行Delaunay三角剖分。從點云流文件中讀取一個點時，采用逐點插入法進行Delaunay三角剖分，并更新當前的三角網鏈表(用于存儲當前已經生成的三角網)。當從點云文件中讀取到結束標識時，表明當前分塊的點云已經遍歷完畢，將四叉樹(將所有分塊作為葉節(jié)點構建)中的該分塊標記為遍歷完畢。判斷當前三角網鏈表中的三角形是否處于固定狀態(tài)(當遍歷一個分塊后，如果三角形的外包圓沒有與未被遍歷的分塊相交時，認為該三角形處于固定狀態(tài))，如果處于固定狀態(tài)，則輸出到三角網文件，釋放內存;如果處于活動狀態(tài)(如果三角形的外包圓與未被遍歷的分塊相交，則認為三角形處于活動狀態(tài))，則繼續(xù)保留在內存中，等待下一分塊遍歷完畢后繼續(xù)判斷，直到所有分塊讀取完畢，完成三角剖分。

3．插值生成規(guī)則格網DEM

與傳統(tǒng)的DEM插值方法不同，本文所采用的插值方法不是依次尋找規(guī)則格網點的領域點進行內插，而是通過遍歷三角網文件中的三角形，判斷三角形是否包含規(guī)則格網點。如果包含規(guī)則格網點，則利用該三角形的3個頂點采用距離倒數(shù)加權插值法計算格網點高程，并將該格網點的行、列號及高程寫入臨時文件，釋放內存。當三角網文件遍歷完畢后，對生成的所有格網點臨時文件重新組織排序，寫入到統(tǒng)一的DEM格式文件中。這樣做的優(yōu)勢是內存中既不保留三角網數(shù)據(jù)，也不保留生成的格網點數(shù)據(jù)，大大降低了程序內存的使用量。算法流程如圖2所示。

圖2 算法流程圖

四、試驗結果與分析

本文采用了大小為100 MB、包含300萬個點的LiDAR數(shù)據(jù)進行試驗，原始點云數(shù)據(jù)如圖3所示。

圖3 原始點云數(shù)據(jù)

首先將原始點云文件轉換為點云流文件。從原始點云文件轉換為點云流文件共耗時34 s，內存最大使用量2．5MB。

對點云流文件進行Delaunay三角剖分生成TIN，耗時9 s，內存最大使用量2．6MB。生成的TIN如圖4所示。由于基于流的算法讀入數(shù)據(jù)進行處理后馬上釋放內存，只保留很少一部分未固定的數(shù)據(jù)在內存中，所以內存的使用量非常小。

DEM生成參數(shù)進行設置如下：

1)采樣間隔設置：設置采樣間隔為5．0m。

2)TIN邊長閾值：設置為50m(邊長過長的三角形內插獲得的高程值誤差很大)。

3)BIL文件設置：高程所放比例為1．0。

圖4 三角剖分后三角網數(shù)據(jù)

由TIN文件內插生成DEM共耗時3 s，內存最大使用量2．3 MB。DEM的內插同樣采用基于流的算法，判斷完輸入三角形后立即釋放內存，顯著提高了算法效率，并減少了內存使用量。生成的規(guī)則格網DEM如圖5所示。

圖5 DEM生成渲染圖

試驗結果表明，采用本文算法生成規(guī)則格網DEM的效率非常高，內存使用量遠遠低于點云文件本身的大小，驗證了流算法用于海量點云數(shù)據(jù)處理的有效性。同時，本文算法生成的DEM準確性非常高，并且能在多種復雜的地形中保持優(yōu)良的性能。

五、結束語

本文提出了一種LiDAR點云快速生成DEM的算法，首先將海量點云數(shù)據(jù)分塊，對每個分塊分別采用改進的增量式Delaunay三角剖分算法構建不規(guī)則三角網;然后遍歷三角網文件，找到被三角形包含的格網點，采用距離倒數(shù)加權插值法計算格網點高程，存入臨時文件;最后，將所有臨時文件排序生成規(guī)則格網DEM。采用基于流的處理算法，實現(xiàn)了點云分塊處理，解決了普通計算機處理大數(shù)據(jù)量點云內存不足的問題。試驗表明，該算法在處理大數(shù)據(jù)量點云時，效率高，內存占用率低，生成規(guī)則格網DEM的準確性也非常高，能夠應用于實際生產應用中。

[1]MAUNE D F．Digital Elevation Model Technologies and Applications：The DEM Users Manual[M]．[S．l．]：ASPRS，2007．

[2]ISENBURG M，LIU Y，SHEWCHUK J，et al．Streaming Computation of Delaunay Triangulations[C]∥Proceedings of ACM SIGGRAPH 2006．New York：ACM，2006：1049-1056．

[3]ISENBURG M，LINDSTROM P．Streaming Meshes[C]∥Proceedings of IEEE Visualization．Minneapolis：IEEE Computer Society，2005：231-238．

[4]ISENBURGM，LIU Y，SHEWCHUK J，et al．Generating Raster DEM from Mass Points via TIN Streaming[C]∥Proceedings of GIScience’06．Berlin：[s．n．]，2006：186-198．

[5]ISENBURG M，LINDSTROM P，GUMHOLD S，et al．Large Mesh Simplification Using Processing Sequences[C]∥ Proceedings of the 14th IEEE Visualization．Washington DC：[s．n．]，2003．

[6]AGARWAL P K，ARGE L，DANNER A．From LiDAR to Grid DEM：A Scalable Approach[C]∥Proceedings of International Symposium on Spatial Data Handling．[S．l．]：[s．n．]，2006．

[7]CIGNONIP，MONTANIC，ROCCHINIC，et al．External Memory Management and Simplification of Huge Meshes[J]．IEEE Transactions on Visualization and Computer Graphics，2003，9(4)：525-537．

[8]AGARWAL P K，ARGE L，YIK．I/O-Efficient Construction of Constrained Delaunay Triangulations[C]∥Proceedings of the 13th European Symposium on Algorithms．Mallorca， Spain： Springer Verlag， 2005：355-366．