利用密度描述符對應的視覺跟蹤算法

查宇飛，楊 源，王錦江，張立朝

（1.空軍工程大學航空航天工程學院，710038，西安；2.空軍工程大學空管領航學院，710038，西安；3.空軍工程大學綜合電子信息系統與電子對抗技術研究中心，710038，西安）

魯棒視覺跟蹤系統的關鍵在于尋找目標的不變特征，光流［1］假定目標在相鄰圖像之間的亮度保持恒定。然而在實際情況下，當目標發生一些微小變化時，如光照變化、目標形變或視頻中噪音較大等，容易丟失目標，很難獲得滿意的跟蹤效果。顏色直方圖特征［2］描述了顏色分布的恒常性，文獻［3-4］分別在粒子濾波和均值漂移框架下，利用目標直方圖不變特征來實現魯棒的目標跟蹤。然而，直方圖本質上是一種統計特征，未考慮目標的結構信息。子空間跟蹤算法［5］利用子空間的不變性，但當目標發生遮擋或姿態變化時，主成分比重降低，易丟失目標。尺度不變特征轉換（SIFT）描述符［6］、BRIEF描述符［7］和DBrief描述符［8］等不變特征描述符，利用局部相關像素對關鍵點進行描述，使關鍵點具有尺度和旋轉不變性。文獻［9］利用SIFT算法檢測到的稀疏關鍵點及其描述符構建相關圖來表征目標，然而在實際中相關圖的構建比較困難，從而導致跟蹤失敗，可將SIFT描述符作為均值漂移的度量實現跟蹤［10］。

以上基于局部不變特征描述符的跟蹤算法均屬于稀疏描述符，關鍵點檢測結果對跟蹤結果影響很大。與稀疏描述符不同，密度描述符不需要檢測關鍵點，可直接對每一個像素建立描述符，DAISY描述符［11］是2010年提出的一種密度描述符，由像素點附近的多個采樣點所生成的卷積方向圖向量組成，該方法對仿射變換和光照差異都有較好的魯棒性，在稠密立體匹配中取得了較好的效果。Liu等人利用密度SIFT［12］尋求圖像對應關系［13］，但密度SIFT沒有考慮尺度的影響。為克服稀疏描述符在關鍵點檢測中的不穩定性，本文提出了一種基于密度描述符的跟蹤算法，避免了關鍵點檢測不穩定及其誤匹配帶來的影響。所提算法通過計算目標在相鄰兩幀之間的密度描述符流，考慮目標的空間分布特性和描述符的權重，得到目標的運動矢量，獲得目標在當前幀中的估計；根據密度描述符的運動矢量與目標運動矢量的關系及其匹配程度，更新密度描述符的權重。如此迭代，從而實現對感興趣目標的魯棒跟蹤。

1 密度描述符及其運動矢量的計算

尺度不變特征轉換是計算機視覺具有里程碑意義的工作，包含關鍵點的檢測、描述和匹配3個步驟，但本文所提算法不檢測關鍵點，只是對圖像中像素點規則采樣，直接構建圖像的密度描述。SIFT描述符在檢測到的關鍵點周圍取一個16×16的鄰域像素區域，并將鄰域劃分為16個子區域，每個子區域的直方圖分布為

式中：N表示該區域中的像素個數；Hi表示第i個子區域的直方圖，將圖像分成16個子區域；b表示圖像的灰度級，一般設為8個灰度級；p表示像素在圖像中的位置；Q（I（p），b）為指示函數，若像素屬于灰度級b，則輸出為1，否則為0。因此，每個子區域對應一個含有8個灰度級的直方圖來描述該像素的局部描述符，然后將每個子區域直方圖合并，得到一個128維的向量，即SIFT描述符

SIFT描述符在匹配時，要預先知道每個描述符的尺度和方向參數。SURF描述符［14］利用積分圖像，降低SIFT描述符計算，獲得接近SIFT描述符的效果。對于目標的描述，需首先檢測目標中的關鍵點，然后對每個關鍵點進行描述，構成目標模型

式中：Pi表示關鍵點的位置；σi表示關鍵點的尺度；θi表示關鍵點的主方向；Fi表示描述符。然而，在實際中并不能總是在同一個位置、尺度和方向上得到相同的描述符，這樣會導致錯誤的匹配，當檢測到的特征很少時，少量的匹配錯誤將會使目標模型無法有效地表示目標。為了解決這一問題，本文提出用密度特征描述符表征目標模型，這種描述符不依賴特征檢測，直接對目標中的規則像素點進行描述。

