多傳感器輔助的快速圖像匹配算法

李自豪，李培林，王　崴,2，瞿　玨，彭勃宇

(1.空軍工程大學防空反導學院，陜西 西安　710051；2.西安交通大學機械制造系統工程國家重點實驗室, 陜西 西安　710049)

?

多傳感器輔助的快速圖像匹配算法

李自豪1，李培林1，王崴1,2，瞿玨1，彭勃宇1

(1.空軍工程大學防空反導學院，陜西 西安710051；2.西安交通大學機械制造系統工程國家重點實驗室, 陜西 西安710049)

針對現有圖像匹配算法效率和精度難以兼顧的問題，提出了多傳感器輔助的快速圖像匹配算法。該算法利用FAST算法提取特征角點，再利用SIFT算法為特征點生成主方向和描述符；并結合基于點積的相似度度量，利用多傳感器輸出的姿態數據輔助搜索策略，以完成快速初匹配；最后通過統計特征點距離誤差的方法剔除誤匹配點，獲取最終同名點集。實驗表明，該圖像匹配算法在效率和精度方面均優于傳統的SIFT算法，能夠滿足增強現實系統對圖像匹配算法的精度高、速度快的要求。

FAST角點檢測；SIFT特征；多傳感器；誤匹配剔除；快速匹配

0　引言

虛實注冊作為增強現實系統的關鍵和難點，用來實現虛擬信息與真實世界場景的準確融合。由于視覺和定位傳感器在特性上的互補，構建混合視覺和定位傳感器的注冊系統成為當前研究熱點。混合系統中視覺注冊的一個關鍵步驟就是找到圖像之間的匹配點對，匹配的準確與否直接影響到后續攝像機位置和姿態的計算精度，而匹配的速度則影響到增強現實系統的實時性。由于增強現實誘導維修系統需要給用戶呈現準確流暢的虛實疊加影像，所以對圖像匹配的精度和速度都提出了較高的要求。

圖像間匹配點對搜尋的過程主要分為圖像特征的提取和特征的匹配兩大步驟，快速提取較為魯棒的特征并進行迅速準確的匹配是算法的發展方向。由 D.G.Lowe于2004年提出的SIFT(Scale Invariant Feature Transform)[1-2]算法在尺度空間中使用鄰域梯度信息對特征進行提取和描述，使得SIFT特征對圖像的旋轉、縮放和噪聲干擾甚至仿射變換都具有較好的魯棒性。但其存在計算量大的缺點，難以滿足系統的高實時性要求。

角點檢測算法是一種常用的圖像特征提取算法，常用的有Moravec[3]、Forstner[3]、Harris[4]、SUSAN[5]和FAST[6]。因為角點檢測算法能夠快速檢測圖像中角點特征，因而將角點檢測算法與SIFT特征描述符結合成為了近年來圖像匹配研究的熱點。加速分割檢測特征(features from accelerated segment test，FAST)是由Rosten和Drummond于2006年提出的一種簡單、快速的角點檢測算法，通過該算法可以快速確定出角點，使特征提取達到毫秒級別，可應用于實時視頻的處理，但其旋轉不變性差，光照不變性差，魯棒性差，難以滿足增強現實系統對匹配精度的要求。而且大多數增強現實應用中圖像匹配過程只是單純使用一種現有的匹配算法，沒有針對所處的增強現實應用環境進行優化和改良，匹配的精度和效率難以有效提升。本文針對此問題，提出了多傳感器輔助的快速圖像匹配算法。

1　算法基礎

1.1FAST角點檢測算法

FAST算法中，為找到局部穩定特征，首先要在每幀內檢測到穩定的角點位置。在某個像素點的周圍鄰域內有足夠多的像素點與該點處于不同的灰度區域時，該點被確認為一個FAST角點。

首先通過分割測試，篩選候選角點。將目標圖像與如圖1所示的一固定半徑的圓形模板進行比較和計算。待檢測點O是否為角點取決于其周圍編號為1—16的灰度值。只要周圍像素點高于某一閾值的個數大于n，那么該O點就是候選角點。

經以上步驟后，在實際角點處可能仍然存在多個興趣點，因此最后需要通過局部非極大值抑制定位角點特征。在上面的分割測試中，沒有計算角點響應函數，非極大值抑制無法直接應用于提取的特征。因此，定義一個角點響應函數V，考慮到分割測試的特征以及計算速度的需要，角點函數定義如下：

(1)

定義了角點響應函數后，就可以采用非極大值抑制方法對非角點進行排除。

圖1　FAST圓形模板示意圖Fig.1　Schematic diagram of circular template

