朱鳴鏑 陳 嬋 孫東岳

（上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093）

1 引言

圖像匹配是許多計(jì)算機(jī)視覺(jué)算法的基本輸入。因此，其速度，準(zhǔn)確性和魯棒性至關(guān)重要。當(dāng)前，慢速（但可靠）的特征匹配器與快得多（但通常不穩(wěn)定）的實(shí)時(shí)解決方案之間存在很大的性能差距。

局部不變特征如SIFT［2］，SURF［3］和ORB［4］。已廣泛用于圖像匹配和其他計(jì)算機(jī)視覺(jué)應(yīng)用中，例如圖像檢索、對(duì)象類別識(shí)別、全景圖構(gòu)建、多光譜圖像匹配和場(chǎng)景重建等［5～13］。近年來(lái)，如何有效地匹配功能成為熱門(mén)問(wèn)題。一般而言，實(shí)現(xiàn)此目的有兩個(gè)方面的考慮。首先是為每個(gè)局部特征構(gòu)造一個(gè)描述符。理想情況下，要求描述符具有高度的區(qū)別性，并且在由相機(jī)姿勢(shì)和光照變化引起的變換中應(yīng)盡可能不變。第二是匹配描述符向量。理想情況下，需要進(jìn)行匹配步驟以獲得更多的真陽(yáng)性結(jié)果，而獲得更少的假陽(yáng)性結(jié)果，并且匹配時(shí)間成本應(yīng)盡可能低。

在圖像匹配的另一個(gè)領(lǐng)域：目標(biāo)識(shí)別和跟蹤中，模板匹配起著重要的作用［14］。模板匹配旨在找到其他圖像中的特定區(qū)域，該區(qū)域與給定的模板具有最高的相似度，并將其選擇為匹配區(qū)域。通過(guò)在另一幅圖像上以給定模板的形狀滑動(dòng)小塊，計(jì)算給定模板與小塊所覆蓋的當(dāng)前區(qū)域之間的相似度，最后選擇相似度最高的特定區(qū)域作為匹配區(qū)域。

通常模板匹配算法涉及兩個(gè)關(guān)鍵方面：相似性度量和搜索策略［15］。

相似性度量確定一次匹配的計(jì)算。搜索策略在一幀中影響匹配時(shí)間。這兩個(gè)方面都決定了目標(biāo)識(shí)別的計(jì)算時(shí)間。平均差是常見(jiàn)的相似性度量，而逐點(diǎn)匹配是常見(jiàn)的搜索策略。

通過(guò)上述分析，提出了一種新穎的參數(shù)，為每個(gè)特征點(diǎn)計(jì)算“得分”，它的作用在于篩選出符合特征點(diǎn)存在的區(qū)域，加速匹配過(guò)程。在輸入圖像的特征點(diǎn)的基礎(chǔ)上，我們使用特征點(diǎn)的坐標(biāo)信息來(lái)計(jì)算每個(gè)特征點(diǎn)的“得分”，從而高“得分”的點(diǎn)在輸入圖像中提取出矩形模板，然后用暴力匹配算法在模板匹配區(qū)域之間分別進(jìn)行特征點(diǎn)匹配。最后，使用描述符的漢明距離篩選提取的匹配項(xiàng)，以獲得最終的特征點(diǎn)匹配結(jié)果。

2 改進(jìn)模板匹配算法

實(shí)時(shí)性能是圖像匹配的前提，因此提高算法的速度始終是一項(xiàng)重要的研究。在進(jìn)行模板匹配之前，必須先從輸入圖像中提取模板，我們提出一種基于特征點(diǎn)的坐標(biāo)分布的模板提取新方法。

我們計(jì)算所有的特征點(diǎn)的得分，目的是描述某個(gè)特征點(diǎn)與其周圍特征點(diǎn)之間的位置關(guān)系，該“得分”是通過(guò)特征點(diǎn)附近的進(jìn)行計(jì)算。每個(gè)特征點(diǎn)的“得分”可以通過(guò)以下公式計(jì)算：

其中，r是高斯核的模糊半徑，σ是正態(tài)分布的標(biāo)準(zhǔn)偏差。

列出計(jì)算特定特征點(diǎn)“得分”的過(guò)程如下。

1）選擇某個(gè)特征點(diǎn)Qi，并獲取其二維坐標(biāo)（xi，yi）。

2）選擇另一個(gè)特征點(diǎn)Qj，得到其坐標(biāo)（xj，yj），計(jì)算兩個(gè)特征點(diǎn)之間距離Dij，如果沒(méi)有其他特征點(diǎn)了，跳去5）。

3）用式（2）判斷Dij的距離，εdis是提前設(shè)置好的閾值距離。如果Dij滿足式（2），視為Qj是其中之一的周圍點(diǎn)，跳去4）。否則，Qj應(yīng)該被拋棄，重新回到2）選擇點(diǎn)。

