基于空間幾何結構的特征跟蹤算法

樊春玲 趙永剛 鄧 亮 馮良炳

(中國科學院深圳先進技術研究院 深圳 518055)

基于空間幾何結構的特征跟蹤算法

樊春玲 趙永剛 鄧 亮 馮良炳

(中國科學院深圳先進技術研究院 深圳 518055)

針對傳統的基于標記的增強現實系統場景受限等缺點,提出一種基于特征空間幾何結構的無標記跟蹤算法。在傳統的金字塔Kanade-Lucas-Tomasi(KLT)跟蹤算法基礎上,通過建立圖像的多尺度空間模型并在多尺度空間模型中對圖像進行實時跟蹤,同時根據圖像特征間特有的空間幾何結構信息優(yōu)選跟蹤特征點,解決了在多尺度變化情況下視頻圖像特征跟蹤穩(wěn)定性問題。實驗結果表明,提出的跟蹤算法在給定的數據庫上性能高效穩(wěn)定,與同類跟蹤算法相比跟蹤精度大幅提高,每幀重投影錯誤率均小于1像素,保持在亞像素級別。

空間幾何;自然特征;增強現實;跟蹤

1 引 言

增強現實技術(Augmented Reality)是在虛擬現實技術的基礎上發(fā)展起來的新技術,通過計算機系統將虛擬模型疊加到真實場景中,增強用戶感官體驗,從而實現對現實的增強。該技術已逐漸被應用到軍事、輔助醫(yī)療診斷與培訓、教育與娛樂等眾多領域。

目前很多增強現實系統是基于事先準備好的標記來獲取相機與物體的位置關系?；跇擞浀脑鰪姮F實系統中一個典型的代表就是華盛頓大學發(fā)布的軟件開發(fā)包ARToolKit[1],它使用事先準備好的矩形標記并將其特征存儲在數據庫中,當攝像機捕捉到包含標記的場景時檢測并識別標記,再根據已知的世界坐標和攝像機內參標定出得到攝像機的姿態(tài)。在這之后,各種不同類型的標記如Artag等[2,3]也被廣泛研究。然而這種基于標記的增強現實系統在實際應用中必須事先準備標記,并將標記存儲于數據庫中,因此其應用場景存在較大局限性。

近年來,隨著計算機視覺技術和計算機圖形學技術的迅速發(fā)展,無標記的自然物體跟蹤增強現實系統已成為發(fā)展趨勢。無標記增強現實系統可以通過對圖像進行自然特征提取并通過對運動過程中自然特征的跟蹤來掌握相機的姿態(tài),因此可以在任何場所和時間即時使用增強現實技術。要掌握好相機和物體位置關系,首要條件就是對圖像的自然特征進行檢測并在運動過程中準確地跟蹤特征。

學者們在自然特征檢測和跟蹤方面做了大量的研究也取得了一定的成效[4,5]。Lowe[6]提出的縮放不變特征轉換算子(Scale-Invariant Feature Transform,SIFT)是一種對圖像旋轉、縮放等保持不變性的圖像局部特征,但其計算太復雜,不能滿足增強現實系統的實時要求。Hernert等[7,8]在SIFT思想的基礎上提出了一種快速魯棒的角點特征,該特征基于積分圖像和盒子濾波的簡化實現,其運算速度比SIFT快得多。Rostenw等[9]提出了加速分割檢測特征角點,對于灰度圖像,檢測候選特征點周圍一圈的像素值,如果該點周圍鄰域內有足夠多的像素點與該點的灰度值差別足夠大,則認為該候選點為一個特征點。該方法簡單快速,能夠達到實時檢測要求,如并行跟蹤和定位[10,11],但是對旋轉和亮度變化敏感?；谔卣鞯母櫡椒ㄖ?主要有光流跟蹤Kanade-Lucas-Tomas(KLT)算法以及后來在其基礎上擴展的金字塔KLT[12]算法。傳統金字塔KLT方法中采用金字塔圖像利用較小的窗口跟蹤較大運動變化的特征,首先在金字塔最頂層(最模糊層)搜索特征點得到本層的光流,然后將其作為下一層(較清晰層)光流的初始估計值,再計算下一層的光流,直到最底層(最清晰層)。該方法對平移變化的圖像有良好的跟蹤效果,但在具有尺度變化的特征跟蹤效果需進一步改進。

