一種新的SAR圖像目標(biāo)檢測(cè)像素聚類算法

宋文青 徐 瑋 相 飛

(西安電子工程研究所 西安 710100)

0 引言

隨著SAR系統(tǒng)的不斷發(fā)展，其在軍事和民用領(lǐng)域的應(yīng)用越來(lái)越廣泛[1-5]。SAR圖像自動(dòng)目標(biāo)識(shí)別就是SAR圖像的重要應(yīng)用之一[5]。在SAR圖像自動(dòng)目標(biāo)識(shí)別中，目標(biāo)檢測(cè)處理是其首要環(huán)節(jié)，目的是從SAR圖像中快速獲取觀測(cè)場(chǎng)景中的疑似目標(biāo)區(qū)域[6-8]。目前，最為常用且最為穩(wěn)健的目標(biāo)檢測(cè)方法為像素級(jí)別的恒虛警率(Constant False Alarm Rate, CFAR)檢測(cè)算法[6]。SAR圖像經(jīng)CFAR目標(biāo)檢測(cè)后，輸出一幅二值圖像，其中0表示對(duì)應(yīng)像素為雜波背景，1表示對(duì)應(yīng)像素為疑似目標(biāo)點(diǎn)。在高分辨SAR圖像中，目標(biāo)通常由空間上多個(gè)像素點(diǎn)組成，因此需要進(jìn)一步對(duì)二值圖像中的目標(biāo)像素點(diǎn)進(jìn)行空間聚類進(jìn)而才能輸出目標(biāo)層的檢測(cè)結(jié)果[7]。

傳統(tǒng)的目標(biāo)像素聚類方法[6-8]，通常假設(shè)觀測(cè)場(chǎng)景的局部區(qū)域內(nèi)僅存在一個(gè)潛在目標(biāo)，從而可以簡(jiǎn)單地將任意兩個(gè)不超過(guò)預(yù)設(shè)距離的像素點(diǎn)(區(qū)域)進(jìn)行聚類以生成目標(biāo)聚類結(jié)果，其中距離范圍通常設(shè)為目標(biāo)在圖像上的最大投影長(zhǎng)度。然而，對(duì)于多目標(biāo)場(chǎng)景，局部區(qū)域內(nèi)僅有一個(gè)潛在目標(biāo)的假設(shè)條件不再滿足，如果采用相同的聚類策略就會(huì)出現(xiàn)相鄰目標(biāo)的像素聚類成一個(gè)目標(biāo)的情況，進(jìn)而不能準(zhǔn)確輸出目標(biāo)層的檢測(cè)結(jié)果。目標(biāo)像素聚類可以看作是一種空間離散點(diǎn)聚類問(wèn)題。目前，常用的聚類方法有K-means算法、層次聚類算法和基于密度的DBSCAN算法等[9-11]。K-means算法需要目標(biāo)個(gè)數(shù)先驗(yàn)信息，而對(duì)于未知的觀測(cè)場(chǎng)景該信息通常很難獲得[9]。層次聚類算法采用自上而下或者自下而上的順序通過(guò)不斷分裂或合并聚類集合從而獲得最終的聚類結(jié)果[10]。算法復(fù)雜度高，不適合大數(shù)據(jù)集樣本的聚類。DBSCAN算法是一種基于密度的聚類算法[11]，其通過(guò)搜索樣本集中相互密度相連的最大樣本集合以實(shí)現(xiàn)樣本的聚類。算法的聚類結(jié)果受密度參數(shù)MinPts和密度半徑參數(shù)Eps影響較大。