1.2特征點主方向的確定

在SIFT算法中，為實現圖像旋轉的不變性，需要利用圖像局部特征給每個特征點分配主方向。統計以特征點為中心的鄰域內梯度的模值和方向并用直方圖表示。統計時，對鄰域內梯度進行高斯加權，其中σ=1.5，圖2中的圓圈表示加權范圍。圖2中為簡化給出了8個方向的直方圖統計結果，D.G.Lowe的原文中采用36方向直方圖。取圖中達最大值80%以上的為輔方向，這樣一個特征點可能具有多個方向，可增強匹配的魯棒性。

圖2　生成特征點主方向Fig.2　Generate the main direction of feature point

1.3SIFT描述符的生成

為使特征描述符具備旋轉不變性，首先以特征點為中心將坐標軸旋轉至特征點的主方向。以特征點為中心取16×16窗口鄰域，對鄰域內梯度進行高斯加權，并在每4×4的小塊上統計8個方向上每個方向的梯度和，形成圖3所示的子點。每個子點有8個方向的梯度信息，特征點鄰域內有4×4共16個子點，可形成128維梯度描述向量，即SIFT特征描述符。此時的特征描述符已經去除了尺度、旋轉等幾何因素的影響，最后將描述向量進行單位化以進一步去除光照變化的影響。利用鄰域梯度信息的方法在降低算法對噪聲的敏感性的同時提升了算法對特征定位誤差的容錯能力。

圖3　生成特征點描述符Fig.3　Generate the feature point descriptors

2　混合多傳感器的快速匹配算法

綜合FAST角點和SIFT描述符的優勢并結合慣性傳感器的位姿輔助提出了本文的混合匹配算法。首先利用FAST算法提取特征角點，然后利用SIFT算法為特征點生成主方向和描述符。之后，結合基于點積的相似度度量，利用多傳感器輸出的姿態數據輔助搜索策略，以完成快速初匹配。然后，通過統計特征點距離誤差的方法剔除誤匹配點，獲取最終同名點集圖4為算法的流程圖。

圖4　算法流程圖Fig.4　Flow chart of the algorithm

2.1基于向量點積的相似度度量

特征點的匹配本質上是描述符間相似度的度量，傳統的歐氏距離度量法是通過搜索待匹配圖像中特征點A到參考圖像中歐氏距離最小點C和距離次小點D(最鄰近點與次鄰近點)，計算最鄰近距離與次鄰近距離的比值rat，并將rat與設置的閾值T進行比對，若小于閾值則認為待匹配點A與最鄰近點C為一對匹配點。這里T通常取0.8。

(2)

對于n維的特征描述符，每求一次歐氏距離都要進行n次減法、n次平方、n-1次加法和1次開方。計算量較大，對此本文提出了一種通過向量點積度量特征點之間相似度的快速匹配算法。

特征描述符X，Y之間的夾角θ(X,Y)可表示為：

(3)

由于特征描述符已進行過單位化處理，所以模值均為1，因此X，Y之間夾角的余弦值可表示為兩向量的內積形式。

(4)

當T1增大，T2減小時匹配對數逐漸減少，通過實驗發現當T1=0.5，T2=0.7時可有效剔除90%的誤匹配同時正確匹配損失不超過5%，能夠取得較好的匹配效果。

由式(4)可知，對于n維的特征描述符，作一次點積只需要進行n次乘法和n-1次加法，運算量和計算歐氏距離相比大大減少，因此用點積代替歐氏距離作為相似性度量能有效提高算法的快速性。

2.2多傳感器輔助的圖像匹配策略

2.2.1多傳感器硬件系統

混合跟蹤注冊[8]的傳感器系統由視覺傳感器(攝像頭)、陀螺儀、加速度計和地磁感應計組成。選用集成了三軸陀螺儀和三軸加速度計的MEMS芯片MPU6050作為慣性傳感器，且選用集成了三軸地磁傳感器的MEMS芯片HMC5883采集地磁數據，芯片內置OFFSET/SET/RESET電路，不會出現磁飽和與累加誤差現象，支持自動校準程序，簡化使用步驟，能夠滿足測量要求。MPU6050和HMC5883內部都自帶16位A/D轉換器并支持I2C總線。

MPU6050和HMC5883焊接在一塊電路板上，并選用基于CortexM3內核的STM32系列ARM處理器STM32F103U8T6進行數據采集，以此構建了慣性/地磁傳感器模塊。STM32F103U8T6主頻達72 MHz，具有1.25 DMIPS/MHz的計算能力，具有硬件單周期乘法器，以保證姿態更新的實時性。模塊上的傳感器通過I2C接口和處理器連接，傳感器數據中斷引腳與STM32的I/O相連，使得處理器能在傳感器在完成AD轉換后的第一時間讀取更新數據。圖5為慣性/地磁模塊硬件框圖。

