基于局部背景加权和能量约束的多目标检测与跟踪算法

陈家红

（金陵科技学院计算机工程学院，南京211169）

基于局部背景加权和能量约束的多目标检测与跟踪算法

陈家红

（金陵科技学院计算机工程学院，南京211169）

针对标记点处理方法用于多目标跟踪时效果不佳的问题，在标记点方法的基础上，提出一种多目标联合检测跟踪算法。改进的帧间差法用于目标的初步确定，通过局部背景加权进一步确定其与多个目标的标记。考虑动态模型的轨迹一致性问题，对动态目标、长时间跟踪和目标互斥相似等问题进行研究。针对非凸性的能量函数采用可逆跳转马尔可夫链蒙特卡洛进行优化。实验结果表明，在有高斯噪声情况下，与其他跟踪算法相比，该算法的检测和跟踪相似度最高，在卫星图像序列和自采集视频中的精度和召回率也最高，整体性能较优。

多目标跟踪；局部背景加权；能量约束；非凸性；可逆跳转马尔可夫链蒙特卡洛

1 概述

目标跟踪在交通、安防、无人机、无线传感器网络等领域应用非常广泛［1-3］，是模式识别、机器视觉等许多交叉学科的热门研究课题。从某种意义上说，可以将目标跟踪定义为图像平面中目标轨迹的评估问题［4］。因此，跟踪器在图像序列的不同图像帧中为目标设置一致标签，还可以提供目标的运动方向、外形或尺寸信息［5］，在目标跟踪中用轨迹评估具有重要意义。目标跟踪按跟踪目标的数量，可以分为单目标跟踪和多目标跟踪，两者虽然有相似之处，但多目标要比单目标复杂得多，要考虑的问题多而复杂，如多目标的重叠、相似区别和排序等问题［6］。本文给出一种多目标跟踪算法，就动态目标、长时间跟踪和目标互斥相似等问题进行研究，提出背景加权和能量约束的多目标跟踪算法。

2 相关研究

关于目标跟踪已经有很多学者对其进行大量研究，本节按单目标［7-9］和多目标跟踪［10-13］进行描述，重要讨论利用序列方法［10-11］和标记点方法［12-13］的多目标跟踪。

文献［7］针对传统的Meanshift跟踪算法在跟踪时的不稳定问题，提出一种改进算法，意图削弱目标模型中的背景特征对目标跟踪的影响，即局部背景加权BWH，通过局部背景模型筛选目标与候选模型的显著特征。文献［8］的设计思想较好，但实验效果并不好。文献［8］用理论和实验证明了文献［7］的BWH并没有起作用，算法最终退化为传统的Meanshift，并对其进行纠正，提出了CBWH算法，真正实现了文献［7］期望的效果。但这类算法依然是以Meanshift为基础，在近似的颜色区域目标经常发生漂移。

文献［9］是著名的TLD（Tracking-Learning-Detecting）算法。在目标跟踪领域中影响非常大，这可能是由于非常好的效果和代码分享，TLD将跟踪和检测同时进行，同时利用N-P专家的学习方法对跟踪和检测出现的错误样本和正确样本同时进行分类，纠正跟踪和检测过程中的错误，而TLD算法是一种单目标跟踪，多目标的学习很困难。文献［9］解决了这个问题，但并未见著于学术，而是见著于他成立的公司中。

文献［10］是一种改进的多假设跟踪器（Multi-Hypothesis Tracker，MHT），数据校准后进行串行合并和点迹合成。属于多目标跟踪领域中常见的技术，该算法的主要缺点在于不能根据新数据修改过去的结果。但是，实时跟踪并不总是一个不可获取的约束条件，比如线下视频处理或信息检索等应用程序就不存在这些限制条件。文献［11］提出了MCMC数据关联方法，利用这种方法可以对一组离散度检测信号进行分区用以跟踪。为了检索每个分区，假设目标和检测是一对一的映射关系。但是，没有并没有对其进行细致的研究。

标记点处理方法（Marked Point Processes，MPP）［12］已经成功地应用于高分辨率遥感光学图像以检测目标，文献［13］中所提出的模型用以获取所有未知目标的后验概率，得出时空信息。因此，这种模型的主要目的在于识别和了解特定事件变化的外力，对能量中的特定因素进行优化会使得处理过程相互依赖。