在SAR圖像目標(biāo)檢測(cè)應(yīng)用中，感興趣的目標(biāo)通常為地面車輛目標(biāo)和海洋艦船目標(biāo)等。這些目標(biāo)體上一般存在點(diǎn)散射和分布散射兩種結(jié)構(gòu)，在圖像中分別表現(xiàn)為孤立散射強(qiáng)點(diǎn)和高密度集中的散射點(diǎn)群。進(jìn)一步，目標(biāo)中的分布式結(jié)構(gòu)散射點(diǎn)，經(jīng)SAR圖像目標(biāo)檢測(cè)后，部分散射點(diǎn)可能會(huì)被漏檢，同樣呈稀疏分布狀態(tài)?；诖爽F(xiàn)象，本論文擬采用一種基于DBSCAN聚類和區(qū)域合并相結(jié)合的目標(biāo)像素聚類算法。DBSCAN聚類使圖像中緊密分布的目標(biāo)散射點(diǎn)首先聚成一類，區(qū)域合并進(jìn)一步使這些初步生成的小區(qū)域合并成目標(biāo)層聚類結(jié)果。DBSCAN初步聚類后，參與區(qū)域合并過(guò)程的區(qū)域個(gè)數(shù)大大減少，進(jìn)而能夠大大降低算法的計(jì)算復(fù)雜度，使其適用于SAR圖像目標(biāo)檢測(cè)應(yīng)用。不同于傳統(tǒng)的目標(biāo)像素聚類方法，該區(qū)域合并方法以區(qū)域間的距離作為區(qū)域合并順序的判斷準(zhǔn)則，因此可以一定程度上解決多目標(biāo)環(huán)境下的目標(biāo)像素聚類問(wèn)題。為了進(jìn)一步提升算法的計(jì)算效率，本文在區(qū)域合并過(guò)程中采用一種基于區(qū)域鄰接圖(Region Adjacency Graph, RAG)和最近鄰接圖(Nearest Neighbor Graph, NNG)快速合并方法[10]。該方法利用RAG圖表征區(qū)域間的連接關(guān)系，同時(shí)在NNG圖中搜索待合并的最小權(quán)值邊所連接的兩個(gè)區(qū)域。相對(duì)于RAG圖，NNG圖中邊的數(shù)量大大減少，進(jìn)而能夠降低算法的計(jì)算復(fù)雜度。

論文內(nèi)容安排如下：第1節(jié)中介紹了DBSCAN算法的聚類原理；第2節(jié)介紹了基于RAG和NNG的快速區(qū)域合并算法；第3節(jié)詳細(xì)介紹了本文基于DBSCAN和區(qū)域合并的聚類算法的具體處理流程；第4節(jié)中基于實(shí)測(cè)數(shù)據(jù)對(duì)本文算法進(jìn)行實(shí)驗(yàn)驗(yàn)證和結(jié)果分析。

1 DBSCAN聚類算法

假設(shè)待聚類樣本集為D，p為其中的一個(gè)樣本，定義點(diǎn)p的Eps鄰域?yàn)镹Eps(p)={q∈D|dist(p,q)

1)直接密度可達(dá)：給定樣本集D中的兩個(gè)樣本p和q，如果q∈NEps(p)，且NEps(p)≥MinPts，則稱q是從核心樣本p直接密度可達(dá)的。

2)密度可達(dá)：給定樣本集D中的n個(gè)樣本p=p1、p2、…、q=pn，如果pi是從pi-1直接密度可達(dá)的，則稱q是從樣本p密度可達(dá)的。

3)密度相連：給定樣本集D中三個(gè)樣本p、q和o，如果p和q都是從核心樣本o密度可達(dá)的，則稱p和q是密度相連的。

可以看出，密度可達(dá)是直接密度可達(dá)關(guān)系的級(jí)聯(lián)傳遞，且兩者是非對(duì)稱的。而密度相連是具有對(duì)稱關(guān)系的。DBSCAN聚類算法就是通過(guò)尋找樣本集合中的相互密度相連的最大樣本集合實(shí)現(xiàn)聚類，算法的處理流程如表1所示。

表1 DBSCAN聚類算法處理流程

2 基于RAG和NNG的快速區(qū)域合并算法

