东北大学 计算机科学与工程学院, 辽宁 沈阳 110819
收稿日期：2015-09-25
基金项目：国家科技支撑计划项目 (2014BAI17B00)；国家关键科技研发基金资助项目 (2015BAH09F02, 2015BAH47F03)；国家自然科学基金资助项目 (61572116, 61572117, 61502089)；中央高校基本科研业务费专项资金资助项目 (N120804001，N120204003)。
作者简介：孟煜 (1990-), 男, 河北唐山人, 东北大学博士研究生;
张斌 (1964-), 男, 辽宁本溪人, 东北大学教授, 博士生导师。
摘要：传统的TLD目标跟踪算法由于检测区域过大导致检测时间过长, 并对相似目标跟踪效果不理想且只能对单个目标快速跟踪.针对这些问题, 利用双Kalman滤波加速预测的DKF检测区域优化算法构造了一种检测区域可自适应调整的多目标跟踪算法——TLD-DOMO算法.TLD-DOMO算法的多目标检测器可对各目标的潜在运动范围进行预测, 使其检测区域的大小及位置自适应地调整至最佳状态, 以此提升对多目标跟踪的精度及效率.此外, 该方法可有效地降低多目标间的相互干扰, 支持对多相似目标的同时跟踪.实验结果表明:TLD-DOMO算法在对各测试视频的多目标跟踪中, 跟踪速度均有提升, 加速比为1.55~2.94倍; 在多相似目标跟踪中, 对各目标的检测与识别效果优于原TLD算法.
关键词：目标跟踪TLD算法多目标检测区域跟踪速度
A Multiple-Object Tracking Algorithm Using TLD-based Adaptive Adjustment of Detection Areas
MENG Yu, ZHANG Bin
School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: ZHANG Bin, E-mail: zhangbin@mail.neu.edu.cn
Abstract: Traditional tracking-learning-detection (TLD) object tracking algorithm takes long time for detection because the area to be detected is too large, and the algorithm is not satisfactory for tracking similar objects, and it is only suitable for single object tracking tasks. Therefore, an efficient TLD-detector optimization for multiple objects (TLD-DOMO) approach is proposed for tracking multiple objects, which is built on a novel algorithm named DKF (double Kalman filter). Detection areas are adjusted adaptively by the prediction method accelerated by double Kalman filtering operation. The multiple-object detectors of TLD-DOMO algorithm can predict potential motion range of each object to optimize the scale and position of detection areas adaptively. Thus, the accuracy and efficiency of multiple-object tracking will be improved. Moreover, the proposed method also reduces the interference among tracked objects effectively for supporting similar objects tracking. Experimental results show that the detection efficiency is improved in all test videos, and the speedup ratios are between 155% and 294%. The effect of detection and recognition of multiple objects surpasses the original TLD approach in tracking multiple similar objects.
Key Words: object trackingTLD algorithmmultiple-objectdetection areatracking speed
在计算机视觉领域中, 目标跟踪是一项重要的研究内容[1-2].目标跟踪可被定义为在视觉图像中围绕某些可变或不变的场景定位估计某个目标对象的运动轨迹的问题[3]，而多目标跟踪技术则是目标跟踪的进阶技术.多目标跟踪需要在同一视频序列的同一帧中标记及跟踪多个目标, 以达到同时跟踪多个目标的目的[4]，其跟踪难度及运算复杂度远远超出单目标跟踪[5].
目前, 多目标跟踪算法有很多:基于多目标运动信息的跟踪[6], 将2D构建成3D空间的多目标跟踪[7], 基于多目标特征融合与自适应模板的跟踪[8], 以及将多目标特征数据进行关联处理的目标跟踪[9].这些算法都在一定程度上有效解决了多目标跟踪问题, 但其精确性与实时性还无法达到相对平衡.
经典的TLD (tracking-learning-detection) 目标跟踪算法[10]将目标的跟踪过程分成三个主要模块:跟踪、学习和检测.在对每一帧图像的处理中, 三个模块同时工作, 完成对目标特征的学习及更新，从而实现长期的目标跟踪.但由于TLD算法检测器运算效率过低以及算法结构的制约, 该算法只能满足单个目标的快速跟踪, 无法在一次跟踪过程中对同一视频序列同一帧内多个目标进行高效地检测与跟踪.
本文针对检测器由于检测子窗口数目过多而导致的目标检测速度过慢的问题, 提出DKF (double Kalman filter) 检测区域自适应调整算法, 使检测器在检测速度提升的同时能够支持多目标检测; 针对学习器建立多目标模板库, 使其能够学习多目标特征; 针对跟踪器利用跟踪优化的多次中值光流法对多目标实施帧间跟踪.在此基础上建立了一个检测区域动态调整的TLD多目标跟踪算法TLD-DOMO (TLD-detector optimization for multiple objects).
1 DKF检测区域自适应调整检测算法TLD算法的运行速度虽然优于一般在线学习方法, 但其检测器要对每一帧的整幅图像的所有子窗口进行检索, 由于子窗口过多, 而绝大部分子窗口并不包含真正的跟踪目标, 所以对这些子窗口内的图像块进行检测会浪费大量运算时间, 严重影响目标跟踪的实时性.因此, 提出一种检测区域可动态自适应调整的方法——DKF检测区域自适应调整检测算法.此方法可使检测器的检测区域自适应调整至合适大小及位置, 大量减少检测器的预算量以提高检测速度.
在DKF算法的每次迭代中, 主要分为四个步骤：第一次预测、第一次更新，以及作为加速矫正的第二次预测和更新.第一次预测的状态方程为
 | (1) |