本文提出一种新的MPP算法，该算法适用于多目标跟踪问题，并且将局部背景加权加入其中用于目标标记，能量约束用于多目标跟踪。

3 多目标检测

多目标的检测是目标跟踪的重要环节，本节介绍的多目标检测是由改进的帧间差法进行快速目标确定，用颜色直方图向量和背景加权对目标进行标记。

3.1 改进的帧间差法目标检测

通过帧差法［14］找到运动目标的可能位置，不同于一般的帧间差法，只使用相邻2帧，本文使用前后3帧，三帧差法可以获得更多的像素间的信息，两帧差法只考虑第k帧与前一帧或后一帧的关系，只进行一次差分运算，三帧差法考虑前后2帧关系，进行了2次差分运算，三帧差法可以获得更多像素灰度信息关系，另外三帧差法也适合之后的相位与运算。在运算量方面，如果不考虑后续操作的不同，三帧差法增加了h×w次减法运算（h，w分别为图像的高度和宽度）。相位与运算和简单的阈值二值化进行目标确定。在每个像素位置上，计算随着时间变化亮度值的平均值，并用pm表示。对于每个视频帧f，计算f中所有的像素亮度值pf与参考帧之间的差值，以及局部的平均差值pm。最后，仅保留那些差值大于预设定阈值的像素点作为前景：

阈值处理之后进行二值处理，然后确定目标。图1为改进的帧间差法的流程图。

图1 使用帧间差法的目标确定流程

3.2 目标标记

背景在目标定位中起着重要作用，对于2个相似的目标，背景是区分不同目标的重要手段，经验表明将目标背景信息融入到目标定位中非常必要。在文献［8］的CBWH算法中，目标局部背景模型的权重计算公式如下：

具体定义可以参考文献［7-8］，本文并没有将完整的CBWH算法引入到目标检测中，只是运用了其中直方图向量表征及其背景加权以对多目标进行划分和标记。由于CBWH是BWH的改正版本（CBWH的确用严格的理论和实验证明了BWH的错误，不过BWH的背景加权思想一直广为使用［8］）。而它们均是基于均值漂移的方法，即M eanshift方法，均是基于单目标跟踪，本文属于多目标跟踪，并不是基于Meanshift，只是将CBWH的背景加权运用于多目标标记，突出背景的因素。

4 多目标跟踪

使用能量约束进行增强跟踪的条件约束，这些约束条件来自于实际场景中的目标约束。

4.1 动态模型

跟踪的定义属性（与每帧中进行独立的检测相反）即为：在大多数情况下目标轨迹是平滑的，运动模型表示为dgn，本文创建一个能量项激励目标遵循给定的运动模型，其约束为一个目标u在时刻k存在的情况，约束情况可以改写为：

其中，dyn0表示阈值，这个阈值描述目标偏离运动模型的程度，且目标仍然可以获取。

能量项遵循动态模型，即所有目标的总和：

这一项有助于目标的创建，目标检测过程受到削弱，但是动态模型增强了目标的存在性。

4.2 标签一致性问题

为了对不同轨迹进行区分，在每个目标上标记一个标签。标签用3.2节的方法进行标注，可以看成是一个轨迹的鉴别符号，不同的标签表示不同的轨迹。因此，在数据集合中标签的数量与轨迹的数量要保持接近。理想情况下，大量的目标u分散在整个图像序列中，目标的数量应该远小于标签的数量。本文利用labels（X）=Uu∈Xl（u）表示在配置X中所构建的标签集合，其中l（u）表示目标u的标签。

其中，|labels（X）|表示集合的基数。

根据运动模型设计所用的标签，给定的目标u集中在位置pos（u）=（ch（u），cw（u）），本文在相邻帧上寻找目标，相邻帧之间的关系满足运动模型。计算目标u与其他目标之间的距离，并将计算获取的距离与距离阈值进行比较，如果计算获取的距离小于阈值，那么将目标u的标签设置为先前图像帧中目标的标签；否则，为目标u分配一个新的大小在［0，L］/labels（Xt）。配置X中在任何实际运行时刻t都不允许含有2个或更多个具有相同标签的目标，这意味着分配给这些配置无限的能量。

4.3 目标互斥及能量公式