本文在傳統金字塔KLT跟蹤算法基礎上,提出一種基于圖像自然特征空間幾何結構的多尺度跟蹤方法,對金字塔KLT方法的改進體現在:(1)在圖像的多尺度空間模型上同時進行特征點跟蹤和融合;(2)利用特征點的空間幾何結構信息進行優(yōu)化?；谶@兩點改進,解決多尺度變化對象的跟蹤穩(wěn)定性問題。

2 算法描述

本文提出的基于圖像自然特征空間幾何結構的無標記跟蹤方法,算法流程如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flow chart

首先對視頻第一幀圖像角點特征進行檢測;接著分別為后續(xù)每幀圖像建立一個多尺度空間模型,并在圖像多尺度空間模型中的每一層圖像上跟蹤第一幀檢測到的特征點,然后將每層跟蹤到的特征點融合并剔除異常點,即可得到每幀圖像的跟蹤點;再通過隨機抽樣一致性算法(Random Sample Consensus,RANSAC)對每幀跟蹤特征點所在平面與第一幀圖像所在平面求取單應性矩陣,根據單應性矩陣將第一幀檢測到的特征點映射到每幀圖像上得到映射點;最后根據每幀圖像上的映射點和跟蹤點的空間幾何特征篩選特征點。

2.1 特征提取

與金字塔KLT算法相同,本文也采用Shi-Tomasi[14]角點進行特征檢測和跟蹤。Shi-Tomasi角點在傳統Harris角點的基礎上進行改進,其定義的基礎為圖像灰度強度的二階導數矩陣——二維的Hessian矩陣:

根據Shi-Tomasi定義,若矩陣H的兩個特征值中較小的一個大于設定的閾值,則認為該點是較強的特征點。

2.2 特征跟蹤

(1)建立多尺度空間模型

由于傳統的金字塔KLT算法對多尺度變化的視頻跟蹤效果不穩(wěn)定,因此本文算法首先為需跟蹤的每幀圖像建立多尺度空間模型,然后在每層圖像上對特征進行跟蹤,能夠實現對多尺度變化的視頻穩(wěn)定跟蹤。采用帶有低通濾波的下采樣方法對每幀圖像建立具備不同分辨率的圖像多尺度空間模型。自上向下,將原圖像按照不同的尺度系數縮放為不同大小的圖像,多尺度空間模型的層數可根據視頻內容目標變化程度設定。

(2)多尺度空間搜索

對首幀圖像中檢測到的特征點,在圖像的每層空間圖像上采用金字塔KLT跟蹤方法進行特征點跟蹤。使用金字塔KLT方法時,假設有一個包含特征信息的窗口w,所有像素點(x,y)都向一個方向移動了(vx,vy),從而得到( ),即t時刻的(x,y)點在t+τ時刻為(x+vx,y+vy),所以尋求匹配的問題可化為最小化式(2),式中,wx和wy分別為窗口在x和y方向上的半徑。對于灰度圖,A(x,y)為t時刻的圖像中點(x,y)處的亮度值,B(x+vx,y+vy)為t+τ時刻的圖像中點(x+vx,y+vy)的亮度值。

對首幀圖像的特征點序列在后續(xù)幀的每個尺度空間圖像進行搜索。本文采用5層的尺度模型空間,最后得到5組新的特征點序列,稱為不同尺度空間的特征點序列。

