基于角度編碼染色體量子遺傳算法的模板匹配

（國防科學技術大學 a.ATR實驗室；b.計算機學院， 長沙 410073）



摘要：研究了如何應用量子遺傳算法進行圖像模板匹配，提出了角度編碼染色體量子遺傳算法。該算法以角度編碼染色體，則基因位的復數對被實數形式的角度所替代，故存儲量減少很多。染色體更新過程由矩陣與矢量相乘簡化成角度加減，染色體觀察方式由概率比較變成角度比較，因此時間性能也有較大提高。基于角度編碼染色體量子遺傳算法，結合模板匹配的特點和需求，進一步提出了逐級目標淘汰機制。該機制使匹配區域粗定位和匹配參考點精搜索有效結合，故匹配效率進一步提高。實驗結果表明，角度編碼染色體量子遺傳算法與CGA、QGA和窮舉方法相比，時間性能有了較大提高；而逐級目標淘汰機制，對于提高匹配速度是十分有效的。

關鍵詞：模板匹配；逐級目標淘汰；量子遺傳算法

中圖分類號：TP18; TP391文獻標志碼：A

文章編號：1001-3695(2008)11-3509-05



Template matching based on angle-coding chromosome quantum genetic algorithm



GAO Ying-huia，LU Kaib，SHEN Zhen-kanga

(a.ATR Key Laboratory，b.School of Computer， National University of Defense Technology， Changsha 410073， China)

Abstract:This paper studied how to realize the template matching using the quantum genetic algorithm.It proposed an angle-coding chromosome quantum genetic algorithm (AC-QGA)， whose chromosome was encoded by the angle. The complex number pair of the gene-bit was replaced by the real angle， so the storage largely. Correspondingly，simplified the updating process of the chromosome from the matrix multiplied by the vector to the angle addition or changed subtraction and the process of observing chromosome from the probability comparison to the angle comparison. So the searching efficiency of AC-QGA was also increased largely. Based on AC-QGA，the paper proposed the gradual target elimination mechanism (GTEM)according to the requirement and the character of the template matching. GTEM combined the coarse search of the matching region with the fine search of the matching point， so the matching time was smaller than that of the classical template matching methods. Experiment shows the algorithm is effective.

Key words:template matching; gradual target elimination; quantum genetic algorithm



0引言

圖像匹配廣泛應用于目標識別、圖像檢索、虛擬現實等方面，是圖像處理領域的一個重要課題。模板匹配是最常用的圖像匹配技術，經典模板匹配一般以整體窮舉為實現手段^[1]，往往無法適應實時處理的需求。所以尋求快速高效的模板匹配實現方法是十分重要和必要的。模板匹配問題能夠轉換為最優化問題，可以利用優化算法解決該問題。

量子遺傳算法（QGA）是新近發展起來的一種概率遺傳算法，是一種具有優良性能的優化算法。于是，考慮將QGA應用到模板匹配中。但在實際應用中QGA還存在存儲量大和更新速度較慢的不足。為了克服這些不足，根據量子比特在二維Hilbert空間上的極坐標表示，本文提出了角度編碼染色體量子遺傳算法（quantum genetic algorithm based on angle-coding chromosome， AC-QGA）。為了進一步減少匹配時間，又提出了一個逐級目標淘汰機制（gradual target elimination mechanism，GTEM）。該機制的引入，使得匹配區域粗定位與匹配參考點精搜索有效結合，達到了進一步提高匹配效率的目的。

1模板匹配

模板匹配是最常用的圖像匹配方法，它一般用歸一化互相關函數作為相似性測度。歸一化互相關函數是用來計算模板與源圖像間互相關系數值的工具。設模板T在源圖像S上平移，模板寬度和高度為P和Q。模板覆蓋下的源圖像區域為子圖Si， j，(i， j)為子圖左上角在S上的坐標，稱其為最佳匹配參考點。歸一化互相關函數定義如式（1）^[1]。