4）根據(jù)式（4），計(jì)算Qj的距離對(duì)Qi的貢獻(xiàn)度，已經(jīng)完成了Qj的整個(gè)計(jì)算過(guò)程，跳到2）選擇另外一個(gè)特征點(diǎn)。

5）清點(diǎn)Qi周圍每個(gè)點(diǎn)按高斯加權(quán)后的總距離之和，當(dāng)作該Qi的得分值。

通過(guò)理論分析可以得出結(jié)論，具有較高得分的特征點(diǎn)更有可能位于特征點(diǎn)塊的中心，而具有較低得分的那些點(diǎn)更有可能位于特征點(diǎn)塊的邊緣，甚至是孤立點(diǎn)。這里我們以TUM 數(shù)據(jù)集中的小熊為例，提取其特征點(diǎn)，從而計(jì)算其每個(gè)點(diǎn)的得分，實(shí)驗(yàn)結(jié)果如圖1～3。

圖1 TUM數(shù)據(jù)集

圖2 輸入圖像提取完特征點(diǎn)

圖3 不同顏色的***特征點(diǎn)的坐標(biāo)位置表示其“得分值”

結(jié)果表明，得分較高的特征點(diǎn)的周圍區(qū)域確實(shí)覆蓋了圖像中具有明顯紋理的特定部分。因此，根據(jù)計(jì)算出的得分，我們可以獲得覆蓋特征點(diǎn)塊的區(qū)域并將其提取為模板。根據(jù)“得分值”提取矩形模板的過(guò)程可以證明如下。

2）以Qi為中心提取輸入圖像的特定區(qū)域的矩形模型；

3）消除位于提取區(qū)域中的那些特征點(diǎn)，跳轉(zhuǎn)到1）并循環(huán)執(zhí)行此過(guò)程，直到其余點(diǎn)Kmax的最高“內(nèi)部索引”低于閾值k0為止。

圖4 TUM數(shù)據(jù)集圖像

圖5 提取出的圖像塊

3 基于改進(jìn)模板匹配的特征點(diǎn)匹配

從輸入圖像中提取矩形模板后，我們提出了一種基于模板匹配的改進(jìn)的特征點(diǎn)匹配算法：使用我們剛剛提取的矩形模板，然后在另一幅圖像上找到與特定模板匹配的區(qū)域，最后進(jìn)行特征處理模板和匹配區(qū)域之間的點(diǎn)匹配。我們?cè)谄ヅ涮卣鼽c(diǎn)時(shí)使用的方法是暴力匹配算法（BF）。在本節(jié)中，將解釋我們提出的算法。

3.1 模板匹配

從輸入圖像成功獲取圖像塊之后，對(duì)于每個(gè)單個(gè)模板，應(yīng)在其他圖像中平移該模板，直到遍歷整個(gè)圖像區(qū)域?yàn)橹?。然后，將與另一幅圖像中所選模板具有最大相似性的特定區(qū)域視為該模板的匹配項(xiàng)。相似度函數(shù)R（x，y）如下計(jì)算，其中（x，y）表示所選特定圖像塊區(qū)域的位置：

其中T'(x',y')表示所選模板T 中該點(diǎn)的已降低灰度值，(x',y')代表了點(diǎn)的坐標(biāo)。同時(shí)，I'(x+x',y+y')表示另一張圖像I 中該點(diǎn)的已降低灰度值，(x+x',y+y')表示了圖像I 中點(diǎn)的坐標(biāo)。式中兩個(gè)參數(shù)可以用以下公式計(jì)算得出：

其中w 和h 分別表示矩形模板T 的寬度和高度，x',x'',y',y''分別表示計(jì)算過(guò)程中使用的坐標(biāo)，應(yīng)該將其設(shè)置為0到w-1，或者到h-1。

此外，需對(duì)相似度函數(shù)R（x，y）進(jìn)行歸一化，因此我們可以通過(guò)下面等式得到歸一化后的相似度函數(shù)Rˉ(x,y)：

在實(shí)驗(yàn)中，我們使用前一節(jié)中提取的模板來(lái)進(jìn)行與同一數(shù)據(jù)庫(kù)中另一幅圖像的模板匹配過(guò)程。Rˉ(x,y)的閾值設(shè)為0.7。

3.2 在匹配區(qū)域的特征點(diǎn)匹配

完成模板匹配的過(guò)程后，這表示我們?cè)诹硪环鶊D像中具有與從輸入圖像中提取的每個(gè)模板圖像塊相對(duì)應(yīng)的特定匹配區(qū)域。然后，將匹配區(qū)域的特征點(diǎn)匹配過(guò)程如下所示。

1）選擇任意一塊特定的圖像塊模板；

2）提取位于模板中的所有特征點(diǎn)；

