改進(jìn)的遺傳算法在醫(yī)學(xué)圖像中的應(yīng)用

梁文宇， 龔 濤， 吳宇翔

(東華大學(xué) 信息技術(shù)與工程學(xué)院，上海 201600)

?

改進(jìn)的遺傳算法在醫(yī)學(xué)圖像中的應(yīng)用

梁文宇， 龔 濤， 吳宇翔

(東華大學(xué) 信息技術(shù)與工程學(xué)院，上海 201600)

針對(duì)標(biāo)準(zhǔn)的遺傳算法(GA)在優(yōu)化Otsu法求取圖像閾值時(shí)出現(xiàn)收斂速度慢、易早熟等問(wèn)題，提出了一種改進(jìn)的GA用于圖像分割。該算法根據(jù)種群不同的進(jìn)化代數(shù)和個(gè)體適應(yīng)度的大小，動(dòng)態(tài)地調(diào)整精英選擇策略和遺傳算子，從而提高了算法的收斂速度、得到了范圍穩(wěn)定的圖像分割閾值，且保持了種群多樣性。將該算法應(yīng)用于醫(yī)學(xué)圖像分割，實(shí)驗(yàn)結(jié)果表明：該算法可以對(duì)醫(yī)學(xué)圖像進(jìn)行分割且效果明顯。

遺傳算法； 圖像分割； 閾值

0 引 言

在圖像分割領(lǐng)域，由于醫(yī)學(xué)圖像所反映的是人體復(fù)雜的組織結(jié)構(gòu)，因此受到越來(lái)越多人的關(guān)注。在醫(yī)學(xué)影像器材實(shí)際的操作中，許多因素會(huì)影響到器材的成像效果，諸如：雜波干擾、電磁場(chǎng)干擾、局部效應(yīng)干擾等，使獲得的CT圖像可能存在關(guān)鍵部位模糊，成像不均勻的缺點(diǎn)[1]。所以，在用計(jì)算機(jī)技術(shù)處理醫(yī)學(xué)圖像時(shí)，很重要的就是突出醫(yī)學(xué)圖像中人們所感興趣的部分，濾除圖像的噪聲，從而為進(jìn)一步的醫(yī)學(xué)分析奠定良好的基礎(chǔ)。

Otsu法(即最大類間方差法)因計(jì)算簡(jiǎn)單、自適應(yīng)性強(qiáng)而成為使用最廣泛的圖像閥值選取方法之一[2]。這種方法主要是在圖像的灰度直方圖基礎(chǔ)上，動(dòng)態(tài)地選取圖像最佳閥值，達(dá)到目標(biāo)與背景之間的方差最大目的。但Otsu方法是通過(guò)窮盡的搜索方法得到最佳閾值，不但圖像分割效果一般，而且運(yùn)算時(shí)間長(zhǎng)。

遺傳算法(GA)具有很好的魯棒性、并行性和自適應(yīng)性[3]，非常適合在全局高速并行的搜索最優(yōu)解，克服了Otsu方法窮盡搜索的不足。本文在GA與Otsu方法結(jié)合的前提下，提出了一種動(dòng)態(tài)確定交叉概率、變異概率和精英選擇策略的改進(jìn)型GA，它可以有效地解決GA易早熟、收斂速度慢等缺點(diǎn)。將該算法運(yùn)用到醫(yī)學(xué)圖像分割上，實(shí)驗(yàn)結(jié)果表明：該算法可自適應(yīng)調(diào)節(jié)變換參數(shù)，圖像分割效果明顯，最佳分割閾值范圍穩(wěn)定。

1 基于GA的Otsu算法

1.1 Otsu算法[4～6]

(1)

假設(shè)圖像的灰度被單個(gè)閾值T分為兩類，c0和c1，得到它們的發(fā)生概率和均值分別為

(2)

(3)

則類間方差σ2為

σ2=w0(u-u0)2+w1(u1-u)2=w0w1(u0-u1)2

(4)

為了使類間方差最大，需要采用窮盡的方法得到最佳閾值T。

1.2 基于GA的Otsu算法

