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

（國防科學(xué)技術(shù)大學(xué) a.ATR實(shí)驗(yàn)室；b.計(jì)算機(jī)學(xué)院， 長沙 410073）



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

關(guān)鍵詞：模板匹配；逐級(jí)目標(biāo)淘汰；量子遺傳算法

中圖分類號(hào)：TP18; TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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引言

圖像匹配廣泛應(yīng)用于目標(biāo)識(shí)別、圖像檢索、虛擬現(xiàn)實(shí)等方面，是圖像處理領(lǐng)域的一個(gè)重要課題。模板匹配是最常用的圖像匹配技術(shù)，經(jīng)典模板匹配一般以整體窮舉為實(shí)現(xiàn)手段^[1]，往往無法適應(yīng)實(shí)時(shí)處理的需求。所以尋求快速高效的模板匹配實(shí)現(xiàn)方法是十分重要和必要的。模板匹配問題能夠轉(zhuǎn)換為最優(yōu)化問題，可以利用優(yōu)化算法解決該問題。

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

1模板匹配

模板匹配是最常用的圖像匹配方法，它一般用歸一化互相關(guān)函數(shù)作為相似性測(cè)度。歸一化互相關(guān)函數(shù)是用來計(jì)算模板與源圖像間互相關(guān)系數(shù)值的工具。設(shè)模板T在源圖像S上平移，模板寬度和高度為P和Q。模板覆蓋下的源圖像區(qū)域?yàn)樽訄DSi， j，(i， j)為子圖左上角在S上的坐標(biāo)，稱其為最佳匹配參考點(diǎn)。歸一化互相關(guān)函數(shù)定義如式（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）

如果將源圖像看做一個(gè)二維矩形網(wǎng)格結(jié)構(gòu)，則歸一化互相關(guān)函數(shù)就可視做三維空間中一個(gè)僅在矩形網(wǎng)格上取值的曲面，模板匹配就是尋求曲面極值點(diǎn)所對(duì)應(yīng)的最佳匹配參考點(diǎn)的值。于是，模板匹配問題就轉(zhuǎn)換為最優(yōu)化問題，可以應(yīng)用量子遺傳算法來尋優(yōu)。

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

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

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

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

二維Hilbert空間中以原點(diǎn)為起點(diǎn)的單位矢量代表了所有的量子比特。對(duì)于任意一個(gè)量子比特|ψ〉=α|0〉+β|1〉。其中|0〉=[1，0]T，|1〉=[0，1]T。其矢量形式為|ψ〉=[α，β]T^[2]。如圖1所示，θ是矢量[α，β]T和|0〉=[1，0]T的夾角，則|ψ〉還可以由式（2）的極坐標(biāo)形式表示。θ為極角，極徑為1，順時(shí)針方向?yàn)闃O角正方向。

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

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

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

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

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

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染色體更新機(jī)制

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

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

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

設(shè)染色體當(dāng)前的二進(jìn)制觀察值為xt，當(dāng)前的最優(yōu)解為bt。令θti表示染色體的第i(i=1，2，…，m)個(gè)基因位，首先將旋轉(zhuǎn)門作用到該基因位上，則有λt+1i=R(θti，Δθti)=θti-S(θti)×Δθti。Δθti表示旋轉(zhuǎn)角度的大小；S(Δθti)用來決定旋轉(zhuǎn)方向。其具體形式如下：當(dāng)xt不優(yōu)于bt時(shí)，以bt來控制旋轉(zhuǎn)方向。有S(Δθti)=(-1)bti；當(dāng)xt優(yōu)于bt時(shí)，以xt來控制旋轉(zhuǎn)方向，有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）中各參數(shù)的意義如下：a）位影響因子η(i)，用來表示染色體各基因位的取值對(duì)其在搜索空間上所處位置的影響程度的不同。一般情況下，高位的影響要大于低位，如含m個(gè)基因位的量子染色體，第(m-1)位的影響就大于第m位的影響，所以位影響因子的取值要能夠體現(xiàn)這種區(qū)別。本文的位影響因子定義如式（8），則η(i)∈(0，1)。該因子的引入，使得可以對(duì)不同的基因位進(jìn)行區(qū)別對(duì)待，從而使基因位的更新更加精確合理。b）差距度量函數(shù)D(θti，bti)，用來度量基因位與其演化目標(biāo)之間的差距，其具體形式可以根據(jù)不同的要求來設(shè)計(jì)。本文定義如式（9），有D(θti，bti)∈(0，1)。該函數(shù)使基因位在距離演化目標(biāo)遠(yuǎn)時(shí)，旋轉(zhuǎn)角度大，則旋轉(zhuǎn)快，從而進(jìn)行粗粒度搜索；在距離演化目標(biāo)近時(shí)，旋轉(zhuǎn)角度小，旋轉(zhuǎn)慢，從而進(jìn)行細(xì)粒度搜索。這樣不但簡化了旋轉(zhuǎn)角度的選取，而且使旋轉(zhuǎn)門的操作更加合理。c）基因位初始值θ0i，一般取π/4。

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

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

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

