基于改進(jìn)K均值的圖像分割算法

蔣大宇

(哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001)

圖像分割技術(shù)在圖像工程中占有重要的地位，是處于圖像分析和圖像處理之間的重要步驟，也為后續(xù)的處理奠定基礎(chǔ).圖像分割是指依據(jù)灰度、彩色、空間紋理、幾何形狀等特征把圖像劃分成若干個(gè)互不相交的區(qū)域，使得這些特征在同一個(gè)區(qū)域內(nèi)，表現(xiàn)出一致性或相似性，而在不同的區(qū)域間表現(xiàn)出明顯的不同［1］.多年來(lái)經(jīng)過(guò)諸多學(xué)者的不懈努力，已經(jīng)提出上千種的圖像分割算法，并且每年還不斷有新的算法產(chǎn)生，盡管已經(jīng)提出了很多用于圖像分割和特征提取的方法，但由于圖像的種類繁多和復(fù)雜多樣性，設(shè)計(jì)一種通用和有效的分割算法仍然具有重要的意義.目前圖像分割方法主要有:閾值法、區(qū)域提取法、聚類法和邊緣檢測(cè)法四類［2］.

在聚類法的圖像分割中，K均值算法的應(yīng)用的最為廣泛，因其算法具有很好的伸縮性，可以處理大像素的圖像，然而缺點(diǎn)也十分突出，聚類結(jié)果受初值的影響而變得不穩(wěn)定［3］.為了讓KM獲得穩(wěn)定的聚類，學(xué)者們提出了許多改進(jìn)方案，其中以高質(zhì)量的層次聚類算法為K均值提供初值是最受認(rèn)可的策略，可是高質(zhì)量的層次聚類往往是因?yàn)檩^高的計(jì)算復(fù)雜度而使得改進(jìn)的K均值失去了伸縮性，不再適合處理規(guī)模稍大的數(shù)據(jù)［4］.本文設(shè)計(jì)了一個(gè)新的KM改進(jìn)方案——并行二分K－Means(Parallel Bisecting K－Means，PBKM)，該方法既可以保留K均值的伸縮性，又能大幅提高KM的算法效率.

1 并行二分K均值

1.1 并行二分思想

首先將數(shù)據(jù)集一分為二得到兩個(gè)簇，然后以每個(gè)簇為起點(diǎn)再一分為二，如此重復(fù)，第r次獲得2r個(gè)簇.這個(gè)切分過(guò)程與細(xì)胞在分裂過(guò)程中的增長(zhǎng)速度一樣，最底層的數(shù)據(jù)稱之為葉子節(jié)點(diǎn).細(xì)胞分裂式的二分給予每個(gè)簇均等的切分機(jī)會(huì)，在每次迭代過(guò)程都要對(duì)所有的簇進(jìn)行切分，這個(gè)過(guò)程具有并行的特點(diǎn).PBKM采用二分思想對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，其過(guò)程在于每次迭代需要更新待切分簇的數(shù)量和大小，算法描述如下:

1)輸入待聚類數(shù)據(jù)集，并初始化n、k;

2)計(jì)算迭代的次數(shù)R=［lg k/lg2］+1;

3)for r=1 to R

計(jì)算并更新待切分簇的數(shù)量M=2r－1;

計(jì)算并更新待切分簇的大小nd=n/2r－1;form=1toM

調(diào)用K-means(nd，2)對(duì)簇進(jìn)行二分;

4)計(jì)算葉子結(jié)點(diǎn)數(shù)量M=2R;

5)把M個(gè)葉子結(jié)點(diǎn)合并到k個(gè);

6)輸出數(shù)據(jù)對(duì)象的類別標(biāo)簽.

雖然PBKM算法在聚類過(guò)程中調(diào)用了KM算法，但整個(gè)過(guò)程仍然簡(jiǎn)潔明了，容易程序?qū)崿F(xiàn).

1.2 PBKM的時(shí)間復(fù)雜度分析

