一種新的基于網(wǎng)格編碼和區(qū)域合并的SAR圖像快速分割算法

張澤均水鵬朗

(西安電子科技大學(xué)雷達信號處理國家重點實驗室 西安 710071)

1 引言

近幾十年來，合成孔徑雷達(SAR)成像系統(tǒng)得到廣泛應(yīng)用[1]。它以全天候、全天時主動成像的優(yōu)點彌補了經(jīng)典被動光學(xué)成像系統(tǒng)的不足。SAR圖像分割技術(shù)是SAR圖像應(yīng)用和自動解譯的關(guān)鍵技術(shù)[2]。由于SAR圖像相干斑的存在，增大了SAR圖像分割難度[2]。國內(nèi)外眾多學(xué)者提出了各種SAR圖像分割算法[36]-，主要分為基于區(qū)域合并[4,6]和全局模型優(yōu)化[5]兩類。

基于區(qū)域合并的 SAR 圖像分割算法[4,6]首先對SAR圖像進行過分割；然后，構(gòu)造相鄰區(qū)域之間的相似性度量；最后，迭代地合并最相似的兩個相鄰區(qū)域，直到最相似的兩個相鄰區(qū)域之間的相似度不滿足預(yù)設(shè)的條件為止。

基于全局模型優(yōu)化的 SAR圖像分割算法的重點是模型的建立及其優(yōu)化求解[5]。從編碼理論的角度出發(fā)，一種經(jīng)典的基于模型的SAR圖像分割方法是利用最短描述長度(MDL)準則建立 SAR圖像的分割模型，遞歸地實現(xiàn)模型的優(yōu)化求解[5]。

MDL準則是 Rissanen[7]在 1978年提出，用于估計描述數(shù)據(jù)的參數(shù)模型的參數(shù)個數(shù)。從圖像編碼的角度出發(fā)，Leclerc[8]首次將MDL準則應(yīng)用到圖像分割中。文獻[9]在 MDL準則下討論傳統(tǒng)蛇模型中的正則化項，提出了將蛇方法、區(qū)域生長、區(qū)域合并和貝葉斯方法統(tǒng)一于一體的區(qū)域競爭算法。Figueiredo等人[10]用B樣條曲線來表示區(qū)域的邊界，利用 MDL準則估計曲線控制點的數(shù)目與位置，將醫(yī)學(xué)圖像分割成目標和背景兩個區(qū)域。文獻[5]利用多邊形網(wǎng)格表示區(qū)域的邊界，提出一種基于 MDL準則的SAR圖像分割模型，通過迭代地變形多邊形網(wǎng)格的形狀、節(jié)點的位置和節(jié)點個數(shù)來實現(xiàn)SAR圖像分割。該方法的最大優(yōu)點是不需要經(jīng)驗地調(diào)整模型的參數(shù)。但是，它在實現(xiàn)模型優(yōu)化的時候存在以下主要的不足：(1)每次迭代都需要全局地更新多邊形網(wǎng)格的編碼長度；(2)分割結(jié)果對初始分割敏感度高；(3)算法的時間復(fù)雜度高。

本文利用八鄰域網(wǎng)格來表示區(qū)域的邊界，建立一種新的基于MDL準則的SAR圖像分割模型，迭代過程中只需要局部地更新網(wǎng)格的編碼長度，提高了模型的計算效率。利用多方向比例邊緣檢測算子提取SAR圖像的比例邊緣強度映射(RESM)，提出一種新的抑制RESM均質(zhì)區(qū)域內(nèi)極小值的閾值處理方法，對閾值處理后的RESM進行分水嶺變換獲得SAR圖像的初始過分割結(jié)果。遞歸合并使圖像的編碼長度減少最快的兩個相鄰區(qū)域，直到圖像的編碼長度不再減少為止。利用區(qū)域鄰接圖(RAG)和最近鄰圖(NNG)技術(shù)來加速遞歸區(qū)域合并過程。將光學(xué)圖像分割中度量邊緣定位精度的精確度(P)和召回率(R)指標借用來評價SAR圖像分割算法的邊緣定位精度。

2 基于網(wǎng)格編碼的SAR圖像分割模型

2.1 基于MDL準則的SAR圖像分割模型

假設(shè)多視強度SAR圖像I中的相干斑是完全發(fā)展的[2]，那么，區(qū)域Ri內(nèi)的每個像素服從均值為iθ的Gamma分布：

