基于不規(guī)則三角網(wǎng)的漸進加密濾波算法研究

邵為真 趙富燕 梁周雁

(1.山東科技大學 測繪科學與工程學院, 山東 青島 266000；2.浙江省第一測繪院, 浙江 杭州 310012)

基于不規(guī)則三角網(wǎng)的漸進加密濾波算法研究

邵為真1趙富燕2梁周雁1

(1.山東科技大學 測繪科學與工程學院, 山東 青島 266000；2.浙江省第一測繪院, 浙江 杭州 310012)

在基于點云的地面變形分析中，往往會獲取與地面變形監(jiān)測無關的點云數(shù)據(jù)，如植被、建筑物和電力線等。為了更好的分析地面變形的程度，需要對非地面點進行剔除。本文應用了一種基于不規(guī)則三角網(wǎng)(TIN)的漸進加密濾波算法，并在TerraScan中對該算法進行驗證。結果證明該算法非常適用于地表變形監(jiān)測中濾波處理。

點云 變形分析 TIN 濾波 算法

1 引言

三維激光掃描儀可以快速、高精度、密集地獲取研究對象表面的原始點云數(shù)據(jù)，但是在掃描過程中，對于點的獲取卻是盲目的，凡是激光脈沖掃到的點都會被獲取。所以掃描儀在掃描變形監(jiān)測區(qū)的數(shù)據(jù)時，不僅掃描了變形區(qū)表面的地面點云數(shù)據(jù)，還掃描了與地面變形監(jiān)測無關的地物點數(shù)據(jù)，如植被、建筑物和電力線等[1]。想要對地表進行變形監(jiān)測就需要把地物點剔除，而且地物點剔除的好壞將直接影響監(jiān)測結果，這個將地物點去除只保留地面點的過程稱為濾波。所以點云濾波是地面變形監(jiān)測中點云處理的一項關鍵工作。

目前濾波算法比較多，經(jīng)典的有基于不規(guī)則三角網(wǎng)(TIN)的漸進加密濾波算法、數(shù)學形態(tài)學濾波算法、移動窗口濾波算法、基于坡度變化的濾波算法、移動曲面濾波算法、迭代最小二乘濾波算法等。本文使用的是由Axelsson于2000年提出的一種基于不規(guī)則三角網(wǎng)(TIN)的漸進加密濾波算法[2]。

2 基于TIN的漸進加密濾波算法

2.1 基本原理

該算法的基本思路是：

(1)首先選擇種子點，將區(qū)域內(nèi)的點劃分成單位間距較大的規(guī)則格網(wǎng)，該格網(wǎng)的大小基于該區(qū)域的最大結構類型，比如60米×60米為一個單元；

(2)然后尋找每個格網(wǎng)中的最低點作為初始的種子點，使用這些初始的種子點生成一個稀疏的TIN；

(3)之后將滿足條件的點不斷的加入對TIN加密；

(4)最初，TIN位于這些點的下方，并且TIN的曲率受到參數(shù)的限制。在加密過程中，判斷如果一個點到最近三角面的垂直距離以及該點到最近頂點連線與三角面的最大夾角小于設定的閾值，則將該點加入地面點集合，接著重新計算TIN，然后再對非地面點集合內(nèi)的點進行判別。如此迭代處理逐層加密，直到遍歷完所有的點，不再增加新的地面點為止，把原始的點云數(shù)據(jù)分為地面點和非地面點[3]。

該算法克服了傳統(tǒng)算法只針對某些特定的連續(xù)表面區(qū)域有效的局限性，對于城市地形以及復雜的山區(qū)地形、森林地區(qū)的點云數(shù)據(jù)都具有適用性[4]。

2.2 基于TerraScan的算法分析