然后进行第一次状态更新, 生成的最优预测状态
 | (2) |
此时第一次预测结束, 系统进入第二次预测, 其预测状态量为
 | (3) |
最后, 第二次更新预测系统, 得到最后的预测向量:
 | (4) |
2 TLD-DOMO多目标跟踪算法2.1 TLD-DOMO多目标跟踪算法架构为了适合多目标跟踪, TLD跟踪架构内的跟踪器、学习器与检测器均需要进行多目标改造.TLD多目标跟踪算法架构如图 1所示, 改动中保留了原TLD算法的跟踪器、学习器及检测器三部分相互独立这一经典设计.
图 1(Fig. 1)
 | 图 1 TLD-DOMO多目标跟踪算法架构Fig.1 Block diagram of the TLD-DOMO multiple-object tracking algorithm |
对于这三个主要部分的内部结构及相互之间的协作处理改进较为明显.多目标检测器能够重新初始化跟踪器, 使跟踪失败的可能性最低.学习器将改进成为多模板库的在线学习, 在每一个目标经过检测器检测之后, 对各目标的特征进行相互独立的学习.对于每个目标在跟踪器与检测器内的更新也是相互独立的以避免多目标之间产生影响.建立多目标跟踪器机制, 通过获取各目标状态来确定每一个跟踪目标在视频图像序列中每一帧的位置.同时, 跟踪器能够将各目标的训练数据反馈给检测器, 通过其相互作用可使整个系统在之后的跟踪中提升对各目标的跟踪效果.
2.2 TLD-DOMO多目标跟踪算法检测器在TLD目标跟踪算法中, 检测器是耗时最长同时也是最重要的一部分, 因此对检测器的多目标优化就尤为重要.首先利用本文提出的DKF算法, 根据各目标的运动情况确定每个目标的检测区域, 将每个目标的检测区域缩小至其周围；然后将与每个目标的检测区域有交集的子窗口内的图像块分别依次利用方差滤波器、集合分类器和最近邻分类器进行分类检测；最后在每一个检测区域内判断每一个子窗口是否存在该目标图像, 并选择最佳的目标图像块.在多目标检测过程中, 每个目标区域都要独立接受检测, 并且检测器需要对与各目标的检测区域相交的全部子窗口进行分类, 以保证能够精确地找出目标, 更加准确地提取目标特征.
2.3 TLD-DOMO多目标跟踪算法学习器多目标学习器对各目标的学习过程是相互独立的.在多目标跟踪初始化过程中, 多目标学习器在已经用矩形框标记出的多个跟踪目标中提取每个目标样本并训练这些样本来初始化检测器.在生成已标注样本的过程中, 首先要从初始的每个跟踪目标矩形框内合成得到正样本：从扫描的子窗口中选择距离每个跟踪目标初始矩形框最近的子窗口，将每一个子窗口内的图像块进行几何变换, 由此对每个目标生成不同的仿射矩形框, 并将它们附加标准高斯噪声, 最后可以得到正样本.负样本则是从初始的跟踪目标矩形框的周边选取的.接着, 每个目标中被选取的正、负训练样本就会被用于更新该目标的检测器.这样, 每个目标的检测器就可以随时利用P-N学习的更新结果来独立地运行.
2.4 TLD-DOMO多目标跟踪算法跟踪器在TLD跟踪器的多目标优化方面, 其核心算法利用中值光流法构建, 并在中值光流法的基础上进行改进, 加入了对每个目标跟踪失败情况的检测.多目标跟踪器利用中值光流法跟踪各目标, 并用矩形框标注.对视频图像序列前一帧图像及每个目标的特征点集进行处理，得到当前帧的各目标特征点集的位置, 并估计各目标在下一帧中的运动.
多目标跟踪器将沿用经典TLD跟踪器对于目标消失情况下的处理策略, 利用每个目标的位移与位移中值的残差来判断跟踪是否失败.同时, 多目标跟踪器对各目标的跟踪是相互独立的, 因此在同一次跟踪过程中, 每个目标的跟踪状态各不相同.
3 实验与结果分析3.1 多目标跟踪效果在3段测试视频中，TLD-DOMO多目标跟踪算法与原TLD算法对各目标成功跟踪的帧数见表 1.
表 1(Table 1)
 表 1 TLD-DOMO算法与原TLD算法成功跟踪的目标帧数Table 1 Number of successful tracking frames with TLD-DOMO and TLD
