程 紅，陳 文 劍

禁忌搜索算法在圖像匹配中的應用研究

程 紅，陳 文 劍

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

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

圖像匹配;禁忌搜索;歸一化積相關

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

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

1 歸一化積相關圖像匹配方法

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

歸一化積相關系數定義為：

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

2 禁忌搜索算法

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

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

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

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

3.1 獲取初始值

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

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

3.2 構造候選解鄰域

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

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

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

3.3 構造適值函數及禁忌表

本文直接用目標函數，即實時圖像與對應的基準子圖的歸一化積相關系數作為適值函數，評價候選解鄰域內所有可能的匹配點的優(yōu)劣。

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

3.4 渴望水平及停止準則

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

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

3.5 對比實驗

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

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

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

圖2 實驗所用的圖像Fig.2 The images used in experiment

表1 實驗參數和結果Table 1 The parameters and results of the experiment

3.6 實驗結果分析和參數確定

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

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

圖3 禁忌長度與運行時間的關系Fig.3 The relationship of tabu size and execution time

圖4 禁忌長度與收斂次數的關系Fig.4 The relationship of tabu size and convergence times

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

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

4 結語

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

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

［2］張強.圖像匹配算法研究［D］.西安電子科技大學，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］陳智.圖像匹配技術研究［D］.華中師范大學，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］韓冰，王永明.基于一種快速歸一化積相關算法的圖像匹配研究［J］.兵工學報，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

全軍軍事學研究生課題（2010JY0844－500）

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