王治丹， 蔣建國， 齊美彬

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009)

類屬圖密集近鄰搜索的視覺跟蹤算法研究*

王治丹， 蔣建國， 齊美彬

(合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009)

提出一種基于密集近鄰搜索的視覺跟蹤算法，能夠有效應(yīng)對目標跟蹤過程中出現(xiàn)的形變和遮擋問題?；隈R爾科夫隨機場建立圖像分割模型，提取出目標部件，建立目標部件的類屬圖矩陣；通過搜索類屬圖矩陣中的密集近鄰，得到相鄰幀之間目標部件的匹配關(guān)系；通過匹配關(guān)系得到跟蹤目標位置概率圖，確定目標跟蹤位置。實驗結(jié)果表明：本文提出的方法相比其他同類方法效果更好。

視覺跟蹤； 類屬圖； 密集近鄰搜索； 置信圖

0 引 言

視覺跟蹤作為計算機視覺領(lǐng)域的基礎(chǔ)問題，在各方面都取得了重要應(yīng)用，比如視頻監(jiān)控等。之前,研究者設(shè)計出了各種算法并取得重要進展，但是由于目標在跟蹤過程中出現(xiàn)形變、面臨遮擋等情況，對目標的跟蹤仍然是一項很棘手的工作。

早期的大多數(shù)跟蹤算法是基于目標整體模型建立特征表達來描述目標的表象變化，比如稀疏表示[1]以及子空間學(xué)習(xí)[2]等。由于存在目標形變和遮擋，即使將特征表達改進得相對全面和復(fù)雜，很多固定尺度的跟蹤器仍然會跟蹤丟失。為克服這一問題，研究者提出了基于部件的跟蹤器[3～5]，可以更靈活地處理目標形變和尺度變化，并且有效檢測出遮擋的發(fā)生。文獻[3]基于簡單線性迭代聚類(simple linear iterative clustering,SLIC)算法將目標搜索區(qū)域分割成超像素集合，通過建立表象模型來區(qū)分前景和背景區(qū)域，抵御因形變和遮擋引入的背景噪聲。但是由于較少考慮目標部件之間的結(jié)構(gòu)信息，當前景和背景表象相似時容易混淆目標。在此基礎(chǔ)上，文獻[4]考慮目標部件間的結(jié)構(gòu)信息，基于頻譜分析算法將跟蹤問題轉(zhuǎn)化為圖匹配問題。相似地，文獻[5]利用目標結(jié)構(gòu)信息，訓(xùn)練了一個在線的結(jié)構(gòu)化隱式支持向量機(support vector machine,SVM)模型來預(yù)測目標中各部件的位置。但是由于假設(shè)目標尺度不變，當目標發(fā)生形變的時候會出現(xiàn)跟蹤困難。另外，文獻[9,10]借助了圖像分割技術(shù)來區(qū)分目標和背景區(qū)域，較精確地給出了跟蹤目標的輪廓，提升跟蹤效果。

考慮到跟蹤目標可能會出現(xiàn)形變和面臨遮擋，本文提出了基于類屬圖密集近鄰搜索的跟蹤(dense neighborhoods-based tracker, DNT)方法。首先，在當前幀的目標搜索區(qū)域內(nèi)，根據(jù)圖像分割技術(shù)提取出目標部件，并建立目標部件的類屬圖矩陣。然后，通過搜索類屬圖矩陣的密集近鄰，得到相鄰幀之間的目標部件匹配關(guān)系。最后，通過目標部件及其匹配關(guān)系得到目標位置的概率圖(confidence map)，通過采樣確定目標的最優(yōu)位置。

1 目標類屬圖

1.1 建立類屬圖

首先，在當前幀的目標搜索區(qū)域內(nèi)，基于馬爾科夫隨機場(Markov random field, MRF)建立圖像分割模型，根據(jù)圖割(graph cut)算法[8]技術(shù)提取出目標部件。初始化第一幀目標部件集合為P，當前幀提取出的候選目標部件集合為Q。根據(jù)兩幀目標部件集合，建立目標部件的類屬圖(affinity graph)：G=(V,E)，其中包括:1)圖節(jié)點v∈V，代表相鄰部件匹配對；2)圖邊e∈E,代表匹配對間的幾何關(guān)系。定義如下

