林曦蕾

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

0 引言

圖像匹配算法經(jīng)過(guò)幾十年的發(fā)展，產(chǎn)生了很多經(jīng)典的算法，整體上來(lái)說(shuō)可以分成四種類型[1]：基于圖像灰度的圖像匹配算法、基于變換域的圖像匹配算法、基于模板的圖像匹配算法和給予特征的圖像匹配算法?；谔卣鞯钠ヅ渌惴ㄍㄟ^(guò)提取圖像中對(duì)形變、光照等具有不變性的信息，對(duì)這些信息進(jìn)行描述構(gòu)造描述符，之后對(duì)這些特征進(jìn)行匹配，計(jì)算出圖像之間幾何變換的參數(shù)?；谔卣鞯钠ヅ渌惴ū绕鸹诨叶鹊钠ヅ渌惴ㄊ怯酶俚男畔⑦M(jìn)行匹配，從而大大提高運(yùn)算速度。除此之外，特征點(diǎn)等局部信息對(duì)圖像遮擋、形變等也有很好的魯棒性。常見的算法有SIFT算法[2]、SURF算法[3]、ORB 算法[4]等。

1 圖像特征匹配算法

1. 1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

圖1 多分分辨率金字塔

圖2 高斯多分辨率金字塔

（2）極值點(diǎn)定位

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

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

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

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

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

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

（3）分配主方向

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

（4）生成描述符

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

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

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

（5）特征匹配

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

2 評(píng)價(jià)方式

在圖像匹配中，常用的是文獻(xiàn)[11]提出的特征點(diǎn)檢測(cè)提取和匹配結(jié)果的評(píng)價(jià)準(zhǔn)則。

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

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

3 結(jié)語(yǔ)

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