PBKM第r次切分給出 m個(gè)簇，m=2r，令2R－1≤ k≤2R，R為迭代的次數(shù).通常完全二叉樹的葉子結(jié)點(diǎn)數(shù)m ＞k，此時(shí)需要將葉子結(jié)點(diǎn)進(jìn)行部分合并，是葉子節(jié)點(diǎn)數(shù)降到k即可完成聚類.

對(duì)于PBKM的時(shí)間復(fù)雜度分析需要考慮二分的迭代計(jì)算和葉子結(jié)點(diǎn)合并等兩個(gè)過(guò)程的時(shí)間開銷.

第r次的并行切分，需要切分m個(gè)簇，此時(shí)待切分簇的大小為nd，時(shí)間開銷為:

因?yàn)槎謺r(shí)m=2r－1，nd= n/2r－1，k'=2，有:

執(zhí)行R次迭代的時(shí)間為:

當(dāng)k＜nd時(shí)，需要將葉子結(jié)點(diǎn)部分合并，所以PBKM算法的總體時(shí)間開銷為:

nd=2R，nd比k略大，需要合并的葉子結(jié)點(diǎn)并不多，因此合并的時(shí)間開銷T(nd)也不大.當(dāng)n很大時(shí)，例如對(duì)大規(guī)模數(shù)據(jù)進(jìn)行聚類，T(nd)可以忽略不計(jì).

因?yàn)樾枰喜⒌娜~子結(jié)點(diǎn)不多，也就是nd和k差別不大，此時(shí)合并的時(shí)間復(fù)雜度接近于 O(nd2).當(dāng)2×R×n?nd2，有:

也就是說(shuō)，n?2R/(2×R)時(shí)，葉子結(jié)點(diǎn)合并的時(shí)間相對(duì)很少，可以忽略T(nd).式(6)給出的條件是十分寬松的，通常規(guī)模的數(shù)據(jù)集都可以滿足因此可以說(shuō)PBKM算法中的葉子結(jié)點(diǎn)合并不會(huì)顯著增加整個(gè)聚類過(guò)程的時(shí)間開銷.R的計(jì)算如下:

2 基于PBKM的圖像分割算法

在描述像素點(diǎn)的時(shí)候我們希望盡可能的不丟失像素信息，這里把每一個(gè)像素點(diǎn)分別用其在RGB和HIS顏色空間上進(jìn)行描述，為了更全面的描述像素的特征，在對(duì)像素特性進(jìn)行描述時(shí)還加入了灰度值.這樣每一個(gè)像素點(diǎn)就擁有了7個(gè)屬性，我們就用這7維的行向量來(lái)代表該像素點(diǎn).

對(duì)于一個(gè)像素為256×256的小圖片，其像素點(diǎn)已達(dá)到216，按照提出的預(yù)處理方法，實(shí)際聚類的數(shù)據(jù)規(guī)模達(dá)到了216×7.這樣看來(lái)圖像的像素?cái)?shù)據(jù)對(duì)于聚類問(wèn)題來(lái)說(shuō)屬于大規(guī)模的數(shù)據(jù)集.

用聚類的法進(jìn)行圖像分割，首先將圖像中的像素點(diǎn)用一個(gè)多維的向量表示，也就是將每個(gè)像素點(diǎn)映射到多維的特征空間中，然后根據(jù)這些像素點(diǎn)在特征空間的聚集情況對(duì)特征空間進(jìn)行聚類，達(dá)到分割的目的，再把多維特征空間中的分割結(jié)果映射回原圖像空間，進(jìn)而得到原圖像的分割結(jié)果.

基于PBKM的圖像分割的過(guò)程如下:

1)對(duì)于原始的圖像I0進(jìn)行預(yù)處理，I0含有m×n個(gè)像素點(diǎn)，經(jīng)預(yù)處理后變成了待聚類的數(shù)據(jù)I1，I1的數(shù)據(jù)規(guī)模達(dá)到了m×n×7;

2)對(duì)待聚類數(shù)據(jù)I1進(jìn)行PBKM聚類，得到一組聚類標(biāo)簽 Idex［m×n，1］

