基于自適應(yīng)量子遺傳算法的圖像閾值分割

關(guān)學(xué)忠，尹廷武，張新城，王文峰

（東北石油大學(xué)黑龍江大慶163318）

?

基于自適應(yīng)量子遺傳算法的圖像閾值分割

關(guān)學(xué)忠，尹廷武，張新城，王文峰

（東北石油大學(xué)黑龍江大慶163318）

摘要：一維最大類間差法（Otsu）是一種廣泛使用的圖像閾值分割方法，雖然處理速度快，但是沒有考慮到像素的領(lǐng)域空間信息，當(dāng)圖像受到噪聲干擾等因素影響時(shí)，難以獲得滿意的分割效果，鑒于此，本文提出了一種基于自適應(yīng)量子遺傳算法和二維Otsu的分割方法。二維Otsu法兼顧了圖像的灰度信息以及鄰域信息，具有抗干擾以及分割精度高的優(yōu)點(diǎn)，但存在計(jì)算量大、實(shí)時(shí)性差的缺點(diǎn)；利用自適應(yīng)量子遺傳算法則能迅速找到最佳分割閾值，提高運(yùn)算速度。仿真實(shí)驗(yàn)表明，本文方法減少了閾值尋優(yōu)的時(shí)間，提高了分割精度，同時(shí)兼具較強(qiáng)的抗干擾能力。

關(guān)鍵詞：圖像分割；二維Otsu；自適應(yīng)量子遺傳算法；閾值尋優(yōu)

圖像分割是圖像預(yù)處理中的關(guān)鍵步驟，是更高層次圖像識(shí)別和理解的基礎(chǔ)，是圖像處理中不可忽視的存在。閾值分割是圖像分割中常用的方法，因?yàn)樗?jiǎn)單并且有效，在計(jì)算機(jī)視覺以及圖像識(shí)別等方面被廣泛使用，人們熟知的閾值分割方法有最大熵法（KSW）［1］、最大類間差法（Otsu）［2］和區(qū)域生長(zhǎng)法［3］等。

Otsu法基于圖像的一維直方圖灰度信息，以目標(biāo)和背景的類間方差最大作為閾值選取準(zhǔn)則，一方面由于圖像的灰度直方圖不一定出現(xiàn)明顯的峰和谷，另一方面，圖片受到噪聲干擾、光照不均勻等不利因素影響時(shí)，致使分割效果不佳。劉健莊等人將Otsu法推廣到適合二維直方圖的情況，考慮了像素的鄰域灰度信息，使得分割效果有了較大的改善，但同時(shí)所帶來的計(jì)算量也是驚人的。為了克服此缺點(diǎn)，許多學(xué)者提出了多種基于二維Otsu的快速算法［4-5］。

考慮到量子遺傳算法在函數(shù)尋優(yōu)方面的快速性，本文將傳統(tǒng)的二維Otsu法與改進(jìn)的自適應(yīng)量子遺傳算法結(jié)合起來，并將其運(yùn)用到圖像閾值分割中。本文所采用改進(jìn)的自適應(yīng)量子遺傳算法，該算法將量子比特用于染色體的編碼，通過量子旋轉(zhuǎn)門實(shí)現(xiàn)染色體向最大適應(yīng)度方向進(jìn)化，利用Hadamard門實(shí)現(xiàn)染色體種群的變異操作，能夠根據(jù)種群進(jìn)化代數(shù)自適應(yīng)動(dòng)態(tài)地調(diào)整量子旋轉(zhuǎn)角步長(zhǎng)，能夠快速有效的得到最佳分割閾值，取得了較好的分割效果。

1　自適應(yīng)量子遺傳算法

1.1量子比特編碼

量子遺傳算法的染色體采用量子比特［6］表達(dá)和存儲(chǔ)一個(gè)基因。該量子位可以是“0”態(tài)或“1”態(tài)，還可以是任意疊加態(tài)，從而染色體基因所表達(dá)的信息包含了所有可能信息，不再是單一信息，相比于傳統(tǒng)的遺傳算法，量子遺傳算法具有更好的種群多樣性特征。量子比特編碼同時(shí)具有較好的收斂性，隨著|α|2或|β|2趨于0或1，量子染色體將收斂到某個(gè)單一狀態(tài)，并且滿足|α|2+ |β|2=1。

