侯堅，張明（上海海事大學信息工程學院，上海 201306）

一種蟻群優(yōu)化的改進SIFT特征點的圖像配準算法

侯堅，張明
（上海海事大學信息工程學院，上海 201306）

為減少圖像配準的匹配時間，提高圖像配準的匹配率，提出一種蟻群優(yōu)化的SIFT圖像配準算法。首先采用內(nèi)核投影算法Walsh-Hadamard對SIFT特征描述子進行降維，然后采用優(yōu)化的蟻群算法針對初匹配點進行提純，提高匹配率。實驗結果證明，改進后的算法與采用RANSAC算法提純的SIFT算法相比，不僅提高匹配的正確性，而且也有效縮短算法的運算時間。

SIFT；圖像配準；蟻群優(yōu)化算法；內(nèi)核投影

0　引言

圖像拼接技術作為計算機視覺領域研究最早和最廣泛的方向之一，在虛擬現(xiàn)實、醫(yī)學圖像處理、三維重建、遙感圖像處理中有著極其廣泛的應用和研究［1］。圖像拼接是將多幅有重疊區(qū)域的圖像匹配融合為一張高分辨率的寬視角的圖像，以極大地滿足了人們對大視野的要求。但是拼接所處理的圖像會因為各種因素而存在不同的差異性，如時間、光照、分辨率、拍照角度、傳感器等。拼接的主要目的就是消除這些差異性，得到自然平滑的拼接圖像。國內(nèi)外學者已提出多種圖像拼接算法，其改進都是為了提高拼接的速度和配準的精度，以得到最好的效果為最終目的。

圖像拼接的主要流程為：對圖像進行去噪等預處理、采用特征點檢測算法進行特征點的檢測與提取、針對特征點進行特征匹配、采用圖像融合算法對匹配后的圖像進行拼接。其中，圖像配準作為拼接的核心，配準的速度和精度直接影響到后續(xù)的融合過程。一般情況下，將圖像配準劃分成以灰度信息、變換域和特征為特點的三類配準算法。在圖像拼接中，根據(jù)特征的圖像配準方法應用最為廣泛。而Lowe D.G提出了一種引入尺度空間理論的尺度不變特征變換（SIFT）算法［2］，經(jīng)過1999年的理論提出，以及2004年完善后的發(fā)表使得尺度不變性特征開始應用到特征點的檢測中。SIFT算子本身具有尺度不變性和旋轉不變性，此外對于仿射變換和光照變化也具有較好的不變性，使其被廣泛應用于圖像配準和圖像拼接等技術中。

研究者們在對SIFT算法的研究中發(fā)現(xiàn)，SIFT算法生成的特征描述算子高達128維，高維使得計算復雜度更高，而在特征匹配階段，也會使得誤匹配率增大。人們針對這一問題，引入RANSAC來改善誤匹配增高。但是傳統(tǒng)的RANSAC算法［3］在誤匹配點比例較大的情況時，會增加特征優(yōu)化迭代的次數(shù)，這樣使得匹配時間延長，從而較大地降低了匹配的效率。

針對傳統(tǒng)的SIFT算法產(chǎn)生高維描述算子，以及RANSAC算法存在的無法快速地收斂到最佳解時，就會通過迭代的次數(shù)的增加來求解，這樣就極大地影響了配準的效率。本文提出一種蟻群優(yōu)化的改進SIFT特征描述子的圖像配準算法，對SIFT特征描述子，采用內(nèi)核投影算法來對SIFT算子進行特種描述，從而避免了SIFT描述子的高維災難，使得初始匹配時的計算量大大減少；在特征匹配階段，利用改進的蟻群算法來優(yōu)化初始匹配點對。仿真實驗證明，改進后的圖像配準方法不僅有效地剔除誤匹配點對，降低了誤匹配點對數(shù)，而且也有效地縮短了配準過程中的匹配的時間。

1　傳統(tǒng)的SIFT算法

