一種結(jié)合遺傳算法和最大類間方差法的圖像分割新方法

韓海峰

(忻州師范學(xué)院 數(shù)學(xué)系，忻州 034000)

?

一種結(jié)合遺傳算法和最大類間方差法的圖像分割新方法

韓海峰

(忻州師范學(xué)院 數(shù)學(xué)系，忻州 034000)

傳統(tǒng)的一維圖像Otsu方法，只能對圖像的灰度信息進(jìn)行處理，對空間信息、像素等部分不能得到處理，因此在圖像受到噪聲或其他干擾時(shí)灰度直方圖中的波峰、波谷會呈現(xiàn)不明顯的分布，造成分割失誤.本文結(jié)合遺傳算法和最大類間方差法的圖像分割新方法,是以遺傳算法確定閥值空間中的最優(yōu)閥值，最大類間方差法確定圖像背景和目標(biāo)圖像之間的灰度方差面的最大值，避免受到噪聲等因素的干擾.通過仿真實(shí)驗(yàn)發(fā)現(xiàn)該圖像分割方法可降低分割時(shí)間,分割質(zhì)量較好，發(fā)展前景廣闊.

遺傳算法；圖像分割；最大類間方差法

0 引 言

隨著科技的不斷發(fā)展，閥值分割技術(shù)也得到了極大的拓展，許多圖像分割方式都是在閥值分割技術(shù)的基礎(chǔ)上被提出的.其中包括：最大熵原理(the maximum entropy principle)、最大類間方差法、最小誤差法以及最小偏態(tài)法.最大類間方差(Otsu)是以統(tǒng)計(jì)原理為基礎(chǔ)的判決方法，該項(xiàng)判決方法不需要經(jīng)過人工設(shè)定，系統(tǒng)可自動(dòng)選取閥值，這種判決方法具有運(yùn)算簡單、分割速度快等優(yōu)勢.也正因?yàn)檫@些優(yōu)勢使它成為使用頻率最高的圖像分割法.在Otsu閾值法中可選出類間方差中最大從一項(xiàng)，實(shí)現(xiàn)圖像中背影和目標(biāo)圖像的切割.在過去，一維圖像Otsu法只能處理圖像中的灰度信息，在空間信息、像素部分不能得到處理，因此在圖像受到噪聲或其他干擾時(shí)灰度直方圖中的波峰、波谷會呈現(xiàn)不明顯的分布，造成分割失誤.在該項(xiàng)問題中，我國劉建莊教授提出了二維Otsu法，二維Otsu法是以二維直方圖的形式選擇無灰度級、平均灰度級的閥值，閥值從一維發(fā)展至二維，與一維相比二維Otsu法的抗噪聲干擾能力更強(qiáng)，圖像分割效果也強(qiáng)于一維，大大提高了圖像分割質(zhì)量.

遺傳算法(Genetic Algorithm)是以生活遺傳機(jī)制以及自然選擇以模型而來的一種擇優(yōu)算法，這種算法可自行處理且魯棒性(robustness)強(qiáng)，目前已被廣泛應(yīng)用在圖像處理、圖像識別、工業(yè)優(yōu)化控制等領(lǐng)域.本文通過分析傳統(tǒng)Otsu閥值的處理原理，將遺傳算法融入Otsu閥值并進(jìn)行仿真實(shí)驗(yàn)探討了這一形式的有效性.

1 圖像分割及其常用方法

圖像分割常被應(yīng)用與計(jì)算機(jī)模式和模式識別中，其中目標(biāo)檢測、特征篩選、目標(biāo)識別等操作都是通過圖像分割技術(shù)實(shí)現(xiàn)的.圖像分割指的是將目標(biāo)圖像與背景圖像分離，讓用戶能在一個(gè)圖像中成功的選取出自己感興趣的那部分.圖像分割技術(shù)中包括許多種方式，其中有閥值法、邊緣檢測法、區(qū)域跟蹤法等.在這三種圖像分割技術(shù)中,區(qū)域跟蹤法和邊緣檢測法對圖像質(zhì)量要求偏高，需要目標(biāo)圖像與背景圖像存在明顯的灰度變化才能應(yīng)用.但是在實(shí)際的狀況下，許多圖像的灰度因素難以特別明顯，導(dǎo)致分割準(zhǔn)確值的偏離過大.但閥值法對圖像質(zhì)量要求一般且運(yùn)作簡單、性能穩(wěn)定等，目前被廣泛地應(yīng)用在圖像分割中.

1.1 灰度閥值分割法

灰度閥值分割法是一種常見的并行處理技術(shù)，它是圖像分割中應(yīng)用最廣泛的一種，閥值的分割過程實(shí)際上是輸入圖像f到輸出圖像g的變換，公式如下：

(1)

