基于改進K-means的彩色圖像分割算法

郭云云，高保祿，趙子潤，杜 德，田 力

(太原理工大學 軟件學院，山西 晉中 030600)

0 引 言

在圖像的研究與應用中，往往只關注圖像的某部分，如醫學領域對圖像病變區域進行檢測等，都需通過圖像分割把目標從整體圖像中分離[1]。圖像分割的效果直接決定后續圖像分析和處理的結果，而現有彩色圖像分割算法存在耗時長和分割效果不理想等問題[2]。因此，提出一種高精度和高效率的彩色圖像分割方法是十分必要的。

目前的彩色圖像分割方法主要有閾值分割法、區域分割法、聚類分析法和神經網絡法等[3]。聚類分析法因其算法原理和圖像分割性質極相似，一直被用于圖像分割[4]。其中，K-means算法具有易于實現、簡單高效的特性，應用最為廣泛，但也存在對初始參數敏感等問題。對此，Aimi等[5]提出通過計算類內方差不斷調整數據分類與中心點位置，該方法可自適應獲取初始參數，但計算量大，降低了分割效率。文獻[6]使用減法聚類算法估計初始中心的位置，分割結果質量得到提高，但沒有擺脫對用戶輸入參數的依賴。Prahara A等[7]將直方圖閾值和K-means算法結合確定初始參數，再對分割后區域進行分裂合并，損壞了物體的邊界信息，導致分割線條不連續。以上算法采用了不同的方法獲取K-means的初始參數，但相似度的計算都是采用像素位置的空間距離，特征單一，忽略了其它重要特征，可能造成像素點的錯分類，使分割效果不理想。

基于此，本文提出基于改進K-means的彩色圖像分割算法。通過圖像的HSI顏色空間直方圖自適應獲得K-means算法的初始參數，減少對用戶輸入參數的依賴。然后提出提取圖像的LDP(local directional pattern)紋理特征，構建像素點的紋理、顏色和空間坐標多維特征計算像素點間的相似度，克服僅使用一個特征的局限性，更好表示像素點的分布特征，使圖像分割結果更符合人的主觀視覺。

1 K-means算法及其在圖像分割中的應用

K-means算法[8]通過預設分類數K和隨機選取的初始中心點，不斷迭代劃分樣本、計算聚類中心，使目標函數的值最優，即E值最小。K-means算法進行圖像分割是根據像素點的特征對其進行聚類。

X={X1,X2,…,Xn}為含有n個樣本數據的集合，{C1,C2,C3,…,CK}為K個中心點，兩個樣本點間的距離采用歐氏距離計算

Dist(Xi,Xj)=(Xi-Xj)2

(1)

聚類中心的更新方法

(2)

目標函數E定義為

(3)

其中，nj和Xj分別表示以Ci為中心點的子集中樣本點的個數、以Ci為中心的子集中的樣本點。利用K-means算法進行圖像分割的具體步驟如下：

(1)輸入彩色圖像、分類數K；

(2)隨機選取K個初始中心點；

(3)按式(1)計算其余像素點與初始中心間的距離，將其歸類為最近的中心點所在的子集；

(4)更新類中心；

(5)循環步驟(3)、(4)直到中心點不再變化；

(6)返回分割結果。

可見，K-means算法進行圖像分割存在的問題主要在于難以預先設定合適的分類數K和隨機選取初始中心點造成聚類結果不穩定。另外，使用單一的空間距離特征計算像素間的相似度可能使像素點錯分類，從而導致圖像分割結果不理想。

2 自適應K-means初始參數計算

一些分割灰度圖像的方法被用于分割彩色圖像，但分割效果往往不理想，因為這些方法只考慮了圖像的灰度值而不考慮色度。對于彩色圖像，顏色是最有效且易獲取的特征。因此，選擇合適的色彩空間是很重要的。RGB顏色模型是目前硬件設備上顯示圖像數據應用最廣的模型，它以R、G、B這3種分量的組合表示顏色。但由于各分量與亮度間具有高度的相關性，RGB空間對光照過于敏感，不適用于圖像的分割[9]。因此本文使用HSI顏色空間，HSI顏色空間采用更符合人視覺系統感知色彩的方式，用色調、飽和度和亮度3種相互獨立的特征量感知顏色，減少了對光照的敏感度，提高了色彩識別準確度。另外，獨立的分量也便于分開處理，可以簡化圖像處理的工作量。為了降低計算復雜度并更好地區分相似顏色，對顏色進行量化[10]，得到顏色特征值L({Li∈Z+∪0|0 ≤Li≤ 71})。

本文提出的初始參數確定方法分為兩步。一是構建圖像的HSI顏色空間直方圖，二是對其進行垂直與水平掃描。首先將顏色特征值L作為橫軸，將落在每個顏色區間內的像素點總數(用P表示)作為縱軸構建圖像的顏色直方圖。然后對顏色直方圖執行兩次掃描操作：

(1)對特征值L進行垂直掃描，經掃描后特征值L須滿足

PLi-1≤PLi≥PLi+1