当检测和跟踪目标时，难点是在一幅给定的图像帧中处理目标碰撞和重叠。在本文模型中，如果配置中含有的目标发生重叠的部分超过给定的范围，那么将这样的配置概率置为0。目标u和v之间的重叠区域的表示如下：

针对重叠的能量项为：

跟踪阶段的能量公式为：

图2直观地展现了每个能量项如何影响输出的结果，上一行显示了每个独立项含有较高能量值的配置，下一行显示了每个独立项含有较低能量值的配置。黑色的点表示在不同时间帧目标的位置。目标上不同的颜色表示分配到不同标签。

图2 能量项不同组成成分的影响

4.4 能量公式的优化

图3 目标时空卷的双锥扩展

本文利用模拟退火寻找能量函数中的极小值。式（1）中的概率密度函数可以改写为：

其中，Tempi表示温度参数，当i趋于无穷时Tempi趋于0。如果Tempi减少对数率，那么Xi趋向于fθ，i的全局最优。

对式（10）的求解一般采用几何法迭代法，通过设计恰当的干扰内核来减少计算量。本文采用了如下的干扰内核，即出生和死亡依赖于出生图：在预处理阶段创建2种类型的图：

（1）出生图：由于目标具有的辐射值应该大于背景，因此本文利用一个简单的阈值技术在每帧图像上确定目标可能的位置，并分配给这些位置较高的内核概率；

（2）水编码：在对船只进行跟踪时，首先检测水区域，然后在水区域内进一步搜索。可以根据水区域特性的特征提取出水区域，具有低辐射值、整个区域方差较小以及相对较大的尺寸。

根据一个出生图内核确定出生和死亡，出生图内核首先选取概率pb和pd=1-pb，pb和pd=1-pb分别表示目标u添加（出生）到配置和从配置中删除（死亡）的概率。如果选取出生，那么内核根据出生图生成一个新的目标u，并且可知X′=X∪u。如果选取死亡，那么内核根据出生图在X中选取一个目标u，可知X′=Xu。将模拟退火方案中嵌入RJMCMC采样器可以获取更好的结果，但是计算量的减少比较轻微。在几次实验中，30 000次抽样，前5 000次左右用于“退火”，MCMC采样20 000多次达到稳定。

5 实验结果和分析

仿真实验在W in7操作系统，Intel酷睿双核，2.95 GHz，4 GB RAM，所用平台为Matlab2011b。

5.1 对比距离测度

对比距离测度用于不同方法检测跟踪目标的匹配程度，当感兴趣的目标在黑色背景中以明亮的形式出现，需要计算物体内部及其边界间的对比距离测度。文献［16］对对比距离测度进行介绍，其定义如下：

质量函数给较好放置的椭圆（即目标u的dB（u，Fρ（u）））一个大于阈值d0（Y）的负值，否则分配给一个正值。

5.2 合成图像实验

首先在3个合成生物图像序列上对本文提出的方法进行测试。文献［13］中已经生成了图像序列，图像序列由25幅尺寸为256×256像素的图像组成，在每帧图像上存在近乎20个目标，3个图像序列上含有不同级别的高斯噪声。图4给出了跟踪结果，采用的目标运动模型是布朗运动模型。

图4 合成生物图像序列的实验结果

图4 （a）表示在第1个图像序列（无噪声）上的跟踪结果。图4（b）表示在第1个图像序列（高斯噪声，μ=25，ρ=2.5）上的跟踪实验结果。图4（c）表示在第1个图像序列（高斯噪声μ=50，ρ=5.0）上的跟踪结果。将本文方法与粒子跟踪进行比较，表1是在3个合成图像序列上对文献［13］中的多目标跟踪器所获取的实验结果和本文提出的算法所获取的实验结果进行比较，根据最大距离为5个像素点计算2种方法配对的检测和跟踪间的相似性。这意味着如果利用文献［13］在位置c1检测出的目标与本文提出的方法在位置c2处检测的目标相同，并且此时c1与c2的对比距离测度|c1-c2|≥5，那么2个检测不匹配。

表1 3个合成图像序列上的实验结果比较

每个序列的计算时间在50 s左右。虽然与目前最先进的方法相比，本文算法性能有所减弱，但是运算时采用串行运算，如果利用并行计算策略可以大幅提高本文算法的性能。

5.3 卫星图像实验

