基于改進(jìn)二維熵-量子遺傳算法的圖像多閾值變化檢測(cè)方法*

仝 彤，慕曉冬，張 力

（火箭軍工程大學(xué)，西安 710025）

0 引言

變化檢測(cè)是指將同一地區(qū)、不同時(shí)期獲得的兩幅或多幅圖像進(jìn)行分析處理以提取所需的地物變化信息的技術(shù)。圖像變化檢測(cè)在資源與環(huán)境監(jiān)測(cè)、輔助測(cè)繪、自然災(zāi)害的監(jiān)測(cè)評(píng)估方面以及在軍事領(lǐng)域的打擊效果評(píng)估方面都有著廣泛的應(yīng)用[1]。合成孔徑雷達(dá)（SAR）利用主動(dòng)雷達(dá)波成像，受光照和天氣情況的影響較小，可對(duì)地表進(jìn)行穩(wěn)定的、周期性的觀測(cè)，因此，常常用于變化檢測(cè)[1-4]。

針對(duì)中低分辨率SAR影像，目前常用的方法是基于差異圖閾值選取的直接比較法。直接比較法的核心是差異圖的生成和變化閾值的選取，其中難點(diǎn)是如何高效自動(dòng)地確定變化閾值。目前，一般采用閾值分割的方法確定變化閾值，得到變化區(qū)域與未變化區(qū)域。經(jīng)典的閾值分割方法主要有最小誤差法、最大類間方差法（OTSU）和最大熵法[5]。基于最大熵的閾值分割方法是一種結(jié)合了信息論的圖像分割方法，但是對(duì)于噪點(diǎn)比較多的圖像中，該方法分割效果較差。二維最大熵分割方法同時(shí)統(tǒng)計(jì)了像素自身的灰度信息和像素周圍鄰域信息，與一維的最大熵閾值分割方法相比，該方法對(duì)噪聲的魯棒性較強(qiáng)，但是存在計(jì)算量大的缺點(diǎn)[6]。針對(duì)這個(gè)問(wèn)題，國(guó)內(nèi)外學(xué)者研究出了許多針對(duì)減小其計(jì)算復(fù)雜度的搜索算法[7-12]。大多數(shù)研究只考慮了單閾值分割的情況，當(dāng)圖像直方圖呈現(xiàn)多峰形狀時(shí)，單閾值分割就不能滿足分割要求，或閾值搜索時(shí)間長(zhǎng)。因此，本文研究展開(kāi)了二維最大熵多閾值分割的研究，目標(biāo)是提升分割精度和搜索時(shí)間性能并將其成功用于變化檢測(cè)問(wèn)題中。

本文提出了一種基于二維熵-量子遺傳算法的圖像多閾值變化檢測(cè)方法。其優(yōu)勢(shì)體現(xiàn)在：1）研究了二維閾值量子染色體編碼方法，解決了傳統(tǒng)遺傳算法優(yōu)化二維最大指數(shù)熵閾值過(guò)程中速度慢、多樣性小的缺點(diǎn)；2）提出了一種半隨機(jī)策略產(chǎn)生閾值解的方法，加快尋優(yōu)速度；3）改進(jìn)了量子門旋轉(zhuǎn)角度方式，提出了自適應(yīng)旋轉(zhuǎn)角度的方法，提高了算法的魯棒性和收斂速度。

1 二維指數(shù)熵圖像多閾值分割

指數(shù)熵克服了傳統(tǒng)對(duì)數(shù)熵的缺點(diǎn)，提高了計(jì)算速度并減少了信息的損失。由于一維的指數(shù)信息熵基于圖像原始分布直方圖，僅考慮像素自身灰度而未考慮空間信息，因此，提出了二維指數(shù)熵。二維指數(shù)熵的分割方法基于圖像的二維直方圖，如圖1所示。設(shè)圖像I的大小為M×N，則圖像的二維直方圖計(jì)算式為：

其中，nij指的是圖像中灰度值為i而鄰域灰度均值為j的像素的個(gè)數(shù)。

圖1 二維直方圖

圖2 二維直方圖俯視平面

圖2為二維直方圖的俯視圖，橫軸代表i，縱軸代表j，設(shè)分割的閾值對(duì)數(shù)C=4，在圖中閾值表示為，整個(gè)區(qū)域被直線i=j分割開(kāi)來(lái)，離該直線距離近的點(diǎn)（陰影部分內(nèi)的點(diǎn)）表示其灰度值和鄰域灰度均值比較接近，應(yīng)屬于圖像的目標(biāo)或者背景，較遠(yuǎn)的點(diǎn)則表示該點(diǎn)為噪聲點(diǎn)或者邊緣點(diǎn)。二維最大熵圖像多閾值分割方法的原理是：選取閾值，使陰影區(qū)域的信息量最大。