| 表 1 TLD-DOMO算法与原TLD算法成功跟踪的目标帧数 Table 1 Number of successful tracking frames with TLD-DOMO and TLD | ||||||||||||||||||||||||||||||||||||
Pedestrian1与Pedestrian2视频序列中的目标均为行人.Carchase视频序列中的跟踪目标1为黑色车辆, 目标2与目标3为特征较为相似的警车.从表 1可以看出, 两算法在视频Pedestrian1的目标2与视频Pedestrian2中的目标1跟踪成功的帧数一样, 对所有其他目标, TLD-DOMO多目标跟踪算法均有更好的跟踪效果.视频序列Pedestrian1的目标2与Pedestrian2中的目标1均为行人目标且行人特征比较明显, 所以两算法跟踪效果一致.为了进一步分析TLD-DOMO多目标跟踪算法精确度较好的原因, 选取两种算法在Pedestrian2视频图像序列中第3帧到第10帧的跟踪情况, 各帧跟踪效果如图 2所示.
图 2(Fig. 2)
 | 图 2 TLD与TLD-DOMO多目标跟踪效果对比Fig.2 Comparison of multiple-object tracking performance between TLD and TLD-DOMO |
各视频帧的左上角数字为帧数.TLD-DOMO多目标跟踪中目标矩形框左上角数字为目标的标号.从图 2中不难看出, 目标1由于其特征明显, 两种算法的跟踪效果一直保持一致.对于目标2, TLD算法跟踪过程中, 在第6帧的跟踪过程中发生偏差, 跟踪到了位于左方的目标3身上.对于目标3, TLD算法跟踪过程中, 在第7帧之后跟踪发生偏移, 错误地跟踪到了位于其右方的目标2身上.而TLD-DOMO多目标跟踪在这些帧中一直正确跟踪各目标.究其原因不难发现, 行人目标2与行人目标3的穿着极为相似, 均为深色上衣浅色裤子, 唯一有些差别的地方为行人目标2的裤子为白色, 行人目标3的裤子为浅蓝色.
在这种有极为相似目标干扰的情况下，TLD-DOMO由于进行了检测区域的优化, 使其检测区域缩小至目标周围, 从而使目标的特征更加明显, 并从区域上排除了背景相似目标, 所以能够从根本上排除相似目标对跟踪目标的干扰.同时, 从另一个角度可以发现, 在原TLD算法中跟踪失误的这两个行人目标距离较近, 很可能导致其检测器中的最近邻分类器与跟踪器中值光流法失效; 在这种情况下, 最好的解决办法就是将两个目标进行有效的物理隔绝.所以虽然TLD-DOMO也沿用了TLD检测器中的最近邻分类器与跟踪器中值光流法跟踪, 但由于检测区域的限制, 可使其相似目标与跟踪目标物理分离, 只针对前景目标区域进行检测分类与跟踪.因此, TLD-DOMO多目标跟踪算法不但具备较原TLD算法运算速度快、抗干扰能力强的特点, 而且在其能够处理多目标跟踪问题的基础上, 对跟踪多相似目标的问题也有着优秀的辨别处理能力.
3.2 多目标检测运算量原TLD算法与TLD-DOMO算法在各测试视频中通过检测器检测的子窗口数量见表 2.
表 2(Table 2)
表 2 TLD与TLD-DOMO检测的子窗口数量Table 2 Number of patches in TLD and TLD-DOMO
| 表 2 TLD与TLD-DOMO检测的子窗口数量 Table 2 Number of patches in TLD and TLD-DOMO |
根据视频的不同, TLD-DOMO算法检测数目相对于原TLD算法减少的比例保持在61%~73%之间.结合表 1不难发现, TLD-DOMO算法中子窗口检测数目的减少比例与目标跟踪的成功率成正比, 成功跟踪目标的帧数越多, 其检测的子窗口图像块数目越少.产生这种现象的主要原因是，当检测器检测不到目标时, 由于无法对目标的检测范围进行有效的预测, 为了保证当目标在图像内任何一个位置重新出现时能有效对其检测并获得其新的特征, 需要对图像序列整帧图像范围内的所有子窗口图像块进行检测.对于子窗口检测数目减少最明显的Carchase视频，其各帧检测的子窗口数如图 3所示.
图 3(Fig. 3)
 | 图 3 Carchase视频序列各帧检测的子窗口数目Fig.3 Number of patches of every frame in Carchase |
