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

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

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

?

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

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

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

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

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

0　引言

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

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

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

1　算法基礎(chǔ)

1.1FAST角點檢測算法

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

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

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

(1)

定義了角點響應(yīng)函數(shù)后，就可以采用非極大值抑制方法對非角點進(jìn)行排除。

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

1.2特征點主方向的確定

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

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

1.3SIFT描述符的生成

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

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

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

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

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

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

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

(2)

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

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

(3)

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

(4)

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

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

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

2.2.1多傳感器硬件系統(tǒng)

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

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

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

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

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

2.2.2位姿估計和輔助策略

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

通過互補濾波器[9]的姿態(tài)輸出和對加速度計進(jìn)行積分得到兩幅幀圖像拍攝時攝像頭姿態(tài)和位置變換為ΔR和ΔT，空間中一點P在第k幀圖像(參考圖像)中的坐標(biāo)為pk(uk,vk)，第k幀和第k+1幀時刻點P在攝像頭坐標(biāo)系下的坐標(biāo)分別為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)得

根據(jù)慣性數(shù)據(jù)點P在待匹配圖像上的重投影的坐標(biāo)pk+1(uk+1,vk+1)并根據(jù)其劃定匹配搜索范圍。這里以pk+1為圓心，R為半徑劃定圓形匹配區(qū)域，R根據(jù)幀圖像時間間隔和攝像頭運動參數(shù)按式(9)自適應(yīng)選取：

(9)

根據(jù)攝像頭姿態(tài)預(yù)測特征點區(qū)域，在有效降低運算量的同時，合理降低了誤匹配點的出現(xiàn)概率，有效提升了算法的速度和精度。攝像機坐標(biāo)系，物體坐標(biāo)系和圖像坐標(biāo)系之間關(guān)系如圖7所示。

圖7　攝像機、物體坐標(biāo)系、圖像面坐標(biāo)系關(guān)系圖Fig.7　The relationship between coordinate system

2.3誤匹配點快速剔除

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

(10)

3　實驗分析

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

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

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

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

圖9　第二組圖像匹配結(jié)果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　結(jié)論

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

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

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

[3]郭寶龍，孫偉.數(shù)字圖像處理系統(tǒng)工程導(dǎo)論[M]. 西安：西安電子科技大學(xué)出版社，2012:74-77.

[4]王崴，唐一平.一種改進(jìn)的Harris角點提取算法[J].光學(xué)精密工程，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樹的快速圖像配準(zhǔn)[J].光電子.激光，2012，23(7):1395-1401.

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

[9]郭軍海.彈道測量數(shù)據(jù)融合技術(shù)[M].北京：國防工業(yè)出版社，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]趙欽君，趙東標(biāo).Harris-SIFT算法及其在雙目立體視覺中的應(yīng)用[J].電子科技大學(xué)學(xué)報，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]許憲東，洪炳镕，關(guān)毅，等. 機器人視覺導(dǎo)航的幾種特征點方法比較[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2011，39:200-203.

[14]賈平，徐寧，張葉.基于局部特征提取的目標(biāo)自動識別[J]. 光學(xué)精密工程，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

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

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

TP391

A

1008-1194(2016)04-0108-06