(1)

1.2 類屬圖矩陣

圖1 類屬圖矩陣含義

2 密集近鄰搜索

(2)

(3)

式中xo為起始目標節(jié)點分數(shù)，k為密集近鄰內(nèi)節(jié)點的個數(shù)，初始化為一個很小的值，在搜索密集近鄰的過程中不斷增大，節(jié)點概率加權(quán)和最大時得到最優(yōu)解。

圖2為密集近鄰關(guān)系搜索示意圖，左側(cè)為類屬圖，實心點為相對可信的匹配對，空心點為異常匹配對。如果k=3，根據(jù)關(guān)聯(lián)矩陣A，3NN(o)={a,c,q}[9]，而通過密集近鄰搜索得到3DN(o)={b,c,q}的關(guān)聯(lián)值加權(quán)和最大，子矩陣B為該密集近鄰的類屬矩陣。

圖2 密集近鄰關(guān)系搜索示意圖

式(7)、式(8)是一個放松約束條件的二次規(guī)劃NP難問題，根據(jù)文獻[9]，對于滿足公式(3)的向量解 ,通過以下步驟進行迭代，獲得最優(yōu)解

(4)

公式表明，每個迭代過程只更新一組節(jié)點對(xi,xj),i≠j。常數(shù)α由下式計算得到

(5)

3 計算目標位置

θn(δl,δs)}

(6)

式中θr(δl,δs)和θc(δl,δs)分別代表目標中心lc+δl和尺度為s+δs確定的目標框里面，匹配候選部件和非匹配候選部件的像素個數(shù)；θn(δl,δs)表示背景部件中的像素個數(shù)。振蕩項{δl,δs}設(shè)置為1.1節(jié)中定義的近鄰距離ε=1.5W·H/N。系數(shù)ω代表了匹配候選部件的可信度。

4 實驗結(jié)果與分析

基于文獻[15]，本文使用了近年來更流行的精度曲線，即給出跟蹤成功率分別與位置誤差和目標覆蓋率大小的關(guān)系。圖3(a)表示成功率評價曲線(successplots)，曲線下面積作為跟蹤器排序分數(shù);圖3(b)表示精度評價曲線(precisionplots)，以像素20為閾值給出排序分數(shù)。從2組精度曲線和排序分數(shù)可以看出，本文提出的算法相比其他8種跟蹤器具有更好的效果。

圖3 實驗結(jié)果評價曲線

圖4給出了幾種序列各跟蹤方法的跟蹤效果?；诓考母櫰鱗3,4,14]相比基于整體目標的跟蹤器[2,12,13]在形變目標跟蹤上效果更好。這是由于基于部件的跟蹤器專注于局部部件表象而非全局目標表象，對目標結(jié)構(gòu)變化不敏感。而本文算法相比于其它基于部件的跟蹤器[3,4,14]具有更精確的效果，是由于采用密集近鄰搜索算法將跟蹤過程中出現(xiàn)的異常值有效地舍去，選擇更可信的密集近鄰，成功地避免了形變或者遮擋問題引入的背景噪聲，捕捉丟失的前景信息。

圖4 跟蹤結(jié)果

本文提出的跟蹤器能在這類序列中表現(xiàn)出比較好的性能，得益于基于MRF的分割模型在目標搜索區(qū)域內(nèi)提供了較為可靠的候選目標部件。另外更高精度的部件匹配算法也抵御了不規(guī)則運動的不利影響。

5 結(jié)束語

實驗在8個視頻序列上比較了最近的8種跟蹤算法，證明了本文提出算法的有效性。未來可考慮引入高階類屬圖建模，提高抗噪性；將目標整體表象和部件表象相結(jié)合建立更魯棒的表象特征，提升跟蹤效果。

[1]ZhangK,ZhangL,YangMH.Real-timecompressivetra-cking[C]∥EuropeanConferenceonComputerVision,Florence,2012:864-877.

