安維勝，余讓明，伍玉鈴

（西南交通大學(xué)機(jī)械工程學(xué)院，成都 610031）

該特征點(diǎn)，否則就舍棄。

基于FAST和SURF的圖像配準(zhǔn)算法

安維勝，余讓明，伍玉鈴

（西南交通大學(xué)機(jī)械工程學(xué)院，成都 610031）

尺度不變特征變換（SIFT）和加速魯棒特征（SURF）方法在進(jìn)行角點(diǎn)檢測和特征點(diǎn)匹配時(shí)的時(shí)間較長。為此，提出一種改進(jìn)的圖像配準(zhǔn)算法。建立參考圖像與待配準(zhǔn)圖像的高斯圖像金字塔，在金字塔各層圖像進(jìn)行檢測，得到具有不同尺度的加速分割測試特征（FAST）點(diǎn)，采用SURF算法為各特征點(diǎn)分配方向，并計(jì)算各特征點(diǎn)的描述向量，使用快速近似最近鄰搜索算法獲取圖像間的初始匹配點(diǎn)對(duì)，用隨機(jī)抽樣一致性算法剔除誤匹配點(diǎn)對(duì)，同時(shí)得到2幅圖像之間的幾何變換矩陣。實(shí)驗(yàn)結(jié)果表明，與SURF算法和SIFT算法相比，該算法的特征檢測速度和匹配速度較快，匹配正確率較高。

圖像配準(zhǔn)；加速分割測試特征；加速魯棒特征；近似最近鄰；隨機(jī)抽樣一致性

DO I：10.3969/j.issn.1000-3428.2015.10.043

1 概述

圖像配準(zhǔn)是對(duì)不同時(shí)間、不同視角或不同傳感器拍攝的2幅或多幅圖像進(jìn)行空間變換處理，使各圖像在幾何上相互對(duì)應(yīng)［1］。其應(yīng)用范圍相當(dāng)廣泛，包括計(jì)算機(jī)視覺和模式識(shí)別（如圖像分割、三維重建、目標(biāo)識(shí)別、運(yùn)動(dòng)跟蹤與估計(jì)等）、醫(yī)學(xué)圖像分析、遙感圖像處理、圖像融合、全景圖像拼接［2］等。圖像配準(zhǔn)方法大致可分為2類：基于區(qū)域的配準(zhǔn)方法和基于特征的配準(zhǔn)方法［3］。

基于區(qū)域的配準(zhǔn)方法計(jì)算簡單、速度快，但是對(duì)存在較大噪聲的圖像或者待配準(zhǔn)圖像的重疊部分較少時(shí)，配準(zhǔn)效果不理想，且易受光照變化的影響?；谔卣鞯呐錅?zhǔn)方法將對(duì)整個(gè)圖像的各種分析轉(zhuǎn)化為對(duì)圖像特定特征的分析，大大減小了圖像處理過程的運(yùn)算量，且對(duì)灰度變化、圖像變形以及遮擋等都有較好的適應(yīng)能力［4］，其應(yīng)用越來越廣泛。

文獻(xiàn)［5-6］提出的尺度不變特征變換（Scale

Invariant Feature Transform，SIFT）算法對(duì)圖像旋轉(zhuǎn)、縮放、光照變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定的穩(wěn)定性，但SIFT算法的特征檢測、特征描述符的生成與匹配計(jì)算量很大，速度較慢，不適合實(shí)時(shí)應(yīng)用。為提高特征提取速度，文獻(xiàn)［7］提出了加速魯棒特征（Speeded-up Robust Feature，SURF）算法，它是對(duì)SIFT算法的一種改進(jìn)，它通過計(jì)算積分圖像和Fast Hessian矩陣大大提高了特征點(diǎn)檢測的速度，但采用全局最近鄰搜索進(jìn)行特征匹配，計(jì)算量大、匹配速度慢。文獻(xiàn)［8］提出加速分割測試特征（Features from Accelerated Segment Test，F(xiàn)AST）提取算法，該算法角點(diǎn)檢測速度很快，但易受噪聲干擾和光照變化影響，不具備尺度不變性。文獻(xiàn)［9］提出基于SURF和快速近似最近鄰搜索算法的圖像匹配方法，提高了SURF算法的匹配正確率和實(shí)時(shí)性。文獻(xiàn)［10］采用FAST角點(diǎn)檢測、SURF描述向量和最佳值優(yōu)先（Best-Bin First，BBF）搜索匹配點(diǎn)的方法進(jìn)行棉花圖像的匹配。

