基于自適應(yīng)權(quán)重法的K-means模型對(duì)遙感圖像分割

姜文斌 劉麗萍,3* 孫學(xué)宏

1(寧夏大學(xué)物理與電子電氣工程學(xué)院 寧夏 銀川 750021)2(寧夏大學(xué)信息工程學(xué)院 寧夏 銀川 750021)3(寧夏沙漠信息智能感知重點(diǎn)實(shí)驗(yàn)室 寧夏 銀川 750021)

0 引 言

遙感圖像分割是一種重要的圖像預(yù)處理方法，在更進(jìn)一步的圖像處理中起著重要的作用。良好的分割算法使得圖像處理事半功倍，并且是解決復(fù)雜圖像處理問題的突破口[1]。到目前為止，已經(jīng)有很多學(xué)者將計(jì)算機(jī)領(lǐng)域的圖像分割算法應(yīng)用于圖像分割過程中，并且已經(jīng)進(jìn)行了深入的研究，提出了各種不同的算法，但是針對(duì)遙感圖像的分割算法還是很少。遙感圖像具有大尺寸、多尺度，地物類型和紋理特征豐富和多波段數(shù)據(jù)等特征，與其他類型的圖像分割相比，遙感圖像的分割難度更大，對(duì)精度要求更高。Hou等[2]提出了一種聚類之前通過直方圖均衡來變換相似性矩陣，在數(shù)據(jù)聚類和圖像分割實(shí)驗(yàn)中測試了增強(qiáng)的聚類算法，雖然這種轉(zhuǎn)換被證明可以有效地消除對(duì)相似性度量的敏感性，但它也會(huì)導(dǎo)致過度分割，從而使得分割精度不高；王民等[3]提出了一種基于核模糊C-均值和融合期望最大化(EM)算法混合聚類的遙感圖像分割，此方法利用原始KFCM算法中的隱含因子將像素進(jìn)行預(yù)分類，接著使用最大期望算法對(duì)分類結(jié)果進(jìn)行評(píng)價(jià)，用此方法來對(duì)遙感圖像進(jìn)行聚類分割，提高了圖像分割的速度與精度；劉戰(zhàn)杰等[4]提出了一種融合的遙感圖像分割算法,該算法將局部和全局的特征進(jìn)行融合，使用一種高級(jí)數(shù)據(jù)結(jié)構(gòu)對(duì)融合區(qū)域進(jìn)行加速，不僅提高了速度，對(duì)精度也有提升。

本文提出一種基于自適應(yīng)權(quán)重法的K-means混合算法。傳統(tǒng)的K-means算法并不能保證完全收斂，對(duì)質(zhì)心k的選取很敏感，所以k的值對(duì)圖像分割結(jié)果影響很大。而自適應(yīng)權(quán)重法通過對(duì)慣性權(quán)重w的不斷優(yōu)化來找出一個(gè)最合適的k值。此方法降低了算法的迭代次數(shù)，并且提高了分割精度。通過對(duì)不同場景的遙感圖像進(jìn)行分割實(shí)驗(yàn)，并且與K-means、GA等算法作比較，分割精度得到了不錯(cuò)的提高。

1 K-means聚類

K-means是由MacQueen提出的一種非監(jiān)督學(xué)習(xí)算法[5]，該算法是將已知的樣本分成不同的具有相似特征的類。若要使得K-means的聚類效果達(dá)到最好，需要每個(gè)初始點(diǎn)到分好類的每一類初始化點(diǎn)距離的平方和最小。

(1)

式中：Ji為第i類聚類的函數(shù)；K為聚類的總個(gè)數(shù)；Xj為第j個(gè)輸入向量；Ci為第i個(gè)聚類中心，wji為隸屬度矩陣。首先，選擇k個(gè)初始質(zhì)心，將每個(gè)像素點(diǎn)合并到與之最近的質(zhì)心，分配到質(zhì)心的點(diǎn)作為一個(gè)簇。接著按照這些簇的位置，迭代簇的中心。重復(fù)分配和迭代步驟，直到簇的位置不發(fā)生變化。隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)Ci，i=1,2,…,k; 把這些數(shù)據(jù)點(diǎn)當(dāng)作初始中心。決定每個(gè)像素點(diǎn)所屬的聚類，若像素點(diǎn)Xj屬于第i聚類，則隸屬度矩陣wji=1，否則為0。

(2)

且滿足：

(3)