R(i， j)=[Pp=1

Qq=1Si， j(p，q)×T(p，q)]/[Pp=1

Qq=1(Si， j(p，q))2×

Pp=1Qq=1(T(p，q))2]

（1）

如果將源圖像看做一個二維矩形網格結構，則歸一化互相關函數就可視做三維空間中一個僅在矩形網格上取值的曲面，模板匹配就是尋求曲面極值點所對應的最佳匹配參考點的值。于是，模板匹配問題就轉換為最優化問題，可以應用量子遺傳算法來尋優。

2角度編碼染色體量子遺傳算法

量子遺傳算法（QGA）是一種基于概率的遺傳算法，是量子理論與遺傳算法相結合的產物，由韓國學者Kuk-Hyun Han等人于20世紀末提出。同經典遺傳算法（CGA）相比，QGA具有很多性能優勢：更好的種群多樣性和全局尋優能力；種群規模小卻不影響搜索性能；進化過程利用了個體進化的歷史信息，搜索速度較快，等。但在實際應用中，QGA還存在存儲量大和更新速度較慢的不足。造成不足的主要原因是：a)染色體的每一個基因位都是一個復數對，需保存四個實數，故存儲量很大；b）以量子旋轉門更新染色體，這是一個酉正矩陣與矢量相乘的過程，需通過查詢表確定旋轉角度的大小和方向，而查詢表的過程是一個多路條件判斷過程，對算法效率有很大的影響。

為克服這些不足，根據量子比特在二維Hilbert空間上的極坐標表示，本文提出了角度編碼染色體量子遺傳算法。

21角度編碼量子染色體

二維Hilbert空間中以原點為起點的單位矢量代表了所有的量子比特。對于任意一個量子比特|ψ〉=α|0〉+β|1〉。其中|0〉=[1，0]T，|1〉=[0，1]T。其矢量形式為|ψ〉=[α，β]T^[2]。如圖1所示，θ是矢量[α，β]T和|0〉=[1，0]T的夾角，則|ψ〉還可以由式（2）的極坐標形式表示。θ為極角，極徑為1，順時針方向為極角正方向。

|ψ〉=cos θ+i sin θ=eiθ=r(θ)(-π＜θ≤π)

cos2 θ=|α|2，sin2 θ=|β|2 (2)

從式（2）可知，疊加態|ψ〉坍縮到|0〉和|1〉的概率僅僅由實數θ決定。由于α和β的符號對于疊加態測量結果沒有影響，將θ的取值限制在第一象限并不影響測量結果。筆者以量子比特的極坐標形式代替矢量形式，構造出了角度編碼量子染色體。具體如下：

qtj=[θtj1|…|θtj1|…|θtjm]（3）

式（3）表示第t代種群第j個染色體，染色體長度為m，滿足0≤θtji≤π/2(i=1，2，…，m)。這樣的一個染色體同樣將2m個經典個體蘊涵于一身，坍縮到各個經典個體的概率由所有基因位角度編碼值的三角函數之乘積決定。例如，有一個長度為3的角度編碼量子染色體[π/4|π/3|π/6]，則它是23個基本態|000〉，|001〉，|010〉，|011〉，|100〉，|101〉，|110〉，|111〉的疊加，取得這些基本態的概率分別為

cos2 （π/4） cos2 （π/3） cos2 （π/6），

cos2 （π/4）cos2 （π/3） sin2 （π/6）， 

cos2 （π/4）sin2 （π/3） cos2 （π/6）， cos2 （π/4）sin2 （π/3） sin2 （π/6）， 

sin2 （π/4）cos2 （π/3） cos2 （π/6），

sin2 （π/4）cos2 （π/3） sin2 （π/6）， 

sin2 （π/4）sin2 （π/3） cos2 （π/6），

sin2 （π/4）sin2 （π/3） sin2 （π/6）

則該角度編碼量子染色體可以展開成如下形式：

（3/32）|000〉+（1/32）|001〉+（9/32）|010〉+（3/32）|011〉+（3/32）|100〉+（1/32）|101〉+（9/32）|110〉+（3/32）|111〉