本文在前人工作的基礎(chǔ)上，研究了FAST和SURF特征檢測原理，通過FAST檢測可能的特征角點(diǎn)，使用Hessian檢測子提取特征，然后采用SURF特征描述和快速近似最近鄰搜索匹配對(duì)的方法實(shí)現(xiàn)圖像的配準(zhǔn)。

2 圖像配準(zhǔn)實(shí)現(xiàn)流程

基于特征的圖像配準(zhǔn)主要有特征檢測、特征匹配、變換模型估計(jì)和圖像重采樣與幾何變換［3］。特征檢測和特征匹配是基于特征的配準(zhǔn)方法的2個(gè)關(guān)鍵步驟。本文提出采用FAST特征檢測、SURF特征描述和快速近似最近鄰搜索的圖像配準(zhǔn)算法，其實(shí)現(xiàn)過程如圖1所示。

圖1 圖像配準(zhǔn)算法流程

3 特征點(diǎn)檢測

特征點(diǎn)檢測是查找和定位圖像中的具有代表性的像素點(diǎn)或者與周圍像素迥異的斑點(diǎn)等，是圖像配準(zhǔn)的基礎(chǔ)。FAST角點(diǎn)檢測算法不具備尺度不變性，因此，本文建立原始圖像的高斯金字塔，對(duì)每一層圖像提取FAST特征點(diǎn)。為提高算法的光照不變性，對(duì)光照變化較大的原始圖像進(jìn)行直方圖均衡化處理。

3.1 高斯圖像金字塔建立

文獻(xiàn)［11］表明在某些合理的假設(shè)條件下高斯函數(shù)是唯一的實(shí)現(xiàn)尺度變換的線性核。用函數(shù)L（χ，y，σ）表示一幅二維圖像 I（χ，y）的尺度空間為：

其中，?表示卷積運(yùn)算；G（χ，y，σ）是尺度可變的高斯函數(shù)，其定義為：

其中，σ為尺度因子，表示圖像被平滑的程度，σ越大圖像越模糊。

為了提高算法效率，本文建立3組3層高斯金字塔，共9層圖像。經(jīng)過實(shí)驗(yàn)比較，圖像金字塔的第0組0層圖像平滑尺度σ0=1.4，任意層與0層之間的尺度關(guān)系為σs=σ0ks，相鄰層間尺度因子k= 21/S，S為每組總層數(shù)3，s為金字塔中圖像的層序數(shù)，s=｛0，1，…，9｝。每組的第一層圖像由前一組的最后一層圖像下采樣得到，因此，每組增加1層圖像，但不進(jìn)行特征點(diǎn)檢測。為了獲取更多的特征點(diǎn)，可將原始圖像放大2倍作為第0組圖像。

3.2 FAST角點(diǎn)檢測

FAST算法通過檢測中心點(diǎn)與周圍像素點(diǎn)的明暗程度來確定中心點(diǎn)是否是特征點(diǎn)，由于計(jì)算簡單使FAST算法速度快。

在以侯選像素點(diǎn)P為中心，半徑為3的Bresenham圓上共有16個(gè)像素點(diǎn)，對(duì)圓周上每一個(gè)像素點(diǎn)χ（χ∈｛1，2，…，16｝）逐一檢測，按照式（3）的規(guī)則判斷測試點(diǎn)是亮點(diǎn)、暗點(diǎn)還是相似點(diǎn)。點(diǎn)χ與點(diǎn)P亮度比較結(jié)果如下：

其中，d，b，s分別表示暗點(diǎn)集、相似點(diǎn)集和亮點(diǎn)集；IP表示點(diǎn)P的亮度灰度值；Iχ表示點(diǎn)χ的亮度灰度值；t為亮度閾值。

如果有n個(gè)連續(xù)的像素點(diǎn)（圖2中的虛線），屬于亮點(diǎn)（或暗點(diǎn)），那么點(diǎn)P屬于角點(diǎn)。

文獻(xiàn)［8］表明n取9檢測特征的可重復(fù)性最好。由于FAST沒有角點(diǎn)響應(yīng)函數(shù)，且具有很大的邊緣響應(yīng)，本文在檢測FAST特征點(diǎn)時(shí)使用Hessian矩陣去除不穩(wěn)定的邊緣響應(yīng)，并采用Harris角點(diǎn)響應(yīng)函數(shù)值對(duì)FAST特征點(diǎn)進(jìn)行排序。若想得到N個(gè)關(guān)鍵點(diǎn)，先降低閾值得到多于N個(gè)點(diǎn)，然后根據(jù)Harris響應(yīng)值取前N個(gè)點(diǎn)。

