李 嘉,林 歡,藍(lán)秋萍,馬符訊

(河海大學(xué)，地球科學(xué)與工程學(xué)院，江蘇 南京 210098)

基于深度差的離群點(diǎn)識(shí)別與修正方法

李 嘉,林 歡,藍(lán)秋萍,馬符訊

(河海大學(xué)，地球科學(xué)與工程學(xué)院，江蘇 南京 210098)

離群點(diǎn)的存在會(huì)給點(diǎn)云后續(xù)處理與應(yīng)用帶來干擾，文中針對掃描過程中快速通過的車輛或行人造成的離群點(diǎn)提出基于深度差的識(shí)別與修正方法。分析此類離群點(diǎn)的產(chǎn)生機(jī)理，并運(yùn)用基于球面投影的點(diǎn)云構(gòu)網(wǎng)方法構(gòu)建點(diǎn)云的拓?fù)潢P(guān)系，在此基礎(chǔ)上提出根據(jù)深度差識(shí)別離群點(diǎn)的方法以及兼顧不同點(diǎn)云質(zhì)量的閾值自動(dòng)選擇方法；設(shè)計(jì)了基于二次曲面擬合的點(diǎn)云修復(fù)方法；利用真實(shí)隧道數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了文中方法的有效性和穩(wěn)定性。

離群點(diǎn)；三角構(gòu)網(wǎng)；測距異常；二次曲面擬合；插值

三維激光掃描系統(tǒng)已經(jīng)廣泛應(yīng)用于已建成并投入運(yùn)營的高速公路橋梁和隧道的三維重建與變形檢測中，掃描過程中快速經(jīng)過的車輛和行人會(huì)在掃描點(diǎn)云中留下“斷續(xù)”、“跳躍”的粗差點(diǎn)，也被稱為離群點(diǎn)[1]。本文提出的離群點(diǎn)識(shí)別及修正方法只針對掃描過程中車輛和行人遮擋造成的這類離群點(diǎn)，所以后文提到的離群點(diǎn)特指此類離群點(diǎn)。如圖1所示為三維激光掃描儀掃描的隧道點(diǎn)云，隧道內(nèi)雜亂的點(diǎn)即為快速通過車輛造成的離群點(diǎn)。三維激光掃描儀是按照倒“Z” 字形的順序掃描[2]，快速通行的車輛會(huì)對掃描目標(biāo)產(chǎn)生臨時(shí)遮擋，阻礙激光光束到達(dá)實(shí)際掃描物體表面，從而在移動(dòng)車輛位置產(chǎn)生離群點(diǎn)，并造成被遮擋目標(biāo)表面的數(shù)據(jù)缺失。經(jīng)分析離群點(diǎn)具有如下特性：

1)離群點(diǎn)與相應(yīng)物體表面缺失點(diǎn)在同一視線方向，即兩者的水平角值和豎直角值相等，只是深度值大小不同；

2)離群點(diǎn)的大部分順序掃描鄰近點(diǎn)都在掃描物體表面，離群點(diǎn)與它們的距離較大。

由上述兩特性可以看出，離群點(diǎn)的測距值存在顯著誤差，針對離群點(diǎn)的識(shí)別問題，Knorr和Raymond提出了一種基于距離的檢測方法[3]，該方法是根據(jù)一個(gè)點(diǎn)與其鄰近點(diǎn)的距離來判斷該點(diǎn)是不是離群點(diǎn)，對于均勻點(diǎn)云處理效果較好，但對于密度存在變化的點(diǎn)云可能產(chǎn)生誤判。Breunig設(shè)計(jì)了LOF(局部離群系數(shù))及基于密度的檢測方法[4]，該方法能處理一般的散亂點(diǎn)云數(shù)據(jù)，但需事先給定離群點(diǎn)的密度估計(jì)，對于那些密度大于給定值的離群點(diǎn)則無法被識(shí)別。

圖1 隧道點(diǎn)云