3）提取模板匹配上的另一幅圖像中的圖像塊中的所有特征點(diǎn)；

4）使用蠻力匹配算法來(lái)匹配這兩組特征點(diǎn)：首先，選擇模板中的某個(gè)特征點(diǎn)，然后計(jì)算選定點(diǎn)與匹配區(qū)域中每個(gè)點(diǎn)之間的描述符漢明距離，最后，描述符的漢明距離最小的特定點(diǎn)應(yīng)與所選點(diǎn)的匹配點(diǎn)有關(guān)。循環(huán)此過(guò)程，直到遍歷模板中的所有特征點(diǎn)；

5）選擇描述符的漢明距離較小的那些特征點(diǎn)對(duì)作為最終匹配結(jié)果。循環(huán)整個(gè)過(guò)程1）～5），直到遍歷所有模板。

不同模板及其匹配區(qū)域之間的特征點(diǎn)的整體匹配結(jié)果如圖6所示。

圖6 整體匹配結(jié)果圖

4 實(shí)驗(yàn)

為了驗(yàn)證上述提出的特征點(diǎn)匹配算法的可行性，利用TUM 數(shù)據(jù)集中的圖片作為主要匹配的圖像。我們的算法中使用的參數(shù)和閾值已針對(duì)不同的情況進(jìn)行了調(diào)整，并且與其他兩種常用的特征點(diǎn)匹配算法的匹配結(jié)果進(jìn)行了比較。

1）暴力匹配算法（Brute Force matching algorithm）；

2）高維數(shù)據(jù)的快速最近鄰算法（FLANN）。

由于本文提出的算法是改進(jìn)模板匹配的基于BF 的特征點(diǎn)匹配算法，因此，通過(guò)與直接使用BF的匹配結(jié)果進(jìn)行比較，可以看出本文算法的優(yōu)勢(shì)。現(xiàn)在，F(xiàn)LANN 在特征點(diǎn)的可用率和匹配結(jié)果的準(zhǔn)確性上都超過(guò)了BF，通過(guò)將我們提出的算法與FLANN 的匹配結(jié)果進(jìn)行比較，具有實(shí)驗(yàn)意義。實(shí)驗(yàn)和比較的結(jié)果顯示在以下各節(jié)中。

我們的算法在不同場(chǎng)景下的匹配結(jié)果如圖7所示。

圖7 提出算法的匹配結(jié)果圖

以TUM的bear圖為例，我們提出的算法，BF和FLANN的匹配結(jié)果如圖8所示。

結(jié)果表明，在bear 的場(chǎng)景下，我們提出的算法可以提取出更多的特征點(diǎn)匹配，而錯(cuò)誤匹配更少。其他方案的匹配結(jié)果顯示在圖9的縮略圖中。

圖9 使用我們的不同場(chǎng)景的特征點(diǎn)匹配結(jié)果從上到下分別是提出了算法，BF和FLANN

選擇了不同的指標(biāo)，nmatch和ncorrect它們分別表示特征點(diǎn)匹配的數(shù)量和正確匹配的數(shù)量。統(tǒng)計(jì)結(jié)果如表1所示。

表1 特征點(diǎn)匹配結(jié)果的統(tǒng)計(jì)結(jié)果

特征點(diǎn)匹配δ的正確率可以計(jì)算如下：

最終的統(tǒng)計(jì)結(jié)果如圖4～10所示。

本節(jié)以TUM 數(shù)據(jù)集中的圖片來(lái)驗(yàn)證了改進(jìn)算法實(shí)驗(yàn)的正確性。實(shí)驗(yàn)證明，改進(jìn)算法能夠減少圖像中的誤匹配對(duì)，提高匹配精度。

圖10 分析不同場(chǎng)景下的不同匹配算法

5 結(jié)語(yǔ)

視覺(jué)里程計(jì)中常用flann 和暴力匹配算法進(jìn)行匹配，而暴力匹配經(jīng)常出現(xiàn)錯(cuò)誤匹配是因?yàn)槿鄙偬卣髌ヅ洳皇怯捎谔俚恼_匹配，而在于很難分辨真假，故加入模板匹配進(jìn)行約束，提出一種改進(jìn)模板匹配算法。為了提升匹配速度和精度，該算法通過(guò)提供特征點(diǎn)的坐標(biāo)，可以計(jì)算出每個(gè)特征點(diǎn)的得分值，并將其用于從輸入圖像中提取模板。基于輸入圖像和另一幅圖像之間的模板匹配，使用暴力匹配算法在模板和匹配區(qū)域之間進(jìn)行特征點(diǎn)匹配。該算法可以將高匹配數(shù)轉(zhuǎn)換為高匹配質(zhì)量。在室內(nèi)數(shù)據(jù)集TUM 的實(shí)驗(yàn)結(jié)果表明，該算法匹配速度較快、準(zhǔn)確度較好。