一種改進遺傳退火算法的圖像分割方法

譚定英，陳平平，李學(xué)征，唐 蓉

(廣州中醫(yī)藥大學(xué)醫(yī)學(xué)信息工程學(xué)院，廣東 廣州 510006)

0 引言

圖像分割是圖像分析和模式識別系統(tǒng)的首要問題，它決定圖像的最終分析質(zhì)量和模式識別的判別結(jié)果。所謂圖像分割是按照一定的規(guī)則把圖像劃分成若干個互不相交、具有一定性質(zhì)的區(qū)域，把人們關(guān)注的部分從圖像中提取出來，進一步加以研究分析和處理[1]。研究者們在傳統(tǒng)分割方法的基礎(chǔ)上提出了各種改進方法。金元郁等人將遺傳算法引入二維雙閾值最大類間方差(Otsu)算法中，提高了圖像分割的精度和效率[2]。丁紅軍等人將遺傳算法引入神經(jīng)網(wǎng)絡(luò)算法中，對算法中的參數(shù)采取自適應(yīng)的方法進行設(shè)置，提出了基于遺傳-神經(jīng)網(wǎng)絡(luò)方法的圖像分割方法，取得了一定的效果[3]。葉青等人在深入研究自適應(yīng)遺傳算法的基礎(chǔ)上，通過對變異算子進行改進，很好地避免了算法陷入局部極值，提高了分割效率[4]。朱斌等人通過將模糊C-均值聚類算法和自適應(yīng)的遺傳算法相結(jié)合，有效地提高了算法的分割速度和分割精確性[5]。種勁松等提出了一些評價圖像分割質(zhì)量的標準，并將它們組成適應(yīng)度函數(shù)，利用遺傳算法進行圖像分割閾值的尋優(yōu)選取[6]。李賢陽[7]等利用改進的遺傳算法對二維Otsu圖像分割函數(shù)進行全局優(yōu)化，在保持群體多樣性的同時加快收斂速度，最后得到圖像分割的最佳閾值。李輝[8]提出一種基于改進遺傳算法的圖像分割方法，在算法中采用二維編碼機制，并設(shè)計了一個自適應(yīng)變異算子使改進后的遺傳算法優(yōu)化了圖像的分割，取得較好的算法性能。

從以上關(guān)于圖像分割的各種算法的研究可以看出，以遺傳算法為基礎(chǔ)的圖像分割應(yīng)用在處理時間和效果方面具有很大的優(yōu)勢。將遺傳算法和閾值法結(jié)合，利用各種傳統(tǒng)閾值法或者改進閾值法將不同的圖像分割問題轉(zhuǎn)化為求解最優(yōu)解的數(shù)學(xué)問題，然后將遺傳算法和其它優(yōu)化算法結(jié)合實現(xiàn)優(yōu)勢互補，從而提高算法運行的穩(wěn)定性和收斂速度。本文通過模擬退火思想改進遺傳算法，結(jié)合最大類間方差閾值分割方法實現(xiàn)對目標圖像的分割。通過對比基本遺傳算法和改進的遺傳退火算法在實驗中的分割效果和運行效率，以表明改進算法在圖像分割方面的高效性。

1 相關(guān)技術(shù)

圖像分割[9]是將圖像表示為物理上有意義的連通區(qū)域的集合，根據(jù)目標與背景的先驗知識，對圖像中的目標、背景進行標記、定位，然后將目標從背景或其他偽目標中分離出來。

1.1 基于閾值的分割方法

閾值法[10]一般是通過圖像的灰度直方圖信息獲取用于分割的閾值。根據(jù)圖像的目標和背景在灰度特性上的差異，把圖像看做具有不同灰度級的2類區(qū)域的組合[11]。

閾值分割圖像過程，設(shè)(x，y)是二維數(shù)字圖像的平面坐標，圖像灰度級的取值范圍是G={0，1，2，…，L－1}，坐標(x，y)上的像素點的灰度級表示為f(x，y)，設(shè) t∈G 為分割閾值，B={C0，C1}代表一個二值灰度級，并且 C0，C1∈G0，函數(shù) f(x，y)在閾值 t上的分割結(jié)果可以表示為2類:

閾值分割法是按某個準則函數(shù)求最優(yōu)閾值t的過程。設(shè)灰度級為i的像素點個數(shù)為mi，則圖像的像素點的總數(shù)目M為:

灰度級i的出現(xiàn)概率Pi為:

接著按照最大類間方差法選取最佳閾值，具體方法為:設(shè)f(x，y)為待分割的圖像，圖像的灰度范圍為{0，1，…，L－1}，閾值t將圖像中的像素劃分為2類:C0={0，1，…，t}，C1={t+1，t+2，…，L －1}，C0與 C1分別代表目標與背景。若 f(x，y)≤t，則(x，y)∈C0，若 f(x，y)﹥ t，則(x，y)∈C1。