由于最佳閾值是通過(guò)遍歷的方法搜索得到的，因此，在圖像分割中，將標(biāo)準(zhǔn)的GA應(yīng)用在Otsu方法中來(lái)尋找全局最佳閾值，其基本實(shí)現(xiàn)步驟如下：1)產(chǎn)生初始種群，確定種群大小，交叉概率、變異概率、進(jìn)化代數(shù)。2)采用式(4)為適應(yīng)度函數(shù)，并計(jì)算每個(gè)個(gè)體適應(yīng)度大小。3)在個(gè)體選擇上采用輪盤賭策略。4)采用固定的交叉概率和變異概率，對(duì)個(gè)體進(jìn)行先交叉后變異操作，產(chǎn)生新的個(gè)體。5)種群進(jìn)行更新。6)判斷是否滿足終止的最大進(jìn)化代數(shù)，若滿足代數(shù)，則輸出最大適應(yīng)度值和最佳閾值；若不滿足條件，則跳轉(zhuǎn)到步驟(2)。

由于GA中所存在的不足，限制了基于GA的Otsu算法，因此，只是簡(jiǎn)單地利用標(biāo)準(zhǔn)GA運(yùn)用到醫(yī)學(xué)圖像分割中，很可能無(wú)法達(dá)到圖像預(yù)期的分割效果。為此，需要用基于改進(jìn)GA的Otsu算法來(lái)進(jìn)行醫(yī)學(xué)圖像分割。

2 基于改進(jìn)GA的Otsu算法

2.1 精英選擇策略

在標(biāo)準(zhǔn)的GA中，單純的采用輪盤賭策略進(jìn)行種群個(gè)體的選擇，這種選擇策略又稱為比例選擇策略，它是指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比[7]。該策略可能會(huì)在交叉和變異產(chǎn)生新的一代時(shí)，導(dǎo)致某個(gè)中間步驟中得到的最優(yōu)解丟失，從而失去了上一代群體中的很多信息。本文根據(jù)種群進(jìn)化代數(shù)的不同，提出了自適應(yīng)的精英選擇策略。

當(dāng)gen<α1×maxgen時(shí)，當(dāng)代最大適應(yīng)度值個(gè)體p取代新一代最小適應(yīng)度值個(gè)體q，其中，gen為當(dāng)前進(jìn)化代數(shù)，maxgen為最大進(jìn)化代數(shù)，α1為設(shè)定的小于1的比例系數(shù)。

當(dāng)gen<α2×maxgen時(shí)，設(shè)當(dāng)代種群中存在有k個(gè)較大適應(yīng)度值的個(gè)體，選擇前l(fā)個(gè)較優(yōu)個(gè)體來(lái)取代新一代種群中較小適應(yīng)度值的個(gè)體，則

(5)

式中 popsize為種群的大小，α2，μ，η均為設(shè)定的小于等于1的比例系數(shù)。

在本文中，根據(jù)實(shí)際情況，選取maxgen=120，popsize=10，α1=0.3，α2=1，μ=0.5，η=0.4。

2.2 自適應(yīng)交叉概率

在標(biāo)準(zhǔn)GA中，隨著新個(gè)體的繁殖，種群的遺傳模式可能會(huì)被固定的交叉概率所破壞。交叉算子不僅對(duì)種群產(chǎn)生新個(gè)體至關(guān)重要，且在進(jìn)化過(guò)程中也有全局搜索作用。因此，本文提出了一種隨著進(jìn)化代數(shù)而自適應(yīng)產(chǎn)生變化的交叉概率

(6)

式中 k1為預(yù)先設(shè)定的比例系數(shù)，λ為常數(shù)，即交叉概率的收斂極限，gen為當(dāng)前進(jìn)化代數(shù)，α為交叉概率的變化曲率。

在本文中，依次確定數(shù)值取值分別為：k1=1，α=0.055，λ=0.3，依照上述參數(shù)控制pc的范圍為0.78～0.3范圍之間。

2.3 自適應(yīng)變異概率