3)將得到的聚類標(biāo)簽Idex，還原回原圖像大小m×n;

4)對(duì)還原的圖像進(jìn)行邊緣檢測(cè)得到圖像分割的輪廓，從而實(shí)現(xiàn)圖像分割.

需要指出的是在第3步結(jié)束后，根據(jù)實(shí)際問(wèn)題的需要可以添加一些后續(xù)的優(yōu)化處理，例如開、閉運(yùn)算、膨脹、腐蝕等，然后在進(jìn)行邊緣檢測(cè)，可以得到更好的分割結(jié)果.

3 對(duì)比試驗(yàn)與結(jié)果分析

3.1 試驗(yàn)設(shè)計(jì)與數(shù)據(jù)源

本文以自然彩色圖像作為試驗(yàn)的對(duì)象來(lái)研究圖像分割.試驗(yàn)的硬件環(huán)境為:CPU Core 2 Quad Q6600 2.4G，Internal memory 4G，Hard disk Hitachi HDP 725050GLA360 500G.軟件環(huán)境為:Windows 2003+Matlab2007b.本文在上述環(huán)境中實(shí)現(xiàn)了實(shí)驗(yàn)算法和實(shí)驗(yàn)驗(yàn)證工作.測(cè)試圖全部取自Berkeley圖像分割庫(kù)［5－6］.為了對(duì)本文圖像分割算法的性能進(jìn)行評(píng)測(cè)，本文進(jìn)行了兩組實(shí)驗(yàn)，對(duì)PBKM算法的有效性和高效性進(jìn)行了驗(yàn)證.

3.2 算法的有效性驗(yàn)證

為了驗(yàn)證PBKM算法在圖像分割領(lǐng)域的有效性，本文將基于PBKM圖像分割算法的分割結(jié)果和人工分割結(jié)果進(jìn)行了比對(duì)，為了更直觀的看到分割過(guò)程及效果，在圖1中列出了原始圖像、基于PBKM方法的聚類結(jié)果、邊緣檢測(cè)得到的輪廓還有人工分割的結(jié)果.

其中第一行的三幅圖像是在Berkeley分割庫(kù)中隨機(jī)抽取的大小為481×321的原始圖像;第二行為原始圖像經(jīng)過(guò)PBKM聚類算法得到的聚類標(biāo)簽，通過(guò)灰度的方式顯示的分割結(jié)果;第三行是圖像聚類結(jié)果經(jīng)邊緣檢測(cè)得到的分割輪廓;第四行是人工分割得到的輪廓，是檢驗(yàn)分割算法好壞的一個(gè)重要參考指標(biāo).

從圖1中三幅圖像的分割情況對(duì)比可以看出:1)PBKM算法的分割結(jié)果和人工分割的結(jié)果具有較強(qiáng)的相似性，說(shuō)明了PBKM算法對(duì)于圖像的分割結(jié)果和人的主觀視覺感知具有較強(qiáng)的一致性;2)三幅圖在圖像主體的分割上與人工分割幾乎完全吻合，第1幅圖中房子的輪廓、棱角、門窗、屋頂?shù)氖旨?，第二幅圖中鳥的輪廓、樹枝的形狀，第三幅圖中兩只鳥的輪廓等都得到了較好的分割，這說(shuō)明PBKM方法用于圖像分割能較好的識(shí)別圖像中的主體，能滿足圖像后續(xù)處理的要求(圖像理解、圖像識(shí)別等).3)在圖像的細(xì)節(jié)部分的分割中，該算法得到的輪廓和人工分割得到的輪廓有一定的出入.例如在第一幅圖圓頂屋旁邊的電線，在人工分割中體現(xiàn)出來(lái)了，但本文方法沒有進(jìn)行分割;第2幅圖，在分割時(shí)對(duì)鳥的胸部和腳進(jìn)行了分割，而人工分割只分割鳥的輪廓，不對(duì)細(xì)節(jié)進(jìn)行分割;在第3幅圖中，本文算法在大鳥的尾部進(jìn)行的分割和人工分割有出入.這些差異的存在恰好體現(xiàn)了圖像分割的難度所在.人工分割只是作為檢驗(yàn)圖像分割算法的一個(gè)參考并不是標(biāo)準(zhǔn)答案，其中人的主觀因素占很大部分.總體上來(lái)講PBKM算法的分割結(jié)果和多數(shù)人的視覺感知想吻合，證明了PBKM的有效性.