圖5　慣性/地磁模塊硬件框圖Fig.5　Hardware block of inertia/ geomagnetism module

攝像頭和慣性/地磁模塊一同固連在自制的增強現實頭盔上，如圖6所示。

圖6　混合注冊AR頭盔Fig.6　AR helmet of mixed registration

2.2.2位姿估計和輔助策略

攝像頭的采樣頻率為30 Hz，相鄰兩幅幀圖像拍攝時間間隔為1/30 s，根據觀察者頭部運動實際情況，相鄰兩幅幀圖像間攝像頭運動應是短時間、小范圍的姿態位置變化，且慣性數據的更新頻率遠高于視覺圖像更新頻率。因此匹配相鄰兩幅幀圖像時，通過對陀螺儀、加速度計的量測值積分進行積分得到攝像頭的位姿變化。獲取姿態變化后可將特征點在待匹配圖像中進行重新投影，并根據投影位置劃定匹配搜索區域。

通過互補濾波器[9]的姿態輸出和對加速度計進行積分得到兩幅幀圖像拍攝時攝像頭姿態和位置變換為ΔR和ΔT，空間中一點P在第k幀圖像(參考圖像)中的坐標為pk(uk,vk)，第k幀和第k+1幀時刻點P在攝像頭坐標系下的坐標分別為Pk(xk,yk,zk)和Pk+1(xk+1,yk+1,zk+1)，下面求點P在第k+1幀圖像(待匹配圖像)中重新投影的位置pk+1(uk+1,vk+1)。

首先由透視投影模型得到式(5)和式(6)：

(5)

(6)

由式(5)得

(7)

代入式(6)得

根據慣性數據點P在待匹配圖像上的重投影的坐標pk+1(uk+1,vk+1)并根據其劃定匹配搜索范圍。這里以pk+1為圓心，R為半徑劃定圓形匹配區域，R根據幀圖像時間間隔和攝像頭運動參數按式(9)自適應選?。?/p>

(9)

根據攝像頭姿態預測特征點區域，在有效降低運算量的同時，合理降低了誤匹配點的出現概率，有效提升了算法的速度和精度。攝像機坐標系，物體坐標系和圖像坐標系之間關系如圖7所示。

圖7　攝像機、物體坐標系、圖像面坐標系關系圖Fig.7　The relationship between coordinate system

2.3誤匹配點快速剔除

經過上述特征匹配后得到初匹配點集S，不可避免地其中會存在一定數量的誤匹配點，因此需要對初匹配點集進行誤匹配點剔除。RANSAC(Random Sample Consensus)算法[10]是常用的誤匹配點剔除方法，它是從一組包含“局外點”的觀測數據中，通過迭代方式估計模型的參數。它是一種不確定算法，通過增加迭代次數提高概率，會產生較大的計算量，因此本文提出了一種通過統計特征點間距離均值誤差以剔除誤匹配點的方法。設Ai,Bi∈S(i=1，2，…，n)，其中Ai,Bi分別是位于待匹配圖像和參考圖像中相匹配的特征點，統計特征點間距離均值誤差的方法可描述如下：

(10)

3　實驗分析

在CoreI5 3.1GHzCPU，4GBRAM的windows7微機上使用VS2010結合openCV編程實現了本文算法。首先對本文的算法與SIFT算法的匹配性能進行了比較；然后驗證了本文算法在視角變化和有無遮擋干擾下的魯棒性；系統中攝像機拍攝的視頻圖像分辨率為640×480。

圖8和圖9為二組不同圖像的匹配結果，每幅圖的上下半幅分別為使用SIFT和本文算法的匹配效果。表1、表2為圖8、圖9匹配結果統計。本文算法在二組圖像下的平均匹配正確率為97.4%，比SIFT算法高出11.2%；平均單個特征點匹配用時為1.63ms，為SIFT算法的38%左右。圖10為使用本文算法的AR虛實注冊效果。圖11統計了0～10s內使用Harris-SIFT[11]、SURF[12]和本文算法的AR系統輸出視頻幀速率。

圖8　第一組圖像匹配結果Fig.8　The matching results of first group images

算法SIFTFAST-SIFT匹配時間/ms704.671.2匹配點數16843誤配點數231正確率/%86.497.7

圖9　第二組圖像匹配結果Fig.9　The matching results of second group images

圖10　虛實注冊效果Fig.10　Virtual-real registration results

