程 紅，陳 文 劍

禁忌搜索算法在圖像匹配中的應(yīng)用研究

程 紅，陳 文 劍

（中國人民解放軍空軍航空大學(xué)特種專業(yè)系，吉林 長春 130022）

搜索策略是圖像匹配研究的主要問題之一，對匹配算法的執(zhí)行速度和最終的匹配精度都有很大的影響。該文將禁忌搜索算法的思想用于圖像匹配的搜索過程，并進(jìn)行了改進(jìn)，構(gòu)造了永久禁忌和暫時禁忌兩種禁忌表，每次搜索都將候選解中的點(diǎn)分別放入不同的禁忌表中，再利用基于灰度的匹配方法，以歸一化積相關(guān)為相似性度量準(zhǔn)則，克服了傳統(tǒng)的歸一化積相關(guān)圖像匹配算法耗時過長的缺點(diǎn)，可以在不失匹配精度的條件下，大大減少匹配所用的時間，實(shí)現(xiàn)了準(zhǔn)確而快速的圖像匹配。

圖像匹配;禁忌搜索;歸一化積相關(guān)

圖像匹配屬于人工智能的范疇，是人類視覺認(rèn)知的一種延伸。圖像匹配技術(shù)的應(yīng)用領(lǐng)域相當(dāng)廣，如醫(yī)學(xué)圖像分析、導(dǎo)彈的地形和地圖匹配制導(dǎo)、武器投射系統(tǒng)的尋的等;同時圖像匹配技術(shù)也是其它一些圖像分析技術(shù)（如立體視覺、運(yùn)動分析、數(shù)據(jù)融合等）的基礎(chǔ)。因此，開展圖像匹配技術(shù)研究具有重要的理論意義和實(shí)用價值［1，2］。

所謂圖像匹配，就是在機(jī)器識別事物的過程中，將已知圖像與陌生圖像的全部或部分在空間上對準(zhǔn)，根據(jù)已知模式的圖像在一幅陌生圖像中尋找對應(yīng)模式的子圖像的過程［2，3］。圖像匹配主要研究的問題有特征空間、相似性度量和搜索策略3方面。其中，搜索策略是指用合適的搜索方法在搜索空間又準(zhǔn)又快地找出平移、旋轉(zhuǎn)等變化參數(shù)的最優(yōu)估計，使得圖像之間經(jīng)過變換后的相似性最大。搜索策略有窮盡搜索、分層搜索、模擬退火算法、遺傳算法、粒子群算法等，后幾種算法都屬于智能優(yōu)化方法，是近年發(fā)展起來的非?；钴S的研究領(lǐng)域［4］。本文提出了一種基于禁忌搜索算法的圖像匹配方法，利用圖像的整體灰度值，以歸一化積相關(guān)作為相似性度量準(zhǔn)則，在搜索策略上使用經(jīng)過改進(jìn)的禁忌搜索算法，構(gòu)造了永久禁忌和暫時禁忌兩種禁忌表，既能避免重復(fù)搜索，又不至于陷入局部最優(yōu)，從而實(shí)現(xiàn)了準(zhǔn)確、快速的圖像匹配。

1 歸一化積相關(guān)圖像匹配方法

歸一化積相關(guān)算法是一種基于灰度的圖像匹配方法。大量研究表明：盡管歸一化積相關(guān)系數(shù)的計算量比較大，但它具有很強(qiáng)的抗噪聲能力，對于灰度變化和較小的幾何畸變具有不變特性，因而仍是圖像匹配較好的相似性度量準(zhǔn)則之一［5－8］。設(shè)實(shí)時圖像為g，大小為M×N，基準(zhǔn)圖像為f，大小為W×H。歸一化積相關(guān)算法計算每個可能的匹配位置處的相關(guān)系數(shù)，并找出其中的最大值點(diǎn)即為匹配點(diǎn)。

歸一化積相關(guān)系數(shù)定義為：

式中：ρ（r，c）表示將實(shí)時圖像平移至基準(zhǔn)圖像（r，c）位置處時，子圖像與實(shí)時圖像的相關(guān)系數(shù)的大小，并且有1≤r≤W－M＋1、1≤c≤H－N＋ 1;gij表示實(shí)時圖像g中第i行、第j列的像素值;fi＋r，j＋c表示基準(zhǔn)圖像f中第i＋r行、第j＋c列的像素值;ˉg為實(shí)時圖像g所有像素的灰度平均值;將基準(zhǔn)圖像f中以（r，c）為左上角點(diǎn)，尺寸大小為M×N的區(qū)域定義為（r，c）處的基準(zhǔn)子圖，記作frc，則ˉfrc表示基準(zhǔn)子圖frc內(nèi)所有像素的平均值［9］。