圖1 三幅真實(shí)圖像的分割結(jié)果人工分割的對(duì)比

3.3 對(duì)比試驗(yàn)

為了對(duì)PBKM算法用于圖像分割的性能、分割效率給出評(píng)價(jià)，將PBKM算法和K－均值算法進(jìn)行了對(duì)比，PBKM算法和K－均值都能處理大規(guī)模的數(shù)據(jù)，我們?cè)趫D像庫(kù)中找到了一個(gè)1 024×768像素的圖像，對(duì)圖像進(jìn)行對(duì)比試驗(yàn)得到的分割結(jié)果如圖2所示，兩種方法的運(yùn)行時(shí)間由表1給出.

圖2 兩種算法分割的輪廓對(duì)比圖

表1 兩種分割算法的運(yùn)行時(shí)間對(duì)比

從圖2中可以看出兩種方法在大像素的圖像上都可以應(yīng)用，充分說(shuō)明了兩種方法都適合處理大規(guī)模的數(shù)據(jù)集，從圖2中可以看出兩種方法對(duì)于原圖的分割幾乎一樣，無(wú)論是云的形狀、雨傘、照相的人還是山的形狀.并且兩種方法對(duì)于圖像細(xì)節(jié)處的分割進(jìn)行的很好，從(B)、(C)中可以看出雨傘的形狀、照相人的輪廓、幾乎連山的大概形狀都分割出來(lái)了，最難能可貴的是就連雨傘上面的小頭都能分割出來(lái)，說(shuō)明了兩種方法都可以應(yīng)用在大像素的圖像分割上.

從表1中能直觀的發(fā)現(xiàn)，我們的方法PBKM在分割質(zhì)量上和K均值幾乎一樣，但是所消耗的時(shí)間只占K均值方法的64%左右，這樣的結(jié)果充分的體現(xiàn)出了PBKM算法在處理大規(guī)模像素圖像分割時(shí)的優(yōu)勢(shì).

4 結(jié) 語(yǔ)

本文針對(duì)K均值方法在圖像分割中的不足，提出了一種基于改進(jìn)K均值算法的PBKM算法，通過(guò)實(shí)驗(yàn)證實(shí)PBKM算法在圖像分割領(lǐng)域具有很強(qiáng)的應(yīng)用性，特別是對(duì)大規(guī)模像素圖像的分割，能得到很好的結(jié)果，并且耗時(shí)較少.

［1］CHENG H D，JIANGX H，SUNH，etal.Color image segmentation;advances and prospects［J］.Pattern Recognition，2001，34(12):2259－2281.

［2］何 俊，葛 紅，王玉峰.圖像分割算法研究綜述［J］.計(jì)算機(jī)工程與科學(xué)，2009，31(12):58－61.

［3］TAN P N，STEINBACH M，KUMAR V.Introduction to Data Mining［M］.北京:機(jī)械工業(yè)出版社，2010:492－495.

［4］CUTTING D R，PEDERSEN JO，KARGER D，etal.Scatter/Gather:A Cluster－based Approach to Browsing Large Document Collections［C］//Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，［S.l.］:［s.n.］，1992:318 －329.

［5］MARTIN D，F(xiàn)OWLKESC，TAL D，etal.A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics［C］//Proceeding of the International Conference on Computer Vision，Los Alamitos，California:IEEE Society Press，2001，416 －423.

［6］肖 剛.基于小波域軟閾值的指紋分割方法研究［J］.哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2012，28(2):231－234.