設原始圖像I的尺寸是M×N，構建的密度特征描述符記作F，其維度為M×N×128，最后一維表示SIFT特征描述符的維數。由于密度特征描述符不是建立在特征檢測的基礎上，故沒有尺度和方向信息。因此，目標模型表示為

在時刻t，圖像中位于（x，y）處的像素值表示為I（x，y，t），而光流假設相鄰兩幀像素灰度值保持不變，即I（x，y，t）=I（x+u，y+v，t+1），從而獲得像素的運動矢量（u，v）。假設相鄰幀的描述符保持不變，即F（x，y，t）=F（x+u，y+v，t+1），同樣獲得各個像素的運動矢量（u，v）。特征描述符含有該像素的局部信息，而不僅僅考慮單個像素的信息。

取p=（x，y）作為與圖像等價的網格，取w（p）=（u（p），v（p））作為p 點的運動向量，得約束密度SIFT描述符為

F（p，t）-F（p+w（p），t+Δt）=0 （5）式中：F（p，t）為t時刻時p點的密度特征描述符?？紤]到跟蹤問題中目標運動的平滑性，利用一階馬爾科夫隨機場構造能量函數

式（6）中的能量函數包含數據項、位移項和平滑項3項。其中：數據項主要保證目標在相鄰幀之間具有相同的描述符；位移項用來懲罰目標在相鄰幀之間的運動量；平滑項用來約束目標內部的相鄰像素應具有的相同的運動矢量。在目標函數的位移和平滑項中引入閾值d，通過簡化L1范數，消除外點匹配和流不連續性的影響，其中β和α分別為數據項和平滑項的系數，代表對應項在整個能量函數中的比重。式（6）可以采用SITF流［14］、PatchMatch［15］、可變空域金字塔匹配［16］等方法進行優化。

2 目標跟蹤算法

通過上節的分析，可以獲得密度描述符的運動矢量，而目標在視頻中的位置不斷發生變化，同時自身的狀態（如尺度、方向等）也不斷發生變化，因此要實現對目標的魯棒跟蹤，需要解決2個問題：如何由單個特征描述符的運動矢量去估計目標的運動矢量；如何有效地更新目標模型，以適應目標的變化。本節將在上節獲得的密度描述符運動矢量的基礎上，詳細描述跟蹤的過程。

（1）初始化。在初始化圖像中，手動標定目標在圖像中的位置，用矩形R=｛x，y，w，h｝來表示，其中（x，y）表示矩形左上角的位置，（w，h）表示矩形的寬和高。目標圖像為x=I（R），即矩形框所對應的圖像。構建目標的密度描述符，同時初始化每個描述符，使其權重相同，即wij=1／（M×N）。

（2）跟蹤過程。當獲得下一幀圖像后，在上一幀估計的目標位置上獲取候選目標圖像xt=It（Rt-1），同時獲得對應的密度特征描述符Ft=Dense（xt）。通過計算相鄰兩幀目標的密度特征描述符對應關系，最小化能量函數獲得運動矢量

式中：u、v為M×N矩陣，表示目標中每個像素點的運動矢量。整個目標的運動矢量還需要考慮目標本身的空間分布特性和特征描述符的重要性。本文采用文獻［16］所提出的可變空域金字塔算法，可快速實現相鄰兩幀目標的密度特征描述符對應關系。在跟蹤過程中，一般采用矩形框標識目標，因此離矩形中心越近的像素，屬于目標的可能性越大，同時不同位置的描述符對表征目標信息的貢獻也不一樣，因此可采用下式來估計目標的運動矢量

式中：pc表示矩形框的中心位置；w表示描述符的重要度度量；δ為空域分布參數?？梢钥闯觯繕说倪\動矢量由密度描述符流、空間分布和描述符的重要程度共同決定。

（3）更新過程。在跟蹤過程中需要適應不斷變化的目標，而每個描述符表征目標的重要程度不一樣，需要不斷更新權重。權重更新如下

3 實驗分析

所有實驗都是在Intel Core Duo 3.0GHz、2GB內存的筆記本上進行的。算法通過MATLAB實現，核心算法采用MEX文件，其中計算SIFT流的算法采用文獻［16］的公開代碼，能量函數構建中的參數取值為：α=2，β=0.05，d=40，空域分布參數δ取目標矩形框寬高均值的1／4，權重更新參數λ=0.7。跟蹤過程中目標狀態只考慮目標在二維空間的狀態，本文算法效率與目標框的大小相關，平均為20幀／s。相對于稀疏描述符，密度描述符不需要檢測關鍵點，得益于文獻［16］提出的快速優化算法，因此大大加快了匹配速度，保證了本文算法的實時性。