本文在分析上述方法的基礎(chǔ)上不僅設(shè)計(jì)了離群點(diǎn)的識(shí)別方法，而且設(shè)計(jì)了點(diǎn)云修復(fù)方法。將點(diǎn)云進(jìn)行以測站中心為原點(diǎn)的球面投影，并基于水平角、豎直角建立點(diǎn)間拓?fù)潢P(guān)系。根據(jù)相對鄰近點(diǎn)的測距值差異顯著性識(shí)別離群點(diǎn)[5]?；谇娑A連續(xù)性改正離群點(diǎn)測距值，從而完成點(diǎn)云修復(fù)。利用真實(shí)高速公路隧道掃描數(shù)據(jù)驗(yàn)證了離群點(diǎn)識(shí)別方法的有效性，并利用仿真實(shí)驗(yàn)論證了離群點(diǎn)修正算法的準(zhǔn)確性。

1 基于球面投影的三維點(diǎn)云三角構(gòu)網(wǎng)

三維點(diǎn)云的三角網(wǎng)構(gòu)建算法種類繁多，本文采用了張帆提出的基于球面投影的單站地面激光掃描點(diǎn)云構(gòu)網(wǎng)方法[6]。首先利用中心投影將單測站點(diǎn)云投影到以測站中心為球心的球面上，然后根據(jù)球面投影點(diǎn)的水平、豎直角實(shí)施掃描點(diǎn)的構(gòu)網(wǎng)，從而完成單測站三維點(diǎn)云在歐氏空間下的三角構(gòu)網(wǎng)[7]。圖2(a)所示為墻面點(diǎn)云數(shù)據(jù),對墻面點(diǎn)云三角構(gòu)網(wǎng)后得到圖2(b)。

圖2 墻面點(diǎn)云

2 離群點(diǎn)的識(shí)別

圖2(a)為含有離群點(diǎn)的墻面點(diǎn)云數(shù)據(jù)，其中矩形框內(nèi)的點(diǎn)即為離群點(diǎn)。對該點(diǎn)云應(yīng)用前述三角化方法之后得到如圖2(b)所示的墻面三角表面網(wǎng)及局部放大示意圖，圖中離群點(diǎn)與其鄰近點(diǎn)所構(gòu)成的三角形為狹長三角形，其中狹長邊(即包含離群點(diǎn)的三角邊)與激光飛行方向大致相似，說明離群點(diǎn)與其鄰近點(diǎn)具有較大的深度差?；谠撎匦?，本文按照如下思路設(shè)計(jì)了識(shí)別離群點(diǎn)的算法：首先計(jì)算每個(gè)點(diǎn)與其鄰近點(diǎn)的深度值之差，然后選擇出合適的閾值，最后根據(jù)閾值識(shí)別離群點(diǎn)。

2.1 深度差計(jì)算

(1)

(2)

2.2 選擇閾值識(shí)別離群點(diǎn)

(3)

(4)

圖3 中值深度差統(tǒng)計(jì)

三維激光掃描是一種針對三維物體表面的連續(xù)密集采樣，相鄰采樣點(diǎn)的間距較小，相鄰點(diǎn)之間的測距深度變化值也較小。通過對多種人工建筑表面三維激光掃描點(diǎn)云的統(tǒng)計(jì)分析，發(fā)現(xiàn)相鄰激光測點(diǎn)的平均深度差都與所采用掃描儀的單點(diǎn)測距誤差值大小相當(dāng)，即：單點(diǎn)激光測距的隨機(jī)誤差是相鄰點(diǎn)之間深度差異的主要成分。因此，在高密度掃描條件下，實(shí)際落在物體表面上的鄰近點(diǎn)之間的測距深度差具有與單點(diǎn)激光測距誤差相一致的正態(tài)統(tǒng)計(jì)分布規(guī)律，而遠(yuǎn)離物體表面的飛點(diǎn)則相當(dāng)于測距粗差點(diǎn)，在如圖3所示的直方圖統(tǒng)計(jì)中表現(xiàn)為遠(yuǎn)離期望中心的異常分布。根據(jù)正態(tài)分布曲線的性質(zhì)可知，正常的情況下，中值深度差在(E-σ,E+σ)區(qū)間的點(diǎn)數(shù)有68.25%(其中E和σ分別代表期望和標(biāo)準(zhǔn)差，可由式(3)、式(4)計(jì)算得到)；在(E-2σ,E+2σ)區(qū)間的點(diǎn)數(shù)有85.45%；在(E-3σ,E+3σ)區(qū)間的點(diǎn)數(shù)有99.73%。即：對于目標(biāo)表面的正常掃描點(diǎn)而言，其中值深度差大于E+3σ的點(diǎn)出現(xiàn)的概率是接近于0的小概率事件，而遠(yuǎn)離目標(biāo)表面的飛點(diǎn)與鄰近點(diǎn)的深度差則顯著大于E+3σ。所以本文選擇E+3σ作為初步識(shí)別候選離群點(diǎn)的閾值。由于這種方法可能會(huì)將一些階躍邊緣點(diǎn)識(shí)別出來，所以又針對候選離群點(diǎn)設(shè)計(jì)了進(jìn)一步精確確認(rèn)的方法。