在圖像多尺度空間模型中每層圖像上跟蹤特征點的結果不盡相同。在一些層上部分特征點會丟失,并且每幀的丟失情況各異,因此在多尺度空間模型中對每層圖像搜索可以彌補由于尺度變化等造成的特征點丟失。

(3)多尺度特征點融合

每層上的特征點序列僅代表該層尺度空間的跟蹤效果,要得到每幀的特征點序列,需要將不同尺度的特征點序列根據其空間幾何結構一一對應來進行融合。本文逐點對比每層空間特征點跟蹤結果,對比其在每層的跟蹤誤差值,選取三層空間中跟蹤誤差最小的點作為該幀最終的跟蹤點,其坐標根據式(3)計算得出:

其中,vi為i點的最終跟蹤坐標;分別表示在第vi第l層上跟蹤到的點的x和y方向坐標;scalel是第l層的尺度系數。圖2給出了三層空間模型的示意圖。第一層中跟蹤到的特征點為(1,3,4,6,8),第二層中跟蹤到的特征點為(1, 2,3,4,6,7,8),第三層中跟蹤到的特征點為(1,2, 3,5,7,8)。融合過程具體為對比跟蹤到的特征點的誤差值,將誤差較小的作為最終跟蹤到的點,最終得到本幀的跟蹤點為(1,2,3,4,5,6,7,8)。對于三層中均未跟蹤到的少數點認為其丟失。

圖2 多尺度空間特征點融合Fig.2 Feature points blending in multi-scale model

(4)剔除異常點

同所有測量數據一樣,跟蹤也會因計算及其他原因造成誤差。本文對每幀跟蹤特征點序列中誤差較大的點進行剔除操作,通過設置合適的“置信域”,位于“置信域”范圍外的點認為是異常點,如圖3中(a)為前一幀跟蹤到的特征點,(n)為后一幀跟蹤到的特征點。其中,虛線圈代表按照其他跟蹤點變化規(guī)律在本幀應該出現的位置,紅色點為與其他點變化相比變化異常的特征點。異常值判斷的準則中最常用的誤差處理方法是準則,表達式見式(4):

其中,xd為映射點和對應跟蹤點的歐氏距離;為所有點對應距離的平均值;為標準方差。

先計算首幀跟蹤特征點序列和每幀跟蹤點序列的變化情況,即距離,其中m為跟蹤到的點個數,再根據 準則結合測量數據點較少的實際情況,將“置信域”設置為,位于“置信域”之外點將被剔除。

圖3 相鄰幀跟蹤示意圖Fig.3 Tracking results in sequence

2.3 優(yōu)化特征點

(1)求取單應性矩陣

在計算機視覺中,平面的單應性是從一個平面到另一個平面的投影映射。本文利用RANSAC方法從第一幀檢測的特征點和后續(xù)每幀跟蹤到的特征點中分別選擇四對以上特征點,求取第一幀圖像所在平面和后續(xù)每一幀圖像所在平面的單應性矩陣H,見式(5):

其中,u為首幀檢測到的特征點;v為后續(xù)某一幀跟蹤到的特征點。特征點坐標均采用齊次坐標形式。

(2)映射特征點

通過單應變換將首幀特征點序列映射到當前幀圖像中得到映射點序列,這些映射點序列將作為候選特征點。

(3)優(yōu)化特征點

在跟蹤過程中,由于目標位置變化劇烈等原因導致跟蹤失敗的情況有兩種:一種是跟蹤點丟失,另一種是跟蹤點位置錯誤。針對這兩種情況,本文算法提出了相應的處理措施:①對于跟蹤中丟失的特征點,根據當前幀上其余跟蹤良好的點得到該幀所在平面與首幀所在平面的單應變換關系,再由此單應變換關系將第一幀中與此點對應的特征點映射到當前幀上,得到一個新的特征點。對這個新的特征點根據式(1)求取H矩陣,判斷其較小的特征向量是否大于設定閾值,如果大于閾值則將該點加入特征點序列。②根據與映射點之間的歐式距離剔除跟蹤錯誤的特征點。跟蹤點如果與其相應映射點的距離較大(大于設置的閾值),則認為該點是異常點,應在每幀特征點序列中剔除掉該點。最終,通過上述步驟得到每幀圖像中跟蹤到的首幀特征點序列的跟蹤點序列。

