仇大偉，劉靜

(山東中醫(yī)藥大學理工學院，山東濟南250355)

目標跟蹤是計算機視覺領域中的一個重要問題，在視頻會議、目標監(jiān)控和人機交互中有著廣泛應用。目標跟蹤的主要目的是在動態(tài)變化的場景下連續(xù)、可靠地獲取目標的準確位置［1］，多年來，研究者們對此進行了大量研究，提出了一些目標跟蹤算法。概括起來，目標跟蹤算法可以分為以下四種類型［2］:基于梯度的方法通過最小化代價函數定位后續(xù)幀中的目標;基于知識的方法使用形狀、輪廓等先驗知識跟蹤目標;基于學習的方法借助模式識別算法首先學習目標模型，然后在后續(xù)幀中搜索目標;基于特征的方法使用提取的諸如亮度、顏色和邊緣等特征跟蹤目標。

主動輪廓模型［3］自1988年提出后，一直是圖像分割領域的研究熱點，但是輪廓的初始化、運算速度等問題使其很難應用于目標跟蹤的研究中?；趯W習的方法［2，4－6］主要使用神經網絡、徑向基函數網絡和支持向量機等方法進行目標跟蹤。該方法允許進行復雜的、非線性目標建模，且可以動態(tài)地進行模型更新。然而，基于學習的方法一般用于特定的目標跟蹤，且需要離線學習大量樣本，通用性較差。近年來，基于特征的目標跟蹤方法引起了研究者的廣泛關注。均值偏移跟蹤［7］(mean shift tracking，MST)及其改進算法主要利用顏色直方圖表示目標，自提出以來得到了廣泛應用。然而，該類算法假定目標的直方圖在跟蹤過程中不會發(fā)生較大改變，實際上，由于光照強度、觀測角度、目標遠近以及遮擋等情況的變化，目標在運動過程中常常會發(fā)生較大改變。針對不斷變化的目標外形，Nejhum等［8］提出一種使用直方圖跟蹤目標的算法，該算法利用目標窗口中的若干小的矩形框表示目標，小矩形框的位置在算法運行過程中自適應地確定，該算法能夠跟蹤在運動過程中外形有較大變化的目標。然而，該算法每次都需掃描整個圖像以確定目標的大體位置，表示目標的小矩形框的調整和再定位、目標模型的更新等方面也需要做出進一步的改進。

研究人員將局部不變特征應用于目標跟蹤，也取得了較好的效果。Tang等［9］使用基于SIFT(scale invariant feature transform，SIFT)的屬性關系圖(attributed relational graph，ARG)表示目標，在幾個連續(xù)的幀中總是出現的特征被認為是穩(wěn)定的特征，用于構建圖;反之，較少出現的特征則從圖中刪除。然而，在實際的視覺目標跟蹤過程中，由于外觀、光照等的變化，這樣穩(wěn)定的特征比較少。Carrera等［10］根據SURF(speeded-up robust features)算法提出了一種魯棒的目標跟蹤算法，該算法使用Harris算子檢測目標區(qū)域中的興趣點，使用SURF描述算子對興趣點進行表示，在目標跟蹤過程中，使用UKF(unscented kalman filter)預測目標中心位置。實驗表明，該算法在目標旋轉、尺度變化等情況下，魯棒性較好。然而，在目標姿態(tài)、外觀發(fā)生改變的情況下，該算法未能及時更新目標模型。

為減少計算量，有效應對目標跟蹤過程中的遮擋、目標外觀變化等情況，本文提出了一種基于SURF的目標跟蹤算法。

1 SURF算法

SURF算法是Bay等［11－12］在2006年提出的一種具有尺度、旋轉不變性的圖像局部特征檢測和描述算子。該算法不但在性能上達到或超過了目前常用的基于Harris、基于Hessian矩陣的方法和SIFT等算法，而且其執(zhí)行速度更快。

1.1 興趣點的檢測

SURF算法的興趣點檢測算子基于Hessian矩陣，這樣可以利用積分圖像，極大地減少時間。

對于圖像中的一個像素點X=(x，y)，在尺度σ下該點處的Hessian矩陣定義為

文獻［13－14］中已經表明高斯核在尺度空間分析中性能優(yōu)良，實際應用時須將其離散化。在SURF算法中，將二階高斯微分算子近似為如圖1所示的盒形濾波。使用這些算子SURF算法不但以較低的開銷在積分圖像上進行計算，且計算時間獨立于濾波大小。

圖1中的高斯二階微分算子可記為Dxx、Dyy和Dyy。Hessian矩陣的行列式為

