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

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

顧及地形特征的LiDAR點云數(shù)據(jù)快速處理算法

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

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

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

點云；圖像學；地形特征；數(shù)據(jù)簡化

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

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

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

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

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

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

圖1 特征點提取過程

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

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

圖2 點云迭代簡化切面圖

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

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

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

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

3 實驗分析

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

圖4 濾波后點云數(shù)據(jù)

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

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

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

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

4 結 語

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

[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] 劉慶元, 趙福生, 胡靜波. 機載激光雷達數(shù)據(jù)簡化算法的研究[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] 張祖勛, 張劍清. 數(shù)字攝影測量學[M]. 武漢：武漢大學出版社, 1997

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

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

P237.3

B

1672-4623（2015）04-0041-03

10.3969/j.issn.1672-4623.2015.04.015

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

2014-09-30。

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