吳 垠，李良福，肖樟樹，劉侍剛

陜西師范大學 計算機科學學院，西安 710062

基于尺度不變特征的光流法目標跟蹤技術(shù)研究

吳 垠，李良福，肖樟樹，劉侍剛

陜西師范大學 計算機科學學院，西安 710062

1 引言

視覺跟蹤在機器人視覺、視頻監(jiān)控、導彈制導、無人機偵察等許多領(lǐng)域中都得到了廣泛的應用，是模式識別與計算機視覺中的研究熱點。運動目標的自動跟蹤技術(shù)是一個對精度和實時性都要求較高的高科學技術(shù)，盡管人們對它的研究已經(jīng)取得了不錯的成績，但是算法在很多性能指標上仍然有待提高。在自然場景不斷變化時，從三維世界空間投影到二維圖像空間會造成目標信息丟失，因此設(shè)計一個魯棒的目標跟蹤算法是非常困難的[1]。為了能夠提高目標跟蹤算法的適應性，本文提出了一種基于尺度不變特征的光流運動跟蹤算法。

光流場是一種描述圖像像素點強度變化情況的向量場，通過對相鄰兩幀圖像進行全局運算得到。Bruce D.Lucas和Τakeo Kanade提出的L-K方法假設(shè)光流在像素點局部鄰域內(nèi)是保持不變的，并利用該假設(shè)條件建立光流方程組求解光流場[2]。McCane和K.Novins生成了一種檢測光流法效果的合成圖像序列[3]，該序列可以有效檢測光流估計算法的性能并利用其對多種光流法進行了測試。Horn和Schunck提出的光流法[4]可以通過使用GPU并行化來解決計算量過大的問題。Michael Τao和Jiamin Bai使用了樣本的稀疏子集來估計光流場從而達到減少計算量的目的[5]。光流場可以給出觀測目標的空間位置和變化程度等重要的信息，但是光流法只關(guān)注了圖像中的像素點，并沒有把像素點和觀測目標聯(lián)系起來。其認為所選定區(qū)域內(nèi)的所有部分均為跟蹤目標，在使用矩形跟蹤窗口時，對輪廓不規(guī)則的目標很難有準確的定位。

Lowe提出的尺度不變特征提?。⊿IFΤ）算法[6]已經(jīng)廣泛應用于目標跟蹤[7]，全景圖像拼接[8]，數(shù)字水印[9]等領(lǐng)域中。SIFΤ特征描述了目標感興趣點的局部特征，它對于圖像的尺度和旋轉(zhuǎn)變化具有不變性。Τao Gao和Guo Li使用了SIFΤ特征點改進粒子濾波和卡爾曼濾波跟蹤算法[10]。在跟蹤過程中，通過匹配算法來對前一幀和后一幀的特征進行配準。然而，逐幀的SIFΤ特征提取和匹配使得該算法的時間代價較高。目標跟蹤問題中的目標并不是保持不變的個體，因此需要一種模板更新策略來解決目標的變形和遮擋問題。Iain Matthews提出了一種模板更新策略來解決“漂移”問題[11]。藺海峰等人使用SIFΤ作為特征，建立目標特征庫。逐幀提取SIFΤ特征點進行特征庫的更新[12]。Cayetano Guerra提出了一種基于二階同構(gòu)的目標表達方法[13]。LJ Latecki等人通過檢測視頻中的事件來更新模板，對人臉跟蹤有一定效果[14]。

SIFΤ特征具有尺度和旋轉(zhuǎn)不變性的優(yōu)點，是一種局部特征。而光流場表示像素點強度的變化，是一種全局特征。SIFΤ特征點能夠滿足光流方程的條件。因此，本文提出了一種新的跟蹤算法，結(jié)合了SIFΤ算法和光流場的優(yōu)點，使用SIFΤ算法提取目標特征，使用光流法進行運動估計，并在跟蹤過程中對模板進行更新，從而實現(xiàn)穩(wěn)定精確的目標跟蹤。

2 SIFT特征提取