TerraScan是芬蘭TerraSolid公司開發(fā)的一套專門處理LiDAR點云數(shù)據(jù)的軟件，根據(jù)對TerraScan中基于不規(guī)則三角網(wǎng)(TIN)的漸進加密濾波算法的分析可知，在利用該算法對點云數(shù)據(jù)濾波時，濾波參數(shù)的設置的恰當與否會對濾波的結果產(chǎn)生重要的影響，其中重要的濾波參數(shù)有最大建筑物尺寸的大小、迭代角、迭代距離和最大地形坡度角等。其中，最大建筑物尺寸可以理解為選取種子點的格網(wǎng)大小，若設置的偏小，則可能將非地面點提取到地面點圖層中，若偏大，則可能漏掉地形復雜處的地面點，一般在地形較陡的山區(qū)設置的參數(shù)較小，在建筑物密集的城區(qū)則設置的參數(shù)較大；迭代角是一個點到三角形最近頂點的連線與這個三角形構成平面的最大夾角值，通常的取值范圍在4-10度，值越小，點云里面起伏的變化越小。在平坦地區(qū)使用小值(接近4.0)，在山區(qū)地形使用較大角度(接近10.0)；迭代距離是迭代時點到三角形平面的最大距離，它可以確保當三角形過大時迭代的起伏不會太大，這樣有助于把低矮的建筑物排除在外，迭代距離過大可能會導致低矮建筑物等錯分到地面點中，迭代距離過小可能會使地勢較陡區(qū)域的地面點而被分到了非地面點[5]，迭代距離還與點云的密度有關，但點云密度較大即點云間距較小時，迭代距離一般設置稍小的值；最大地形角即地形中允許出現(xiàn)的最陡的坡度值，對于地形較陡的區(qū)域設置的參數(shù)應該較大，地勢平坦區(qū)域設置的參數(shù)要小。因此，在對點云進行濾波時，應該針對不同地形選擇不同大小的參數(shù)，當然在選擇參數(shù)時還需要對不同的參數(shù)進行不斷的實驗和比較，最終使濾波效果盡量達到最好[6]。

3 基于TerraScan的算法實例

TerraScan中提供了大量的分類工具，包括分離低點、地面點、孤立點、空中點、建筑物點、模型關鍵點、鐵路點等[7]。在TerraScan進行濾波的過程即為分離點云獲取地面點的過程。

本文選取了一塊既有樹木又有房屋的比較典型的點云數(shù)據(jù)作為實驗數(shù)據(jù)，對其進行點云數(shù)據(jù)濾波。圖1顯示的是未分類的原始點云數(shù)據(jù)，點云個數(shù)為4316999，點云的平均密度是4.3pts/m2。

3.1 分離低點

分離低點即把較低的點從其相鄰的點中分離出來。經(jīng)常用于搜索明顯低于地面的點，這些點可能是錯誤的。分離低點的基本原理是：用一個點的高程值與給定距離范圍內(nèi)的每一個點的高程作比較，如果中心點明顯低于其他點，這個點將被分離出來。

因為分離地面點，選取種子點時選取的是最低點，但當最低點是錯誤點而不是地面點時將會影響分類的效果，所以在分離地面點之前分離低點是有必要的。分離低點的具體操作及參數(shù)設置如表1所示。

表1 分離低點窗口

對實驗數(shù)據(jù)首先選取表1中參數(shù)進行了分離低點操作，然后反復進行了幾次，且每次也改變了相應的參數(shù)，通過截面圖來看分離低點的情況，直到達到了較好的分離結果。圖2顯示了分離低點后某位置點云的截面圖，圖中黑色的點表示未分類的點，紅色為分離出的低點，由圖可以看出成功地將明顯低于周圍點云的三個點分離了出來。

3.2 地面點分類

通過設置最大建筑物尺寸的大小、迭代角、迭代距離和最大地形坡度角等參數(shù)分離地面點。在地面點分類時，針對不同的地形設置不同的參數(shù)，在設置參數(shù)時可以對不同的參數(shù)進行不斷的實驗和比較，最終達到較好的濾波效果。