變異算子可以增加新的搜索空間，擴(kuò)大算法的搜索范圍[8]。種群的多樣性主要靠變異算子來(lái)維持，它可以有效地防止種群陷入局部最優(yōu)解現(xiàn)象的發(fā)生。本文根據(jù)個(gè)體不同適應(yīng)度值，自適應(yīng)進(jìn)行調(diào)節(jié)變異概率，當(dāng)適應(yīng)度低于平均適應(yīng)度時(shí)，采用較大的變異概率，當(dāng)適應(yīng)度高于平均適應(yīng)度時(shí)，可以采用較小變異概率，保護(hù)種群較優(yōu)個(gè)體,則自適應(yīng)變異概率為

(7)

式中 最大變異概率Pmax=0.08，比例系數(shù)k2=0.06，f為要變異個(gè)體適應(yīng)度，favg為當(dāng)代適應(yīng)度平均值，fmax為當(dāng)代適應(yīng)度最大值，依照上述參數(shù)控制變異概率在0.08～0.02范圍內(nèi)。

同時(shí)，本文采用了多位變異法種群個(gè)體的編譯位數(shù)M由下式?jīng)Q定[9]

(8)

式中fmin為當(dāng)代適應(yīng)度最小值。

3 仿真研究

3.1 本文算法的性能分析

本文在Matlab R2012a軟件平臺(tái)上進(jìn)行仿真，采用了一幅600×398大小的肺部結(jié)構(gòu)圖，目標(biāo)為肺部結(jié)節(jié)。將肺部結(jié)節(jié)圖與基于本文改進(jìn)GA的Otsu算法處理的肺部結(jié)節(jié)圖進(jìn)行對(duì)照，如圖1。

由圖1可以看出：左半部分肺部結(jié)節(jié)明顯嚴(yán)重，右半部分肺部結(jié)節(jié)病情好于左半部分。該算法可以對(duì)原圖像進(jìn)行有效分割，使得目標(biāo)與背景得到很好分離，不但濾除了噪聲干擾，且左右肺部的結(jié)節(jié)點(diǎn)得到明顯的圖像增強(qiáng)，有利于后續(xù)的醫(yī)療診斷。

圖1 肺部分割前后效果圖Fig 1 Segmentation effect comparison of lung

3.2 參數(shù)性能分析

由于GA存在隨機(jī)性，本文以實(shí)驗(yàn)過(guò)程中隨機(jī)的一次進(jìn)化為例進(jìn)行分析，主要針對(duì)改進(jìn)GA中每代的最佳適應(yīng)度值進(jìn)化曲線和每代的最佳閾值進(jìn)化曲線進(jìn)行分析討論。

從圖2中可以看出:最佳適應(yīng)度值逐步增大，最終在20代左右時(shí)得到穩(wěn)定的最佳適應(yīng)度值，收斂速度快。圖2與圖3各代相統(tǒng)一，經(jīng)過(guò)改進(jìn)遺傳算法的閾值尋優(yōu)后，最后穩(wěn)定在139上。

3.3 算法比對(duì)分析

結(jié)合上述肺部圖像，以圖像閾值和算法運(yùn)行時(shí)間作為評(píng)價(jià)標(biāo)準(zhǔn)，分別采用Otsu圖像分割法、基本GA和改進(jìn)的GA進(jìn)行多次實(shí)驗(yàn)，對(duì)每種算法各選其中5次實(shí)驗(yàn)結(jié)果進(jìn)行比對(duì)，如表1所示。

圖2 最佳適應(yīng)度值進(jìn)化曲線Fig 2 Evolution curve of the optimal fitness

圖3 最佳閾值進(jìn)化曲線Fig 3 Evolution curve of the optimal threshold

表1 各算法的圖像閾值與時(shí)間

通過(guò)表1，可以分析出改進(jìn)的遺傳算法在運(yùn)行時(shí)間上比Otsu圖像分割法縮短了16 ms左右，比基本的GA縮短了3 ms左右。改進(jìn)的GA求取的閾值范圍在2個(gè)像素之間波動(dòng)，而基本的遺傳算法在9個(gè)像素之間波動(dòng)。

