类属图密集近邻搜索的视觉跟踪算法研究*

王治丹， 蒋建国， 齐美彬

(合肥工业大学 计算机与信息学院，安徽 合肥 230009)

类属图密集近邻搜索的视觉跟踪算法研究*

王治丹， 蒋建国， 齐美彬

(合肥工业大学 计算机与信息学院，安徽 合肥 230009)

提出一种基于密集近邻搜索的视觉跟踪算法，能够有效应对目标跟踪过程中出现的形变和遮挡问题。基于马尔科夫随机场建立图像分割模型，提取出目标部件，建立目标部件的类属图矩阵；通过搜索类属图矩阵中的密集近邻，得到相邻帧之间目标部件的匹配关系；通过匹配关系得到跟踪目标位置概率图，确定目标跟踪位置。实验结果表明：本文提出的方法相比其他同类方法效果更好。

视觉跟踪； 类属图； 密集近邻搜索； 置信图

0 引 言

视觉跟踪作为计算机视觉领域的基础问题，在各方面都取得了重要应用，比如视频监控等。之前,研究者设计出了各种算法并取得重要进展，但是由于目标在跟踪过程中出现形变、面临遮挡等情况，对目标的跟踪仍然是一项很棘手的工作。

早期的大多数跟踪算法是基于目标整体模型建立特征表达来描述目标的表象变化，比如稀疏表示[1]以及子空间学习[2]等。由于存在目标形变和遮挡，即使将特征表达改进得相对全面和复杂，很多固定尺度的跟踪器仍然会跟踪丢失。为克服这一问题，研究者提出了基于部件的跟踪器[3～5]，可以更灵活地处理目标形变和尺度变化，并且有效检测出遮挡的发生。文献[3]基于简单线性迭代聚类(simple linear iterative clustering,SLIC)算法将目标搜索区域分割成超像素集合，通过建立表象模型来区分前景和背景区域，抵御因形变和遮挡引入的背景噪声。但是由于较少考虑目标部件之间的结构信息，当前景和背景表象相似时容易混淆目标。在此基础上，文献[4]考虑目标部件间的结构信息，基于频谱分析算法将跟踪问题转化为图匹配问题。相似地，文献[5]利用目标结构信息，训练了一个在线的结构化隐式支持向量机(support vector machine,SVM)模型来预测目标中各部件的位置。但是由于假设目标尺度不变，当目标发生形变的时候会出现跟踪困难。另外，文献[9,10]借助了图像分割技术来区分目标和背景区域，较精确地给出了跟踪目标的轮廓，提升跟踪效果。

考虑到跟踪目标可能会出现形变和面临遮挡，本文提出了基于类属图密集近邻搜索的跟踪(dense neighborhoods-based tracker, DNT)方法。首先，在当前帧的目标搜索区域内，根据图像分割技术提取出目标部件，并建立目标部件的类属图矩阵。然后，通过搜索类属图矩阵的密集近邻，得到相邻帧之间的目标部件匹配关系。最后，通过目标部件及其匹配关系得到目标位置的概率图(confidence map)，通过采样确定目标的最优位置。

1 目标类属图

1.1 建立类属图

首先，在当前帧的目标搜索区域内，基于马尔科夫随机场(Markov random field, MRF)建立图像分割模型，根据图割(graph cut)算法[8]技术提取出目标部件。初始化第一帧目标部件集合为P，当前帧提取出的候选目标部件集合为Q。根据两帧目标部件集合，建立目标部件的类属图(affinity graph)：G=(V,E)，其中包括:1)图节点v∈V，代表相邻部件匹配对；2)图边e∈E,代表匹配对间的几何关系。定义如下

(1)

1.2 类属图矩阵

图1 类属图矩阵含义

2 密集近邻搜索

(2)

(3)

式中xo为起始目标节点分数，k为密集近邻内节点的个数，初始化为一个很小的值，在搜索密集近邻的过程中不断增大，节点概率加权和最大时得到最优解。

图2为密集近邻关系搜索示意图，左侧为类属图，实心点为相对可信的匹配对，空心点为异常匹配对。如果k=3，根据关联矩阵A，3NN(o)={a,c,q}[9]，而通过密集近邻搜索得到3DN(o)={b,c,q}的关联值加权和最大，子矩阵B为该密集近邻的类属矩阵。

图2 密集近邻关系搜索示意图

式(7)、式(8)是一个放松约束条件的二次规划NP难问题，根据文献[9]，对于满足公式(3)的向量解 ,通过以下步骤进行迭代，获得最优解

(4)

公式表明，每个迭代过程只更新一组节点对(xi,xj),i≠j。常数α由下式计算得到

(5)

3 计算目标位置

θn(δl,δs)}

(6)

式中θr(δl,δs)和θc(δl,δs)分别代表目标中心lc+δl和尺度为s+δs确定的目标框里面，匹配候选部件和非匹配候选部件的像素个数；θn(δl,δs)表示背景部件中的像素个数。振荡项{δl,δs}设置为1.1节中定义的近邻距离ε=1.5W·H/N。系数ω代表了匹配候选部件的可信度。

4 实验结果与分析

基于文献[15]，本文使用了近年来更流行的精度曲线，即给出跟踪成功率分别与位置误差和目标覆盖率大小的关系。图3(a)表示成功率评价曲线(successplots)，曲线下面积作为跟踪器排序分数;图3(b)表示精度评价曲线(precisionplots)，以像素20为阈值给出排序分数。从2组精度曲线和排序分数可以看出，本文提出的算法相比其他8种跟踪器具有更好的效果。

图3 实验结果评价曲线

图4给出了几种序列各跟踪方法的跟踪效果。基于部件的跟踪器[3,4,14]相比基于整体目标的跟踪器[2,12,13]在形变目标跟踪上效果更好。这是由于基于部件的跟踪器专注于局部部件表象而非全局目标表象，对目标结构变化不敏感。而本文算法相比于其它基于部件的跟踪器[3,4,14]具有更精确的效果，是由于采用密集近邻搜索算法将跟踪过程中出现的异常值有效地舍去，选择更可信的密集近邻，成功地避免了形变或者遮挡问题引入的背景噪声，捕捉丢失的前景信息。

图4 跟踪结果

本文提出的跟踪器能在这类序列中表现出比较好的性能，得益于基于MRF的分割模型在目标搜索区域内提供了较为可靠的候选目标部件。另外更高精度的部件匹配算法也抵御了不规则运动的不利影响。

5 结束语

实验在8个视频序列上比较了最近的8种跟踪算法，证明了本文提出算法的有效性。未来可考虑引入高阶类属图建模，提高抗噪性；将目标整体表象和部件表象相结合建立更鲁棒的表象特征，提升跟踪效果。

[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

国家自然科学基金资助项目(61371155)；安徽省科技攻关资助项目(1301b042023)

TP 751

A

1000—9787(2017)04—0146—04

王治丹(1989-),女，硕士，研究方向为数字图像处理、目标检测以及智能视频监控系统。