混合特征匹配结合Viterbi数据关联的目标跟踪算法

徐燕华，李　荣，王华君，徐平平（.无锡太湖学院，江苏 无锡　4064；.东南大学 信息科学与工程学院，江苏 南京　89）

混合特征匹配结合Viterbi数据关联的目标跟踪算法

徐燕华1，李荣1，王华君1，徐平平2
（1.无锡太湖学院，江苏 无锡214064；2.东南大学 信息科学与工程学院，江苏 南京211189）

传统跟踪算法在视频分辨率低、帧图像模糊或噪声较多时跟踪效果较差。针对此情况，提出一种混合特征匹配结合Viterbi数据关联的目标跟踪算法。首先，采用直方图反向投影技术对双局部阈值图像中的目标边缘进行有效分割，克服了低对比度问题；然后，将邻域特征、区域特征、运动方向特征和直方图特征作为目标表征特征，建立混合特征代价函数；最后，采用Viterbi数据关联计算代价总和，求得最相似目标。实验结果表明，在帧图像模糊或噪声较多的情况下，目标跟踪稳定且有效，单目标跟踪准确率为0.89，多目标跟踪精度达0.975，召回率达0.920，优于其他几种同类跟踪算法。

分割跟踪；混合特征匹配；双局部阈值；直方图反向投影；Viterbi数据关联

0引　言

目标跟踪在军事、安防、交通等领域应用极其广泛［1-2］，目前是模式识别、图像处理等学科领域的热门研究课题。根据跟踪目标的数量，目标跟踪可分为单目标跟踪和多目标跟踪，两者的处理方式有很大不同。多目标跟踪涉及到目标特征相似或互斥情况，有时还需解决目标遮挡、重叠和分类问题［3-5］。单目标跟踪仅需选取目标单个特征即可［6-7］。

传统跟踪算法在视频分辨率低，帧图像模糊或噪声较多时跟踪效果较差。针对此情况，本文选择邻域特征、区域特征、运动方向特征和直方图特征等多个目标特征进行跟踪，并给出了联合特征代价函数以及数据关联运算方法。

1　相关工作

近年来，许多学者对单目标跟踪［4-7］和多目标跟踪［8-10］进行了研究。

文献［7］提出了TLD（Tracking-Learning-Detecting）算法。算法实现目标检测和跟踪同时进行，TLD算法使用NP学习方法检测和纠正跟踪过程中的错误，但NP不适合联合学习，在多目标情况下无法使用该算法。

文献［8］提出了一种基于视频的多目标跟踪算法。算法使用码本模型检测前景，提取每一帧的头部和脚部特征，根据几何约束关系计算目标高度，具有一定精度和鲁棒性。但码本模型仅适用于简单场景中的前景提取。

文献［9］提出标记点处理方法（Marked Point Processes，MPP）。算法能获取所有未知目标的后验概率，得出时空信息；并能识别和了解特定事件变化的外力。

针对复杂、低信噪比背景的红外小目标跟踪问题，文献［10］提出用阈值分割和形态学滤波检测目标，采用邻域轨迹和Kalman滤波跟踪目标，避免了噪声干扰。但跟踪的目标数量有限，也没考虑目标遮挡消失问题。

本文提出一种新的带图像分割的多目标跟踪算法。算法将多个有用的特征用于目标匹配，并设计了总代价函数，给出了代价函数的数据关联计算方法。实验视频结果证明，本文算法能获取良好的目标跟踪效果。

2　目标分割

本文提出的自动分割算法由四个步骤组成，如图1所示。

（1）进行局部双阈值处理；

（2）利用基于直方图反向投影的方法将两个不同阈值处理生成的二值目标掩码进行有效整合；

（3）利用区域和方差阈值移除噪声和干扰目标；

（4）对分割后的目标边界进行精提取。

图1　目标自动分割流程图

2.1局部双阈值处理

Otsu算法［11］是一种常用的阈值确定算法。通过Otsu算法确定的阈值可将直方图分为两类，使合并后的类内方差最小。利用Otsu改进型方法对每个区域选取自适应阈值。对于较暗的目标，阈值的大小需接近背景，位置的大小值为：

式中：τ是Otsu方法获取的阈值；μL（τ）表示直方图中经过阈值τ分类后获取较小的一类；p为偏移系数。利用式（1），通过设置不同大小的 p可以获取两个阈值，即τlow=τ-plow（τ-μL（τ）作为低阈值，τhigh=τ-phigh（τ-μL（τ））作为高阈值。通过这两个阈值处理视频帧中的局部区域可获取两个相应的目标掩码Mlow和Mhigh，如文献［12-13］所述，利用一个3×3的中值滤波算子处理两个二值目标掩码。

