徐 梅

(安徽新華學(xué)院 信息工程學(xué)院，安徽 合肥 230088)

隨著計算機(jī)視覺和圖像處理技術(shù)的蓬勃發(fā)展，圖像匹配技術(shù)作為其發(fā)展過程中的核心載體之一，應(yīng)用領(lǐng)域進(jìn)一步擴(kuò)展，在高精度導(dǎo)航定位、醫(yī)學(xué)器械成像處理、具有真實(shí)紋理特性的測繪作業(yè)等領(lǐng)域具有不可替代的作用[1-2]。各種圖像匹配算法雖然切入點(diǎn)不同，但都基于特征空間、相似性度量、等價變換、最優(yōu)化變換參數(shù)搜尋等四要素。傳統(tǒng)的圖像匹配算法主要分為基于先驗(yàn)?zāi)０搴突趥€性特征的圖像匹配算法，這兩類算法具有較好的匹配精度，但是其計算過程繁瑣，導(dǎo)致實(shí)時性較差；最優(yōu)化變換參數(shù)搜尋易出現(xiàn)早熟收斂且易陷入局部最優(yōu)陷阱，導(dǎo)致匹配效果不佳[3-5]。在此背景下，綜合考慮模擬退火算法與量子遺傳算法存在的優(yōu)勢與不足，提出了一種基于模擬退火算法與量子遺傳算法的圖像匹配混合算法，可以克服模擬退火算法的收斂速度慢與量子遺傳算法的局部搜尋能力弱等單一算法的固有劣勢，從而較好地解決了傳統(tǒng)圖像匹配算法存在的諸多問題。通過在Matlab2015b環(huán)境下開發(fā)GUI驗(yàn)證界面，從多角度驗(yàn)證了論文所提算法的有效性，實(shí)際驗(yàn)證結(jié)果表明，論文所提算法魯棒性較好，匹配精度、實(shí)時性等評價參數(shù)滿足設(shè)計需求，具有一定的推廣價值。

1 圖像匹配及最優(yōu)化核心技術(shù)

1.1 圖像匹配的通用流程

圖像匹配的主要意義在于消除由于圖像獲取實(shí)體不同、外界環(huán)境差異等因素對同一實(shí)體的影響而造成的外在差異，針對同一實(shí)體的圖像特征，對兩幅不同獲取實(shí)體、具有明顯外界環(huán)境差異的圖像進(jìn)行一致化[6]，獲取序列圖像中的固有相似特征，從而實(shí)現(xiàn)高效率圖像匹配。圖像匹配算法一般涉及以下要素：S1：特征空間，可以分為局部和全局特征空間，特征空間的主要作用是把原始圖像的低緯特征映射到高緯度空間，是對具體特征的抽象化；S2：相似性度量，常用的相似性度量函數(shù)主要分為代價函數(shù)和距離函數(shù)，用來度量特征之間的相似程度；S3：搜索空間，搜索空間是圖像匹配過程中由相似參數(shù)組成的多維空間[7]，是進(jìn)行全局最優(yōu)參數(shù)搜索的限制空間；S4：搜索策略，選擇合適的最優(yōu)化參數(shù)搜尋算法基于搜索空間進(jìn)行圖像變換相似值最大參數(shù)搜尋。與圖像匹配上述要素相吻合，圖像匹配的通用流程如圖1所示。

圖1圖像匹配的通用流程示意圖

1.2 圖像匹配的相似性測度方法

圖像匹配的相似性測度方法較多，合理地選取圖像匹配的相似性測度方法對圖像匹配的效率和質(zhì)量至關(guān)重要?；诜€(wěn)定性和精度的考慮，選擇歸一化互相關(guān)算法(NCC)來進(jìn)行圖像匹配的相似性測度，詳細(xì)步驟如下：S1：對匹配圖像和待匹配圖像進(jìn)行平均平滑濾波處理，保證兩幅圖像相似矩陣具有相關(guān)性；S2：基于預(yù)處理過的具有相似矩陣的匹配圖像和待匹配圖像，進(jìn)行歸一化處理，得到歸一化互相關(guān)矩陣；S3：分別對匹配圖像和待匹配圖像的歸一化互相關(guān)矩陣進(jìn)行對應(yīng)位置行與列的最大值及索引規(guī)則的建立，得出匹配圖像中的固定一點(diǎn)與待匹配圖像中任意一點(diǎn)相似性極大值；S4：根據(jù)步驟S3制定的索引規(guī)則，兩圖像對應(yīng)點(diǎn)索引一致，則為一對初始匹配點(diǎn)對，至此，索引第一個循環(huán)結(jié)束；S5：不斷重復(fù)步驟S1-S4，循環(huán)求出一一匹配的點(diǎn)對。經(jīng)過歸一化互相關(guān)算法處理過的匹配圖像和待匹配圖像的歸一化互相關(guān)矩陣平面圖效果如圖2所示。