从图 3中可以看出, 第221帧~第257帧和第705帧~第790帧的TLD-DOMO检测子窗口数目远远高于其他帧的数目, 其中部分帧的TLD-DOMO算法跟踪效果如图 4所示.从图 4中可以看出, 由于目标被遮挡或在视频中消失, 导致某个或多个目标跟踪失败, 针对这些跟踪丢失的目标需要检测图像中的子窗口图像块, 因此在这些丢失跟踪目标的帧中子窗口检测数目较多.
图 4(Fig. 4)
 | 图 4 Carchase视频中TLD-DOMO算法对部分帧的跟踪效果Fig.4 Result of tracking frames with TLD-DOMO in Carchase |
3.3 多目标跟踪时间TLD算法与TLD-DOMO算法在各测试视频中的跟踪时间见表 3.
表 3(Table 3)
表 3 TLD与TLD-DOMO的跟踪时间Table 3 Tracking time with TLD and TLD-DOMO
| 表 3 TLD与TLD-DOMO的跟踪时间 Table 3 Tracking time with TLD and TLD-DOMO |
从表 3中可以看出，3段视频中TLD-DOMO的跟踪速度是原TLD算法的1.55~2.94倍.结合表 1和表 2分析, TLD-DOMO跟踪算法的加速比与跟踪精度成正比, 与减少的子窗口检测数目成正比, 因此, 在TLD-DOMO算法中, 跟踪精度越高, 减少的子窗口检测数目就越多, 加速效果越明显.
4 结语本文设计了多目标跟踪精度、检测器运算量及跟踪时间三组对比实验, 结果表明, TLD-DOMO算法能够快速地对同一帧中多个目标同时进行跟踪, 且跟踪速度是原TLD算法的1.55~2.94倍.同时由于检测与跟踪区域的动态调整并结合多目标模板库的优化, 使得多个跟踪目标之间互不干扰, 保证了对多目标的跟踪精度, 尤其是在同时跟踪多相似目标时, 该算法有优秀的表现, 因此TLD-DOMO多目标跟踪算法具有较高的实际应用价值.然而, 在TLD-DOMO多目标跟踪算法运算过程中, 可能出现因检测区域构建失误而导致的检测失败并致使检测器重新检测的问题, 因此在今后的研究中需进一步提升检测区域预测的精准度.
参考文献
| [1] | Babenko B, Yang M H, Belongie S. Robust object tracking with online multiple instance learning[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1619–1632.DOI:10.1109/TPAMI.2010.226 |
| [2] | Wu Y, Lim J, Yang M H.Online object tracking:a benchmark[C]//Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Oregon:IEEE, 2013:2411-2418. |
| [3] | Kristan M, Pflugfelder R, Leonardis A, et al.The visual object tracking VOT2014 challenge results[C]//IEEE International Conference on Computer Vision Workshops.Chile:IEEE Computer Society, 2015:98-111. |
| [4] | Keni B, Rainer S. Evaluating multiple object tracking performance:the CLEAR MOT metrics[J].EURASIP Journal on Image and Video Processing, 2008, 2008(8): 1–10. |
| [5] | 蒋恋华, 甘朝晖, 蒋旻. 多目标跟踪综述[J].计算机系统应用, 2010, 19(12): 271–275. ( Jiang Lian-hua, Gan Zhao-hui, Jiang Min. Review of multi-target tracking[J].Computer Systems & Applications, 2010, 19(12): 271–275.) |
| [6] | 闫辉, 许廷发. 多特征融合匹配的多目标跟踪[J].中国光学, 2013, 6(2): 163–170. ( Yan Hui, Xu Ting-fa. Multi-object tracking based on multi-feature joint matching[J].Chinese Optics, 2013, 6(2): 163–170.) |
| [7] | Brau E, Guan J, Simek K, et al.Bayesian 3D tracking from monocular video[C]//IEEE International Conference on Computer Vision.Sydney:IEEE, 2013:3368-3375. |
| [8] | Milan A, Schindler K, Roth S.Detection-and trajectory-level exclusion in multiple object tracking[C]//Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Oregon:IEEE Computer Society, 2013:3682-3689. |
| [9] | Kurz G, Baum M, Hanebeck U D.Real-time kernel-based multiple target tracking for robotic beating heart surgery[C]//2014 8th IEEE Sensor Array and Multichannel Signal Processing Workshop.A Coru?a, 2014:201-204. |
| [10] | Kalal Z, Mikolajczyk K, Matas J. Tracking-learning-detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1409–1422.DOI:10.1109/TPAMI.2011.239 |