Hessian矩陣H的公式為：

其中，Dχχ，Dχy，Dyy是候選角點(diǎn)處的二階偏導(dǎo)數(shù)，通過附近區(qū)域的差分近似計(jì)算。由于D的主曲率和 H的特征值成正比，為了避免直接計(jì)算這些特征值，而求其比率ratio。令α為最大特征值，β為最小的特征值，α=rβ，則：

該特征點(diǎn)，否則就舍棄。

4 SURF特征描述

4.1 主方向確定

為使特征點(diǎn)描述子具有旋轉(zhuǎn)不變性，需要對(duì)每個(gè)特征點(diǎn)分配主方向。首先計(jì)算以某個(gè)特征點(diǎn)為圓心，6s（s為特征點(diǎn)對(duì)應(yīng)的尺度）為半徑的圓形鄰域內(nèi)所有點(diǎn)在χ和y方向上的Haar小波響應(yīng)，Haar小波邊長為4s，取樣步長為s。然后給響應(yīng)值賦以特征點(diǎn)為中心的高斯（σ=2.5）權(quán)重系數(shù)。接下來以χ方向的響應(yīng)為橫坐標(biāo)，以 y方向的響應(yīng)為縱坐標(biāo)，取60°的扇形區(qū)域作為滑動(dòng)窗口，使用該窗口以5°為步長旋轉(zhuǎn)遍歷整個(gè)圓形鄰域，分別計(jì)算在每個(gè)角度下該扇形區(qū)域內(nèi)所有點(diǎn)在χ和y方向的Haar小波響應(yīng)和，生成一個(gè)局部的方向向量，選擇所有窗口中最長的向量方向作為該特征點(diǎn)的主方向。

4.2 特征描述向量的生成

以特征點(diǎn)為中心構(gòu)建邊長為 20s的正方形區(qū)域，旋轉(zhuǎn)該區(qū)域使之與特征點(diǎn)的主方向平行，沿主方向?qū)⒃搮^(qū)域劃分為4×4個(gè)子區(qū)域，每個(gè)子區(qū)域有5s×5s個(gè)像素點(diǎn)，計(jì)算每個(gè)子區(qū)域內(nèi)每個(gè)像素點(diǎn)在χ方向（平行于主方向）和y方向（垂直于主方向）的Haar小波響應(yīng)值，Haar小波邊長為2s，分別記為dχ，dy。為增加對(duì)幾何變換的魯棒性，對(duì)dχ和dy賦以特征點(diǎn)為中心的高斯（σ=3.3s）權(quán)重系數(shù)。然后把每個(gè)子區(qū)域內(nèi)的Haar小波響應(yīng)值及響應(yīng)值的絕對(duì)值相加得到這樣，在每個(gè)子區(qū)域得到一個(gè)四維向量：

對(duì)每個(gè)特征點(diǎn)，就產(chǎn)生了一個(gè)4×4×4=64維的SURF特征描述向量，再對(duì)描述向量進(jìn)行歸一化處理以獲得對(duì)比度不變性。

5 特征匹配

特征匹配的目的是根據(jù)參考圖像和待配準(zhǔn)圖像在提取的特征及其屬性信息，求出反映2幅圖像之間幾何變化關(guān)系的最優(yōu)變換模型參數(shù)。本文以特征點(diǎn)描述向量之間的歐氏距離作為特征點(diǎn)的相似性度量。SURF特征向量是高維向量，雖然采用窮舉搜索最近鄰的匹配方法得到的最近鄰結(jié)果較準(zhǔn)確，但搜索速度慢。文獻(xiàn)［12］對(duì)計(jì)算機(jī)視覺中高維向量的近似最近鄰匹配算法進(jìn)行了比較，提出對(duì)于高維空間中的最近鄰搜索問題，采用分層k-means樹和多重隨機(jī)k-d樹具有較好的性能，并且實(shí)現(xiàn)了根據(jù)用戶輸入數(shù)據(jù)和期望的精度自動(dòng)選擇最佳算法和參數(shù)值的算法。本文采用快速近似最近鄰搜索算法進(jìn)行特征的搜索，其實(shí)現(xiàn)過程基于目前流行的OpenCV的FLANN（Fast Library for Approximate Nearest Neighbors）庫。