[2]LiuH,YangX,LateckiLJ,etal.Denseneighborhoodsonaffinitygraph[J].InternationalJournalofComputerVision,2012,98(1):65-82.

[3]ZhongW,LuH,YangMH.Robustobjecttrackingviasparsity-basedcollaborativemodel[C]∥ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition,Rhode,2012:1838-1845.

[4]LimJ,RossDA,LinRS,etal.Incrementallearningforvisualtracking[C]∥AdvancesinNeuralInformationProcessingSystems,Vancouver,2004:793-800.

[5]HareS,SaffariA,TorrPHS.Struck:Structuredoutputtrackingwithkernels[C]∥InternationalConferenceonComputerVision,IEEETransPatternAnalMachIntell,2011:263-270.

[6]WangS,LuH,YangF,etal.Superpixeltracking[C]∥Procee-dingsoftheIEEEInternationalConferenceonComputerVision,Barcelona,2011:1323-1330.

[7]YaoR,ShiQ,ShenC,etal.Part-basedvisualtrackingwithonlinelatentstructurallearning[C]∥ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition,Oregon,2013:2363-2370.

[8]CaiZ,WenL,LeiZ,etal.Robustdeformableandoccludedobjecttrackingwithdynamicgraph[J].IEEETransactionsonImageProcessing,2014,23(12):5497-5509.

[9]WenL,DuD,LeiZ,etal.JOTS:Jointonlinetrackingandsegmentation[C]∥IEEEConferenceonComputerVisionandPatternRecognition,Boston,2015:2226-2234.

[10]ChangJ,FisherJW.Topology-constrainedlayeredtrackingwithlatentflow[C]∥IEEEInternationalConferenceonComputerVision,Sydney,2013:161-168.

[11]BoykovY,KolmogorovV.Anexperimentalcomparisonofmin-cut/max-flowalgorithmsforenergyminimizationinvision[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2001,11(26):1124-1137.

[12]ChoM,SunJ,DuchenneO,etal.Findingmatchesinahaystack:Amax-poolingstrategyforgraphmatchinginthepresenceofoutliers[C]∥ProceedingsoftheComputerVisionandPatternRecognition,Columbus,2014:2091-2098.

[13]ZhangK,ZhangL,LiuQ,etal.Fastvisualtrackingviadensespatio-temporalcontextlearning[C]∥EuropeanConferenceonComputerVision,Zurich,2014:127-141.

[14]AdamA,RivlinE,ShimshoniI.Robustfragments-basedtrackingusingtheintegralhistogram[C]∥ProceedingsofComputerVisionandPatternRecognition,NewYork,2006:798-805.

[15]CehovinL,KristanM,LeonardisA.Robustvisualtrackingusinganadaptivecoupled-layervisualmodel[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2013,35(4):941-953.

[16]WuY,LimJ,YangMH.Onlineobjecttracking:Abench-mark[C]∥IEEEConferenceonComputerVisionandPatternRecognition,2013:2411-2418.

Research on visual tracking algorithm based on affinity graph dense neighborhoods searching*

WANG Zhi-dan, JIANG Jian-guo, QI Mei-bin

(School of Computer and Information,Hefei University of Technology,Hefei 230009,China)

A visual tracking algorithm based on dense neighborhoods searching on affinity graph,which can be applied in the scenes with large deformations and severe occlusions.Object parts are extracted based on image segmentation model of Markov random field,affinity graph matrix is built by searching dense neighborhoods in affinity graph matrix, confidence map of target location is obtained by matching relationship to determine location of target tracking.Experimental results show that the proposed algorithm is better compared to other state-of-the-art methods.

visual tracking; affinity graph; dense neighborhoods searching; confidence map

10.13873/J.1000—9787(2017)04—0146—04

2016—04—14

國家自然科學(xué)基金資助項目(61371155)；安徽省科技攻關(guān)資助項目(1301b042023)

TP 751

A

1000—9787(2017)04—0146—04

王治丹(1989-),女，碩士，研究方向為數(shù)字圖像處理、目標檢測以及智能視頻監(jiān)控系統(tǒng)。