2 禁忌搜索算法

禁忌搜索算法（Tabu Search或Taboo Search，TS）是繼遺傳算法之后出現(xiàn)的又一種元啟發(fā)式優(yōu)化算法，最早于1977年由Glover提出。禁忌搜索算法模仿人類的記憶功能，使用禁忌表封鎖剛剛搜索過的區(qū)域以避免迂回搜索，同時赦免禁忌區(qū)域中的一些優(yōu)良狀態(tài)，進(jìn)而保證搜索的多樣性，從而達(dá)到全局優(yōu)化。

由于禁忌搜索算法的渴望水平、選擇策略以及停止準(zhǔn)則等都可以有多種設(shè)定方式，禁忌搜索算法的步驟多種多樣。最基本的步驟［4］如下：1）初始化。給出初始解，禁忌表設(shè)為空。2）判斷是否滿足停止條件。如果滿足，輸出結(jié)果，算法停止;否則繼續(xù)下一步。3）對于候選解集中的最好解，判斷其是否滿足渴望水平。如果滿足，更新渴望水平，更新當(dāng)前解，轉(zhuǎn)至第5步;否則繼續(xù)下一步。4）選擇候選解集中不被禁忌的最好解作為當(dāng)前解。5）更新禁忌表。6）轉(zhuǎn)至第2步。

3 基于禁忌搜索算法的圖像匹配方法

歸一化積相關(guān)圖像匹配方法就是在某一鄰域內(nèi)搜索實(shí)時圖像的最佳匹配位置，其解可以看成是一個二維坐標(biāo)（行和列），這實(shí)際上就是一個離散優(yōu)化的過程，而禁忌搜索算法一般僅用于離散優(yōu)化的情況，排斥實(shí)優(yōu)化，并且它的各個構(gòu)成要素正好與匹配過程的某一方面對應(yīng)。因此，可以考慮應(yīng)用禁忌搜索算法實(shí)現(xiàn)匹配。另外，為了盡可能地加強(qiáng)算法的魯棒性和提升匹配速度，需要對標(biāo)準(zhǔn)的禁忌搜索算法進(jìn)行改進(jìn)。本文提出的基于禁忌搜索算法的圖像匹配方法的實(shí)現(xiàn)過程說明如下：

3.1 獲取初始值

初始值的確定對最終的匹配速度和結(jié)果影響很大。為使算法在剛開始時具有較好的全局尋優(yōu)性能，第一次迭代的初始值一般取搜索空間的中心坐標(biāo)。

設(shè)實(shí)時圖像為g，大小為M×N，基準(zhǔn)圖像為f，大小為W×H，則第一次迭代的初始值為（‖r/2‖，‖c/2‖），其中1≤r≤W－M＋1，1≤c≤H－N＋ 1;第二次迭代選取第一次迭代過程中產(chǎn)生的最優(yōu)搜索狀態(tài)對應(yīng)的坐標(biāo)為初始值（如果中心坐標(biāo)產(chǎn)生的結(jié)果最優(yōu)，則選取次優(yōu)搜索狀態(tài)對應(yīng)的坐標(biāo)作為初始值）;以后的迭代過程則選取不在禁忌表中的最優(yōu)值作為下一次迭代的初始值。

3.2 構(gòu)造候選解鄰域

候選解鄰域是指某次迭代過程中所有可能的解的集合，這里將其看作是以該次迭代的初始值為中心的一定大小的區(qū)域，如3×3、5×5、7×7等，區(qū)域大小與參與匹配的圖像大小有關(guān)，并能夠影響迭代的速度和最終的匹配耗時。另外，當(dāng)鄰域中心靠近搜索空間的邊緣時，可能得不到一個完整的鄰域，這時將搜索空間看成以r行、c列為周期的二維離散周期函數(shù)，從而仍可確定出一個指定大小的區(qū)域。

設(shè)搜索空間大小為r×c，某次迭代的鄰域中心（即初始值）為（x0，y0），鄰域大小為（2R＋1）×（2R＋1），則鄰域是指滿足式（2）的像素點(diǎn)的集合，其中－R≤i，j≤R，i，j∈Z。如圖1所示，圖中陰影部分分別是以A、B點(diǎn)為中心的3×3大小的鄰域區(qū)域。

圖1 候選解鄰域的確定Fig.1 The determination of the candidate solution neighborhood

3.3 構(gòu)造適值函數(shù)及禁忌表

