基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割

許良鳳， 林 輝， 胡 敏， 吳東升， 徐元英， 景 佳

（1. 合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)應(yīng)用物理系，安徽 合肥 230009；3. 合肥工業(yè)大學(xué)科研處，安徽 合肥 230009；4. 中國科學(xué)院等離子體物理研究所，安徽 合肥 230031）

基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割

許良鳳1， 林 輝2， 胡 敏1， 吳東升3， 徐元英2， 景 佳4

（1. 合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230009；2. 合肥工業(yè)大學(xué)應(yīng)用物理系，安徽 合肥 230009；3. 合肥工業(yè)大學(xué)科研處，安徽 合肥 230009；4. 中國科學(xué)院等離子體物理研究所，安徽 合肥 230031）

模擬退火和并行遺傳算法是兩種較好的改進(jìn)進(jìn)化算法性能的方法。將這兩種思想有機(jī)地結(jié)合起來，利用遺傳算法能全局尋優(yōu)的優(yōu)勢和模擬退火算法的爬山性能，提出了一種基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割算法。在該算法中，進(jìn)化在多個不同的子群中并行進(jìn)行，利用模擬退火算法的爬山性能，避免單種群進(jìn)化過程中出現(xiàn)的過早收斂現(xiàn)象，提高整個算法的收斂速度。實(shí)驗證明，這種新的圖像分割算法與并行遺傳算法相比，不僅能夠?qū)D像進(jìn)行準(zhǔn)確的分割，而且具有更強(qiáng)的精確性和穩(wěn)定性。其收斂速度明顯比并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割快。

醫(yī)學(xué)圖像分割；Otsu；并行遺傳算法；模擬退火

醫(yī)學(xué)圖像是臨床醫(yī)生和專家進(jìn)行疾病診斷的重要依據(jù)，而醫(yī)學(xué)圖像分割技術(shù)就是將圖像中感興趣的觀察目標(biāo)提取出來，以有利于醫(yī)學(xué)研究和臨床診斷。由于醫(yī)學(xué)圖像的解剖組織結(jié)構(gòu)和形狀十分復(fù)雜，加上本身具有的模糊和不均勻等特點(diǎn)，另外還受到圖像噪聲，成像質(zhì)量等諸多因素的影響，傳統(tǒng)的圖像分割方法顯得很困難，因此在這個領(lǐng)域已出現(xiàn)了許多不同的圖像分割方法[1]。

常用的圖像分割方法包括灰度閾值法，邊緣檢測法等[2]。這些方法要求目標(biāo)和背景之間有明顯的灰度變化。但是在實(shí)際情況中，由于光照、對焦等影響，這種明顯的灰度變化很難出現(xiàn)。因此人們提出了許多新的圖像分割的方法，比較有代表性的如Kapur 等人提出的最佳熵閾值法[3],以及1979年由N Otsu 提出的最大類間方差方法（Otsu法）[4]等。最大類間方差選擇閾值的目的在于用幾個閾值將圖像的灰度直方圖分成獨(dú)立的類，使得各類間的方差最大。確定閾值是閾值化分割的關(guān)鍵，最佳閾值的確定是目前有待于解決的問題。根據(jù)閾值的個數(shù)，圖像閾值分割可分為單閾值分割和多閾值分割。多閾值分割問題可轉(zhuǎn)化為一系列單閾值分割問題來解決，但這需要在全灰度范圍內(nèi)搜索一個最佳門限組合，耗時較多，難于實(shí)際應(yīng)用。為簡化計算，可利用遺傳、免疫等進(jìn)化算法來搜索最佳閾值[5-6]。由于遺傳算法容易導(dǎo)致過早收斂，使得算法的精確性、穩(wěn)定性受到限制，且收斂速度也受到限制。

為了進(jìn)一步改善這些弱點(diǎn)，本文在“基于并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割”[7]一文的基礎(chǔ)上將模擬退火和并行遺傳算法有機(jī)地結(jié)合起來，利用遺傳算法能全局尋優(yōu)的優(yōu)勢和模擬退火算法的爬山性能設(shè)計了基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割，在該算法中，一方面利用了并行遺傳算法將并行計算機(jī)的高速并行性和遺傳算法天然并行性相結(jié)合，極大地提升了遺傳算法的求解速度和質(zhì)量；另一方面通過Boltzmann機(jī)制來接收子代，這樣做有利于優(yōu)良個體的保留。隨著進(jìn)化過程的進(jìn)行，溫度逐漸下降，接收劣質(zhì)解的概率逐漸減小，即利用模擬退火算法的爬山性能提高整個算法的收斂速度。仿真結(jié)果表明，該算法能夠準(zhǔn)確、迅速地找到圖像分割的最佳閾值，并對圖像進(jìn)行雙閾值分割，具有較好的效果、較強(qiáng)的穩(wěn)定性和精確性和較快的收斂速度。

