基于自適應量子遺傳算法的圖像閾值分割

關學忠，尹廷武，張新城，王文峰

（東北石油大學黑龍江大慶163318）

?

基于自適應量子遺傳算法的圖像閾值分割

關學忠，尹廷武，張新城，王文峰

（東北石油大學黑龍江大慶163318）

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

關鍵詞：圖像分割；二維Otsu；自適應量子遺傳算法；閾值尋優

圖像分割是圖像預處理中的關鍵步驟，是更高層次圖像識別和理解的基礎，是圖像處理中不可忽視的存在。閾值分割是圖像分割中常用的方法，因為它簡單并且有效，在計算機視覺以及圖像識別等方面被廣泛使用，人們熟知的閾值分割方法有最大熵法（KSW）［1］、最大類間差法（Otsu）［2］和區域生長法［3］等。

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

考慮到量子遺傳算法在函數尋優方面的快速性，本文將傳統的二維Otsu法與改進的自適應量子遺傳算法結合起來，并將其運用到圖像閾值分割中。本文所采用改進的自適應量子遺傳算法，該算法將量子比特用于染色體的編碼，通過量子旋轉門實現染色體向最大適應度方向進化，利用Hadamard門實現染色體種群的變異操作，能夠根據種群進化代數自適應動態地調整量子旋轉角步長，能夠快速有效的得到最佳分割閾值，取得了較好的分割效果。

1　自適應量子遺傳算法

1.1量子比特編碼

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

量子比特位可以同時包含0和1的二進制信息，那么長度為m的量子染色體可以表示2m個不同的形態，在量子遺傳算法中，種群Q（t）第t代中一個長度為m位的量子比特個體可表示為：

式中：n為染色體種群大小，j為當前進化代數。

1.2自適應量子旋轉門

用于染色體進化操作的量子旋轉門為：

其更新過程如下：

由上式可知，量子旋轉門只是改變了量子比特的相位而沒有改變量子位的長度，能夠使染色體向適應度更高的個體進化。△θi為旋轉角，符號和大小一般由設計好的調整策略表［7］確定，一般取（0.005π，0.1π），本文采用量子旋轉門動態自適應調整策略［8］。公式如下：

在公式（4）中，α1和β1為當前解中某個量子位的概率幅，α0和β0為當前最優解中對應量子位的概率幅。當Ai=0時，旋轉方向正負均可以；當Ai≠0時，轉角方向為-sgn（Ai）。△θ用來確定轉角的大小，采用公式如下：

其中，gen為當前進化代數，maxgen為全局最大進化代數。初始進化時，△θ較大，能夠增大算法全局搜索范圍，更易獲得全局最優解，避免算法早熟，隨著種群的不斷進化，△θ逐漸減小，能夠實現在局部區域的精確搜索。

1.3Hadamard門變異

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

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

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

2.1二維0tsu法

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

圖1　二維灰度直方圖

A和C兩個區域的概率分別為：

那么兩個區域對應的均值矢量分別為：

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

目標和背景的類間離散度被定義為：

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

由以上公式可以看出二維Otsu的計算量很大，為了實際應用的需要，結合本文提出的自適應量子遺傳算法實現最優閾值的求取，從而實現減少計算量、提高計算效率的目的。

2.2圖像分割算法步驟

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

Step1種群Q（t）初始化。相對于一維Otsu法中染色體的位數為8位，我們在二維Otsu中采用16個量子比特位編碼染色體種群。

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

Step3根據適應度大小評估各個解的優劣，保留適應度最高的個體；

Step4判斷是否滿足結束條件，如果滿足則按照最佳適應度即最佳閾值對灰度圖像進行分割，否則繼續計算。

Step5分別利用量子旋轉門和Hadamard門對染色體種群實施進化和變異操作，得到新的種群Q（t+1）。

Step6對新種群Q（t+1）進行解碼操作，得到對應的確定解P（t+1）；

Step7根據適應度大小評估各個解的優劣，保留適應度最高的個體；

Step8如果種群最優個體連續多代沒有變化時，對種群進行災變操作，將迭代次數t加1，返回步驟4。

3　實驗結果及分析

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

圖2　Lena分割效果比較

圖3　cjrcujt分割效果比較

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

圖4　cjrcujt分割效果比較

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

4　結論

二維直方圖Otsu法求取最佳分割閾值的問題，實際上就是函數尋優的問題，雖然對圖像的分割較為準確性，抗噪性也較強，但存在計算量大，花費時間過長的缺點，本文在此問題上引入了自適應量子遺傳算法來用于圖像分割的最佳閾值求取，通過仿真實驗表明，本文方法能夠大大縮短分割時間，同時相比于一維直方圖Otsu法，本文方法分割更準確，而且抗噪聲能力更強。

表1　時間性能比較

參考文獻：

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

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

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

［4］郝穎明，朱楓.2維Otsu自適應閾值的快速算法［J］.中國圖像圖形學報，2005，10（4）：485-488.

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

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

［6］李士勇，李盼池.量子計算與量子優化算法［M］.哈爾濱：哈爾濱工業大學出版社，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］于艾青，劉濤.基于自適應量子遺傳算法的電力系統機組組合問題［J］.上海電力學院學報，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

中圖分類號：TN01

文獻標識碼：A

文章編號：1674-6236（2016）07-0168-03

收稿日期：2015-05-26稿件編號：201505224

作者簡介：關學忠（1960—），男，吉林蛟河人，博士，教授。研究方向：工業自動化、嵌入式系統。