基于聚類的合成孔徑雷達圖像分割算法研究

邢 濤 趙海賓 胡慶榮 李 軍 王冠勇

(1.中國航天二院二十三所北京100854;2.中國人民解放軍駐航天二院二十三所軍代表室北京100854)

總體工程

基于聚類的合成孔徑雷達圖像分割算法研究

邢 濤1趙海賓2胡慶榮1李 軍1王冠勇1

(1.中國航天二院二十三所北京100854;2.中國人民解放軍駐航天二院二十三所軍代表室北京100854)

針對SAR圖像的分割問題，對K均值聚類算法進行了研究，分析了自適應動態(tài)K均值聚類算法，改進了最大適應度函數聚類的樣本分離準則。毫米波SAR圖像分割表明，對于城區(qū)建筑及路、橋場景的分割，改進算法比基本的K均值聚類算法、動態(tài)K均值聚類算法及自適應動態(tài)K均值聚類算法性能要好，指標更優(yōu)。在運算效率上，改進算法與自適應動態(tài)K均值聚類算法效率相當。

合成孔徑雷達;圖像分割;聚類;K均值

0 引 言

合成孔徑雷達(synthetic aperture radar，SAR)經過多年的發(fā)展［1－3］，成像方面很多問題已經得到解決［4，5］。目前的熱點和難點主要集中在新體制雷達的信號處理［6－8］或SAR圖像的解譯與應用研究上［9－10］。

圖像分割能夠從圖像中提取感興趣的信息，圖像分割是從圖像處理到圖像分析的關鍵步驟。圖像分割的方法有多種，主要有基于閾值、基于邊緣、基于區(qū)域、基于特定理論的圖像分割方法等［11－13］。

聚類作為一種無監(jiān)督的分類方法，在眾多領域應用廣泛［13］，例如生物學上的基因分類和動植物分類，圖像處理中的圖像分割、圖像增強、圖像壓縮、圖像檢索等。K均值聚類算法［14－17］是一種典型的基于劃分的聚類算法，該算法思想簡單，計算速度快，已經成為最常用的聚類算法之一。

本文以毫米波高分辨SAR圖像為研究對象，采用K均值聚類方法對SAR圖像進行分割，并對文獻中的自適應動態(tài)K均值聚類算法進行了分析與改進。城市區(qū)域、路和橋梁的分割結果驗證了本文改進算法相對已有算法在分割質量上的提升。

1 當前的K均值聚類算法

K均值聚類算法的基本思路是在最小化誤差函數的基礎上將數據劃分成K類。算法的處理過程［11，12］為:先指定聚類數目K及K個初始聚類中心，然后根據一定的準則將每個數據分配給最近的聚類中心。

將樣本空間X={x1，x2，…，xi，…，xn}的樣本分成K類，聚類中心為C={c1，c2，…，cj，…，cK}，用dij(xi，cj)表示樣本xi與其對應的中心cj間的距離，樣本空間內所有數據點與所屬聚類質心距離的總和用目標函數J來表示，為:

目標函數J越小，表明聚類越緊湊，聚類越優(yōu)。當選擇歐式距離作為樣本xi與其對應的中心cj間的距離時為屬于聚類j的數據樣本，nj為聚類j的樣本個數，式為:

為使目標函數最小，各聚類中心為:

K均值聚類算法流程如下:

(1)初始化，輸入樣本集及聚類數K，并在中隨機選取K個樣本作為初始聚類中心;

(2)初始聚類;

(3)按式計算新的聚類中心;

(4)重新聚類;

(5)反復進行(3)、(4)直至迭代結束，得到聚類結果。

稱上述K均值聚類算法為基本K均值聚類算法，記為KM_Basic。KM_Basic算法理論嚴密，計算簡單。但是聚類結果對初始聚類中心有很強的依賴性，容易收斂于局部極值點。初始聚類中心選取不當會對聚類結果產生很大的負面影響。

