邵為真 趙富燕 梁周雁

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

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

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

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

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

點(diǎn)云 變形分析 TIN 濾波 算法

1 引言

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

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

2 基于TIN的漸進(jìn)加密濾波算法

2.1 基本原理

該算法的基本思路是：

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

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

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

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

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

2.2 基于TerraScan的算法分析

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

3 基于TerraScan的算法實(shí)例

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

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

3.1 分離低點(diǎn)

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

因?yàn)榉蛛x地面點(diǎn)，選取種子點(diǎn)時(shí)選取的是最低點(diǎn)，但當(dāng)最低點(diǎn)是錯(cuò)誤點(diǎn)而不是地面點(diǎn)時(shí)將會(huì)影響分類的效果，所以在分離地面點(diǎn)之前分離低點(diǎn)是有必要的。分離低點(diǎn)的具體操作及參數(shù)設(shè)置如表1所示。

表1 分離低點(diǎn)窗口

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

3.2 地面點(diǎn)分類

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

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

4 點(diǎn)云濾波的質(zhì)量評(píng)價(jià)

對(duì)于點(diǎn)云數(shù)據(jù)濾波效果的好壞，有定性和定量兩種評(píng)價(jià)指標(biāo)[8]。

4.1 定性評(píng)價(jià)

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

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

表2 交叉表結(jié)構(gòu)

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

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

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

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

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

clear all;

clc;

format

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

second_import=importdata('濾波數(shù)據(jù)非地面點(diǎn).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

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

上面是對(duì)使用TerraScan自動(dòng)濾波算法濾波效果的評(píng)價(jià)，當(dāng)然在使用TerraScan濾波時(shí)，在自動(dòng)濾波后還應(yīng)該通過人工交互的方式進(jìn)行人工分類，使濾波效果達(dá)到滿意的水平。

5 結(jié)束語

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

[1] 丁延輝, 湯羽揚(yáng), 周克勤,等. 基于地面三維激光技術(shù)的建筑物變形監(jiān)測(cè)研究[J]. 北京測(cè)繪, 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點(diǎn)云濾波中的應(yīng)用研究[J]. 淮海工學(xué)院學(xué)報(bào)(自然科學(xué)版), 2011, 20(3): 46-49.

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

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

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

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

[8] 高志國. 海量點(diǎn)云數(shù)據(jù)濾波處理方法研究[J]. 測(cè)繪工程, 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