顧及地形特征的LiDAR點云數據快速處理算法

盧維欣，萬幼川，陳茂霖，秦家鑫，王思穎

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079）

顧及地形特征的LiDAR點云數據快速處理算法

盧維欣1，萬幼川1，陳茂霖1，秦家鑫1，王思穎1

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079）

提出了一種基于地形特征的點云簡化算法，首先根據圖像學差分算子提取點云中的地形特征點，再以地形特征點作為種子點建立TIN模型進行迭代簡化，并對算法中存在的計算效率低下的問題進行優(yōu)化。采用兩組數據進行算法有效性測試，并與經典的距離-高差簡化算法結果進行對比。結果表明，該算法在地形復雜的區(qū)域有更好的簡化效果。

點云；圖像學；地形特征；數據簡化

目前，國內外關于點云簡化方面的研究多是針對逆向工程中較為規(guī)則平滑的點云數據[1-5]，而對地面點云數據的簡化則研究較少，且各有不足[6-8]。本文提出了一種基于特征的點云迭代簡化算法，該算法能有效減少點云冗余，并具有比較高的精度。

1 基于圖像差分算子的地形特征點提取

將規(guī)則DEM視為柵格圖像，將連續(xù)變化的山脊山谷線視為線特征，使用差分算子法進行特征提取，該算法使用一個2×2的窗口對DEM進行掃描，將窗口內最高點標記為山脊點，最低點標記為山谷點[9]。

為了實現(xiàn)上述算法，同時提高點云數據的處理效率，根據格網長度lgrid對整個測區(qū)進行二維劃分，即

式中，（Xmax，Xmin）、（Ymax，Ymin）分別為測區(qū)的橫縱坐標最大最小邊值；M、N分別為格網的行列數；lgrid的大小與簡化精度并無直接聯(lián)系，但是適當選擇格網長度能減少數據冗余并提高算法效率。

判斷點云中每個離散點所在的網格，將格網中心點作為該格網的代表點，使用格網內所有點按距離倒數加權平均法[10]內插獲取其高程，依次遍歷所有格網可建立原始點云的概略DEM。根據概略DEM得到的山脊山谷點為一系列的格網，而非原始點云，根據山脊（山谷）點的局部最高（低）特性，對標記為山脊的格網選其中最高點作為山脊點，同樣，標記為山谷的格網則選其中最低點。山脊線提取過程如圖1所示。

圖1 特征點提取過程

2 顧及特征的點云迭代簡化

點云簡化需滿足在失真最小的情況下最大限度地減少數據量的原則，即在局部地形中起伏越大的點越有可能保留下來，而變化不明顯的點則有可能被剔除。迭代簡化是點云簡化過程中常用的一種策略，本文提出一種基于特征的迭代簡化思路：以初始特征點集建立TIN模型，將剩余的點分別在該模型中進行內插獲取新的高程值并與原有的高程值進行比較得到高程差值Δh，將所有剩余點的Δh與點云簡化所要求的精度mh進行比較，若均小于mh，則簡化結束；否則將剩余點集中Δh最大的點加入特征點集并重新建網，迭代計算直至達到簡化結束條件（如圖 2）。算法以點云簡化的精度作為迭代結束的閾值，最終得到的簡化點集的精度即為簡化所要求的精度。

圖2 點云迭代簡化切面圖

迭代簡化的算法保證了每次循環(huán)中所加入的均是最滿足精度需求的點，能得到滿足需求的結果點集，然而直接的迭代算法存在執(zhí)行效率低下的問題。算法耗時主要體現(xiàn)在2個方面：① TIN模型內插時查找三角形；② 每次迭代則需重建一次Delaunay三角網。為此，分別提出以KD樹輔助的三角形查找算法以及格網跳進算法來解決上述問題。

KD樹是一種常用的點云組織結構，在點云鄰域查找中起到了非常重要的作用。其特點在于樹的每層都根據該層的分辨器對相應對象作出分枝決策。本文中采用二維KD樹對三角網中每個三角形重心的平面坐標進行組織，每個節(jié)點中保存有該三角形在三角網中的索引號。在對待內插點進行搜索時，首先依據KD樹搜索該點一定范圍鄰域內所有的三角形重心點，并根據向量叉積法[11]快速找到待定點所在的平面三角形，最后使用三角形插值法[10]計算待定點的內插高程值。

Delaunay三角剖分具有區(qū)域性的特性，即在新增、刪除或移動某一頂點時只會影響鄰近的三角形。根據這一特性，當若干個滿足高差條件的點之間的距離足夠遠時，可同時加入到三角網中而互不影響，為了讓每次進行判斷的點滿足距離條件，使用格網跳進的方式進行最佳點的查找（圖3），將格網劃分為4×4（或3×3、5×5等，按實際地形劃分）的分格網并分別編號，編號相同的區(qū)域將在同一個TIN模型下進行判斷，當所有同樣編號區(qū)域判斷完畢，即重新建網并跳轉至下一編號相同區(qū)域；當對某一個格網進行判斷時，只與當前格網內的點進行比較，若當前格網內并沒有滿足條件的點，則予以標記，之后不再判斷。以KD樹輔助的三角形搜索能大幅提高搜索速度，而且對簡化結果并沒有影響，而格網跳進的迭代算法會給數據帶來少量冗余，但相比于其所帶來的速度提升，是可以接受的。