22染色體更新機制

量子旋轉門是量子染色體更新的主要手段^[3～8]。基因位表現形式不同，則量子旋轉門的作用形式也大不相同。角度編碼量子染色體的每一個基因位都是一個在[0，π/2]上取值的角，則旋轉門對基因位的作用由矩陣與向量相乘，變成了角度的加減。作用形式大大簡化，計算量大大減少。量子旋轉門R簡化成以下形式：

R(θ，Δθ)=θ-S(Δθ)×Δθ（4）

式（4）中：Δθ為旋轉角度的大小；S(Δθ)為決定旋轉方向的算式，其具體形式可以根據實際需要設計。當旋轉門使基因位持續向一個方向旋轉時，則該基因位的值將接近于0或π/2，即使基因位收斂到0或π/2，從而使基因位測量值固定為0或1。基因位一旦收斂，則其測量值就很難再跳出固定的0或1，從而易造成未成熟收斂。文獻[5]對該問題進行了有益的探索，定義了一個Hε門，該門是量子旋轉門的擴展。在文獻[5]研究的基礎上，基于角度編碼量子染色體，本文定義了一種帶δ擴展的量子旋轉門Rδ。下面以Rδ門對第t代某染色體的第i個基因位的作用為例，給出Rδ門的定義：

設染色體當前的二進制觀察值為xt，當前的最優解為bt。令θti表示染色體的第i(i=1，2，…，m)個基因位，首先將旋轉門作用到該基因位上，則有λt+1i=R(θti，Δθti)=θti-S(θti)×Δθti。Δθti表示旋轉角度的大小；S(Δθti)用來決定旋轉方向。其具體形式如下：當xt不優于bt時，以bt來控制旋轉方向。有S(Δθti)=(-1)bti；當xt優于bt時，以xt來控制旋轉方向，有S(Δθti)=(-1)xti。

Rδ門定義如下：

θt+1i=Rδ(θti，Δθti)=

δ，λt+1i≤δ

（π/2）-δ，λt+1i≥（π/2）-δ

λt+1i=R(θti，Δθti)，δ＜λt+1i＜（π/2）-δ（5）

Δθti的取值為

Δθti=min((1-η(i))×(π/10)，θ0i×D(θti，bti))（6）

式（6）中各參數的意義如下：a）位影響因子η(i)，用來表示染色體各基因位的取值對其在搜索空間上所處位置的影響程度的不同。一般情況下，高位的影響要大于低位，如含m個基因位的量子染色體，第(m-1)位的影響就大于第m位的影響，所以位影響因子的取值要能夠體現這種區別。本文的位影響因子定義如式（8），則η(i)∈(0，1)。該因子的引入，使得可以對不同的基因位進行區別對待，從而使基因位的更新更加精確合理。b）差距度量函數D(θti，bti)，用來度量基因位與其演化目標之間的差距，其具體形式可以根據不同的要求來設計。本文定義如式（9），有D(θti，bti)∈(0，1)。該函數使基因位在距離演化目標遠時，旋轉角度大，則旋轉快，從而進行粗粒度搜索；在距離演化目標近時，旋轉角度小，旋轉慢，從而進行細粒度搜索。這樣不但簡化了旋轉角度的選取，而且使旋轉門的操作更加合理。c）基因位初始值θ0i，一般取π/4。

η(i)=i/ei（7）

D(θti，bti)=sin((π/2)×|(θti/(π/2))-bti|)（8）

從Rδ門的定義及其參數分析可以看出，Rδ門既保留了旋轉門R的簡單易實現的特點，又通過定義位影響因子和差距度量函數，使得基因位的更新更加快速高效。圖2是Rδ門示意圖。可以看出，當limδ→0Rδ(·)時，Rδ門與旋轉門R相同。旋轉門R使基因位收斂到0或π/2；Rδ門使其收斂到δ或((π/2)-δ）。δ的值不能設置過大，否則基因位收斂趨勢將消失。

23基本流程

1)初始化種群將種群中所有染色體的所有基因位均初始化為π/4，這意味著染色體表達搜索空間中所有可能狀態的等概率疊加。

