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

安維勝，余讓明，伍玉鈴

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

該特征點，否則就舍棄。

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

安維勝，余讓明，伍玉鈴

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

3 特征點檢測

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

3.1 高斯圖像金字塔建立

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

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

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

為了提高算法效率，本文建立3組3層高斯金字塔，共9層圖像。經(jīng)過實驗比較，圖像金字塔的第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)行特征點檢測。為了獲取更多的特征點，可將原始圖像放大2倍作為第0組圖像。

3.2 FAST角點檢測

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

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

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

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

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

Hessian矩陣H的公式為：

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

該特征點，否則就舍棄。

4 SURF特征描述

4.1 主方向確定

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

4.2 特征描述向量的生成

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

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

5 特征匹配

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

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

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

6 實驗結(jié)果與分析

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

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

6.1 實驗環(huán)境

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

6.2 結(jié)果分析

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

表1 角點檢測時間比較

表2 特征匹配性能比較

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

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

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

7 結(jié)束語

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

［1］ 陳秀新，邢素霞.圖像/視頻檢索與圖像融合［M］.北京：機械工業(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算法和隨機 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］.計算機應(yīng)用研究，2013，30（3）：921-923.

［10］ 時 顥，賴惠成，龔金輝，等.基于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］.計算機工程，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ù)費專項基金資助項目（2682013CX024）。

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

2014-09-23

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