一種圖像局部特征快速匹配算法*

張格森，陳東生，王懷野，陸振林

（1.北京航天微系統(tǒng)研究所，北京 100094；2.中國航天時代電子公司博士后科研工作站，北京 100094）

一種圖像局部特征快速匹配算法*

張格森1，2，陳東生1，王懷野1，陸振林2

（1.北京航天微系統(tǒng)研究所，北京 100094；2.中國航天時代電子公司博士后科研工作站，北京 100094）

在圖像處理和機器視覺領域，SIFT是目前被廣泛應用的一種基于局部特征的圖像匹配算法。針對SIFT算法匹配速度較慢和常常存在錯誤匹配對的問題，本文提出在匹配過程中采用角度相似性分析替代傳統(tǒng)的歐式距離分析法，由此提高匹配速度，然后通過RANSAC一致性篩選刪除錯誤匹配對，最后通過實驗驗證了新算法的有效性。新算法結(jié)構(gòu)清晰，計算簡便，易于硬件實現(xiàn)。

圖像匹配；局部特征；SIFT；角度相似性；RANSAC

0 引言

圖像匹配是指通過圖像分析方法在兩幅或者多幅圖像中尋找同名點的過程[1]。圖像匹配是機器視覺和圖像處理領域的核心問題之一，是目標識別技術(shù)的重要研究內(nèi)容，廣泛應用于遙感影像處理、目標識別與跟蹤、醫(yī)學圖像處理和圖像制導技術(shù)等領域。目前，常用的圖像匹配算法主要有基于區(qū)域統(tǒng)計性特征的圖像匹配和基于局部特征的匹配兩大類[2]，而由于圖像場景的復雜性和局部特征具有更好的魯棒性，基于局部特征的圖像匹配算法日益成為該領域研究的主流方向[3]。

迄今為止，SIFT（Scale Invariant Feature Transform）算法[4]被公認為具有很好的魯棒性，是最適合在復雜場景中應用的一種局部特征匹配算法，已成為目前最主流的圖像匹配算法之一[5]。根據(jù) SIFT算法的原理，SIFT算法能夠很好地抵御圖像尺度變換、旋轉(zhuǎn)變換和仿射變換，當圖像存在一定程度的噪聲時，也能夠?qū)崿F(xiàn)圖像匹配，因此該算法常常被用于一些復雜場景的圖像匹配問題。但是，SIFT需要生成很高維度的描述向量，匹配時利用歐式空間距離法分析描述向量的相似性，運算量大，很大程度上限制了該算法在實際硬件系統(tǒng)中的應用。目前，針對SIFT算法簡化運算的研究主要聚焦在如何簡化描述向量方面，如 PCA-SIFT[6]，而對描述向量匹配過程中運算量大的問題研究較少。針對該問題，本文以角度相似性分析為基本思路，提出了一種易于實現(xiàn)的圖像局部特征快速匹配算法，提升算法性能。

1 SIFT匹配算法原理

SIFT匹配算法主要包括特征點搜索、描述向量生成和特征點匹配三個基本步驟。

1.1 特征點搜索

SIFT特征點搜索也稱特征點檢測，主要分為三個基本步驟：尺度空間生成、空間鄰域極大值搜索和特征點精確定位[4]。

(1)尺度空間生成

目前，已經(jīng)有文獻用數(shù)學方法證明了高斯核是產(chǎn)生信號多尺度空間的惟一有效核[7]，由高斯核生成的尺度空間滿足尺度、平移以及旋轉(zhuǎn)不變性等。對于二維圖像I(x，y)，其尺度空間L(x，y，σ)的定義為：

其中，σ為尺度空間的尺度因子，?表示在x和y雙方向的卷積運算，G(x，y，σ)為高斯核函數(shù)，G(x，y，σ)的定義為：

(2)空間鄰域極大值搜索

Lowe在文獻[4]中提出，在某個尺度上搜索圖像斑點，可以先在兩個相鄰的高斯尺度空間圖像之間做減運算，求得一個 DoG（Difference of Gaussian）響應值圖像D(x，y，σ)，D(x，y，σ)的公式為：

其中，k為兩個相鄰尺度倍數(shù)的常數(shù)。

在實際操作中，DoG是通過建立圖像的尺度空間金字塔來實現(xiàn)的[8]。在尺度空間金字塔中，每一個像素點和其26個鄰域(包含同尺度相鄰點和上下相鄰尺度的相鄰點共26點)進行比較，實現(xiàn)空間范疇的局部極大值搜索，得到的所有極大值點構(gòu)成的集合即為特征點的備選集合。建立備選集合時，可去除對比度較低的極值點，由此對集合進行初步提純。