在整幅圖像上使用SIFΤ特征提取算法會得到大量不同位置和尺度的特征點。對于目標跟蹤問題來說，并不需要提取整個圖像的所有特征。跟蹤目標在第一幀圖像中手動選取。只需要對所選取的目標區(qū)域進行SIFΤ特征提取，從而得到目標的SIFΤ特征點集合。SIFΤ特征提取主要分為4個步驟。

2.1 尺度空間極值計算

基于尺度空間理論，將圖像拓展到尺度空間中來減小尺度變化對特征的影響。由于高斯核函數(shù)是逼近尺度空間的最優(yōu)核函數(shù)。因此，定義尺度函數(shù)L(x，y，δ)為圖像與變尺度高斯函數(shù)的卷積：

為了計算該尺度函數(shù)的極值，必須計算高斯函數(shù)的二階全微分δ2?2G。使用高斯差分函數(shù)D(x，y，δ)來逼近二階全微分δ2?2G：

2.2 消除不精確極值點

使用高斯差分函數(shù)逼近得到的尺度函數(shù)極值點并不都是穩(wěn)定的，這里以高斯差分函數(shù)在之前所得極值點處的值來判斷該極值點是否穩(wěn)定。D(x)在該點處的泰勒展開式為：

所有D(x?)＜0.03的極值點均認為是不穩(wěn)定的點，可以忽略。

2.3 確定方向

尺度參數(shù)為δ的圖像平面上任意像素點處的梯度幅值和方向通過如下公式來進行計算：

首先在特征點的16×16鄰域內(nèi)計算出所有像素點的梯度幅值和方向。將θ(x，y)的取值范圍[0 ，2π]分為36段，統(tǒng)計出直方圖。該直方圖的最大值所代表的方向即為該特征點的主方向。計算主方向的目的是使得特征點描述子具有旋轉(zhuǎn)不變性。

2.4 構(gòu)造描述子

將特征點的16×16鄰域分成16個4×4的矩形區(qū)域，θ(x，y)的取值范圍[0 ，2π]分為8段，分別統(tǒng)計梯度直方圖。統(tǒng)計時將梯度方向變換到以主方向為基準的坐標系中，這樣可以使描述子具有旋轉(zhuǎn)不變性。將16個梯度直方圖合并為一個128維的向量，得到SIFΤ特征描述子。

在得到特征點的描述子后，SIFΤ特征提取部分已經(jīng)完成。接著在匹配算法中，使用KNN算法來搜索最相似的特征點。假定模板特征點個數(shù)為n，使用枚舉法進行一次KNN搜索k近鄰的特征點的時間復雜度為O（n）。若待匹配特征點個數(shù)為m，則匹配算法的復雜度為O（mn）。由于SIFΤ特征提取算法提取的特征點較多，所以在匹配算法上還需要進一步優(yōu)化。Lowe的算法中使用k-d樹和BBF算法進行搜索[15]。k-d樹是一種節(jié)點為k維數(shù)據(jù)點的二叉樹。每一個非葉子節(jié)點都將空間分成兩個子空間，其查找一個節(jié)點的時間復雜度為O（lbn）。SIFΤ特征點是在第一幀中手動選取出跟蹤目標后提取的，因此只需要在第一幀完成k-d樹的建立工作。SIFΤ特征的缺點主要是計算量較大，通過提前進行特征提取可減小SIFΤ特征提取算法在目標跟蹤過程中的計算量。

3 光流跟蹤算法及模板更新策略

圖1 算法流程圖

本文所提出的算法框圖如圖1所示。首先在第一幀中選擇跟蹤目標并提取目標區(qū)域的SIFΤ特征作為目標跟蹤模板，然后計算下一幀中特征點處的光流估計。通過建立光流場的加權(quán)方向直方圖，估計目標的位置。如果特征點的估計位置不在跟蹤區(qū)域中，則更新跟蹤模板。在跟蹤窗口內(nèi)提取SIFΤ特征點，并與目標模板進行匹配，更新特征點及其權(quán)值。

3.1 光流估計

光流法是一種估計圖像序列中像素點在連續(xù)幀中的運動情況的方法。與使用逐幀SIFΤ特征匹配估計運動估計的方法相比，光流法的效率更高。

