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

徐 梅

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

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

1 圖像匹配及最優化核心技術

1.1 圖像匹配的通用流程

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

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

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

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

圖2經過NCC處理過的歸一化互相關矩陣平面效果圖

1.3 基于匹配梯度的改進型的歸一化互相關算法

圖3 基于匹配梯度的改進型的歸一化互相關算法流程圖

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

圖4基于匹配梯度的改進型的歸一化互相關算法處理效果圖

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

2.1 算法總體概述

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

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

2.2 基于模擬退火算法的變換參數全局最優搜尋子算法設計

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

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

ans.len = 0;

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

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

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

Print(ans, n);

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

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

%計算代價函數值

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%接受準則

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基于模擬退火算法的變換參數全局最優搜尋子算法效果圖圖7基于量子遺傳算法的高實時性圖像匹配子算法流程圖

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

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

3 圖像自動匹配系統設計

圖8 通用圖像自動匹配系統界面示意圖

圖9 極端環境下的系統效果示意圖

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

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

4 結論

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