其中，T為閥值，在物體的圖像元素g(i，j)=0的背景的圖像元素g(i，j)=0.可見，圖像閥值算法的關(guān)鍵是確定最優(yōu)閥值閾.

1.2 區(qū)域跟蹤法

區(qū)域跟蹤法是以區(qū)域生長為基礎(chǔ)，將相似性質(zhì)的像素集合成區(qū)域.在每個(gè)需要分割的區(qū)域中尋找種子像素為生長.在種子像素周圍與其有相同性質(zhì)的像素結(jié)合在種子像素的區(qū)域中.然后將種子像素中得出新像素為種子像素，再進(jìn)行以上操作直到無符合條件的像素被篩選出，此時(shí)一個(gè)區(qū)域被形成了.區(qū)域跟蹤法有一個(gè)明顯的特點(diǎn)，它的運(yùn)算步驟簡單，處理均勻聯(lián)通的對象時(shí)可得到較好的分割效果.但是區(qū)域跟蹤法也有缺點(diǎn)，噪聲對它的影響較大，種子點(diǎn)需要人為的進(jìn)行設(shè)置，否則很容易有空洞區(qū)域的存在，導(dǎo)致分割效果不佳.

1.3 邊緣檢測法

邊緣檢測法是圖像分割中的一種，它是檢測結(jié)構(gòu)突變、灰度等級的方法，它代表某一區(qū)域的結(jié)束，另一區(qū)域的開始，這種不連續(xù)的性質(zhì)稱為邊緣.不同的圖像具有不同的灰度，在邊界部分一般具有明顯的邊緣，以邊緣特征進(jìn)行分割圖像.在分割圖像上常應(yīng)用一階微分算子，其中包括：羅伯茨算子(Roberts算子)、Sobel算子、Prewitt算子等，二階微分算子有Kirsh算子、拉普拉斯算子(Laplace算子)等.在實(shí)際的運(yùn)作中一般以微分算子的小區(qū)域模板作為代表，其中微分運(yùn)算是通過模版、圖像卷積來展現(xiàn)的.這些算子對噪聲的敏感性偏高，但是只適合噪聲小且簡單圖像.

2 最大類間方差法圖像分割方法

2.1 最大類間方差法圖像分割

最大類間方差法是由日本學(xué)者Nobuyuki Otsu在1979年提出的，Otsu算法是在灰度直方圖的基礎(chǔ)上用最小二乘法原理推導(dǎo)出來的最佳分割閥值.通過計(jì)算目標(biāo)圖像與背景圖像的最大方差的灰度閥值分離目標(biāo)圖像與背景圖像，選擇尺寸為M×N的原圖像，在此設(shè)圖像灰度級為L，同時(shí)與原圖像相鄰的圖像領(lǐng)域平均灰度級為L，在原始圖像在坐標(biāo)(x,y)的位置上標(biāo)記象素灰度值，記作i，并用f(x,y)標(biāo)記，在圖像(x,y)坐標(biāo)位置的k×k位置平均灰度值記作j，用g(x,y)表示，可推導(dǎo)出下列公式：

(1)

在公式(1)中，假設(shè)圖像寬度為m，圖像高度為n，可得出：

(2)

其中，i=0,1,…,L-1;j=0,1,…,L-1

二維直方圖的平面如圖1所示，Ⅰ區(qū)為目標(biāo)圖像，Ⅲ區(qū)為背景圖像，Ⅰ區(qū)與Ⅲ區(qū)呈對角線分布；Ⅱ區(qū)為邊界線，Ⅳ區(qū)為噪聲，Ⅱ區(qū)與Ⅳ區(qū)遠(yuǎn)離對角線.利用二維Otsu法在Ⅰ區(qū)與Ⅲ區(qū)篩選出最佳閥值，從而保障目標(biāo)圖像與背景圖像的信息量最大化.

圖1 二維直方圖

若Ⅰ區(qū)與Ⅲ區(qū)是以不同的概率分布的，那么閥值為(s,t)，而出現(xiàn)兩類的概率為：

(3)

兩類均值向量為：

(4)

(5)

由此可知二維直方圖的總均值向量為：

(6)

與對角線相距較遠(yuǎn)的Ⅱ區(qū)和Ⅳ區(qū)在一般情況下概率為0，可設(shè)i和j在兩個(gè)區(qū)域內(nèi)：i=1,2,…,s和j=t+1,2,…,L，則可知以下關(guān)系公式：

w0+w1≈1,μT=w0μ0+w1μ1

(7)

類間離散度測度以矩陣SB(s,t)的軌跡表示，得出：

trSB=w0((μ0j-μTj)2+(μ0i-μTi)2)+((μ1j-μTj)2+(μ1i-μTi)2)

(8)

最佳閥值(s*,t*)可滿足下列式子：

(9)

