G0分布中鏈碼網格SAR圖像分割算法

張澤均,水鵬朗

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

G0分布中鏈碼網格SAR圖像分割算法

張澤均,水鵬朗

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

為了降低合成孔徑雷達(SAR)圖像場景復雜度對SAR圖像分割結果的影響,提出一種基于最短描述長度(MDL)準則的自適應權值SAR圖像分割模型.該模型利用G0分布描述SAR圖像數據,用鏈碼網格對SAR圖像中區域的邊緣進行編碼.提出一種利用SAR圖像數據自適應地估計分割模型權值的方法.利用區域合并技術實現SAR圖像分割模型快速最小化.實驗結果表明,與兩種同類方法相比,文中方法有效地減輕了紋理區域的過分割程度.

合成孔徑雷達圖像分割;G0分布;鏈碼網格;區域合并技術

隨著合成孔徑雷達(Synthetic Aperture Radar,SAR)成像的發展,SAR圖像的運用更廣泛[1].圖像分割技術為SAR圖像解譯提供可靠的區域和邊緣信息,它將一幅SAR圖像分割成互不重疊的子區域[2].一類有效的SAR圖像分割方法是基于模型的方法[3-5],它首先對SAR圖像分割問題建模,然后通過優化求解模型實現圖像分割.基于最短描述長度(Minimum Description Length,MDL)準則[6]的模型分割方法是一種經典的圖像分割方法[4-5,7].

1978年Rissanen提出MDL準則估計數據模型的參數個數[6].Leclerc首次利用MDL準則對圖像分割問題建模[8].Zhu和Yuille基于MDL準則提出將經典的蛇方法、區域生長、區域合并和貝葉斯方法統一于一體的區域競爭算法[9].Galland等[4]利用多邊形網格劃分圖像區域,建立了不需要調整參數的MDL準則SAR圖像分割模型,遞歸地變形多邊形網格的形狀實現模型優化求解.文獻[4]中的方法要求SAR圖像數據服從Gamma分布,而在不滿足要求的紋理或者場景復雜區域,分割結果中存在嚴重的過分割.針對這個問題,文獻[5]利用Fisher分布對SAR圖像數據建模,改善了處理復雜場景SAR圖像的能力,但它仍存在如下問題:算法性能與效率對初始多邊形網格敏感;多邊形網格變形過程增加了算法的時間復雜度;分割模型中沒有考慮地面場景復雜度對分割結果的影響,降低了處理復雜場景SAR圖像的能力.

針對以上問題,筆者利用G0[3,10]分布對SAR圖像建模和鏈碼網格編碼區域邊緣,建立一種基于MDL準則的自適應加權SAR圖像分割模型.利用區域合并技術快速最小化SAR圖像分割模型.文中方法具有如下特點:利用鏈碼網格編碼和區域合并技術簡化了分割模型的計算,提高了算法的效率;分割模型中引入權值來度量場景復雜度對分割結果的影響,提出了一種自適應權值估計方法,提高了算法的性能.

1 SAR圖像分割模型的建立

MDL準則是根據卡爾莫戈羅夫復雜度理論[11]建立的一種數據最優編碼準則.它首先將一幅N=Nx× Ny個像素的強度SAR圖像I={I(x,y):1≤x≤Nx,1≤y≤Ny},分割成M個互不相交的子區域,?M= {R1,R2,…,RM},每個子區域用其邊緣來界定;然后,分別對每個子區域的像素和邊緣進行編碼.設區域Ri內像素的編碼長度為LI,i,其概率密度函數P(·;θi)的編碼長度為LG,i,所有區域邊緣的編碼長度為LB. MDL準則的目的是尋找SAR圖像的一個最優分割,使

模型(1)中面臨的問題是區域像素建模和區域邊緣的編碼.

G0分布憑其對復雜場景SAR圖像數據的精確建模能力而被應用于SAR圖像處理中[3,10].文中利用G0分布對強度SAR圖像建模.區域Ri內像素的概率密度函數為[10]

其中,ni為區域Ri的視數;γi為尺度參數;αi為形狀參數,它與場景的地面起伏程度有關,當地面較平滑時, αi值較小,起伏較大時,αi值較大.G0分布能用來描述地面起伏范圍較大的場景的雷達回波數據,實現對復雜場景SAR圖像數據的精確建模.

由式(2)和香農編碼原理,區域Rk內像素值的平均編碼長度依概率收斂于,其中,Nk為區域Rk的像素個數,HG,k為區域Rk的G0分布的熵

對于區域Rk的概率分布函數G0分布的平均編碼長度[4]LG,k為3 ln Nk2.

區域邊緣的編碼長度由邊緣的編碼方式決定.文獻[4-5]利用多邊形網格近似區域的邊緣,利用最大熵原理計算多邊形網格的編碼長度,其時間復雜度較高.文中利用鏈碼網格編碼區域邊緣,如圖1所示.區域邊緣的鏈碼網格的編碼長度LB為