本文主要的目标是运用本文提出的算法处理真实的数据，利用高分辨率卫星图像进行目标跟踪是遥感领域中的一个新应用［17］。在2个含有船只的图像序列上对本文算法进行测试，每个图像序列由低时间频率情况下拍摄的16幅图像组成，由于图像拍摄的角度变化，目标的外形也发生了大幅度的变化。本文将3种跟踪器实验结果进行比较：文献［12］的MPP，文献［13］的Icy和经典的卡尔曼跟踪器。

5.3.1 度量

由于许多因素的影响，对不同跟踪算法进行一个客观的比较十分困难：（1）单个跟踪识别的重要性与应用相关；（2）将跟踪器的输出分为正确和不正确十分困难，这通常需要额外的参数去评估跟踪器的正确性和精度。

为了对多目标跟踪的精度进行评估，计算了3种类型的错误：假阳性（FP），假阴性（FN）和身份转换（ID），3种类型错误的权重相同。本文对真阳性（TP）的数量进行了规定并且提供了运动目标（TO）总的个数。运动目标总的个数（TO）是所有图像帧中目标的总和，在2个连续帧上一个运动目标的位置会发生变化。另外，利用不同轨迹的总数量计算主要跟踪（MT）和主要丢失（M L）的分数，进而测量有多少真实地面轨迹被成功跟踪（至少跟踪了80%）或丢失（跟踪少于20%）（TT）。最后，确定每个算法的精度，定义为：

5.3.2 定量评价

表2显示了所有图像序列的定量结果。本文显示了4个跟踪器的实验结果：本文算法（用BW-EC表示），卡尔曼跟踪器（用K lman表示），MPP和Icy。图5显示了本文算法在2个图像序列上的实验结果。图5（a）是第1个图像序列上的跟踪过程持续到第11幅图像，图5（b）是第2个图像序列上的跟踪过程持续到第14帧。为了进行比较，在表2中列出了实验结果的数据形式。

表2 2个卫星图像序列的实验结果

图5 不同角度拍摄的卫星图像序列

图5 （a）由大小为1 840×820像素的16幅图像帧构成，整个图像帧中含有恒定的8个运动目标。利用目标证据以更好地评估出目标的位置，利用恒定的距离测度获取目标尺寸和方向的精确值。此外，在整个图像序列中对标签进行了保留。运行时间为48 s。图5（b）是由尺寸为830×730像素的16幅图像构成，在区分动态目标和静态目标时，本文的模型与经典跟踪器［12-13］相比显现出了更高的跟踪性能，这是由于本文模型获取了更好的检测结果，保持整个图像序列中的所有标签。

本文算法BW-EC的性能超过卡尔曼跟踪器，卡尔曼跟踪器性能比较低，而且需要对时间进行初始化。目标的外形在整个图像序列中都在发生变化，因此，跟踪器的精度受到较大影响。本文的跟踪器仅受到目标和目标边界间对比度的影响。因此，外形的改变不会影响本文算法的有效性。

5.4 自采集视频实验

为了更好地说明本文算法的效果，笔者自行采集一段视频进行实验。图6和图7是一段交通视频跟踪的效果图。

图6 目标车辆的初始化

图7 车辆跟踪结果

图6 是初始化的目标车辆，图7是目标出现跟踪和检测的结果。可以看出，即使类似目标出现也没有丢失目标或者发生扰乱，车运动轨迹也被成功标出。

表3为这段交通视频的实验结果，从精度和召回率看，本文算法优于其他算法。

表3 交通视频实验结果

6 结束语

本文提出一种利用局部背景加权和能量约束的多目标检测和跟踪算法，背景加权用于检测和标记。本文重点定义了一个新的直观能量约束模型，利用这个能量可以检测出图像序列中所有的目标并将其分成不同的轨迹。另外，采用著名的RJMCMC采样器对能量模型进行最优化，最后在3种不同图像序列或视频上证明了本文算法的有效性。

下一步将就以下2个方向进行研究：（1）模型对于噪声和并行执行的奇异值鲁棒性分析。（2）设计一个并行执行的RJMCMC采样器，这种执行方式将会显著减少采样器的计算时间。

［1］ 丁业兵，赵 峰，郝诗海.多特征带宽自适应Mean Shift目标跟踪算法［J］.计算机工程，2013，39（2）：197-201.

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

