摘  要： 為了降低圖像配準誤匹配率以及減少RANSAC算法特征優(yōu)化迭代次數(shù)，提出了SIFT-FCACO的圖像配準算法，用快速收斂的蟻群算法對圖像匹配后的特征點對進行優(yōu)化。實驗結果表明，該算法不僅減少了匹配時間，而且提高了匹配的準確率。

　　關鍵詞： SIFT-FCACO算法；蟻群算法；圖像配準

　　圖像配準是指將采集到的兩幅或多幅圖像進行空間變換，利用相關性尋找像素間的對應關系，從而確定幾何變換模型的過程。一般將圖像的配準方法分成基于灰度信息的圖像配準方法、基于變換域的圖像配準方法、基于特征的圖像配準方法三種[1-2]，其中基于特征的圖像配準方法在圖像拼接中得到了廣泛的應用。2004年LOWE D G提出的尺度不變特征變換算法（SIFT）[3]對圖像的尺度和旋轉具有不變形，被廣泛應用于圖像拼接。但傳統(tǒng)的SIFT算法在圖像配準階段誤匹配率比較高，并且傳統(tǒng)RANSAC算法[4]在誤匹配點比例較大時，特征優(yōu)化迭代次數(shù)多，大大影響了拼接算法的效率。20世紀90年代初，意大利的DORIGO M、MANIEZZO V和COLORNI A等著名學者提出一種用來在圖像中搜索優(yōu)化路徑的機率型仿生進化算法——蟻群算法（Ant Colony Algorithm）[5]，該算法是群體智能領域主流的新型研究方法。

　　針對傳統(tǒng)的SIFT算法在圖像配準階段誤匹配率比較高以及RANSAC算法特征優(yōu)化迭代次數(shù)多，從而導致圖像拼接后在重疊區(qū)域容易出現(xiàn)拼接縫的問題，本文提出SIFT-FCACO的圖像配準算法，對SIFT特征匹配算法進行了改進，利用快速收斂的蟻群優(yōu)化算法FCACO（Fast Convergence Ant Colony Optimization Algorithm）來優(yōu)化匹配點對。仿真實驗證明，改進后的匹配方法不僅能有效地剔除誤配點，而且減少了匹配時間。

　　1 SIFT算法

　　1.1 尺度空間極值點檢測

　　SIFT算法建議，在某一尺度通過引入一種新算子——DOG算子（Difference of Gaussians，高斯差分算子）來檢測特征點，該算子只需對平滑后的相鄰尺度高斯圖像作減法計算，得到相鄰尺度圖像的差異信息，其優(yōu)點是計算簡單、速度快[6]。DOG函數(shù)表達式為：

　　其中，k是常數(shù)，表示相鄰層之間的間隔距離，k=21/s，本文中s=2。

　　對高斯差分金字塔尺度空間中的每個像素點和與它相同層的8個相鄰像素點以及與其相鄰上下兩層的18個像素點，總共26個相鄰像素點進行比較，看此像素點是否為它的圖像空間或者尺度空間的極大值或者極小值，如果該點是極值點，則確定該點作為候選點。

　　1.2 精確定位特征點

　　由于上述特征檢測是在離散空間進行的，得到的候選極值點中有許多不是真正的極值點，而是隨機噪聲和邊緣響應[7]，因此需要進一步優(yōu)化匹配點對以使匹配的穩(wěn)定性更好，提高算法的抗噪聲能力。通過擬合三維二次函數(shù)來精確確定特征點的位置和尺度，即對泰勒二次展開式（2）求極值，同時去除低對比度的極值點，并利用Hession矩陣的跡與行列式的比值去除不穩(wěn)定的邊緣響應點。

　　1.3 生成特征描述符

　　為了使檢測到的特征點保持一定的方向不變性，需要根據(jù)圖像的局部特征規(guī)定每個特征點的方向。特征點（x，y）處的梯度幅值和相位按式（3）、（4）進行計算：

　　其中，m（x，y）表示特征點的梯度幅值，θ（x，y）表示其相位方向。

　　為了使特征點可以適應圖像的方向變化，需要將特征點沿主方向順時針旋轉角度θ，提取特征點的特征向量過程如下：

　?。?）以特征點為中心，選取大小為16×16的窗口區(qū)域，高斯加權圖像窗口區(qū)域（窗口大小為8×8）內各像素點（不包括像素點所在行和列的點）與特征點間隔距離越小，對其貢獻越大，反之則越小。生成的特征點描述符如圖1所示。