圖11　輸出視頻幀速率對比Fig.11　The rate comparison of video frame

4　結論

本文提出了多傳感器輔助的快速圖像匹配算法。該算法首先用FAST算法檢測兩幅圖像中的特征角點，然后利用SIFT算法為特征點生成主方向和描述符；其次，結合基于點積的相似度度量完成初匹配；其中，通過慣性傳感器數據預測攝像頭姿態和特征點在待匹配圖像中的位置，縮小匹配范圍，同時運用隨機K-D樹完成鄰近點搜索，提高運算效率；最后利用距離均值誤差統計法剔除誤匹配點得到最終同名點集。實驗表明，該圖像匹配算法在效率和精度方面均優于傳統的SIFT算法，能夠滿足增強現實系統對圖像匹配算法的精度高、速度快的要求?？偟膩碚f，該算法解決了現有的圖像匹配算法在AR系統中應用的三個問題[13-14]：1)計算量大不適用于實時運算；2)特征定位精度和匹配正確率不能滿足AR系統虛實注冊的要求；3)數據利用效率低，沒有針對具體AR應用特點對匹配算法進行優化。實驗證明，該算法是一種快速魯棒的圖像匹配方法，能夠很好地應用于AR系統。

[1]LoweDG.DistinctiveImageFeaturesfromScale-InvarientKeypoints[J].InternationalJournalofComputerVision，2004, 60(2):91-110.

[2]曾巒，王元欽，譚久彬.改進的SIFT特征提取和匹配算法[J].光學精密工程，2011,19(6):1391-1397.

[3]郭寶龍，孫偉.數字圖像處理系統工程導論[M]. 西安：西安電子科技大學出版社，2012:74-77.

[4]王崴，唐一平.一種改進的Harris角點提取算法[J].光學精密工程，2008，16(10):1995-2000.

[5]Smith S M，Brady J M. SUSAN a new approach to low level image processing [J].Journal of Computer Vision，1997，23(1):45-78.

[6] Rosten，Drummond T. Machine Learning for High-speed Corner Detection[C]// European Conference on Computer Vision，Graz，Austria，2006:430-443.

[7]丁南南，劉艷瀅.基于SURF-DA-ISY算法和隨機k-d樹的快速圖像配準[J].光電子.激光，2012，23(7):1395-1401.

[8]李薪宇，陳東義.基于混合跟蹤的增強現實系統設計與實現[J].計算機應用，2009,29(10):2853-2858.

[9]郭軍海.彈道測量數據融合技術[M].北京：國防工業出版社，2012:169-174.

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

[11]趙欽君，趙東標.Harris-SIFT算法及其在雙目立體視覺中的應用[J].電子科技大學學報，2010，39(4):546-550.

[12]BAY H，TUVTELLARS T，GOOL L Van. SURF:speeded up robust features[C]// Proceedings of the European Conference on Computer Vision，2006:404-417.

[13]許憲東，洪炳镕，關毅，等. 機器人視覺導航的幾種特征點方法比較[J].華中科技大學學報(自然科學版)，2011，39:200-203.

[14]賈平，徐寧，張葉.基于局部特征提取的目標自動識別[J]. 光學精密工程，2013，21(7):1898-1904.

Multi-sensor Aided Fast Image Matching Algorithm

LI Zihao1, LI Peilin1, WANG Wei1,2, QU Jue1, PENG Boyu1

(1. College of Air Defense and Anti-Missile, Air Force Engineering University, Xi’an 710051, China;2. State Key Laboratory for Manufacturing System Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Aiming at the problem that the existing image-matching algorithms can’t give consideration to both efficiency and precision, a multi-sensor aided and fast matching algorithm was proposed. Firstly, the feature points were detected by using robust FAST operator. Then, the main direction of feature point and the feature point descriptors were generated by using SIFT algorithm. Afterward, the preliminary matching was finished by using the similarity matric method based on the dot product, using position and attitude data of multi-sensor to narrow the range of search. Afterwards, the final matching points set was obtained by counting the distance error of feature points. Finally, the process of target tracking became more robust through template updating. Experimental results indicated that the accuracy and speed of this algorithm was superior to the traditional SIFT algorithm, which could satisfy the system requirements of higher precision and rapid speed.

FAST corner detection; SIFT feature; multi-sensor; error points eliminating; fast match

2016-02-18

國家自然科學基金項目資助(51405505)

李自豪(1992—)，男，土家族，湖南張家界人，碩士研究生，研究方向：增強現實，人機交互和誘導維修。E-mail:871805104@qq.com。

TP391

A

1008-1194(2016)04-0108-06