對圖像的直方圖進行歸一化得到灰度級的概率分布[12]:

其中:ni是灰度為i的像素數(shù);N為圖像的總像素數(shù)，為灰度級出現(xiàn)的概率。

C0與C1類出現(xiàn)的概率分別為:

C0與C1類的均值分別為:

使σ2取最大值時的t就是最佳閾值。

1.2 遺傳退火算法

遺傳算法[13]是以自然選擇和遺傳理論為基礎(chǔ)，將生物過程中適者生存的規(guī)則與群體內(nèi)部的隨機信息交換機制相結(jié)合的搜索算法。遺傳退火算法(GASA)就是將遺傳算法(GA)和模擬退火算法(SA)相結(jié)合而構(gòu)成的一種優(yōu)化算法，是一個雙層并行搜索結(jié)構(gòu)[14]，在逐漸進行降溫操作的各溫度下串行地依次進行GA和SA搜索，其中GA的進化結(jié)果為SA提供了初始解，而SA經(jīng)隨機擾動后的結(jié)果又成為退溫后GA進一步進化的新的初始種群。該混合算法結(jié)合GA的并行搜索和SA的概率突跳性，對搜索行為進行優(yōu)化，提高了全局和局部的搜索能力和執(zhí)行效率。

2 基于改進遺傳退火算法的圖像分割方法

2.1 最大類間方差分割方法

通常用均值和方差來反映圖像像素的分布情況，圖像灰度均值反映了圖像灰度分布的均勻性，方差反映了灰度值的跳變。背景和目標域的內(nèi)部是比較均勻的，但是在邊界上和邊界附近的點的灰度值跳躍性很大，因此可以用方差反映邊界及其附近點灰度值的跳變。用均值和方差共同來反映圖像的均勻性和跳躍性比傳統(tǒng)的Otsu只考慮均值分割出來的效果應(yīng)該更好些。綜合考慮均值和方差來改進Otsu法，對式(9)做改進如下:

其中:

2.2 改進的遺傳退火圖像分割方法

將模擬退火算法與遺傳算法相結(jié)合用于圖像閾值分割，改進思路是:利用模擬退火算法對遺傳算法的適應(yīng)度進行拉伸，在溫度高時，相近適應(yīng)度的個體產(chǎn)生后代的概率相近;而當(dāng)溫度不斷下降后，拉伸的作用更強，放大了適應(yīng)度相近的個體適應(yīng)度差異，從而使得優(yōu)秀個體的優(yōu)勢更明顯。因此利用改進后的式(10)作為算法的適應(yīng)度函數(shù)，在保證圖像分割質(zhì)量的基礎(chǔ)上有效提高分割效率。

算法實現(xiàn)過程如下:

1)初始化控制參數(shù)。初始種群個體大小N，最大進化次數(shù)MAXGEN，交叉概率Pc，變異概率Pm，退火初始溫度T0，溫度冷卻系數(shù)q，終止溫度Tend，鏈長L默認為當(dāng)代種群個體數(shù)目，變量的二進制編碼長度PRECI。

2)隨機初始化圖像分割閾值，并通過函數(shù)創(chuàng)建初始種群Chrom，對每個分割閾值用式(10)計算每個個體的適應(yīng)度 φi，其中 i=1，2，3，…，N。選用改進的Otsu法中的式(10)作為本算法的適應(yīng)度函數(shù)，能在保證圖像分割質(zhì)量的基礎(chǔ)上有效提高分割效率。

遺傳編碼方式，對于具有256級灰度的圖像，其候選閾值在0～255之間，選用一個8位二進制進行編碼，即:00000000～11111111。每個染色體代表一個分割閾值。初始群體的每個個體都是隨機產(chǎn)生的，其相應(yīng)的適應(yīng)度值也有高有低。

3)初始化gen=0，設(shè)循環(huán)計數(shù)條件gen＜MAXGEN＆退火溫度Tr＞Tend。

4)對群體Chrom實施選擇、交叉和變異等遺傳操作，對新產(chǎn)生的個體用式(10)計算適應(yīng)度值φi'。若φi'＜φi，則以新個體替換舊個體，否則，以概率P=exp((φi－φi')/Tr)接受新個體，舍棄舊個體。

5)若 gen＜MAXGEN 且 Tr＞Tend，則 gen=gen+1，執(zhí)行降溫操作Tr+1=qTr，返回下一代種群，轉(zhuǎn)至步驟4);否則，轉(zhuǎn)至步驟6)。

6)利用返回的全局最優(yōu)閾值實現(xiàn)圖像分割。

7)算法結(jié)束。

算法流程如圖1所示。

圖1 基于遺傳退火算法的圖像分割流程圖

