侯堅(jiān)，張明（上海海事大學(xué)信息工程學(xué)院，上海 201306）

一種蟻群優(yōu)化的改進(jìn)SIFT特征點(diǎn)的圖像配準(zhǔn)算法

侯堅(jiān)，張明
（上海海事大學(xué)信息工程學(xué)院，上海 201306）

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

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

0　引言

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

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

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

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

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

1.1SIFT特征點(diǎn)提取

（1）尺度空間極值點(diǎn)檢測(cè)

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

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

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

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

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

（2）關(guān)鍵點(diǎn)定位

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

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

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

Hessian矩陣的跡和行列式為：

實(shí)驗(yàn)中主曲率的選取范圍一般為6～10。

（3）確定關(guān)鍵點(diǎn)的方向

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

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

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

（4）特征描述符

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

圖2　圖像特征點(diǎn)梯度方向及高斯加權(quán)后的主方向

圖3　SIFT特征描述子構(gòu)造窗口

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

1.2SIFT特征匹配

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

當(dāng)設(shè)定的閾值T的參數(shù)減小時(shí)，誤匹配點(diǎn)對(duì)數(shù)目會(huì)減少，但是同時(shí)也剔除了正確匹配點(diǎn)對(duì)的數(shù)目；反之，當(dāng)設(shè)定的閾值T增大時(shí)，會(huì)迅速增加誤匹配點(diǎn)對(duì)的數(shù)目，這將極大影響結(jié)果的配準(zhǔn)效果。

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

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

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

2　改進(jìn)的SIFT圖像配準(zhǔn)算法

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

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

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

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

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

2.2改進(jìn)的SIFT特征描述算子

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

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

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

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

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

2.3改進(jìn)的特征匹配算法

（1）SIFT初匹配特征點(diǎn)對(duì)

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

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

（2）改進(jìn)蟻群算法的特征點(diǎn)對(duì)優(yōu)化算法

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

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

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

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

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

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

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

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

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

③更新信息素?fù)]發(fā)因子：因?yàn)殡S著螞蟻信息素的釋放，連接各個(gè)城市之間路徑上的信息素會(huì)逐漸減少，所以螞蟻完成一次循環(huán)之后，每條路徑上的信息素濃度就需要進(jìn)行及時(shí)的更新，即：

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

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

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

4　實(shí)驗(yàn)結(jié)果及分析

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

改進(jìn)算法主要針對(duì)圖像配準(zhǔn)的精確度和計(jì)算時(shí)間進(jìn)行改進(jìn)，原始SIFT算法初匹配得到的圖像表示如下圖5所示。

圖5　特征初匹配得到的結(jié)果圖

下面針對(duì)本文改進(jìn)的算法和SIFT-RANSAC算法進(jìn)行匹配精確度的實(shí)驗(yàn)對(duì)比，對(duì)比結(jié)果如圖6。

通過(guò)對(duì)比實(shí)驗(yàn)結(jié)果，雖然本文改進(jìn)的算法獲得的匹配點(diǎn)數(shù)少于SIFT-RANSAC算法獲得的匹配點(diǎn)數(shù)，但是本文的改進(jìn)算法卻是取得了較好的實(shí)驗(yàn)結(jié)果，進(jìn)行匹配的精確度明顯好于SIFT-RANSAC算法。

本文對(duì)改進(jìn)后的算法與原始SIFT算法進(jìn)行了相關(guān)實(shí)驗(yàn)，針對(duì)特征點(diǎn)的匹配時(shí)間，以及特征點(diǎn)的匹配效率進(jìn)行了實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如表1所示：

圖6　SIFT-RANSAC算法得到的結(jié)果圖像

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

表1　改進(jìn)算法與SIFT算法在匹配時(shí)間和配準(zhǔn)率上的實(shí)驗(yàn)結(jié)果

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

4　結(jié)語(yǔ)

針對(duì)一般性的SIFT算法和RANSAC算法在配準(zhǔn)精度與時(shí)間上的不足，本文在原來(lái)算法的基礎(chǔ)上，通過(guò)引入內(nèi)核投影技術(shù)來(lái)降低特征描述子的維數(shù)，并采用快速收斂的蟻群算法對(duì)初始匹配點(diǎn)進(jìn)行了提純，較好地提高了配準(zhǔn)算法的配準(zhǔn)率，同時(shí)也較好地提高了算法的計(jì)算效率，通過(guò)實(shí)驗(yàn)取得了較好的實(shí)驗(yàn)效果。使得圖像配準(zhǔn)在精度于與時(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］何志明.群體智能算法在圖像匹配中的應(yīng)用［D］.西安∶陜西師范大學(xué)2010.

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

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

［9］林小平，周石琳，張官亮等.一種基于蟻群算法和互信息測(cè)度的圖像拼接技術(shù)［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)，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

侯堅(jiān)（1989-），男，山東臨沂人，碩士研究生，在讀研究生，研究方向?yàn)槟Ｊ阶R(shí)別與圖像處理

張明（1957-），男，江蘇盱眙人，博士，教授，研究方向?yàn)槎嗝襟w信息處理、計(jì)算機(jī)視覺(jué)、人工智能等

2016-04-25

2016-07-10