譜聚類算法及其在SAR圖像分割中的應(yīng)用研究

摘 要：譜聚類算法作為一種高效的智能聚類算法被廣泛地研究與應(yīng)用，它與傳統(tǒng)的聚類算法相比，具有明顯的優(yōu)勢(shì)。文章首先對(duì)譜聚類理論進(jìn)行了概述，介紹了圖劃分準(zhǔn)則、譜松弛及譜聚類算法，后介紹算法在SAR圖像分割中的應(yīng)用，并對(duì)分割時(shí)出現(xiàn)的一些問題加以分析和討論，對(duì)研究譜聚類算法及其對(duì)SAR圖像的分割具有一定得理論參考。

關(guān)鍵詞：譜聚類；SAR圖像；圖像分割

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2015）29-0046-02

1 譜聚類算法

譜聚類算法基于譜圖劃分理論，它將聚類問題看成是圖的劃分問題，使用數(shù)據(jù)樣本的相似度矩陣的特征向量進(jìn)行聚類。該算法對(duì)凸型的球形空間或非凸的任意空間的聚類表現(xiàn)不敏感，易于得到全局最優(yōu)解，較傳統(tǒng)聚類算法（K-means和最大期望值EM算法）優(yōu)勢(shì)明顯，是當(dāng)前流行的一種高性能聚類算法。利用譜聚類算法實(shí)現(xiàn)圖像的分割是人們較感興趣的一個(gè)研究方向。

圖的最優(yōu)劃分其實(shí)是一個(gè)NP難問題，有效的解決辦法就是對(duì)原問題進(jìn)行實(shí)數(shù)域松弛，進(jìn)而可將圖的劃分轉(zhuǎn)換為求解矩陣的特征值和特征向量問題。對(duì)于合成孔徑雷達(dá)圖像（簡(jiǎn)稱SAR圖像）的分割來(lái)講，譜聚類算法除了要考慮圖像的光譜特性、空間特征等因素，還要考慮算法的計(jì)算速度及內(nèi)存消。

2 譜聚類理論及算法實(shí)現(xiàn)

2.1 譜聚類理論算法

得到圖G的一個(gè)最優(yōu)二分圖即是對(duì)公式（1）最小化，但這種做法傾向于獲得不均衡、歪斜的劃分。基于2-way劃分的規(guī)范割判據(jù)（Ncut）可以克服這種現(xiàn)象，其目標(biāo)函數(shù)為：

將x松弛至連續(xù)實(shí)數(shù)域 ，求解minNcut（A，B）的問題可以轉(zhuǎn)化為下式（4）的優(yōu)化問題：

根據(jù)Rayleigh商原理的知識(shí)，我們可將對(duì)（4）式的優(yōu)化問題轉(zhuǎn)化為式（5）中特征值和特征向量的求解問題。

2.2 譜聚類的圖像分割方法實(shí)現(xiàn)步驟

雖然第二最小特征值？姿2所對(duì)應(yīng)的特征向量x2（也稱Fiedler向量）包含了豐富的圖劃分信息。但僅僅根據(jù)x2對(duì)數(shù)據(jù)進(jìn)行迭代性聚類，不僅計(jì)算效率低且聚類結(jié)果不穩(wěn)定。研究發(fā)現(xiàn)，同時(shí)使用多個(gè)特征向量可以避免由于信息損失造成的不穩(wěn)定性，并且直接進(jìn)行k路分割可以得到更好的聚類效果。一種基于多路劃分譜聚類的圖像分割方法實(shí)現(xiàn)步驟。

2.2.1 預(yù)處理

2.2.2 譜映射

2.2.3 聚 類

將Y的每一行看成是k維空間Rk中的一個(gè)樣本，通過K-Means算法將這些樣本聚成k類，當(dāng)且僅當(dāng)Y的第i行被分配為j類時(shí)才將圖像的像素點(diǎn)vi分配為j類。

3 關(guān)于SAR圖像分割的兩大問題