根據(jù)式(1)與不同區(qū)域之間和區(qū)域內(nèi)像素之間的統(tǒng)計獨立性，SAR圖像I的香農(nóng)編碼長度為

其中，N為原始圖像的像素個數(shù)。Gamma模型的編碼長度 ()L θ近似為[5]

2.2 區(qū)域邊界的網(wǎng)格編碼

區(qū)域邊界的表示及其編碼方式對 SAR圖像的分割結(jié)果和效率均有影響[5]。本文使用八鄰域網(wǎng)格表示區(qū)域的邊界。

(2)分割結(jié)果中，每條公共邊的起點在整個圖像網(wǎng)格平面上的位置是隨機的，因此，需要lnN位來編碼每條公共邊界的起始坐標。

將式(4)右邊的第3項、式(5)和式(7)代入式(2)，得到本文提出的基于八鄰域網(wǎng)格編碼的 SAR圖像分割模型：

模型式(7)的優(yōu)化求解是一個關(guān)鍵問題，一般沒有簡單有效的方法求解之。文獻[5]和文獻[10]分別基于區(qū)域邊界的多邊形網(wǎng)格和B樣條曲線表示提出了求解次優(yōu)解的方法。但它們的時間復(fù)雜度高。本文結(jié)合多方向比例邊緣檢測和區(qū)域合并技術(shù)來求解分割模型式(7)的次優(yōu)解。

3 基于區(qū)域合并技術(shù)的模型優(yōu)化算法

本文的模型優(yōu)化方法主要包括兩個模塊：第 1個模塊利用多方向比例邊緣檢測算子獲得 SAR圖像的比例邊緣強度映射(RESM)，提出一種新的抑制RESM均質(zhì)區(qū)域內(nèi)的極小值點的閾值處理方法，對處理后的RESM進行分水嶺變換，得到SAR圖像的初始過分割結(jié)果；第2個模塊使用區(qū)域合并技術(shù)迭代地合并使圖像的編碼長度式(7)減少最快的兩個相鄰區(qū)域，利用區(qū)域鄰接圖(RAG)和最近鄰圖(NNG)加速區(qū)域合并過程，得到最終分割結(jié)果。

3.1 SAR圖像的初始分割

在基于區(qū)域合并的圖像分割中，初始分割結(jié)果的質(zhì)量對區(qū)域合并的效率與性能起著關(guān)鍵性的作用，要求它同時滿足如下兩個條件：

條件1：區(qū)域個數(shù)盡量少；

條件2：不存在欠分割。

條件1保證區(qū)域合并的高效性；條件2保證初始分割結(jié)果中不能丟失真實的邊緣。本文利用多方向比例邊緣檢測器[11]提取原始SAR圖像的RESM，提出一種抑制RESM均質(zhì)區(qū)域內(nèi)極小值的閾值處理方法，然后，對閾值處理后的RESM進行分水嶺變換得到SAR圖像的初始過分割結(jié)果。