首先采用FLANN搜索算法從待配準(zhǔn)圖像中找出與參考圖像的歐氏距離最近和次近的2個(gè)點(diǎn)，以最近歐氏距離與次近歐氏距離的比值同給定的閾值T比較來判定特征點(diǎn)是否匹配。閾值T通常為0.4～0.8，閾值越大匹配點(diǎn)數(shù)越多，但匹配正確率會(huì)降低。

經(jīng)過歐氏距離匹配后的匹配點(diǎn)對(duì)仍會(huì)存在錯(cuò)誤匹配的情況，需對(duì)初始匹配結(jié)果進(jìn)行去誤提純。本文采用隨機(jī)抽樣一致性（Randomized Sample Consensus，RANSAC）算法剔除誤匹配對(duì)。

6 實(shí)驗(yàn)結(jié)果與分析

圖像配準(zhǔn)的目的是找到待配準(zhǔn)圖像間的變換關(guān)系，圖像間的變換通常有剛體變換、仿射變換和透射變換。透射變換只要給定 4對(duì)點(diǎn)就可獲得圖像間的單應(yīng)性矩陣。眾所周知，需要處理的數(shù)據(jù)越

少算法的總體時(shí)間消耗就少。本文通過設(shè)定合理的閾值來得到一定數(shù)量的特征點(diǎn)和匹配點(diǎn)對(duì)，并獲得圖像間的單應(yīng)性矩陣，以進(jìn)行不同算法的性能比較。

6.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)環(huán)境為Intel Core i3-2310@2.10 GHz，內(nèi)存2 GB。實(shí)驗(yàn)所用測試圖像均為現(xiàn)實(shí)場景圖像，來自Mikolajczyk和Schmid提供的一組圖像數(shù)據(jù)集。FAST角點(diǎn)檢測亮度閾值t=20，圖像匹配的最近與次近歐氏距離比值閾值T=0.5。

6.2 結(jié)果分析

以 boat圖像為例，圖像分辨率大小為 850× 680像素，圖像間具有尺度和旋轉(zhuǎn)變化，分別使用本文算法、SURF算法和SIFT算法進(jìn)行特征檢測及匹配，通過設(shè)置閾值提取適量的角點(diǎn)，檢測結(jié)果如表1所示，匹配結(jié)果如表2所示，檢測時(shí)間為5次實(shí)驗(yàn)平均值。

表1 角點(diǎn)檢測時(shí)間比較

表2 特征匹配性能比較

從表1和表2可以看出，本文算法與SURF和SIFT算法相比，特征點(diǎn)檢測速度更快，匹配時(shí)間更短。SIFT和SURF特征點(diǎn)的檢測定位通過搜索尺度空間局部三維極值點(diǎn)來確定特征點(diǎn)的位置和尺度，定位效果好，但計(jì)算復(fù)雜運(yùn)算量大。FAST角點(diǎn)檢測依據(jù)像素點(diǎn)亮度差值，不像SURF和SIFT需要大量的計(jì)算過程，因此，速度更快。本文采用 SURF的64 bit浮點(diǎn)描述向量，其生成與匹配過程中的計(jì)算量比SIFT的128 bit描述向量的計(jì)算量小，因此，速度比SIFT快很多。同時(shí)，本文采用快速近似鄰搜索方法進(jìn)行特征點(diǎn)的匹配，速度比全局最近鄰搜索方法快很多。雖然匹配點(diǎn)數(shù)量較少，但其正確率比較高?？偟膩碚f，在相同的匹配閾值條件下，SIFT算法的匹配正確率最高，本文算法次之，SURF算法的匹配正確率最低，但SURF算法的匹配數(shù)量較本文算法多。SIFT算法定位精度好，但總匹配時(shí)間長，不適用于實(shí)時(shí)應(yīng)用場合。

本文算法對(duì)視角變化、尺度和旋轉(zhuǎn)、光照變化等情況也進(jìn)行了匹配實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖 3所示。圖3（a）、圖3（b）為光照變化的情況，圖3（b）對(duì)右圖進(jìn)行了直方圖均衡化處理，可以看出，處理后匹配特征點(diǎn)數(shù)量更多，分布更均勻。圖3（c）為尺度和旋轉(zhuǎn)變化的情況，圖3（d）中待匹配圖像與匹配圖像為不同視角下拍攝所得。從圖3中可見本文算法對(duì)于視角變化、尺度和旋轉(zhuǎn)、光照變化等具有一定的不變性。

圖3 不同變化情況下的匹配結(jié)果

7 結(jié)束語