23基本流程

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

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

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

3AC-QGA在模板匹配中的應(yīng)用

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

31目標(biāo)淘汰機(jī)制

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

初始時(shí)這些染色體并行進(jìn)化，各自擁有自己的演化目標(biāo)。定義一個(gè)標(biāo)記次數(shù)數(shù)組LabCount_Array，其元素個(gè)數(shù)與初始種群中的染色體個(gè)數(shù)相同，即與初始目標(biāo)集合中演化目標(biāo)的個(gè)數(shù)相同。初始目標(biāo)集合中的每一個(gè)目標(biāo)都與一個(gè)數(shù)組元素相對(duì)應(yīng)。每進(jìn)化一代，就對(duì)最差目標(biāo)進(jìn)行一次標(biāo)記，即將LabCount_Array中對(duì)應(yīng)元素的值加1。當(dāng)某一目標(biāo)的標(biāo)記次數(shù)大于所定義的最大標(biāo)記次數(shù)時(shí)，該目標(biāo)被淘汰，其對(duì)應(yīng)染色體的進(jìn)化終止。

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

32標(biāo)號(hào)—角度混合編碼染色體

子圖像與初始種群中的染色體一一對(duì)應(yīng)，子圖像數(shù)量即為初始種群規(guī)模。染色體的編碼內(nèi)容是子圖像編號(hào)和子圖像上像素相對(duì)于其左上角坐標(biāo)的高度和寬度偏移量。如圖3，將源圖像分成M×N個(gè)子圖像，圖上數(shù)字為子圖像編號(hào)（Li，Lj），則初始有M×N個(gè)染色體。

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

例如，有一個(gè)標(biāo)號(hào)—角度混合編碼染色體[(01|11|)(π/4|π/4|)(π/3|π/6|)]，它表示Lab_i部分為01，Lab_j部分為11。Offset_i部分編碼為(π/4|π/4|)，Offset_j部分編碼為(π/3|π/6|)，則其對(duì)應(yīng)的子搜索空間編號(hào)(Li，Lj)為(1，3)。Offset_i部分是|00〉、|01〉、|10〉、|11〉四種基本態(tài)的疊加，取得這四種基本態(tài)的概率均為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兩個(gè)部分，則共有16種狀態(tài)，可以展開為

（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代表染色體的隨機(jī)觀察值，Offset_i和Offset_j兩個(gè)部分通過觀察變成了二值編碼p11p12…p1mp21p22…p2n。

定義一個(gè)結(jié)構(gòu)LTCoordOfSub Img存儲(chǔ)子圖像左上角像素在源圖像上的坐標(biāo)(i0，j0)，再定義二維LTCoordOfSub Img結(jié)構(gòu)數(shù)組來存儲(chǔ)所有子圖像左上角坐標(biāo)：LTCoordOfSub Img ArrayOfLTCoord[M][N]。以式（9）解碼得到子圖像編號(hào)：

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的染色體觀察值解碼得到源圖像上對(duì)應(yīng)的坐標(biāo)(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)取極值時(shí)的(i， j)值，即以式（1）作為GTEQGA的適應(yīng)度函數(shù)，適應(yīng)度值越接近1，表明匹配效果越好。

33匹配流程

應(yīng)用帶目標(biāo)淘汰機(jī)制的AC-QGA實(shí)現(xiàn)模板匹配的流程如下：

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

b)對(duì)Q(t)中染色體實(shí)施測(cè)量，得二值解集P(t)；解碼所有二值解，并計(jì)算適應(yīng)度值，保存到適應(yīng)度值集合V(t)；

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

d)標(biāo)記V(t)中最小值所對(duì)應(yīng)目標(biāo)，即將LabCount_Array中相應(yīng)元素的值加1；