通過量距工具大致量取了點云中建筑物的長度，測得最大長度不超過30米，通過旋轉(zhuǎn)觀察可知該實驗區(qū)域坡度也不大，所以分離地面點時設置的參數(shù)為：最大建筑物尺寸為30米，迭代角為4度，迭代距離1.4米，最大坡度角為88度。圖3顯示的是濾波的效果圖，其中黃色點為分離出的地面點，黑色點為非地面點，a是濾波后點云俯視圖，b是濾波后點云截面圖。

4 點云濾波的質(zhì)量評價

對于點云數(shù)據(jù)濾波效果的好壞，有定性和定量兩種評價指標[8]。

4.1 定性評價

定性評價是通過濾波完成后點云數(shù)據(jù)的截面圖或生成的DEM情況來觀察濾波結果的好壞，從而評價算法的優(yōu)劣，這種方法是在真實地面點不知道的情況下的一種人工評定方法。圖4(a)是對濾波后的點云數(shù)據(jù)生成的DEM圖，從圖中可以看出比較符合真實地形情況，且很少有毛刺現(xiàn)象，所以濾波效果不錯。圖4(b)是濾波后某位置點云數(shù)據(jù)的截面圖，其中黃色點是地面點，黑色點是非地面點，可以看出有幾個地面點被分在了非地面點中，但是總體濾波效果還不錯。

2003年美國國際攝影測量與遙感協(xié)會下設的第三委員會提出了交叉表的評價體系，如表2所示。

表2 交叉表結構

表中，a表示正確分類的地面點數(shù)，b表示地面點被錯分到非地面點中的個數(shù)，c表示非地面點被錯誤分到地面點中的個數(shù)，d表示正確分類的非地面點數(shù)，e表示參考數(shù)據(jù)中地面點個數(shù)，f表示參考數(shù)據(jù)中非地面點個數(shù)，g表示濾波結果中非地面點數(shù)，h則表示濾波結果中非地面點數(shù)，n表示總點數(shù)。

根據(jù)交叉表結構，可以將誤差定義為三類：

這種評定方法是假設已知實驗數(shù)據(jù)中每個點的真實類別， 但是現(xiàn)實中的需處理的數(shù)據(jù)中點的真實類別是不知道的，所以算法的好壞較難這樣直觀地評價。但是當測區(qū)中點云數(shù)據(jù)的真實點類不知道時，可以將通過人工逐點選擇精確分類數(shù)據(jù)作為參考數(shù)據(jù)。本實驗數(shù)據(jù)不知道點云的真實類別，只能通過人工的逐點編輯進行精確分類，將精確分類后的數(shù)據(jù)作為參考數(shù)據(jù)。由于實驗區(qū)域點云數(shù)據(jù)比較多，全部進行逐點分類非常費時，因此定量評價只選取了一部分數(shù)據(jù)。

使用matlab編程計算一類誤差、二類誤差和總誤差。下面列出了計算第一類誤差的程序代碼：

西南聯(lián)大時期，大家生活都很困難，難以為繼。梅貽琦校長千辛萬苦向教育部要來一筆學生補助金，按規(guī)定，他家四個孩子都有資格申請，可是他卻一個不準沾邊，就是為了避嫌，不讓人說閑話。其實，那個時候他的家用相當拮據(jù)，早已捉襟見肘，寅吃卯糧，可他寧肯舉債，變賣家產(chǎn)，或讓夫人磨米粉，做米糕，提籃小賣去補貼家用，也不涉“瓜田李下”之地。因而他在師生中享有崇高威望，帶領大家共度時艱，培養(yǎng)了大批優(yōu)秀人才，鑄就了中國教育的一段輝煌歷史。

clear all;

clc;

format

first_import=importdata('參考數(shù)據(jù)地面點.txt');

second_import=importdata('濾波數(shù)據(jù)非地面點.txt');

