張 辭，馬 麗

(中國(guó)地質(zhì)大學(xué)(武漢)機(jī)械與電子信息學(xué)院，湖北武漢430074)

基于改進(jìn)的GSA彩色圖像分割方法研究

張 辭，馬 麗

(中國(guó)地質(zhì)大學(xué)(武漢)機(jī)械與電子信息學(xué)院，湖北武漢430074)

提出了一種基于改進(jìn)的GSA(Gravitational Search Algorithm)無監(jiān)督彩色圖像分割方法。在GSA的基礎(chǔ)上，采用了改進(jìn)的歐氏距離，引入了像素分離過程，并給出了像素分離條件的最小速度。首先像素點(diǎn)的移動(dòng)采用改進(jìn)的歐氏距離進(jìn)行GSA搜索;然后進(jìn)行區(qū)域生長(zhǎng)，合并相同性質(zhì)的像素;最后達(dá)到一定速率的部分像素點(diǎn)從聚類中分離出來。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)C均值聚類算法和GSA算法相比，該方法在復(fù)雜場(chǎng)景圖像中具有更好的分割效果。

萬(wàn)有引力搜索算法;無監(jiān)督;圖像分割;區(qū)域生長(zhǎng)

圖像分割經(jīng)過40多年的研究，仍是圖像處理中的一個(gè)難點(diǎn)問題［1］。其主要目的是把一幅圖像劃分成為若干互不重疊、具有相同性質(zhì)的區(qū)域。目前圖像分割已被廣泛應(yīng)用于圖像檢索、模式識(shí)別和機(jī)器人視覺等方面［2］。

常見的圖像分割方法有:1)基于閾值的方法。例如直方圖閾值法、分水嶺分割等。但是它們計(jì)算量較大，運(yùn)行時(shí)間較長(zhǎng)，有時(shí)存在過分割的情況。2)基于聚類分割的方法。例如C均值聚類(CM)、模糊C均值聚類(FCM)等。受自然現(xiàn)象和生物學(xué)的啟發(fā)，目前啟發(fā)式聚類算法很受歡迎，蟻群聚類算法已應(yīng)用于圖像分割［3］。但當(dāng)數(shù)據(jù)量較大時(shí)，速度較慢。3)基于區(qū)域的方法。例如區(qū)域生長(zhǎng)和區(qū)域分裂合并。雖然容易實(shí)現(xiàn)，但有時(shí)造成局部分割不均勻。4)基于邊緣的方法。常見算子有Roberts、Prewitt和Sobel等，但分割效果一般要受噪聲的影響，并且其自適應(yīng)分割能力不理想［4］。因此關(guān)于圖像分割的新算法研究從未停止。

萬(wàn)有引力搜索算法(Gravitational Search Algorithm，GSA)是2009年由伊朗克曼大學(xué)教授Esmat Rashedi提出的一種啟發(fā)式優(yōu)化算法，是利用物理學(xué)中萬(wàn)有引力和運(yùn)動(dòng)定律進(jìn)行模擬得到的群體智能優(yōu)化算法［5］。將該算法應(yīng)用于圖像分割的研究中，本文提出一種基于改進(jìn)的GSA圖像分割方法，在原有GSA的基礎(chǔ)上，采用了改進(jìn)的歐氏距離，引入了像素分離過程。通過區(qū)域生長(zhǎng)和聚類技術(shù)，利用像素的顏色、空間特征實(shí)現(xiàn)圖像分割，并獲得了較好效果。

1 萬(wàn)有引力搜索算法

萬(wàn)有引力定律是指任意兩個(gè)質(zhì)點(diǎn)通過連心線方向上的力相互吸引［6］。該引力的大小與它們的質(zhì)量乘積成正比，與它們距離的平方成反比，與兩物體的化學(xué)本質(zhì)或物理狀態(tài)以及中介物質(zhì)無關(guān)。其公式可表示為

式中:Fij表示兩個(gè)物體之間的引力;Mi和Mj分別為兩個(gè)物體的質(zhì)量;G是萬(wàn)有引力常量;r表示兩個(gè)物體之間的歐氏距離。圖1表示了兩個(gè)物體之間的萬(wàn)有引力。