(3)特征點精確定位

特征點精確定位時，通過三維二次函數(shù)來擬合特征點，由此可以獲得特征點的精確位置和尺度值，此外，為了確保所提取特征點的穩(wěn)定性，基于Hessian矩陣計算主曲率，去除在邊緣上極值點。

1.2 描述向量生成

SIFT描述向量生成主要包括求取特征點主方向和特征點描述兩個基本步驟。

(1)求取特征點主方向

對于某個特征點，首先在其尺度圖像中設定一定范圍為鄰域區(qū)域，在鄰域中計算每個點的梯度 M(x，y)和方向θ(x，y)，其表達式分別為：

統(tǒng)計鄰域區(qū)域內(nèi)的梯度及方向數(shù)據(jù)，構(gòu)建直方圖，直方圖中的主峰值則為特征點的主方向，若在直方圖中存在一個次峰值，其能量相當于主峰值80%以上，則將這個方向確定為特征點的輔方向[9]。至此，特征點有了四個參數(shù)信息(x，y，σ，θ)，分別為特征點坐標、尺度信息、方向信息。確定主方向和輔方向的作用是使特征點具有旋轉(zhuǎn)不變性。

(2)描述向量生成

在對每個特征點進行描述時，首先將尺度圖像坐標軸旋轉(zhuǎn)至主方向上，在特征點鄰域范圍劃定4×4共16個子區(qū)域，在每個子區(qū)域，將0～360°全方向劃分為 8個子方向（每個子方向?qū)挾葹?45°），統(tǒng)計各子方向梯度強度，構(gòu)建8維子區(qū)域描述向量。對于16個子區(qū)域，則最終生成 4×4×8=128維描述向量，描述向量也稱描述子或特征向量。

1.3 特征點匹配

特征點匹配的目的是在原圖像和待匹配圖像中尋找相似程度高的特征點對，通常特征點在圖像間都是一對一關(guān)系，因此點對匹配時僅考慮相似度最近鄰情況。

目前的匹配方法主要采用歐式距離分析法[4]，對于k維向量Xi和 Xj，其歐式距離公式為：

式(7)中，Min{Dis}為求得的最近鄰，secMin{Dis}為求得的次近鄰，TDis表示最近鄰與次近鄰的比值閾值。若式(7)成立，則認定最近鄰相對應的特征點對為正確匹配對。通常，TDis在0.6～0.75之間取值。

歐式距離分析法能夠有效實現(xiàn)特征點對的相似性篩選，物理意義明確，但該方法運算速度慢，制約了SIFT算法的應用范圍。

為刪除一些易混淆點對，采用最優(yōu)與次優(yōu)比值的方法，對于歐式距離來說，即為最近鄰與次近鄰比值的方法。在運算中，若最近鄰與次近鄰比值小于預設的閾值，則認定為正確匹配對，認定關(guān)系式可表述為：

2 改進的匹配算法

為了提升匹配速度和進一步篩選匹配對，本文提出角度相似性分析和隨機抽樣一致性(Random Sample Consensus，RANSAC)篩選[10]相結(jié)合的方法，簡化匹配運算并刪除不符合空間一致性關(guān)系的錯誤匹配對。該算法以SIFT描述向量為處理對象，包括描述向量預匹配和匹配點對篩選兩個基本步驟。

2.1 描述向量預匹配

描述向量預匹配以角度相似性作為匹配準則，該方法也可稱為角度相似性匹配。角度相似性分析的原理：對于兩個單位向量，其夾角與弧長正相關(guān)，夾角很小時，弧長與弦長近似相等，弦長即為歐式距離。因此，夾角大小與歐式距離正相關(guān)，可以利用夾角的大小來判斷單位向量之間的相似程度。對于待匹配的k維單位向量，計算向量間的空間夾角，夾角越小，則這兩個描述向量越相似。

k維空間中的向量夾角 Φij計算公式為：

對于SIFT描述向量，描述向量生成過程中已經(jīng)進行過歸一化運算，因此，式（8）可簡化為：

因 Φ(i，j)較大時不符合相似性準則，因此，首先舍棄Φ(i，j)數(shù)值較大的情況。然后，利用最優(yōu)與次優(yōu)的比值大小來認定是否為正確匹配對，其認定關(guān)系可表述為：