實驗數據為 MILT數據庫［17］和PROST數據庫［18］中的8段視頻，目標真實狀態通過相應的數據庫獲得，目標初始狀態由數據庫給出。比較算法包括基于子空間不變的跟蹤算法（IVT）、基于正反向光流的跟蹤算法（Median Flow）［19］和基于稀疏不變特征的稀疏描述符［20］。IVT跟蹤和 Median Flow跟蹤的代碼分別來自公開的代碼，稀疏描述符的代碼是由VLFEAT和RANSAC工具箱［21］編寫的。

圖1 跟蹤結果

3.1 定性分析

圖1 是部分實驗結果圖，IVT跟蹤算法、Median Flow跟蹤算法、稀疏描述符跟蹤算法和本文所提算法（DDC算法）分別用虛線、點線、點劃線和實線的矩形框表示。下面將從光照變化、姿態變化和部分遮擋3個方面對實驗結果進行定性分析。

（1）光照變化。在視頻“Sylvester”和“David”中，都有不同程度的光照變化，特別是“David”中，目標由暗處走向亮處，光照變化較大，光照變化使目標灰度值突然變化，導致目標外觀改變，增加了跟蹤的難度?；谙∈杳枋龇母櫼蕾囂卣鼽c的檢測從而導致跟蹤的不穩定。IVT跟蹤受光照的影響，導致正樣本更新產生誤差，而誤差積累會導致跟蹤結果偏離真實目標。Median Flow跟蹤是利用光流在相鄰兩幀之間預測目標運動矢量，在光照變化不大的情況下，能夠較好地跟蹤目標。密度特征描述符利用相鄰像素相對分布關系，而目標整體灰度的變化不會改變相對分布，從而避免了光照變化帶來的影響，故能穩定地跟蹤目標。

（2）姿態變化。視頻“Girl”、“Jumping”、“Lemming”和“Box”中，目標發生了大的姿態變化。雖然目標的變化很大，但是它們都是漸變的，也就是目標在時序上具有連續性，這將考驗跟蹤算法的在線學習能力。IVT跟蹤是每隔5幀更新，對特征基向量進行更新，不能適應目標的快速變化；Median Flow跟蹤只考慮相鄰兩幀之間的情況，誤差積累導致跟蹤結果偏離真實的目標；基于稀疏描述符的跟蹤能適應目標大的變化，但誤匹配和特征檢測的不穩定會導致跟蹤失??；本文的算法由于采用密度特征描述符，能夠適應目標的變化，同時利用動態特征描述符，從而消除了誤差積累的影響。

（3）部分遮擋。視頻“Faceocc”和“Faceocc2”主要測試遮擋對算法的影響，其中“Faceocc2”中的目標還發生了旋轉變化。受遮擋影響最大的是基于稀疏描述符的跟蹤算法，由于目標遮擋后無法檢測到特征，從而導致誤匹配；IVT跟蹤是將目標整體當作向量看待，遮擋使得特征基模糊，偏離了真實目標；Median Flow跟蹤由于只用匹配較好的點，則目標部分遮擋對算法的影響不是很大；本文算法基于密度特征，使得部分遮擋并不能導致匹配失敗。因此，在目標發生各種變化和背景干擾很大的情況下，本文算法能夠很好地跟蹤目標，與Median Flow算法、IVT算法和稀疏描述符算法相比，能夠更好地處理光照、姿態變化和遮擋的影響。

3.2 定量分析

本文用重疊度、均方根誤差2個標準來衡量本文算法與其他算法的優劣。重疊度是檢測目標與真實目標重疊部分與兩者的并集之比，即

式中：^S和S分別表示估計值和真實值。當檢測目標與真實目標完全重疊時，重疊度為1；當檢測到錯誤目標時，重疊度會降低；當完全檢測不到目標時，重疊度為0。若重疊度大于0.5，可認為跟蹤成功，否則認為目標丟失。

均方根誤差的計算如下

式中：（x，y）為算法得出的跟蹤框的中心位置坐標；（^x，^y）為標定的跟蹤框的中心位置坐標。均方根誤差表示了目標中心與真實目標中心的誤差，值越小表明跟蹤精度越高。

表1和表2分別為4種算法在各個視頻上的跟蹤成功率和均方根誤差。加粗和加線的表示在該視頻中的成功率排名第1和第2。與基于子空間不變的IVT和基于灰度不變的Median Flow相比，本文算法獲得了更好的結果，部分原因在于SIFT描述符能更好地描述變化目標的不變屬性。與稀疏描述方法相比，本文算法由于不需要檢測關鍵點和計算仿射矩陣，同樣獲得了更好的結果。