e)當(dāng)小于最大進(jìn)化代數(shù)，進(jìn)行以下步驟：

(a)t←t+1。

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

（c）標(biāo)記V(t)中最小值所對(duì)應(yīng)目標(biāo)，即將LabCount_Array中相應(yīng)元素的值加1。

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

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

算法進(jìn)入循環(huán)后，如何實(shí)現(xiàn)逐級(jí)目標(biāo)淘汰成為關(guān)鍵：目標(biāo)淘汰的基礎(chǔ)是標(biāo)記最差目標(biāo)，標(biāo)記情況通過標(biāo)記次數(shù)數(shù)組來體現(xiàn)。隨著進(jìn)化深入，若某一目標(biāo)的標(biāo)記次數(shù)超過了最大標(biāo)記次數(shù)，則最佳匹配參考點(diǎn)將最不可能出現(xiàn)在該目標(biāo)對(duì)應(yīng)的子區(qū)域，所以可以將其從目標(biāo)集中剔除，結(jié)束對(duì)應(yīng)染色體的進(jìn)化。不斷從目標(biāo)集合中剔除最差目標(biāo)，就相當(dāng)于逐漸縮小搜索范圍，從而快速定位到最佳匹配參考點(diǎn)的潛在區(qū)域；然后再在潛在區(qū)域進(jìn)行精搜索，則搜索效率就提高了。

34特性分析

模板匹配是一個(gè)計(jì)算量很大的工作，為了進(jìn)一步縮短匹配時(shí)間，提高匹配效率，本文進(jìn)一步根據(jù)模板匹配的特點(diǎn)和需求，提出了逐級(jí)目標(biāo)淘汰機(jī)制。以帶逐級(jí)目標(biāo)淘汰機(jī)制的AC-QGA實(shí)現(xiàn)模板匹配，具有以下優(yōu)點(diǎn)：

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

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

c)進(jìn)化過程伴隨著目標(biāo)淘汰和種群規(guī)模逐漸縮小，所以這是一個(gè)由繁到簡逐漸精簡的進(jìn)化過程。

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

e)演化目標(biāo)與子搜索空間一一對(duì)應(yīng)，目標(biāo)集合涵蓋了整個(gè)搜索空間，極大地減少了陷入局部最優(yōu)的可能。

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

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

表1子圖像信息表

編號(hào)（i0，j0）編號(hào)（i0，j0）編號(hào)（i0，j0）編號(hào)（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)

在同樣的實(shí)驗(yàn)環(huán)境下：以Pentium(R) 4 CPU 1.7 GHz主頻為硬件環(huán)境，以Visual C++ 6.0為軟件開發(fā)平臺(tái)；分別應(yīng)用CGA、QGA、AC-QGA、GAC-QGA，及窮舉匹配進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置及實(shí)驗(yàn)結(jié)果如下：

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

為對(duì)比CGA、QGA、AC-QGA、GAC-QGA性能，就不同種群規(guī)模和最大進(jìn)化代數(shù)各進(jìn)行30次實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表2、3所示。

表2最大進(jìn)化代數(shù)為60代時(shí)的實(shí)驗(yàn)結(jié)果（實(shí)驗(yàn)30次）

結(jié)果項(xiàng)GAC-QGAAC-QGAQGACGA

種群規(guī)模161010203040

正確匹配次數(shù)303030242630

匹配率/%1001001008086.7100

平均尋優(yōu)時(shí)間/s0.72.73.56.57.7510

表3最大進(jìn)化代數(shù)為120代時(shí)的實(shí)驗(yàn)結(jié)果（實(shí)驗(yàn)30次）

結(jié)果項(xiàng)GAC-QGAAC-QGAQGACGA

種群規(guī)模16552030

正確匹配次數(shù)3030302730

匹配率/%10010010090100

平均尋優(yōu)時(shí)間/s1.53.14.28.910.5

筆者還針對(duì)窮舉匹配進(jìn)行了實(shí)驗(yàn)，匹配完成的時(shí)間為15 s。

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

5結(jié)束語

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

參考文獻(xiàn)：

［1］

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

[2]李承祖.量子通信和量子計(jì)算[M].長沙：國防科技大學(xué)出版社，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]楊俊安，鄒誼，莊鎮(zhèn)泉.基于多宇宙并行量子遺傳算法的非線性盲源分離算法研究[J].電子與信息學(xué)報(bào)，2004，26(8)：1210-1216.

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

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