圖1 區域邊緣的鏈碼網格

其中,集合E為相鄰區域對集合,若區域Ri與Rj相鄰,那么(i, j)∈E,Γij為它們之間的公共邊緣像素集合,表示?M中的公共邊的條數.

(1)L(Γij)為區域Ri與Rj之間公共邊緣的編碼長度:為公共邊緣Γij的長度.ln3表示從當前點走向下一點的可能走向有3個選擇(左、右和前),如圖1所示的整數編碼長度…,其中,c≈2.865 064,等號右邊累加所有正數項;

(2)對于每條公共邊緣,需要存儲其起始坐標,編碼長度為ln N位.

將式(3)和式(4)帶入式(1)中,即得到SAR圖像分割模型為

式(5)由兩部分組成:SAR圖像數據編碼長度和參數編碼長度.權值λ均衡兩部分編碼長度對分割結果的影響,它與SAR圖像的場景復雜度有關.

2 分割模型優化求解

利用區域合并技術遞歸地合并初始分割結果中使式(5)降低最快的相鄰區域,實現分割模型的最小化.利用對數矩估計方法估計G0分布的參數,提出一種自適應權值λ估計方法.

2.1 初始分割

文中直接利用文獻[12]中的結合多方向比例邊緣檢測算子和分水嶺變換的初始分割方法獲得SAR圖像的初始分割結果.該方法中,多方向比例邊緣檢測算子的矩形的長度、寬度、兩個矩形之間的距離和矩形與水平方向之間的夾角數分別為9、3、1和16,閾值處理過程中的分位數為0.35.圖2中給出了4幅SAR圖像的初始分割結果.

圖2 SAR圖像的初始分割

2.2 基于區域合并的模型優化算法

利用區域鄰接圖(Region Adjacency Graph,RAG)表示分割結果,并利用最近鄰圖(Nearest Neighbor Graph,NNG)加速區域合并過程.

SAR圖像的分割結果?M的RAG為一個無向圖GM,GM=(VM,EM,WM),其中,頂點集VM為區域像素集合,即v∈VM,v={(x,y)|(x,y)∈Rv};邊集EM為公共邊界集,若區域Ru和Rv相鄰,則euv∈EM, euv={(x,y)|(x,y)∈?Ru∩?Rv},它們之間的權值w(u,v)∈WM定義為合并相鄰區域Ru和Rv時,式(5)的減少量為

圖3 圖像區域的RAG及其NNG

為了加速區域合并過程,利用RAG的NNG加速RAG中最大權值wmax(u,v)的搜索.一個RAG GM的 NNG定義為一個有向圖Gd,M,Gd,M=(VM,Ed,M,Wd,M),其中,Ed,M是有向邊集,當euv∈EM,且w(u,v)= max{w(u,k)|k∈N(u)}時,存在一條從u指向v的有向邊〈u,v〉∈Ed,M,N(u)為與u相鄰的區域集,且w(u,v)∈Wd,M.圖3(c)為圖3(b)中RAG的NNG示意圖.從圖3(c)看出,一個RAG的NNG由多個有向子圖構成,最多/2個子圖,每個子圖僅存在一個環,且環上的權值是該子圖的最大權值.這樣,NNG中的最大權值環就是RAG中的最大權值.

進行區域合并時,RAG GM及其NNG Gd,M的局部更新算法如下:

算法1 RGA和NNG更新算法

輸入:RAG GM,NNG Gd,M,合并區域Ru和Rv.

輸出:更新后的RAG GM-1和NNG Gd,M-1.

(1)合并相鄰區域Ru和Rv,產生新的區域Rk;

(2)更新VM-1:VM-1=(VM-{u,v})∪{k};

(3)更新EM-1:令eu*={eui|eui∈EM}∪{eiu|eiu∈EM}和ev*={evi|evi∈EM}∪{eiv|eiv∈EM}, NE=eu*∪ev*,V*={l|eul∈NE}∪{l|elu∈NE}∪{l|evl∈NE}∪{l|elv∈NE},那么EM-1=(EM-euv-NE)∪{eki|i∈V*};

(4)更新WM-1:WM-1=(WM-w(u,v)-{w(u,i),w(i,u),w(v,i),w(i,v)|i∈V*})∪{w(k,j)| j∈V*},利用式(6)重新計算與區域Rk相鄰的區域之間的權值w(k,j);

(5)更新NNG Gd,M-1:利用更新后的RAG GM-1和區域Rk的相鄰區域集V*局部更新NNG Gd,M-1.

基于區域合并技術的分割模型(1)的優化求解算法如下:

算法2 基于區域合并技術的模型優化算法