1 基于最大類間方差閾值的圖像分割

這樣，利用最大類間方差法,圖像的雙閾值分割的閾值求解問題就可歸納為最佳閾值,的優(yōu)化問題。

2 基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割

2.1 并行遺傳算法

并行遺傳算法主從處理器的結(jié)構(gòu)圖如文獻(xiàn)[7]所示。首先主處理器將種群劃分成若干個子種群給從處理器，然后各個子種群在不同的從處理器上相互獨(dú)立的并發(fā)執(zhí)行進(jìn)化操作主循環(huán)，每運(yùn)行完確定的代數(shù)以后，每個從處理器運(yùn)行的遺傳算法的主循環(huán)將接收上游相鄰主循環(huán)的最佳染色體，并向下游相鄰主循環(huán)傳遞自身的最佳染色體；如此運(yùn)行下去直到終止條件滿足為止。當(dāng)算法結(jié)束時，每個從處理器就有一個最佳染色體，從處理器將各自的最佳染色體傳給主處理器，主處理器取其中最佳染色體作為最后的結(jié)果。

2.2 模擬退火算法

模擬退火算法起源于統(tǒng)計物理學(xué)中對固體退火過程的模擬[8]。它采用Boltzmann接受準(zhǔn)則接收新解, 用一個稱為冷卻系數(shù)的參數(shù)控制算法進(jìn)程, 使算法在多項式時間里給出一個近似最優(yōu)解。求解過程如下：

（1） 初始化退火溫度Tk（令k=0），產(chǎn)生隨機(jī)初始解X0；

（2） 在溫度Tk下重復(fù)執(zhí)行如下操作，直至達(dá)到溫度Tk的平衡狀態(tài)：

1） 在解x的領(lǐng)域中產(chǎn)生新的可行解x′；

2） 計算新解的評價函數(shù) f (x′)和舊解的評價函數(shù) f (x)的差值Δ f；

3） 依照概率min{1, exp (-Δf /Tk) }＞random[0, 1 ]接收新解，其中random [0, 1 ]是[0, 1 ]區(qū)間內(nèi)的隨機(jī)數(shù)。

（3） 令 Tk+1＝αTk，k←k+1，其中 α∈(0, 1)。若滿足收斂判據(jù)，則退火過程結(jié)束；否則，轉(zhuǎn)(2)。

2.3 基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割

由式(1)可知，圖像雙閾值分割的閾值求解問題是一個優(yōu)化問題，結(jié)合模擬退火及并行遺傳算法的特點(diǎn)，提出一種基于模擬退火并行遺傳算法的 Otsu雙閾值醫(yī)學(xué)圖像分割。每個處理器運(yùn)行模擬退火遺傳算法的主循環(huán)詳細(xì)流程圖如圖1所示。

圖1 每個從處理器模擬退火遺傳算法的主循環(huán)流程圖

（1） 種群初始化

在搜索空間隨機(jī)產(chǎn)生N個個體作為初始種群，并計算每個個體的適應(yīng)度。

（2） 編 碼

由于圖像灰度值在0～255之間，故將各個染色體編碼為16位二進(jìn)制碼，前8位代表一個分割閾值，后8位代表另一個分割閾值。

（3） 適應(yīng)度函數(shù)

采用式(1)作為適應(yīng)度函數(shù)。

（4） 選 擇

采用進(jìn)行賭輪法（蒙特卡羅法）。

（5） 交 叉

采用雙點(diǎn)交叉，兩個交叉點(diǎn)分別在前8位和后8位隨機(jī)產(chǎn)生，對隨機(jī)匹配交叉的個體的部分串（在交叉點(diǎn)后）進(jìn)行互換。

（6） 變 異

按變異概率隨機(jī)地改變前8位和后8位中某一個串位的值(即取反)。

3 結(jié)果與分析

為驗證本文算法的有效性，作者將本文算法與并行遺傳算法分別對圖像進(jìn)行分割實(shí)驗并作對比。實(shí)驗中模擬退火并行遺傳算法的參數(shù)如下：從處理器的個數(shù)為2，每個從處理器處理種群的個體總數(shù)為10，變異概率為Pm=0.1，交叉概率為Pc=0.6，溫度冷卻系數(shù)α = 0.9，退火初始溫度T =999，迭代代數(shù)為150。對兩種算法分別進(jìn)行了100次獨(dú)立實(shí)驗。

3.1 分割結(jié)果比較

圖2(a)是腦部MR原始圖像(512×512)，根據(jù)窮盡搜索的結(jié)果，真實(shí)閾值為（51, 150）。

兩種算法100次計算所得平均閾值并取整都與真實(shí)閾值相同，即使用雙閾值t1=51，t2=150（與真實(shí)值相同）的分割結(jié)果如圖2(b)所示。

圖2 分割結(jié)果