圖1 兩個(gè)物體之間的萬(wàn)有引力

GSA是受到萬(wàn)有引力定律及運(yùn)動(dòng)定律的啟發(fā)而提出的。主要有以下3個(gè)特點(diǎn):一是不存在初始質(zhì)點(diǎn)的選取問題;二是初始的樣本分布情況基本不影響最終分類結(jié)果;三是設(shè)定閾值要優(yōu)于設(shè)定類別數(shù)目［7］。該算法中，每個(gè)質(zhì)點(diǎn)都有位置、慣性質(zhì)量、主動(dòng)引力質(zhì)量和被動(dòng)引力質(zhì)量4個(gè)描述特征。隨著時(shí)間的增加，假設(shè)在某一時(shí)刻，所有的質(zhì)點(diǎn)都被質(zhì)量較大的質(zhì)點(diǎn)所吸引，那么此時(shí)質(zhì)點(diǎn)的位置就是搜索空間中的最優(yōu)解。

假設(shè)在一個(gè)D維搜索空間中存在N個(gè)質(zhì)點(diǎn)。定義第i個(gè)質(zhì)點(diǎn)的位置為

在某時(shí)刻t，定義第j個(gè)質(zhì)點(diǎn)對(duì)第i個(gè)質(zhì)點(diǎn)的作用力大小為

式中:Maj(t)表示質(zhì)點(diǎn)j的慣性質(zhì)量;Mpi(t)表示質(zhì)點(diǎn)i的慣性質(zhì)量;ε為一個(gè)很小的常量;G(t)表示t時(shí)刻的萬(wàn)有引力常數(shù)，隨著時(shí)間的增加而不斷減小。具體關(guān)系式為

式中:G0為初始值，通常取100;α取20;T表示最大迭代次數(shù);Rij(t)為i與j之間的歐氏距離，即

在GSA中，假設(shè)t時(shí)刻在第d維上作用在第i個(gè)物體上的總作用力等于其他所有質(zhì)點(diǎn)對(duì)它的作用力之和，其大小Fdi(t)為

式中:randj是0～1的隨機(jī)數(shù)。

由牛頓第二定律可得

式中:Mi(t)表示第i個(gè)質(zhì)點(diǎn)的慣性質(zhì)量。

GSA在每次迭代過程中，可根據(jù)式(8)、式(9)來更新質(zhì)點(diǎn)i的速度和位置，即

式中:randi是0～1的隨機(jī)數(shù)。

質(zhì)點(diǎn)的慣性質(zhì)量是根據(jù)其適應(yīng)值的大小來計(jì)算的，在GSA中使用以下公式更新質(zhì)點(diǎn)的慣性質(zhì)量

式中:fiti(t)表示在t時(shí)刻第i個(gè)質(zhì)點(diǎn)的適應(yīng)值;best(t)和worst(t)分別表示最佳和最差的適應(yīng)值。在求解最小值問題時(shí)，best(t)和worst(t)定義為

2 基于改進(jìn)的GSA彩色圖像分割方法

基于改進(jìn)的GSA無監(jiān)督彩色圖像分割方法主要有移動(dòng)、合并和分離三個(gè)過程。在達(dá)到最大迭代次數(shù)之前，首先像素點(diǎn)在萬(wàn)有引力的作用下，在屬性空間中移動(dòng)，搜索相同性質(zhì)的像素點(diǎn)。然后在合并過程中，鄰近的區(qū)域?qū)⒈缓喜⒊尚碌膮^(qū)域。最后隨著移動(dòng)速度的增大，像素點(diǎn)將會(huì)以一定概率從聚類中分離出來，再被鄰近的質(zhì)點(diǎn)吸收。本文算法的總體流程如圖2所示。

圖2 基于改進(jìn)的GSA彩色圖像分割方法的流程圖

2.1 映射

首先把彩色圖像映射到屬性空間。本文定義了一個(gè)5維的屬性空間。前2個(gè)參數(shù)表示像素點(diǎn)在原始圖像中的位置，后3個(gè)參數(shù)表示RGB值的成分大小。對(duì)于任意一個(gè)像素點(diǎn)i，上述空間可表示為