圖3 格網跳進搜索圖（陰影部分將在同一模型下判斷）

3 實驗分析

本文選擇了兩組數據進行算法有效性的測試。實驗區(qū)域內地形起伏明顯，并濾去了植被和房屋，如圖4所示。區(qū)域1為機載點云數據，范圍為3 548 m× 1 405 m ，平均點距為 0.84 m；區(qū)域2為地面激光點云數據，范圍為882 m×929 m ，平均點距為0.30 m。

圖4 濾波后點云數據

區(qū)域1、2分別依據1∶2 000、1∶500的制圖要求進行簡化，根據制圖精度要求[12]，將區(qū)域1與區(qū)域2的簡化精度分別設置為1.0 m和0.5 m。簡化時區(qū)域1格網間隔設為10 m，區(qū)域2設為2 m，簡化結果與距離-高差算法結果進行對比，如圖5所示。在簡化程度大致相同的情況下，距離-高差算法簡化得較為均勻，但對地形沒有針對性。而本文算法則在地形變化劇烈的區(qū)域有明顯加密。從圖6的等高線局部細節(jié)顯示來看，本文算法對地形變化的細節(jié)表達更有優(yōu)勢。

圖5 區(qū)域1簡化結果

圖6 區(qū)域2簡化結果

為了進一步說明本文算法對精度控制的效果，對算法進行精度檢查，采用對所有原始點進行三角網內插的方法來檢查簡化精度，檢查結果如表1所示。從結果來看，本文算法中誤差小于預設精度的點均達到了99%以上，而距離-高差算法分別為92%和94%。從誤差統(tǒng)計結果來看，相對于距離-高差算法，本文算法對山區(qū)地形的簡化擁有更好的精度和穩(wěn)定性。

4 結 語

根據山區(qū)地形的特點，提出一種依據精度要求的地面點云簡化算法，并給出了具體的簡化步驟與算法流程。實驗結果表明，該算法能有效控制點云的簡化精度，在保存了點云的地形特征信息的同時盡量避免冗余，并且算法中自定義閾值的選取問題，有效解決了之前算法中存在的不足，具有一定的實用價值。

[1] Pauly M, Gross M, Kobbelt L P. Efficient Simplification of Point-sampled Surfaces[C].Conference on Visualization, IEEE Computer Society,2002

[2] Xiwei P,Wenming H,Peizhi W, et al. Simplification of Scattered Point Cloud Based on Feature Extraction[C]. 3rd International Conference on. IEEE, 2009

[3] Song H, Feng H Y, Ouyang D. Automatic Detection of Tangential Discontinuities in Point Cloud Data[J]. Journal of Computing andInformation Science in Engineering, 2008, 8(2): 1-10

[4] Song H, Feng H Y. A Global Clustering Approach to Point Cloud Simplification with a Specified Data Reduction Ratio[J].Computer-aided Design, 2008, 40(3): 281-292

[5] Song H, Feng H Y. A Progressive Point Cloud Simplification Algorithm with Preserved Sharp Edge Data[J]. The International Journal of Advanced Manufacturing Technology, 2009, 45(5-6): 583-592

[6] LaFontaine P S. A Data Density Reduction Algorithm for Post-processed Airborne LiDAR Bathymetric Survey Data[D].University of Florida, 2000

[7] 劉慶元, 趙福生, 胡靜波. 機載激光雷達數據簡化算法的研究[J]. 測繪科學, 2010, 35(2): 90-92

[8] 徐景中, 萬幼川, 張圣望. LiDAR 地面點云的簡化方法研究[J].測繪信息與工程, 2008, 33(1): 32-34

[9] Peucker T K, Douglas D H. Detection of Surface-specific Points by Local Parallel Processing of Discrete Terrain Elevation Data[J].Computer Graphics and Image Processing, 1975, 4(4): 375-387

[10] 張祖勛, 張劍清. 數字攝影測量學[M]. 武漢：武漢大學出版社, 1997

[11] 龐明勇, 盧章平. 計算兩凸多邊形的并集多邊形及其面積的計算機算法與實現(xiàn)[J]. 工程圖學學報, 2004, 25(1): 90-94

[12] GB 15967-1995. 1∶500 、1∶1 000 、1∶2 000地形圖航空攝影測量數字化測圖規(guī)范[S].

P237.3

B

1672-4623（2015）04-0041-03

10.3969/j.issn.1672-4623.2015.04.015

盧維欣，碩士，主要研究方向為地面激光點云數據處理。

2014-09-30。

項目來源：國家高技術研究發(fā)展計劃資助項目（2013AA122104-3）；博士點基金資助項目（20130141130003）。