計(jì)算目標(biāo)函數(shù)J，如果J保持穩(wěn)定，代表聚類結(jié)果達(dá)到最優(yōu)，可以結(jié)束迭代方法，否則接著更新迭代聚類的中心點(diǎn)。

(4)

2 改進(jìn)的K-means聚類算法

自適應(yīng)權(quán)重法是一種基于權(quán)重改進(jìn)的粒子群算法[6]，傳統(tǒng)的K-means算法對(duì)初始質(zhì)心的選取具有較高的依賴性，并且容易陷入局部最優(yōu)。本文引入了自適應(yīng)權(quán)重法里的慣性權(quán)重w，改變w的值能夠改良算法進(jìn)行全局搜尋的能力，從而防止陷入部分最優(yōu)并高效搜尋。

2.1 二維高斯濾波

使用二維高斯函數(shù)對(duì)圖像邊緣進(jìn)行濾波，由于該函數(shù)具備旋轉(zhuǎn)對(duì)稱性，所以可保證濾波時(shí)在各個(gè)方向具有相同的平滑水平，且當(dāng)像素點(diǎn)距離中心點(diǎn)越近時(shí)權(quán)值越大，從而可以使得像素點(diǎn)清晰。二維高斯平滑函數(shù)為：

(5)

式中:δ為高斯平滑函數(shù)的尺度參數(shù)。G(x,y,δ)在不同尺度參數(shù)δ下的一階偏導(dǎo)數(shù)分別為：

(6)

求原始圖像f(x,y)分別與高斯函數(shù)的不同尺度下的一階偏導(dǎo)數(shù)的卷積，于是得到兩個(gè)方向的梯度值分別如下：

(7)

則梯度幅值和梯度方向分別為：

(8)

(9)

式中:M(x,y)為圖像上點(diǎn)(x,y)的邊緣強(qiáng)度矢量；A(x,y)為圖像上點(diǎn)(x,y)的法向矢量，垂直于邊緣的方向。

2.2 權(quán)重優(yōu)化

根據(jù)圖像集群的早熟收斂度和個(gè)體適應(yīng)值，可以確定慣性權(quán)重的變化，設(shè)定粒子pi的適應(yīng)值為fi，最優(yōu)粒子適應(yīng)度是fm，則粒子群的平均適應(yīng)值為[7]：

(10)

(11)

(12)

(13)

式中：k1、k2為控制參數(shù)，k1用來控制w的上限，k2主要用來控制w的調(diào)節(jié)能力。

2.3 位置調(diào)整

采用非線性動(dòng)態(tài)慣性權(quán)重系數(shù)公式為：

(14)

式中：f表示像素點(diǎn)的目標(biāo)函數(shù)值；favg和fmin分別表示像素點(diǎn)的均值和最小值。然后初始化圖像集群中各個(gè)像素點(diǎn)的位置和速度，且對(duì)每個(gè)像素點(diǎn)的適應(yīng)度進(jìn)行評(píng)價(jià)，把像素點(diǎn)的位置和適應(yīng)值放在的個(gè)體極值pbest中，將所有pbest中最優(yōu)適應(yīng)值的位置和適應(yīng)值保存在全局極值gbest中[8]。更新像素點(diǎn)的位移和速度為:

xi,j(t+1)=xi,j(t)+vi,j(t+1)j=1,2,…,dvi,j(t+1)=w·vi,j(t)+c1r1[pi,j-xi,j(t)]+c2r2[pg,j-xi,j(t)]

(15)

更新權(quán)重：將每個(gè)像素點(diǎn)的適應(yīng)值與像素點(diǎn)的最佳位置比較，若是離得特別近，則將當(dāng)前值作為最優(yōu)聚類中心。

2.4 更新簇的中心

由于使用的是歐幾里得距離，所以采用誤差平方和SSE(Sum of the Squared Error)[9]作為對(duì)比函數(shù)來和初始聚類中心作比較，運(yùn)行改進(jìn)的K-means算法得到不同的結(jié)果：

(16)

式中：k代表的是聚類中心的值，ci則表示開始的第i個(gè)聚類中心，dist(·)則表示的是像素點(diǎn)到聚類中心的SSE距離。

當(dāng)算法停止時(shí)，如果像素點(diǎn)的分布分散，則Δ比較大，w變小，此時(shí)算法局部搜索能力加強(qiáng)，從而使得群體趨于收斂；若像素點(diǎn)分布聚集，則Δ比較小，w變大，這樣像素點(diǎn)的探測能力增加，可以很好地跳出局部最優(yōu)。