式中:N為圖像像素總和;x和y代表i的位置;r，g，b是i的彩色成分大小。

2.2 移動(dòng)

像素點(diǎn)在萬(wàn)有引力的作用下移動(dòng)搜尋空間。本文在GSA的基礎(chǔ)上，針對(duì)歐氏距離容易忽略不同屬性的差別和屬性之間的關(guān)聯(lián)問題，采用一種改進(jìn)的歐氏距離，即根據(jù)每個(gè)屬性在聚類過程中所起作用的程度不同，給每個(gè)屬性賦一個(gè)與該屬性相對(duì)應(yīng)的加權(quán)系數(shù)。在D維空間中，改進(jìn)后的歐氏距離計(jì)算公式為

式中:hp表示每個(gè)屬性的加權(quán)系數(shù)。

首先求出樣本空間像素的每個(gè)屬性的均值

再計(jì)算樣本空間像素的每個(gè)屬性的標(biāo)準(zhǔn)差

最后根據(jù)GSA搜索算法，像素點(diǎn)i的加速度、速度和位置可表示為

2.3 合并

當(dāng)質(zhì)點(diǎn)r和s之間的距離小于預(yù)先設(shè)定的閾值θ時(shí)，這兩個(gè)質(zhì)點(diǎn)將合并成一個(gè)新的質(zhì)點(diǎn)q。顯然在合并過程中，像素點(diǎn)的數(shù)量會(huì)隨著迭代次數(shù)的增加而減少。其位置、質(zhì)量和速度為

2.4 分離

合并之后，當(dāng)像素點(diǎn)的速度超過一定速度時(shí)會(huì)以概率Pe從聚類中分離出來，從而成為新的自由質(zhì)點(diǎn)，新的像素點(diǎn)在屬性空間中又會(huì)被最鄰近的聚類吸收。在聚類引力場(chǎng)的作用下，像素點(diǎn)達(dá)到分離條件的最小速度類比第二宇宙速度，即

像素點(diǎn)i從聚類k分離的概率為

假設(shè)像素距離中心距離小于dmin不會(huì)分離，而距離中心距離大于dmax將會(huì)分離。那么Vemax就是像素點(diǎn)距離中心小于閾值dmin的速度，Vemin則是距離中心大于閾值dmax的速度。Vemax和Vemin可表示為

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

實(shí)驗(yàn)在Windows系統(tǒng)環(huán)境下，使用MATLAB-2010b軟件進(jìn)行仿真。測(cè)試圖像采用如圖3所示的Plane，Peppers，Lena和Baboon等4幅圖像，大小均為256×256。實(shí)驗(yàn)分別使用CM算法、GSA算法與本文方法對(duì)上述圖像進(jìn)行了分割，其中設(shè)置參數(shù)初始重力常量G0為10，閾值dmax和dmin分別為80和10，閾值θ為80，仿真實(shí)驗(yàn)結(jié)果如圖4所示。

圖3 原始圖像

除了使用常見的峰值信噪比(Peak Signal-to-Noise Ratio，PSNR)作為評(píng)價(jià)標(biāo)準(zhǔn)，文獻(xiàn)［8］提出了一個(gè)評(píng)價(jià)函數(shù)F，即

圖4 仿真實(shí)驗(yàn)結(jié)果

此外，本文還采用一種基于熵和最小描述原則的定量評(píng)價(jià)函數(shù)E來評(píng)估分割質(zhì)量［9-10］。假設(shè)圖像I分割成C個(gè)任意形狀的不相鄰區(qū)域，SI為圖像I的大小，Lj(i)為區(qū)域j(記作Rj)中的像素?cái)?shù)，在I中的亮度值為i，Vj是Rj中所有可能的亮度值的預(yù)設(shè)值，本文把熵Rj、預(yù)計(jì)區(qū)域熵和圖像布局熵分別用H(Rj)，Hr和HI表示

基于熵評(píng)估函數(shù)E=Hr+HI，其包含了預(yù)計(jì)區(qū)域熵與布局熵。