[first_m,first_n]=size(first_import);

[second_m,second_n]=size(second_import);

counter=0;

same_coord=[];

for i=1:first_m

for j=1:second_m

if(first_import(i,1)==second_import(j,1)&&first_import(i,2)==second_import(j,2))&&(first_import(i,3)==second_import(j,3))

counter=counter+1;

%same_coord=[same_coord;first_import(i,:)];

end

end

end

firsterror_percent=counter/first_m

計算的一類誤差是5.3%，二類誤差是0.26%，總誤差為2.3%。從誤差的結果可知這種算法的一類誤差比較大，即將地面點誤分為非地面點的概率比較高，而二類誤差非常小，即將非地面點誤分為地面點的概率非常小。在進行地表的變形監(jiān)測時，如果將非地面點數(shù)據(jù)誤分為地面點對變形監(jiān)測的結果影響比較大，而由于地面點的密度比較大，將地面點誤分為非地面點則對變形監(jiān)測的結果影響相對較小，所以該種算法非常適用于地表變形監(jiān)測中濾波處理。

上面是對使用TerraScan自動濾波算法濾波效果的評價，當然在使用TerraScan濾波時，在自動濾波后還應該通過人工交互的方式進行人工分類，使濾波效果達到滿意的水平。

5 結束語

本文針對三維激光掃描技術在地表變形監(jiān)測中，為剔除多余的非地面點，借鑒了一種基于不規(guī)則三角網(wǎng)(TIN)的漸進加密濾波算法，對一塊典型的數(shù)據(jù)通過TerraScan進行了濾波處理和濾波的質(zhì)量評價，驗證了該算法非常適用于地表變形監(jiān)測中濾波處理。

[1] 丁延輝, 湯羽揚, 周克勤,等. 基于地面三維激光技術的建筑物變形監(jiān)測研究[J]. 北京測繪, 2011(2):4-6.

[2] Peter Axelsson. DEM generation from laser scanner data using adaptive TIN models [J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B4):110-117.

[3] 史建青, 史照良. TerraScan在LiDAR點云濾波中的應用研究[J]. 淮海工學院學報(自然科學版), 2011, 20(3): 46-49.

[4] 曾靜靜. 基于LiDAR點云與CCD影像的建筑物特征提取[D]. 山東青島: 山東科技大學, 2011.

[5] 黃金浪. 基于TerraScan的LiDAR數(shù)據(jù)處理[J]. 測繪通報, 2007(10):13-16.

[6] 蔡慶生. 基于機載LiDAR點云數(shù)據(jù)濾波方法研究[J]. 北京測繪, 2015(2):25-29.

[7] 黃金浪. 基于TerraScan的LiDAR數(shù)據(jù)處理[J]. 測繪通報, 2007, (10): 13-16.

[8] 高志國. 海量點云數(shù)據(jù)濾波處理方法研究[J]. 測繪工程, 2013, 01: 35-38.

The Research of Improved Progressive Triangulated Irregular Network Densification Filtering Algorithm

SHAO Wei-zhen1,ZHAO Fu-yan2,LIANG Zhou-yan1

(1.School of Surveying and Mapping Science and Engineering, Shan dong University of science and Technology, Qingdao Shandong 266000, China；2.The First Surveying and Mapping Institute of Zhejiang Province, Hangzhou Zhejiang 310012,China)

The point cloud data is usually irrelevant to ground deformation monitoring was captured in ground deformation analysis based on point clouds, such as vegetation, bulidings and power line, etc. In order to distinguish the degree of ground deformation effectively, non-terrain point should be rejected. This paper employ the filtering algorithm based on Triangular Irregular Networks, and verify the algorithm in TerraScan. The results well demonstrate this algorithm apply to the filtering of ground deformation monitoring.

point cloud; deformation analysis; TIN; filtering; algorithm

2016-06-14

P221+.1

B

1007-3000(2016)06-5