圖 1顯示了多方向比例邊緣檢測器的配置結(jié)構(gòu)，它的參數(shù)配置和分別表示：檢測器的長度，寬度，兩個矩形之間的寬度和檢測器的方向。對于某一特定方向fθ，首先計算中心像素點(x,y)兩邊矩形區(qū)域內(nèi)像素點的均值︿1(,R x和，然后計算點在方向上的比例邊緣強度映射：

圖1 邊緣檢測濾波器配置

緣檢測器的方向數(shù)。構(gòu)造圖像的RESM：

圖2顯示了3視SAR圖像閾值處理后的RESM及其分水嶺變換結(jié)果。為了比較本文方法的優(yōu)勢，在圖2分別給出了文獻[4]和文獻[6]中的初始分割結(jié)果。很明顯，本文方法獲得的初始分割結(jié)果滿足以上兩個條件，而文獻[4]和文獻[6]的初始分割結(jié)果只滿足第2個條件。

圖2 初始分割方法比較

3.2 基于區(qū)域合并技術(shù)的模型優(yōu)化算法

用RAG表示圖像的區(qū)域[12]。RAG被定義為一個無向連接圖，，其中，是圖G的節(jié)點集合，每個結(jié)點表示分割結(jié)果中的一個區(qū)域。是邊集合，如果一條邊，則區(qū)域i和j相鄰。在邊集合E中，每條邊被賦予一個權(quán)值

圖3給出用RAG表示圖像分割的例子，圖3(a)表示一個6個區(qū)域的分割結(jié)果，圖3(b)是它的RAG表示，邊上的數(shù)值表示它的權(quán)值。

利用 RAG的最近鄰圖(NNG)特性加速區(qū)域合并過程，RAG的NNG定義為一個有向圖，其中，如果，那么存在從節(jié)點i指向節(jié)點j的有向邊，其權(quán)值為。當而且時，那么區(qū)域i和j之間構(gòu)成一個環(huán)，圖3(c)表示圖3(b)的NNG。搜索RAG中的最小權(quán)值時，只需要在NNG的環(huán)上搜索即可。表1中描述了基于RAG和NNG的區(qū)域合并過程。

表1 基于RAG的區(qū)域合并算法

4 實驗結(jié)果與性能評價

為了驗證本文算法的有效性，分別對合成和真實SAR圖像進行試驗，同時與3種方法進行比較，分別是：SRG-HM[4], MDL-PGP[5]和 CHUMSIS[6]。分析了本文算法的計算復(fù)雜度。借用光學(xué)圖像分割中用于度量邊緣定位精度的精確度-召回率(Precision-Recall, P-R)指標[13]來度量 SAR 圖像分割算法的邊緣定位精度。

4.1 實驗結(jié)果

在分片常數(shù)卡通圖 4(a)的基礎(chǔ)上，利用乘性噪聲模型分別產(chǎn)生服從Gamma分布的1視和4視合成強度格式 SAR 圖像(分別對應(yīng)圖 5(a)中從上至下)。圖5(b)-5(e)分別給出了4種算法的分割結(jié)果。為了視覺效果，所有圖像均用幅度格式顯示。

圖3 圖像區(qū)域的RAG表示

圖4 合成的光學(xué)圖像

從圖5的合成SAR圖像的分割結(jié)果可以看出，在1視圖像分割中，前面3種方法中均有漏檢的弱邊緣(如圖中白色箭頭所指)，而且邊緣定位精度低。對于4視的合成SAR圖像，CHUMSIS方法也存在漏檢的邊緣。MDL-PGP方法與本文方法在視覺上獲得相似的結(jié)果，均優(yōu)于前面兩種方法。

圖6給出了真實SAR圖像的分割結(jié)果，圖6(a1),6(a2)和6(a3)的視數(shù)分別為1視、3視和4視。視覺上，SRG-HM方法和MDL-PGP方法均存在明顯的過分割現(xiàn)象，而且 SRG-HM 方法的邊緣定位精度低。CHUMSIS方法存在明顯的欠分割現(xiàn)象。本文方法降低了過分割和欠分割程度，而且提高了邊緣定位精度。

4.2 效率分析

在表1中描述的區(qū)域合并算法中，假設(shè)初始分割所需要的時間為tin，在搜索最小權(quán)值的邊時，每次權(quán)值比較的時間為tcm，更新RAG的時間為tup,RAG的平均連接度為d，最終分割結(jié)果中區(qū)域的個數(shù)為K,RAG中初始節(jié)點個數(shù)為，每次迭代區(qū)域個數(shù)減少1，算法總的運行時間ttl為

實際中，K遠小于初始分割中的區(qū)域個數(shù)|V0|。因此，式(11)近似為

式(14)中右邊的第3項是更新RAG和NNG所需要的時間。

表2給出了4種算法的運行時間，計算機平臺為：Pentium (R) Dual-Core, 2.93 GHz CPU, 2 GB內(nèi)存，MATLAB 2010b?？梢钥闯?，本文方法要比其它3種方法的高效得多。

4.3 性能評價

引入自然圖像分割中度量邊緣定位精度的精確度-召回率(Precision-Recall, P-R)指標[13]來度量SAR圖像分割算法的邊緣定位精度。在圖4(a)的基礎(chǔ)上分別獨立產(chǎn)生30幅1視、3視和4視合成SAR圖像集合。圖4(b)為真實邊緣。

圖5 合成SAR圖像分割結(jié)果，從上到下分別為1視和4視，圖像尺寸為512×479

圖6 真實SAR圖像分割結(jié)果，3幅圖像的尺寸均為401×401

表2 4種算法的運行時間比較

表3給出了4種分割算法分別取最優(yōu)參數(shù)設(shè)置時，每視數(shù)的30幅圖像的平均指標值。從表中可以看出，本文方法的 3個邊緣定位指標均明顯優(yōu)于SRG-HM方法和 CHUMSIS方法；與 MDL-PGP方法相比，除了單視圖像的命中率略低，本文方法的其它指標均優(yōu)于它。

表3 4種方法邊緣定位指標比較

5 結(jié)束語

本文建立了一種新的基于 MDL準則和八鄰域網(wǎng)格編碼的SAR圖像分割模型。結(jié)合多方向比例邊緣檢測器和區(qū)域合并技術(shù)實現(xiàn)模型的快速求解。利用多方向比例邊緣檢測器提取SAR圖像的RESM，提出一種新的閾值化處理方法來抑制RESM均質(zhì)區(qū)域內(nèi)部極小值，對閾值處理后的RESM進行分水嶺變換，獲得原始圖像的初始分割結(jié)果。利用區(qū)域鄰接圖(RAG)和最近鄰圖(NNG)技術(shù)實現(xiàn)快速區(qū)域合并，將區(qū)域合并的時間復(fù)雜度降低了近d(d為RAG的節(jié)點的平均連接度)倍。引入精確度(P)和召回率(R)來評價分割算法的邊緣定位性能。與3種常用方法相比，本文方法邊緣定位精度高，算法時間復(fù)雜度低，而且降低了欠分割與過分割程度。

[1] 鄧云凱, 趙鳳軍, 王宇. 星載SAR技術(shù)的發(fā)展趨勢及應(yīng)用淺析[J]. 雷達學(xué)報, 2012, 1(1): 1-10.Deng Yun-kai, Zhao Feng-jun, and Wang Yu. Brief analysis on the development and application of spaceborne SAR[J].Journal of Radars, 2012, 1(1): 1-10.

[2] Gonzalez A A, Valero S, Chanussot J, et al.. Processing multidimensional SAR and hyperspectral images with binary partition tree[J]. Proceedings of the IEEE, 2013, 101(3):723-747.

[3] 顏學(xué)穎, 焦李成, 王凌霞, 等. 一種提高SAR圖像分割性能的新方法[J]. 電子與信息學(xué)報, 2011, 33(7): 1700-1705.Yan Xue-ying, Jiao Li-cheng, Wang Ling-xia, et al.. New method for improving the performance of SAR image segmentation[J]. Journal of Electronics ＆amp; Information Technology, 2011, 33(7): 1700-1705.

[4] Carvalho E A, Ushizima D M, Medeiros F N S, et al.. SAR imagery segmentation by statistical region growing and hierarchical merging[J]. Digital Signal Processing, 2009,20(5): 1365-1378.

[5] Galland F, Bertaux N, and Refregier P. Minimum description length synthetic aperture radar image segmentation[J]. IEEE Transactions on Image Processing, 2003, 12(9): 995-1006.

[6] Yu Hang, Zhang Xiang-rong, Wang Shuang, et al.. Contextbased hierarchical unequal merging for SAR image segmentation[J]. IEEE Transactions on Geoscience and Remote Sensing, 2013, 51(2): 995-1009.

[7] Rissanen J. Modeling by shortest data description[J].Automatica, 1978, 14(1): 465-471.

[8] Leclerc Y C. Constructing simple stable descriptions for image partitioning[J]. Computer Vision, 1989, 8(1): 73-102.

[9] Zhu S C and Yuille A. Region competition: unifying snakes,region growing, and Bayes/MDL for multiband image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(9): 884-900.

[10] Figueiredo M A T, Leitao J M N, and Jain A K.Unsupervised contour representation and estimation using B-splines and a minimum description length criterion[J].IEEE Transactions on Image Processing, 2000, 9(6):1075-1087.

[11] Schou J, Skriver H, Nielsen A A, et al.. CFAR edge detector for polarimetric SAR images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2003, 41(1): 20-32.

[12] Peng B, Zhang L, and Zhang D. Automatic image segmentation by dynamic region merging[J]. IEEE Transactions on Image Processing, 2011, 20(12): 3592-3605.

[13] Arbelaez P, Maire M, Fowlkes C, et al.. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5):898-916.