圖像局部特征匹配算法發(fā)展綜述

林曦蕾

（四川大學(xué)計算機學(xué)院，成都610065）

0 引言

圖像匹配算法經(jīng)過幾十年的發(fā)展，產(chǎn)生了很多經(jīng)典的算法，整體上來說可以分成四種類型[1]：基于圖像灰度的圖像匹配算法、基于變換域的圖像匹配算法、基于模板的圖像匹配算法和給予特征的圖像匹配算法。基于特征的匹配算法通過提取圖像中對形變、光照等具有不變性的信息，對這些信息進行描述構(gòu)造描述符，之后對這些特征進行匹配，計算出圖像之間幾何變換的參數(shù)。基于特征的匹配算法比起基于灰度的匹配算法是用更少的信息進行匹配，從而大大提高運算速度。除此之外，特征點等局部信息對圖像遮擋、形變等也有很好的魯棒性。常見的算法有SIFT算法[2]、SURF算法[3]、ORB 算法[4]等。

1 圖像特征匹配算法

1. 1 算法描述

基于特征的匹配算法主要包括特征提取、特征匹配、生成幾何變換這幾個步驟。特征提取是指提取出圖像中具有代表性的信息，例如：圖像中的角點、拐點等，提取出來的信息必須滿足對尺度、旋轉(zhuǎn)、光照、視角和噪聲干擾等影響因素具有一定程度的魯棒性。除此之外所提取的特征還必須具有獨特性，以防止將相似的特征被誤認為是相同的事物，從而造成特征的誤匹配。經(jīng)算法提取出來的圖像特征主要由點、線和面這三種類型，其中由點構(gòu)成局部特征對噪聲、形變等具有較強的魯棒性，因此當(dāng)前很多的特征匹配算法選擇以點作為特征。

特征匹配是指為圖像中的特征尋找對應(yīng)關(guān)系的過程。此過程如果只是使用暴力匹配的方法，算法的時間復(fù)雜度會很高，因此可以通過某些算法提高匹配的效率。例如，在SIFT算法中，利用測試圖像中的特征點建立一棵KD-Tree，之后對于參考圖像中的每一個特征點使用BBF算法[5]在測試圖像形成的KD-Tree中尋找相鄰的點。通過KD-Tree加BBF算法的匹配策略，使得特征匹配的速度有了大幅的提高。

在匹配的圖像之間存在著一種幾何變換，該幾何變換可能是放射變換、透視變換等。而生成幾何變換即為求這些幾何變換的參數(shù)的過程，常用的算法有隨機抽樣一直算法（RANSAC）[6]、模擬退火算法和遺傳算法等。

1. 2 尺度不變特征變換（SIFT）算法

SIFT算法是當(dāng)前被廣泛使用的局部特征匹配算法，該算法通過尺度空間檢測極值點作為特征點，從而實現(xiàn)特征點的尺度不變性，之后通過特征點的周邊區(qū)域內(nèi)像素為特征點計算主方向，用于實現(xiàn)旋轉(zhuǎn)不變性，最后將描述子采樣區(qū)域旋轉(zhuǎn)到特征點的方向，然后基于該區(qū)域構(gòu)造描述符。

（1）構(gòu)造DOG尺度空間

當(dāng)人們與其觀測的對象離得越遠，則所能觀察到的事物就越模糊，即尺度越大；當(dāng)與對象離得越近，則事物越清晰，尺度越小。由于機器無法預(yù)先知道圖像中物體的最佳尺度。因此，需要使用尺度空間模擬此過程。Koenderink[7]與Lindeberg[8]證明了空間高斯核是唯一可以模擬人眼對圖像造成模糊效果的線性核，因此，通過空間高斯核構(gòu)造尺度空間。其中，二維空間高斯函數(shù)表示為：

在上式中，( )x,y表示圖像像素坐標，σ表示尺度因子，它決定著圖像被模糊的程度。則一副二維圖像的尺度空間定義為：

其中I(x,y)表示輸入的圖像，而G(x ,y,σ )表示二維空間高斯函數(shù)，*表示卷積運算。

Lindeberg在文獻[9]中指出尺度規(guī)范化的LOG（Laplacian Of Gaussian）算子具有真正的尺度不變性，即讓圖像與LOG算子進行卷積運算，可檢測出斑點（特征點）以及它的尺度。因此，用于檢測特征點的是Laplacian金字塔，其中LOG算子是高斯函數(shù)的二階偏導(dǎo)。

Lindeberg[10]通過研究發(fā)現(xiàn)高斯差分算子（Difference Of Gaussian,DOG）與尺度歸一化的高斯拉普拉斯算子非常近似。由于高斯差分算子與高斯拉普拉斯算法子非常近似，且構(gòu)造尺度空間的效率更高。因此，Lowe[2]提出了用高斯差分尺度空間近似拉普拉斯尺度空間：

構(gòu)建高斯差分金字塔包括三個步驟：①構(gòu)建多分辨金字塔，每一層通過對下一層進行下采樣獲得，如圖1所示；②在構(gòu)建的多分辨金字塔的基礎(chǔ)上，對每一層的圖像使用不同的σ進行高斯模糊，從而獲得多組圖像，如圖2所示，在每一組位于最底層的圖像，是由該組圖像的下一組圖像的倒數(shù)第三張降采樣得到的；③對金字塔中處在同一層中的相鄰圖像進行相減操作，從而獲得新的一組圖像。