量子比特位可以同時(shí)包含0和1的二進(jìn)制信息，那么長(zhǎng)度為m的量子染色體可以表示2m個(gè)不同的形態(tài)，在量子遺傳算法中，種群Q（t）第t代中一個(gè)長(zhǎng)度為m位的量子比特個(gè)體可表示為：

式中：n為染色體種群大小，j為當(dāng)前進(jìn)化代數(shù)。

1.2自適應(yīng)量子旋轉(zhuǎn)門

用于染色體進(jìn)化操作的量子旋轉(zhuǎn)門為：

其更新過程如下：

由上式可知，量子旋轉(zhuǎn)門只是改變了量子比特的相位而沒有改變量子位的長(zhǎng)度，能夠使染色體向適應(yīng)度更高的個(gè)體進(jìn)化?！鳓萯為旋轉(zhuǎn)角，符號(hào)和大小一般由設(shè)計(jì)好的調(diào)整策略表［7］確定，一般取（0.005π，0.1π），本文采用量子旋轉(zhuǎn)門動(dòng)態(tài)自適應(yīng)調(diào)整策略［8］。公式如下：

在公式（4）中，α1和β1為當(dāng)前解中某個(gè)量子位的概率幅，α0和β0為當(dāng)前最優(yōu)解中對(duì)應(yīng)量子位的概率幅。當(dāng)Ai=0時(shí)，旋轉(zhuǎn)方向正負(fù)均可以；當(dāng)Ai≠0時(shí)，轉(zhuǎn)角方向?yàn)?sgn（Ai）。△θ用來確定轉(zhuǎn)角的大小，采用公式如下：

其中，gen為當(dāng)前進(jìn)化代數(shù)，maxgen為全局最大進(jìn)化代數(shù)。初始進(jìn)化時(shí)，△θ較大，能夠增大算法全局搜索范圍，更易獲得全局最優(yōu)解，避免算法早熟，隨著種群的不斷進(jìn)化，△θ逐漸減小，能夠?qū)崿F(xiàn)在局部區(qū)域的精確搜索。

1.3Hadamard門變異

為了提高染色體種群的多樣性，本文采用Hadamard門對(duì)其進(jìn)行變異操作，變異過程可描述為：

由公式（6）可以看出，對(duì)第i條染色體的第j個(gè)量子位施加Hadamard門變異，能夠使該量子位的幅角逆時(shí)針方向旋轉(zhuǎn)-2θij）度，從而增加了染色體種群的多樣性。如果種群經(jīng)過多代以后最優(yōu)個(gè)體沒有任何變化，就對(duì)群體進(jìn)行災(zāi)變操作。

2　基于自適應(yīng)量子遺傳算法和二維0tsu的圖像分割

2.1二維0tsu法

二維Otsu法是在二維灰度空間尋找最佳灰度閾值來分割圖像。二維灰度直方圖的平面示意圖如圖1所示，i表示像素灰度，j表示像素鄰域灰度，閾值向量（s，t）將二維灰度直方圖分成4個(gè)區(qū)域，區(qū)域A和C代表目標(biāo)和背景，區(qū)域B和D表示邊緣點(diǎn)及噪聲，邊緣點(diǎn)和噪聲點(diǎn)的概率值很小，可以忽略不計(jì)，即p（B）=p（D）=0。

圖1　二維灰度直方圖

A和C兩個(gè)區(qū)域的概率分別為：

那么兩個(gè)區(qū)域?qū)?yīng)的均值矢量分別為：

二維直方圖總的均值矢量為：

目標(biāo)和背景的類間離散度被定義為：

最佳閾值向量（s*，t*）滿足下式：