表1為分別采用CM算法、GSA算法和本文方法的分割結(jié)果評(píng)價(jià)比較，可以看出本文方法求得的峰值信噪比略遜色于CM算法和GSA算法，但求得的評(píng)價(jià)函數(shù)F和熵值E均小于其他兩種算法，而且當(dāng)圖像的結(jié)構(gòu)復(fù)雜時(shí)，本文方法具有一定優(yōu)勢(shì)。

表1 分割結(jié)果評(píng)價(jià)比較

4 小結(jié)

本文提出了一種基于改進(jìn)的GSA彩色圖像分割方法。該方法在原有GSA的基礎(chǔ)上，優(yōu)化了歐氏距離，引入了像素分離過程，并給出了像素分離時(shí)的最小速率。不僅利用像素的顏色、空間特征，而且參數(shù)都是預(yù)先設(shè)置，從而實(shí)現(xiàn)了無監(jiān)督的圖像分割。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)CM算法和GSA算法相比，當(dāng)圖像的結(jié)構(gòu)復(fù)雜時(shí)，本文方法具有更佳的分割性能。

［1］黃洋文，王紅亮.基于量子粒子群優(yōu)化算法的圖像分割方法［J］.電視技術(shù)，2010，34(4):16-18.

［2］紀(jì)則軒，潘瑜，陳強(qiáng).無監(jiān)督模糊C均值聚類自然圖像分割算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2011，16(5):773-783.

［3］林麗莉，周文暉.多蟻群動(dòng)態(tài)協(xié)作優(yōu)化的道路圖像分割算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2012，17(4):553-559.

［4］龐冬冬，史健芳.基于改進(jìn)主動(dòng)輪廓模型的圖像分割算法［J］.電視技術(shù)，2013，37(1):41-44.

［5］RASHEDIE，NEZAMABADI-POUR H，SARYAZDIS.GSA:a gravitational search algorithm［J］.Information Sciences，2009，179(3): 2232-2248.

［6］王永久.引力理論［M］.北京:科學(xué)出版社，2011.

［7］杜隆胤.基于萬(wàn)有引力定律的分類方法研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2013，30(2):205-207.

［8］TAN K，ISA N.Color image segmentation using histogram thresholdingfuzzy C-means hybrid approach［J］.Pattern Recognition，2011，44(1): 1-15.

［9］ZHANGH，F(xiàn)RITTSJ，GOLDMAN S.An entropy-based objective evaluationmethod for image segmentation［C］//Proc.Conference on Storage and Retrieval Methods and Applications for Multimedia.San Jose，CA:［s.n.］，2003:38-49.

［10］YU Z，OSCAR C，ZOU R.An adapt unsupervised approach toward pixel clustering and color image segmentation［J］.Pattern Recognition，2010 (43):1889-1906.

Color Image Segmentation Research Based on Im proved GSA

ZHANG Ci，MA Li
(Faculty of Mechanical and Electronic Information，China University of Geosciences(Wuhan)，Wuhan 430074，China)

An unsupervised color image segmentationmethod based on improved GSA is proposed in this paper.On the basis of GSA，improved euclidean distance is used，separation process of pixels is introduced and theminimum velocity isgiven.Firstly，pixelsmove by GSA using improved euclidean distance.Secondly，every two objects aremerged to a new object via region growing.Finally，some pixels reachingminimum velocity is separated from their corresponding clusterswith a probability.Comparingwith CM and GSA algorithm，the novelmethod shows a better performance especially in complex scene images.

GSA;unsupervised;image segmentation;region growing

TN911.73

A

?? 雯

2013－11－14

【本文獻(xiàn)信息】張辭，馬麗.基于改進(jìn)的GSA彩色圖像分割方法研究［J］.電視技術(shù)，2014，38(13).

國(guó)家自然科學(xué)基金項(xiàng)目(61102104)

張 辭(1988—)，碩士生，主研數(shù)字圖像處理;

馬 麗(1982— )，女，博士，碩士生導(dǎo)師，本文通訊作者，主研圖像處理與分析、模式識(shí)別、計(jì)算機(jī)視覺等。