2.2直方图反向投影

由于两个目标掩码包含有不同数量的背景像素，所以通过两个目标掩码中像素分布的比较和聚合对分割边界进行精提取［14］。

首先，根据目标掩码的Mlow和Mhigh分别计算出两个灰度级别的直方图Hlow（r）和Hhigh（r）。任何灰度大小r的比例直方图定义如下所示：

其次，将比例直方图反向投影到视频帧域，即BP（x，y）=HR［I（x，y）］，1≤x≤W，1≤y≤H，其中，I（x，y）表示（x，y）所处位置的像素灰度值大小。对比例直方图HR（r）的反向投影进行阈值处理，二值分割掩码B（x，y）定义如下：

式中：θBP为范围在0～1之间的一个阈值。

2.3区域和方差阈值处理

本文算法既利用直方图对掩码进行精确分割，还通过目标的区域和目标内像素值的方差去除区域内大于阈值上限或小于阈值下限的值。对于第k个分割目标Ok内的每个像素点（x，y），通过式（4）对其在前景掩码中对应的像素进行修改。

使用每个分割目标内像素的方差对候选目标进行检测。因前景目标拥有比背景或干扰目标更多的纹理特征，导致分割目标的方差可能更大。每个目标像素的方差为：

式中：Īk表示第k个目标内像素的平均值。给定方差，利用式（6）对该目标的前景掩码进行阈值处理。

2.4形态学处理

通过以上算法提取的前景目标，经常会出现一些噪声。例如，直方图反向投影在对目标边界进行精提取时会生成斑点。本文进一步利用形态学操作精确提取分割边界。首先利用结构元素对目标掩码做开形态学操作；然后进行闭合操作。平滑目标边界不会影响目标外形的细节信息［11］。

3　混合特征匹配跟踪

对目标进行分割后，利用混合特征进行快速匹配。本文所提跟踪算法利用目标整个寿命的时间相关性，而不仅仅是两个视频帧间的相关性。本文跟踪系统流程图如图2所示。

图2　本文的跟踪系统

3.1混合特征匹配

混合特征匹配利用各种有用特征测量目标间的相似性。对于在时间t和t-1处的目标本文对四个线索进行如下调查。

（2）区域线索：为了消除区域间的视差问题，通过立体三角形计算目标的深度信息，对目标区域进行相应的归一化处理，使得多目标相对立体相机具有相同的距离。两个连续帧中关联目标间区域的差异十分微小，利用连接组件算法计算目标区域，用A（·）表示。时刻t的目标Otj和时刻t-1的目标间区域的视差用表示。

根据运动趋势或者运动方向可以选取预定义的参考向量。

（4）直方图：本文采用32灰度级直方图间的距离矩阵。

在本文所有视频数据的每帧图像上通过收集所有混合特征匹配候选者的特征值，系统计算出标准偏差。

匹配代价定义如式（9）所示：

式中｛σ｝表示特征的标准偏差。

3.2Viterbi数据关联

在本文提出的Viterbi数据关联［15］系统中，所利用的立体信息是指匹配目标的立体信息，即视频帧中相同的目标作为一个目标进行观察以执行跟踪，为此，需要计算混合特征匹配代价的总和，即其基本思想如图3所示，框架是一种有向图，每个节点在其寿命中都含有单独的框架、开始节点（三角形）和结束节点（正方形）。彩色箭头标记每个框架中的最优路径。从图3可以看出，节点被划分为有序子集接相邻子集中任意的配对节点。节点表示一帧中存在的目标，将每个边界设定为cij（t）。一条路径（一系列的边）的总代价为：

其中：

图3　目标跟踪有向图形式

3.2.1单目标跟踪

对于单目标跟踪，本文利用文献［15］寻找最小代价。利用零代价和初始化一个节点的观察值，根据式（9）获取每个节点nj（t），j=1，2，…，||N（t）。设定一个节点nj（t）的前身和累积代价分别为：

目标一旦离开视频边界，即到达框架的最后一级，则执行回溯。在最后一级中，以代价最小的节点开始执行回溯，根据事先在每一级中存储的数据遍历第一级以发现最优路径P*=argminPC（P）。

3.2.2多目标跟踪

