基于三角形驅動的機載LiDAR數據柵格化算法

張 春 亢，趙 學 勝，鐘 新 科

(1.中國礦業大學(北京)地球科學與測繪工程學院，北京 100083； 2．中國科學院地理科學與資源研究所，北京 100101)

?

基于三角形驅動的機載LiDAR數據柵格化算法

張 春 亢1，趙 學 勝1，鐘 新 科2

(1.中國礦業大學(北京)地球科學與測繪工程學院，北京 100083； 2．中國科學院地理科學與資源研究所，北京 100101)

針對基于TIN的機載LiDAR點云數據插值為GRID過程中，大量TIN數據I/O操作導致的柵格化效率下降問題，提出了基于三角形驅動的點云柵格化流式算法:以基于直線正負區判別原理的TIN向GRID轉換新算法為基礎，通過遍歷三角形模擬流計算實現三角形生成、三角形插值為GRID以及內存釋放，有效避免了TIN數據的I/O操作，并可以提高內存利用率。試驗表明：流式算法顯著提高了點云柵格化效率，為海量點云的柵格化及并行計算提供了一種算法支撐。

機載LiDAR點云；柵格化；I/O操作；流計算；三角形驅動

作為一種高精度、高密度、快速獲取地面三維信息的有效手段，機載LiDAR已成為生成數字地面模型(DTM)的重要工具[1]。而作為DTM的兩種主要表達方式，規則格網(GRID)相對于不規則三角網(TIN)具有數據結構簡單、存儲量小、分析與計算方便等優點[2]。將LiDAR點云柵格化，不但便于其管理與表達，也為其濾波與應用創造了條件，但在柵格化大量LiDAR點云的過程中，因數據的I/O操作時間超過CPU計算時間而成為制約轉換效率的瓶頸[3-5]。在實現較大數據量的點云直接插值為GRID時，只需將點云以一定的數據結構進行劃分重組，即可提高I/O操作的效率，實現點云向GRID的高效轉換[4，5]。與直接插值方法相比，利用點云生成TIN，然后將TIN內插為GRID具有更高的精度和效率[2]。傳統TIN插值為GRID通常采用對生成的TIN數據進行分塊并建立索引，然后逐個判斷待插值格網節點在哪個三角形中，進而計算格網點屬性值的插值策略[6]。因此，在實現基于TIN的點云數據插值為GRID時，需首先將點云剖分為TIN并進行存儲，然后完成TIN向GRID轉換。這種基于格網節點驅動的分步轉換方法雖然易于理解與實現，但轉換過程中涉及中間數據TIN的I/O操作。離散點的數量m(m≥3)與其所構建的三角形數量n滿足條件[7]：m-2≤n≤2m-5。實驗發現，當m較大時，n逼近2m，并且TIN復雜的數據結構決定其數據量要遠大于離散點本身的數據量，所以點云數據比較大時，對計算機內存也有較高要求。通過上述分析，本文引入流計算的思想，以TIN向GRID轉換新算法為基礎，對基于TIN的點云柵格化流程進行了改造，以避免TIN數據的I/O操作，提高柵格化效率及內存利用率。

1 基于三角形驅動的流式算法

1.1 算法原理

流式算法的基本思想為：利用逆向思維，依據直線正負區判別原理，提出一種新的TIN向GRID轉換算法，使構成TIN的每個三角形能夠獨立地實現其內格網節點判斷及其屬性值的計算;同時引入流計算的思想，實現三角形的構建、三角形插值為GRID和內存的釋放在三角形驅動下，以流水線的形式進行組合，從而避免TIN數據的I/O操作并提高內存的利用率。流式算法步驟如下：1)對于點云數據，利用Delaunay三角網構建算法生成一個三角形T;2)利用本文提出的基于直線正負區判別原理的TIN向GRID轉換算法,對三角形T所包含的格網節點進行判斷與插值;3)存儲完成插值的格網節點屬性值，釋放三角形T和格網節點所占用的內存資源;4)重復步驟1-3，直至TIN構建完成，實現所有三角形包含的格網節點的判斷與插值;5)對未包含在任何三角形內的格網節點賦予一個特定屬性值，算法結束。

在流式算法的實現過程中，Delaunay三角網構建算法需要選用三角網生長算法或分治算法，以便在TIN構建過程中不間斷地釋放符合Delaunay三角網準則、不需再優化的三角形，從而形成數據流。本文詳細闡述基于直線正負區判別原理的TIN向GRID轉換算法。

1.2 基于直線正負區判別原理的TIN向GRID轉換算法

存在一直線，假定直線兩邊分別為該直線的正區與負區，有如下公式：

(1)

其中：A=(y2-y1)/(x2-x1)，B=(x2y1-x1y2)/(x2-x1)，(x1,y1)、(x2,y2)為直線上兩點坐標。對于任意一點P(x,y)，可利用下式判斷該點處于直線的正區或負區：

(2)

由式(1)、式(2)可知：平面內兩點的表達式同號時，則兩點位于直線段的同側；表達式異號時，兩點位于直線段的異側。

