基于改進的GSA彩色圖像分割方法研究

張 辭，馬 麗

(中國地質大學(武漢)機械與電子信息學院，湖北武漢430074)

基于改進的GSA彩色圖像分割方法研究

張 辭，馬 麗

(中國地質大學(武漢)機械與電子信息學院，湖北武漢430074)

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

萬有引力搜索算法;無監督;圖像分割;區域生長

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

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

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

1 萬有引力搜索算法

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

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

圖1 兩個物體之間的萬有引力

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

假設在一個D維搜索空間中存在N個質點。定義第i個質點的位置為

在某時刻t，定義第j個質點對第i個質點的作用力大小為

式中:Maj(t)表示質點j的慣性質量;Mpi(t)表示質點i的慣性質量;ε為一個很小的常量;G(t)表示t時刻的萬有引力常數，隨著時間的增加而不斷減小。具體關系式為

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

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

式中:randj是0～1的隨機數。

由牛頓第二定律可得

式中:Mi(t)表示第i個質點的慣性質量。

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

式中:randi是0～1的隨機數。

質點的慣性質量是根據其適應值的大小來計算的，在GSA中使用以下公式更新質點的慣性質量

式中:fiti(t)表示在t時刻第i個質點的適應值;best(t)和worst(t)分別表示最佳和最差的適應值。在求解最小值問題時，best(t)和worst(t)定義為

2 基于改進的GSA彩色圖像分割方法

基于改進的GSA無監督彩色圖像分割方法主要有移動、合并和分離三個過程。在達到最大迭代次數之前，首先像素點在萬有引力的作用下，在屬性空間中移動，搜索相同性質的像素點。然后在合并過程中，鄰近的區域將被合并成新的區域。最后隨著移動速度的增大，像素點將會以一定概率從聚類中分離出來，再被鄰近的質點吸收。本文算法的總體流程如圖2所示。

圖2 基于改進的GSA彩色圖像分割方法的流程圖

2.1 映射

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

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

2.2 移動

像素點在萬有引力的作用下移動搜尋空間。本文在GSA的基礎上，針對歐氏距離容易忽略不同屬性的差別和屬性之間的關聯問題，采用一種改進的歐氏距離，即根據每個屬性在聚類過程中所起作用的程度不同，給每個屬性賦一個與該屬性相對應的加權系數。在D維空間中，改進后的歐氏距離計算公式為

式中:hp表示每個屬性的加權系數。

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

再計算樣本空間像素的每個屬性的標準差

最后根據GSA搜索算法，像素點i的加速度、速度和位置可表示為

2.3 合并

當質點r和s之間的距離小于預先設定的閾值θ時，這兩個質點將合并成一個新的質點q。顯然在合并過程中，像素點的數量會隨著迭代次數的增加而減少。其位置、質量和速度為

2.4 分離

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

像素點i從聚類k分離的概率為

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

3 實驗結果及分析

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

圖3 原始圖像

除了使用常見的峰值信噪比(Peak Signal-to-Noise Ratio，PSNR)作為評價標準，文獻［8］提出了一個評價函數F，即

圖4 仿真實驗結果

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

基于熵評估函數E=Hr+HI，其包含了預計區域熵與布局熵。

表1為分別采用CM算法、GSA算法和本文方法的分割結果評價比較，可以看出本文方法求得的峰值信噪比略遜色于CM算法和GSA算法，但求得的評價函數F和熵值E均小于其他兩種算法，而且當圖像的結構復雜時，本文方法具有一定優勢。

表1 分割結果評價比較

4 小結

本文提出了一種基于改進的GSA彩色圖像分割方法。該方法在原有GSA的基礎上，優化了歐氏距離，引入了像素分離過程，并給出了像素分離時的最小速率。不僅利用像素的顏色、空間特征，而且參數都是預先設置，從而實現了無監督的圖像分割。實驗結果表明，與傳統CM算法和GSA算法相比，當圖像的結構復雜時，本文方法具有更佳的分割性能。

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

［2］紀則軒，潘瑜，陳強.無監督模糊C均值聚類自然圖像分割算法［J］.中國圖象圖形學報，2011，16(5):773-783.

［3］林麗莉，周文暉.多蟻群動態協作優化的道路圖像分割算法［J］.中國圖象圖形學報，2012，17(4):553-559.

［4］龐冬冬，史健芳.基于改進主動輪廓模型的圖像分割算法［J］.電視技術，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］.北京:科學出版社，2011.

［7］杜隆胤.基于萬有引力定律的分類方法研究［J］.計算機應用與軟件，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，FRITTSJ，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

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

國家自然科學基金項目(61102104)

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

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