基于局部近鄰圖的特征描述與特征匹配算法研究

謝宜婷 王愛平 鄒 海

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

?

基于局部近鄰圖的特征描述與特征匹配算法研究

謝宜婷 王愛平 鄒 海

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

特征描述和特征匹配是計算機視覺領域的重要組成部分。近年來，為了實現圖像匹配上的可靠性和魯棒性，許多特征描述算法被提出來，例如SIFT、SURF、DAISY和BRIEF等。然而，當圖像發生平移、旋轉、縮放等大視角變化時，這些描述符通常會失效。為了解決這個問題，在局部近鄰圖模型的基礎上，提出一種新穎的特征描述和相似性度量方法(LNFM算法)。所提出的描述符和相似度可以很好地應用于各種流行的圖像匹配算法。實驗結果表明：在特征匹配過程中，該算法可以檢測到可靠的匹配關系，性能較為優越。

特征描述 局部近鄰圖 特征匹配 相似性度量

0 引 言

假如給定同一場景中的兩幅或多幅圖像，特征匹配的任務就是確定不同圖像中對應特征點的匹配關系。圖像特征匹配是計算機視覺和模式識別領域中的一個基本問題，也是最核心的問題之一。據相關報道統計，它在60%的機器視覺問題中[1-5]，如圖像檢索、圖像合并、指紋識別、運動目標跟蹤、醫學圖像分析等都有著廣泛的應用。基于特征點的匹配過程包括以下三個步驟：圖像特征的檢測；特征描述符的提取；特征描述符的相似性度量。

其中，特征描述是基于特征點的匹配方法中一個很關鍵的步驟，對圖像匹配的效果起到了決定性作用。良好的特征描述符應具有魯棒性和獨特性兩種性質，魯棒性是指對灰度、光照、顏色等光度變化和平移、旋轉、尺度等幾何變形魯棒；獨特性是指所提取的描述符應該具有充分的信息來辨別不同的特征點。特征描述符的構造很多是基于局部結構信息的，近幾年來，以SIFT為代表的基于描述符的特征匹配方法尤為突出，且應用最廣。但是，當場景中存在物體遮擋或者場景中存在較多復雜結構時，離群匹配會大大增加。遇到這種情況，常用的方法是首先對圖像的局部結構進行相似性度量，然后在此基礎上，加入一些幾何約束條件，從而提高特征匹配的性能。為了更高效地描述特征點之間的局部幾何約束關系，通常將這些約束關系表示為屬性關系圖的結構形式，其中，圖像里面提取的特征點表示為圖的頂點，特征點之間的幾何約束關系表示為圖的邊。因此，圖像特征匹配問題就可以轉化成為圖匹配問題去求解。

本文提出了一種新穎的特征描述方法，首先通過FAST和SURF算法檢測初始特征點，然后為每個特征點構建局部圖，使用的是其近鄰特征點。與以往的特征描述符[6-7]不同，本文方法通過考慮每個特征點及其近鄰特征點，給出了一個相似性度量函數。在這種新穎的特征描述符和相似性度量函數的基礎上，提出了一種基于局部近鄰圖的特征匹配算法。該算法在理論上和實際應用中都具有重要的意義。實驗表明：該算法有良好的性能，提高了特征匹配算法的精度。

1 相關工作

特征描述是計算機視覺領域中的一個基礎性探究問題，在建立圖像之間的對應關系以及物體識別中發揮著十分重要的作用。特征描述是特征匹配的基礎，在進行圖像特征匹配的過程中，建立圖像之間特征點與特征點之間的可靠對應關系通常都依賴于一個優秀的特征描述符。

在眾多的特征描述符中，Lowe[8]提出的SIFT是其中應用最廣的。它對平移、旋轉、尺度以及大視角和光照變化等都具有不變性，并且具有很好的可區別性。Bay等[9]提出的SURF是對SIFT的改進，它利用Haar小波來近似SIFT方法中的梯度操作，同時利用積分圖技術進行快速計算，其魯棒性很好且計算速度較快。Tola等[10]在2007年提出了DAISY，其本質思想和SIFT是一樣的，不同的是，DAISY利用了高斯卷積的可快速計算性，可以快速稠密地進行特征描述符的提取。Morel等[11]提出的ASIFT(Affine SIFT)通過模擬各種成像視角下得到的圖像進行特征點匹配，可以高效地處理不同視角變化的情況，尤其是大視角變化下的特征點匹配。Calonder等[12]提出了BRIEF描述符用于實時匹配，它是基于二進制位串的，不僅匹配速度快，而且存儲要求低。