(4)

經過垂直掃描后獲得的峰值集合中可能存在彼此非常接近的特征值，即(Li≈Li+1)，易造成圖像的過分割。因此，接下來將對顏色直方圖進行水平掃描，來確定實際的峰值。

(2)將垂直掃描后得到的峰值集合中每個特征值與一定半徑w內的峰值點進行比較，選擇具有較高像素數的特征值L作為實際的峰值點，對于可能的峰值被選擇為實際峰值Lr，必須滿足以下條件

Lr=(PLp≥PLi) ?PLi∈w

(5)

對圖像的HSI顏色空間直方圖進行兩次掃描后，獲得了具有最高峰值且相距較遠的特征值L，將得到的實際峰值數作為分類數K，選擇K個峰值特征值點作為初始中心點。

本文方法對顏色進行量化，構建HSI顏色空間直方圖表示圖像的色彩分布信息，計算復雜度低。峰值點處的顏色特征值在圖像中出現的概率高，相隔一定距離可避免選擇多個相似的特征值，這樣得到的分類數更準確、中心點更能代表圖像中各區域。

3 基于多維特征的相似度計算

K-means算法通過空間距離來計算像素點間的相似度，忽略了彩色圖像像素點包含的其它重要特征，易造成像素點的錯誤分類。因此，本文提出提取圖像像素點的LDP紋理特征，結合像素的顏色特征和空間坐標特征，構建像素點的多維特征向量。使用多維特征向量代替傳統K-means算法中單一空間位置距離計算像素間的相似度，增加了相似性計算的特征條件，可以更準確反映彩色圖像中像素點的分布，從而提高圖像分割的準確性。

3.1 LDP紋理特征提取

首先使用LDP算法提取像素點的紋理特征，LDP[11]是Jabid 等提出的一種局部二進制模式的改進方法，常被用作潛在的特征提取方法。它可以通過比較不同方向上像素的相對邊緣響應值來計算。給定圖像中的中心像素，8個方向邊緣響應值{mi}，i=0, 1,…,7。通常由Krisch掩模Mi在以像素位置為中心的8個不同方向上計算。8個方向的Kirsch模板如圖1所示。

圖1 Kirsch模板

由于不同方向響應值重要性不同，因此選擇k個最突出的方向來生成LDP。top-k個方向響應值bi被設置為1，而其它方向比特值被設置為0。最后，LDP代碼由式(6)、式(7)計算得到，其中mk是k個最重要的方向響應值

(6)

(7)

圖2表示8個方向邊緣響應位置和LDP二進制位位置。通常，k取3。

圖2 8個方向邊緣響應位置和LDP二進制位位置

本文先將圖像分別與8個不同方向的Kirsch模板卷積，得到8個邊緣響應矩陣；再對圖像中的每個像素構造8位二進制LDP描述符，將二進制串轉為十進制作為該像素的LDP特征。

LDP編碼引入了二階方向信息，大大減少了紋理信息的損失。另外，由于只對邊緣響應絕對值排名前n位的方向編碼為1，而梯度排名前n位的方向一般不會因噪聲的影響改變位置[11]。因此LDP編碼可以充分表達像素點的紋理特征，對非均勻光照不敏感。

3.2 多維特征相似度計算

將像素點的LDP紋理特征與顏色、空間坐標共同組成6個維度的特征向量。首先，HSI 顏色模型能很好模擬人的顏色感知，因此H、S、I這3個參數都被添加到特征向量中，用來描述像素點的顏色特征。然后，使用一個維度表示像素點的LDP紋理特征。最后，使用X，Y表示像素點在圖像中的位置信息。因此，每個像素點i的特征向量可以表示為

(8)

其中,i=1,2,…,N，N表示圖像中的像素數，Hi、Si、Ii是像素i的顏色特征，LDPi表示像素i的紋理特征，Xi、Yi表示像素i的空間坐標。

像素點間的相似性距離通過多維特征向量的歐氏距離計算得到，公式如下

(9)

其中,dist(i1,i2)表示像素點i1和i2之間的相似性距離，F(i,m)表示第i個像素的第m個特征。

使用式(9)計算像素點到各個初始中心點的相似性距離，并將其分配給距離最近的中心點，形成K個子集，計算各子集中所有像素點的特征值均值作為新的中心，迭代執行直到中心點不再改變，輸出分割后的圖像。

基于改進K-means的彩色像分割算法流程如圖3所示。

圖3 算法流程

詳細步驟如下：

(1)輸入彩色圖像；

(2)將圖像由RGB顏色空間轉換為HSI顏色空間，對HSI顏色空間進行非均勻量化，構建顏色直方圖;

(3)對直方圖進行垂直、水平掃描得到分類數K與初始中心點{C1,C2,C3,…,CK};

(4)提取像素點的LDP紋理特征，構建多維特征向量Fi;

(5)計算每個像素點與初始中心點間的相似度，并將其歸類為最近的中心點所在的子集;

(6)更新類中心;

(7)迭代執行步驟(5)、步驟(6)直到聚類中心不再發生變化;