Lxx、Lyy和Lxy分別為Dxx、Dyy和Dxy與輸入圖像在某像素點處卷積，權值w按如下方式計算

式中，|·|F為F-范數。

興趣點從不同尺度檢測，尺度空間通常表示為一個圖像金字塔。由于積分圖像的使用，SURF算法可以通過不斷增大濾波而不是減小圖像進行尺度空間分析，如圖2所示，左圖表示不斷減少圖像大小進行尺度空間分析，SURF算法使用右圖所示方法，使用相同大小的輸入圖像，通過不斷增大濾波大小進行尺度空間分析。

圖1 高斯二階微分算子Fig.1 Gaussian second-order partial derivative operator in x-，y-and xy-directions

尺度空間分成不同分組，為了使濾波大小為奇數且保證中心像素的存在，相鄰濾波必須增大至少2像素。對于每一新的尺度空間分組，濾波增大加倍(從6～12到24～48)。在SURF算法中，第1分組的濾波大小分別為9、15、21、27，第2分組至第4分組中的濾波大小分別為15、27、39、51;27、51、75、99;51、99、147、195。

SURF算法運用非最大化抑制和插值方法尋找興趣點。

圖2 尺度空間分析Fig.2 Scale space analysis

1.2 興趣點的描述

為提取興趣點的描述，首先構造一個以興趣點為中心，沿興趣點方向的窗口，窗口大小為20s。該窗口被劃分成4×4的小區(qū)域，在每個小區(qū)域計算Haar小波響應，水平方向記為 dx，垂直方向記為 dy(濾波大小為2s)。dx和dy與以興趣點為中心高斯分布(σ=3.3s)進行加權。在每個小區(qū)域中計算向量v=(Σ dx，Σ dy，Σ |dx|，Σ |dy|)，連接4×4個小區(qū)域的向量，就可得到一個長度為64的向量。

圖3 興趣點方向的指定Fig.3 Orientation assignment for the interest point

1.3 興趣點的匹配

興趣點的匹配基于向量間的距離，一般使用馬氏(Mahalanobis)距離或歐氏(Euclidean)距離。

2 基于SURF的目標跟蹤算法

在目標跟蹤中，目標的表示、目標的檢測、遮擋情況的處理、目標大小的縮放、目標模型的更新等是需要著重解決的幾個問題，在本算法中，我們針對這幾個問題提出了基于SURF的目標跟蹤算法。

基于SURF的目標跟蹤算法以第1幀圖像中矩形框界定的目標為輸入，后續(xù)幀中表示目標位置的矩形框作為輸出。該算法的總體框架見圖4。

算法獲得輸入后，對于每一幀新的圖像，為減少計算量，不是在整個圖像中搜索目標，而是首先根據目標的運動狀態(tài)，計算目標搜索區(qū)域。算法在目標搜索區(qū)域中檢測SURF點，將SURF點與目標模型中的SURF點進行比較，計算最佳匹配SURF點。然后，根據最佳匹配SURF點的個數，判定目標是否發(fā)生遮擋。若發(fā)生遮擋，則根據獲得的匹配SURF點在目標模型中相對應的SURF點，計算目標中心，根據SURF點及其鄰近R、G、B直方圖計算目標的實際位置。若目標未發(fā)生遮擋，則根據檢測到的最佳匹配SURF點，計算目標中心，根據SURF點鄰近R、G、B直方圖縮放跟蹤窗口，計算目標的最佳大小和位置。并根據獲得的目標窗口，重新計算窗口內SURF點及其鄰近R、G、B直方圖，對目標模型進行更新，以反映目標的最新變化。

圖4 算法框架圖Fig.4 Flowchart of the tracking process

2.1 目標檢測

目標檢測是視覺跟蹤的中心任務之一。本節(jié)的主要任務是計算目標的搜索區(qū)域，然后在該區(qū)域中檢測目標的SURF點，這些點作為目標的主要特征點，確定了目標的大致位置，為后面計算目標的準確位置做必要的準備。

2.1.1 目標表示

本文提出的算法屬于基于特征的目標跟蹤算法。算法首先檢測目標區(qū)域中的SURF點，然后計算每個SURF點鄰近的R、G、B直方圖，以SURF點和R、G、B直方圖來表示目標。如圖5所示，以目標跟蹤窗口內的若干小矩形框的R、G、B直方圖表示目標。在對跟蹤的目標進行直方圖的相似度比較時，不同的小矩形框賦以不同權值，離目標中心近的賦以較大權值，離目標中心較遠的賦以較小權值，權值在算法運行過程中動態(tài)確定(權值的計算見2.3節(jié))。在目標跟蹤框中不可避免地會包含很多背景像素，對離目標中心較遠的小矩形框直方圖賦以較小權值，可以降低其對目標表示的影響，以便較準確地檢測到目標，提高跟蹤的精度。