本文直接用目標(biāo)函數(shù)，即實(shí)時圖像與對應(yīng)的基準(zhǔn)子圖的歸一化積相關(guān)系數(shù)作為適值函數(shù)，評價候選解鄰域內(nèi)所有可能的匹配點(diǎn)的優(yōu)劣。

為了盡可能充分地實(shí)現(xiàn)全局搜索和局部搜索，本算法構(gòu)造了兩種禁忌表：永久禁忌表和暫時禁忌表。永久禁忌表中的點(diǎn)在接下來的迭代過程中不再作為初始值，而暫時禁忌表中的點(diǎn)只在一定迭代次數(shù)之內(nèi)禁忌被作為初始值，過了一定迭代次數(shù)后，這些點(diǎn)就可以成為迭代初始值，用來構(gòu)建候選解鄰域。也就是說，將本次迭代的初始值（候選解鄰域的中心點(diǎn)）放入永久禁忌表中，將鄰域中的其它點(diǎn)賦予某個禁忌長度，并放入暫時禁忌表中。

3.4 渴望水平及停止準(zhǔn)則

本算法將每次迭代產(chǎn)生的所有搜索狀態(tài)與歷史最優(yōu)值作比較，如果優(yōu)于歷史最優(yōu)值，則將本次迭代產(chǎn)生的最優(yōu)搜索狀態(tài)作為新的歷史最優(yōu)值。

本算法以迭代次數(shù)達(dá)到某一閾值為停止準(zhǔn)則。為了避免適值函數(shù)的重復(fù)計算，本算法構(gòu)造了兩個r×c大小的矩陣，一個用來保存已經(jīng)計算過的坐標(biāo)點(diǎn)對應(yīng)的適值函數(shù)值，另一個用來標(biāo)記哪些點(diǎn)的適值函數(shù)值已經(jīng)計算過。在某次迭代過程中，需要把候選解的適值函數(shù)值與歷史最優(yōu)解進(jìn)行比較，如果該候選解的適值函數(shù)值在之前的迭代過程中已經(jīng)計算過，則可以直接使用，避免再一次重復(fù)計算。另外，由于搜索過程實(shí)際上是在包含多個極值“山峰”的空間內(nèi)移動，尋找最高的峰值，本算法在某次迭代完成后就將該次迭代所訪問的區(qū)域“削平”，即把該區(qū)域內(nèi)所有點(diǎn)的適值函數(shù)值賦為零，這樣的處理可以使算法盡可能地呈“發(fā)散狀”向外搜索，從而避免陷入局部最優(yōu)的情況。

3.5 對比實(shí)驗

將本文算法與傳統(tǒng)的歸一化積相關(guān)匹配方法進(jìn)行對比實(shí)驗，以驗證本文算法的可靠性和優(yōu)越性。在使用本文算法時鄰域大小、禁忌長度等參數(shù)都取大量實(shí)驗得出的經(jīng)驗最優(yōu)值，在3.6節(jié)詳細(xì)討論這些參數(shù)的確定過程。

實(shí)驗條件：CPU：Intel（R）Core（TM）i 5;主頻：2.40 GHz;內(nèi)存：2.00 GB;操作系統(tǒng)：Windows 7家庭普通版;編程環(huán)境：Matlab 7.1。

測試圖像和實(shí)驗對比結(jié)果分別如圖2和表1所示。測試圖像中，第一組圖像的最佳匹配點(diǎn)位于中心點(diǎn)上方，第二組圖像的最佳匹配點(diǎn)位于左上角，且右側(cè)存在一塊相似的干擾區(qū)域;表1中的收斂次數(shù)是指算法收斂到最佳匹配點(diǎn)所需的最少迭代次數(shù)。

圖2 實(shí)驗所用的圖像Fig.2 The images used in experiment

表1 實(shí)驗參數(shù)和結(jié)果Table 1 The parameters and results of the experiment

3.6 實(shí)驗結(jié)果分析和參數(shù)確定

由表1可知，本文算法能在很短的時間內(nèi)穩(wěn)定地收斂到最佳匹配點(diǎn)，但同時也發(fā)現(xiàn)，最終的收斂結(jié)果和收斂速度受鄰域大小、禁忌長度等參數(shù)的影響很大。通過在實(shí)驗中逐一改變各參數(shù)的取值，可以得到如圖3、圖4的關(guān)系。

需要說明的是，在圖3b和圖4b中，鄰域大小為5×5的曲線變成了兩段，這是因為當(dāng)禁忌長度為6時算法在迭代4 000次時仍沒有找到最佳匹配點(diǎn)，故認(rèn)為此時算法的運(yùn)行時間和收斂次數(shù)為無窮大。