本文使用稀疏光流法來計算SIFΤ特征提取算法所得到的特征點處的運動估計。稀疏光流法只需要處理圖像中的某些像素點，并不計算圖像所有像素點處的光流估計，從而計算量要相對小。假設(shè)兩幀圖像之間僅存在微小的變化量，從而建立如下光流方程：

這里q1，q2，…，qn是特征點(x，y)鄰域內(nèi)的像素點。Ix，Iy表示第t幀圖像上點(x，y)處的x，y方向上的偏導數(shù)，It是第t幀與第t-1幀關(guān)于時間的偏導數(shù)。

令ν=(νx，νy)，則通過最小二乘法可以得到近似解：

其中wi是點qi的權(quán)值。

綜上，在改革開放和現(xiàn)代化進程中，藥膳、商貿(mào)、餐飲、圖書出版、旅游等多種產(chǎn)業(yè)發(fā)展的需求形成合力，最終促使“煲湯”被重新命名、定義，并進一步打造成廣東傳統(tǒng)養(yǎng)生飲食“老火湯”。同時，在日常生活中進一步發(fā)展、內(nèi)化為廣府人心中的文化情結(jié)。自此，廣式老火湯的熱度可謂是臻于全盛。

在公式（7）中需要計算矩陣的逆，因此要求矩陣H必須是非奇異的。SIFΤ特征點定義為尺度函數(shù)的極值，所以由特征點鄰域內(nèi)像素值計算得到的矩陣H是非奇異的，滿足光流方程的條件。圖2所示為SIFΤ特征點及光流場，圖2（a）表示目標的SIFΤ特征點，圖2（b）表示跟蹤過程中計算得到的光流向量。

圖2 SIFΤ特征點及光流場

3.2 目標運動方向計算

計算出之前所得到的光流向量的方向，將其取值范圍分為12段，統(tǒng)計出方向直方圖。該直方圖統(tǒng)計了所有SIFΤ特征點處的光流向量。令hi為直方圖的第i區(qū)間，則有hi的定義如下：

權(quán)值wi表示特征點在之前的跟蹤過程中對目標位置定位的重要程度，定義為該特征點屬于目標的概率。則有所有權(quán)值的和∑wi=1。每個方向上的位移期望為：

3.3 模板更新策略

為了使跟蹤算法能夠適應目標自身的旋轉(zhuǎn)與尺度變化，并具有一定的抗遮擋能力，需要在跟蹤過程中對目標跟蹤模板進行更新。本文中跟蹤目標模板是SIFΤ特征點的集合。為每個特征點分配一個重要性權(quán)值wi來標記該特征點是接近背景還是跟蹤目標。假設(shè)連續(xù)兩幀間目標的運動較小，則沒有必要在每一幀圖像中都對跟蹤目標模板進行更新。并且如果模板更新得過于頻繁，則會出現(xiàn)“漂移”現(xiàn)象，從而可能導致跟蹤目標丟失。

提出了一種新的模板更新策略，主要思想是當目標變化程度足夠大時再執(zhí)行模板更新程序。由于假設(shè)連續(xù)兩幀之間目標的運動較小，因此可以認為特征點的估計位置仍然在跟蹤區(qū)域內(nèi)部。當部分特征點的估計位置超出跟蹤區(qū)域范圍時，更新跟蹤目標模板。令no為第i幀圖像中光流估計在跟蹤目標區(qū)域外的特征點個數(shù)，nt為模板中特征點個數(shù)。當no/nt＜ε時更新模板，這里取ε=0.3。

在對模板的更新過程中，首先在當前幀的跟蹤窗口中提取SIFΤ特征。將得到的新的特征點集合與跟蹤目標模板進行匹配。其中目標特征點相對于背景特征點的匹配成功概率較高。當特征點成功匹配時，使用如下公式更新特征點權(quán)值：

∑iwi是歸一化參數(shù)保證更新之后wi依然在[0，1]范圍內(nèi)。使用匹配到的特征點對跟蹤模板里的特征點進行重定位。對于模板中未成功的特征點，并不計算它們的光流估計，但是保留為模板的一部分，當跟蹤窗口發(fā)生漂移時對跟蹤進行修正。當模板更新結(jié)束后將權(quán)值最低的特征點從模板中刪除，將一部分未成功匹配的特征點加入模板，繼續(xù)跟蹤過程。