因此，通過(guò)反復(fù)的實(shí)驗(yàn)可以證明：改進(jìn)的GA不但最佳分割閾值的穩(wěn)定性明顯優(yōu)于基本的遺傳算法，且加快了算法運(yùn)行速度。

4 結(jié)束語(yǔ)

1)根據(jù)種群個(gè)體進(jìn)化的代數(shù)，動(dòng)態(tài)地調(diào)整精英選擇策略和自適應(yīng)的變化交叉概率，加快了種群收斂速度，保證了優(yōu)秀個(gè)體順利進(jìn)入下一代，增加了全局的搜索范圍。

2)根據(jù)種群個(gè)體適應(yīng)度的大小，動(dòng)態(tài)地調(diào)整變異概率，擴(kuò)大了算法新的搜索空間，為種群的多樣性提供了保證，避免了遺傳算法過(guò)早陷入局部最優(yōu)解的現(xiàn)象。

將該算法運(yùn)用到醫(yī)學(xué)圖像的處理中，可以達(dá)到預(yù)期醫(yī)學(xué)圖像增強(qiáng)的效果，明顯地提高了圖像的對(duì)比度，穩(wěn)定的算法處理效果明顯優(yōu)于基本的處理算法，也為圖像后續(xù)的醫(yī)學(xué)診斷研究提供了寶貴的素材。

[1] 康一鶴,李文俊.改進(jìn)型遺傳算法在醫(yī)學(xué)圖像分割中的應(yīng)用[J].信息通信,2015(4):2-3.

[2] 付忠良.圖像閾值選取方法—Otsu方法的推廣[J].計(jì)算機(jī)應(yīng)用,2000,20(5):37-39.

[3] 田 瑩，苑瑋琦.遺傳算法在圖像處理中的應(yīng)用[J].中國(guó)圖像圖形學(xué)報(bào)，2007,12(3)：390-391.

[4] 郭 臻，陳遠(yuǎn)知.圖像閾值分割算法研究[J].中國(guó)傳媒大學(xué)學(xué)報(bào)，2008,15(2)：77-82.

[5] 周德龍，潘 泉，張鴻才.最大熵閾值處理算法[J].軟件學(xué)報(bào)，2001,12(9)：1-4.

[6] 陳冬嵐，劉金南，余玲玲.幾種圖像分割閾值選取方法的比較與研究[J].機(jī)械制造與自動(dòng)化，2003(1)：77-80.

[7] 江 建.精英自適應(yīng)混合遺傳算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(27):34-36.

[8] 聶 轟.改進(jìn)的遺傳算法在圖像分割中的應(yīng)用[J].湘南學(xué)院學(xué)報(bào),2010,31(2):65-68.

[9] 劉 翔，董 昱.改進(jìn)的自適應(yīng)免疫遺傳算法在圖像增強(qiáng)中的應(yīng)用[J].傳感器與微系統(tǒng),2015,34(6):156-160.

梁文宇(1992 -)，男，山東威海人，碩士研究生，研究方向?yàn)槿斯ぶ悄?、圖像處理、Web開(kāi)發(fā)。

Application of improved genetic algorithm in medical image

LIANG Wen-yu, GONG Tao, WU Yu-xiang

(College of Information Technology & Engineering,Donghua University,Shanghai 201600,China)

Aiming at problem of low speed of convergence,early mature of standard genetic algorithm(GA) occur in optimizing Otsu method to search for threshold of image,an improved GA for image segmentation is proposed.According to different evolution generation and individual fitness,this improved GA can adjust strategies of elite selection and genetic operator dynamically,so it not only can speed up the convergence speed,but also can get image segmentation threshold with stable range and keep diversity of population.This algorithm is used in medical image segmentation, and experimental results show that the algorithm can be used for segmentation of medical image and effect is obvious.

genetic algorithm(GA); image segmentation; threshold

2015—11—20

10.13873/J.1000—9787(2016)10—0152—03

TP 391

A

1000—9787(2016)10—0152—03

張長(zhǎng)勝，通訊作者，E—mail:ttztty@sina.com。