圖4 階躍邊緣點(diǎn)與連續(xù)的鄰近點(diǎn)分布對比

圖5 隧道點(diǎn)云

3 離群點(diǎn)的修正

由于離群點(diǎn)與相應(yīng)表面缺失點(diǎn)的水平角值和豎直角值相等，只是深度值大小不同，所以可以根據(jù)鄰近點(diǎn)的深度值插值得到離群點(diǎn)的實(shí)際深度，從而達(dá)到修復(fù)點(diǎn)云的目的。首先根據(jù)已建立的三角網(wǎng)找出每個(gè)離群點(diǎn)的鄰近點(diǎn)集，然后基于離群點(diǎn)的鄰近點(diǎn)集進(jìn)行局部二次曲面擬合，測站中心和當(dāng)前離群點(diǎn)所連直線與二次曲面相交的點(diǎn)即為修正之后的離群點(diǎn)。

二次曲面方程的一般形式為：ax2+by2+cz2+dxy+exz+fyz+gx+hy+kz+1=0，方程所含未知參量較多[11-13]，只取與當(dāng)前離群點(diǎn)有直接邊連接關(guān)系的第一層閉環(huán)點(diǎn)有可能不足以完成曲面擬合，因此，本文在實(shí)驗(yàn)中選取每個(gè)離群點(diǎn)最近的兩圈鄰近點(diǎn)作為二次曲面擬合計(jì)算的樣本點(diǎn)，采用文獻(xiàn)[14]中提到的二次曲面擬合方法計(jì)算二次曲面方程。

如圖6所示，修正離群點(diǎn)P是為了得到點(diǎn)P′(點(diǎn)P′代表相應(yīng)物體表面缺失點(diǎn))，點(diǎn)P′與點(diǎn)P的水平角α和豎直角θ相同，只是深度值ρ不同，而且點(diǎn)P′在擬合的二次曲面上。設(shè)點(diǎn)P′的極坐標(biāo)為(α,θ,ρ)，其歐氏坐標(biāo)表示如下：

圖6 離群點(diǎn)修正示意圖

將上述坐標(biāo)(只有ρ一個(gè)未知值)帶入二次曲面方程求出點(diǎn)P′的坐標(biāo)，遍歷所有離群點(diǎn)完成點(diǎn)云修復(fù)。如圖7(a)所示隧道內(nèi)含有許多離群點(diǎn)，而且隧道表面出現(xiàn)了局部數(shù)據(jù)缺失，運(yùn)用上述算法對該隧道點(diǎn)云處理后得到圖7(b)，觀察發(fā)現(xiàn)離群點(diǎn)被成功修正，隧道表面得到修復(fù)。

圖7 修正前后隧道點(diǎn)云

4 實(shí)驗(yàn)結(jié)果與分析

圖8 完整隧道點(diǎn)云

