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

王宏文，梁彥彥，王志華

（河北工業大學控制科學與工程學院，天津300130）

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

王宏文，梁彥彥，王志華

（河北工業大學控制科學與工程學院，天津300130）

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

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

引 言

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

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

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

1 Otsu算法

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

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

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

Fig.1 2-D histogram

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

則兩類對應的均值向量分別為：

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

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

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

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

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

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

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

2.1 猴王遺傳算法

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

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

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

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

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

（5）達到終止代數或獲得滿意解則過程結束，否則轉步驟（2）。

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

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

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

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

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

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

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

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

Fig.2 Flow chart

（6）計算新一代種群個體灰度的類間方差（見步驟（2））。若連續多代種群適應度都沒有任何改變，或已經達到最大進化代數，停止尋優操作，這時得到的最高適應度值就是圖像分割閾值。否則返回步驟（2）。

流程圖見圖2。

3 仿真結果及分析

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

Fig.3 Original illustration

Fig.4 Segmentation effect of traditional Ostu algorithm

Table 1 The performance of two algorithms

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

4 結 論

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

［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-），男，碩士，教授，主要從事現代傳動控制系統與智能化工程裝備的研究。

E-mail：wanghongwen＠hebut.edu.cn

2013-05-20；

2013-07-31