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

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

0 引 言

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

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

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

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

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

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

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

(1)

聚類中心的更新方法

(2)

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

(3)

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

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

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

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

(4)更新類中心；

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

(6)返回分割結果。

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

2 自適應K-means初始參數(shù)計算

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

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

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

PLi-1≤PLi≥PLi+1

(4)

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

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

Lr=(PLp≥PLi) ?PLi∈w

(5)

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

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

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

K-means算法通過空間距離來計算像素點間的相似度，忽略了彩色圖像像素點包含的其它重要特征，易造成像素點的錯誤分類。因此，本文提出提取圖像像素點的LDP紋理特征，結合像素的顏色特征和空間坐標特征，構建像素點的多維特征向量。使用多維特征向量代替?zhèn)鹘y(tǒng)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個參數(shù)都被添加到特征向量中，用來描述像素點的顏色特征。然后，使用一個維度表示像素點的LDP紋理特征。最后，使用X，Y表示像素點在圖像中的位置信息。因此，每個像素點i的特征向量可以表示為

(8)

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

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

(9)

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

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

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

圖3 算法流程

詳細步驟如下：

(1)輸入彩色圖像；

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

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

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

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

(6)更新類中心;

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

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

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

4 實驗結果與分析

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

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

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

圖4 House分割結果對比

圖5 Swan分割結果對比

圖6 Flower分割結果對比

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

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

另外，為了客觀評價各算法的分割效果，采用 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分別是輸入圖像中的行、列數(shù)。GI和SI是原始圖像和分割后圖像。

表1是文獻[6]算法、文獻[7]算法、不引入多維特征的本文方法與本文算法在House、Flower、Swan這3張圖片上分割結果的MSE值、PSNR值比較?？梢钥闯觯疚乃惴ㄔ诿繌垐D像的結果評估中都獲得了最優(yōu)的客觀指標值，表明本文分割結果更接近基準分割，與上文主觀分析結果一致。

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

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

圖7 各算法運行時間對比

5 結束語

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

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