1.1SIFT特征點提取

（1）尺度空間極值點檢測

SIFT算法首先將原圖像放大為原來的兩倍，然后通過對圖像進行不同尺度的高斯平滑（模糊）處理和降采樣，得到高斯金字塔，即高斯尺度空間。

其中，I（x，y）為輸入的圖像，*為卷積，σ為可變核，即尺度空間因子，σ的大小決定了圖像的平滑程度，它對應了圖像的概貌特征和細節(jié)特征。當σ連續(xù)變化時，L（x，y，σ）構成的圖像組即為尺度空間。

SIFT算法通過在同一尺度下對兩個相鄰的高斯尺度空間的相減，從而得到高斯差分（DoG）的響應值，即高斯差分尺度空間D（x，y，σ），然后通過對高斯尺度空閑圖像進行局部最大化搜索，根據(jù)空間位置和尺度空間確定局部特征點。D（x，y，σ）表達式如下：

其中，k為常數(shù)因子，表示相鄰的兩個尺度空間的間隔。

在高斯差分尺度空間中，關鍵點的確定是以比較空間內(nèi)的是否為極值點確定的。每個待檢測像素點與當前所在圖像中的8鄰域內(nèi)像素點，以及9個鄰域規(guī)模的上下相鄰的同一組的像素點進行比較。只有當它大于或者小于這些鄰域點時，才被認為是極值點，這樣的操作不會帶來很大的成本，由此可以得到候選關鍵點。

（2）關鍵點定位

由于關鍵點是在離散空間中進行計算，得到的候選關鍵點中存在許多不是真正的極值點，而是隨機產(chǎn)生的噪聲點和以及圖像的邊緣響應［4］，如低對比度的關鍵點，因為DoG的邊緣相應而產(chǎn)生的不穩(wěn)定的邊緣響應點等。因此在得到候選關鍵后，需要將其擬合到像素附近的位置、尺度和主曲率。這個操作可以允許其過濾掉具有低對比度或沿邊緣被定位不佳的響應點。算法通過三維二次擬合函數(shù)來精確關鍵點的位置和尺度，同時設置閾值來去除不穩(wěn)定的相應點。

算法由三維二次擬合函數(shù)來精確關鍵點的位置和尺度，具體做法是對（3）式的泰勒二次展開式求極值。

對⑷式進行求導，得到極值點以及對應的極值，通過對X進行修改已得到的局部最優(yōu)點，剔除低對比度的極值點，并利用Hessian矩陣的跡與行列式的比值表示的主曲率來剔除不穩(wěn)定的邊緣響應點。其中，Hessian矩陣為：

Hessian矩陣的跡和行列式為：

實驗中主曲率的選取范圍一般為6～10。

（3）確定關鍵點的方向

根據(jù)關鍵點的圖像屬性像素為每一個關鍵點分配一個一致的方向，然后關鍵點描述符可以相對于這個方向來描述，這樣實現(xiàn)圖像的旋轉不變性。像素點處的梯度值（x，y，σ）以及方向θ（x，y）的計算如下：

一個方向直方圖通過圍繞關鍵點鄰域內(nèi)進行采樣獲取梯度方向生成的。將360°平分成36柱，然后對每一個鄰近特征點的采樣點進行σ為1.5倍的高斯加權圓形窗口加權，按照相對于中心關鍵點梯度方向的信息貢獻，設置權值的變化，即隨著采樣點距離關鍵點的增加而變小。方向直方圖的峰值對應于局部梯度的主方向。此外，其他任何局部峰值也就是最高峰值的80%用來創(chuàng)建幅方向。雖然僅有約15%被分配了多個方向，但是這些貢獻增強了匹配的穩(wěn)定性。如下圖所示，使用lena圖進行檢測，提取出SIFT特征點的關鍵點方向顯示圖。由圖（1）中顯示的特征描述算子可以看出，存在有多個方向的特征點。

圖1　SIFT算法生成的主方向特征圖