　?。?）將大小為16×16的窗口平均分成16個小塊，每個小塊的大小為4×4，對每小塊8個方向的梯度進行計算并且對其累加，于是在特征點大小為16×16的窗口內總共能夠生成4×4×8=128個數(shù)據(jù)，即每個特征點可以生成128維的特征向量，用特征點描述符A=（α1，α2，…，α128）來表示。

　　（3）為了去掉光照變化的影響，將特征向量的長度進行歸一化。假如一幅圖像共有n個特征點，那么這幅圖像的全部特征向量就組成了初始匹配數(shù)據(jù)的矩陣集合，大小為128×n，其中的每一列就表示一個特征點描述子。

　　1.4 SIFT特征匹配

　?。?）本文采用歐式距離作為待匹配圖像和模板圖像中生成的128維特征向量描述子的相似性度量方法[8]，任意兩個待匹配描述子的歐氏距離為：

　　2 FCACO特征點對優(yōu)化算法

　　通過上述特征匹配后得到了一系列特征點對，但是在匹配過程中由于受到各種外界或者內在因素的影響，容易產生大量的誤配點，影響后續(xù)的圖像拼接過程。同時，現(xiàn)有提純誤配點的RANSAC算法在求解最佳模型的過程中，假如初始數(shù)據(jù)集合內點概率較低時，不僅需要比較多的迭代次數(shù)，而且還可能無法收斂到最優(yōu)解，因此要對匹配的特征點對進行優(yōu)化。本文提出一種用FCACO算法優(yōu)化匹配點對的方法，具體過程如下：

　?。?）初始化參數(shù)：包括螞蟻數(shù)量m、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素蒸發(fā)系數(shù)ρ、信息素總量Q、最大迭代次數(shù)iter_max、迭代次數(shù)初始值iter=1。

　　（2）構建螞蟻城市模型：在兩幅圖像上利用蟻群作為搜索窗口，SIFT算法匹配出的特征點Ri（i=1，2，…，m）被看作m只螞蟻，根據(jù)圖像S中的窗口在模板圖像R中搜索食物的迭代過程建立“i只螞蟻的城市模型”，將m只螞蟻Ri隨機放于n個城市（m≤n），并將螞蟻聚類到j個聚類中心Sj（j=1，2，…，k），為每只螞蟻建立禁忌表tabuk（k=1，2，…，m），并用禁忌表中存儲的初始節(jié)點信息來記錄螞蟻目前已經走過的城市。假如算法中的每一只螞蟻都有一定的記憶功能，可以按照兩幅待拼接圖像上的灰色關聯(lián)度大小來引導螞蟻搜索并且向特定的方向移動，最終朝著灰色關聯(lián)度最大的方向搜索，從而確定出兩幅圖像之間匹配點對。

　?。?）構造螞蟻灰色關聯(lián)度Di，j，并將灰色關聯(lián)度作為相似性函數(shù)，從距離空間的角度反映系統(tǒng)因素間的關聯(lián)性：

　　其中，d（Ri，Sj）為待優(yōu)化特征點對間灰色關聯(lián)度距離；min d（Ri，Sj）為待優(yōu)化特征點對間灰色關聯(lián)度距離的最小值，maxd（Ri，Sj）為待優(yōu)化特征點對間灰色關聯(lián)度距離的最大值。

　?。?）螞蟻搜索過程：搜索過程當中的狀態(tài)轉移概率由道路上的信息量和路徑的啟發(fā)信息決定，i城市的第k只螞蟻選擇下一個城市j的概率分別為：

　　其中，p為狀態(tài)轉移概率；α為信息素的重要程度因子，其值越大，表示信息素的濃度在轉移中起的作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉移過程中所起的作用越大；allowk為第k只螞蟻可以訪問的城市集合，初始狀態(tài)，allowk中有n-1個集合，也就是包括除去螞蟻k出發(fā)城市的其余所有城市，隨著時間的推移，allowk中的元素逐漸減少，直到所有的城市全部訪問完成之后變?yōu)榭占沪菫閱l(fā)函數(shù)表達式，代表螞蟻由城市i轉移到城市j的期望程度，由兩個特征點對之間的灰色關聯(lián)度大小Di，j決定。

　?。?）更新信息素重要程度因子：當信息素達到某一臨界值后，隨著信息素重要程度因子α逐漸變大，這條路徑被選擇的概率逐漸變小，算法的全局搜索能力由弱變強，慢慢地跳出局部最優(yōu)解，直到求得全局最優(yōu)解。當算法在N次循環(huán)之內沒有改進當前最優(yōu)解時，信息素重要程度因子的取值范圍進行變換，即：

