基于自適應權重法的K-means模型對遙感圖像分割

姜文斌 劉麗萍,3* 孫學宏

1(寧夏大學物理與電子電氣工程學院 寧夏 銀川 750021)2(寧夏大學信息工程學院 寧夏 銀川 750021)3(寧夏沙漠信息智能感知重點實驗室 寧夏 銀川 750021)

0 引 言

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

本文提出一種基于自適應權重法的K-means混合算法。傳統的K-means算法并不能保證完全收斂，對質心k的選取很敏感，所以k的值對圖像分割結果影響很大。而自適應權重法通過對慣性權重w的不斷優化來找出一個最合適的k值。此方法降低了算法的迭代次數，并且提高了分割精度。通過對不同場景的遙感圖像進行分割實驗，并且與K-means、GA等算法作比較，分割精度得到了不錯的提高。

1 K-means聚類

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

(1)

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

(2)

且滿足：

(3)

計算目標函數J，如果J保持穩定，代表聚類結果達到最優，可以結束迭代方法，否則接著更新迭代聚類的中心點。

(4)

2 改進的K-means聚類算法

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

2.1 二維高斯濾波

使用二維高斯函數對圖像邊緣進行濾波，由于該函數具備旋轉對稱性，所以可保證濾波時在各個方向具有相同的平滑水平，且當像素點距離中心點越近時權值越大，從而可以使得像素點清晰。二維高斯平滑函數為：

(5)

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

(6)

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

(7)

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

(8)

(9)

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

2.2 權重優化

根據圖像集群的早熟收斂度和個體適應值，可以確定慣性權重的變化，設定粒子pi的適應值為fi，最優粒子適應度是fm，則粒子群的平均適應值為[7]：

(10)

(11)

(12)

(13)

式中：k1、k2為控制參數，k1用來控制w的上限，k2主要用來控制w的調節能力。

2.3 位置調整

采用非線性動態慣性權重系數公式為：

(14)

式中：f表示像素點的目標函數值；favg和fmin分別表示像素點的均值和最小值。然后初始化圖像集群中各個像素點的位置和速度，且對每個像素點的適應度進行評價，把像素點的位置和適應值放在的個體極值pbest中，將所有pbest中最優適應值的位置和適應值保存在全局極值gbest中[8]。更新像素點的位移和速度為:

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)

更新權重：將每個像素點的適應值與像素點的最佳位置比較，若是離得特別近，則將當前值作為最優聚類中心。

2.4 更新簇的中心

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

(16)

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

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

3 實驗及結果分析

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

(a) 原圖

(b) GA算法

(c) k-means算法

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

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

(17)

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

(18)

式中：Os表示多出的像素點的個數。欠分割率數學定義如下：

(19)

式中：Us表示少了的像素點的個數。不同算法的分割精度如表1所示。

表1 不同方法的分割精度

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

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

圖2 誤差概率與尺寸的關系

4 結 語

本文通過使用對慣性權重的不斷優化，找出一個最優聚類中心從而對傳統的K-means算法加以改進。通過實驗可以發現，本文提出的改進的K-means算法對圖像的分割效果更為顯著，更加適用于遙感圖像的分割。