信息熵定義為

選取的最佳閾值T*應(yīng)滿足：

2 量子遺傳算法

二維最大熵圖像閾值的選擇問(wèn)題實(shí)質(zhì)上是一個(gè)優(yōu)化問(wèn)題，可以用遺傳算法等優(yōu)化方法來(lái)求解。但是普通遺傳算法（Conventional Genetic Algorithm，CGA）收斂速度慢[12-14]，因此，本文引入了量子遺傳算法。

量子遺傳算法（Quantum Genetic Algorithm，QGA）就是將量子理論的思想嵌入到普通遺傳算法。CGA種群染色體是以0和1組成的數(shù)據(jù)串，而QGA的染色體是由量子比特組成的，量子理論對(duì)CGA的改進(jìn)體現(xiàn)在以下兩點(diǎn)：

1）CGA中染色體的編碼是由若干個(gè)0或1組成的數(shù)據(jù)串，而QGA將量子學(xué)中的量子比特引入到了染色體編碼，它是由若干個(gè)量子比特組成。量子比特是的一個(gè)線性組合。量子比特可以表達(dá)為：

3 改進(jìn)QGA優(yōu)化圖像二維熵多閾值分割方法

本文提出了量子染色體編碼二維閾值方法、半隨機(jī)策略產(chǎn)生閾值解的策略和一種新的自適應(yīng)角度旋轉(zhuǎn)方法。

3.1 量子染色體編碼二維閾值

設(shè)圖像灰度級(jí)L=256，二維最大熵多閾值分割的閾值為二維，這就需要對(duì)二維閾值進(jìn)行染色體編碼，本文二維閾值量子染色體編碼方法是：設(shè)分割的閾值數(shù)為C，用8×2×C個(gè)量子比特組成的串來(lái)表示一個(gè)量子染色體，將每條染色體初始化為：

3.2 半隨機(jī)策略產(chǎn)生閾值解

通常情況下，對(duì)二維熵閾值的編碼是采用隨機(jī)產(chǎn)生閾值解的方法，但是這些方法通常忽略了兩個(gè)問(wèn)題：1）閾值解需是從小到大依次排列的，且所有的解處于圖像灰度值與鄰域均值的范圍內(nèi)，如果隨機(jī)產(chǎn)生的閾值解不符合上述要求，則需要重新產(chǎn)生閾值解，直至滿足要求，導(dǎo)致算法的收斂速度顯著降低；2）像素灰度值及其鄰域灰度均值存在某種依賴關(guān)系，如果采用完全隨機(jī)（Random）產(chǎn)生的方法，或使兩個(gè)值從相差很大開(kāi)始緩慢收斂到相近的狀態(tài)。針對(duì)上述問(wèn)題，本文提出了半隨機(jī)（Half-random）產(chǎn)生二維閾值解的方法。

從式（11）可以看出，第2維閾值解由兩項(xiàng)組成，第1項(xiàng)是通過(guò)第1維解轉(zhuǎn)換得到，第2項(xiàng)與隨機(jī)觀察染色體產(chǎn)生的解相關(guān)，即在處理第2維閾值解時(shí)，將第1維數(shù)據(jù)與隨機(jī)因素按照特定的權(quán)重因子相加形成第2維閾值解，這樣就使得第2維閾值解不僅滿足從小到大的變化規(guī)律，而且保持了與對(duì)應(yīng)第1維閾值的相關(guān)性。

3.3 自適應(yīng)旋轉(zhuǎn)角度

QGA中，變異操作是常用量子旋轉(zhuǎn)門完成，量子旋轉(zhuǎn)門定義為：

則量子旋轉(zhuǎn)變異操作為：

通常情況下，旋轉(zhuǎn)角度θ是由經(jīng)驗(yàn)確定的固定值，θ的大小影響算法的收斂速度，太小會(huì)使進(jìn)化緩慢，太大可能造成發(fā)散或過(guò)早收斂。因此，本文提出了一種旋轉(zhuǎn)角度的自適應(yīng)策略（Adaptive angle rotation strategy），如式（12）所示：

3.4 算法流程

基于二維指數(shù)熵-量子遺傳算法的圖像多閾值分割方法流程圖，如圖3所示。

圖3 本文算法流程圖

1）設(shè)定種群的個(gè)數(shù)p、閾值對(duì)數(shù)C，代數(shù)g=0，最大進(jìn)化代數(shù)gen以及結(jié)束條件μ，初始化全局最優(yōu)多閾值對(duì)解為max_T，其相應(yīng)的適應(yīng)度值為max_H。按照式（5）產(chǎn)生初始種群；

