王宏文，梁彥彥，王志華

（河北工業(yè)大學(xué)控制科學(xué)與工程學(xué)院，天津300130）

基于新遺傳算法的Otsu圖像閾值分割方法

王宏文，梁彥彥，王志華

（河北工業(yè)大學(xué)控制科學(xué)與工程學(xué)院，天津300130）

最大類間方差（Otsu）圖像分割法是常用的一種基于統(tǒng)計(jì)原理的圖像閾值分割方法。為了改善Otsu耗時(shí)較多、分割的精度低、易產(chǎn)生圖像誤分割等不足，將猴王遺傳算法與Otsu算法結(jié)合，運(yùn)用猴王遺傳算法的原理，尋找圖像灰度的最大類間方差，即最佳閾值。結(jié)果表明，結(jié)合后的方法不僅提高了圖像的分割質(zhì)量、縮短了運(yùn)算時(shí)間，而且非常適合圖像的實(shí)時(shí)處理。

圖像處理；最佳閾值；猴王遺傳算法；最大類間方差

引 言

圖像分割是數(shù)字圖像處理中的關(guān)鍵技術(shù)，它通常是為了簡化或者改變圖像的表示形式，使圖像更容易理解和分析［1］。圖像分割的準(zhǔn)確性直接影響后續(xù)任務(wù)的有效性［2］，因此具有十分重要的理論和實(shí)際意義。常用的圖像分割方法［3］有邊緣檢測法、區(qū)域跟蹤法和閾值法等。在實(shí)際應(yīng)用中，考慮到外界因素影響，閾值分割簡單有效且性能穩(wěn)定，成為圖像分割中的常用技術(shù)。

閾值分割技術(shù)中最大類間方差法（Otsu算法）［4］是最常用的，它基于統(tǒng)計(jì)原理，通過選擇一個(gè)閾值使得目標(biāo)與背景類間方差最大，從而達(dá)到分離圖像。但它比較耗時(shí)、分割的精度低、存在圖像誤分割等缺點(diǎn)。

猴王遺傳算法是一種新穎的全局搜索遺傳算法，具有程序直觀易懂、參量少、計(jì)算量小、收斂速度快等特點(diǎn)［5］。將此算法與Otsu算法進(jìn)行組合［6］來求解圖像的分割閾值，可有效地縮短Otsu算法處理實(shí)時(shí)圖像的時(shí)間，大大提高圖像的分割質(zhì)量。

1 Otsu算法

在1980年，Otsu算法被日本的大津展之提出來，Otsu算法是經(jīng)典的、無參量、沒有監(jiān)督的一種自適應(yīng)閾值選取的方法，它的原理是利用圖像中的灰度直方圖，確定目標(biāo)與背景之間的最大方差值，即圖像分割的閾值。

假設(shè)原始灰度圖像大小為A×B，灰度級別為D，f（x，y）為圖像中坐標(biāo)為（x，y）的像素的灰度值，設(shè)Rij為圖像中灰度級別為i、鄰域平均灰度為j的像素點(diǎn)的個(gè)數(shù)，那么可以得到圖像中灰度級別為i、鄰域平均灰度為j的像素點(diǎn)在整個(gè)圖像中的概率是：

圖1為圖像的2維直方圖，是一個(gè)L×L的矩陣。設(shè)原始灰度圖像的2維直方圖被閾值（m，n）分成4個(gè)部分，背景（目標(biāo)）內(nèi)部的像素與鄰域的平均灰度值接近。但是二者邊界處的像素與鄰域的平均灰度值差距較大，因此設(shè)區(qū)域0和1代表目標(biāo)或背景，區(qū)域2和3代表邊界點(diǎn)。所以應(yīng)該在0和1區(qū)上用Otsu法確定最佳閾值。

Fig.1 2-D histogram

設(shè)圖像中存在目標(biāo)C0（ω0）和背景C1（ω1）兩大類，那么二者出現(xiàn)的概率可以表示為：

則兩類對應(yīng)的均值向量分別為：

2維直方圖上總的均值向量為：

由于區(qū)域2和3占少量，可假設(shè)2維直方圖中區(qū)域2和3的分量和約為0（Pij≈0），

則定義一個(gè)目標(biāo)和背景間的離散測度矩陣為：

以矩陣σ（m，n）的軌跡作為類間離散度的測度，有：

尋找最佳閾值向量（m′，n′），使得：

從上述分析可知，傳統(tǒng)Otsu算法直接搜索使得（9）式運(yùn)算量十分大、耗費(fèi)時(shí)間長，難以應(yīng)用到實(shí)時(shí)處理中，而且效率低、分割誤差大。如果圖像尺寸的增加，其運(yùn)算量急劇增加。猴王遺傳算法存在并行性和全局搜索的優(yōu)點(diǎn)，加快獲得最優(yōu)閾值的速率，完善圖像分割的效果。

2 基于猴王遺傳算法的Otsu算法

2.1 猴王遺傳算法