區(qū)域合并算法將樣本集中的每個(gè)樣本看成圖中的一個(gè)節(jié)點(diǎn)，樣本間的連接關(guān)系看成圖中的邊，邊的權(quán)值為兩個(gè)樣本的距離度量。算法通過(guò)迭代合并圖中具有最小權(quán)值的邊所連接的兩個(gè)樣本實(shí)現(xiàn)樣本集聚類，且當(dāng)最小權(quán)值超過(guò)預(yù)設(shè)閾值時(shí)合并結(jié)束。為了提高算法的計(jì)算效率，文獻(xiàn)[10]中給出了一種基于區(qū)域鄰接圖RAG和最近鄰接圖NNG合并的快速區(qū)域合并方法。

對(duì)于集合中樣本間的連接關(guān)系，可以采用無(wú)向圖RAG有效表示，G=(V,E)。其中V為樣本集合，E=(V,V)為樣本間的關(guān)系，每條邊的權(quán)值為樣本間的距離度量。在RAG圖中，每個(gè)節(jié)點(diǎn)通常具有多個(gè)節(jié)點(diǎn)與其連接。然而，在算法合并過(guò)程中，僅利用到每個(gè)節(jié)點(diǎn)的最小權(quán)值邊及其所對(duì)應(yīng)的節(jié)點(diǎn)。因此，對(duì)于每個(gè)節(jié)點(diǎn)，僅需要記錄與其具有最小權(quán)值連接的邊，從而大大減少圖中最小權(quán)值邊的搜索范圍，以實(shí)現(xiàn)降低算法計(jì)算復(fù)雜度的目的。此時(shí)，集合中樣本連接關(guān)系可采用最近鄰圖NNG有效表示，Gm=(Vm,Em)。NNG中的頂點(diǎn)集合與RAG相同，而連接兩個(gè)節(jié)點(diǎn)的邊(vi,vj)是一個(gè)有向邊，表示在RAG中所有與vi具有邊連接的節(jié)集合中vj與其具有最短距離。在NNG中，從某個(gè)節(jié)點(diǎn)出發(fā)最后回到該節(jié)點(diǎn)所連接的節(jié)點(diǎn)路徑稱之為一個(gè)閉環(huán)(Cycle)，閉環(huán)具有以下四個(gè)特點(diǎn)[10]：

1)每個(gè)最近鄰圖中至少存在一個(gè)閉環(huán)；

2)每個(gè)閉環(huán)中有且僅有兩個(gè)頂點(diǎn)；

3)最近鄰圖中具有最小權(quán)值的兩個(gè)頂點(diǎn)必是一個(gè)閉環(huán)；

4)每個(gè)節(jié)點(diǎn)最多僅存在一個(gè)閉環(huán)中。

從NNG中閉環(huán)的特點(diǎn)可以看出，在搜索最小權(quán)值邊時(shí)，僅需要對(duì)NNG中的閉環(huán)集合進(jìn)行操作，因此能夠進(jìn)一步地降低算法的計(jì)算復(fù)雜度?；赗AG和NNG的快速區(qū)域合并算法處理流程如表2所示。

表2 基于RAG和NNG的快速區(qū)域合并算法處理流程

3 本文目標(biāo)像素聚類算法

前文中指出，根據(jù)SAR圖像中目標(biāo)檢測(cè)像素在空間的分布情況，本文采用DBSCAN聚類和區(qū)域合并聚類相結(jié)合的目標(biāo)像素聚類方法。算法首先采用DBSCAN聚類方法在目標(biāo)局部結(jié)構(gòu)層對(duì)像素進(jìn)行初步聚類。然后再對(duì)這些初步聚類的區(qū)域進(jìn)行區(qū)域合并進(jìn)而生成目標(biāo)層的聚類結(jié)果。