優秀特征描述符的獲取是為了更準確地進行特征匹配，近年來，很多基于圖理論的特征匹配算法被提出，受到了計算機視覺領域中很多專家和學者的關注。Leordeanu等[13]提出一種譜匹配算法SM(Spectral Matching)，該算法首先構造親鄰矩陣，然后用譜分解方法獲得親鄰矩陣的最大特征值對應的特征向量，以此實現特征點之間的匹配。Caetano等[14]提出了一種基于圖模型(Graphic model)的特征匹配算法，該方法的核心思想是將圖匹配問題轉換為概率推理問題去求近似解，在無噪聲的環境中，此算法獲得的圖像匹配效果良好。Bolles等[15]提出隨機采樣一致性算法RANSAC(Random Sample Consensus)來去除離群匹配，雖然該算法可以魯棒地估計模型參數，但是它只能從某個特定的數據集中估計出一個模型。如果存在兩個及其以上的模型，RANSAC算法則會失效。Aguilar等[16]提出了一種圖變換匹配算法GTM(Graph Transformation Matching)，該算法在k近鄰圖模型的基礎上，根據幾何一致性約束條件，從初始匹配關系中尋找相應的匹配關系子集，最終可以獲得較多的正確匹配關系。Cho等[17]提出漸進的圖匹配算法ProGM(Progressive Graph Matching)，通過貝葉斯框架不斷地更新目標圖，從而在后續的圖匹配中增加匹配關系數目。

以上的圖像匹配算法使用傳統的特征描述符，通過一組特征點來描述對象，進而找到初始匹配關系。然而，這些特征描述符存在固有的缺點，即在圖像發生顯著變化時，不能準確地表示特征點。本文提出的算法克服了這個困難，通過使用圖像的局部近鄰結構來表示特征點。

2 局部近鄰圖描述

算法1局部圖模型化

輸入：特征點集K，距離閾值Td，重疊閾值T0，近鄰節點個數最大值n。

步驟1：對每一個vi∈K、vj∈K且i≠j，計算vi和vj之間的歐式距離dij。如果dij

步驟2：如果|Vi|>n，取前n個最近鄰的特征點。將vi加入Vi，然后更新Vi的屬性，接著以vi為中心點，連接Vi中的其余節點，至此，形成了一個星狀局部圖，即Gi=(Vi,Ei,Ai)。

步驟3：所有的vi進行步驟1和步驟2兩步操作之后，形成了局部圖集S={Gi|i=1,2,…,M}。

本文算法采用MATLAB來實現，局部近鄰圖算法流程圖如圖1所示。

圖1 局部近鄰圖算法流程圖

在局部近鄰圖模型的基礎上，本文提出一個相似性度量函數F(i,j)，用來計算圖Gi和圖Gj之間的相似度，定義如下：

(1)

式中，a和b表示圖Gi和圖Gj中的節點指數，也就是說，1≤a≤n且1≤b≤n。G(·)是一個高斯分布函數，β和d分別是相對根特征點的角度和歸一化距離，相似性函數F(i,j)是所有節點的最大相似性值的聚合。基于圖論的描述符在特征域中生成之后，如果一些特征點由于大視圖更改或變形而消失，那么圖的幾何特性會被破壞，這與特征檢測器的性質有很大關系。為了防止依賴于特征檢測器，我們只聚合每個節點的最大相似性值。因此，相似性函數F(i,j)的值越大，描述符之間匹配的可能性越高。

3 局部近鄰圖的特征匹配

算法2基于局部近鄰圖的特征匹配算法

步驟2：能量函數E(x)=∑φi(xi)+∑φij(xi,xj)由一元項φi(xi)和二元項φij(xi,xj)組成，根據式(2)和式(3)分別計算出φi(xi)和φij(xi,xj)的值，然后進行累加求和，即可得到E(x)的值。

步驟3：最后利用x*=argminxE(x)解出x*，根據x*的取值，恢復出兩個局部圖集S和S′之間的對應關系。

利用式(1)的相似性函數F(i,j)，一元能量函數φi(xi)定義如下：

φi(xi) =e-F(i,xi )

(2)

另一方面，二元能量函數φij(xi,xj)定義如下：