圖2經(jīng)過NCC處理過的歸一化互相關(guān)矩陣平面效果圖

1.3 基于匹配梯度的改進(jìn)型的歸一化互相關(guān)算法

圖3 基于匹配梯度的改進(jìn)型的歸一化互相關(guān)算法流程圖

歸一化互相關(guān)算法(NCC)雖然具有較高的匹配精度和效率，但是由于其計算量較為復(fù)雜，導(dǎo)致匹配實(shí)時性無法滿足航天測繪等對實(shí)時性要求較高的領(lǐng)域，一定程度上制約了歸一化互相關(guān)算法(NCC)的應(yīng)用范圍?；谏鲜霰尘?，提出了一種基于匹配梯度的改進(jìn)型的歸一化互相關(guān)算法(TNCC)，如圖3所示，改進(jìn)后的算法詳細(xì)步驟如下：S1：對匹配圖像和待匹配圖像進(jìn)行平均平滑濾波處理，保證兩幅圖像相似矩陣具有相關(guān)性；S2：引入匹配梯度因子，根據(jù)經(jīng)過平均平滑濾波處理的匹配圖像和待匹配圖像的空間信息大小和方向確定匹配梯度因子，并確定與索引規(guī)則之間的對應(yīng)關(guān)系；S3：對相似矩陣進(jìn)行歸一化處理，得到歸一化互相關(guān)矩陣，根據(jù)匹配梯度因子大小，確定索引規(guī)則，確保匹配點(diǎn)索引的實(shí)時性；S4：根據(jù)索引規(guī)則，尋找匹配圖像中的固定一點(diǎn)與待匹配圖像中任意一點(diǎn)相似性極大值，重復(fù)上述步驟，直到識別到初始點(diǎn)為止。根據(jù)上述流程，在Matlab環(huán)境下編程實(shí)現(xiàn)，效果如圖4所示。由圖可知，基于匹配梯度的改進(jìn)型的歸一化互相關(guān)算法的實(shí)時性具有較大幅度的提高。

圖4基于匹配梯度的改進(jìn)型的歸一化互相關(guān)算法處理效果圖

2 基于模擬退火算法與量子遺傳算法的圖像匹配

2.1 算法總體概述

基于模擬退火算法與量子遺傳算法的圖像匹配算法主要包括基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法、基于量子遺傳算法的高實(shí)時性圖像匹配子算法兩部分，如圖5所示。其中，基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法用來從全局層面搜尋變換參數(shù)的最優(yōu)解，主要包含溫度T的初始值設(shè)置子問題、基于退火平衡策略的退火速度設(shè)置子問題、溫度管理子問題等，可以避免變換參數(shù)陷于局部最優(yōu)；基于量子遺傳算法的高實(shí)時性圖像匹配子算法主要用來解決圖像匹配高速率問題，主要包含初始父代染色體選取子問題、與量子位相對應(yīng)的狀態(tài)適應(yīng)度求解子問題、遺傳變異代數(shù)的選取子問題、最佳適應(yīng)度終止條件選取子問題等，可以有效改善圖像匹配的實(shí)時性問題。為了保證算法執(zhí)行效率，采用接續(xù)模式，基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法、基于量子遺傳算法的高實(shí)時性圖像匹配子算法按序執(zhí)行，形成具有良性循環(huán)的接續(xù)結(jié)構(gòu)，使算法整體向著最優(yōu)解方向迭代。

圖5基于模擬退火算法與量子遺傳算法的圖像匹配算法總體示意圖

2.2 基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法設(shè)計

基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法可以克服量子遺傳算法易陷于局部最優(yōu)這一固有缺點(diǎn)，實(shí)現(xiàn)變換參數(shù)全局最優(yōu)搜尋，子算法的詳細(xì)實(shí)現(xiàn)方法如下：S1：確定目標(biāo)函數(shù)，本文對應(yīng)的目標(biāo)函數(shù)是變換參數(shù)全局最優(yōu)搜尋函數(shù)，需要將目標(biāo)函數(shù)編寫為M文件或inline函數(shù)，以供在Matlab環(huán)境下調(diào)用；S2：確定退火溫度，退火溫度一方面可以確定對新解的接受概率，另一方面，限制當(dāng)前解與新解之間的搜索半徑，即確定搜索范圍，其中接受新解的概率由Meteopolis準(zhǔn)則確定，退火溫度的初始值由溫度單位時間內(nèi)下降速率決定；S3：確定退火進(jìn)度表，退火進(jìn)度表由溫度隨著算法迭代的下降速度決定，退火過程越緩慢，SA找到全局最優(yōu)解的機(jī)會就越大，對應(yīng)的運(yùn)行時間也會增加。退火進(jìn)度表包括初始溫度和溫度更新函數(shù)等參數(shù)。與上述過程相對應(yīng)，核心代碼如下：

