基于改進二維熵-量子遺傳算法的圖像多閾值變化檢測方法*

仝 彤，慕曉冬，張 力

（火箭軍工程大學，西安 710025）

0 引言

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

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

本文提出了一種基于二維熵-量子遺傳算法的圖像多閾值變化檢測方法。其優勢體現在：1）研究了二維閾值量子染色體編碼方法，解決了傳統遺傳算法優化二維最大指數熵閾值過程中速度慢、多樣性小的缺點；2）提出了一種半隨機策略產生閾值解的方法，加快尋優速度；3）改進了量子門旋轉角度方式，提出了自適應旋轉角度的方法，提高了算法的魯棒性和收斂速度。

1 二維指數熵圖像多閾值分割

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

其中，nij指的是圖像中灰度值為i而鄰域灰度均值為j的像素的個數。

圖1 二維直方圖

圖2 二維直方圖俯視平面

圖2為二維直方圖的俯視圖，橫軸代表i，縱軸代表j，設分割的閾值對數C=4，在圖中閾值表示為，整個區域被直線i=j分割開來，離該直線距離近的點（陰影部分內的點）表示其灰度值和鄰域灰度均值比較接近，應屬于圖像的目標或者背景，較遠的點則表示該點為噪聲點或者邊緣點。二維最大熵圖像多閾值分割方法的原理是：選取閾值，使陰影區域的信息量最大。

信息熵定義為

選取的最佳閾值T*應滿足：

2 量子遺傳算法

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

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

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

3 改進QGA優化圖像二維熵多閾值分割方法

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

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

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

3.2 半隨機策略產生閾值解

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

從式（11）可以看出，第2維閾值解由兩項組成，第1項是通過第1維解轉換得到，第2項與隨機觀察染色體產生的解相關，即在處理第2維閾值解時，將第1維數據與隨機因素按照特定的權重因子相加形成第2維閾值解，這樣就使得第2維閾值解不僅滿足從小到大的變化規律，而且保持了與對應第1維閾值的相關性。

3.3 自適應旋轉角度

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

則量子旋轉變異操作為：

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

3.4 算法流程

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

圖3 本文算法流程圖

1）設定種群的個數p、閾值對數C，代數g=0，最大進化代數gen以及結束條件μ，初始化全局最優多閾值對解為max_T，其相應的適應度值為max_H。按照式（5）產生初始種群；

2）用3.2小節中和半隨機策略觀察染色體種群產生多閾值解T（g）；

3）以式（2）作為適應度函數，評價 T（g）的適應度，從較大為原則更新max_T和max_H；

5）選擇操作，將當代適應度最小的量子染色體替換為適應度最大的量子染色體；

6）如果兩代平均種群適應度小于設定的值μ或者代數大于設定的進化代數gen，則結束，輸出當前最優閾值對，程序結束；否則轉向步驟2）。

3.5 多閾值變化檢測算法

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

1）使用中值濾波對兩時相原始SAR圖像進行濾波，降低圖像中的噪聲干擾；

2）生成差異圖；

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

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

4 實驗結果與分析

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

表1 實驗的4種算法

4.1 抗噪性測試

分別用算法QGA1和本文算法QGA4對Pillsetc圖進行圖像分割，用來對比二維熵與一維熵分割時的抗噪性。兩種算法的實驗參數均設定為：C=3，gen=500，population=20，μ=0.001，分割結果如圖4所示。

從圖4可以看出，利用最大二維熵原理分割圖像的噪點明顯少于基于一維熵原理的分割結果。這是因為二維熵直方圖加入了像素鄰域像素的信息，對噪聲具有魯棒性。

4.2 搜索性能測試

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

圖5 本文算法對測試圖像的分割結果

表2 4種算法進行100次分割平均熵、平均代數、平均時間

對比QGA1與其他3種算法，其信息熵均小于其他3種算法，這是因為其他3種算法采用的是二維熵原理，能夠得到更高分割精度；對比QGA2與本文算法，可以看出QGA2產生的部分熵值與本文算法相近，但是消耗了過多的時間，這是因為QGA2在產生閾值解時使用了完全隨機的策略，大量產生的解被判為無效被否定，直到產生了符合期望的閾值解，在這個循環的過程中消耗了大量的時間，而本文算法采用了半隨機產生閾值解的策略，線性變換使得閾值解從小到大排列，而后將第1維數據與隨機因素按照特定的權重因子相加起來形成第2維閾值解，保證了閾值的相關性，大大加快了尋優速度；QGA3與本文算法相比，本文算法總體上迭代的次數少，算法速度快，這是因為本文算法采用了自適應旋轉策略，從而加快了收斂速度。

4.3 變化檢測實驗

基于差異圖的變化檢測實際上是對差異圖進行目標和背景的分割。經過多次試驗證明，當選取C=2，即確定兩個閾值，分成3類時得到的結果性能最好。其他參數設定為 gen=200，population=20，μ=0.001。為了節省篇幅，實驗數據選取一組拍攝于1997年5月和1997年8月的渥太華地區水災變化圖，大小為 290×350，圖6（c）為變化參考圖。實驗結果如圖7所示。

相對于參考圖，對3種方法的檢測結果定量分析如下頁表3所示。

圖6 Ottawa實驗數據

圖7 Ottawa數據集不同算法變化檢測結果圖

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

表3 Ottawa實驗數據各檢測結果的定量分析指標

5 結論

針對多目標復雜圖像的分割問題，提出了一種改進的二維熵-量子遺傳算法的圖像多閾值分割方法，定義了二維閾值量子染色體編碼方式；提出了一種基于半隨機策略產生閾值解的方法，加快了尋優速度；改進了量子門旋轉角度方式，提出了自適應旋轉角度的方法，提高了算法的魯棒性和收斂速度。通過圖像分割和SAR圖像變化檢測實驗驗證，得到如下結論：

1）基于二維最大熵原理的分割圖像統計了領域像素的灰度信息，圖像分割的噪點明顯少于一維熵的分割圖像，并且具有更高的分割精度；

2）算法采用半隨機策略產生閾值解，保證了閾值的遞增性和相關性，其尋優速度較完全隨機產生閾值解的量子遺傳算法提高了3倍～5倍；

3）采用量子門自適應旋轉角度策略，能夠避免算法發散或過早收斂，提高算法優化的精度和速度，使算法更具魯棒性。

量子理論在圖像處理領域的研究還處于初級階段，如何充分利用到量子的特點來解決圖像處理中的難題如圖像增強、識別等領域將是下一步的研究重點。