(3)

因此，根據以上一元項和二元項的定義，能量函數E(x)的計算公式如下：

E(x)=∑φi(xi)+∑φij(xi,xj)

(4)

通過使用最大積環路信念傳播算法[19]，可以獲得x*=argminxE(x)的解。

4 實驗與分析

本文實驗是在MATLAB R2014a、Win2007系統中運行的，實驗圖象數據來源于Caltech-101[20]和MSRC圖像庫[21]。為了驗證算法的有效性和魯棒性，本文首先添加高斯噪聲進行模擬實驗，然后在真實圖像上做特征匹配實驗，主要與SM方法進行比較。其中，特征點是由FAST和SURF 算法進行檢測。在本文算法中，局部圖中近鄰節點的最大個數n設置為12，距離閾值Td設置為5倍的特征尺度。對于實驗參數的選擇，近鄰節點的最大個數n和距離閾值Td等都是為了構建大小合適的局部近鄰圖。例如，在本文中設置近鄰節點的最大個數n=12，如果n值設置得較大，則獲得的局部近鄰圖個數會很少，導致正確匹配數目變少，從而影響算法的精度；如果n值設置得較小，則獲得的局部近鄰圖個數會很多，導致錯誤匹配數目變多，從而影響算法的精度。

4.1 高斯噪聲模擬實驗

(a) 離群點實驗

(b) 變形噪聲實驗圖2 實驗對比結果

由圖2(a)和(b)的模擬結果可以看出，本文在局部近鄰圖模型的基礎上，提出的特征匹配算法，即LNFM算法的平均精度要比SM算法的高。因此，LNFM算法的性能比SM算法有優勢。

4.2 真實圖像特征匹配實驗

在Caltech-101和MSRC圖像庫上，本文所提出的局部近鄰圖的特征匹配算法與SM算法用于檢測同一對圖像上的目標所獲得的匹配關系數目是不同的。為了便于觀察，每對圖像中正確匹配用一般直線表示，錯誤匹配用帶有標記的直線表示。圖3—圖8分別是6個不同目標的特征匹配結果。

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖3 目標1匹配結果

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖4 目標2匹配結果

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖5 目標3匹配結果

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖6 目標4匹配結果

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖7 目標5匹配結果

(a) LNFM算法匹配結果

(b) SM算法匹配結果圖8 目標6匹配結果

雖然以上這些圖像發生了平移、旋轉、視角、尺度等復雜變換，但是用本文的方法仍能獲得較多的正確匹配關系。為了定量分析，在此定義匹配精度來對兩種算法進行比較。

(5)

每對圖像，手動地標記正確匹配關系的個數，根據式(5)，計算出匹配精度的值，記為MK_i，其中下標i∈{1,2}代表兩種不同的方法(i=1是本文方法，i=2是SM方法)。如果MK_1>MK_2，則表明本文算法比SM算法有優勢，反之亦然，表1為相應的對比結果。

表1 Caltech-101和MSRC圖像庫上特征匹配精度

由表1的統計結果和圖2—圖8的匹配效果可以看出，本文在局部近鄰圖模型的基礎上，提出的特征匹配算法在真實圖像特征匹配的過程中，LNFM算法的性能明顯比SM算法要優越得多，本文LNFM算法的匹配精度要比SM算法的高。

5 結 語

本文在局部近鄰圖模型的基礎上，提出了一種新穎的特征匹配算法。在所提出的方法中，初始特征點首先通過FAST和SURF算法進行檢測，然后為每個特征點構造局部圖，每個局部圖是由根特征點及其近鄰特征點組成的。基于局部近鄰圖模型，本文給出了一個相似性度量函數，用于計算兩個局部圖之間的相似度。在特征匹配過程中，利用相似性度量函數，本文提出一個能量函數來找到兩個局部圖集之間的對應關系，最終達到圖像匹配的效果。本文算法與SM算法進行了比較，實驗的實例圖、定量分析結果，以及高斯噪聲模擬實驗結果都表明本文算法在匹配精度上顯示性能優越。本文算法可應用于車牌字符的識別。為了識別車流量較大的市區道路上的車牌號碼，首先給出一個標準字符模板樣式，運用本文局部近鄰圖的特征匹配算法，將標準化的車牌區字符和字符模板進行匹配，進而達到車牌字符識別的目的。對實際交通環境中的各種車牌類型運用本文算法進行識別，識別率約達92%，結果較為滿意。