2)初始染色體測量及初始演化目標定義隨機產生[0，π/2]內的角度ji(i=1，2，…，m)，若ji＜θji，則測量值x0ji取0，否則取1。可以對一個染色體進行多次測量，得到多個二值個體，將適應度值最大的個體作為該染色體的演化目標，并保存到演化目標集合B(t)中。

3)算法進入迭代階段迭代過程中，首先對種群進行測量，可以對一個染色體進行多次測量，得到多個二值個體，將適應度值最大的個體作為該染色體的演化目標，并保存到演化目標集合B(t)中。以B(t)中目標作指導，利用Rδ門對Q(t)進行更新，從而獲得子代種群Q(t+1)。隨著迭代深入，種群逐漸向最優解收斂。

3AC-QGA在模板匹配中的應用

以AC-QGA解決模板匹配問題時，為了進一步減少匹配時間，根據模板匹配的特點和需求，本文提出了逐級目標淘汰機制（GTEM），并將帶目標淘汰機制的AC-QGA簡稱為GAC-QGA。該機制可以有效地將匹配區域粗定位和匹配參考點精搜索結合起來，從而極大地提高了匹配效率。

31目標淘汰機制

GTEM的實現基于對搜索空間的劃分。模板匹配的搜索空間是源圖像坐標平面，所以首先將原圖像坐標平面進行劃分，分成多個子圖像，相鄰子圖像之間有重疊，且滿足一定的重疊率η（η≥30%），以防止子圖像邊界處的漏搜索；然后將每個子圖像以一個染色體編碼，編碼內容是子圖像在源圖像中的編號及其上的像素坐標偏移，該染色體被稱為標號—角度混合編碼染色體。所以種群初始規模等于子圖像的個數。為了編碼方便，每一個子圖像的高度和寬度都應保證是2的整數次冪。

初始時這些染色體并行進化，各自擁有自己的演化目標。定義一個標記次數數組LabCount_Array，其元素個數與初始種群中的染色體個數相同，即與初始目標集合中演化目標的個數相同。初始目標集合中的每一個目標都與一個數組元素相對應。每進化一代，就對最差目標進行一次標記，即將LabCount_Array中對應元素的值加1。當某一目標的標記次數大于所定義的最大標記次數時，該目標被淘汰，其對應染色體的進化終止。

隨著進化深入，不斷有目標被淘汰，從而逐漸將搜索范圍限制在最佳匹配參考點的潛在區域；再在這些區域進行精搜索，直至找到最佳匹配參考點。

32標號—角度混合編碼染色體

子圖像與初始種群中的染色體一一對應，子圖像數量即為初始種群規模。染色體的編碼內容是子圖像編號和子圖像上像素相對于其左上角坐標的高度和寬度偏移量。如圖3，將源圖像分成M×N個子圖像，圖上數字為子圖像編號（Li，Lj），則初始有M×N個染色體。

圖4代表標號—角度混合編碼染色體。可以看出，該染色體由三部分組成：a）標號（Label）、含行標號（Lab_i）和列標號（Lab_j）兩個部分，分別是子圖像行編號和列編號的二進制編碼。b）高度偏移量（Offset_i）。該部分表示所編碼像素相對于子圖像上部的高度偏移量，以m個角度量子位表示。c）寬度偏移量（Offset_j）。該部分表示所編碼像素相對子圖像左部的寬度偏移量，以n個角度量子位表示。

例如，有一個標號—角度混合編碼染色體[(01|11|)(π/4|π/4|)(π/3|π/6|)]，它表示Lab_i部分為01，Lab_j部分為11。Offset_i部分編碼為(π/4|π/4|)，Offset_j部分編碼為(π/3|π/6|)，則其對應的子搜索空間編號(Li，Lj)為(1，3)。Offset_i部分是|00〉、|01〉、|10〉、|11〉四種基本態的疊加，取得這四種基本態的概率均為1/4。Offset_j部分也是|00〉、|01〉、|10〉、|11〉的疊加，各自概率為cos2(π/3)cos2(π/6)cos2(π/3)sin2(π/6)，sin2(π/3)cos2(π/6)，sin2(π/3)sin2(π/6)，也就是3/16，1/16，9/16，3/16。綜合考慮Offset_i和Offset_ j兩個部分，則共有16種狀態，可以展開為

