·信息科學(xué)·

細(xì)菌覓食算法優(yōu)化歸一化準(zhǔn)則的彩色圖像分割

周遜，郭敏，馬苗

(陜西師范大學(xué) 現(xiàn)代教育技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室/計(jì)算機(jī)科學(xué)學(xué)院, 陜西 西安710062)

摘要：為了求解彩色圖像分割問(wèn)題,采用一種基于離散細(xì)菌覓食算法優(yōu)化歸一化準(zhǔn)則的彩色圖像分割方法。引入模糊C均值聚類算法對(duì)圖像預(yù)處理,降低算法維度;同時(shí)用細(xì)菌覓食優(yōu)化算法求解Ncut的最小值,提高了算法的穩(wěn)定性和收斂速度;通過(guò)最優(yōu)個(gè)體菌得到分割結(jié)果。實(shí)驗(yàn)表明,該方法能夠較好地分割圖像,優(yōu)于SM算法和遺傳算法處理問(wèn)題的分割效果,且耗時(shí)少。

關(guān)鍵詞：模糊C均值聚類;歸一化劃分;細(xì)菌覓食優(yōu)化算法;彩色圖像分割

收稿日期：2014-03-11

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(10974130);陜西省青年科技新星基金資助項(xiàng)目(2011kjxx17);陜西師范大學(xué)研究生培養(yǎng)創(chuàng)新基金資助項(xiàng)目(2013CXS045);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目(GK20145007)；陜西省重點(diǎn)科技創(chuàng)新團(tuán)隊(duì)基金資助項(xiàng)目(2014KTC-18)；陜西師范大學(xué)學(xué)習(xí)交叉學(xué)科培育計(jì)劃基金資助項(xiàng)目

作者簡(jiǎn)介：周遜,男,江蘇揚(yáng)州人,從事圖像處理,模式識(shí)別研究。

通訊作者：郭敏，女，江蘇鎮(zhèn)江人，從事信號(hào)處理，模式認(rèn)識(shí)研究。

中圖分類號(hào)：TP391

Color image segmentation based on bacterial foraging

optimization and normalized cut algorithm

ZHOU Xun, GUO Min, MA Miao

(Key Loboratory of Modern Teaching Technology, Ministry of Educational/

School of Computer Science, Shaanxi Normal University, Xi′an 710062， China)

Abstract:In order to solve the problem of color image segmentation, a method based on bacterial foraging optimization and normalized cut algorithm was proposed. In order to solve the problem of premature convergence, introduced fuzzy C-means dealing with color image for reducing the algorithm dimension; meanwhile the bacterial foraging optimization algorithm was introduced to minimize normalized cut, so the stability and convergence speed of algorithm was improved; then segmentation result by the optimal individual bacterium was got. Experimental results show that the method achieves a better segmentation result compared with SM algorithm and genetic algorithm, and consumes less time.

Key words: fuzzy C-means; normalized cut; bacterial foraging optimization algorithm; color image segmentation

圖像分割是利用灰度、顏色、紋理、形狀等信息按照一定標(biāo)準(zhǔn)從圖像中分離出感興趣目標(biāo)的技術(shù)和過(guò)程,是圖像理解、圖像分析、模式識(shí)別等領(lǐng)域中首要解決的關(guān)鍵問(wèn)題之一。近年來(lái)基于圖論的圖像分割[1-3]成為圖像分割算法領(lǐng)域的一個(gè)熱點(diǎn),這類方法將整幅圖像看作一幅無(wú)向帶權(quán)圖,圖像中每一個(gè)像素對(duì)應(yīng)圖中一個(gè)節(jié)點(diǎn),邊上的權(quán)值代表像素的近似關(guān)系,利用最小剪切準(zhǔn)則得到圖像最佳分割。其中Shi和Malik提出的normalized cut準(zhǔn)則[4-5]是一種規(guī)范化的準(zhǔn)則,它綜合考慮分割后子圖的內(nèi)部相似度和子圖之間的相似度,有效避免了出現(xiàn)歪斜分割區(qū)域。

基于圖論的圖像分割以像素點(diǎn)之間的相似度構(gòu)造權(quán)值矩陣,權(quán)值矩陣規(guī)模較大,為減少計(jì)算耗時(shí),文獻(xiàn)[6]建立概貌細(xì)節(jié)灰度級(jí)矩陣模型,相比以像素點(diǎn)之間的相似度建立權(quán)值矩陣規(guī)模較小,但以灰度構(gòu)造矩陣算法維度仍較大。文獻(xiàn)[7]使用K均值聚類將像素的灰度值劃分為K類,對(duì)圖像進(jìn)行了預(yù)處理。文獻(xiàn)[8-9]使用分水嶺算法將圖像劃分為若干區(qū)域,有效降低了算法維度,但當(dāng)前景和背景區(qū)別不大時(shí),容易造成過(guò)分割。