3 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證提出方法的實(shí)施性及優(yōu)點(diǎn)，使用由武漢大學(xué)標(biāo)注的RSOD-Dataset的數(shù)據(jù)集，分別對(duì)飛機(jī)場、立交橋、油桶的遙感圖像進(jìn)行分割。本實(shí)驗(yàn)在Matlab R2014a環(huán)境下編程實(shí)現(xiàn)。分別將遺傳算法分割、傳統(tǒng)的K-means分割和本文提出改進(jìn)的K-means方法進(jìn)行實(shí)驗(yàn)對(duì)比。原圖如圖1(a)所示。在圖1(b)中，由于GA算法本身的特點(diǎn)，導(dǎo)致它的局部搜索能力較差[10]，所以在進(jìn)行圖像分割時(shí)一些邊緣區(qū)域分割的不完整出現(xiàn)漏分割和欠分割的現(xiàn)象；在圖1(c)中，所選圖像的一些待分割物體與周圍的區(qū)別性不強(qiáng)，故把周圍的背景也誤判成待分割物體，造成了過分割的現(xiàn)象；在圖1(d)中使用本文提出的改進(jìn)的K-means算法，解決了上面兩種算法出現(xiàn)的過分割與欠分割的問題，很好地消除了一些誤分像素，使得分割結(jié)果更加精確。由此可見，本文提出的改進(jìn)的K-means算法對(duì)遙感圖像的分割有較為良好的效果。

(a) 原圖

(b) GA算法

(c) k-means算法

(d) 改進(jìn)的k-means算法圖1 不同方法的分割結(jié)果

為了能更好地體現(xiàn)提出算法的有效性，本文使用分割精度、過分割率和欠分割率[11]來評(píng)價(jià)本算法。分割精度是指分割后分割物的面積占圖像中分割物面積的比率，定義如下所示：

(17)

式中：Rm是指圖像原本的面積，Tm是指算法分割后得到的圖像的面積，|Rm-Tm|表示錯(cuò)誤分割的面積。過分割率數(shù)學(xué)定義如下：

(18)

式中：Os表示多出的像素點(diǎn)的個(gè)數(shù)。欠分割率數(shù)學(xué)定義如下：

(19)

式中：Us表示少了的像素點(diǎn)的個(gè)數(shù)。不同算法的分割精度如表1所示。

表1 不同方法的分割精度

OS和US的取值范圍都在0和1之間，當(dāng)值為0時(shí)表示分割效果最好，當(dāng)值為1時(shí)表示完全沒有分割。本實(shí)驗(yàn)分割圖像的參考面積由手工畫出，精度相對(duì)較高，分別用GA算法、K-means算法與本文提出的算法將分割后的圖片面積與參考面積作比較，得到表1的結(jié)果。根據(jù)表1的數(shù)據(jù)分析，傳統(tǒng)的K-means分割算法比GA的分割效果要好，而本文提出的算法相對(duì)于傳統(tǒng)K-means算法對(duì)遙感圖像的分割精度又提高了兩個(gè)百分點(diǎn)。

接下來對(duì)每個(gè)類，使用隨機(jī)初始化的方法繪制錯(cuò)誤概率[12]與尺寸圖。在圖2中，橫坐標(biāo)代表的是分割圖像的面積，縱坐標(biāo)表示的是錯(cuò)誤概率，表示的是不同面積內(nèi)分割的錯(cuò)誤概率。本實(shí)驗(yàn)選取了9個(gè)點(diǎn)，分別對(duì)這9個(gè)點(diǎn)的面積進(jìn)行誤差分析，可以發(fā)現(xiàn)在待分割面積很小的時(shí)候，錯(cuò)誤概率很小，誤分割的像素也很少。隨著面積的不斷增大，GA算法的誤差概率上升的最快，其次是K-means，本文提出的算法變化效果平緩。因此可以看出，本文提出的改進(jìn)的K-means算法對(duì)遙感圖像的分割效果更為顯著。

圖2 誤差概率與尺寸的關(guān)系

4 結(jié) 語

本文通過使用對(duì)慣性權(quán)重的不斷優(yōu)化，找出一個(gè)最優(yōu)聚類中心從而對(duì)傳統(tǒng)的K-means算法加以改進(jìn)。通過實(shí)驗(yàn)可以發(fā)現(xiàn)，本文提出的改進(jìn)的K-means算法對(duì)圖像的分割效果更為顯著，更加適用于遙感圖像的分割。