圖5 目標的表示Fig.5 Target representation

2.1.2 目標搜索區(qū)域的計算

為減少算法的計算成本，加快算法的執(zhí)行速度，本算法不是掃描整個輸入圖像檢測目標，而是根據上一幀圖像中目標的位置和速度，在當前幀中掃描目標可能的鄰近區(qū)域，進而確定目標的準確位置。目標可能鄰近區(qū)域，即目標搜索區(qū)域的計算方法為:

其中，testRect和targetRect分別表示當前幀的目標搜索區(qū)域和上一幀的目標區(qū)域。其第一、第二分量表示矩形區(qū)域左上角坐標，第三、第四分量分別表示矩形區(qū)域的寬度和高度。dx和dy分別表示目標在x和y方向上的速度，此處我們假定目標沿右下角方向移動，若目標向其他方向移動，目標搜索區(qū)域可相應向該方向增長。step_w和step_h分別表示矩形區(qū)域在寬度和高度方向上需要增加的量，其計算方法如下

其中，sw和sh分別表示目標搜索區(qū)域在寬度和高度方向上的增長系數，一般選擇0.1～0.3，本文中sw和sh均設置為0.2。

目標搜索區(qū)域的計算見圖6，圖中虛線框為上一幀圖像中檢測到的目標的準確位置，點線框為原目標位置進行擴展后的區(qū)域。

圖6 目標搜索區(qū)域的計算Fig.6 Computation of target searching area

2.1.3 SURF點的檢測

確定了目標搜索區(qū)域后，應用SURF算法檢測該區(qū)域中的SURF點，一般來說，在目標搜索區(qū)域中檢測到的SURF點將多于目標模型中SURF點的數量。為計算最佳匹配SURF點，我們首先計算目標搜索區(qū)域與目標模型中SURF點的歐氏距離

其中，TI(i)表示在目標搜索區(qū)域中檢測到的第i個SURF點，TS(k)表示目標模型中的第k個SURF點。對于歐氏距離小于某一閾值θdist的SURF點，我們選定為最佳匹配點，其中θdist的值在算法運行過程中動態(tài)確定，一般為上一幀最佳SURF匹配點歐氏距離的最大值。

檢測到的最佳SURF匹配點即為目標的大致位置，為計算目標的準確位置，需要計算目標的中心位置，為此算法將判斷目標是否發(fā)生遮擋。

2.2 遮擋處理

為簡單起見，算法根據如下原則，判斷目標是否發(fā)生遮擋，并進行相應處理:

(1)若未檢測到匹配點，則目標發(fā)生完全遮擋，在后續(xù)幀中，再次檢測到與目標模型中相匹配的SURF點時，標志著目標再次出現。

(2)若匹配點的個數少于上一幀中最佳匹配點個數的75%，則目標發(fā)生部分遮擋。此時，目標中心根據目標模型中相應匹配點到中心的距離來計算，為方便說明，我們進行如下符號約定:目標模型中目標中心位置為O?

，目標模型中相應最佳SURF匹配點的位置為P?i，因此，目標中心到該點的距離為

如圖7所示。從而，當前幀目標中心的估計值為

其中，n為檢測到的最佳匹配SURF點的個數。

圖7 目標發(fā)生遮擋時的目標中心位置計算Fig.7 Computation of the center position of a shaded target

圖8 目標未發(fā)生遮擋時的目標中心位置計算Fig.8 Computation of the center position without a shaded target

(3)否則，目標未發(fā)生遮擋，根據檢測到的最佳SURF匹配點計算目標中心位置，見圖8，目標中心的估計值為

2.3 目標縮放

檢測到當前幀目標中心的估計值后，算法將根據最佳匹配SURF點鄰近的顏色直方圖來計算目標的準確位置。

根據上一幀中目標跟蹤窗口的大小，在當前幀中，算法隨機改變跟蹤窗口的寬度和高度，對于每一個窗口W'=S(W，winw，winh)，其中W為上一幀中目標跟蹤窗口，winw和winh分別為寬度和高度方向上窗口大小改變系數，本文中我們選取0.8≤winw，winh≤1.2。算法計算在該窗口內，最近匹配SURF點鄰近的R、G、B直方圖，并與目標模型中相應SURF點的R、G、B直方圖進行比較，返回相似度最高的窗口大小，即