預(yù)處理后的圖像計(jì)算復(fù)雜度降低,但最小化Ncut值仍是NP難問(wèn)題。Shi和Malik將問(wèn)題轉(zhuǎn)化為求解特大矩陣的第二小特征值[5],得到了Ncut值的近似解。文獻(xiàn)[10]引進(jìn)智能優(yōu)化算法優(yōu)化求解Ncut最小值,智能優(yōu)化算法通過(guò)迭代尋優(yōu),能夠較好地分割圖像,但文獻(xiàn)構(gòu)造的仍是像素級(jí)的矩陣,算法非常耗時(shí)。另外,歸一化準(zhǔn)則在灰度圖像的分割中應(yīng)用已經(jīng)很廣泛,但在彩色圖像的分割中仍不常見(jiàn)[11-12]。

本文全面考慮到圖像的局部和全局信息,先對(duì)彩色圖像的R，G，B3個(gè)信道分別作模糊C均值預(yù)處理[13],綜合3個(gè)通道預(yù)處理得到的信息將圖像劃分為n塊最大相似區(qū)域,然后構(gòu)造區(qū)域級(jí)的權(quán)值矩陣,降低了算法的維度,再將Ncut準(zhǔn)則作為適應(yīng)度函數(shù),Ncut值作為適應(yīng)度值,通過(guò)二進(jìn)制離散細(xì)菌覓食算法尋優(yōu)求解Ncut的最小值,將得到的最優(yōu)二進(jìn)制位置映射回原圖對(duì)圖像進(jìn)行分割。

1相關(guān)算法理論

1.1Normalized cut準(zhǔn)則

無(wú)向帶權(quán)圖G=(V,E),節(jié)點(diǎn)集合V對(duì)應(yīng)于圖像中的每個(gè)像素點(diǎn);連接節(jié)點(diǎn)邊的集合為E,每個(gè)邊有權(quán)值ω(i,j),ω(i,j)表示像素i和像素j之間的相似度。通過(guò)刪去某些邊,將圖分為兩個(gè)非連接性點(diǎn)集A，B,使得A∪B=V,A∩B=?,被刪去邊的權(quán)值總和定義為這兩個(gè)部分的不相似度,圖論中稱為割cut,如下公式所示

(1)

其中,ω(i,j)為連接節(jié)點(diǎn)i與節(jié)點(diǎn)j的權(quán)值,表示為

ω(i,j)=

(2)

使公式(1)的值達(dá)到最小值即為最小割,最小割能夠得到最小的分割值,但容易劃分出孤立點(diǎn)。

NormalizedCut克服了這種缺點(diǎn),提出了一種規(guī)范化的分割方法,描述如下

(3)

這里,asso(A,V)表示A中節(jié)點(diǎn)與圖G中所有節(jié)點(diǎn)之間的聯(lián)系程度,同理，asso(B,V)表示B中節(jié)點(diǎn)與圖G中所有節(jié)點(diǎn)之間的聯(lián)系程度?？梢钥闯鯪cut值越小,劃分的結(jié)果越好。

1.2SM算法

Shi和Malik提出的譜聚類算法(SM算法)求解Ncut值,將最小化Ncut值轉(zhuǎn)化為矩陣求解形式[4]

(4)

上面的形式是Rayleigh商數(shù),將y松弛到連續(xù)域[-1,1],求解最小值便轉(zhuǎn)化為求解矩陣的特征方程(D-W)y=λDy。此特征方程的解就是問(wèn)題的實(shí)值解,顯然,最小特征值為零,因此第二小特征值對(duì)應(yīng)的特征向量滿足規(guī)范約束,然后使用閾值將特征向量分為兩部分,作為分割結(jié)果。

1.3遺傳算法

遺傳算法GA(genetic algorithm)是一種自適應(yīng)全局搜索優(yōu)化算法,采用二進(jìn)制編碼,一般通過(guò)選擇、交叉、變異這3種模式來(lái)改變個(gè)體和種群,在許多領(lǐng)域得到了應(yīng)用。

1.4細(xì)菌覓食算法