圖1 多分分辨率金字塔

圖2 高斯多分辨率金字塔

（2）極值點定位

為了檢測尺度空間中的極值點，需要讓尺度空間中的每一個像素與其相鄰的26個像素點進行比較，選取其中最大或最小的點作為潛在的特征點。由于在離散空間中檢測到的極值點存在誤差，因此需要通過三維二次函數(shù)擬合來精確定位極值的位置。為了精確定位極值點的位置，首先對尺度空間函數(shù)D(x,y,σ)進行泰勒展開，如下所示：

上式中X=(x,y,σ)T。之后對上式進行求導(dǎo)并令其為0，通過求解式子可得精確的位置，解得：

為了去掉低對比度的點，將求得的解 X^代入D(X )，于是可得：

為了去掉邊緣響應(yīng)點的影響，通過Hessian矩陣來判斷某處是否為邊緣，若不是邊緣則保留，否則剔除，其中Hessian矩陣為：

設(shè)α，β分別為Hessian矩陣的兩個特征值，且α大于β，又由于特征值的和與積可以通過Hessian矩陣的跡與行列式來計算得到，則有：

設(shè)r=α/β ，則：

（3）分配主方向

為了實現(xiàn)旋轉(zhuǎn)不變性，需要為檢測到的特征分配主方向。首先，計算特征點的領(lǐng)域中每個像素點的梯度的方向和大小，然后統(tǒng)計領(lǐng)域中梯度方向的分布，選取直方圖中累積梯度大小最大的梯度方向角作為主方向。領(lǐng)域內(nèi)某個點x的梯度的方向θ(x ,y)和大小m(x ,y)，可以通過以下公式得到：

（4）生成描述符

選取以特征點為中心的16×16個像素作為構(gòu)造描述符的區(qū)域。在構(gòu)建描述符之前，對用于構(gòu)建描述符的區(qū)域按主方向的角度執(zhí)行旋轉(zhuǎn)操作，如圖3所示。將旋轉(zhuǎn)之后的區(qū)域劃分為4×4個子區(qū)域，在每個子區(qū)域中統(tǒng)計8個方向的直方圖，每個方向為45°，如圖4所示，左邊部分將窗口劃分為4×4個子區(qū)域，每個子區(qū)域由4×4個像素點組成，并標出每個像素的梯度方向和大小，右邊部分每個子區(qū)域表示8個方向以及每個方向的梯度大小累積和。最后，用每個子區(qū)域中的梯度大小累積和構(gòu)成一個向量，此向量為4×4×8=128維，其即為特征點的描述符，為了消除光照變化的影響，還要對特征向量進行歸一化處理。

圖3 對描述符構(gòu)造區(qū)域執(zhí)行旋轉(zhuǎn)操作

圖4 構(gòu)造描述符

（5）特征匹配

當(dāng)為特征點構(gòu)造完描述符之后，通過相應(yīng)的特征相似度度量方法計算特征之間的相似度，從而判斷兩幅圖像中的特征是否匹配。

2 評價方式

在圖像匹配中，常用的是文獻[11]提出的特征點檢測提取和匹配結(jié)果的評價準則。

對于特征點檢測提取，評價優(yōu)劣常常用到Repeatability（重復(fù)率）這個概念。圖A、B是兩幅待匹配圖像，圖A映射到圖B有一個單應(yīng)性矩陣H1，圖B映射到圖A有單應(yīng)性矩陣H2，圖A檢測出N1個特征點，圖B檢測出N2個特征點，因為圖像A和B有部分圖像不重疊，故將A圖檢測的特征點坐標由H1算出在B圖的坐標，去掉不合格（計算結(jié)果超出在B圖像坐標）的特征點，剩下的特征點數(shù)記為n1；同樣，B圖的特征點經(jīng)過處理剩下n2個；分母便是min（n1,n2）。將圖A剩下的特征點由H1計算出在圖B中的坐標，與圖B檢測出的特征點的坐標求距離，即dist（h1*a1,b1），若距離小于閾值ε，則認為是重復(fù)的，這么做是因為得到的單應(yīng)性矩陣不一定完全精確以及一些別的誤差原因。

特征點匹配的評價首先應(yīng)當(dāng)知道兩個圖像間的單應(yīng)性矩陣H，然后通過特征點檢測算法得到左右圖像中的特征點信息，根據(jù)單應(yīng)性矩陣得到重復(fù)特征點對，記為M；接著由特征點匹配算法計算正確的匹配點對和錯誤匹配點對，分別記為N、K；繪制N/M和K/（N+K）曲線，其中曲線靠上方的結(jié)果較出色。

3 結(jié)語

基于局部特征的匹配算法給圖像匹配等領(lǐng)域帶來了不一樣的活力，而后續(xù)的相關(guān)算法的改進使得這個領(lǐng)域的算法具有更好的魯棒性，能夠更好地運用到諸如三維表面重建、立體視覺等領(lǐng)域。本文主要按照圖像特征匹配算法的發(fā)展史和其具有代表性的經(jīng)典算法，介紹了它相關(guān)的理論和評價方法。但是該領(lǐng)域仍然存在許多問題沒有完美解決，例如在幾何形變較大的匹配場景中，如何提高特征檢測子以及描述符的幾何不變性仍然需要深入研究。