（3/8）|0000〉+（3/8）|0001〉+（1/8）|0010〉+（3/8）|0011〉+（3/8）|0100〉+（3/8）|0101〉+（1/8）|0110〉+（3/8）|0111〉+（3/8）|1000〉+（3/8）|1001〉+（1/8）|1010〉+（3/8）|1011〉+（3/8）|1100〉+（3/8）|1101〉+（1/8）|1110〉+（3/8）|1111〉

圖5代表染色體的隨機觀察值，Offset_i和Offset_j兩個部分通過觀察變成了二值編碼p11p12…p1mp21p22…p2n。

定義一個結構LTCoordOfSub Img存儲子圖像左上角像素在源圖像上的坐標(i0，j0)，再定義二維LTCoordOfSub Img結構數組來存儲所有子圖像左上角坐標：LTCoordOfSub Img ArrayOfLTCoord[M][N]。以式（9）解碼得到子圖像編號：

Li=Li1×2q-1+Li2×2q-2+…+Liq×20

Lj=Lj1×2r-1+Lj2×2r-2+…+Ljr×20（9）

則由圖5的染色體觀察值解碼得到源圖像上對應的坐標(i， j)為

i=ArrayOfLTCoord[Li][Lj]×i0+p11×2m-1+p12×2m-2+…+p1m×20

j=ArrayOfLTCoord[Li][Lj]×j0+p21×2n-1+p22×2n-2+…+p2n×20（10）

將式（10）的(i， j)代入式（1），則匹配過程就是尋找R(i， j)取極值時的(i， j)值，即以式（1）作為GTEQGA的適應度函數，適應度值越接近1，表明匹配效果越好。

33匹配流程

應用帶目標淘汰機制的AC-QGA實現模板匹配的流程如下：

a)t←0，初始化種群Q(t)，并將LabCount_Array的所有元素賦初值0；

b)對Q(t)中染色體實施測量，得二值解集P(t)；解碼所有二值解，并計算適應度值，保存到適應度值集合V(t)；

c)將P(t)中所有解保存到目標集合B(t)；

d)標記V(t)中最小值所對應目標，即將LabCount_Array中相應元素的值加1；

e)當小于最大進化代數，進行以下步驟：

(a)t←t+1。

(b)對Q(t-1)中所有染色體實施測量，得二值解集P(t)。解碼所有二值解，計算其適應度值，并與V(t)中的對應值比較。若某解的適應度值大于V(t)中對應值，則以其替換B(t)中的對應目標，否則不變。

（c）標記V(t)中最小值所對應目標，即將LabCount_Array中相應元素的值加1。

(d)若LabCount_Array中所有元素的值都小于最大標記次數NLmax，則以B(t)中目標為指導，利用Rδ門更新種群Q(t)，得子代種群Q(t+1)；否則，淘汰LabCount_Array中最大元素值所對應的B(t)中的演化目標，結束相應染色體的進化，LabCount_Array中相應元素賦值-1。

首先，所有染色體Offset_i和Offset_j部分的所有基因位都初始化為π/4，這意味著每一個染色體均是其所在子空間上所有可能狀態的等概率疊加，而非整個搜索空間上所有可能狀態的等概率疊加。染色體測量時，標號部分無須作任何改變，僅需針對Offset_i和Offset_j部分進行測量，測量結果解碼后代入式（1）即可計算適應度值。每一個染色體都有自己的短期演化目標，分別與各自的子搜索空間相對應，然后在各自的子空間中引導進化。這樣就將整個搜索空間上的搜索分成了多個子空間上的搜索并行進行，從而實現匹配區域粗定位與匹配參考點精搜索的有效結合。而演化目標之間適應度值的比較，可以有效地防止算法陷入局部最小。

