基于局部異常因子算法的三維聲納單幀重建研究

曾騰，張春華，王朋

(1.中國科學(xué)院 聲學(xué)研究所，北京 100190;2.中國科學(xué)院 先進(jìn)水下信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100190;3.中國科學(xué)院大學(xué)，北京 100049)

0 引言

三維聲納能夠獲得三維空間信息，實(shí)現(xiàn)高分辨率的實(shí)時(shí)水聲探測，在海洋資源開發(fā)、海洋地形測繪和水體障礙物探測中有著廣泛應(yīng)用，使得三維聲學(xué)圖像處理的研究變得尤為重要。另外，由于海洋環(huán)境的復(fù)雜性，聲納系統(tǒng)的性能受背景噪聲的限制[1]，除環(huán)境噪聲外，聲速的非線性變化以及水池池壁的反射等因素[2]，都會(huì)使三維成像聲納獲取的點(diǎn)云數(shù)據(jù)存在噪點(diǎn)，直接影響后期三維重建的準(zhǔn)確性和效率。因此，在點(diǎn)云重建之前需要進(jìn)行點(diǎn)云去噪，最大程度地保留目標(biāo)的輪廓信息，去除圖像中的干擾信息。

光斑噪聲通常使用平滑有限沖激響應(yīng)(FIR)濾波器處理，通過對(duì)鄰域像素點(diǎn)的加權(quán)線性組合修復(fù)當(dāng)前像素點(diǎn)，雖然它有較好的去噪平滑效果，但是會(huì)導(dǎo)致圖像模糊，影響目標(biāo)識(shí)別[3-4]。文獻(xiàn)[5]中采用馬爾可夫隨機(jī)場(MRF)模型，利用統(tǒng)計(jì)方法建模和反演技術(shù)進(jìn)行去噪，但這種方式實(shí)現(xiàn)復(fù)雜。閾值法具有實(shí)現(xiàn)簡單、計(jì)算量小、性能較穩(wěn)定、應(yīng)用最廣泛的特點(diǎn)，能夠通過設(shè)定閾值區(qū)分目標(biāo)回波與雜波，就噪聲降低和質(zhì)量改進(jìn)而言，在計(jì)算復(fù)雜性和性能之間有很好的折衷[6-7]。文獻(xiàn)[8]在快速目標(biāo)檢測與追蹤背景下，采用雙閾值方法實(shí)現(xiàn)簡單有效的去噪，但是這種方式很難定義2個(gè)閾值的選擇標(biāo)準(zhǔn)。文獻(xiàn)[9]將閾值固定在最大像素值的22%，直接作用于波束信號(hào)，但閾值選擇過于單一，在去除大部分目標(biāo)以外的噪點(diǎn)外，還會(huì)存在對(duì)目標(biāo)輪廓造成干擾的異常點(diǎn)。

異常點(diǎn)(離群點(diǎn))的定義最早由Hawkins[10]提出，異常點(diǎn)和數(shù)據(jù)集中的其他數(shù)據(jù)產(chǎn)生于不同機(jī)制，在數(shù)據(jù)特性上有很大差異。因此復(fù)雜背景和強(qiáng)雜波干擾下,背景和干擾帶來的非目標(biāo)點(diǎn)被視為異常點(diǎn)，可通過目標(biāo)點(diǎn)和干擾點(diǎn)的差異來進(jìn)行區(qū)分[11-13]。目前異常點(diǎn)檢測主要用于數(shù)據(jù)挖掘領(lǐng)域，主要分為基于統(tǒng)計(jì)的方法、基于深度的方法、基于聚類的方法、基于密度的方法和基于距離的方法[14-15]。當(dāng)數(shù)據(jù)分布密度相差較大時(shí)，基于密度的異常點(diǎn)檢測方法能得到更理想的結(jié)果[16-20]。局部異常因子(LOF)是一種基于密度的異常點(diǎn)檢測方法，其主要思想是基于每個(gè)點(diǎn)的密度及其鄰域點(diǎn)的密度決定該點(diǎn)是否為異常點(diǎn)。該方法簡單直觀，不需要對(duì)數(shù)據(jù)分布有過多的要求。

為了獲得易識(shí)別的目標(biāo)重建結(jié)果，本文首先采用48×48個(gè)聲學(xué)換能器的平面接收陣(512個(gè)通道)，發(fā)射單脈沖聲波信號(hào)進(jìn)行128×128個(gè)波束形成，對(duì)獲取到的目標(biāo)單幀數(shù)據(jù)依次進(jìn)行三維波束成像、最大值濾波和坐標(biāo)系轉(zhuǎn)換，進(jìn)而得到原始點(diǎn)云，提出基于LOF算法的去噪方法對(duì)點(diǎn)云進(jìn)行平滑，并利用一種改進(jìn)的三角網(wǎng)生長方法進(jìn)行單幀重建得到目標(biāo)重建結(jié)果。