在DBSCAN聚類中，鄰域半徑Eps和最小密度MinPts是影響聚類結(jié)果的關(guān)鍵因素。由于該聚類過(guò)程主要目的是生成目標(biāo)局部結(jié)構(gòu)層的初始聚類結(jié)果，以降低參與后續(xù)區(qū)域合并的區(qū)域個(gè)數(shù)。因此參數(shù)Eps和MinPts的設(shè)定僅需要保證不同目標(biāo)的任意兩個(gè)像素p和q是相互非密度相連的，即Eps設(shè)定應(yīng)小于相鄰目標(biāo)的最小間隔。同時(shí)，為了防止相鄰目標(biāo)之間的虛警像素成為核心樣本，使不同目標(biāo)的像素產(chǎn)生密度相連關(guān)系，參數(shù)MinPts不能設(shè)置太小，本文中設(shè)為鄰域總像素個(gè)數(shù)的60%。

經(jīng)DBSCAN初步聚類后，每個(gè)聚類可以看作為一個(gè)區(qū)域，作為后續(xù)的區(qū)域合并的輸入。在原始DBSCAN算法中，聚類后將未聚類到任意一個(gè)核心樣本內(nèi)的像素歸為噪聲像素。而對(duì)于本文應(yīng)用，這些稀疏分布的像素點(diǎn)可能同樣為目標(biāo)像素點(diǎn)。因此，這些像素點(diǎn)同樣作為單像素區(qū)域參與到后續(xù)的區(qū)域合并過(guò)程中。

在區(qū)域合并算法中，節(jié)點(diǎn)間的距離度量是影響算法聚類結(jié)果的關(guān)鍵因素。本文采用一種最遠(yuǎn)距離約束最近距離的距離度量方法。對(duì)于兩個(gè)像素聚類集合R1和R2，其最近距離定義為

(1)

最遠(yuǎn)距離定義為

(2)

則最遠(yuǎn)距離約束的最近距離的定義為

(3)

其中，S為目標(biāo)在圖像中的最大尺寸。采用公式(3)的距離度量方法其目的是，在區(qū)域合并過(guò)程中，一方面需要考慮區(qū)域間的最近距離，根據(jù)該距離權(quán)值確定區(qū)域合并的順序；另一方面還需考慮區(qū)域間的最遠(yuǎn)距離，兩個(gè)區(qū)域合并后的區(qū)域尺寸大小應(yīng)限定在目標(biāo)尺寸范圍內(nèi)。

由前文可以看出，當(dāng)兩個(gè)像素p和q間的距離dist(p,q)大于S時(shí)，兩者所在區(qū)域不會(huì)合并到一個(gè)區(qū)域內(nèi)，因此我們?cè)谟?jì)算當(dāng)前像素與其他像素的距離時(shí)僅需計(jì)算其2×S+1鄰域內(nèi)像素的距離，并將與其他像素的距離置為無(wú)窮大。這樣以來(lái)，在構(gòu)建RAG圖時(shí)，僅對(duì)當(dāng)前區(qū)域與其內(nèi)部所有像素的2×S+1鄰域內(nèi)的像素所在區(qū)域建立連接關(guān)系。兩個(gè)區(qū)域間的最近距離、最遠(yuǎn)距離和最遠(yuǎn)距離約束的最近距離可分別由式(1)、式(2)和式(3)計(jì)算得出。

(4)

綜上所述，本文目標(biāo)檢測(cè)像素聚類處理流程如表3所示。

表3 本文目標(biāo)檢測(cè)像素聚類處理

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

本節(jié)中，采用實(shí)測(cè)SAR圖像的二值檢測(cè)圖對(duì)本文聚類算法進(jìn)行對(duì)比分析，其中對(duì)比方法采用傳統(tǒng)的聚類方法[7]。實(shí)驗(yàn)中采用的SAR圖像數(shù)據(jù)，其距離和方位分辨率為0.1m。原始SAR圖像，其二值檢測(cè)結(jié)果如圖1所示。