算法進入循環后，如何實現逐級目標淘汰成為關鍵：目標淘汰的基礎是標記最差目標，標記情況通過標記次數數組來體現。隨著進化深入，若某一目標的標記次數超過了最大標記次數，則最佳匹配參考點將最不可能出現在該目標對應的子區域，所以可以將其從目標集中剔除，結束對應染色體的進化。不斷從目標集合中剔除最差目標，就相當于逐漸縮小搜索范圍，從而快速定位到最佳匹配參考點的潛在區域；然后再在潛在區域進行精搜索，則搜索效率就提高了。

34特性分析

模板匹配是一個計算量很大的工作，為了進一步縮短匹配時間，提高匹配效率，本文進一步根據模板匹配的特點和需求，提出了逐級目標淘汰機制。以帶逐級目標淘汰機制的AC-QGA實現模板匹配，具有以下優點：

a)染色體的標號—角度混合編碼是二進制編碼與量子比特角度編碼的有效結合。以二進制編碼存儲子搜索空間編號，簡單方便；以量子比特角度編碼存儲子圖像上像素相對于其左上角的高度和寬度偏移量，滿足以小規模、小存儲量種群表示多樣性狀態的要求。

b)每一個染色體均有自己的短期演化目標，分別對應各自的子搜索空間，所有子空間上的搜索并行進行，且不斷對演化目標之間的適應度值進行比較，從而可以有效克服所有染色體共用一個演化目標所造成的未成熟收斂。

c)進化過程伴隨著目標淘汰和種群規模逐漸縮小，所以這是一個由繁到簡逐漸精簡的進化過程。

d)演化目標逐級淘汰，使得粗定位與精搜索有效結合，從而使搜索速度得到極大提高。

e)演化目標與子搜索空間一一對應，目標集合涵蓋了整個搜索空間，極大地減少了陷入局部最優的可能。

4實驗結果及分析

實驗原圖像為圖4的286×286 Lena圖，圖5為30×30的模板。將圖像劃分成4×4個子圖像，子圖像間重疊率為32％，每一個子圖像的寬度和高度均為94，其左上角像素在源圖像上的坐標的取值如表1所示。采用標號—角度混合編碼量子染色體：Label部分含四個二進制位，Lab_i和Lab_j各兩位；Offset_i和Offset_j部分各以六個角度量子比特表示。令式（1）中的Pp=1Qq=1(T(p，q))2=F，匹配過程中，F值恒定。搜索開始前先將F值計算出來，然后每次代入計算適應度值就可以了。

表1子圖像信息表

編號（i0，j0）編號（i0，j0）編號（i0，j0）編號（i0，j0）

(0，0)（0，0）(2，0)(128，0)（0，1）(0，64)(2，1)(128，64)

(0，2)（0，128）(2，2)(128，128)（0，3）(0，192)(2，3)(128，192)

(1，0)（64，0）(3，0)(192，0)（1，1）(64，64)(3，1)(192，64)

(1，2)（64，128）(3，2)(192，128)（1，3）(64，192)(3，3)(192，192)

在同樣的實驗環境下：以Pentium(R) 4 CPU 1.7 GHz主頻為硬件環境，以Visual C++ 6.0為軟件開發平臺；分別應用CGA、QGA、AC-QGA、GAC-QGA，及窮舉匹配進行了實驗。實驗參數設置及實驗結果如下：

CGA的染色體編碼為兩個二進制編碼子串的串聯，它們分別代表坐標i和j。實驗原圖像的高度和寬度均為286，所以兩個編碼子串的長度均需9位，則整個染色體長度為18位。交叉概率pc和變異概率pm分別取0.8和0.05。QGA的基因編碼方法為兩個量子比特矢量編碼子串的串聯，也分別代表坐標i和j。編碼子串長度為9位，整個染色體長度為18位。AC-QGA的基因編碼方法為兩個量子比特角度編碼子串的串聯，編碼子串長度為9位，整個染色體長度為18位。GAC-QGA采用標號—角度混合量子染色體，因為分成4×4個子圖像，所以染色體的標號部分采用四個二進制位，行標號和列標號各兩位。又由于子圖像與模板的高度差和寬度差均為64，染色體的Offset_i和Offset_j部分均為六位角度量子比特。所以染色體的總長度為16位，四個二進制位不參與進化，12個角度量子比特位參與進化。最大標記次數NLmax取10。