式中，n為最佳匹配SURF點的個數，θ(i)為相應于第i個匹配點的目標模型中的SURF點，λi為第i個SURF點鄰近直方圖的權重系數，在算法運行過程中動態(tài)改變，其計算方法為

其中，b為直方圖箱子索引號，Hi為目標搜索區(qū)域中第i個SURF點鄰近的原始直方圖。ρ(·)度量目標區(qū)域和目標模板的R、G、B直方圖的接近程度，本文對R、G、B三個分量采用相同權重，即均為1/3，算法采用Bhattacharyya距離

上式中，N為直方圖箱數。

因為在本文中，目標跟蹤窗口和直方圖的計算均是矩形框，所以可以采用積分直方圖以加快算法的執(zhí)行速度。

2.4 模型更新

由于姿態(tài)改變、光線變化以及場景改變等因素的影響，目標在運動過程中其特征不斷發(fā)生變化，目標模型應及時反映這些變化。因此，模型更新也是影響目標跟蹤效果的一個重要方面。為此，本文提出了一種在線更新目標模型的策略。

在遮擋發(fā)生前，系統(tǒng)保存有最近未發(fā)生遮擋的前M(本文中，我們設置M為10)幀圖像中的目標特征(SURF點、鄰近直方圖)。若當前幀中目標未發(fā)生遮擋，則根據2.3中計算目標的準確跟蹤窗口，重新計算跟蹤窗口內的SURF點鄰近的R、G、B直方圖，將SURF點即R、G、B直方圖保存到目標模型中，若目標模型中的幀數超過M，則刪除最前幀中的目標特征。

若當前幀中目標發(fā)生遮擋，停止更新目標模型，根據匹配的最佳SURF點及目標模型，估計可能的目標中心位置，計算SURF點鄰近R、G、B直方圖，輸出目標未遮擋部分。

3 實驗結果與分析

為了評價所提出算法的性能，通過幾個實驗對其進行測試，主要針對目標縮放、遮擋情況的處理。經典均值偏移(MST)算法［7］應用較為廣泛，因此本文選擇該算法作為對比算法。本文將選用PETS［15－16］作為測試數據集，該數據集在目標跟蹤領域作為測試數據集得到了廣泛應用。

3.1 目標縮放的對比實驗

本次實驗使用PETS2001［15］中數據集，在該數據集的視頻中，目標由遠至近，跟蹤目標逐漸變大，圖像大小為768×576。圖9為使用不同算法的部分跟蹤結果，其中左側為經典MST算法的部分跟蹤結果，右側為本文提出算法的跟蹤結果。實驗中本文算法選用的參數為:最優(yōu)匹配SURF點個數為12，目標模型中歷史幀數為10，R、G、B直方圖箱數為128。圖9中從上到下依次為第329、333、343、360、379幀圖像。

圖9 目標發(fā)生縮放情況下的不同方法的跟蹤結果比較Fig.9 Comparisons of tracking results of different algorithms for a zoomer target

從圖9中可以看出，在目標大小發(fā)生變化的情況下，本文提出的算法可以較好地適應目標大小的變化，而經典MST算法在第360幀己不能很好地適應目標大小的變化，最終只能定位到目標的一部分。

3.2 遮擋情況的對比實驗

在本節(jié)中，我們使用PETS2007［16］中的數據集，圖像大小為720×576。圖10為使用不同算法的部分跟蹤結果，其中左側為經典MST算法的部分跟蹤結果，右側為本文提出算法的跟蹤結果。實驗中本文算法選用的參數為:最優(yōu)匹配SURF點個數為12，目標模型中歷史幀數為10，R、G、B直方圖箱數為128。圖10中從上到下依次為第10、47、75、110幀圖像。

從圖10可以看出，從第47幀開始，經典MST算法的跟蹤結果即開始偏離目標，在第75幀中，經典MST算法已經失去了目標。而本文提出的算法，即使在有遮擋的情況下，也可較好地跟蹤目標，說明了本文算法的有效性。

圖10 目標發(fā)生遮擋情況下的不同方法的跟蹤結果比較Fig.10 Comparisons of tracking results of different algorithms for a shaded target

3.3 實驗分析

本節(jié)從以下三個方面說明不同參數的選擇對目標跟蹤結果的影響。

3.3.1 SURF特征點個數的選擇

SURF特征點并不是越多越好，如圖11所示，從上到下依次為SURF特征點數4、8、12、16的跟蹤結果。左側分別表示不同參數下PETS2001［15］中第349幀的跟蹤結果，右側分別表示不同參數下第379幀的跟蹤結果。

