基于改進(jìn)K-means的彩色圖像分割算法

郭云云，高保祿，趙子潤(rùn)，杜 德，田 力

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

0 引 言

在圖像的研究與應(yīng)用中，往往只關(guān)注圖像的某部分，如醫(yī)學(xué)領(lǐng)域?qū)D像病變區(qū)域進(jìn)行檢測(cè)等，都需通過圖像分割把目標(biāo)從整體圖像中分離[1]。圖像分割的效果直接決定后續(xù)圖像分析和處理的結(jié)果，而現(xiàn)有彩色圖像分割算法存在耗時(shí)長(zhǎng)和分割效果不理想等問題[2]。因此，提出一種高精度和高效率的彩色圖像分割方法是十分必要的。

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

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

1 K-means算法及其在圖像分割中的應(yīng)用

K-means算法[8]通過預(yù)設(shè)分類數(shù)K和隨機(jī)選取的初始中心點(diǎn)，不斷迭代劃分樣本、計(jì)算聚類中心，使目標(biāo)函數(shù)的值最優(yōu)，即E值最小。K-means算法進(jìn)行圖像分割是根據(jù)像素點(diǎn)的特征對(duì)其進(jìn)行聚類。

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

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

(1)

聚類中心的更新方法

(2)

目標(biāo)函數(shù)E定義為

(3)

其中，nj和Xj分別表示以Ci為中心點(diǎn)的子集中樣本點(diǎn)的個(gè)數(shù)、以Ci為中心的子集中的樣本點(diǎn)。利用K-means算法進(jìn)行圖像分割的具體步驟如下：

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

(2)隨機(jī)選取K個(gè)初始中心點(diǎn)；

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

(4)更新類中心；

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

(6)返回分割結(jié)果。

可見，K-means算法進(jìn)行圖像分割存在的問題主要在于難以預(yù)先設(shè)定合適的分類數(shù)K和隨機(jī)選取初始中心點(diǎn)造成聚類結(jié)果不穩(wěn)定。另外，使用單一的空間距離特征計(jì)算像素間的相似度可能使像素點(diǎn)錯(cuò)分類，從而導(dǎo)致圖像分割結(jié)果不理想。

2 自適應(yīng)K-means初始參數(shù)計(jì)算

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

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

(1)對(duì)特征值L進(jìn)行垂直掃描，經(jīng)掃描后特征值L須滿足

PLi-1≤PLi≥PLi+1

(4)

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

(2)將垂直掃描后得到的峰值集合中每個(gè)特征值與一定半徑w內(nèi)的峰值點(diǎn)進(jìn)行比較，選擇具有較高像素?cái)?shù)的特征值L作為實(shí)際的峰值點(diǎn)，對(duì)于可能的峰值被選擇為實(shí)際峰值Lr，必須滿足以下條件

Lr=(PLp≥PLi) ?PLi∈w

(5)

對(duì)圖像的HSI顏色空間直方圖進(jìn)行兩次掃描后，獲得了具有最高峰值且相距較遠(yuǎn)的特征值L，將得到的實(shí)際峰值數(shù)作為分類數(shù)K，選擇K個(gè)峰值特征值點(diǎn)作為初始中心點(diǎn)。

本文方法對(duì)顏色進(jìn)行量化，構(gòu)建HSI顏色空間直方圖表示圖像的色彩分布信息，計(jì)算復(fù)雜度低。峰值點(diǎn)處的顏色特征值在圖像中出現(xiàn)的概率高，相隔一定距離可避免選擇多個(gè)相似的特征值，這樣得到的分類數(shù)更準(zhǔn)確、中心點(diǎn)更能代表圖像中各區(qū)域。

3 基于多維特征的相似度計(jì)算

K-means算法通過空間距離來計(jì)算像素點(diǎn)間的相似度，忽略了彩色圖像像素點(diǎn)包含的其它重要特征，易造成像素點(diǎn)的錯(cuò)誤分類。因此，本文提出提取圖像像素點(diǎn)的LDP紋理特征，結(jié)合像素的顏色特征和空間坐標(biāo)特征，構(gòu)建像素點(diǎn)的多維特征向量。使用多維特征向量代替?zhèn)鹘y(tǒng)K-means算法中單一空間位置距離計(jì)算像素間的相似度，增加了相似性計(jì)算的特征條件，可以更準(zhǔn)確反映彩色圖像中像素點(diǎn)的分布，從而提高圖像分割的準(zhǔn)確性。

3.1 LDP紋理特征提取

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

圖1 Kirsch模板

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

(6)

(7)

圖2表示8個(gè)方向邊緣響應(yīng)位置和LDP二進(jìn)制位位置。通常，k取3。

圖2 8個(gè)方向邊緣響應(yīng)位置和LDP二進(jìn)制位位置

本文先將圖像分別與8個(gè)不同方向的Kirsch模板卷積，得到8個(gè)邊緣響應(yīng)矩陣；再對(duì)圖像中的每個(gè)像素構(gòu)造8位二進(jìn)制LDP描述符，將二進(jìn)制串轉(zhuǎn)為十進(jìn)制作為該像素的LDP特征。

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

3.2 多維特征相似度計(jì)算

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

(8)

其中,i=1,2,…,N，N表示圖像中的像素?cái)?shù)，Hi、Si、Ii是像素i的顏色特征，LDPi表示像素i的紋理特征，Xi、Yi表示像素i的空間坐標(biāo)。

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

(9)

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

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

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

圖3 算法流程

詳細(xì)步驟如下：

(1)輸入彩色圖像；

(2)將圖像由RGB顏色空間轉(zhuǎn)換為HSI顏色空間，對(duì)HSI顏色空間進(jìn)行非均勻量化，構(gòu)建顏色直方圖;

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

(4)提取像素點(diǎn)的LDP紋理特征，構(gòu)建多維特征向量Fi;

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

(6)更新類中心;

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)基于通用windows平臺(tái)，使用Matlab對(duì)算法進(jìn)行編程。計(jì)算機(jī)硬件環(huán)境為CPU (Intel@CoreTM i7． 3770 CPU@3.40 GHz)，顯卡(AMD Radeon HD 7470)。實(shí)驗(yàn)用到的彩色圖像與基準(zhǔn)圖像均來自Berkeley圖像分割庫(kù)[12]，每個(gè)圖像的大小為481*321。

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

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

圖4 House分割結(jié)果對(duì)比

圖5 Swan分割結(jié)果對(duì)比

圖6 Flower分割結(jié)果對(duì)比

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

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

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

(10)

(11)

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

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

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

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

圖7 各算法運(yùn)行時(shí)間對(duì)比

5 結(jié)束語

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

但是，本文算法仍存在不足之處，如在計(jì)算相似度時(shí)，多維特征計(jì)算使算法復(fù)雜度增加，導(dǎo)致算法運(yùn)行時(shí)間較長(zhǎng)，進(jìn)一步提高算法效率是未來的研究方向。