1 三維聲納點(diǎn)云模型

1.1 三維波束形成成像技術(shù)

假設(shè)接收平面陣的陣元數(shù)為M×N,陣元各向同性。方位角α與俯仰角β的定義示意圖[21]如圖1所示。

圖1 方位角及俯仰角定義示意圖Fig.1 Definition of azimuth and pitch angles

以遠(yuǎn)場波束形成為背景，其波束形成表達(dá)式為

(1)

利用FFT實(shí)現(xiàn)三維成像聲納的波束形成，在遠(yuǎn)場對(duì)接收信號(hào)的頻域信號(hào)進(jìn)行空域二維FFT的結(jié)果為

(2)

式中：fα為方位角方向上的波數(shù)；fβ為俯仰角方向上的波數(shù)。

根據(jù)上述過程，接收面陣中每個(gè)單元接收到不同距離、不同方向上的回波疊加形成混合信號(hào)，對(duì)48×48個(gè)混合信號(hào)進(jìn)行128×128個(gè)波束形成，從而得到一系列距離切片，如圖2所示，每個(gè)切片是128×128個(gè)點(diǎn)的反射強(qiáng)度信息集合。圖2中：I為數(shù)據(jù)點(diǎn)強(qiáng)度；i表示數(shù)據(jù)點(diǎn)在x軸方向上的波束位置；j表示數(shù)據(jù)點(diǎn)在y軸方向上的波束位置；根據(jù)距離采樣率，L表示數(shù)據(jù)點(diǎn)所在的層數(shù)，即數(shù)據(jù)點(diǎn)到接收陣的距離；O(x0、y0、z0)為視角原點(diǎn)。

圖2 接收陣128×128個(gè)波束示意圖Fig.2 128×128 beams of receiving array

1.2 三維點(diǎn)云的獲取

對(duì)接收面陣接收到的聲學(xué)數(shù)據(jù)進(jìn)行解析，聲學(xué)數(shù)據(jù)點(diǎn)格式可以表示為(i,j,L,I)。每幀信號(hào)得到包含128×128×2 048的體數(shù)據(jù)，其中距離切片數(shù)由聲納成像距離和距離分辨率決定。

由于原始數(shù)據(jù)的數(shù)據(jù)量過于龐大、干擾較多，不易獲取目標(biāo)的真實(shí)輪廓，對(duì)后期的目標(biāo)分割重建操作有著很大的影響。為了改善這種情況，對(duì)體數(shù)據(jù)進(jìn)行最大值濾波，即在每一個(gè)波束方向的不同距離切片中找到強(qiáng)度最大的數(shù)據(jù)點(diǎn)位置和對(duì)應(yīng)強(qiáng)度，從而得到128×128大小的目標(biāo)位置和強(qiáng)度信息矩陣。然后進(jìn)行坐標(biāo)轉(zhuǎn)換，將數(shù)據(jù)點(diǎn)位置映射到三維坐標(biāo)系下，數(shù)據(jù)點(diǎn)強(qiáng)度信息作為色彩信息，生成預(yù)期的點(diǎn)云數(shù)據(jù)。

李棟，山西太谷縣人，1969年出生，中國詩歌學(xué)會(huì)會(huì)員，山西省作協(xié)會(huì)員。1992年發(fā)起創(chuàng)辦太陽谷文學(xué)會(huì)。2010年起觸網(wǎng)寫詩，組詩偶見于《人民文學(xué)》《詩刊》《星星》等處。

(3)

2 算法描述

2.1 基于LOF去噪算法

為了解決閾值方法仍存在異常點(diǎn)的情況，本文針對(duì)三維成像聲納獲取的數(shù)據(jù)密度不均勻且維度較高的特性，在閾值去噪基礎(chǔ)上，采用一種基于密度的異常點(diǎn)檢測方法——LOF檢測算法。為了驗(yàn)證該方法的效性，將聲納數(shù)據(jù)閾值去噪方法和該方法進(jìn)行性能對(duì)比。

LOF算法的主要思想是通過對(duì)每個(gè)點(diǎn)p及其鄰域點(diǎn)的密度判斷該點(diǎn)是否為異常點(diǎn)，如果點(diǎn)p的密度越低，則點(diǎn)p是異常點(diǎn)的可能性越大。假設(shè)在經(jīng)過閾值處理后的點(diǎn)云中取任意一點(diǎn)p，其第k距離dk(p)定義為