依據上述直線正負區判別原理，TIN向GRID轉換算法描述如下：1)如圖1，對于構成TIN的一個三角形ABC，根據其頂點坐標，計算其頂點在x與y方向上坐標的最大(小)值xmax(xmin)、ymax(ymin)；2)根據xmin、xmax、ymin、ymax與格網大小，計算格網的起始行Ymin和終止行Ymax以及起始列Xmin和終止列Xmax，則直線x=Xmin、x=Xmax、y=Ymin和y=Ymax相交構成矩形EFGH，計算矩形內格網節點的坐標值；3)將三角形的3個頂點A、B、C與三角形的三邊AB、AC、BC組成三組點線數據A、BC，B、AC和C、AB，對于需要判斷的格網節點P，當點P與三組點線數據中的點相對于該組中的線段運用式(1)與式(2)計算的值都同號時，則點P在三角形ABC內，否則，點P在三角形外；4)根據三角形頂點的坐標及其屬性值內插三角形內格網節點的屬性值；5)重復步驟1-4，遍歷TIN中的三角形，實現TIN向GRID的轉換。

圖1 三角形插值為格網節點示意

2 實驗與分析

2.1TIN向GRID轉換算法實驗與分析

實驗環境為Intel(R)Pentium(R)DCPU(3.40GHz)，1G內存。圖2為本文算法的測試效率，其格網分辨率約1.6個節點/三角形。文獻[6]與本文算法效率對比見表1。分析可知：本文算法的時間復雜度為O(n)，n為構成TIN的三角形個數；本文算法比傳統算法在效率上有明顯的提高，當點云數量或格網分辨率增大時，效率優勢更加突出。因此，在算法效率與時間復雜度方面，本文算法更適合海量點云的處理。

圖2 TIN向GRID轉換效率

點數(個)三角形數(個)行列數(行數×列數)本文算法所用時間(s)文獻[6]算法所用時間(s)843816754800×6000．22．310986218043200×24003．372．5

2.2 流式算法實驗與分析

表2為流式算法測試結果，其中TIN的生成利用文獻[8]提出的分治算法。作為對比，測試了基于格網節點驅動的分步轉換算法的時間，包括TIN的生成、TIN的I/O操作與TIN插值為GRID三部分時間。由測試結果可知：1)TIN的I/O操作占用了分步轉換算法消耗的大部分時間，嚴重制約了轉換算法的效率，可見，避免TIN的I/O操作對于提高點云柵格化效率意義重大；2)因避免了TIN的I/O操作，流式算法在效率上比分步轉換算法有了顯著提高；3)相比于分步測試中TIN構建與TIN插值為GRID的時間和，流式算法多消耗了部分時間，這些時間主要用于內存空間的申請與釋放。另外，因文獻[8]是一種分治算法，其遞歸的特性使其對內存空間要求較高，無法對更大數據量的機載LiDAR點云進行處理。

表2 流式算法測試結果

并行計算是處理海量空間數據的有效方法[3,5]，串行算法并行化的一個難點在于任務分解。分步算法在進行并行化時任務分解較困難，流式算法基于三角形驅動的轉換方式使任務分解相對簡單，點云的柵格化并行處理也易于實現。

3 結論

流計算是避免I/O操作的一種有效方式，本文針對基于TIN的點云柵格化方法存在的缺陷，對柵格化過程進行了改進,即通過遍歷三角形模擬流計算，有效避免了TIN數據的I/O操作，提高了內存利用效率，實現了大量點云的快速柵格化。下一步將著重研究兼顧算法時間和空間性能的 Delaunay三角網剖分算法，用于海量點云數據的柵格化流式處理及并行計算。

[1] KOBLER A,PFEIFER N,OGRINC P,et al.Repetitive interpolation:A robust algorithm for DEM generation from Aerial Laser Scanner data in forested terrain[J].Remote Sensing of Environment,2007,108(1):9-23.

[2] 李志林,朱慶.數字高程模型[M].武漢:武漢測繪科技大學出版社,2000.34-59.

[3] 宋效東,劉學軍,湯國安,等.DEM與地形分析的并行計算[J].地理與地理信息科學,2012,28(4):1-7.

[4] AGARWAL P K,ARGE L,DANNER A.From point cloud to grid DEM:A scalable approach[A].The 12th International Symposium on Spatial Data Handing[C].2006.771-788.

[5] GUAN X F,WU H Y.Leveraging the power of multi-core platform for large-scale geospatial data processing:Exemplified by generating DEM from massive LiDAR point clouds[J].Computers & Geosciences,2010,36(10):1276-1282.

[6] 吳飛,吳凡.TIN向規則格網DEM轉換的快速算法[J].測繪科學,2005,30(4):76-77.

[7] 章孝燦,黃智才,戴企成,等.GIS中基于拓撲結構和凸殼技術的快速TIN生成算法[J].計算機學報,2002，25(11):1212-1218.

[8] 胡金星,潘懋,馬照亭,等.高效構建Delaunay三角網數字地形模型算法研究[J].北京大學學報(自然科學版),2003,39(5):736-741.

2014-06-16；

2014-08-19

高等學校博士學科點專項科研基金項目(20130023110001)

張春亢(1984-)，男，博士研究生，主要研究方向為LiDAR數據處理及應用。E-mail：chkang.chd@163.com

10.3969/j.issn.1672-0504.2015.01.026