基于深度差的離群點識別與修正方法

李 嘉,林 歡,藍秋萍,馬符訊

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

基于深度差的離群點識別與修正方法

李 嘉,林 歡,藍秋萍,馬符訊

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

離群點的存在會給點云后續處理與應用帶來干擾，文中針對掃描過程中快速通過的車輛或行人造成的離群點提出基于深度差的識別與修正方法。分析此類離群點的產生機理，并運用基于球面投影的點云構網方法構建點云的拓撲關系，在此基礎上提出根據深度差識別離群點的方法以及兼顧不同點云質量的閾值自動選擇方法；設計了基于二次曲面擬合的點云修復方法；利用真實隧道數據進行實驗，實驗結果驗證了文中方法的有效性和穩定性。

離群點；三角構網；測距異常；二次曲面擬合；插值

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

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

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

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

圖1 隧道點云

本文在分析上述方法的基礎上不僅設計了離群點的識別方法，而且設計了點云修復方法。將點云進行以測站中心為原點的球面投影，并基于水平角、豎直角建立點間拓撲關系。根據相對鄰近點的測距值差異顯著性識別離群點[5]。基于曲面二階連續性改正離群點測距值，從而完成點云修復。利用真實高速公路隧道掃描數據驗證了離群點識別方法的有效性，并利用仿真實驗論證了離群點修正算法的準確性。

1 基于球面投影的三維點云三角構網

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

圖2 墻面點云

2 離群點的識別

圖2(a)為含有離群點的墻面點云數據，其中矩形框內的點即為離群點。對該點云應用前述三角化方法之后得到如圖2(b)所示的墻面三角表面網及局部放大示意圖，圖中離群點與其鄰近點所構成的三角形為狹長三角形，其中狹長邊(即包含離群點的三角邊)與激光飛行方向大致相似，說明離群點與其鄰近點具有較大的深度差。基于該特性，本文按照如下思路設計了識別離群點的算法：首先計算每個點與其鄰近點的深度值之差，然后選擇出合適的閾值，最后根據閾值識別離群點。

2.1 深度差計算

(1)

(2)

2.2 選擇閾值識別離群點

(3)

(4)

圖3 中值深度差統計

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

圖4 階躍邊緣點與連續的鄰近點分布對比

圖5 隧道點云

3 離群點的修正

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

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

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

圖6 離群點修正示意圖

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

圖7 修正前后隧道點云

4 實驗結果與分析

圖8 完整隧道點云

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

圖9 離群點修正后隧道表面

圖10 平面標靶和球標靶點云

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

表1 點云擬合結果對比 mm

5 結束語

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

[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]赫春曉，李浩.基于三維激光掃描數據的三維實景構建[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]高志國.海量點云數據濾波處理方法研究[J].測繪工程，2013,22(1)：35-38.

[6]張帆，黃先鋒，李德仁.基于球面投影的單站地面激光掃描點云構網方法[J].測繪學報，2009，38(1)：48-54.

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

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

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

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

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

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

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

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

[責任編輯：劉文霞]

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;補充更新日期：2014-10-20

國家自然科學基金資助項目(41201439)

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

P23

：A

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