式(10)中，Min{Φ}表示最小夾角(即最優(yōu)夾角)，secMin{Φ}表示次小夾角(即次優(yōu)夾角)，TΦ為最小夾角與次小夾角比值閾值，當式(10)成立時，最小夾角對應的匹配對即被認定為備選匹配對，經(jīng)過遍歷運算后，建立備選匹配對集合。需要注意根據(jù)角度相似性分析原理，作為無量綱的比值閾值TDis和TΦ應具有相同的取值區(qū)間，即TΦ同樣可在0.6～0.75之間取值。

為了進一步減化運算，在實際算法設計中，計算向量之間夾角余弦值后僅保留最大和次大值，然后僅對最大和次大值做反余弦計算求取最小和次小角度值。

2.2 匹配點對篩選

由于圖像場景的復雜性，不能避免在備選匹配對集合中有錯誤匹配對存在的情況。針對該問題，采用RANSAC算法[10]對特征點對進一步篩選，保證匹配點對空間關(guān)系的一致性。

RANSAC算法原理：認為正確的匹配對在圖像中滿足空間關(guān)系的一致性，因此，可以在備選集合中不斷地隨機性抽取匹配點對，利用抽取的匹配點對建立圖像間空間投影矩陣，然后通過空間關(guān)系的一致性度量驗證該空間投影關(guān)系的正確性，多次抽取和計算后，獲得的一致性最強的空間投影矩陣即為實際的空間投影矩陣，由此可以刪除備選集合中的錯誤匹配對。

RANSAC算法的基本步驟包括[10]：

(1)從備選集合中隨機抽取 4對初始匹配點對（每個圖像平面上的4個點須滿足任意3點不共線），計算兩平面之間的線性投影矩陣的參數(shù)。

(2)對于未被抽取到的特征點，通過步驟(1)中計算得到的投影矩陣計算其在另一平面中的坐標值，進而獲得該坐標值與它預匹配的點之間的距離，若該距離很小，則該匹配點對認定為內(nèi)點，否則認定為外點，記錄內(nèi)、外點數(shù)量。

(3)多次重復步驟(1)、(2)操作，選擇內(nèi)點數(shù)量最多時對應的投影矩陣參數(shù)作為正確的投影矩陣參數(shù)。

(4)對于被確認的投影矩陣，其相應的內(nèi)點即被認定為正確的匹配點對。

經(jīng)過上述篩選后，不滿足空間一致性關(guān)系的匹配點對將被成功刪除。

2.3 算法流程

本文算法的實現(xiàn)流程如圖1所示。

新算法結(jié)構(gòu)清晰、運算簡便，易于向硬件系統(tǒng)移植。在實際應用中，可采用典型的DSP+FPGA雙核心結(jié)構(gòu)實現(xiàn)硬件設計。

圖1 本文算法流程圖

3 算法驗證與分析

將圖 2中原始圖像 SCENE（分辨率：384×512）和目標圖像BASMATI（分辨率：175×265）作為待匹配圖像，采用本文算法進行實驗。實驗環(huán)境：Intel Core i3-2 350 M 2.30 GHz CPU、4 GB（3.07 GB可用）內(nèi)存、Win7操作系統(tǒng)PC機，Matlab7.6。從圖2可以看出，原始圖像對應區(qū)域和目標圖像之間存在尺度、旋轉(zhuǎn)和仿射變換。

圖2 原始圖像（SCENE）和目標圖像（BASMATI）

實驗中，首先對SCENE圖像和BASMATI圖像進行SIFT特征點搜索，然后，分別用歐式距離分析和本文的角度相似性分析進行預匹配，當閾值 TDis和 TΦ取 0.65時，輸出結(jié)果如圖3和圖4所示。

圖 3 歐式距離法匹配結(jié)果(TDis=0.65)

在描述向量預匹配過程，歐式空間匹配法耗時6.31 s，而角度相似性匹配法耗時 4.19 s，運算速度明顯提升。圖3中，預匹配對總數(shù)量和正確匹配對數(shù)量分別為39和37，圖4中，預匹配對總數(shù)量和正確匹配對數(shù)量分別為41和39。為了更好地說明算法的有效性，將比值閾值在0.6~0.75間取值，預匹配正確率統(tǒng)計結(jié)果如表1所示。

圖 4 本文方法預匹配結(jié)果(TΦ=0.65)

表1 預匹配正確率統(tǒng)計

由于特征點匹配以遍歷搜索為基本流程，因此比值閾值的大小不影響匹配耗時。經(jīng)過預匹配后，再利用RANSAC空間一致性篩選刪除錯誤匹配對，獲得的最終匹配結(jié)果（TΦ=0.65）如圖 5所示。

圖5 RANSAC篩選后本文方法匹配結(jié)果(TΦ=0.65)