猴王遺傳算法基本思想是：首先對種群中的各點(diǎn)按適應(yīng)度函數(shù)值進(jìn)行升序排列，排在前面的視為猴王點(diǎn)，然后和少部分較優(yōu)點(diǎn)一起直接復(fù)制到下代種群；接著引入部分變異染色體來更換其中的較劣點(diǎn)；然后讓最優(yōu)點(diǎn)依次與種群中的其它點(diǎn)通過一定的概率，進(jìn)行交叉變異，得到符合約束條件的新點(diǎn)。將這些點(diǎn)依次加入下一代種群，直到下一代種群中的數(shù)目達(dá)到設(shè)想規(guī)模。重復(fù)以上過程，達(dá)到最終預(yù)想結(jié)果［7］。與傳統(tǒng)遺傳算法［8-9］相比，猴王遺傳算法［10］融合交叉和變異遺傳運(yùn)算，可以各代最優(yōu)點(diǎn)（猴王點(diǎn)）為核心展開遺傳計(jì)算，迅速提高收斂速度和收斂概率?？珊喪鋈缦隆?/p>

（1）初始化：搜索空間內(nèi)隨機(jī)產(chǎn)生L個(gè)個(gè)體，將其函數(shù)值做升序排列，確定猴王點(diǎn)。將排在后面的Im個(gè)個(gè)體用搜索空間內(nèi)隨機(jī)產(chǎn)生的同樣數(shù)目的個(gè)體置換。令初始進(jìn)化代數(shù)為0。

（2）復(fù)制：從當(dāng)前群體中復(fù)制前面In個(gè)個(gè)體直接進(jìn)入新一代群體。

（3）交叉變異遺傳：通過猴王點(diǎn)交叉再產(chǎn)生LIn個(gè)新個(gè)體。如此產(chǎn)生新一代群體。

（4）排序新一代群體并引進(jìn)隨機(jī)個(gè)體：同步驟（1）。此時(shí)令進(jìn)化代數(shù)＝進(jìn)化代數(shù)＋1。新猴王點(diǎn)確定。

（5）達(dá)到終止代數(shù)或獲得滿意解則過程結(jié)束，否則轉(zhuǎn)步驟（2）。

2.2 基于猴王遺傳算法的閾值尋優(yōu)步驟和流程圖

步驟簡述如下。（1）初始化。在MATLAB7.1環(huán)境下對20幅256pixel×256pixel原始灰度圖像進(jìn)行閾值選取仿真，設(shè)初始種群L＝20，初始代數(shù)＝0，最大進(jìn)行化代數(shù)100，隨機(jī)個(gè)體占比Rm＝0.4，復(fù)制率Rn＝0.08，隨機(jī)數(shù)Rd＝0.8∈（0，1），調(diào)整系數(shù)α＝3，交叉概率0.7，變異概率0.3。

（2）計(jì)算初始個(gè)體灰度的類間方差。若要分割越準(zhǔn)確，目標(biāo)和背景的方差就要越大，所以用圖像灰度的類間方差為適應(yīng)度函數(shù)。如果個(gè)體的適應(yīng)度值越大，表明其性能越好。適應(yīng)度函數(shù)如下：

式中，λ1（m）為大于m的灰度像素?cái)?shù)，λ2（m）為小于m的灰度像素?cái)?shù)，v2（m）為大于m的平均灰度值，v1（m）表示小于m的平均灰度值。

（3）排序和替換。將計(jì)算出來的每個(gè)個(gè)體（設(shè)個(gè)體為Qi，i＝1，2，…，L）適應(yīng)度進(jìn)行升序排列，即有f（Q1′）≤f（Q2′）≤…≤f（QL′）（i＝1，2，…，L），找出猴王點(diǎn)Q1′。然后根據(jù)隨機(jī)個(gè)體占比Rm，用隨機(jī)生成的同樣規(guī)模的新個(gè)體替換Im（Im＝round（Rm·L），round（x）表示與x距離最小的整數(shù)）之后的個(gè)體，組成新的種群。

（4）復(fù)制、產(chǎn)生新個(gè)體。根據(jù)復(fù)制率Rn，從當(dāng)前群體中復(fù)制前面In＝round（Rn·L）個(gè)個(gè)體直接進(jìn)入新一代群體。

（5）交叉變異。將猴王點(diǎn)與In之后的個(gè)體進(jìn)行交叉，然后產(chǎn)生L－In個(gè)新個(gè)體。其中：

若（12）式中的Qi越界，則重新用（11）式反復(fù)計(jì)算，直到Qi在搜索范圍內(nèi)。在一定的概率下選取個(gè)體向量的元素進(jìn)行變異。

Fig.2 Flow chart

（6）計(jì)算新一代種群個(gè)體灰度的類間方差（見步驟（2））。若連續(xù)多代種群適應(yīng)度都沒有任何改變，或已經(jīng)達(dá)到最大進(jìn)化代數(shù)，停止尋優(yōu)操作，這時(shí)得到的最高適應(yīng)度值就是圖像分割閾值。否則返回步驟（2）。