（4）特征描述符

首先為了實現(xiàn)取向不變性，特征點的坐標和梯度方向是相對于關鍵點的主方向轉動的。然后如圖2中2×2種子點圖像所示，在以關鍵點為中心的區(qū)域，取8× 8的窗口，在圖2中第一幅圖像的梯度幅值和取向圍繞關鍵點位置進行采樣，使用關鍵點的尺度來選擇高斯模糊來對圖像進行濾波。然后采用三線性插值來計算每個梯度樣本的值并將其累加到箭頭代表的方向上，從而得到第二幅圖中顯示的直方圖。高斯模糊計算后就得到了一個種子點。這樣描述符就從包含梯度直方圖的向量中生成了。圖2中一個關鍵點由2×2個種子點組成，每個種子點具有8個方向的向量信息。但是為了使算法的匹配性能更穩(wěn)定，Lowe使用了4×4個種子點來描述特征點，這樣每個特征點就形成了4×4×8= 128維的描述子。

圖2　圖像特征點梯度方向及高斯加權后的主方向

圖3　SIFT特征描述子構造窗口

通過SIFT算法生成的SIFT特征描述子，就具有了特征點的位置信息、尺度信息和方向信息，而且向量去除了尺度變化和旋轉變化對特征點的影響。通過將特征描述子進行歸一化處理，可以去除光照變化的影響。

1.2SIFT特征匹配

SIFT算法采用歐氏距離作為兩幅圖像特征描述子的相似性度量方法。

當設定的閾值T的參數(shù)減小時，誤匹配點對數(shù)目會減少，但是同時也剔除了正確匹配點對的數(shù)目；反之，當設定的閾值T增大時，會迅速增加誤匹配點對的數(shù)目，這將極大影響結果的配準效果。

通過對閾值修改實驗表明，當閾值T選取的范圍在0.4～0.6之間的時候，特征匹配的效果是最佳的，而Lowe作者選取的0.8的實驗效果，雖然得到的匹配的特征點數(shù)目多，但是同時也存在著大量的錯誤匹配點。所以本文根據(jù)實驗效果將閾值設置為0.6。

通過歐氏距離的到匹配的特征點對后，有學者通過RANSAC算法對這些匹配的特征點對進行提純，以剔除錯誤的匹配點對?，F(xiàn)有提純算法RANSAC算法，雖然在通常情況下取得了較好的效果，但是在求解最佳模型的情況時，當出現(xiàn)初始數(shù)據(jù)集合內(nèi)的特征點的概率較低的情況時，在增加更多的迭代次數(shù)后，其結果可能獲取不到收斂到最優(yōu)解的解決方案，從而導致提純的特征點對人存在誤匹配點對，影響圖像拼接的效果。

根據(jù)歐氏距離計算兩個特征點之間的相似性，若最鄰近點與次鄰近點的歐氏距離的比值小于所設定的閾值，則認為兩特征點匹配成功。

2　改進的SIFT圖像配準算法

雖然傳統(tǒng)的SIFT算法可以生成大量穩(wěn)定的特征點，但是主要依賴的是主方向旋轉和使用直方圖的方法生成的特征描述算子，產(chǎn)生了128維的特征描述子，使得在后期的圖像配準進行特征匹配時，增加了極大的運算量，影響了配準算法的時效性。所以現(xiàn)有的改進方法主要針對其高維度的問題進行相關的改進，并且取得了較好的結果?；诂F(xiàn)有的改進結果，本文研究決定，采用內(nèi)核投影對描述子進行降維來降低計算量。

2.1Walsh-Hadamard內(nèi)核投影