2.2 最大類間方差法圖像分割的缺點(diǎn)

通過上述分析可見，在傳統(tǒng)運(yùn)算中Otsu閾值需要通過以下過程才能完成：①遍歷整個(gè)圖像的灰度值，運(yùn)算各個(gè)灰度值的類間方差.②排序類間方差，以圖像尺寸和運(yùn)算量的正比關(guān)系排列.由此可見，傳統(tǒng)Otsu閾值方法的步驟繁瑣且運(yùn)算量大.但分割閥值的確定是Otst圖像分割算法中不可或缺的部分.遺傳算法中可在全局中進(jìn)行搜索,對閥值進(jìn)行智能化篩選，可大大降低傳統(tǒng)Otsu閾值的計(jì)算量，提高圖像分割運(yùn)作效率.本文通過傳統(tǒng)Otsu閾值結(jié)合遺傳算法，以智能化篩選減少運(yùn)算量，尋求最優(yōu)Otsu閾值，實(shí)現(xiàn)圖像分割的運(yùn)作效率的提高.

3 結(jié)合遺傳算法和最大類間方差法的圖像分割新方法

3.1 遺傳算法

遺傳算法是美國J.Holland教授在1975年第一次提出，是一種模擬達(dá)爾文進(jìn)化論中遺傳學(xué)和自然選擇為原理產(chǎn)生的一種搜索算法，在處理復(fù)雜問題上具有優(yōu)越性.它的特點(diǎn)是只對在對象結(jié)構(gòu)中操作，遺傳算法與自然選擇中優(yōu)勝劣汰的原則類似，將待處理問題的解看作染色體，每個(gè)染色體為待處理問題的解.染色體形成特定的種群為解的搜索范圍，每個(gè)個(gè)體的適應(yīng)度由函數(shù)運(yùn)算得出，得出的值越大則解也相對較優(yōu).在求解的步驟中有選擇、變異等操作,加速染色體適應(yīng)新環(huán)境,進(jìn)而出現(xiàn)新的染色體群，在不斷的更新中得到相對最優(yōu)解.

3.2 結(jié)合遺傳算法和最大類間方差法的圖像分割新方法

最大類間方差法的求解可在空間閥值中，尋找到最優(yōu)解，閥值的解使圖像背景和目標(biāo)圖像之間的灰度方差值最大.本文通過遺傳算法在閥值空間中進(jìn)行快速計(jì)算、最優(yōu)解尋找等，可快速的尋找到符合最大類間方差標(biāo)準(zhǔn)的最優(yōu)閥值，具體過程如圖2所示.

基于遺傳算法的Ostu算法可分為如下操作步驟：

步驟1：個(gè)體范圍的劃分，實(shí)際圖像分割灰度值在0～255的范圍內(nèi)，因此種群個(gè)圖灰度值的范圍也在0～255之內(nèi)，代表每個(gè)灰度值的數(shù)字通過隨機(jī)產(chǎn)生.

步驟2：適應(yīng)度函數(shù)的確定，在Ostu算法中的背景圖像與目標(biāo)圖像間的方差比例與分割的準(zhǔn)確率呈正比，也就是說個(gè)體的適應(yīng)度值越大，性能越好，個(gè)體適應(yīng)度函數(shù)為：

f(t)=w1(t)×w2(t)×(u1(t)-u2(t))2

(10)

步驟3：選擇操作，本文采用遺傳算法中兩兩競爭的法則，在上一代種群中的個(gè)體，作為父代進(jìn)行對比，個(gè)體適應(yīng)值<父代適應(yīng)值則淘汰，個(gè)體適應(yīng)值>父代適應(yīng)值可進(jìn)入下一輪競爭群體內(nèi).

步驟4：交叉操作，本文采用兩點(diǎn)交叉的方式，在選擇后的2個(gè)作為父母，在交叉概率Pc產(chǎn)生2個(gè)新個(gè)體，兩點(diǎn)交叉可增加算法中的隨機(jī)性，進(jìn)而獲取局部最優(yōu)值.

步驟5：變異操作，通過變異概率Pm對每個(gè)個(gè)體的變異進(jìn)行處理，在變異操作下個(gè)體多樣性增加.

步驟6：結(jié)束條件，經(jīng)過連續(xù)的多代操后，最優(yōu)適應(yīng)度值未達(dá)最大進(jìn)化代數(shù)或無改變時(shí)，系統(tǒng)停止操作，則最佳分割閥值為最高適應(yīng)度值的個(gè)體.

圖2 遺傳算法的Ostu算法流程圖

4 仿真實(shí)驗(yàn)

4.1 參數(shù)設(shè)置

4.2 分割效果比較

采用傳統(tǒng)的Ostu算法的圖片分割效果如圖4所示，遺傳算法優(yōu)化的Ostu算法分割效果如圖5所示.