3 實驗結(jié)果與分析

3.1 實驗環(huán)境簡介

實驗在 MATLAB 7.11.0(R2010b)上編寫、運行，硬件配置為 Pentium(R)Dual-Corn 2.OO GHz CPU，操作系統(tǒng)為Windows XP。MATLAB具有強大的數(shù)學(xué)運算能力、方便實用的圖像處理功能及語言的高度集成性，其集成的遺傳算法工具箱、模擬退火算法工具箱及圖像分析工具對本文算法的實現(xiàn)和圖像分割算法提供了基礎(chǔ)。

3.2 實驗過程和結(jié)果分析

算法的運行參數(shù)對算法的求解效率和求解結(jié)果至關(guān)重要，但目前尚沒有選擇遺傳算法和模擬退火算法參數(shù)的統(tǒng)一標準，在實際運用中，常常需要經(jīng)過多次實驗后才能合理確定參數(shù)或其范圍?；谖墨I[15-16]提出了相關(guān)參數(shù)選取的經(jīng)驗總結(jié):遺傳算法中一般群體規(guī)模取值為10～100;常用的交叉概率取值可在0.4～0.99之間，取值偏大較為合適;常用的變異概率取值可在0.0001～0.1之間，取值偏小較為合適;遺傳進化代數(shù)一般取為10～500;而模擬退火算法的冷卻溫度表對算法的效率影響也很大，一般初始溫度取值較大，冷卻系數(shù)越大，找到全局最優(yōu)解的機會就越大，相應(yīng)的運行時間也會增加，所以合適的降溫速率選取也是意義重大的。

基于文獻[17]求最優(yōu)分割閾值的方法，結(jié)合之前研究者的實驗經(jīng)驗總結(jié)發(fā)現(xiàn)，種群規(guī)模15，計算遺傳代數(shù)10，交叉概率為0.9，變異概率0.01，初始溫度為100，冷卻系數(shù)為0.8，能得到很好的分割效果，因此在本文實驗中參數(shù)設(shè)置采用經(jīng)驗值。

為了直觀地測試圖像分割算法在“自然圖像”上的效果，在圖像處理領(lǐng)域使用了許多常用的測試圖像。選取標準灰度測試圖像作為分割對象，測試圖集為著名的Lena圖和Cameraman圖。圖像灰度級別統(tǒng)一選為[0，255]范圍。測試中，分別采用傳統(tǒng) Otsu法、Otsu結(jié)合基本遺傳算法和Otsu結(jié)合遺傳退火算法(即是改進后的算法)對不同類型圖像進行了多次實驗，從中選取5個樣本數(shù)據(jù)作分析。

3.2.1 利用Lena標準測試圖像進行分割

利用以上3種算法對Lena標準測試圖像(512×512)進行分割，圖2為原圖像灰度直方圖，它代表圖像中具有某種灰度級的像素的數(shù)目，反映了圖像中某種灰度出現(xiàn)的頻率。Otsu算法以及改進算法的實現(xiàn)主要依賴于圖像灰度直方圖的統(tǒng)計特性。圖3為Lena原圖像及分割結(jié)果。

圖2 Lena標準測試圖像灰度直方圖

圖3 Lena標準測試圖像分割效果對比圖

表1 Lena標準測試圖像分割閾值及運行時間比較

表1顯示，基于基本遺傳算法改進和遺傳退火算法改進的Otsu法的平均分割閾值相近，但與傳統(tǒng)Otsu法存在一定的差距。這差距相應(yīng)體現(xiàn)在分割效果圖上，正如圖3所示，改進的Otsu法分割圖像的背景陰影部分相對傳統(tǒng)Otsu法減少了，目標圖像分割效果更好。從圖4(a)與圖4(b)可以看出，利用基本遺傳算法進行圖像分割可有效減少閾值計算的時間，對于本文的遺傳退火算法在閾值計算時間上與基本遺傳算法相近，但閾值范圍穩(wěn)定在5個像素以內(nèi)，閾值的波動曲線起伏較為平穩(wěn)。另外，與基本遺傳算法相比，在進化代數(shù)相同條件下，遺傳退火算法在保持群體多樣性的同時，收斂速度進一步加快，其穩(wěn)定性也比基本遺傳算法要好。

圖4 基于表1的數(shù)據(jù)分析圖

3.2.2 利用Cameraman標準測試圖像進行分割

利用以上3種算法對Cameraman標準測試圖像(256×256)進行分割，圖5為原圖像灰度直方圖，圖6為原圖像及分割結(jié)果。

圖5 Cameraman標準測試圖像灰度直方圖

圖6 Cameraman標準測試圖像分割效果對比圖

表2 Cameraman標準測試圖像分割閾值及運行時間比較