文獻［8］中通過實驗說明了使用單一直方圖進行目標跟蹤時，常常得不到令人滿意的跟蹤效果。從圖11中也可以看出，SURF特征點選取得少，算法雖然也能較準確地跟蹤到目標，但是并不能準確地定位到完整的目標大小。這是因為SURF特征點較少，這些特征點只能代表目標的局部特征，其R、G、B直方圖表示目標的區(qū)分性不足。反之，SURF特征點選取得越多，跟蹤結果受目標周邊背景特征點的影響越大;再者，SURF特征點越多，每個特征點的鄰近區(qū)域越小，其R、G、B直方圖在最終目標跟蹤結果中所占的權重也越小。所以，應選取適當數量的SURF特征點。實驗表明，目標跟蹤過程中，一般選取SURF特征點的數量為目標區(qū)域中檢測到的SURF特征點數量的1/3，跟蹤效果較好。

圖11 不同SURF特征點個數下的跟蹤結果比較Fig.11 Comparisons of tracking results corresponding to different numbers of SURF feature points

3.3.2 目標模型中歷史幀數量的選擇

直覺上，跟蹤目標的特征在連續(xù)幀中相似度較大。因此，目標模型中歷史幀數一般不會設置較大。

表1 目標在歷史幀中的相似度比較Table 1 Object similarity comparison among the past frames

我們在選取的SURF特征點數分別為4、8、12、16的情況下，多次進行實驗，在目標模型的最優(yōu)SURF特征點匹配中，歷史幀的使用情況如表1所示。從表1可以看出，當前幀中的SURF特征點主要與前3幀相匹配。所以，目標模型中歷史幀數一般設置為3～5。

3.3.3 直方圖中箱數量的選擇

對于RGB圖像來說，直方圖的箱數最大為256。實驗表明，箱數越大，越能較好地表示目標的特征。箱數的大小對算法的運行速度影響不顯著。

4 結論

本文根據SURF相比于SIFT等特征提取方法在性能、執(zhí)行速度等方面的優(yōu)點，提出了一種基于SURF的目標跟蹤和在線目標模型更新算法，該方法的時間復雜度較低，執(zhí)行速度快，并能夠在線實時更新目標模型。對于目標運動過程中突然改變運動方向，以及光照突然變化的場景下的目標跟蹤算法是今后研究的方向。

［1］HU W M，TAN T N，WANG L，et al.A survey on visual surveillance of object motion and behaviors［J］.IEEE Transactions on Systems，Man and Cybernetics，Part C，2004，34(3):334 －352.

［2］BABU R V，SURESH S，MAKUR A.Online adaptive radial basis function networks for robust object tracking［J］.Computer Vision and Image Understanding，2010，114(3):297－310.

［3］KASS M，WITKIN A，TERZOPOULOS D.Snakes:Active contour models［J］.International Journal of Computer Vision，1988，1(4):321－331.

［4］MUSAVI M，AHMED W，CHAN K H，et al.On the training of radial basis function classifiers［J］.Neural Networks，1992，5(4):595－603.

［5］AVIDAN S.Support vector tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(8):1064－1072.

［6］AVIDAN S.Ensemble tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(2):261 －271.

［7］COMANICIU D，RAMESH V，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(5):564－577.

［8］NEJHUM S M，HO J，YANG M H.Online visual tracking with histograms and articulating blocks［J］.Computer Vision and Image Understanding，2010，114(8):901－914.

［9］TANG F，TAO H.Object tracking with dynamic feature graph［C］//2nd Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance，2005.Piscataway:IEEE，2005:25－32.

［10］CARRERA G，SAVAGE J，MAYOL-CUEVAS W.Robust feature descriptors for efficient vision-based tracking［M］//Progress in Pattern Recognition，Image Analysis and Applications.Berlin:Springer，2007，4756:251 －260.

［11］BAY H，TUYTELAARS T，van GOOL L.Surf:Speeded up robust features［C］//Computer Vision – ECCV 2006.Berlin:Springer，2006:404 －417.

［12］BAY H，ESS A，TUYTELAARS T，et al.Speeded-up robust features(surf)［J］.Computer Vision and Image Understanding，2008:110(3):346－359.

［13］KOENDERINK J J.The structure of images［J］.Biological Cybernetics，1984，50(5):363 －370.

［14］LINDEBERG T.Scale-space for discrete signals［J］.IEEE Trans Pattern Anal Mach Intell，1990，12(3):234 －254.

［15］PETS.Sequence 2［EB/OL］.［2014－02－10］.ftp://ftp.cs.rdg.ac.uk/pub/PETS2001/.

［16］PETS.Sequence 3［EB/OL］.［2014－02－10］.ftp://ftp.cs.rdg.ac.uk/pub/PETS2007/.