dk(p)=d(p,o)，

(4)

式中：d(p,o)為點(diǎn)p與點(diǎn)o之間的距離。(4)式滿足：

1)在輸入點(diǎn)云中至少有不包括p在內(nèi)的k個(gè)點(diǎn)o′∈C(x≠p)，滿足d(p,o′)≤d(p,o)；其中x為點(diǎn)集中的點(diǎn)，C(x≠P)為不包括點(diǎn)P的集合，o′為該集合中的某一點(diǎn)。

2)在集合中最多有不包括p在內(nèi)的k-1個(gè)點(diǎn)o′∈C(x≠p)，滿足d(p,o′)

Nk(p)={q∈D{p}|d(p,q)≤dk(p)}，

(5)

式中：Nk(p)為點(diǎn)p的第k距離鄰域；q為點(diǎn)p的鄰域點(diǎn)；D{p}表示除點(diǎn)p之外的點(diǎn)云集合。

點(diǎn)p到點(diǎn)o的第k可達(dá)距離為

dr(p,o)=max {dk(o),d(p,o)}.

(6)

(6)式意味著離點(diǎn)o最近的k個(gè)點(diǎn)，o到它們的可達(dá)距離相等且等于dk(o)。圖3所示為k=4的可達(dá)距離dr(p1,o)和dr(p2,o)的示意圖。

圖3 k=4的可達(dá)距離示意圖Fig.3 Schematic diagram of reach distance for k=4

根據(jù)上述定義，點(diǎn)p的局部可達(dá)密度表示為

(7)

通過點(diǎn)p的局部可達(dá)距離以及點(diǎn)o(點(diǎn)p的鄰域點(diǎn))的局部可達(dá)距離作比，構(gòu)造如下所示的比較因子，即局部離群因子，進(jìn)而檢測異常點(diǎn)：

(8)

該比值越接近1，表明點(diǎn)p的密度和其鄰域點(diǎn)密度相差不多，p可能與鄰域同屬一簇；該比值越小于1，表明p的密度高于其鄰域點(diǎn)密度，p為密集點(diǎn)；該比值越大于1，表明p的密度小于其鄰域點(diǎn)密度，p越可能是異常點(diǎn)。因此，觀察LOF值選取合適的值，保留取值范圍之內(nèi)的點(diǎn)，即為異常點(diǎn)去除之后的目標(biāo)點(diǎn)云。

2.2 改進(jìn)的三角網(wǎng)生長重建算法

1979年Brassel和Reif提出了三角網(wǎng)生長算法的主要思想，即首先找出點(diǎn)集中相距最短的兩點(diǎn)并連接成一條Delaunay邊，然后按Delaunay邊三角網(wǎng)的判別法則找出包含此邊的Delaunay三角形另一端點(diǎn)，依次處理新生成的邊，直至最終完成[22]。三角網(wǎng)生長法的改進(jìn)實(shí)現(xiàn)多表現(xiàn)在搜尋“第三點(diǎn)”的策略上。為了簡化搜尋過程、降低算法復(fù)雜度，本文利用Delaunay三角網(wǎng)的空?qǐng)A特性進(jìn)行構(gòu)網(wǎng)，即Delaunay三角網(wǎng)中任一三角形的外接圓范圍內(nèi)不會(huì)有其他點(diǎn)存在。

圖4所示為點(diǎn)p1、p2和第3點(diǎn)p3組成的外接圓。從圖4中可以看出，位于外接圓內(nèi)部的p3對(duì)應(yīng)的三角形內(nèi)角角度大于外接圓上p3對(duì)應(yīng)的三角形內(nèi)角角度α2.通過觀察不同點(diǎn)對(duì)應(yīng)的三角形內(nèi)角角度α1、α2和α3，若要實(shí)現(xiàn)外接圓內(nèi)無其他點(diǎn)，則第3點(diǎn)對(duì)應(yīng)的角度最大。

圖4 外接圓與第三點(diǎn)關(guān)系示意圖Fig.4 Relationship between circumcircle and the third point

另外，為了降低擴(kuò)展三角網(wǎng)搜尋第3點(diǎn)的計(jì)算量，在以已有三角形的邊為基準(zhǔn)擴(kuò)展時(shí)，只搜尋邊一側(cè)的點(diǎn)集，將此作為第3點(diǎn)備選點(diǎn)，即第3點(diǎn)與該邊相對(duì)的點(diǎn)關(guān)于該邊異側(cè)。由圖4可以看出，△p1pp2為已有三角形，以邊為基準(zhǔn)擴(kuò)展，新生成的第3點(diǎn)p3與點(diǎn)p關(guān)于邊對(duì)稱。首先需要對(duì)第三邊進(jìn)行直線方程求解，假設(shè)p1坐標(biāo)為(x1,y1,z1)、p2坐標(biāo)為(x2,y2,z2)，根據(jù)直線Ax+By+C=0的一般式方程，代入兩點(diǎn)坐標(biāo)求出系數(shù)：

