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

王宏文，梁彥彥，王志華

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

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

王宏文，梁彥彥，王志華

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

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

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

引 言

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

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

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

1 Otsu算法

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

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

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

Fig.1 2-D histogram

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

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

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

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

則定義一個目標和背景間的離散測度矩陣為：

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

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

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

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

2.1 猴王遺傳算法

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

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

（2）復(fù)制：從當前群體中復(fù)制前面In個個體直接進入新一代群體。

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

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

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

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

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

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

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

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

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

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

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

Fig.2 Flow chart

（6）計算新一代種群個體灰度的類間方差（見步驟（2））。若連續(xù)多代種群適應(yīng)度都沒有任何改變，或已經(jīng)達到最大進化代數(shù)，停止尋優(yōu)操作，這時得到的最高適應(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圖像分割方法。圖像分割后邊緣輪廓的清晰度提高，目標邊緣的范圍增大，輪廓清晰度也瞬間提高，整個圖像也更清楚，而且圖像的失真率大幅度減小。通過表1可以看出，達到最大閾值的時間明顯縮短，傳統(tǒng)算法取得最優(yōu)閾值的平均時間為7.825ms，新算法平均時間為2.138ms。傳統(tǒng)算法平均最優(yōu)閾值約為116，新算法平均最優(yōu)閾值約為109。從而明顯彌補單獨使用Otsu算法的不足，成為一種較理想的圖像實時閾值分割方法。

4 結(jié) 論

圖像分割在近代的應(yīng)用領(lǐng)域已取得了重大的成果和深遠的影響，如生物醫(yī)學(xué)工程、航空航天、工業(yè)檢測、機器人視覺、公安司法等。仿真實驗結(jié)果表明，將本文中的算法對比傳統(tǒng)Otsu圖像分割算法，前者能夠更快速、更準確地找到圖像的全局最優(yōu)分割閾值，大大縮短了最優(yōu)閾值搜索時間，有利于圖像的實時處理，將具有廣泛的應(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)代傳動控制系統(tǒng)與智能化工程裝備的研究。

E-mail：wanghongwen＠hebut.edu.cn

2013-05-20；

2013-07-31