Walsh-Hadamard內(nèi)核是Gray-Code內(nèi)核投影的特例。首先，W-H內(nèi)核投影非常利于生成和應用。一維內(nèi)核可以通過連續(xù)使用二叉樹生成相關的內(nèi)核［5］。在二維的圖像處理上，二維內(nèi)核可以通過一位內(nèi)核的外積生成。W-H內(nèi)核的所有坐標都是由+1或者-1組成。因此，W-H內(nèi)核投影只涉及維度數(shù)量的增加和減少，計算速度快。Walsh-Hadamard內(nèi)核函數(shù)采用如下矩陣表達式：

其次，當內(nèi)核根據(jù)增加的信號變化時，實驗表明緊致下界可以通過一定小數(shù)量的內(nèi)核得到。所以，我們可以極大地減少相似性度量計算的復雜度，同時獲取具有區(qū)分的特征向量。圖4顯示了二維W-H內(nèi)核按順序增加的圖像。

圖4　二維4×4的W-H內(nèi)核順序遞增的圖像，陰影表示值1，白色部分代表值-1

2.2改進的SIFT特征描述算子

改進的SIFT算法主要針對算法的第四步進行改進，在基于像素梯度值統(tǒng)計的基礎上得到關于特征點的位置以及主方向的信息后。下面根據(jù)特征點的位置和尺度信息，以此特征點為中心選取一個區(qū)域作為圖像子塊，在該區(qū)域內(nèi)，將區(qū)域內(nèi)的像素點的梯度方向調整至主方向，這樣就得到圖像的規(guī)范化區(qū)域塊。

在得到的區(qū)域塊內(nèi)，計算該區(qū)域塊的方向梯度矩陣Fθ（x，y），其中θ劃分為4個方向：0，。在圖像子塊中，不同方向的梯度矩陣可以通過以下公式得到：

其中，F(xiàn)0（x，y）代表水平梯度，代表豎直梯度。通過對梯度矩陣進行高斯濾波的方法來消除光照和視角變化的影響。

其中，參數(shù)σ設為圖像子塊寬度的四分之一。通過高斯濾波后，可以有效消除距離圖像子區(qū)域中心的梯度值對最終結果的不利影響。

計算出梯度方向矩陣后，對梯度方向矩陣進行WH內(nèi)核投影，在投影值中，計算前12個投影值的兩個梯度方向水平梯度F0（x，y）、豎直梯度；再取前6個投影值，添加兩個梯度方向，即梯度值為y）和。由上述梯度值產(chǎn)生36維的特征描述算子，即12×2+6×2=36維。

2.3改進的特征匹配算法

（1）SIFT初匹配特征點對

為了保證不增加額外的計算量，對改進的SIFT特征描述算子，采用歐氏距離作為相似度準則其進行匹配。任意兩個待匹配描述算子的歐氏距離為：