3 實驗及結果分析

本方案已在處理器為AMD AthlonTMII X2 B24 2.99 GHz,操作系統為Microsoft Windows XP的計算機上實現,為檢測算法的跟蹤效果,采用Metaio標準庫[15]測試本文提出的算法在不同尺度變化情況下跟蹤的準確度,結果見圖4。其中,圖4(a)為對“CAR”圖像縮放至0.25倍跟蹤效果對比,圖4(n)為縮放至0.4倍跟蹤效果對比,且在圖4(a)和(n)中,左圖均為采用金字塔KLT方法跟蹤效果,右圖均為采用本文算法跟蹤效果。從圖4可看出,在不同的尺度上跟蹤中,本文算法跟蹤到的特征點數目以及準確性明顯優(yōu)于傳統金字塔KLT算法。

圖4 本文方法和金字塔KLT方法跟蹤不同尺度變化的圖像對比圖Fig.4 Tracking result for using proposed method and KLT

圖5 顯示Metaio標準庫中“STOP”組圖的跟蹤效果,圖中綠色線條表示跟蹤成功的特征。圖5(a)為對原始圖像縮小至0.25倍跟蹤效果,圖 5(n)為將原始圖像順時針旋轉 30°跟蹤效果,圖5(c)為將原始圖像順時針旋轉60°跟蹤效果。從圖5中可看出,本文算法不但對多尺度變換跟蹤穩(wěn)定,并且對旋轉保持穩(wěn)定性。

圖6與圖7分別顯示采用金字塔KLT、帶方向性的加速分割檢測特征和旋轉不變的二進制魯棒獨立基本特征(Oriented FAST and Rotated BRIEF,ORB)[16]以及本文算法對兩段視頻(分別為300幀和600幀,分辨率均為1280×720像素)做跟蹤的每幀重投影錯誤率。結合圖6和圖7可看出,本文算法每幀重投影錯誤率均小于1像素,而金字塔KLT算法和ORB算法重投影錯誤率相對較大而且在對部分幀的跟蹤中出現較大波動,并且由于本文算法中對跟蹤的特征點進行了基于空間幾何特征信息的優(yōu)化,包括跟蹤錯誤點的剔除和跟蹤丟失點的找回,重投影錯誤率沒有出現較大波動的情況,因此跟蹤性能穩(wěn)定。實驗表明,本文算法與金字塔KLT、ORB算法相比,對于多尺度變化的對象跟蹤準確性和穩(wěn)定性均有大幅提高。

圖5 本文方法對Metaio數據庫“STOP”圖跟蹤效果Fig.5 Feature points tracked results from Metaio“STOP”

圖6 金字塔KLT、ORB與本文算法跟蹤結果(視頻1)Fig.6 Results of tracking via Pyramidal KLT,ORB and our method(video 1)

圖7 傳統金字塔KLT、ORB與本文算法跟蹤結果(視頻2)Fig.7 Results of tracking via Pyramidal KLT,ORB and our method(video 2)

4 結束語

本文提出一種可用于無標記增強現實系統的跟蹤算法。通過對真實場景中目標圖像的自然特征進行檢測,建立圖像的多尺度模型并在模型中的每層圖像上跟蹤特征點;同時,根據特征點的空間幾何結構對多尺度特征點進行融合;最后通過RANSAC方法求取單應性矩陣并映射特征點,對比映射點和跟蹤點之間的空間幾何關系優(yōu)化跟蹤點。實驗結果表明,本文算法應用于無標記增強現實系統中時,在圖像的多尺度空間模型中進行特征點搜索方法更適用于具有多尺度變化的視頻跟蹤,并能得到實時準確的跟蹤效果。