每个目标的起始帧可能不同，每个节点处的前期和最小代价也可能不同。本文为每个目标创建一个单独的框架进行跟踪，如图3所示。根据式（11）和式（12），利用所有观测值分别对每个目标进行数据关联，其中大多数错误警告都是在分割后处理阶段产生的，因此分割区域通常较小。对观测的位置和区域进行测试以将新目标和错误警告区分开来。因此，仅当目标的预期位置距离帧边界很近时才设定这个目标的跟踪过程结束，这也阻止了因暂时遮挡而引起的目标删除。其实就是为每个目标设置存活时间。图3中给出了目标跟踪总体框架，图中节点在任何阶段都允许包含多个路径。

数据关联中需要更新目标的位置和速度，设定帧t-1时刻第k个跟踪目标的位置和速度分别为 xkt-1和数据关联后，选取代价最小的观测节点更新位置和速度，即：分别表示代价最小观察节点的位置和速度，α表示更新比例。每一帧的数据关联及总结算法如下所示：

4　实验结果与分析

4.1参数说明及度量函数

视频帧的尺寸为1 280×768像素，帧率为8 f/s。本文利用形态学做开操作时结构元素设定为7×7像素大小的模板（7×7为一个经验值），表1为根据经验设定的形态学操作模板中的参数大小。

为了对多目标跟踪的精度进行评估，本文设计了两种类型错误：假阳性（FP）和假阴性（FN），两种类型错误的权重相同。本文规定了真阳性（TP）的数量并提供了运动目标总的个数。运动目标总的个数（TO）是所有图像帧中目标的总和。主要跟踪（MT）和主要丢失（ML）的分数进而测量有多少跟踪成功或丢失，算法的精度分别定义为：

表1　实验中所使用的参数值

4.2单目标跟踪效果分析

图4所示为一段比较模糊的足球比赛视频序列帧。从图4可以看出，比赛双方运动员中的一方穿着相同，很难直接辨识。利用本文算法对图4单目标进行跟踪，并将实验结果与文献［4］提出的粒子群优化算法（PSO-PF）和文献［5］提出的局部背景加权算法（CBWH）进行比较。图4（a）所示为本文算法结果，从图中可以看出，选择的运动员基本定位完整。即使有很多类似特征的运动员，因采用了目标运动方向特征和时间信息，目标也能准确定位，图4（b）和图4（c）分别是CBWH和PSO-PF跟踪结果，可以看出CBWH在第三帧已偏离目标，PSO-PF在第二帧已偏离目标。比较三种算法，本文算法精确性能明显优于CBWH和PSO-PF两种算法。

此外，测试了CBWH算法［5］和TLD算法［7］所使用的部分视频，表2为各算法的跟踪准确率比较。跟踪准确率是指正确分割锁定目标的时间比上总时间。总体来说，本文提出的单目标跟踪算法跟踪准确率高于其他两种算法。

4.3多目标跟踪效果分析

图5为一段分辨率比较低的鱼类视频序列帧。从图中可以看出，帧背景比较黑暗，图像中目标姿态不断变化。利用本文算法对图5多目标进行跟踪，并将实验结果与文献［9］提出的标记点处理算法MPP和文献［10］提出的多目标Kalman跟踪器进行比较。图5是本文算法与MPP和Kalman的跟踪分割结果图。图5（a）是本文算法结果，可以看出目标基本完全定位，图5（b）和图5（c）分别是MPP和Kalman跟踪结果，其中红色框是漏检的目标。从图5可以看出，本文算法漏检率明显低于MPP和Kalman算法。表3是精度和召回率比较，其中实验总体目标数目设置为90个。从表3可以看出，本文算法精度和召回率明显优于MPP和Kalman算法。

图4　单目标跟踪结果比较

表2　各算法的平均跟踪准确率

图5　多目标跟踪结果比较

表3　各算法的精度、召回率比较

5结　论

本文提出一种基于混合特征匹配的多目标分割跟踪算法，算法可用于低对比度的多目标跟踪。算法中采用的局部双阈值能克服低对比度和噪声对目标跟踪的影响，并利用直方图反向投影进行外形分割结果，利用四种特征进行目标匹配，并设计了总体代价函数以及代价函数的数据关联计算。实验结果表明，本文算法取得了较高的跟踪成功率，具有很好的实际应用价值。

下一步的研究内容是对于不同的场景，如何自适应地选择有效特征进行目标匹配。

［1］王健.基于目标跟踪的交通违停事件检测的研究［D］.合肥：中国科学技术大学，2011.

［2］史志刚.视频序列中运动目标检测与跟踪技术研究［D］.西安：西安电子科技大学，2014.