SAR圖像不同于醫(yī)學(xué)圖像、紋理圖像和彩色圖像的分割，由于其圖像本身的特點(diǎn)，如成像機(jī)理、對(duì)比度、一致性、信息熵、灰度共生矩陣、小波能量等特征，直接采用傳統(tǒng)的分割方法往往不能夠得不出較好的分割結(jié)果。針對(duì)SAR圖像的分割問題值得討論。

3.1 構(gòu)造相似度問題

對(duì)于SAR圖像的分割缺乏標(biāo)準(zhǔn)統(tǒng)一的相似度構(gòu)造函數(shù)，目前針對(duì)這方面的研究，國(guó)內(nèi)外許多研究、科研人員進(jìn)行的大量工作。如：提取一窗口大小中像素點(diǎn)的小波能力、灰度共生矩陣等特征，并計(jì)算窗口內(nèi)像素點(diǎn)的平均特征構(gòu)造相似度矩陣；另一種方法是，首先對(duì)采用分水嶺算法得出的特征塊集合X聚成k 個(gè)子集合進(jìn)行預(yù)處理，再使用高斯核函數(shù)構(gòu)造相似度矩陣。3.2 時(shí)空復(fù)雜度問題

對(duì)于一個(gè)包含n個(gè)像素點(diǎn)的圖像（如一副256×256的圖像，n=28×28）來(lái)講，算法的計(jì)算復(fù)雜度數(shù)量級(jí)為n3，往往致使計(jì)算機(jī)內(nèi)存溢出和處理器計(jì)算時(shí)間過長(zhǎng)。對(duì)內(nèi)存的高消耗和處理器的計(jì)算速度優(yōu)化問題顯得尤為重要。典型的一種減少計(jì)算復(fù)雜度的方法是Fowlkes等人提出的Nystrom算法，該方法使用優(yōu)化標(biāo)準(zhǔn)割準(zhǔn)則對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化、逼近，并對(duì)矩陣特征矩陣進(jìn)行稀疏，提取出典型特征方式來(lái)減少計(jì)算量。另一種是基于形態(tài)學(xué)分水嶺的技術(shù)，并結(jié)合譜聚并結(jié)合譜聚類算法的聚類優(yōu)勢(shì)得出的一種多階段聚類算法。該算法也能夠大大降低構(gòu)造相似性矩陣時(shí)的計(jì)算量。

4 結(jié) 語(yǔ)

本文介紹了譜聚類的理論基礎(chǔ)及算法實(shí)現(xiàn)原理，并給出了基于譜聚類的SAR圖像分割方法。最后，對(duì)SAR圖像的分割問題加以分析，并對(duì)SAR圖像的分割研究方向加以引導(dǎo)，對(duì)基于譜聚類算法的合成孔徑雷達(dá)圖像和航拍圖像的目標(biāo)定位和識(shí)別研究具有一定的理論參考和指導(dǎo)意義。

參考文獻(xiàn)：

[1] Luxburg U V.A tutorial on spectral clustering [J].Statistics and Computing，2007，（4）.

[2] 葛洪偉，李志偉，楊金龍.基于局部密度估計(jì)和近鄰關(guān)系關(guān)系傳播的 譜聚類[J].模式識(shí)別與人工智能，2014，（9）.

[3] 李志偉，葛洪偉，楊金龍.基于鄰里關(guān)系傳播與模式合并的譜聚類[J].計(jì)算機(jī)工程，2014，（6）.

[4] 李志偉.基于近鄰傳播和密度信息的譜聚類算法研究與應(yīng)用[D].無(wú) 錫：江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，2014.

[5] Shi Jianbo，Malik J.Normalized cuts and image segmentation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，（8）.

[6] 賈建華，焦李成.空間一致性約束譜聚類算法用于圖像分割[J].紅外與毫米波學(xué)報(bào)，2010，（1）.

[7] Fowlkes C，Belongie S，Chung F，et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，（2）.