文獻［13］提出了全局K均值聚類算法，文獻［14］對全局K均值聚類算法進行了研究。全局K均值聚類算法通過迭代的方式來產生初始聚類中心。全局K均值聚類算法處理效率不高。文獻［12］提出了動態(tài)K均值聚類算法，動態(tài)K均值聚類算法能減小對聚類中心初值的依賴，改善性能，并且運算效率也較高。動態(tài)K均值聚類算法的適應度函數為聚類中心與屬于該中心區(qū)域內的所有像素之間的歐式距離之和:

若f(cj)越小，則中心的適應度越小，聚類越緊湊。動態(tài)K均值算法通過調整聚類來使各中心的適應度函數均衡，當適應度均衡時，認為聚類最優(yōu)。動態(tài)K均值聚類算法流程如下:

(1)給定初始聚類中心cj和權值α0(α0為常數)，αa=αb=α0;

(2)初始聚類;

(3)根據式計算每個聚類中心的適應度函數f (cj);

(4)設f(*)中，最大的f(*)對應的聚類中心為ci，最小的f(*)對應的聚類中心為cs。如果f (cs＜αaf(cl)，重新分配 cl聚類中的數據樣本，將其中xi＜cl的數據樣本分配給聚類cs;

(5)根據式計算新的聚類中心;

(6)更新閾值αa=αa－αa/K，重復(3)～(5)，直至f(cs)≥αaf(cl);

(7)按最小距離原則聚類一次;

(8)根據式計算新的聚類中心;

(9)更新權值αa=α0和 αb=αb－αb/K，重復(3)～(8)，直至f(cs)≥αbf(cl)。

記上述動態(tài)K均值聚類算法為KM_MKM。KM_MKM通過調整具有最大適應度函數值和最小適應度函數值的聚類區(qū)域的樣本，最終達到各區(qū)域適應度函數的均衡。KM_MKM能減少對初始聚類中心的依賴，改善并減少陷入局部極值引起的死區(qū)中心和中心冗余問題，但該算法對孤立數據和噪聲敏感的問題依然存在［12］。

KM_MKM將最大適應度函數聚類里面的部分樣本強制分配給最小適應度函數聚類區(qū)域，如果這些樣本是噪聲，那么具有最小適應度的聚類就將代表噪聲數據，這將導致錯誤的分類［12］?；诖?，文獻［12］提出了一種自適應動態(tài)K均值聚類算法，改變了KM_MKM算法強制分配樣本給具有最小適應度聚類的做法，引入最小距離原則來分配這些樣本，即將待分配樣本配給與這些樣本最近距離的聚類區(qū)域，以此來減少噪聲數據的錯誤分類。自適應動態(tài)K均值算法記為KM_AMKM，KM_AMKM與KM_MKM流程類似，只是在(4)中將其中xi＜cl的數據樣本按照最小距離原則分配給最近的聚類中心，而非統(tǒng)一分配給聚類cs。

2 當前算法分析與改進

KM_Basic給定聚類中心，然后以J最小為準則迭代聚類;KM_MKM以各Ji均衡為準則迭代聚類;KM_AMKM改進了KM_MKM中樣本的分配方式，在KM_MKM中樣本直接分配給最小適應度的聚類，在KM_AMKM中樣本根據最小距離原則分配給其他聚類。根據文獻［12］的研究結果，在以文獻中的灰度圖像為研究對象時，從KM_Basic、KM_MKM到KM_AMKM，分割結果依次更好。

本文沿用文獻［12］的思路，即認為“Ji均衡準則”優(yōu)于“J最小準則”，對KM_AMKM進行分析與改進。在樣本分配方式上，KM_AMKM對KM_ MKM進行了改進，但是在樣本的選取上，KM_ AMKM并未做到盡善盡美。

在KM_MKM、KM_AMKM中，將cl聚類中滿足xi＜cl的數據樣本剝離出cl聚類，重新進行分配。雖然從cl聚類中分離出一部分樣本能減小f(cl)，使得f(cs)≥αaf(cl)、f(cs)≥αbf(cl)，但是滿足xi＜cl的樣本可能也有一部分處在cl的鄰域內，這部分處在cl左鄰域內的樣本按照最小距離原則應當是分配給cl聚類的，一刀切式地把這部分樣本分離出cl聚類并不科學，也許會影響最終的聚類效率及聚類質量。定義一個常數ε，修改KM_MKM、KM_AMKM處理流程的(4)為:

(4)設f(*)中，最大的f(*)對應的聚類中心為cl，最小的f(*)對應的聚類中心為cs。如果f(cs)＜αaf(cl)，重新分配cl聚類中的數據樣本，將其中‖xi－cl‖≥ε的數據樣本按照最小距離原則分配給其余聚類;

稱上述改進后的聚類算法為修正的自適應動態(tài)K均值聚類算法，記為KM_RAMKM。

3 毫米波SAR圖像分割實驗

3.1 圖像分割結果評價指標

除了目視判讀，文獻［12，15］給出了如下的評價指標:

其中，I表示原始圖像，R表示分割的區(qū)域個數，Ai表示第i個區(qū)域的尺寸，ei表示原始圖像與分割圖像在第i個區(qū)域內每個對應像素的歐幾里德距離之和。

文獻［16］對式進行了修正，給出了如下評價指標:

其中，M×N表示圖像I的尺寸，R(A)表示尺寸為A的區(qū)域數，Max為最大尺寸的區(qū)域，1+1/A為加大了的小區(qū)域權值。

在對過分割和分割不足充分考慮的基礎上，文獻［17］提出了如下的分割質量評價指標:

本文對分割結果的評價將采用以上三個指標，指標數據越小，分割效果越好。

分割采用Intel(R)Core(TM)i3 CPU 550@ 3.20GHz，3.19GHz，2.99GB的內存，Microsoft Windows XP Professional Service Pack3系統(tǒng)，軟件采用MATLAB 7.5.0(R2007b)，分割效率用分割所用時間來衡量。

3.2 毫米波SAR圖像分割

分割圖像為Ka波段SAR數據，分辨率0.3m ×0.3m。圖1(a)為建筑物場景，圖1(b)為城區(qū)場景，圖1(c)為高架橋場景，圖1(d)為平地道路場景，圖1(a)和圖1(d)大小為600×600像素，圖1 (b)和圖1(c)大小為2000×2000像素。表1、表2、表3、表4分別為四個場景對應的分割時間及評價指標。

圖1 選取分割的場景

圖2 圖1(a)分割后的結果

圖3 圖1(b)分割后的結果

圖4 圖1(c)分割后的結果

圖5 圖1(d)分割后的結果

表1 圖1(a)場景分割時間及評價指標

表2 圖1(b)場景分割時間及評價指標

表3 圖1(c)場景分割時間及評價指標

表4 圖1(d)場景分割時間及評價指標

表2中，KM_RAMKM的時間比KM_AMKM的時間略長，表1、表3、表4中，KM_RAMKM的時間比KM_AMKM的時間略短。在每一個場景中，KM _RAMKM與KM_AMKM分割所用時間基本相當，可以認為兩種分割算法運算效率相同。

表1～表4對應的四種場景分割指標中，KM_ Basic評價指標最大，分割質量最差;KM_MKM和KM_AMKM評價指標小于KM_Basic評價指標; KM_RAMKM的評價指標最小，分割質量最好。圖2～圖5的分割結果中KM_RAMKM分割結果擁有最多的邊緣和細節(jié)信息，輪廓特征最明顯。

4 結 論

本文對幾種K均值聚類算法進行了分析，改進了自適應動態(tài)K均值聚類算法中最大適應度函數聚類樣本的選擇準則。改進算法與自適應動態(tài)K均值聚類算法運算效率相當，分割質量有明顯改善。毫米波SAR圖像分割實驗表明，在SAR圖像城區(qū)建筑及路橋的分割應用中，改進算法比已有算法分割效果更好。

［1］Ghasr M T，Case J T，Zoughi R.Novel reflectometer for millimeter－wave 3－D holographic imaging［J］.IEEE Instrumentation and Measurement Society，2014，63(5): 1328 －1336.

［2］Fjortoft R，Gaudin J，Pourthie N，et al.KaRIn on SWOT:Characteristics of near－nadir Ka－band interferometric SAR imagery［J］.IEEE Transactions on Geoscience and Remote Sensing，2014，52(4):2172－2185.

［3］Anghel A，Vasile G，Cacoveanu R，et al.Short－range wideband FMCW radar for millimetric displacement measurements［J］.IEEE Transactions on Geoscience and Remote Sensing，2014，52(9):5633－5642.

［4］Zhang S X，Xing M D，Xia X G，et al.Focus improvement of high－squint SAR based on azimuth dependence of quadratic range cell migration correction［J］.IEEE Geoscience and Remote Sensing Letters，2013，10(1): 150－154.

［5］Fiss J，Curless B，Szeliski R.Refocusing plenoptic images using depth－adaptive splatting［C］∥Proc.of IEEE International Conference on Computational Photography，2014:1－9.

［6］Garren D A.Smear signature morphology of surface targets with arbitrary motion in spotlight synthetic aperture radar imagery［J］.IET Radar，Sonar＆Navigation，2014，8(5):435－448.

［7］Spencer M F，Thornton D E，Hyde M W，et al.Piston phase compensation of tiled apertures in the presence of turbulence and thermal blooming［C］∥Proc.of the IEEE Aerospace Conference，2014:1－20.

［8］邢濤，胡慶榮，李軍等.基于非均勻FFT的超寬帶合成孔徑雷達高效成像算法［J］.系統(tǒng)工程與電子技術，2015，37(2):291－296.

［9］李小平，王衛(wèi)衛(wèi)，羅亮等.圖像分割的改進稀疏子空間聚類方法［J］.系統(tǒng)工程與電子技術，2015，37 (10):2418－2424.

［10］陳祥，孫俊，尹奎英等.基于Otsu與海域統(tǒng)計特性的SAR圖像海陸分割算法［J］.數據采集與處理，2014，29(4):603－608.

［11］張新野.基于聚類分析的圖像分割方法研究［D］.大連:大連海事大學，2012.

［12］梁燁煒.K－均值聚類算法的改進及其應用［D］.長沙:湖南大學，2012.

［13］Sulaiman S N，Isa N A M.Adaptive fuzzy－K－means clustering algorithm for image segmentation［J］.IEEE Transactions on Consumer Electronics，2010，56(14): 2661－2668.

［14］趙麗.全局K－均值聚類算法研究與改進［D］.西安:西安電子科技大學，2013.

［15］Likas，Vlassis M，Verbeek J.The global k－means clustering algorithm［J］.Pattern Recognition，2003，36(2):451－461.

［16］Mashor M Y.Hybrid Training Algorithm for RBF Network［J］.International Journal of the Computer，2000，8(2):50－65.

［17］Borsotti M，Campadelli P，Schettini R.Quantitative evaluation of color image segmentation results［J］.Pattern Recognition Letters，1998，19(8):741－747.

Study on Synthetic Aperture Radar Image Segmentation Algorithm Based on Clustering

Xing Tao1，Zhao Haibin2，Hu Qingrong1，Li Jun1，Wang Guanyong1
(1.No.23 Research Institute of the Second Research Academy，CASIC，Beijing 100854; 2.Military Representative Office of PLA positioned in No.23 Research Institute of the Second Research Academy，CASIC，Beijing 100854)

Aiming at SAR image segmentation issue，K mean value clustering algorithm is studied;adaptive dynamic K mean value clustering algorithm is analyzed，and sample separation criteria of maximum fitness function clustering is improved.MMW SAR image segmentation shows that the improved algorithm has better performance and more excellent index than that of basic K mean value clustering algorithm，dynamic K mean value clustering algorithm and adaptive dynamic K mean value clustering algorithm for segmentation of urban area building，road，bridge scenes.The improved algorithm has correspondent efficiency with adaptive dynamic K mean value clustering algorithm in operation efficiency.

synthetic aperture radar;image segmentation;clustering;K mean value

TN957

A

1008-8652(2016)04-001-05

2016-10-23

國家自然科學基金(61271417)

邢 濤(1986－)，男，博士研究生。研究方向為雷達成像技術。