[1] Ma J, Zhou H, Zhao J, et al. Robust feature matching for remote sensing image registration via locally linear transforming[J].IEEE Transactions on Geoscience and Remote Sensing, 2015, 53(12): 6469-6481.

[2] Arnfred J T, Winkler S. A general framework for image feature matching without geometric constraints[J].Pattern Recognition Letters, 2016, 73: 26-32.

[3] Zhou W, Yang M, Wang X, et al. Scalable feature matching by dual cascaded scalar quantization for image retrieval[J]. IEEE transactions on pattern analysis and machine intelligence, 2016, 38(1): 159-171.

[4] Chen H Y, Lin Y Y, Chen B Y. Co-segmentation guided hough transform for robust feature matching[J]. IEEE transactions on pattern analysis and machine intelligence, 2015, 37(12): 2388-2401.

[5] Ma J, Ma Y, Zhao J, et al. Image feature matching via progressive vector field consensus[J]. IEEE Signal Processing Letters, 2015, 22(6): 767-771.

[6] Murala S, Maheshwari R P, Balasubramanian R. Local tetra patterns: a new feature descriptor for content-based image retrieval[J]. IEEE Transactions on Image Processing, 2012, 21(5): 2874-2886.

[7] Ma B, Chai X, Wang T. A novel feature descriptor based on biologically inspired feature for head pose estimation[J]. Neurocomputing, 2013, 115: 1-10.

[8] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

[9] Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features (SURF)[J]. Computer vision and image understanding, 2008, 110(3): 346-359.

[10] Tola E, Lepetit V, Fua P. Daisy: An efficient dense descriptor applied to wide-baseline stereo[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 32(5): 815-830.

[11] Morel J M, Yu G. ASIFT: A new framework for fully affine invariant image comparison[J]. SIAM Journal on Imaging Sciences, 2009, 2(2): 438-469.

[12] Calonder M, Lepetit V, Ozuysal M, et al. BRIEF: Computing a local binary descriptor very fast[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1281-1298.

[13] Leordeanu M, Hebert M. A spectral technique for correspondence problems using pairwise constraints[C]//Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. IEEE, 2005, 2:1482-1489.

[14] Caetano T S, Caelli T, Schuurmans D, et al. Graphical models and point pattern matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10): 1646-1663.

[15] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[16] Aguilar W, Frauel Y, Escolano F, et al. A robust graph transformation matching for non-rigid registration[J]. Image and Vision Computing, 2009, 27(7): 897-910.

[17] Cho M, Lee K M. Progressive graph matching: Making a move of graphs via probabilistic voting[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012:398-405.

[18] Rublee E, Rabaud V, Konolige K, et al. ORB: An efficient alternative to SIFT or SURF[C]//2011 International conference on computer vision. IEEE, 2011: 2564-2571.

[19] Felzenszwalb P F, Huttenlocher D P. Efficient belief propagation for early vision[J]. International journal of computer vision, 2006,70(1): 41-54.

[20] Fei-Fei L, Fergus R, Perona P. One-shot learning of object categories[J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28(4): 594-611.

[21] Winn J, Criminisi A, Minka T. Object categorization by learned universal visual dictionary[C]//Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1. IEEE, 2005, 2:1800-1807.

RESEARCHOFFEATUREDESCRIPTIONANDFEATUREMATCHINGALGORITHMBASEDONLOCALNEIGHBORHOODGRAPH

Xie Yiting Wang Aiping Zou Hai
(CollegeofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

Feature description and feature matching are important parts in the field of computer vision. In recent years, many feature description algorithms have been proposed to achieve reliable and robust performance in image matching, such as SIFT, SURF, DAISY and BRIEF. However, their descriptors usually fail when the images have undergone large viewpoint changes such as translation, rotation and scaling. To solve this problem, on the basis of local neighborhood graph model, a novel feature description and similarity measure method (referred to as LNFM algorithm) is proposed. The proposed descriptor and similarity can be well applied to a variety of popular image matching algorithms. The experimental results show that: in the process of feature matching, the proposed algorithm can detect reliable matching relationship, and the performance is relatively superior.

Feature description Local neighborhood graph Feature matching Similarity measure

2016-08-06。國家自然科學基金項目(61573022)。謝宜婷，碩士生，主研領域：圖像匹配與識別。王愛平，教授。鄒海，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.08.033