[1] Kato H,Billinghurst M.Marker tracking and HMD calinration for a video-nased augmented reality conferencing system[C]//Proceedings of the 2nd IEEE and ACM International Workshop on Augmented Reality,1999:85-94.

[2] Bergamasco F,Alnarelli A,Rodola E,et al.RUNETag:a high accuracy fiducial marker with strong occlusion resilience[C]//IEEE Conference on Computer Vision and Pattern Recognition,2011: 113-120.

[3] Uchiyama H,Saito H.Random dot markers[C]// IEEE Virtual Reality Conference,2011:35-38.

[4] Uchiyama H,Marchand E.Onject detection and pose tracking for augmented reality:Recent approaches[C]//The 18th Korea-Japan Joint Workshop on Frontiers of Computer Vision,2012.

[5] Van Krevelen DWF,Poelman R.A survey of augmented reality technologies,applications and limitations[J].International Journal of Virtual Reality,2010,9(2):1-20.

[6] Lowe DG.Distinctive image features from scaleinvariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[7] Bay H,Tuytelaars T,Gool LV.SURF:speeded up ronust features[C]//Proceedings of the 9th European Conference on Computer Vision,Lecture Notes in Computer Science,2006,3951:404-417.

[8] 張志禹,劉耀陽.基于SURF與光流法的增強現實跟蹤注冊[J].計算機工程與應用,2013,doi: 10.3778/j.issn.1002-8331.1303-0339.

[9] Rosten E,Drummond T.Machine learning for highspeed corner detection[C]//Proceedings of the 9th European Conference on Computer Vision,Lecture Notes in Computer Science,2006,3951:430-443.

[10]Klein G,Murray D.Parallel tracking and mapping for small AR workspaces[C]//The 6th IEEE and ACM International Symposium on Mixed and Augmented Reality,2007:225-234.

[11]Klein G,Murray D.Parallel tracking and mapping on a camera phone[C]//The 8th IEEE International Symposium on Mixed and Augmented Reality,2009:83-86.

[12]Bouguet JY.Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm[OL].[2014-07-03].http://ronots. stanford.edu/cs223n04/algo_affine_tracking.pdf.

[13]Fischler MA,Bolles RC.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.

[14]Shi J,Tomasi C.Good features to track[C]// Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,1994: 593-600.

[15]Runlee E,Ranaud V,Konolige K,et al.ORB:an efficient alternative to SIFT or SURF[C]//IEEE International Conference on Computer Vision, 2011:2564-2571.

[16]Academic Research and Punlications[OL].[2014-07-03].http://www.metaio.com/research/.

Feature Tracking Based on Space Geometry Structure

FAN Chunling ZHAO Yonggang DENG Liang FENG Liangning
(Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen518055,China)

In this paper, a novel method for tracking without a marker was proposed. This method alleviated many constraints in augmented reality systems nased on fiducial markers. To improve the tracking stanility in multi-scale, the effective features and space geometry structure were detected, and the effective features were searched in a multi-scale model. Based on space geometry structure of features, the effective feature points were selected and fictitious features points were wiped off. Experiments show that the proposed algorithm works ronustly in the video with scaling onjects. The feature points reprojection error of every frame is smaller than one pixel, and the average of feature points reprojection error is kept in sun-pixel.

space geometry； natural feature； augmented reality； tracking

TP 391.41

A

2013-12-30

:2014-07-04

國家自然科學基金項目(61070147);深圳市科技研發(fā)資金基礎研究計劃(JC201105190951A,JC201005270331A)

樊春玲,碩士,研究方向為圖像處理、增強現實等;趙永剛,碩士,研究方向為增強現實,圖像處理等;鄧亮,碩士,研究方向為模式識別、視頻監(jiān)控等;馮良炳(通訊作者),博士,研究方向為智能計算與智能控制、多視角三維重建及增強現實等,E-mail:ln.feng@siat.ac.cn。