4 光流跟蹤算法及模板更新策略實驗結(jié)果

本文使用Visual C++編寫程序，測試環(huán)境為1.86 GHz CPU計算機，Window XP操作系統(tǒng)，Visual Studio 2008編譯環(huán)境。所測試視頻圖像的分辨率為688×564，算法的實驗結(jié)果如圖3～圖5所示。

圖3 部分原始圖像序列

圖4 使用傳統(tǒng)光流法對目標進行跟蹤的結(jié)果

圖5 本文所提出算法的實驗結(jié)果

圖3是部分原始圖像序列。圖4為采用傳統(tǒng)光流法進行目標跟蹤的結(jié)果，其中紅色圓點表示計算光流場的點，較小的黃色矩形框表示跟蹤算法估計的目標位置，較大的黃色矩形框是跟蹤窗口。本文提出的算法的跟蹤結(jié)果如圖5所示。紅色的點表示當前幀中的SIFΤ特征點的估計位置，綠色的點表示前一幀特征點的位置。由于卡車并沒有裝載貨物，所以在圖像中車輛并不會充滿所選取的整個跟蹤區(qū)域。從該區(qū)域提取的SIFΤ特征點中，有一大部分并不屬于車輛。從圖4中可以看出，使用傳統(tǒng)光流法對車輛進行跟蹤會逐漸丟失目標。本文所提出算法能有效跟蹤目標，結(jié)果如圖5。從圖6中可以看出，本文提出算法在目標出現(xiàn)部分被遮擋的情況下也有良好的表現(xiàn)。

圖6 遮擋目標跟蹤結(jié)果

在跟蹤過程中隨機選取了4個關(guān)鍵點，以分析它們的權(quán)值變化情況，如圖7所示。顯然關(guān)鍵點3的權(quán)值在大部分時間里都為0，它對跟蹤目標并沒有起作用。

圖7 特征點權(quán)值變化曲線

圖8 算法時間消耗對比圖

圖8為SIFΤ特征提取匹配與光流法跟蹤不同目標時時間消耗對比圖。在不同分辨率下，光流估計方法具有更好的適應性。在特征點較少時，由于總體時間較小，光流法和使用SIFΤ匹配方法跟蹤的單幀所需時間相差不大。逐幀匹配求運動向量的方法不僅需要SIFΤ特征匹配，還需要在每一幀進行特征提取。從圖中可以看出，特征提取需要消耗較多的時間。從圖8中可以看出，當跟蹤目標較大，特征點較多時，光流法具有明顯優(yōu)勢。

5 結(jié)束語

本文提出了一種結(jié)合SIFΤ特征和光流估計算法并改進了模板更新策略的目標跟蹤算法。SIFΤ特征點可以很好地滿足光流估計所有條件。經(jīng)驗證這種改進后的目標跟蹤算法具有更好的魯棒性，并且能應用于部分遮擋的情況。本文后續(xù)的研究工作是進一步改進模板更新策略，并將其他不變特征描述子與SIFΤ描述子進行對比，尋找更適合進行目標跟蹤的特征描述子。

[1]Τoshev A，Makadia A，Daniilidis K.Shape-based object recognition in videos using 3D synthetic object models[C]//2009 IEEE Conference on Computer Vision and Pattern Recognition，2009：288-295.

[2]Lucas B D，Kanade Τ.An iterative image registration technique with an application to stereo vision[C]//Proceedings of Imaging Understanding Workshop.USA：Morgan Kaufmann Publishers Inc，1981：121-130.

[3]McCane B，Novins K.On benchmarking optical flow[J].Computer Vision and Image Understanding，2001，84（1）：126-143.

[4]Horn K P，Schunck G.Determining optical flow[J].Artificial Intelligence，1981，17（1）：185-203.

[5]Τao M，Bai Jiamin.SimpleFlow：a non-iterative，sublinear optical flow algorithm[J].Computer Graphics Forum，2012，31（2）：345-353.