本文基于FAST特征檢測、SURF特征描述向量和快速近似最近鄰搜索方法，提出一種快速的圖像配準(zhǔn)算法。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)圖像的視角變化、尺度變化和旋轉(zhuǎn)以及光照變化等具有不變性，特征點(diǎn)提取速度快、匹配正確率高，可用于對(duì)實(shí)時(shí)性要求高、存在尺度變化和旋轉(zhuǎn)、光照變化以及視角變化不大的圖像匹配。下一步將實(shí)現(xiàn)本文算法閾值的自適應(yīng)調(diào)整，并用于圖像拼接。

［1］ 陳秀新，邢素霞.圖像/視頻檢索與圖像融合［M］.北京：機(jī)械工業(yè)出版社，2012.

［2］ Brown M，Low e D G.Automatic Panoramic Im age Stitching Using Invariant Features［J］.International Journal of Computer Vision，2007，74（1）：59-73.

［3］ Zitová B，F(xiàn)lusser J.Image Registration Methods：A Survey［J］.Image and Vision Computing，2003，21（11）：977-1000.

［4］ 丁南南，劉艷瀅，張 葉，等.基于SURF-DAISY算法和隨機(jī) kd樹的快速圖像配準(zhǔn)［J］.光電子·激光，2012，23（7）：1395-1402.

［5］ Lowe D G.Object Recognition from Local Scaleinvariant Features［C］//Proceedings of the 7th IEEE International Conference on Computer Vision. Washington D.C.，USA：IEEE Press，1999：1150-1157.

［6］ Lowe D G.Distinctive Image Features from Scaleinvariant Keypoints［J］.International Journal of Computer Vision，2004，60（2）：91-110.

［7］ Bay H，Ess A，Tuytelaars T，et al.SURF：Speeded-up Robust Features［J］.Computer Vision and Image Understanding，2008，110（3）：346-359.

［8］ Rosten E，Porter R，Drummond T.Faster and Better：A Machine Learning Approach to Corner Detection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1）：105-119.

［9］ 趙璐璐，耿國華，李 康，等.基于SURF和快速近視最近鄰的搜索的圖像匹配算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30（3）：921-923.

［10］ 時(shí) 顥，賴惠成，龔金輝，等.基于SURF和BBF的棉花圖像匹配算法［J］.江蘇農(nóng)業(yè)科學(xué)，2014，42（3）：343-346.

［11］ Lindeberg T.Scale-space Theory：A Basic Tool for Analysing Structures at Different Scales［J］.Journal of Applied Statistics，1994，21（2）：224-270.

［12］ Muja M，Low e D G.Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration［C］// Proceedings of the 4th International Conference on Computer Vision Theory and Application.Lisboa，Portugal：INSTICC Press，2009：331-340.

編輯 劉 冰

Image Registration Algorithm Based on FAST and SURF

AN Weisheng，YU Rangming，WU Yuling
（School of Mechanical Engineering，Southwest Jiaotong University，Chengdu 610031，China）

For Scale Invariant Feature Transform（SIFT）and Speeded-up Robust Feature（SURF）needing a long time in the corner detecting and feature points matching，an improved image registration algorithm is put forward.A Gaussian scale pyramid of the reference image and the matching image are established.Feature points which have different scale information are detected from each level in the image pyramid.It gets Features from Accelerated Segment Test（FAST）point with different scales.An orientation is assigned to every feature point，and feature vector is calculated by using the same way as SURF.The original matching points which have minimum Euclidean distance under some condition are determined through fast approximate nearest neighbor search.The false matching points are excluded by Randomized Sample Consensus（RANSAC）algorithm，and the transformation matrix is gained.Experimental results show that the algorithm is better than SURF and SIFT in feature detection speed and matching speed，and matching accuracy is higher.

image registration；Features from Accelerated Segment Test（FAST）；Speeded-up Robust Feature（SURF）；Approximate Nearest Neighbor（ANN）；Randomized Sample Consensus（RANSAC）

安維勝，余讓明，伍玉鈴.基于FAST和SURF的圖像配準(zhǔn)算法［J］.計(jì)算機(jī)工程，2015，41（10）：232-235，239.

英文引用格式：An Weisheng，Yu Rangming，Wu Yuling.Image Registration Algorithm Based on FAST and SURF［J］. Computer Engineering，2015，41（10）：232-235，239.

1000-3428（2015）10-0232-04

A

TP391

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目（2682013CX024）。

安維勝（1974-），男，副教授、博士，主研方向：計(jì)算機(jī)圖形學(xué)，虛擬現(xiàn)實(shí)；余讓明、伍玉鈴，碩士研究生。

2014-09-23

2014-11-21E-mail：anweisheng@swjtu.edu.cn