王治丹， 蔣建國， 齊美彬

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

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

王治丹， 蔣建國， 齊美彬

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

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

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

0 引 言

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

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

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

1 目標(biāo)類屬圖

1.1 建立類屬圖

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

(1)

1.2 類屬圖矩陣

圖1 類屬圖矩陣含義

2 密集近鄰搜索

(2)

(3)

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

圖2為密集近鄰關(guān)系搜索示意圖，左側(cè)為類屬圖，實(shí)心點(diǎn)為相對可信的匹配對，空心點(diǎn)為異常匹配對。如果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ù)文獻(xiàn)[9]，對于滿足公式(3)的向量解 ,通過以下步驟進(jìn)行迭代，獲得最優(yōu)解

(4)

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

(5)

3 計算目標(biāo)位置

θn(δl,δs)}

(6)

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖3 實(shí)驗(yàn)結(jié)果評價曲線

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

圖4 跟蹤結(jié)果

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

5 結(jié)束語

實(shí)驗(yàn)在8個視頻序列上比較了最近的8種跟蹤算法，證明了本文提出算法的有效性。未來可考慮引入高階類屬圖建模，提高抗噪性；將目標(biāo)整體表象和部件表象相結(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-),女，碩士，研究方向?yàn)閿?shù)字圖像處理、目標(biāo)檢測以及智能視頻監(jiān)控系統(tǒng)。