利用k-d樹的優(yōu)先搜索算法進行搜索，搜索特征點P的最近鄰和次近鄰的特征點Q`、Q``，計算P點與Q`點，P點和Q``點兩組算子之間的歐氏距離比γ，設置如果比值γ小于給定的閾值T時，匹配成功，記錄初始匹配點對（P，Q`），否則，匹配不成功。根據(jù)算法的實驗效果，在閾值T為0.8時效果較好。

（2）改進蟻群算法的特征點對優(yōu)化算法

蟻群算法是一種整體最優(yōu)化算法，相關的研究表明［6-9］，蟻群算法的離散性和并行性特點在處理求解復雜性優(yōu)化問題時，尤其對于離散優(yōu)化問題，顯示出了其獨特的優(yōu)越性。這對處理數(shù)字圖像是十分有利的。

對初匹配特征點對引入快速收斂的蟻群算法來進行優(yōu)化。具體操作如下：

首先，我們對蟻群算法用到的相關參數(shù)進行說明介紹并且符號化：n設為螞蟻數(shù)量，β設為啟發(fā)式函數(shù)重要程度的因子，α設為信息素因子，ρ設為信息素蒸發(fā)系數(shù)，Q設為信息素總量，iter_max設最大迭代次數(shù)，初始值迭代次數(shù)iter設為1。

初始化螞蟻的城市模型：采用螞蟻作為搜索窗口，在圖像A和圖像B上，在參考圖像B上，將改進的SIFT算法初匹配得到的特征點Xj（i=1，2，…，m）來比作n只螞蟻，然后，搜索窗口使用圖像A中的窗口來表示，將搜索特征點的迭代過程構建為城市模型，則每一個螞蟻在不同時刻的觀測數(shù)據(jù)，就是城市模型中的點坐標。隨機的將n只螞蟻放在m個城市上，讓n只螞蟻聚集到j個聚類中心Xj（i=1，2，…，m）；灰色關聯(lián)度看作是相似性函數(shù)，構建灰色距離關聯(lián)度D（i，j），系統(tǒng)因素間的關聯(lián)性以距離來表示，即：

其中，d（Xi，X'j）表示兩個城市i，j之間的距離，這里表示待優(yōu)化匹配點對間的灰色關聯(lián)度距離。

假設算法中的螞蟻具有一定的存儲能力，能根據(jù)兩幅待拼接圖像的灰色關聯(lián)度選擇轉移的方向，使得灰色關聯(lián)度值最大的方向為螞蟻最終的移動方向。在圖像匹配中，在參考圖像B上，將匹配圖像A中的窗口作為搜索窗口，則搜索特征點的迭代過程就可以看做是i只螞蟻的城市模型，那么螞蟻爬行的過程中，螞蟻爬行所獲得的每個哈密頓路，都對應著一個灰色關聯(lián)度最大的組合。優(yōu)化初匹配點具體過程如下：

①在爬行搜索操作中，禁忌表Tabuk（k=1，2，…，q）記錄了螞蟻當前走過的城市，每只螞蟻轉移的方向則是通過個體路徑上的信息量來決定。根據(jù)路徑的啟發(fā)信息，以及各路徑上的信息量，得到螞蟻的狀態(tài)轉移概率，即：

②刷新信息素因子：當信息素達到某一臨界值后，螞蟻選擇這條路徑的概率大小與信息素因子α發(fā)熱值的大小呈現(xiàn)類似反比的關系。算法的全局搜索能力會隨著α的增大而由弱變強，逐漸跳出局部最優(yōu)解，直到求得全局最優(yōu)解。如果在N次循環(huán)內(nèi)最優(yōu)解都沒有得到改進，那么就采用如下公式對信息素因子的取值范圍進行改進：

其中，λ為常數(shù)，取值范圍是λ≥1。本文選取λ= 1.0，αmax=5。

③更新信息素揮發(fā)因子：因為隨著螞蟻信息素的釋放，連接各個城市之間路徑上的信息素會逐漸減少，所以螞蟻完成一次循環(huán)之后，每條路徑上的信息素濃度就需要進行及時的更新，即：

由于信息素揮發(fā)因子ρ的參數(shù)的取值范圍小，需要對其進行調整。而螞蟻選擇以前搜索的路徑的概率會隨著各路徑上殘留信息素的變化而變化，從而影響全局搜索能力的變化。當ρ設置偏小時，就會增加在各路徑上殘留的信息素，而螞蟻選擇以前搜索的路徑的概率也會隨著增加，這樣全局搜索能力就會變??；當ρ設置偏大時，就會減小在各路徑的信息素堆積的速度。為了增強算法的全局搜索能力，算法以犧牲收斂速度的方法為代價來完成。ρ值得自動修改變換如下：

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

④停止搜索的條件：當初始迭代次數(shù)iter≤iter_ max，則令iter+1，將螞蟻經(jīng)過的路徑的禁忌表清空，然后轉到步驟（2）；反之停止搜索，輸出搜索后的結果。

4　實驗結果及分析

實驗環(huán)境硬件如下：使用的操作系統(tǒng)為Win7，采用的處理器為Intel Celeron CPU N2830@2.16GHz，運行內(nèi)存4G，仿真平臺MATLAB版本為MATLAB （R2010b）。

改進算法主要針對圖像配準的精確度和計算時間進行改進，原始SIFT算法初匹配得到的圖像表示如下圖5所示。

圖5　特征初匹配得到的結果圖

下面針對本文改進的算法和SIFT-RANSAC算法進行匹配精確度的實驗對比，對比結果如圖6。

通過對比實驗結果，雖然本文改進的算法獲得的匹配點數(shù)少于SIFT-RANSAC算法獲得的匹配點數(shù)，但是本文的改進算法卻是取得了較好的實驗結果，進行匹配的精確度明顯好于SIFT-RANSAC算法。

本文對改進后的算法與原始SIFT算法進行了相關實驗，針對特征點的匹配時間，以及特征點的匹配效率進行了實驗分析，實驗結果如表1所示：

圖6　SIFT-RANSAC算法得到的結果圖像

圖7　本文算法進行優(yōu)化得到的圖像

表1　改進算法與SIFT算法在匹配時間和配準率上的實驗結果

通過實驗結果我們可以發(fā)現(xiàn)，改進算法在提取的特征點數(shù)量與原算法相同的情況下，雖然降維后，得到的初始匹配的特征點數(shù)目減少，但是在使用蟻群優(yōu)化后，匹配效率上有較好的提高，配準算法運行的總時間也有了很大的提升。

4　結語

針對一般性的SIFT算法和RANSAC算法在配準精度與時間上的不足，本文在原來算法的基礎上，通過引入內(nèi)核投影技術來降低特征描述子的維數(shù)，并采用快速收斂的蟻群算法對初始匹配點進行了提純，較好地提高了配準算法的配準率，同時也較好地提高了算法的計算效率，通過實驗取得了較好的實驗效果。使得圖像配準在精度于與時間上有了極大的提高。

［1］Brown L G.A Survey of Image Registration Techniques［J］.ACM Computing Surveys，1992，24（4）：325-376.

［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］Chen Fuxing，Wang Runsheng.Fast RANSAC with Preview Model Parameters Evaluation［J］.Journal of Software，2005，16（8）：1431-1437.

［4］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.

［5］Yacov Hel-Or，Hagit Hel-Or.Real-Time Pattern Matching Using Projection Kernels［J］.IEEE Computer Society，2005，27（9）∶1430-1445.

［6］何志明.群體智能算法在圖像匹配中的應用［D］.西安∶陜西師范大學2010.

［7］段海濱，王道波．蟻群算法的全局收斂性研究及改進［J］．系統(tǒng)工程與電子技術，2004，26（10）．

［8］段海濱，王道波.一種快速全局優(yōu)化的改進蟻群算法及仿真［J］.信息與控制，2004，33（2）.

［9］林小平，周石琳，張官亮等.一種基于蟻群算法和互信息測度的圖像拼接技術［J］.重慶理工大學學報：自然科學，2013，27（1）∶76-81.

SIFT；Image Registration；ACO；Kernel Projection

An Improved Ant Colony Optimization SIFT Feature Points of Image Registration Algorithm

HOU Jian，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

In order to reduce the matching of image registration time and improve the matching rate of the image registration，proposes an ant colony optimization SIFT image registration algorithm.First，uses the kernel projection algorithm Walsh-Hadamard to SIFT feature descriptor for dimension reduction，then uses the optimization of the ant colony algorithm for initial matching points for purification，improves the matching rate.The experimental results show that the improved algorithm is compared with purified SIFT algorithm with RANSAC algorithm，not only to improve the validity of the match，but also effectively shorten the computation time of the algorithm.

1007-1423（2016）20-0078-07

10.3969/j.issn.1007-1423.2016.20.016

侯堅（1989-），男，山東臨沂人，碩士研究生，在讀研究生，研究方向為模式識別與圖像處理

張明（1957-），男，江蘇盱眙人，博士，教授，研究方向為多媒體信息處理、計算機視覺、人工智能等

2016-04-25

2016-07-10