［3］LI Z，LI G，TAN J，et al.Low observable moving target tracking based on modified PDA-AI［J］.Journal of infrared millimeter& terahertz waves，2010，31（10）：1245-1256.

［4］陈志敏，薄煜明，吴盘龙，等.基于自适应粒子群优化的新型粒子滤波在目标跟踪中的应用［J］.控制与决策，2013，28（2）：859-864.

［5］NING J，ZHANG L，ZHANG D，et al.Robust mean-shift tracking with corrected background-weighted histogram［J］.IET computer vision，2010，6（1）：62-69.

［6］COMANCIU D，VISVANATHAN R，MEER P.Kernel-based object tracking［J］.IEEE transactions on pattern analysis&machine intelligence，2003，25（5）：564-575.

［7］KALAL Z，MIKOLAJCZYK K，MATAS J.Tracking-learningdetection［J］.IEEE transactions on pattern analysis and machine intelligence，2012，34（7）：1409-1422.

［8］姜明新，王培昌，王洪玉.基于视频多目标跟踪的高度测量算法［J］.电子学报，2015，43（3）：591-596.

［9］IBE O C.Markov processes for stochastic modeling［M］.US：Chapman&Hall，1997.

［10］罗寰，于雷，廖俊，等.复杂背景下红外弱小多目标跟踪系统［J］.光学学报，2009，29（6）：1536-1541.

［11］李雨朋.基于Otsu算法的图像分割研究［D］.镇江：江苏大学，2014.

［12］ZHAO Y，TAUBIN G.Real-time median filtering for embedded smart cameras［C］//Proceedings of 2006 IEEE International Conference on Computer Vision Systems.［S.l.］：IEEE，2006：55-57.

［13］CHANDRA E，KANAGALAKSHMI K.Noise suppression scheme using median filter in gray and binary images［J］.International journal of computer applications，2011，26（1）：49-57.

［14］KIM C，HWANG J N.Video object extraction for object-oriented applications［J］.Journal of VLSI signal processing systems for signal，image and video technology，2001，29（1/2）：7-21.

［15］VITERBI A J.A personal history of the Viterbi algorithm［J］. IEEE signal processing magazine，2006，23（4）：120-142.

［16］MUSICKI D，SONG T L，LEE H H，et al.Correlated Dopplerassisted target tracking in clutter［J］.IET radar sonar&navigation，2013，7（1）：94-100.

［17］柳培忠，阮晓虎，田震，等.一种基于多特征融合的视频目标跟踪方法［J］.智能系统学报，2014，17（3）：1-6.

Target tracking algorithm combining hybrid feature matching with Viterbi data association

XU Yanhua1，LI Rong1，WANG Huajun1，XU Pingping2
（1.Taihu University of Wuxi，Wuxi 214064，China；2.School of Information Science and Engineering，Southeast University，Nanjing 211189，China）

The tracking effect of the traditional tracking algorithms is poor due to the low video resolution，blurred frame image or heavy noise.To solve the above problems，a target tracking algorithm combining hybrid feature matching with Viterbi data association is proposed.The histogram back-projection technology is used to effectively segment the target edge in local bithreshold image to overcome the problem of low contrast.The neighborhood feature，regional feature，movement direction feature and histogram feature are taken as the target characterization features to establish the cost function of hybrid feature.The Viterbi data association is used to calculate the sum of cost function to obtain the most similar target.The experimental results show that，in the condition of blurred frame image or heavy noise，the proposed algorithm has stable and effective target tracking，the accuracy rate of single target tracking is 0.89，the accuracy rate of multi-target tracking is 0.975，the recall rate is 0.920，and the algorithm is superior to other similar tracking algorithms.

segmentation tracking；hybrid feature matching；local bi-threshold；histogram back projection；Viterbi data association

TN911.73-34；TP391

A

1004-373X（2016）17-0001-05

10.16652/j.issn.1004-373x.2016.17.001

2015-11-16

国家自然科学基金资助项目（61375028）；江苏省高校自然科学研究项目（14KJD460004）

徐燕华（1979—），女，江苏无锡人，硕士，讲师。研究领域为目标跟踪、图像处理等。李荣（1978—），女，江苏淮安人，硕士，讲师。研究领域为目标跟踪、图像处理等。王华君（1979—），男，江苏宜兴人，硕士，讲师。研究领域为目标跟踪、图像处理等。徐平平（1957—），女，江苏南京人，博士，教授，博士生导师。 研究领域为图像处理、目标跟踪等。