細(xì)菌覓食算法BFO(bacterial foraging optimization algorithm)是K.M.Passino[14]根據(jù)大腸桿菌的生存覓食原理于2002年提出的一種新型群智能優(yōu)化算法。BFO求解優(yōu)化問(wèn)題的一般步驟為:產(chǎn)生初始解群,計(jì)算適應(yīng)度函數(shù)值,利用菌群趨化、繁殖、遷移3種行為實(shí)現(xiàn)對(duì)優(yōu)化問(wèn)題的求解。

1.4.1趨化行為在細(xì)菌的覓食過(guò)程中,細(xì)菌向營(yíng)養(yǎng)密集的地方聚集的行為,主要分為翻轉(zhuǎn)和游動(dòng)兩種方式。設(shè)個(gè)體菌的當(dāng)前狀態(tài)為Xi,隨機(jī)朝任意方向移動(dòng)一步即翻轉(zhuǎn)一次。若新位置的營(yíng)養(yǎng)度較低則保持Xi狀態(tài)不變;若新位置Xi′所在位置的營(yíng)養(yǎng)度較高,則將Xi更新為Xi′,然后從狀態(tài)Xi′接著翻轉(zhuǎn),直到狀態(tài)Xik′處的營(yíng)養(yǎng)度不再增高或者達(dá)到最大移動(dòng)步數(shù)Step則停止移動(dòng)。趨化方式使得細(xì)菌具有局部搜索能力。

1.4.2繁殖行為將所有個(gè)體菌所在位置的營(yíng)養(yǎng)度排序,營(yíng)養(yǎng)度較低之處的細(xì)菌則移動(dòng)到營(yíng)養(yǎng)度較高的位置,實(shí)現(xiàn)細(xì)菌的繁殖。若個(gè)體菌Xi處的營(yíng)養(yǎng)度較低,它會(huì)向營(yíng)養(yǎng)度較高的Xj移動(dòng)。這一方式體現(xiàn)了自然界優(yōu)勝劣汰的生存規(guī)則,加快了菌群的收斂速度。

1.4.3遷移行為在趨化和繁殖行為之后,每個(gè)個(gè)體菌都有一定概率遷移到搜索空間的任意位置。個(gè)體菌的狀態(tài)Xi有一個(gè)概率Ped使其的狀態(tài)發(fā)生變化,遷移行為使得種群多樣化,防止算法陷入局部最優(yōu)。

2本文算法

基于圖論的圖像分割是二元標(biāo)號(hào)優(yōu)化問(wèn)題,需要將細(xì)菌覓食算法離散化。本文首先對(duì)圖像進(jìn)行FCM預(yù)處理,以得到的n塊最大相似區(qū)域構(gòu)造權(quán)值矩陣,然后用二進(jìn)制離散細(xì)菌覓食算法優(yōu)化求解最佳分割的二進(jìn)制狀態(tài)。

2.1圖像預(yù)處理

真彩色圖像包含豐富的顏色信息,一般認(rèn)為每個(gè)像素由R，G，B 3個(gè)分量組成?？紤]到以像素構(gòu)造的權(quán)值矩陣計(jì)算量大,為減少時(shí)間復(fù)雜度,本文對(duì)彩色圖像的R，G，B 3個(gè)通道分別作模糊C均值聚類,每個(gè)信道分別聚類為具有c個(gè)最大相似區(qū)域的圖像IR，IG，IB,在保證識(shí)別每個(gè)像素的前提下取IR，IG，IB的最大交集,得到具有n塊最大相似區(qū)域的圖像。以n塊最大相似區(qū)域構(gòu)造權(quán)值矩陣,縮小了權(quán)值矩陣規(guī)模,在保證識(shí)別圖像基本信息前提下,降低了歸一化分割算法的求解規(guī)模。

2.2細(xì)菌覓食算法的離散化

基于圖論的圖像分割是二元標(biāo)號(hào)問(wèn)題,因此將細(xì)菌覓食算法離散化后求解最優(yōu)分割是可行的。離散細(xì)菌覓食算法尋優(yōu)便是將預(yù)處理得到的n塊最大相似區(qū)域整合成內(nèi)部相似最大、外部相似最小的兩部分,最大相似區(qū)域的個(gè)數(shù)即為問(wèn)題的維度D。

將細(xì)菌覓食算法離散化,Xi(xi,1,xi,2,…,xi,D)表示第i個(gè)個(gè)體菌在D維空間里的位置,xi,k(k=1,2,…,D)取值為0或1,具體標(biāo)準(zhǔn)化方法如下:

(5)

重新定義細(xì)菌覓食算法的行為操作準(zhǔn)則,在0-1狀態(tài)下進(jìn)行算法的優(yōu)化,至此完成對(duì)細(xì)菌覓食算法的二進(jìn)制離散化。

