圖像局部特征匹配算法發展綜述

林曦蕾

（四川大學計算機學院，成都610065）

0 引言

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

1 圖像特征匹配算法

1. 1 算法描述

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

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

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

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

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

（1）構造DOG尺度空間

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

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

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

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

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

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

圖1 多分分辨率金字塔

圖2 高斯多分辨率金字塔

（2）極值點定位

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

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

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

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

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

設r=α/β ，則：

（3）分配主方向

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

（4）生成描述符

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

圖3 對描述符構造區域執行旋轉操作

圖4 構造描述符

（5）特征匹配

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

2 評價方式

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

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

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

3 結語

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