為對比CGA、QGA、AC-QGA、GAC-QGA性能，就不同種群規模和最大進化代數各進行30次實驗。實驗結果如表2、3所示。

表2最大進化代數為60代時的實驗結果（實驗30次）

結果項GAC-QGAAC-QGAQGACGA

種群規模161010203040

正確匹配次數303030242630

匹配率/%1001001008086.7100

平均尋優時間/s0.72.73.56.57.7510

表3最大進化代數為120代時的實驗結果（實驗30次）

結果項GAC-QGAAC-QGAQGACGA

種群規模16552030

正確匹配次數3030302730

匹配率/%10010010090100

平均尋優時間/s1.53.14.28.910.5

筆者還針對窮舉匹配進行了實驗，匹配完成的時間為15 s。

綜合以上實驗結果可以知道： 窮舉匹配的時間開銷最大。CGA的種群規模和進化代數很難兼顧。當種群規模較小，進化代數也較小時，匹配率很低，若想提高匹配率，就需要擴大種群規模，或增大進化代數；由于QGA具有當前最優個體引導進化的特點，當達到同樣的匹配率時，其種群規模和進化代數均較CGA低很多；AC-QGA采用角度編碼量子染色體，其進化機制較QGA有了很大變化，所以其性能較QGA又有了提高。但無論是CGA、QGA還是AC-QGA，均無法與GAC-QGA相比。由于演化目標的逐級淘汰，GAC-QGA比它們具有更大的時間優勢。GTEQGA算法極大地提高了圖像模板匹配的效率，是一種具有很高應用價值的算法。

5結束語

從實驗分析可知，使用GAC-QGA進行模板匹配具有較大的時間優勢，可以獲得較快的匹配速度。在實際應用中，還應該根據不同的圖像類型和應用需求，對原圖像如何劃分進行研究，以保證更好的匹配效果和匹配效率；同時，算法的并行化實現應成為未來研究的重點。

參考文獻：

［1］

孫即祥.數字圖像處理[M].石家莊：河北教育出版社，1993.

[2]李承祖.量子通信和量子計算[M].長沙：國防科技大學出版社，2000.

[3]HAN K H，KIM J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proc of Congress on Evolutionary Computation.Piscataway，USA:IEEE Press，2000：1354-1360.

[4]HAN K H，PARK K H，LEE C H，et al.Parallel quantum-inspired genetic algorithm for combinatorial optimization problem[C]//Proc of Congress on Evolutionary Computation.Piscataway:IEEE Press，2001:1422-1429.

[5]KIM Y，KIM J H，HAN K H.Quantum-inspired multiobjective evolutionary algorithm formultiobjective 0/1 knapsack problems[C]//Proc of IEEE Congress on Evolutionary Computation.Vancouver BC， Canada:IEEE Press，2006:2601-2606.

[6]HAN K H，KIM J H.Quantum-inspired evolutionary algorithms with a new termination criterion ， H/sub/splepsil/gate， and two-phase scheme[J].IEEE Trans on Evolutionary Computation，2004，8(2):156-169.

[7]楊俊安，鄒誼，莊鎮泉.基于多宇宙并行量子遺傳算法的非線性盲源分離算法研究[J].電子與信息學報，2004，26(8)：1210-1216.

[8]李映，焦李成.一種有效的基于并行量子進化的圖像邊緣檢測方法[J].信號處理，2003，19（1）：69-74.

[9]郭海燕，金煒東，李麗，等.分組量子遺傳算法及其應用[J].西南科技大學學報，2004，19(1):18-21.