由以上公式可以看出二維Otsu的計(jì)算量很大，為了實(shí)際應(yīng)用的需要，結(jié)合本文提出的自適應(yīng)量子遺傳算法實(shí)現(xiàn)最優(yōu)閾值的求取，從而實(shí)現(xiàn)減少計(jì)算量、提高計(jì)算效率的目的。

2.2圖像分割算法步驟

自適應(yīng)量子遺傳算法能夠在二維灰度直方圖解空間中快速查找最佳閾值向量，使得目標(biāo)與背景的灰度差異最大，其閾值尋優(yōu)步驟如下：

Step1種群Q（t）初始化。相對(duì)于一維Otsu法中染色體的位數(shù)為8位，我們?cè)诙SOtsu中采用16個(gè)量子比特位編碼染色體種群。

Step2對(duì)染色體種群Q（t）進(jìn)行解碼操作，得到解空間中的某一確定解P（t）；

Step3根據(jù)適應(yīng)度大小評(píng)估各個(gè)解的優(yōu)劣，保留適應(yīng)度最高的個(gè)體；

Step4判斷是否滿足結(jié)束條件，如果滿足則按照最佳適應(yīng)度即最佳閾值對(duì)灰度圖像進(jìn)行分割，否則繼續(xù)計(jì)算。

Step5分別利用量子旋轉(zhuǎn)門和Hadamard門對(duì)染色體種群實(shí)施進(jìn)化和變異操作，得到新的種群Q（t+1）。

Step6對(duì)新種群Q（t+1）進(jìn)行解碼操作，得到對(duì)應(yīng)的確定解P（t+1）；

Step7根據(jù)適應(yīng)度大小評(píng)估各個(gè)解的優(yōu)劣，保留適應(yīng)度最高的個(gè)體；

Step8如果種群最優(yōu)個(gè)體連續(xù)多代沒有變化時(shí)，對(duì)種群進(jìn)行災(zāi)變操作，將迭代次數(shù)t加1，返回步驟4。

3　實(shí)驗(yàn)結(jié)果及分析

圖像仿真實(shí)驗(yàn)是在MATLAB7.0環(huán)境下進(jìn)行的。為了驗(yàn)證本文閾值分割方法的準(zhǔn)確性，選取MATLAB仿真軟件圖庫中Lena和cjrcujt兩幅圖像，在同等條件下，分別采用基于遺傳算法的一維直方圖Otsu分割方法和本文方法對(duì)兩幅圖像進(jìn)行分割實(shí)驗(yàn)，分割結(jié)果如圖2和圖3所示。比較圖2（b）、（c）兩幅圖的分割效果，可以直觀的看到本文算法分割后的圖片人物細(xì)節(jié)更加清晰、細(xì)膩，另外由圖3（b）可以看到管線粘連在一起，看不出原來的樣子，而圖3（c）雖然有些管道粘連在一起，但是總體上實(shí)現(xiàn)對(duì)管線的分割，分割效果更好。

圖2　Lena分割效果比較

圖3　cjrcujt分割效果比較

為了驗(yàn)證本文分割方法的抗噪聲能力，選取了一張含噪聲的rjce圖像進(jìn)行試驗(yàn)，分別用分別采用基于遺傳算法的一維直方圖Otsu分割方法和本文方法對(duì)該圖像進(jìn)行分割實(shí)驗(yàn)，分割效果比較如圖4所示。由圖4（b）可以看到圖像上有許多的噪聲點(diǎn)，抗噪能力差，嚴(yán)重影響了分割效果，而圖4（c）分割效果較好，噪聲點(diǎn)很少，具有較強(qiáng)的抗噪聲能力，分割效果較好。

圖4　cjrcujt分割效果比較

為了驗(yàn)證本文算法的快速性，我們分別采用二維Otsu窮舉法和本文算法對(duì)上述3幅圖像進(jìn)行了仿真實(shí)驗(yàn)，時(shí)間性能比較如表1所示。由表可知，本文方法計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)少于傳統(tǒng)二維Otsu法，降低了計(jì)算量，提高了計(jì)算效率。

4　結(jié)論