利用VC++聯(lián)合OpenGL編程實(shí)現(xiàn)了本文提出的離群點(diǎn)識(shí)別及修正算法并應(yīng)用于寧杭高速公路梯子山隧道的一段實(shí)際掃描點(diǎn)云。如圖8(a)所示為單測站隧道掃描點(diǎn)云(約42萬個(gè)點(diǎn))，包括：隧道內(nèi)表面掃描點(diǎn)、拱頂?shù)鯚魭呙椟c(diǎn)、限行錐桶掃描點(diǎn)、以及通行車輛所致離群點(diǎn)和現(xiàn)場測量人員走動(dòng)造成的離群點(diǎn)。應(yīng)用本文提出的離群點(diǎn)識(shí)別算法處理后得到圖8(b)。圖8(b)所示車輛和行人造成的離群點(diǎn)都被識(shí)別出來且單獨(dú)顯示出來，而錐桶和隧道表面的頂燈并沒有識(shí)別為離群點(diǎn)，表明該離群點(diǎn)識(shí)別算法能有效去除階躍邊緣點(diǎn)的影響。圖9(a)和圖9(b)所示為離群點(diǎn)修正之后的隧道點(diǎn)云，觀察可以發(fā)現(xiàn)隧道點(diǎn)云得到了有效的修復(fù)。

圖9 離群點(diǎn)修正后隧道表面

圖10 平面標(biāo)靶和球標(biāo)靶點(diǎn)云

為了驗(yàn)證點(diǎn)云修復(fù)算法的準(zhǔn)確性，本文專門設(shè)計(jì)了一組實(shí)驗(yàn)：對平面標(biāo)靶和球標(biāo)靶掃描過程中故意讓行人通過造成離群點(diǎn)，所得點(diǎn)云如圖10(a)和圖10(b)所示，其中含有孤立和連續(xù)離群點(diǎn)。然后分別采用手工剔除離群點(diǎn)和本文提出的自動(dòng)識(shí)別、修正方法，對處理后的標(biāo)靶點(diǎn)云分別擬合中心坐標(biāo)，并與實(shí)際中心坐標(biāo)對比。如表1所示，擬合中心1和擬合中心2分別代表人工去除離群點(diǎn)后的擬合中心和點(diǎn)云修正之后的擬合中心，對比可發(fā)現(xiàn)人工去除離群點(diǎn)的平面標(biāo)靶與球形標(biāo)靶點(diǎn)云的擬合中心分別偏離實(shí)際坐標(biāo)0.95 mm和0.16 mm，采用本文方法修復(fù)的平面標(biāo)靶和球形標(biāo)靶點(diǎn)云的擬合中心分別偏離實(shí)際坐標(biāo)0.19 mm和0.07 mm。得益于本文提出方法對離群點(diǎn)的自動(dòng)修復(fù)能力，有效保證了掃描點(diǎn)云的完整性，從而使建模精度顯著高于將離群點(diǎn)視為粗差點(diǎn)簡單剔除的處理方法。該實(shí)驗(yàn)也證明了本文提出離群點(diǎn)修復(fù)算法的準(zhǔn)確性。

表1 點(diǎn)云擬合結(jié)果對比 mm

5 結(jié)束語

三維激光自動(dòng)測量過程中由于瞬時(shí)遮擋造成的離群點(diǎn)屬于偶然誤差數(shù)據(jù)，三維激光掃描儀的等間隔均勻采樣工作機(jī)制使得針對此類離群點(diǎn)的自動(dòng)識(shí)別和自動(dòng)修復(fù)成為可能。本文在分析此類離群點(diǎn)測量幾何誤差的基礎(chǔ)上，設(shè)計(jì)了一種基于深度差的離群點(diǎn)識(shí)別方法，以及基于鄰近點(diǎn)幾何分布特性的離群點(diǎn)修正方法。利用隧道點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)，試驗(yàn)結(jié)果表明該方法能夠完成孤立離群點(diǎn)和連續(xù)離群點(diǎn)的自動(dòng)識(shí)別和修復(fù)，能夠有效排除階躍邊緣點(diǎn)對于離群點(diǎn)識(shí)別的影響，并且具有較高的修復(fù)準(zhǔn)確性。該方法適用于原始測站掃描點(diǎn)云的初級去噪應(yīng)用，不僅具有較高的處理效率，而且能夠有效提高點(diǎn)云的完整性和后續(xù)建模的精度。