流程圖見圖2。

3 仿真結(jié)果及分析

圖3為原圖，圖4為傳統(tǒng)的Otsu算法的分割效果圖，圖5為本文中算法的分割效果圖，表1為本文中的算法與傳統(tǒng)的Otsu算法的性能表（只列舉了其中10幅圖像的仿真結(jié)果）。

Fig.3 Original illustration

Fig.4 Segmentation effect of traditional Ostu algorithm

Table 1 The performance of two algorithms

對比上述3幅圖像可見，基于猴王遺傳算法的Otsu圖像分割方法明顯優(yōu)于傳統(tǒng)的Otsu圖像分割方法。圖像分割后邊緣輪廓的清晰度提高，目標(biāo)邊緣的范圍增大，輪廓清晰度也瞬間提高，整個(gè)圖像也更清楚，而且圖像的失真率大幅度減小。通過表1可以看出，達(dá)到最大閾值的時(shí)間明顯縮短，傳統(tǒng)算法取得最優(yōu)閾值的平均時(shí)間為7.825ms，新算法平均時(shí)間為2.138ms。傳統(tǒng)算法平均最優(yōu)閾值約為116，新算法平均最優(yōu)閾值約為109。從而明顯彌補(bǔ)單獨(dú)使用Otsu算法的不足，成為一種較理想的圖像實(shí)時(shí)閾值分割方法。

4 結(jié) 論

圖像分割在近代的應(yīng)用領(lǐng)域已取得了重大的成果和深遠(yuǎn)的影響，如生物醫(yī)學(xué)工程、航空航天、工業(yè)檢測、機(jī)器人視覺、公安司法等。仿真實(shí)驗(yàn)結(jié)果表明，將本文中的算法對比傳統(tǒng)Otsu圖像分割算法，前者能夠更快速、更準(zhǔn)確地找到圖像的全局最優(yōu)分割閾值，大大縮短了最優(yōu)閾值搜索時(shí)間，有利于圖像的實(shí)時(shí)處理，將具有廣泛的應(yīng)用前景。

［1］ YANG H，QU X J.Survey of image segmentationmethod［J］.Computer Development and Applications，2005，18（3）：21-23（in Chinese）.

［2］ LIU JH，WANG JW.research on contour correction in medical CT image segmentation［J］.Journal of Computers，2012，7（3）：762-767.

［3］ YANG H Y.Application research on image segmentation method［J］.Computer Simulation，2012，29（2）：229-232（in Chinese）.

［4］ HAN C Y，KONG J.An improved image segmentation algorithm based on Otsu method［J］.Computer Simulation，2011，28（6）：262-265（in Chinese）.

［5］ WEIZh Ch，ZHOU J L，HANG L，et al.A study on image segmentation by a new adaptive algorithm［J］.Journal of Image and Graphics，2000，5（3）：216-220（in Chinese）.

［6］ XU Y F.Image segmentation based on the genetic fuzzy C-mean algorithm［J］.Journal of Northwestern Polytechnical University，2002，20（4）：549-553（in Chinese）.

［7］ LU B B，JIA Zh H，HE D，et al.A new FCM algorithm based on monkey-king genetic algorithm for remote sensing image segmengtation［J］.Laser Journal，2010，31（6）：15-17（in Chinese）.

［8］ LIY Zh，LIU H X，ZHANG Sh.Improvingmonkey-king genetic algorithm［J］.Journal of Nanjing Normal University（Engineering and Technology Edition），2004，4（3）：53-56（in Chinese）.

［9］ JIN J，SU Y.An improved adaptive genetic algorithm［J］.Computer Engineering and Applications，2005，18（2）：64-69（in Chinese）.

［10］ SHI B，TONG X N.Dual-threshold image segmentation method based on parallel genetic algorithms［J］.Microcomputer Information，2009，25（1）：304-306（in Chinese）.

Otsu image threshold segmentation method based on new genetic algorithm

WANG Hongwen，LIANG Yanyan，WANG Zhihua
（School of Control Science and Engineering，Hebei University of Technology，Tianjin 300130，China）

Maximum between-class variance（Otsu）image segmentation method is a common image threshold segmentation method based on statistical theory，but Otsu image segmentation method has some disadvantages，such as more time-consuming，low segmentation accuracy and false image segmentation.Combining the principles ofmonkey king genetic algorithms，with Otsu algorithm，image gray，justas optimal threshold，was found.The results show that combined method not only improves the quality of image segmentation but also reduce the computation time.It is very suitable for real-time image processing.

image processing；optimal threshold；monkey king genetic algorithm；maximum between-class variance

TN919.73

A

10.7510／jgjs.issn.1001-3806.2014.03.017

1001-3806（2014）03-0364-04

王宏文（1957-），男，碩士，教授，主要從事現(xiàn)代傳動(dòng)控制系統(tǒng)與智能化工程裝備的研究。

E-mail：wanghongwen＠hebut.edu.cn

2013-05-20；

2013-07-31