圖1(a)為觀測(cè)場(chǎng)景原始SAR圖像，場(chǎng)景中存在一個(gè)多目標(biāo)區(qū)域，其分布在場(chǎng)景的右側(cè)(圖中虛線框區(qū)域)。圖1(b)觀測(cè)場(chǎng)景像素級(jí)的二值檢測(cè)結(jié)果示意圖，0表示背景像素，1表示疑似目標(biāo)像素。

實(shí)驗(yàn)中，考慮到相鄰目標(biāo)間距(約0.5m=0.1m×5)和目標(biāo)尺寸大小(約6m=0.1m×60)，本文方法輸入?yún)?shù)鄰域半徑Eps、最小密度MinPts和目標(biāo)最大尺寸分別設(shè)為5、15(?5×5×60%」=15)和60；傳統(tǒng)方法目標(biāo)最大尺寸參數(shù)設(shè)為60。圖2中給出了傳統(tǒng)方法和本文方法的實(shí)驗(yàn)結(jié)果目標(biāo)像素聚類結(jié)果。圖2(a)和圖2(b)為整幅圖像的聚類結(jié)果，圖2(c)和圖2(d)分別為圖2(a)和圖2(b)中多目標(biāo)區(qū)域的聚類結(jié)果。圖2中，每一個(gè)方框代表一個(gè)聚類區(qū)域。

從場(chǎng)景原始SAR圖像可以看出，在多目標(biāo)區(qū)域，相鄰目標(biāo)的間距要小于目標(biāo)的尺寸。傳統(tǒng)聚類方法，僅通過(guò)判斷像素(區(qū)域)之間距離來(lái)決定該目標(biāo)是否聚類到該區(qū)域，而對(duì)像素(區(qū)域)聚類的順序沒(méi)有要求，因此很容易將相鄰目標(biāo)的像素聚成一個(gè)目標(biāo)，形成虛警目標(biāo)的現(xiàn)象。而本文算法采用區(qū)域合并的策略進(jìn)行像素聚類，并根據(jù)像素與像素、區(qū)域與區(qū)域之間的距離來(lái)判斷合并順序，進(jìn)而能夠有效地解決該多目標(biāo)場(chǎng)景目標(biāo)像素聚類問(wèn)題。從圖2實(shí)驗(yàn)結(jié)果也可以看出，傳統(tǒng)方法聚類結(jié)果中出現(xiàn)了多處相鄰目標(biāo)被聚類成一個(gè)目標(biāo)的情況，而本文方法輸出的每個(gè)聚類區(qū)域僅包含一個(gè)目標(biāo)。

圖1 實(shí)測(cè)SAR圖像及其二值檢測(cè)圖

圖2 傳統(tǒng)方法和本文方法目標(biāo)聚類結(jié)果對(duì)比

5 結(jié)束語(yǔ)

針對(duì)SAR圖像目標(biāo)檢測(cè)中的多目標(biāo)區(qū)域目標(biāo)像素聚類問(wèn)題，文中提出一種基于最遠(yuǎn)距離約束的最近距離區(qū)域合并算法。算法首先采用DBSCAN方法對(duì)目標(biāo)像素進(jìn)行聚類，生成目標(biāo)局部結(jié)構(gòu)層的初步聚類結(jié)果；然后利用區(qū)域合并算法對(duì)這些初步聚類區(qū)域進(jìn)行合并，進(jìn)而給出目標(biāo)層的目標(biāo)像素聚類結(jié)果。同時(shí)，采用RAG和NNG表征聚類區(qū)域間的連接關(guān)系，對(duì)區(qū)域合并過(guò)程進(jìn)行加速處理。實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)聚類算法，本文算法能夠?qū)⑼荒繕?biāo)的像素聚成一個(gè)區(qū)域，將目標(biāo)與其相鄰目標(biāo)有效地隔離開來(lái)。