[1]LESLAR M，WANG J，HU B.Comprehensive Utilization of Temporal and Spatial Domain Outlier Detection Methods for Mobile Terrestrial LiDAR Data[J].Remote Sensing，2011，3(8)：1724-1742.

[2]赫春曉，李浩.基于三維激光掃描數(shù)據(jù)的三維實(shí)景構(gòu)建[J].測繪工程，2013,22(1)：81-85.

[3]KNORR E M，NG R T，TUCAKOV V.Distance-based outliers：algorithms and applications[J].The VLDB Journal-The International Journal on Very Large Data Bases，2000，8(3-4)：237-253.

[4]BREUNIG M M，KRIEGEL H P，NG R T，et al.LOF：identifying density-based local outliers[C]//ACM Sigmod Record.ACM，2000，29(2)：93-104.

[5]高志國.海量點(diǎn)云數(shù)據(jù)濾波處理方法研究[J].測繪工程，2013,22(1)：35-38.

[6]張帆，黃先鋒，李德仁.基于球面投影的單站地面激光掃描點(diǎn)云構(gòu)網(wǎng)方法[J].測繪學(xué)報(bào)，2009，38(1)：48-54.

[7]鄭德華，龐逸群，曹操.基于橢球面投影的散亂點(diǎn)云建立三角格網(wǎng)方法[J].測繪工程，2010，19(4)：19-23.

[8]孫正林，鄒崢嶸，吳愛琴.一種改進(jìn)的 Mean Shift 點(diǎn)云數(shù)據(jù)濾波[J].測繪工程，2011，20(5)：57-59.

[9]浮丹丹，周紹光，徐洋，等.基于主成分分析的點(diǎn)云平面擬合技術(shù)研究[J].測繪工程，2014，23(4)：20-33.

[10]江恒彪.基于實(shí)體化的地面點(diǎn)云建模技術(shù)[J].測繪工程，2014，23(7):30-33.

[11]席高文.二次曲面方程分類與化簡的新方法[J].大學(xué)數(shù)學(xué)，2005，21(5)：129-134.

[12]于志路，姚吉利，馬寧.真彩色點(diǎn)云三維模型方法研究[J].測繪與空間地理信息，2014，37(9)：119-121.

[13]張洪棟，劉翔，時(shí)振偉.影響地面三維激光掃描儀數(shù)據(jù)質(zhì)量的因素分析[J].測繪與空間地理信息，2014，37(9)：183-186.

[14]鄭德華.三維激光掃描數(shù)據(jù)處理的理論與方法 [D].上海：同濟(jì)大學(xué)，2005.

[責(zé)任編輯：劉文霞]

Algorithm of recognizing and correcting the outlier based on depth difference

LI Jia,LIN Huan,LAN Qiu-ping,MA Fu-xun

(School of Earth Science and Engineering，Hohai University，Nanjing 210098，China)

The existence of outlier will bring interference to the following processing and application of the point cloud.For the outlier caused by the fast passing of car or pedestrian during the scans the algorithm of recognizing and correcting is proposed based on the depth difference.First，the mechanism is analyzed by the use of triangulation method based on the spherical projection to build the topology of the point cloud; then an algorithm using the depth difference to identify the outlier is proposed which can select corresponding threshold from different point cloud automatically; finally, a method is designed to repair the point cloud based on the quadratic surface fitting.Using the real tunnel data in the experiment，the results show that the algorithm has higher stability.

outlier;triangulation;ranging exception;quadratic surface fitting;interpolation

2013-09-26;補(bǔ)充更新日期：2014-10-20

國家自然科學(xué)基金資助項(xiàng)目(41201439)

李 嘉(1979-)，男，講師.

P23

：A

：1006-7949(2014)11-0001-06