由圖5可知，錯誤匹配對被RANSAC篩選成功刪除。實驗表明，當 TΦ在（0.6，0.75）范圍內(nèi)取值時，RANSAC同樣能有效刪除錯誤匹配對。

分析上述實驗可知，本文算法的預匹配速度較傳統(tǒng)方法明顯提升，預匹配點對總數(shù)量和正確率均優(yōu)于傳統(tǒng)方法，引入RANSAC篩選后，錯誤的匹配對被成功刪除。上述實驗驗證了本文算法的有效性。

4 結(jié)論

針對SIFT匹配運算速度較慢和存在錯誤匹配對的問題，本文提出采用角度相似性分析代替?zhèn)鹘y(tǒng)的歐式距離分析，引入RANSAC篩選刪除不滿足空間一致性關(guān)系的匹配對。實驗結(jié)果表明，新算法計算速度和預匹配正確率均優(yōu)于傳統(tǒng)方法，且能夠有效刪除錯誤匹配對。后續(xù)的研究將重點著眼于如何進一步提升算法運算速度和算法的環(huán)境適應性等問題。

[1]ARICAN Z，F(xiàn)ROSSARD P.Scale-invariant features and polar descriptors in omnidirectional imaging[J].IEEE Transaction on Image Processing，2012，21(5)：2412-2423.

[2]堯思遠，王曉明，左帥.基于 SURF的特征點快速匹配算法[J].激光與紅外，2014，44(3)：347-350.

[3]余先川，呂中華，胡丹.遙感圖像配準技術(shù)綜述[J].光學精密工程，2013，21(11)：2960-2972.

[4]LOWE D G.Distinctive image feature from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60(2)：91-110.

[5]楊天天，魯云萍，張為華.一種基于GPGPU的 SIFT加速算法[J].電子技術(shù)應用，2015，41(1)：149-152，160.

[6]KE Y，SUKTHANKAR R.PCA-SIFT：A more distinctive representation for local image descriptors[C].Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition，Washington DC，USA：CVPR，2004(2)：506-513.

[7]白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究[J].北京理工大學學報，2013，33(6)：622-627.

[8]楊娜娜，哈力旦·阿布都熱依木，伊力亞爾·達吾提.基于SIFT圖像配準的維吾爾語文字識別方法[J].傳感器與微系統(tǒng)，2014，33(3)：40-43.

[9]王程冬，程筱勝，崔海華，等.SIFT算法在點云配準中的應用[J].傳感器與微系統(tǒng)，2012，31(2)：149-152.

[10]LI B，MING D，YAN W，et al.Image matching based on two-column histogram hashing and improved RANSAC[J]. IEEE Geosciences and Remote Sensing Letters，2014，11 (8)：1433-1437.

A rapid matching algorithm via image local feature

Zhang Gesen1，2，Chen Dongsheng1，Wang Huaiye1，Lu Zhenlin2
（1.Beijing Aerospace Institute of Microsystems，Beijing 100094，China；2.Postdoctoral Workstation of China Aerospace Times Electronics Corporation，Beijing 100094，China）

In the fields of image processing and machine vision,SIFT is a widely adopted image matching algorithm based on local feature.In view of the slow speed of matching and the frequently existing of the inaccurate matching pairs,the analysis of angle similarity is presented to replace the conventional Euclidean distance analysis and improve the speed in matching process.Then, RANSAC consensus selection is performed to eliminate the inaccurate matching pairs.At last,the experimental results verify the validity of proposed algorithm.The new algorithm has the advantages of clear framework,easy calculation and being easily realized by hardware.

image matching；local feature；SIFT；angle similarity；RANSAC

TP391.4

A

10.16157/j.issn.0258-7998.2015.11.035

張格森，陳東生，王懷野，等.一種圖像局部特征快速匹配算法[J].電子技術(shù)應用，2015，41(11)：124-127.

英文引用格式：Zhang Gesen，Chen Dongsheng，Wang Huaiye，et al.A rapid matching algorithm via image local feature[J]. Application of Electronic Technique，2015，41(11)：124-127.

2015-08-31）

張格森（1980-），男，博士，高級工程師，主要研究方向：圖像處理與精確制導技術(shù)、信號檢測與雷達成像。

國防科工局軍貿(mào)科研項目；國防科工局民用航天基金(2014537)

陳東生（1962-），男，博士，研究員，主要研究方向：慣性導航與信息處理技術(shù)。

王懷野（1973-），男，博士，研究員，主要研究方向：機器視覺與制導控制技術(shù)。