張 春 亢，趙 學 勝，鐘 新 科

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

?

基于三角形驅(qū)動的機載LiDAR數(shù)據(jù)柵格化算法

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

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

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

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

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

1 基于三角形驅(qū)動的流式算法

1.1 算法原理

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

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

1.2 基于直線正負區(qū)判別原理的TIN向GRID轉(zhuǎn)換算法

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

(1)

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

(2)

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

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

圖1 三角形插值為格網(wǎng)節(jié)點示意

2 實驗與分析

2.1TIN向GRID轉(zhuǎn)換算法實驗與分析

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

圖2 TIN向GRID轉(zhuǎn)換效率

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

2.2 流式算法實驗與分析

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

表2 流式算法測試結(jié)果

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

3 結(jié)論

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

[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] 李志林,朱慶.數(shù)字高程模型[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向規(guī)則格網(wǎng)DEM轉(zhuǎn)換的快速算法[J].測繪科學,2005,30(4):76-77.

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

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

2014-06-16；

2014-08-19

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

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

10.3969/j.issn.1672-0504.2015.01.026