輸入:初始分割結果?M.

輸出:最終分割結果?M*.

(1)估計每個區域Ri,i=1,2,…,M的G0分布參數(αi,γi,ni)和參數λ;(2.3小節)

(2)初始化初始分割?M的RAG GM及其NNG Gd,M;

(3)在NNG Gd,M中搜索最大權值環wmax(u,v);

(4)如果wmax(u,v)＞0,則合并相鄰區域Ru與Rv,產生新的區域Rk,重新估計區域Rk的G0分布參數(αk,γk,nk),利用算法1中的算法更新RAG GM-1和NNG Gd,M-1,令M=M-1,轉至(3);否則,轉至(5);

(5)輸出根據RAG GM構造的最終分割結果RM*.

2.3 參數估計

2.3.1 G0分布參數估計

利用對數矩估計方法估計模型(2)中的G0分布的參數αi、γi和ni,其非線性方程組[13]為

其中,Ψ(·)為Digamma函數,Ψ(k,·)為k階Polygamma函數,Ψ(k,·)=dklnΓ(·)d xk,ck為k階對數矩利用經典Newton-Raphson方法估計ni,αi和γi.

2.3.2 參數λ的估計

在式(5)和式(6)中,參數λ均衡分割模型中數據編碼長度和參數編碼長度對分割結果的影響,其值與SAR圖像的場景復雜度有關.對于場景較復雜的圖像,較小的λ值降低了欠分割程度;而場景較簡單的圖像,較大的λ值降低了過分割程度.因此,文中提出參數λ的估計方法為

其中,T為常數,文中取3.5,J為初始過分割中,所有相鄰區域之間的平均Fisher距離為

其中,μi和σi分別為區域Ri的樣本均值和方差,NE為初始分割結果中相鄰區域對數.B為初始分割中,所有公共邊緣的長度之和與圖像尺寸的比值,即

在式(8)中,J和B度量SAR圖像場景復雜度,其值越大,場景越復雜,圖像中細節信息越多,估計的λ值越小,有利于圖像中細節信息的提取;其值越小,場景復雜度越低,圖像中的細節信息越少,估計的λ值越大,越降低由SAR圖像中的噪聲引起的過分割現象.

3 實驗結果與分析

為了驗證文中算法的有效性,分別對4幅SAR圖像(圖2(a)～圖2(d))進行分割實驗,并將其分割結果與兩種同類方法(MDLPGP方法[4]和FMDLPGP方法[5])進行比較.利用基于信息熵的定量評價指標[14]對3種算法進行數值比較,分析了文中算法的時間復雜度.

3.1 實驗結果

表1給出了圖2中4幅SAR圖像的先驗信息.3種方法的分割結果如圖4所示.

表1 SAR圖像先驗信息

從圖4中可以看出,對于場景比較簡單的農田區域,3種分割方法都獲得了滿意的結果,但對于較復雜的城市、居民區和建筑物區域,由于MDLPGP方法中Gamma分布不能精確地對復雜場景建模,而出現明顯的過分割.雖然FMDLPGP方法利用Fisher分布改善了分割結果,但由于其分割模型以及模型優化方法的限制,其分割結果中也出現明顯的過分割.文中方法將圖像初始分割成均質的小區域,提高了優化過程中G0模型參數的估計精度和紋理區域輪廓的檢測能力,同時,自適應地估計分割模型中的權值,明顯降低了欠分割程度.

3.2 性能分析

筆者利用基于信息熵的兩個數值指標Hr和Hl[14]度量3種算法.Hr度量分割結果中,每個區域內像素的一致性特性,Hr值越小,區域內像素的一致性越好;Hl度量分割結果的過分割程度,Hl值越小,過分割程度越小.度量分割算法性能的綜合數值指標E=Hr+Hl.

表2給出3種算法的性能指標比較.從表中可以看出,文中方法獲得最好的綜合數值指標.

文中算法的時間復雜度為

其中,tini為初始分割的時間,它與圖像大小和邊緣檢測算子的參數有關;tcp為比較兩條邊的權值的時間; tRAG和tNNG分別為更新RAG和NNG的時間.

圖4 分割結果

表2 數值指標比較

在MDLPGP方法和FMDLPGP方法中,每次變形多邊形網格全局更新所有節點和區域的信息增加了時間復雜度.而FMDLPGP方法,每次更新都需要計算一個與文中式(7)相似的非線性方程組來估計Fisher分布的參數.文中方法的更新只涉及局部運算,其時間復雜度較低.表3中給出了3種方法的CPU運行時間,計算機平臺為Pentium(R)Dual-Core,2.93 GHz CPU,2 GB內存,MATLAB 2010b.

表3 3種分割方法運行時間比較

4 結束語