2）用3.2小節(jié)中和半隨機(jī)策略觀察染色體種群產(chǎn)生多閾值解T（g）；

3）以式（2）作為適應(yīng)度函數(shù)，評(píng)價(jià) T（g）的適應(yīng)度，從較大為原則更新max_T和max_H；

5）選擇操作，將當(dāng)代適應(yīng)度最小的量子染色體替換為適應(yīng)度最大的量子染色體；

6）如果兩代平均種群適應(yīng)度小于設(shè)定的值μ或者代數(shù)大于設(shè)定的進(jìn)化代數(shù)gen，則結(jié)束，輸出當(dāng)前最優(yōu)閾值對(duì)，程序結(jié)束；否則轉(zhuǎn)向步驟2）。

3.5 多閾值變化檢測(cè)算法

基于改進(jìn)的量子遺傳算法選取多閾值的SAR圖像變化檢測(cè)算法步驟如下：

1）使用中值濾波對(duì)兩時(shí)相原始SAR圖像進(jìn)行濾波，降低圖像中的噪聲干擾；

2）生成差異圖；

3）對(duì)差異圖進(jìn)行多閾值分割，具體分割流程如4.1；假設(shè)選取n個(gè)閾值，則差異圖就被分成了n+1類；灰度最小的一類為未變化類；灰度最大的一類為變化類；灰度在未變化類與變化類中間的像素點(diǎn)則歸為待分類點(diǎn)；

使用模糊C均值（FCM）算法確定待分類點(diǎn)類別。

4 實(shí)驗(yàn)結(jié)果與分析

本節(jié)設(shè)計(jì)實(shí)驗(yàn)測(cè)試本文算法的分割精度和時(shí)間性能。抗噪性和搜索性能試驗(yàn)中進(jìn)行對(duì)比試驗(yàn)的4種量子遺傳算法原理及測(cè)試圖像如表1和下頁(yè)圖4所示。算法QGA1使用的是一維最大熵原理，算法QGA2使用的是隨機(jī)產(chǎn)生閾值解的方法，算法QGA3使用的是固定旋轉(zhuǎn)角度，QGA4是本文提出的算法。變化檢測(cè)試驗(yàn)中比較了3種主要的閾值法：廣義高斯假設(shè)的最小誤差法（GG_KI）、最大類間方差法（OTSU）和期望最大化法（EM）。實(shí)驗(yàn)硬件環(huán)境：處理器CORE2 E7500，主頻2.93 GHz，顯卡ATI RADEON HD 4300/4500 Series，軟件環(huán)境：Matlab R2014a。

表1 實(shí)驗(yàn)的4種算法

4.1 抗噪性測(cè)試

分別用算法QGA1和本文算法QGA4對(duì)Pillsetc圖進(jìn)行圖像分割，用來(lái)對(duì)比二維熵與一維熵分割時(shí)的抗噪性。兩種算法的實(shí)驗(yàn)參數(shù)均設(shè)定為：C=3，gen=500，population=20，μ=0.001，分割結(jié)果如圖4所示。

從圖4可以看出，利用最大二維熵原理分割圖像的噪點(diǎn)明顯少于基于一維熵原理的分割結(jié)果。這是因?yàn)槎S熵直方圖加入了像素鄰域像素的信息，對(duì)噪聲具有魯棒性。

4.2 搜索性能測(cè)試

分別利用QGA1、QGA2、QGA3與QGA4對(duì)baboon、Barbara、Peppers、Lena 圖像進(jìn)行分割，用來(lái)測(cè)試本文提出的半隨機(jī)策略產(chǎn)生閾值解的方法與提出的自適應(yīng)角度在優(yōu)化算法性能方面的表現(xiàn)。各算法的參數(shù)均設(shè)定為：gen=500，population=20，μ=0.001，其中，QGA3采用的固定旋轉(zhuǎn)角度θ=0.005π，QGA4對(duì)4幅圖像的分割結(jié)果如圖5所示。每種算法獨(dú)立運(yùn)行100次分割操作，當(dāng)C=1，2，3，4時(shí)將分割后的平均最大熵（me）、平均代數(shù)（mg）、平均時(shí)間（mt，單位s）數(shù)據(jù)統(tǒng)計(jì)在下頁(yè)表2中。

圖5 本文算法對(duì)測(cè)試圖像的分割結(jié)果

表2 4種算法進(jìn)行100次分割平均熵、平均代數(shù)、平均時(shí)間