　　其中，ρ為信息素蒸發(fā)系數(shù)，0≤ρ≤1；τ為窗口信息素含量，?駐τijk為第k只螞蟻在城市i與城市j連接路徑上釋放的信息素濃度；?駐τij為所有螞蟻在城市i與城市j連接路徑上釋放的信息素濃度之和；Q為常數(shù)，為螞蟻循環(huán)一次所釋放的信息素總量。

　　由于信息素揮發(fā)因子ρ的參數(shù)取值范圍小，因此需要對它進行微調。當ρ過小時，在各路徑上殘留的信息素過多，導致以前搜索過的路徑被選擇的概率增大，使全局搜索能力減??；當ρ過大時，各路徑的信息素堆積速度慢，以犧牲收斂速度為代價來增強算法的全局搜索能力。本文算法將自適應地修改ρ：

　　其中，ρmax=0.9；δ是一個常數(shù)，δ≥1，經試驗，本文取δ=1.01。

　?。?）判斷是否停止搜索：如果iter≤iter_max，則令iter+1，清空螞蟻經過路徑的禁忌表，返回步驟（2）；否則停止搜索，輸出結果。

　　SIFT-FCACO算法優(yōu)化匹配點對的流程圖如圖2所示。

　　3 實驗結果及分析

　　為了驗證本文算法對光照的魯棒性，采用本文提出的SIFT-FCACO圖像匹配算法與一般的SIFT-RANSAC圖像匹配算法進行對比實驗。實驗所用的圖像為不同光照強度下拍攝的兩幅圖像，尺寸大小均調整為400×300，圖像格式為JPG，圖像如圖3所示，其中圖3（a）為天氣晴朗的中午拍攝的圖像，圖3（b）是下午五點左右拍攝的圖像，分別利用SIFT-RANSAC圖像匹配算法和SIFT-FCACO圖像匹配算法進行實驗，效果如圖4、圖5所示。

　　圖4（c）是采用經典的SIFT-RANSAC算法得到的匹配效果圖，圖5（c）為本文算法得到的匹配效果圖。從提取的特征點進行分析，圖4（a）中提取的特征點比圖5（a）中的特征點要多一些；從匹配的特征點數(shù)進行分析，圖4（b）、4（c）中的特征點雖然多，但是誤匹配也多，這將導致誤匹配率較高；圖5（b）、5（c）在特征點幾乎相同的情況下錯誤匹配并未增加，從而降低了誤匹配率。

　　不同工作狀態(tài)的計算機硬件設備對軟件運行速度的影響會有一定的差異，因此表1中的數(shù)據(jù)是在對整個實驗運行10次計算平均值的結果，其中匹配率為優(yōu)化后匹配對數(shù)與特征個數(shù)中較小值之比。從表1可以得出，SIFT-FCACO算法提純的誤配點對比較多，對光照、位移、尺度變化均保持一定的魯棒性，經過本文算法優(yōu)化誤配點對后，有效地提高了匹配效率，減少了匹配時間，更有利于后續(xù)的圖像拼接過程。

　　針對一般的SIFT和RANSAC算法在配準精度與速度上的不足，本文提出了一種SIFT-FCACO的圖像匹配算法，憑借SIFT特征對于旋轉和尺度的不變性以及對于噪聲、亮度變化等魯棒性良好的優(yōu)勢進行特征提取和匹配，并設計了一種FCACO算法進一步優(yōu)化SIFT匹配的特征點對，從而提取出具有較大信息量的匹配點對，有利于圖像拼接的進行。

　　參考文獻

　　[1] ZITOVA B， FLUSSER J. Image registration methods： a survey[J]. Image and Vision Computing（S0262-8856），2003，21（11）：977-1000.

　　[2] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision（S0920-5691），2004，60（2）：91-110.

　　[3] Deng Rongfeng， Li Xiying. Robust image mosaic algorithm based on SIFT feature matching[J]. Journal of Computer Applications， 2009，29（6）：219-221.

　　[4] Chen Fuxing， Wang Runsheng. Fast RANSAC with preview model parameters evaluation[J]. Journal of Software，2005，16（8）：1431-1437.

　　[5] 何志明.群體智能算法在圖像匹配中的應用[D].西安：陜西師范大學，2010.

　　[6] 王靜.基于SIFT和角點檢測的自動圖像配準方法研究[D].武漢：華中科技大學，2010.

　　[7] Sun Wei， Guo Baolong. A robust object detecting and tracking method[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery， USA， IEEE Computer Society， 2009：121-125.

　　[8] 曹建秋.基于SIFT圖像拼接技術研究[D].重慶：重慶交通大學，2012.