表1 不同算法的跟蹤成功率

表2 不同算法的均方根誤差比較

4 結 論

魯棒視覺跟蹤的一個關鍵問題在于如何快速有效地描述視頻中的目標，本文算法通過計算目標在相鄰兩幀之間的密度描述符流，估計得到目標的運動矢量，同時更新密度描述符的權重。在實驗中，針對光照變化、姿態變化和遮擋等情況，對本文算法和其他相關算法進行了對比實驗，結果表明本文算法能夠很好地適應復雜的變化，能取得比其他算法更好的結果。本文算法的運行效率需要進一步提升，主要原因在于密度描述符對應的計算量較大。

［1］ SENST T，EISELEIN V，SIKORA T.Robust local optical flow for feature tracking ［J］.IEEE Transactions on Circuits and Systems，2012，22（9）：1377-1387.

［2］ LEE K Y，PARK R H，LEE S W.Color matching for soft proofing using a camera［J］.IET Image Process，2012，6（3）：292-300.

［3］ PEREZ P，HUE C，VERMAAK J，et al.Color-based probabilistic tracking［C］∥Proceedings of 7th European Conference on Computer Vision.Berlin，Germany：Springer，2002：661-675.

［4］ COMANICIU D，RAMESH V，MEER P.Kernel-based object tracking ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

［5］ ROSS D，LIM J，LIN Ruei-Sung，et al.Incremental learning for robust visual tracking ［J］.International Journal of Computer Vision，2007，77（1）：125-141.

［6］ DAVID G L.Scale ＆ affine invariant interest point detectors［J］.International Journal of Computer Vision，2004，60（1）：63-86.

［7］ CALONDER M，LEPETIT V，FUA P.Binary robust independent elementary features［C］∥Proceedings of 11th European Conference on Computer Vision.Berlin，Germany：Springer，2010：778-792.

［8］ HEINLY J，DUMN E，FRAHM J M.Comparative evaluation of binary features［C］∥Proceedings of 12th European Conference on Computer Vision.Berlin，Germany：Springer，2012：369-382.

［9］ MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors ［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

［10］ZHOU Huiyu，YUAN Yuan，SHI Chunmei.Object tracking using SIFT features and mean shift［J］.Computer Vision and Image Understand，2009，113（3）：345-352.

［11］ENGIN T，VINCENT L，PASCAL F.An efficient dense descriptor applied to wide baseline stereo ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（5）：815-830

［12］VEDALDI A，FULKERSON B.An open and portable library of computer vision algorithms ［C］∥Proceedings of the International Conference on Multimedia.New York，USA：ACM，2010：1469-1472

［13］LIU Ce，JENNY Y，ANTONIO T，et al.Dense correspondence across different scenes［C］∥Proceedings of 9th European Conference on Computer Vision.Berlin，Germany：Springer，2008：28-42.

［14］BAY H，TUYTELAARS T，GOOL L V.Speeded up robust features ［C］∥Proceedings of 7th European Conference on Computer Vision.Berlin，Germany：Springer，2006：404-417

［15］BARNES C，SHECHTMAN E，GOLDMAN D，et al.The generalized PatchMatch correspondence algorithm ［C］∥Proceedings of 11th European Conference on Computer Vision.Berlin，Germany：Springer，2010：29-43.

［16］KIM J，LIU Ce，SHA Fei，et al.Deformable spatial pyramid matching for fast dense correspondences［C］∥26th IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2013：2307-2314.

［17］BABENKO B，YANG Ming-Hsuan，BELONGIE S.Visual tracking with online multiple instance learning［C］∥24th IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2009：983-990.

［18］SANTNER J，LEISTNER C，SAFFARI A，et al.Parallel robust online simple tracking［C］∥ Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2010：723-730.

［19］KALAL Z，MIKOLAJCZYK K，MATAS J.Tracking learning detection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，6（1）：1-14

［20］藺海峰，馬宇峰，宋濤.基于SIFT特征目標跟蹤算法研究 ［J］.自動化學報，2010，36（8）：1204-1208.

LIN Haifeng，MA Yufeng，SONG Tao.Research on object tracking algorithm based on SIFT ［J］.Acta Automatica Sinica，2010，36（8）：1204-1208.

［21］ZULIANI M，KENNEY C S，MANJUNATH B S.The multiRANSAC algorithm and its application to detect planar homographies［C］∥Proceedings IEEE International Conference on Image Processing.Piscataway，NJ，USA：IEEE，2005：153-156.