(8)輸出圖像分割結果。

上述算法步驟中，考慮了彩色圖像像素點的色彩分布，自適應獲取了合理的分類數和初始中心點。相似度計算時，對像素點進行具有良好視覺紋理特征的LDP編碼，增加了特征約束，更充分表示了像素點的分布特征。另一方面，對顏色進行量化大大降低了數據量，更準確的初始參數和像素點的正確分類也使算法在較少的迭代次數內收斂。因此，本文算法可以大幅提升彩色圖像分割效果，同時將時間復雜度保持在較低的范圍內。

4 實驗結果與分析

本文實驗基于通用windows平臺，使用Matlab對算法進行編程。計算機硬件環境為CPU (Intel@CoreTM i7． 3770 CPU@3.40 GHz)，顯卡(AMD Radeon HD 7470)。實驗用到的彩色圖像與基準圖像均來自Berkeley圖像分割庫[12]，每個圖像的大小為481*321。

為了驗證本文算法的有效性，將文獻[6]算法、文獻[7]算法、不引入多維特征計算相似度的本文方法與本文算法進行對比。在該實驗中，文獻[6]算法進行分割時聚類數K需要用戶輸入，實驗直接取為基準值，算法所需其它參數選取最優值。3張圖片分別命名為House、Swan和Flower，各算法分割結果如圖4～圖6所示。

圖像House中各個部分之間有明顯顏色差異，由圖4可以看出文獻[6]算法、文獻[7]算法、不引入多維特征的本文算法和本文算法均將建筑與背景天空分離。但如圖4中方框部分所示，其它算法分割結果存在線條不連續的缺陷，文獻[7]算法受光照的影響較大，將建筑的屋頂部分錯分為了兩部分。而本文算法克服光照不均勻現象，成功將建筑主體、屋頂和天空分為3類，且線條連續完整。

圖4 House分割結果對比

圖5 Swan分割結果對比

圖6 Flower分割結果對比

圖像Swan中天鵝、影子、水面的顏色較為接近，增大了圖像分割的難度。如圖5所示，文獻[7]算法將部分影子和水面錯分為同一類，文獻[6]和不引入多維特征的本文算法均未將天鵝的頭部完整分割出來。本文算法分割得到的天鵝頭部輪廓完整，很好的將天鵝與水面分離。

圖像Flower中背景較為復雜。如圖6所示，文獻[6]算法只將花朵的主體外輪廓分割出來，對于細節部分分割的不夠精細。文獻[7]算法和不引入多維特征的本文算法的分割結果產生的碎片區域較多。本文算法將圖像中的花朵花瓣和背景中的葉子部分有效分割，更接近基準分割結果，得到了較好的直觀分割效果。因此，無論對顏色差異大或小的圖像還是復雜圖像，本文算法都可以得到較優的分割結果。

另外，為了客觀評價各算法的分割效果，采用 MSE(mean square error)指標、PSNR(peak to signal noise ratio)[13]指標對各算法分割結果與基準結果之間的相似性進行定量分析。PSNR可通過式(10)計算，范圍在[0,1)之間，越大越好。MSE使用式(11)計算，范圍在[0,1]之間，越低越好

(10)

(11)

其中，S為255。M和N分別是輸入圖像中的行、列數。GI和SI是原始圖像和分割后圖像。

表1是文獻[6]算法、文獻[7]算法、不引入多維特征的本文方法與本文算法在House、Flower、Swan這3張圖片上分割結果的MSE值、PSNR值比較。可以看出，本文算法在每張圖像的結果評估中都獲得了最優的客觀指標值，表明本文分割結果更接近基準分割，與上文主觀分析結果一致。

表1 各算法分割結果的MSE值、PSNR值比較

圖7對各算法的運行時間做了對比。文獻[6]算法迭代計算圖像內所有的像素點，耗時最長。文獻[7]算法采用直方圖閾值法，在分割時間上與文獻[6]算法相比用時較短。未引入多維特征計算相似度的本文算法通過顏色量化降低了計算復雜度，分割耗時遠遠小于其它兩種算法。增加特征維度后計算復雜度增加，但合理的初始參數和像素點的正確分類使算法在較少的迭代次數內收斂，所以本文算法最終運行時間與文獻[7]算法運行時間相當，短于文獻[6]算法運行時間。

圖7 各算法運行時間對比

5 結束語

針對k-means算法進行圖像分割時依賴用戶輸入初始參數與分割效果不理想的問題，本文提出了一種基于改進K-means的彩色圖像分割算法。首先通過圖像HSI顏色空間自適應獲得K-means算法準確的初始參數來表示圖像各部分，減少對用戶輸入參數的依賴。然后提出構建多維特征向量計算像素間的相似度，降低了像素點的錯分類率，使算法在較少的迭代次數內收斂，保證較高圖像分割質量的同時保持較低的時間復雜度。

但是，本文算法仍存在不足之處，如在計算相似度時，多維特征計算使算法復雜度增加，導致算法運行時間較長，進一步提高算法效率是未來的研究方向。