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

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

總體工程

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

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

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

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

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

0 引 言

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

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

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

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

1 當(dāng)前的K均值聚類算法

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

將樣本空間X={x1，x2，…，xi，…，xn}的樣本分成K類，聚類中心為C={c1，c2，…，cj，…，cK}，用dij(xi，cj)表示樣本xi與其對(duì)應(yīng)的中心cj間的距離，樣本空間內(nèi)所有數(shù)據(jù)點(diǎn)與所屬聚類質(zhì)心距離的總和用目標(biāo)函數(shù)J來表示，為:

目標(biāo)函數(shù)J越小，表明聚類越緊湊，聚類越優(yōu)。當(dāng)選擇歐式距離作為樣本xi與其對(duì)應(yīng)的中心cj間的距離時(shí)為屬于聚類j的數(shù)據(jù)樣本，nj為聚類j的樣本個(gè)數(shù)，式為:

為使目標(biāo)函數(shù)最小，各聚類中心為:

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

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

(2)初始聚類;

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

(4)重新聚類;

(5)反復(fù)進(jìn)行(3)、(4)直至迭代結(jié)束，得到聚類結(jié)果。

稱上述K均值聚類算法為基本K均值聚類算法，記為KM_Basic。KM_Basic算法理論嚴(yán)密，計(jì)算簡單。但是聚類結(jié)果對(duì)初始聚類中心有很強(qiáng)的依賴性，容易收斂于局部極值點(diǎn)。初始聚類中心選取不當(dāng)會(huì)對(duì)聚類結(jié)果產(chǎn)生很大的負(fù)面影響。

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

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

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

(2)初始聚類;

(3)根據(jù)式計(jì)算每個(gè)聚類中心的適應(yīng)度函數(shù)f (cj);

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

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

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

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

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

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

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

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

2 當(dāng)前算法分析與改進(jìn)

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

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

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

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

稱上述改進(jìn)后的聚類算法為修正的自適應(yīng)動(dòng)態(tài)K均值聚類算法，記為KM_RAMKM。

3 毫米波SAR圖像分割實(shí)驗(yàn)

3.1 圖像分割結(jié)果評(píng)價(jià)指標(biāo)

除了目視判讀，文獻(xiàn)［12，15］給出了如下的評(píng)價(jià)指標(biāo):

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

文獻(xiàn)［16］對(duì)式進(jìn)行了修正，給出了如下評(píng)價(jià)指標(biāo):

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

在對(duì)過分割和分割不足充分考慮的基礎(chǔ)上，文獻(xiàn)［17］提出了如下的分割質(zhì)量評(píng)價(jià)指標(biāo):

本文對(duì)分割結(jié)果的評(píng)價(jià)將采用以上三個(gè)指標(biāo)，指標(biāo)數(shù)據(jù)越小，分割效果越好。

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

3.2 毫米波SAR圖像分割

分割圖像為Ka波段SAR數(shù)據(jù)，分辨率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分別為四個(gè)場景對(duì)應(yīng)的分割時(shí)間及評(píng)價(jià)指標(biāo)。

圖1 選取分割的場景

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

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

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

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

表1 圖1(a)場景分割時(shí)間及評(píng)價(jià)指標(biāo)

表2 圖1(b)場景分割時(shí)間及評(píng)價(jià)指標(biāo)

表3 圖1(c)場景分割時(shí)間及評(píng)價(jià)指標(biāo)

表4 圖1(d)場景分割時(shí)間及評(píng)價(jià)指標(biāo)

表2中，KM_RAMKM的時(shí)間比KM_AMKM的時(shí)間略長，表1、表3、表4中，KM_RAMKM的時(shí)間比KM_AMKM的時(shí)間略短。在每一個(gè)場景中，KM _RAMKM與KM_AMKM分割所用時(shí)間基本相當(dāng)，可以認(rèn)為兩種分割算法運(yùn)算效率相同。

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

4 結(jié) 論

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

［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的超寬帶合成孔徑雷達(dá)高效成像算法［J］.系統(tǒng)工程與電子技術(shù)，2015，37(2):291－296.

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

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

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

［12］梁燁煒.K－均值聚類算法的改進(jìn)及其應(yīng)用［D］.長沙:湖南大學(xué)，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－均值聚類算法研究與改進(jìn)［D］.西安:西安電子科技大學(xué)，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

國家自然科學(xué)基金(61271417)

邢 濤(1986－)，男，博士研究生。研究方向?yàn)槔走_(dá)成像技術(shù)。