從表2數(shù)據(jù)顯示，基于遺傳算法改進和遺傳退火算法改進的Otsu法的平均分割閾值相近，但與傳統(tǒng)Otsu法存在的差距較大。這差距相應(yīng)體現(xiàn)在分割效果圖上，正如圖6所示，改進的Otsu法分割圖像的地面上的陰影部分相對傳統(tǒng)Otsu法減少了，目標圖像分割效果更好。從圖7(a)與圖7(b)可以看出，利用基本遺傳算法進行圖像分割可有效減少閾值計算的時間，但Otsu結(jié)合基本遺傳算法閾值最大為80，最小為71，閾值范圍在10個像素之間，閾值的波動曲線起伏幅度大。對于改進的遺傳退火算法在閾值計算時間上與基本遺傳算法相近，而且閾值范圍穩(wěn)定在3個像素以內(nèi)，閾值的波動曲線起伏較為平穩(wěn)。同樣，與基本遺傳算法相比，在進化代數(shù)相同條件下，遺傳退火算法在保持群體多樣性的同時，收斂速度進一步加快，其穩(wěn)定性也較好。

圖7 基于表2的數(shù)據(jù)分析圖

4 結(jié)束語

圖像分割閾值的正確選擇直接影響到優(yōu)化的精度和圖像的分析、理解和識別的正確性。本文在閾值分割算法研究中，在原來基本遺傳算法中融入模擬退火思想，同時結(jié)合最大類間方差方法，實驗表明改進遺傳退火算法的最大類間方差圖像分割方法能很好提高算法的全局搜索能力，避免遺傳算法陷入局部最優(yōu)，并且能更快速、更穩(wěn)定收斂到最佳的分割閾值，得到更好的圖像分割效果。

在圖像分割方法的研究方面，還可以進一步結(jié)合其他智能優(yōu)化方法以提高圖像分割的高效性，針對彩色圖像的分割也是目前研究的熱點和難點，下一步可以繼續(xù)開展基于Otsu閾值彩色圖像分割方法的研究，尋找新的應(yīng)用思路。

[1] 戴天虹.基于計算機視覺的木質(zhì)板材顏色分類方法的研究[D].哈爾濱:東北林業(yè)大學(xué)，2008.

[2] 金元郁，張洪波，馮宇.基于遺傳算法的二維雙閾值Otsu圖像分割算法[J].電子科技，2009，22(11):35-39.

[3] 丁紅軍，蔡鴻杰，邢克禮.遺傳神經(jīng)網(wǎng)絡(luò)在圖像分割中應(yīng)用研究[J].自動化技術(shù)與應(yīng)用，2010，29(3):8-12.

[4] 葉青，洪霞飛.改進遺傳算法在霧天圖像清晰化中的應(yīng)用[J].長沙理工大學(xué)校學(xué)報(自然科學(xué)版)，2011，8(1):65-69.

[5] 朱斌，管莉，張勝超，等.基于優(yōu)化遺傳算法的模糊聚類圖像分割算法[J].彈箭與制導(dǎo)學(xué)報，2008，28(4):190-192.

[6] 種勁松，周孝寬，王宏琦，等.基于遺傳算法的圖像閾值分割[J].電子科學(xué)學(xué)刊，2000，22(5):785-790.

[7] 李賢陽，黃嬋.一種結(jié)合改進Otsu法和改進遺傳算法的圖像分割方法[J].實驗室研究與探索，2012，31(12):57-61.

[8] 李輝.基于改進遺傳算法的圖像分割[D].長春:東北師范大學(xué)，2004.

[9] 單春芝.基于形態(tài)學(xué)策略的高分辨率遙感影像道路提取方法研究[D].青島:山東科技大學(xué)，2011.

[10] 楊修國.淺談圖像閾值分割技術(shù)[J].電子設(shè)計工程，2012，20(23):36-37.

[11] 葉文浩.閾值分割算法的研究及其在拉鏈缺陷檢測中的應(yīng)用[D].廣州:廣東工業(yè)大學(xué)，2013.

[12] 馬文，周紹光，丁慧珍.基于遺傳算法的Otsu法在圖像分割中的應(yīng)用[J].沿海企業(yè)與科技，2005(8):160-161.

[13] 黃友銳.智能優(yōu)化算法及其應(yīng)用[M].北京:國防工業(yè)出版社，2008:17-20.

[14] 殷春芳，李正明，孫俊.一種混合遺傳算法在圖像分割中的應(yīng)用[J].計算機仿真，2004，21(8):158-160.

[15] 史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京:北京航空航天大學(xué)出版社，2011:178-204.

[16] 趙云珍.遺傳算法及其改進[D].昆明:昆明理工大學(xué)，2005.

[17] 李康順，李茂民，張文生.一種基于改進遺傳算法的圖像分割方法[J].計算機應(yīng)用研究，2009，26(11):4364-4367.