swap(ans.citys[x], ans.citys[y]);

ans.len = 0;

for(int i = 0; i < n - 1; i++) %確定目標(biāo)搜尋函數(shù)

ans.len += w[ans.citys[i]][ans.citys[i + 1]]; %確定退火溫度

cout << "nCase = " << nCase << endl;

Print(ans, n);

nCase++; %確定迭代下降速度

c1=c(1);c2=c(2);

%計算代價函數(shù)值

df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));

if df<0%接受準(zhǔn)則

S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]；

Sum=Sum+df;

elseif exp(-df/T)>rand(1)%以概率exp(-df/T)接受新的路徑%注意時elseif而不是else if

S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]；

圖6基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋子算法效果圖圖7基于量子遺傳算法的高實(shí)時性圖像匹配子算法流程圖

2.3 基于量子遺傳算法的高實(shí)時性圖像匹配子算法設(shè)計

基于量子遺傳算法的高實(shí)時性圖像匹配子算法可以克服模擬退火算法實(shí)時性較差、早熟收斂等固有缺點(diǎn)，實(shí)現(xiàn)圖像匹配的高實(shí)時性，如圖7所示，子算法的詳細(xì)實(shí)現(xiàn)方法如下S1：根據(jù)當(dāng)前選擇的變換參數(shù)全局最優(yōu)搜尋算法確定并初始化父代染色體；S2：對初始父代染色體進(jìn)行量子位測量并得到與其對應(yīng)的狀態(tài)，對每個狀態(tài)計算適應(yīng)度，記錄最佳個體及適應(yīng)度；S3：根據(jù)上文給出的模擬退火表，確定需要迭代的遺傳進(jìn)化代數(shù)，其中采用量子旋轉(zhuǎn)門對每一代染色體進(jìn)行遺傳變異，確保算法實(shí)時性；S4：根據(jù)圖像匹配實(shí)時性效果確定迭代終止條件，輸出最佳個體及適應(yīng)度。

3 圖像自動匹配系統(tǒng)設(shè)計

圖8 通用圖像自動匹配系統(tǒng)界面示意圖

圖9 極端環(huán)境下的系統(tǒng)效果示意圖

為了實(shí)際驗(yàn)證上文所提算法的有效性和實(shí)用性，本文在Matlab環(huán)境下調(diào)用圖形化開發(fā)插件GUI開發(fā)了一款通用圖像自動匹配系統(tǒng)，該系統(tǒng)可以實(shí)現(xiàn)通用匹配圖像與待匹配圖像之間的格式化預(yù)處理、特征參數(shù)的提取與描述、相似性參數(shù)的提取與描述、基于模擬退火算法的變換參數(shù)全局最優(yōu)搜尋、基于量子遺傳算法的高實(shí)時性圖像匹配等通用圖像自動匹配的全流程，系統(tǒng)實(shí)際運(yùn)行界面如圖8所示。

為了進(jìn)一步驗(yàn)證系統(tǒng)在非正常環(huán)境下的性能，選取對圖像匹配影響較大的因素(選取圖像特征點(diǎn)數(shù)量和迭代次數(shù))進(jìn)行控制變量驗(yàn)證，具體做法為：選取具有多維特征點(diǎn)的復(fù)雜圖像重復(fù)上述處理過程，控制迭代次數(shù)為標(biāo)準(zhǔn)迭代次數(shù)的二分之一，觀察圖像匹配效果，由此可以得出文中所提算法在極端條件下的性能，對表征系統(tǒng)的整體性能和魯棒性具有積極意義。試驗(yàn)結(jié)果如圖9所示。

4 結(jié)論

本文提出了一種基于模擬退火算法與量子遺傳算法的圖像匹配混合算法，該混合算法融合兩種算法的優(yōu)點(diǎn)，克服單一算法的缺點(diǎn)，可以實(shí)現(xiàn)全局最優(yōu)，具有匹配精度高、抗干擾性強(qiáng)、并行搜索效率高等優(yōu)勢。在此基礎(chǔ)上，本文在Matlab環(huán)境下調(diào)用GUI圖形化插件開發(fā)了一款通用圖像自動匹配系統(tǒng)，并對系統(tǒng)的性能進(jìn)行了實(shí)際測試。實(shí)際測試表明，基于模擬退火算法與量子遺傳算法的圖像匹配混合算法精度高、信息需求量較小、匹配效率較高，匹配出的圖像信息紋理清晰，配準(zhǔn)效果較好，可以滿足高精度導(dǎo)航定位、醫(yī)學(xué)器械成像處理、具有真實(shí)紋理特性的測繪作業(yè)等領(lǐng)域的應(yīng)用需求，具有一定的實(shí)際推廣價值。