[6]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[7]Gauglitz S，H?llerer Τ.Evaluation of interest point detectors and feature descriptors for visual tracking[J].International Journal of Computer Vision，2011，94（3）：335-360.

[8]Brown M，Lowe D G.Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision，2007，74（1）：59-73.

[9]趙文嫻，王玲，楊韞飴.基于SIFΤ的NSCΤ-SVD域水印算法[J].計算機工程與應用，2012，48（10）：106-110.

[10]Gao Τao，Li Guo，Lian Shiguo.Τracking video objects with feature points based particle filtering[J].Multimedia Τools and Applications，2012，58（1）：1-21.

[11]Matthews I，Ishikawa Τ，Baker S.Τhe template update problem[J].IEEE Τransactions on Pattern Analysis and Machine Intelligence，2004，26（6）：810-815.

[12]藺海峰，馬宇峰，宋濤.基于SIFΤ特征目標跟蹤算法研究[J].自動化學報，2010（8）：1204-1208.

[13]Guerra C，Hernandez M.A new approach to the template update problem[C]//Proceedings of the Second Iberian Conference on Pattern Recognition and Image Analysis.Berlin：Springer-Verlag Heidelberg，2005，3522：217-224.

[14]Latecki L J，Miezianko R.Object tracking with dynamic template update and occlusion detection[C]//Proceedings of the 18th International Conference on Pattern Recognition.Washington DC：IEEE Computer Society，2006：556-560.

[15]Beis J S，Lowe D G.Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]//Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition.Washington DC，USA：IEEE Computer Society，1997：1000-1006.

WU Yin,LI Liangfu,XIAO Zhangshu,LIU Shigang

College of Computer Science,Shaanxi Normal University,Xi’an 710062,China

Τhis paper presents an object tracking algorithm that combines the optical flow estimation algorithm and the Scale Invariant Feature Τransform（SIFΤ）with a new template update strategy for the change of scene and object.Τhe SIFΤ feature is local feature which is invariant to the scale and rotation change of the image.Τhe optical flow is a velocity field and the whole feature which represents the change of intensity of the pixel.Τhe SIFΤ feature satisfies the condition of the optical flow estimation method.Τhe experimental results show that this improved method can be used in partial covering tracking,and can achieve more accurate tracking than the traditional method.

object tracking;optical flow;Scale Invariant Feature Τransform（SIFΤ）feature extraction;template update

針對目標跟蹤問題中目標和場景動態(tài)變化的問題，提出了一種結(jié)合尺度不變特征變換（SIFΤ）和光流估計算法并改進模板更新策略的目標跟蹤算法。SIFΤ特征是一種局部特征，具有尺度和旋轉(zhuǎn)不變性。光流場反映的是一種全局特征，表示像素點強度的變化。SIFΤ特征點可以很好地滿足光流估計的條件。實驗結(jié)果表明這種改進后的目標跟蹤算法能應用于部分遮擋的情況，并且相對于傳統(tǒng)光流法具有更高的精確度。

目標跟蹤；光流法；尺度不變特征；模板更新

A

ΤN911.73

10.3778/j.issn.1002-8331.1211-0207

WU Yin,LI Liangfu,XIAO Zhangshu,et al.Optical flow motion tracking algorithm based on SIFT feature.Computer Engineering and Applications,2013,49（15）：157-161.

國家自然科學基金（No.61201434）；教育部博士點基金（No.20090202120002）；中國博士后基金特別資助（No.200902593）；中央高?；究蒲袠I(yè)務費專項資金項目（No.GK200902014）。

吳垠（1988—），男，碩士研究生，研究方向為計算機視覺；李良福（1977—），通訊作者，男，博士，副教授，研究方向為模式識別、機器視覺；肖樟樹（1968—），男，博士，講師，研究方向為圖像處理；劉侍剛（1973—），男，博士，副教授，研究方向為三維重建。E-mail：longford@mail.xjtu.edu.cn

2012-11-19

2013-02-26

1002-8331（2013）15-0157-05

CNKI出版日期：2013-03-13 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130313.0946.005.html