二維直方圖Otsu法求取最佳分割閾值的問題，實(shí)際上就是函數(shù)尋優(yōu)的問題，雖然對(duì)圖像的分割較為準(zhǔn)確性，抗噪性也較強(qiáng)，但存在計(jì)算量大，花費(fèi)時(shí)間過長(zhǎng)的缺點(diǎn)，本文在此問題上引入了自適應(yīng)量子遺傳算法來用于圖像分割的最佳閾值求取，通過仿真實(shí)驗(yàn)表明，本文方法能夠大大縮短分割時(shí)間，同時(shí)相比于一維直方圖Otsu法，本文方法分割更準(zhǔn)確，而且抗噪聲能力更強(qiáng)。

表1　時(shí)間性能比較

參考文獻(xiàn)：

［1］范九倫，雷博.灰度圖像的二維交叉熵直線型閾值分割法［J］.電子學(xué)報(bào)，2009，37（3）：476- 480.

［2］李惠光，姚磊，石磊.改進(jìn)的Otsu理論在圖像閾值選取中的應(yīng)用［J］.計(jì)算機(jī)仿真，2007，24（04）：217-219.

［3］夏晶，孫繼銀.基于區(qū)域生長(zhǎng)的前視紅外圖像分割方法［J］.激光與紅外，2011，41（1）：108-111.

［4］郝穎明，朱楓.2維Otsu自適應(yīng)閾值的快速算法［J］.中國(guó)圖像圖形學(xué)報(bào)，2005，10（4）：485-488.

［5］唐英干，劉東，關(guān)新平.基于粒子群和二維Otsu方法的快速

圖像分割［J］.控制與決策，2007，22（2）：203-205.

［6］李士勇，李盼池.量子計(jì)算與量子優(yōu)化算法［M］.哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2009：69-95.

［7］NARAYANAN A，MOORE M. Quantum -jnspjred genetjc a1gorjthms［C］.//Proceedjngs of IEEE Internatjona1 Conference on Evo1utjonary Computatjon，Nagoya，Japan，1996：61-66.

［8］于艾青，劉濤.基于自適應(yīng)量子遺傳算法的電力系統(tǒng)機(jī)組組合問題［J］.上海電力學(xué)院學(xué)報(bào)，2015，1（31）：25-28.

Image threshold segmentatlon based on AQGA

GUAN Xue-zhong，YIN Tjng-wu，ZHANG Xjn-cheng，WANG Wen-feng （Northeast Petroleum University，Daqing 163318，Chjna）

Abstract:One-djmensjona1 Otsu method js a wjde1y used jmage thresho1d method，a1though the processjng speed js fast，but jt do not take spatja1 jnformatjon of the pjxe1 jnto account，whj1e the jmage js affected by nojse and other factors，jt js djffjcu1t to obtajn satjsfactory segmentatjon resu1ts，jn vjew of thjs，a segmentatjon method based on adaptjve quantum genetjc a1gorjthm and 2D Otsu js proposed jn thjs paper. The 2D Otsu method consjders not on1y the gray 1eve1 jnformatjon but a1so the nejghborhood jnformatjon，jt has the advantages of antj-jnterference and hjgh segmentatjon accuracy，but the djsadvantages are computatjona11y jntensjve and poor rea1-tjme performance；by usjng adaptjve quantum genetjc a1gorjthm，we can qujck1y fjnd the optjma1 segmentatjon thresho1d，jmprove processjng speed. Sjmu1atjon resu1ts show that thjs method reduces the tjme of thresho1d optjmjzatjon and jmprove the accuracy of segmentatjon，jt a1so has re1atjve1y strong antj-jnterference abj1jty at the same tjme.

Key words:jmage segmentatjon；2D Otsu；adaptjve quantum genetjc a1gorjthm；thresho1d optjmjzatjon

中圖分類號(hào)：TN01

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1674-6236（2016）07-0168-03

收稿日期：2015-05-26稿件編號(hào)：201505224

作者簡(jiǎn)介：關(guān)學(xué)忠（1960—），男，吉林蛟河人，博士，教授。研究方向：工業(yè)自動(dòng)化、嵌入式系統(tǒng)。