圖3 原始圖

圖4 傳統(tǒng)的Ostu算法效果

圖5 改進(jìn)的Ostu算法效果

對比圖4和圖5的分割效果可知，傳統(tǒng)算法經(jīng)過改進(jìn)后與遺傳算法結(jié)合，所得到的圖像更為清晰，目標(biāo)圖像邊界更為明顯，則表明遺傳算法優(yōu)化的Ostu算法優(yōu)于傳統(tǒng)的Ostu算法.

4.3 算法性能比較

對圖3 、圖4、 圖5的分割效果進(jìn)行對比，對比項(xiàng)目包括：計(jì)算次數(shù)、計(jì)算時(shí)間、最優(yōu)閾值等，分別衡量閥值的獲取和尋優(yōu)的用時(shí)，比較結(jié)果見表1.

經(jīng)對比分析可見，傳統(tǒng)Ostu算法在計(jì)算次數(shù)、計(jì)算時(shí)間、最優(yōu)閾值方面均遜色于遺傳算法的Ostu圖像分割算法.由此可知，遺傳算法的Ostu圖像分割算法在圖像分割效果、處理用時(shí)等方面均具有優(yōu)勢，是一種較為理想的圖像分割方法.

表1 3幅圖像的算法性能比較

5 結(jié) 論

傳統(tǒng)的一維圖像Otsu法只能處理圖像中的灰度信息，在空間信息、像素部分不能得到處理，因此在圖像受到噪聲或其他干擾時(shí)灰度直方圖中的波峰、波谷會呈現(xiàn)不明顯的分布，造成分割失誤.本文遺傳算法和最大類間方差法的圖像分割新方法是以遺傳算法確定閥值空間中的最優(yōu)閥值，最大類間方差法確定圖像背景和目標(biāo)圖像之間的灰度方差面的最大值，避免受到噪聲等因素的干擾，在得到良好分割效果的同時(shí)降低了分割時(shí)間，其發(fā)展前景廣闊.

[1] 許良鳳,林 輝,羅 珣,等.基于并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割[J].工程圖學(xué)學(xué)報(bào),2011,32(2):88-92.

[2] 扶 曉,劉 勁,趙 蕾.基于遺傳算法的最佳直方圖熵圖像分割算法研究[J].電腦編程技巧與維護(hù),2011(18):101+103-101,103.

[3] 孫艷歌,邵 罕.基于改進(jìn)遺傳算法的最優(yōu)閾值圖像分割算法[J].信息系統(tǒng)工程,2010(6):25-25,27.

[4] 張?jiān)虑?胡 斌.基于遺傳神經(jīng)網(wǎng)絡(luò)的圖像分割[J].電腦開發(fā)與應(yīng)用,2011,24(2):16-18.

[5] SUN Pengfei , REN Hong'e , DONG Benzhi.Partial Minimum Error Thresholding Method of Cavity Image Combined with Genetic Algorithm[J].Computer Engineering and Applications,2012,48(7):169-171.

[6] Xue Lanyan,Cheng Li.IMAGE SEGMENTATION BASED ON THE METHOD OF THE MAXIMAL VARIANCE AND THE IMPROVED GENETIC ALGORITHM[J].Computer Applications and Software,2008,25(2):221-222,247.

[7] JIN Lu , FU Meng-Yin.Images Segmentation Based on Genetic Kernel Fuzzy C-Means Clustering Algorithm[J].Pattern Recognition and Artificial Intelligence,2013,26(2):205-210.

[8] LI Xian-yang,HUANG Chan.A Novel Method for Image Segmentation Based on Improved OTSU and Improved Genetic Algorithm[J].Laboratory Research and Exploration,2012(12):57-61,112.

A New Image Segmentation Method Combining Genetic Algorithm and Otsu Method

HAN Hai-feng

(Mathematics Department,Xinzhou Teachers College, Xinzhou 034000,China)

The traditional one-dimensional image Otsu method can only process the image grayinformation, and cannot get treatment on spatial information and pixel part.Ttherefore the image is affected by noise or other disturbances in the gray histogram of wave crest and trough which show the distribution is not obvious, resultingin insegmentation errors. In this paper, combining the image of genetic algorithm and Otsu segmentation method, the genetic algorithm is used to determine the optimal threshold threshold in the space Otsu method is used to determin the maximum of gray value variance sufacc between the background image and target image so as to, avoid noise interference and other factors. The simulation experiment shows that the image segmentation method can reduce the time of segmentation the segmentation quality is good,and the prospects of development are broad.

genetic algorithm; image segmentation; Otsu method

2014-12-02

韓海峰(1981-)，男，碩士，助教，研究方向：數(shù)學(xué)理論與算法分析.

TP391.41

A

1671-119X(2015)02-0043-04