［3］ 刘淑英.无线传感器网络中改进的多目标定位和跟踪算法［J］.计算机工程，2015，41（4）：7-13.

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

［5］ M uŝicki D，Song Taek-Lyul，Lee H H，et al.Correlated Doppler-assisted Target Tracking in Clutter［J］.IET Radar Sonar&Navigation，2013，7（1）：94-100.

［6］ 才 盛.多目标监控场景下的检测和跟踪技术研究［D］.厦门：厦门大学，2014.

［7］ Comanciu D，Visvanathan R，Meer P.Kernel-based Object Tracking［J］.IEEE Transactions on Pattern Analysis&Machine Intelligence，2003，40（5）：564-575.

［8］ Ning Jifeng，Zhang Lei，Zhang David，et al.Robust Meanshift Tracking with Corrected Background-weighted Histogram［J］.IET Computer Vision，2012，6（1）：62-69.

［9］ Kalal Z，Mikolajczyk K，Matas J.Tracking-learningdetection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（7）：1409-1422.

［10］ 李世忠，王国宏，白 晶，等.压制干扰下雷达网点目标概率多假设跟踪算法［J］.西安交通大学学报，2012，46（10）：101-106.

［11］ Oh S，Russell S，Sastry S.Markov Chain Monte Carlo Data Association for General Multiple-target Tracking Problems［C］//Proceedings of IEEE Conference on Decision &Control.Washington D.C.，USA：IEEE Press，2005：735-742.

［12］ van Lieshout M N M.Markov Point Processes and Their Applications［M］.London，UK：Imperial College Press，2000.

［13］ Dallongeville S，Chenouard N，HervéN.Icy：An Open Bioimage Informatics Platform for Extended Reproducible Research［J］.Nature Methods，2012，9（7）：690-696.

［14］ 彭 爽，蒋荣欣.面向高清视频监控系统的实时运动检测算法［J］.计算机工程，2014，40（11）：288-291.

［15］ 金美娜，赵拥军，盖江伟.一种基于混合RJMCMC方法的宽带信号DOA估计方法［J］.电子与信息学报，2010，32（2）：504-508.

［16］ 夏建涛，何明一.基于Bhattacharyya距离准则的核空间特征提取算法［J］.计算机学报，2004，27（5）：683-689.

［17］ 汤亚波，徐守时.基于D-S证据理论的多源遥感图像目标数据联合关联算法［J］.中国科学技术大学学报，2006，36（5）：466-471.

编辑 顾逸斐

Multi-target Detection and Tracking Algorithm Based on Local Background Weighting and Energy Constraint

CHEN Jiahong
（School of Computing Engineering，Jinling Institute of Technology，Nanjing 211169，China）

As the performance of multi-target tracking based on Marked Point Process（MPP）is poor，a hybrid multitarget detection and tracking is proposed.The improved frame difference method is used to determine the preliminary of the target.Local background weighting is applied to identify further and mark the targets.The consistency of the dynamic model is considered.Energy is used to constraint target dynamics，long-term tracking and target similarity and mutual exclusion.Reversible jump Markov chain Monte Carlo is applied to optimize the nonconvex energy function.Some image sequences are added with different levels of noise.Experimental results show that in the image sequences with Gaussian noise，compared with other tracking algorithm s，the similarities of the proposed algorithm's detection and tracking are highest.In addition，the precision and recall in satellite image sequences and self-capture videos are also highest.The overall performance of the proposed algorithm is better.

multi-target tracking；local background weighting；energy constraint；nonconvex；reversible jump Markov chain Monte Carlo

陈家红.基于局部背景加权和能量约束的多目标检测与跟踪算法［J］.计算机工程，2015，41（11）：267-272.

英文引用格式：Chen Jiahong.Multi-target Detection and Tracking Algorithm Based on Local Background Weighting and Energy Constraint［J］.Computer Engineering，2015，41（11）：267-272.

1000-3428（2015）11-0267-06

A

TP391

10.3969/j.issn.1000-3428.2015.11.046

江苏省高校自然科学基金资助项目（11KJD520006）；江苏省教育科学“十二五”规划课题基金资助项目（D/2013/01/068）。

陈家红（1979-），男，讲师，主研方向：图像处理，目标跟踪。

2015-06-12

2015-07-07 E-m ail：chenjiahong-email@126.com