對(duì)比QGA1與其他3種算法，其信息熵均小于其他3種算法，這是因?yàn)槠渌?種算法采用的是二維熵原理，能夠得到更高分割精度；對(duì)比QGA2與本文算法，可以看出QGA2產(chǎn)生的部分熵值與本文算法相近，但是消耗了過(guò)多的時(shí)間，這是因?yàn)镼GA2在產(chǎn)生閾值解時(shí)使用了完全隨機(jī)的策略，大量產(chǎn)生的解被判為無(wú)效被否定，直到產(chǎn)生了符合期望的閾值解，在這個(gè)循環(huán)的過(guò)程中消耗了大量的時(shí)間，而本文算法采用了半隨機(jī)產(chǎn)生閾值解的策略，線性變換使得閾值解從小到大排列，而后將第1維數(shù)據(jù)與隨機(jī)因素按照特定的權(quán)重因子相加起來(lái)形成第2維閾值解，保證了閾值的相關(guān)性，大大加快了尋優(yōu)速度；QGA3與本文算法相比，本文算法總體上迭代的次數(shù)少，算法速度快，這是因?yàn)楸疚乃惴ú捎昧俗赃m應(yīng)旋轉(zhuǎn)策略，從而加快了收斂速度。

4.3 變化檢測(cè)實(shí)驗(yàn)

基于差異圖的變化檢測(cè)實(shí)際上是對(duì)差異圖進(jìn)行目標(biāo)和背景的分割。經(jīng)過(guò)多次試驗(yàn)證明，當(dāng)選取C=2，即確定兩個(gè)閾值，分成3類時(shí)得到的結(jié)果性能最好。其他參數(shù)設(shè)定為 gen=200，population=20，μ=0.001。為了節(jié)省篇幅，實(shí)驗(yàn)數(shù)據(jù)選取一組拍攝于1997年5月和1997年8月的渥太華地區(qū)水災(zāi)變化圖，大小為 290×350，圖6（c）為變化參考圖。實(shí)驗(yàn)結(jié)果如圖7所示。

相對(duì)于參考圖，對(duì)3種方法的檢測(cè)結(jié)果定量分析如下頁(yè)表3所示。

圖6 Ottawa實(shí)驗(yàn)數(shù)據(jù)

圖7 Ottawa數(shù)據(jù)集不同算法變化檢測(cè)結(jié)果圖

GG_KI算法在均值比差異圖中找到的分割閾值為199，結(jié)果中漏檢數(shù)非常高，效果很不理想。RFLICM算法正確率檢測(cè)準(zhǔn)確率和Kappa系數(shù)較高，效果較GG_KI好很多，但是計(jì)算量大、用時(shí)過(guò)長(zhǎng)。本文提出的算法在均值比差異圖找到的分割閾值為90和165，檢測(cè)結(jié)果正確率及Kappa系數(shù)均比其他兩種方法高，分割效果更好。且盡管如此，速度比單閾值的GG_KI還要快，比RFLICM算法甚至提高了4倍以上，算法實(shí)時(shí)性好。

表3 Ottawa實(shí)驗(yàn)數(shù)據(jù)各檢測(cè)結(jié)果的定量分析指標(biāo)

5 結(jié)論

針對(duì)多目標(biāo)復(fù)雜圖像的分割問(wèn)題，提出了一種改進(jìn)的二維熵-量子遺傳算法的圖像多閾值分割方法，定義了二維閾值量子染色體編碼方式；提出了一種基于半隨機(jī)策略產(chǎn)生閾值解的方法，加快了尋優(yōu)速度；改進(jìn)了量子門旋轉(zhuǎn)角度方式，提出了自適應(yīng)旋轉(zhuǎn)角度的方法，提高了算法的魯棒性和收斂速度。通過(guò)圖像分割和SAR圖像變化檢測(cè)實(shí)驗(yàn)驗(yàn)證，得到如下結(jié)論：

1）基于二維最大熵原理的分割圖像統(tǒng)計(jì)了領(lǐng)域像素的灰度信息，圖像分割的噪點(diǎn)明顯少于一維熵的分割圖像，并且具有更高的分割精度；

2）算法采用半隨機(jī)策略產(chǎn)生閾值解，保證了閾值的遞增性和相關(guān)性，其尋優(yōu)速度較完全隨機(jī)產(chǎn)生閾值解的量子遺傳算法提高了3倍～5倍；

3）采用量子門自適應(yīng)旋轉(zhuǎn)角度策略，能夠避免算法發(fā)散或過(guò)早收斂，提高算法優(yōu)化的精度和速度，使算法更具魯棒性。

量子理論在圖像處理領(lǐng)域的研究還處于初級(jí)階段，如何充分利用到量子的特點(diǎn)來(lái)解決圖像處理中的難題如圖像增強(qiáng)、識(shí)別等領(lǐng)域?qū)⑹窍乱徊降难芯恐攸c(diǎn)。