(9)

之后基于直線方程尋找滿足條件的第3點(diǎn)，假設(shè)點(diǎn)p坐標(biāo)為(x,y,z)，第3點(diǎn)p3坐標(biāo)為(x3,y3,z3)，第3點(diǎn)和點(diǎn)p關(guān)于已求得的直線滿足異側(cè)準(zhǔn)則，即：

(Ax3+By3+C)(Ax+By+C)<0.

(10)

3 實(shí)驗(yàn)結(jié)果及分析

為了檢測算法的實(shí)用性，對(duì)鐵管目標(biāo)進(jìn)行水池實(shí)驗(yàn)。實(shí)驗(yàn)場景環(huán)境參數(shù)如下：聲納系統(tǒng)入水深度2.0 m，目標(biāo)與聲納系統(tǒng)的距離為3.4 m，聲納系統(tǒng)距離消聲壁約5.3 m，聲納接收陣面與水面基本垂直，如圖5所示。目標(biāo)實(shí)物為金屬圓管，長度為2.05 m，直徑約3.0 cm，帶有一定彎度，周身用白布條包裹，兩端有螺絲紋，如圖6所示。

實(shí)驗(yàn)利用48×48陣元數(shù)目的平面陣對(duì)水池?cái)?shù)據(jù)進(jìn)行采集。接收陣形成128×128波束，在0～50 m探測范圍內(nèi)形成2 048個(gè)距離切片。對(duì)鐵管目標(biāo)數(shù)據(jù)進(jìn)行處理，鐵管的原始數(shù)據(jù)經(jīng)過坐標(biāo)轉(zhuǎn)換得到的目標(biāo)點(diǎn)云如圖7所示。由圖7可以看出，由于海洋環(huán)境的干擾，很難辨別出目標(biāo)的輪廓。

圖7 水池中鐵管三維坐標(biāo)系點(diǎn)云Fig.7 Point cloud in Cartesian coordinates of iron tube

對(duì)點(diǎn)云分別使用閾值去噪方法和LOF去噪方法，得到結(jié)果如圖8所示。從圖8(a)中可以看出，閾值去噪后已經(jīng)能看出鐵管的基本輪廓，但是仍會(huì)有一些離群點(diǎn)，容易對(duì)后續(xù)的構(gòu)網(wǎng)結(jié)果造成偏差，模糊目標(biāo)邊界。而圖8(b)中LOF去噪方法設(shè)定閾值去除大于1.2的點(diǎn)后，異常點(diǎn)數(shù)目相比圖8(a)中減少為0，不存在模糊目標(biāo)輪廓的干擾點(diǎn)，只保留了目標(biāo)本身的點(diǎn)，使得目標(biāo)輪廓能很好地體現(xiàn)。

圖8 水池中鐵管去噪后點(diǎn)云Fig.8 Point cloud after denoising of iron tube

對(duì)兩種去除干擾點(diǎn)后的方法分別進(jìn)行改進(jìn)的三角網(wǎng)生長法建網(wǎng)，得到圖9所示的結(jié)果。由圖9可見，閾值去噪方法由于離群點(diǎn)的影響，網(wǎng)格中會(huì)出現(xiàn)不需要的三角形，使得鐵管的邊界被嚴(yán)重混淆。LOF方法相比而言有很好的效果。

圖9 水池鐵管構(gòu)網(wǎng)結(jié)果Fig.9 Triangulation result of iron tube

4 結(jié)論

本文通過實(shí)驗(yàn)數(shù)據(jù)分析，發(fā)現(xiàn)基于LOF算法的去噪方式相比于傳統(tǒng)閾值去噪方式，能夠在保持目標(biāo)真實(shí)輪廓的前提下有效剔除異常噪點(diǎn)，得到更貼合實(shí)際的目標(biāo)輪廓。另外，三維數(shù)據(jù)可視化的實(shí)時(shí)性要求低復(fù)雜度的算法實(shí)現(xiàn)，本文所提出的改進(jìn)三角網(wǎng)方法大大簡化了構(gòu)網(wǎng)過程。然而LOF的閾值設(shè)定需要觀察后手動(dòng)設(shè)定，在將來可以考慮自適應(yīng)地選取適合不同目標(biāo)的閾值。