2.3離散細(xì)菌覓食算法的參數(shù)選取

離散細(xì)菌覓食算法參數(shù)較多,參數(shù)的選取直接影響圖像的分割效果。本文選取細(xì)菌總數(shù)N=20,趨化次數(shù)Nc=5,繁殖次數(shù)Nre=2,遷移次數(shù)Ned=2,其他幾個(gè)重要參數(shù)及離散化定義如下:

1)營(yíng)養(yǎng)度。營(yíng)養(yǎng)度是菌群覓食行為的參考依據(jù)。式(3)即為營(yíng)養(yǎng)度的評(píng)價(jià)標(biāo)準(zhǔn),通過(guò)計(jì)算Ncut值確定細(xì)菌的適應(yīng)度值,從而得到細(xì)菌所在位置的營(yíng)養(yǎng)度,可以看出Ncut越小,指導(dǎo)分割圖像的效果越好。

2)朝任意方向移動(dòng)一步。本文定義朝任意方向移動(dòng)一步為個(gè)體菌的二進(jìn)制狀態(tài)Xi的某一維隨機(jī)變異,0變?yōu)?,1變?yōu)?。

3)最大移動(dòng)步數(shù)。當(dāng)細(xì)菌趨化時(shí)達(dá)到了最大移動(dòng)步數(shù)強(qiáng)制終止本次趨化,本文選擇最大移動(dòng)步數(shù)為Step=7。

4)遷移概率。遷移概率決定了算法全局搜索能力,概率過(guò)大則容易盲目搜索,反之則容易局部收斂,本文選擇遷移概率Ped=0.25。

2.4算法流程

結(jié)合上述分析,離散細(xì)菌覓食算法優(yōu)化歸一化準(zhǔn)則的彩色圖像分割算法流程如圖1所示。

圖1　細(xì)菌覓食算法優(yōu)化歸一化準(zhǔn)則的彩色圖像分割流程圖 Fig.1　Flow process diagram of the color image segmentation based on bacterial foraging optimization and normalized cut algorithm

1)對(duì)彩色圖像的3個(gè)信道通過(guò)模糊C均值聚類分別得到具有C塊最大相似區(qū)域的圖像IR，IG，IB,綜合3個(gè)通道的聚類信息生成n塊最大相似區(qū)域,然后將每個(gè)區(qū)域的像素R，G，B均值作為區(qū)域像素值構(gòu)造權(quán)值函數(shù),構(gòu)造無(wú)向帶權(quán)圖。

2)將Ncut值作為適應(yīng)度函數(shù),利用二進(jìn)制離散細(xì)菌覓食算法對(duì)其進(jìn)行尋優(yōu),通過(guò)個(gè)體菌在覓食行為中不停更新自身得到最優(yōu)營(yíng)養(yǎng)度位置及最優(yōu)個(gè)體菌的二進(jìn)制狀態(tài)。

3)將最優(yōu)個(gè)體菌的二進(jìn)制狀態(tài)映射回原圖,指導(dǎo)劃分圖像,完成對(duì)圖像的分割。

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

實(shí)驗(yàn)平臺(tái)為Microsoft Windows 7 Professional, CPU:Intel Core 2.2 GHz,RAM:2GB.選取大小均為256×256的彩色圖像進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果分別如圖2～圖4所示。

圖2　圖像elephant分割效果圖 Fig.2　Segmentation result of the photo elephant

圖3　圖像pilot分割效果圖 Fig.3　Segmentation result of the photo pilot

圖4　圖像bird分割效果圖 Fig.4　Segmentation result of the photo women

由上述圖像可見(jiàn),當(dāng)圖像中顏色的變化幅度比較大,細(xì)節(jié)較多,顏色信息比較豐富,尤其前景和背景差別不大時(shí),運(yùn)用SM算法和遺傳算法分割效果不理想。例如圖2(b)中,SM算法對(duì)前景的辨別能力不強(qiáng),將較大的大象身體區(qū)域分為背景。圖3(b)中,SM算法將飛機(jī)頂部分割錯(cuò)誤,飛行員的輪廓及影子也未能劃分好。圖3(c)中,遺傳算法將較大區(qū)域劃分錯(cuò)誤。圖4(b)與4(c)中,SM算法和遺傳算法將對(duì)鳥(niǎo)兒和樹(shù)干的輪廓都未能較好的劃分,混入人們感興趣的目標(biāo)之中。而運(yùn)用細(xì)菌覓食算法優(yōu)化之后,上述情況能夠有效地避免。因?yàn)镾M算法求解的特征向量對(duì)應(yīng)一個(gè)分割,細(xì)菌覓食算法每個(gè)個(gè)體菌的二進(jìn)制狀態(tài)都相當(dāng)于一個(gè)特征向量,相對(duì)于遺傳算法,細(xì)菌覓食算法的尋優(yōu)策略要優(yōu)于遺傳算法的,在迭代中過(guò)程中優(yōu)化得到的結(jié)果優(yōu)于SM算法和遺傳算法。