3.2 算法穩(wěn)定性和精確性比較

表1列出了各個算法所得結(jié)果的平均值、絕對誤差、相對誤差和方差，對比了基于并行遺傳算法的Otsu雙閾值（算法1）與基于模擬退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割（算法2）兩種算法的性能。平均值、絕對誤差和相對誤差代表了算法的精確性，而方差則說明了算法的穩(wěn)定性?？梢钥闯?，不論是在精確性，還是在穩(wěn)定性上，本文算法相對算法1都更接近真實(shí)值，且各次計算結(jié)果的波動更小，更為穩(wěn)定。

表1 算法性能對比

3.3 算法收斂速度比較

圖3是100次實(shí)驗的統(tǒng)計平均結(jié)果曲線，圖中每一進(jìn)化代的適應(yīng)度值均為100次平均的結(jié)果。

圖3 平均進(jìn)化曲線圖

由圖3可以看到基于模擬退火并行遺傳算法的Otsu雙閾值的收斂速度比基于并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割的收斂速度要快?；谀M退火并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割經(jīng)過約4代的種群迭代后收斂，而基于并行遺傳算法的Otsu雙閾值醫(yī)學(xué)圖像分割則要經(jīng)過約15代的種群迭代后收斂。

4 結(jié) 論

本文將模擬退火和并行遺傳算法兩種思想有機(jī)的結(jié)合起來，建立了一種基于模擬退火并行遺傳算法的 Otsu雙閾值醫(yī)學(xué)圖像分割，對比實(shí)驗說明，本文提出的模擬退火并行遺傳算法的Otsu雙閾值成功地應(yīng)用于醫(yī)學(xué)圖像分割，不僅保持了模擬退火并行遺傳算法比并行遺傳算法收斂速度快的特點(diǎn)，在不增大運(yùn)算復(fù)雜度的情況下，在優(yōu)化閾值的搜索性能方面表現(xiàn)出了一定的優(yōu)勢，提高了搜索的準(zhǔn)確性與穩(wěn)定性。

[1]林 瑤, 田 捷. 醫(yī)學(xué)圖像分割方法綜述[J]. 模式識別與人工智能, 2002, 15(2)：192-204.

[2]章毓晉. 圖像工程(中冊)(第2版)[M]. 北京：清華大學(xué)出版社, 2005. 73-201.

[3]Kapur J N, Sahoo P K, et al. A new method of gray-level picture thresholding using the entropy of the histogram [J]. Computer Vision, Graphics, and Image Processing, 1985, 29(3)：273-285.

[4]Otsu N. A threshold selection method from gray-level histograms [J]. IEEE Transactions on Systems, Man and Cybernetic, 1979, 9(1)：62-66.

[5]Ujjwal Maulik. Medical image segmentation using genetic algorithms [J]. IEEE Transactions on Information Technology in Biomedicine, 2009, 13(2)：166-173.

[6]李 映, 趙榮椿, 張艷寧, 等. 基于自適應(yīng)免疫遺傳算法的圖像分割[J]. 模式識別與人工智能, 2005,18(2)：193-197.

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

[8]康立山. 非數(shù)值并行算法(第 1冊)——模擬退火算法[M]. 北京：科學(xué)出版社, 1997. 22-55.

An Otsu Dual-threshold Value Method Based on Simulated Annealing Parallel Genetic Algorithm for Medical Image Segmentation

XU Liang-feng1, LIN Hui2, HU Min1, WU Dong-sheng3, XU Yuan-ying2, JING Jia4
( 1. School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China;2. Application Physics Department, Hefei University of Technology, Hefei Anhui 230009, China;3. Research and Administration Department, Hefei University of Technology, Hefei Anhui 230009, China;4. Institute of Plasma Physics, Chinese Academy of Sciences, Hefei Anhui 230031, China )

Simulated annealing and parallel genetic algorithm are two helpful methods which can improve the performance of evolutionary algorithm. The paper applies the global optimum performance of evolutionary programming and the hill climbing performance of simulated annealing, and proposes an Otsu dual-threshold value method based on simulated annealing parallel genetic algorithm for medical image segmentation. In the algorithm, evolutions of subgroups are performed among subgroups in parallel, and the hill climbing performance of simulated annealing is utilized, so this algorithm avoids premature convergence of alone group evolutionary process and improves its convergence efficiency. Experiments show that this new algorithm can achieve exact image segmentation and is of better accuracy and stability than parallel genetic algorithm, and its convergence speed is faster than the Otsu dual-threshold value method based on parallel genetic algorithm.

medical image segmentation; Otsu; parallel genetic algorithm; simulated annealing

TP 391.41

A

1003-0158(2011)05-0025-05

2010-03-09

國家自然科學(xué)青年基金資助項目（10805012）

許良鳳（1970-），女，安徽肥東人，副教授，碩士，主要研究方向為多媒體通信，圖像處理。