筆者針對SAR圖像分割模型的建立及優化問題,在G0分布中利用鏈碼網格編碼區域邊緣,建立基于MDL準則的自適應權值SAR圖像分割模型,自適應地估計權值.在SAR圖像初始過分割的基礎上,遞歸地合并相鄰區域實現模型優化求解.實驗結果表明,與兩種同類方法相比,文中方法有效地降低了紋理區域的過分割程度且提高了算法的效率.

[1]Bovolo F,Marin C,Bruzzone L.A Hierarchical Approach to Change Detection in Very High Resolution SAR Images for Surveillance Applications[J].IEEE Transactions on Geoscience and Remote Sensing,2013,51(4):2042-2054.

[2]崔艷鵬,胡建偉,楊紹全,等.利用DT-Grow Cut的MSTAR SAR圖像自動分割技術[J].西安電子科技大學學報, 2011,38(3):150-154. Cui Yangpeng,Hu Jianwei,Yang Shaoquan,et al.SAR Image Automatic Segmentation Based on DT-Grow Cut[J]. Journal of Xidian University,2011,38(3):150-154.

[3]Marques R C P,Medeiros F N,Nobre JS.SAR Image Segmentation Based on Level Set Approach and G-zero-amplitude Model[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(10):2046-2057.

[4]Galland F,Bertaux N,Refregier P.Minimum Description Length Synthetic Aperture Radar Image Segmentation[J]. IEEE Transactions on Image Processing,2003,12(9):995-1006.

[5]Galland F,Nicolas J M,Sportouche H,et al.Unsupervised Synthetic Aperture Radar Image Segmentation Using Fisher Distributions[J].IEEE Transactions on Geoscience and Remote Sensing,2009,47(8):2966-2972.

[6]Rissanen J.Modeling by Shortest Data Description[J].Automatica,1978,14(5):465-471.

[7]Morio J,Goudail F,Dupuis X,et al.Polarimetric and Interferometric SAR Image Partition into Statistically Homogeneous Regions Based on the Minimization of the Stochastic Complexity[J].IEEE Transactions on Geoscience and Remote Sensing,2007,45(11):3599-3609.

[8]Leclerc Y C.Constructing Simple Stable Descriptions for Image Partitioning[J].Computer Vision,1989,8(1):73-102.

[9]Zhu S C,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]Feng J,Cao Z,Pi Y.Multiphase SAR Image Segmentation with G0-statistical-model-based Active Contours[J].IEEE Transactions on Geoscience and Remote Sensing,2013,51(7):4190-4199.

[11]Cover T M,Thomas J A.Elements of Information Theory[M].New York:Wiley,1991.

[12]Shui P L,Zhang Z J.Fast SAR Image Segmentation via Merging Cost with Relative Common Boundary Length Penalty [J].IEEE Transactions on Geoscience and Remote Sensing,2014,52(10):6434-6448.

[13]時公濤,高貴,周曉光,等.基于Mellin變換的G0分布參數估計方法[J].自然科學進展,2009,19(6):677-690. Shi Gongtao,Gao Gui,Zhou Xiaoguang,et al.A Parameter Estimation Method for G0Distribution Based on Mellin Transform[J].Progress in Natural Science,2009,19(6):677-690.

[14]王珂,顧行發,余濤,等.結合光譜相似性與相位一致模型的高分辨率遙感圖像分割方法[J].紅外與毫米波學報, 2013,32(1):73-79. Wang Ke,Gu Xingfa,Yu Tao,et al.Segmentation of High-resolution Remotely Sensed Imagery Combining Spectral Similarity with Phase Congruency[J].Journal of Infrared and Millimeter Waves,2013,32(1):73-79.

(編輯:李恩科)

SAR images segmentation algorithm using chain coding grid in G0distribution

ZHANG Zejun,SHUI Penglang
(National Key Lab.of Radar Signal Processing,Xidian Univ.,Xi’an 710071,China)

An adaptive weighted synthetic aperture radar(SAR)images segmentation model is proposed based on the minimum description length(MDL)principle to alleviate the influence of complexity of the SAR images’scene on segmentation results.In the model,G0distribution is used for describing SAR image data,and the 4-neighborhood chain coding grid is utilized for coding boundaries of regions in the SAR image.An adaptive estimation method for the weight of the segmentation model is proposed using the SAR image data.The segmentation model is fast minimized by using region merging technology.Experimental results show that,compared with two methods of the same kind,the proposed method effectively alleviates the degree of over-segmentation in texture fields.

synthetic aperture radar(SAR)image segmentation;G0distribution;chain coding grid; region merging technique

TP751.1

A

1001-2400(2015)05-0048-07

2014-05-31< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

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

張澤均(1984-),男,西安電子科技大學博士研究生,E-mail:zjzhang_xd@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.009.html

10.3969/j.issn.1001-2400.2015.05.009