由表1-3還可以看出,傳統(tǒng)Ncut算法與本文算法耗時(shí)區(qū)別不大,都能在較短的時(shí)間內(nèi)分割出圖像,滿足實(shí)時(shí)性需求,這是由于本文對(duì)圖像進(jìn)行了預(yù)處理,降低了問(wèn)題的維度。細(xì)菌覓食算法求解的Ncut值都比傳統(tǒng)Ncut算法要小,說(shuō)明本文算法優(yōu)于傳統(tǒng)Ncut算法,能夠較好地分割彩色圖像。

表1　圖像elephant的分割數(shù)據(jù)

表2　圖像pilot分割數(shù)據(jù)

表3　圖像bird分割數(shù)據(jù)

4結(jié)語(yǔ)

本文基于圖論的圖像分割思想,提出了一種將細(xì)菌覓食優(yōu)化算法與歸一化準(zhǔn)則相結(jié)合的彩色圖像分割方法。該方法利用菌群的覓食行為?在搜索空間中尋找能使Ncut值最小的個(gè)體菌,再將最優(yōu)個(gè)體菌二進(jìn)制狀態(tài)映射回?zé)o向帶權(quán)圖,得到對(duì)圖的最優(yōu)劃分。由于本文預(yù)處理方法考慮的是圖像的局部信息,normalized cut能夠有效地把握全局信息,細(xì)菌覓食算法在求解NP-hard問(wèn)題上是有效且快速的,通過(guò)理論分析和實(shí)驗(yàn)仿真表明,本文提出的方法綜合了細(xì)菌覓食算法和歸一化分割準(zhǔn)則的優(yōu)點(diǎn),能夠快速、有效地指導(dǎo)彩色圖像分割。

參考文獻(xiàn)：

[1]LI X B, TIAN Z. Optimum cut-based clustering[J]. Signal Processing, 2007, 87(11):2491-2505.

[2]ZHANG M, ALHAJJT R. Improving the graph-based image segmentation method[C]//Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence Arlington, Arlinglon:IEEE Press, 2006: 617-624.

[3]廖武忠. 基于圖論理論的圖像分割算法的研究[D]. 重慶:重慶大學(xué),2006.

[4]SHI J B, MALIK J. Normalized cuts and image segmentation[C]//Proc IEEE CS Conf Computer Vision and Pattern Recognition, 1997: 731-737.

[5]SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 2000, 22(8): 888-905.

[6]唐艷亮,吳一全,吳詩(shī)婳,等. 基于NSCT和Tsallis熵的SAR圖像快速分割方法[J]. 信號(hào)處理,2011,27(8):1133-1139.

[7]吳永芳,楊鑫,徐敏,等 基于K均值聚類的圖割醫(yī)學(xué)圖像分割方法[J]. 計(jì)算機(jī)工程,2011,37(5):232-234.

[8]楊靜,陳昭炯. 結(jié)合分水嶺的Mean-Shift 圖像分割新算法[J]. 小型微型計(jì)算機(jī)系統(tǒng). 2009,30(12):2493-2496.

[9]盧志茂,許曉麗,范冬梅,等. 二次分水嶺和Ncut相結(jié)合的彩色圖像分割算法[J]. 華中科技大學(xué)學(xué)報(bào), 2011,39:95-98.

[10]翟艷鵬,郭敏,馬苗, 等. 遺傳算法優(yōu)化歸一化劃分準(zhǔn)則的圖像分割[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010,46(33):148-157.

[11]TAO Win-bing, JIN Hai, ZHANG Yi-min. Color image segmentation based on mean shift and normalized cuts[J]. IEEE Transactions on Systems, and Cybemetics, 2007, 37(5): 1382-1389.

[12]李南希. 基于圖論的彩色圖像分割方法研究[D]. 廣州:華南師范大學(xué),2007.

[13]關(guān)慶,鄧趙紅,王士同. 改進(jìn)的模糊C-均值聚類算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011,47(10):27-29.

[14]PASSION K M. Biomimicry of bacterial foraging for distributed optimization and control[J]. IEEE Control Systems Magazine, 2002, 22(3):52-67.

(編輯曹大剛)