圖3 禁忌長度與運(yùn)行時間的關(guān)系Fig.3 The relationship of tabu size and execution time

圖4 禁忌長度與收斂次數(shù)的關(guān)系Fig.4 The relationship of tabu size and convergence times

由圖3、圖4可知，鄰域大小為5×5時，無論是運(yùn)行時間還是收斂次數(shù)都不穩(wěn)定，隨禁忌長度的變化波動很大;當(dāng)最佳匹配位置位于搜索空間的4個角時，鄰域大小取7×7時的運(yùn)行時間和收斂次數(shù)也不穩(wěn)定;相比較而言，鄰域大小取9×9時較為理想，此時禁忌長度可以取區(qū)間［2，7］內(nèi)的某一個值，算法在迭代150次以內(nèi)均能穩(wěn)定地收斂到最佳匹配值，耗時僅0.3 s左右。

用另外幾組圖像對上述得出的算法參數(shù)取值進(jìn)行驗證，結(jié)果均能收斂到與傳統(tǒng)的歸一化積相關(guān)算法相同的匹配結(jié)果，而耗時僅為傳統(tǒng)算法的1/8左右。當(dāng)參與匹配的圖像較大時，鄰域大小和禁忌長度也需要進(jìn)行相應(yīng)的調(diào)整，但也可以通過上述方法確定出算法的最佳參數(shù)值，并且能在滿足相同匹配精度的情況下，在匹配速度上得到明顯的提升。

4 結(jié)語

本文針對傳統(tǒng)的歸一化積相關(guān)圖像匹配方法執(zhí)行時間過長的問題，利用智能優(yōu)化方法中的禁忌搜索算法來優(yōu)化匹配的搜索過程，通過構(gòu)造候選解鄰域、兩種禁忌表、適值函數(shù)等實(shí)現(xiàn)了準(zhǔn)確快速的匹配。但本文提出的算法本質(zhì)上并不是一種隨機(jī)搜索算法，首先算法的初值是確定值，其次是算法每次執(zhí)行都能保證穩(wěn)定地得到相同的匹配結(jié)果。

［1］朱永松，國澄明.基于相關(guān)系數(shù)的相關(guān)匹配算法的研究［J］.信號處理，2003，19（6）：53l－534.

［2］張強(qiáng).圖像匹配算法研究［D］.西安電子科技大學(xué)，2006.

［3］BROWN L G.A survey of image registration techniques［J］.ACM Computing Surveys，1992，24（4）：325－376.

［4］汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法［M］.北京：高等教育出版社，2007.

［5］陳智.圖像匹配技術(shù)研究［D］.華中師范大學(xué)，2006.

［6］EPPLER W，PAGLIERONI D，HANSON J.GOES landmark positioning system［J］.SPIE Proceedings，1994，2812（2）：189－195.

［7］PRATT W.K.Correlation techniques of image registration［J］.IEEE Trans.Aerospace and Electronics System，1974，10（3）：243－256.

［8］TILION J C.Comparison of registration techniques for GOES visible imagery data［J］.Proceedings of IRW，1997，20（10）：133－136.

［9］韓冰，王永明.基于一種快速歸一化積相關(guān)算法的圖像匹配研究［J］.兵工學(xué)報，2010，31（2）：160－165.

Study on Application of Tabu Search Algorithm to Image Matching

CHENG Hong，CHEN Wen－jian
（DepartmentofSpecialty，TheAviationUniversityofAirForce，Changchun130022，China）

Search strategy is one of the main problems of image matching.It has great impacts on the execution speed and the final matching accuracy of the algorithm.In this paper，the idea of tabu search algorithm is applied to the search process of image matching，and it is promoted by constructing two different types of tabu lists：permanent tabu list and temporary tabu list.After each search process，the solutions in the candidate solution neighborhood are placed in different tabu lists.Then it accomplished the image matching accurately and quickly with the normalized product correlation as the criteria for similarity measurement.The results of experiment show that this method can overcome the shortcoming of time-consuming and large calculation amount of the traditional normalized product correlation algorithm，and greatly reduce the time spend in matching without losing the accuracy.

image matching;tabu search（TS）;normalized product correlation

TP751

A

1672－0504（2011）06－0032－04

2011－07- 03;

2011－09－22

全軍軍事學(xué)研究生課題（2010JY0844－500）

程紅（1969－），女，博士，教授，碩士生導(dǎo)師，從事遙感信息處理研究。E－mail：nanna1204＠163.com