DSP实现基于改进压缩跟踪算法的目标实时跟踪

闫钧华，姜惠华，杨 勇，谢天夏

（南京航空航天大学 航天学院，江苏 南京210016）

DSP实现基于改进压缩跟踪算法的目标实时跟踪

闫钧华，姜惠华，杨 勇，谢天夏

（南京航空航天大学 航天学院，江苏 南京210016）

为解决目标外形、姿态变化以及被遮挡的难点，对压缩跟踪算法进行改进：以Kalman预测位置为中心，采用由粗到精的搜索策略，快速准确地找到具有最大分类分数的目标位置；根据目标在每一帧最大分类分数的变化规律进行粗判定，再利用目标和模板的相似度进行精判定以判断遮挡的开始；利用Kalman预测器预测目标被遮挡时的位置，利用基于MCD距离的模板匹配检出脱离遮挡后的目标。使用浮点转定点等策略将算法在DSP上优化实现。实验结果表明：跟踪效果稳定，在目标外形、姿态缓慢变化以及被遮挡时能准确地跟踪目标。对640×480像素的视频，跟踪框为64×64像素时，被遮挡目标跟踪速度达到38.5毫秒/帧，满足实时性要求。

目标实时跟踪；遮挡；压缩跟踪；定点DSP

视频目标实时跟踪在视觉导航、安防监控等领域应用广泛，具有重要的研究价值。在实际的各种场景中，目标跟踪存在着光照变化、目标外形尺度变化，运动模糊、遮挡等难点［1］。基于判决模型的算法是当前跟踪算法的研究热点［2-5］。判决模型将跟踪视为背景与目标的二分类问题，如多示例学习跟踪MIL［3］，压缩跟踪CT［4］。压缩跟踪算法利用稀疏的随机测量矩阵提取目标特征，基于朴素贝叶斯分类器对提取的样本进行分类，具有计算量少和跟踪效果鲁棒的优势，但在目标发生外形、姿态、尺度变化以及被遮挡时会出现漂移。现有的压缩跟踪算法的改进主要集中于特征的优化选择和引入多尺度特征［6-8］。为解决跟踪目标外形、姿态变化以及被遮挡的问题，本文对压缩跟踪算法提出如下改进：以Kalman预测位置为中心，采用由粗到精的搜索策略以提高搜索效率，设置粗精判定条件以高效准确地判断遮挡的开始。

以DSP为核心的嵌入式跟踪系统具备结构紧凑、功耗低、移动性强的优势。受到DSP资源的限制，浮点运算多、计算量大的目标跟踪算法实现困难［9］。在DSP上应用成熟的算法以相关跟踪、质心跟踪、MeanShift跟踪和粒子滤波跟踪为主［9-11］。文中算法基于定点DSP实现，采用各项优化策略，以充分利用DSP的硬件资源和软件流水技术。

1 压缩跟踪算法

压缩跟踪算法利用公式v=Φx将一个高维图像空间特征向量变换到一个低维的图像空间特征向量。其中x∈Rm是高维图像空间的特征向量，Φ∈Rn×m（n<

其中，ρ=m%4（取余），利用（1）式对高维图像空间特征向量进行投影，得到一个低维的图像空间特征向量。稀疏随机投影得到的每一个特征实际上表现为原图像特征以φij为权值的加权和。

初始状态下目标位置已知，选取正样本（目标，y=1），负样本（背景，y=0），对所有样本计算其压缩后的低维特征向量v=（v1，…，vn）T，构建朴素贝叶斯分类器式（2）。样本的低维特征向量的任意分量vi都近似看作正态分布，式（3）。其中：和分别为正样本的均值与标准差，和分别为负样本的均值与标准差。

跟踪过程中，在以上一帧的跟踪位置为中心，半径为r的搜索域内遍历候选框，通过上述压缩方法对每个候选框降维并得到低维的图像空间特征向量，用朴素贝叶斯分类器进行分类，计算每个候选框的分类分数H（v），选取具有最大分数的候选框为当前帧的目标位置。之后选取正、负样本，计算样本的所有低维特征。利用式（4）来得到更新后的分类器参数和。 同理，求得分类器参数和。

式（4）中s为正样本个数，λ（λ＞0）表示学习速率，λ越小表示更新速率越快，之前的目标特征遗忘越快。

2 基于改进压缩跟踪算法的目标实时跟踪的DSP实现

2.1 改进的压缩跟踪算法

1）基于Kalman预测器的由粗到精的搜索策略

利用Kalman预测器预测下一帧图像中目标位置，缩小整个图像上目标跟踪的搜索区域，减少计算量且提高准确度。在目标被遮挡时，输出Kalman预测跟踪框，估计目标运动轨迹。

xk为目标在k时刻的状态变量，由目标中心位置在图像水平与垂直方向上的位置和速度构成，即［px，vx，py，vy］T。yk为目标在k时刻的观测状态，由目标中心位置在图像水平与垂直方向上的观测位置构成，即［px，py］T。k时刻的Kalman状态方程和观测方程分别为：

式中，Ak-1，为状态转移矩阵，Ck为观测矩阵，wk-1是k-1时刻状态的随机干扰，vk是k时刻的观测噪声。文中均采用互不相关零均值标准正态白噪声序列，Qk与Rk分别为wk与vk的协方差矩阵，分别如下式所示：

式（6）中Δt表示连续两帧图像间的时间间隔。根据Kalman预测公式（7）可以预测下一帧目标状态ˆ（k+1|k）。

在当前帧，以上一帧得到的Kalman预测位置为中心，采用由粗到精的搜索策略寻找具有最大分类分数的目标位置，从而提高搜索效率。在以R1像素长度为半径的搜索域内，以Δ1像素长度为采样步长采样并计算其分类分数，确定其中最大分类分数的样本位置作为粗跟踪位置；同理，再以为中心，R2像素长度（R1＞R2）为搜索半径，Δ2（Δ1＞Δ2）像素长度为采样步长进行相同过程的计算获取跟踪位置P'k；同理，再以为中心，R3像素长度（R2＞R3）为搜索半径，Δ3（Δ2＞Δ3）像素长度为采样步长进行相同过程的计算得出当前帧的最终精跟踪位置Pk。通过这种搜索策略需要计算的样本数约为。与密集遍历法相比，该策略可以在扩大了目标搜索范围的同时计算更少的样本，且跟踪精度基本保持不变。

2）被遮挡目标的跟踪

压缩跟踪算法对被轻微遮挡的目标和形变目标的跟踪具有鲁棒性，但是无法对被严重遮挡的目标进行持续跟踪。如图1所示，当目标开始进入被遮挡状态，分类器最大分类分数会有一个明显的逐帧减小过程。当目标被严重遮挡时，由最大分类分数定位的目标位置是错误的，这将导致分类器不断学习到负样本，遗忘目标的正样本，导致不可恢复的跟踪失败。

图1 Jogging序列中目标被遮挡状态下压缩跟踪效果和最大分类分数变化示意图

如何有效地判断遮挡的开始、遮挡的结束及相应的处理方法，是被遮挡目标跟踪的关键。建立目标的模板图像T，按式（8）更新。

其中Tk为当前帧的模板图像，S为当前帧跟踪得到的目标图像，Tk+1为下一帧的模板图像。α为模板更新系数，本文取α=0.9。根据目标在被遮挡过程中最大分类分数的变化规律，进行遮挡粗判定。

设定一个阈值Hocc，当连续三帧的最大分类分数持续减小，且当前帧与其相隔的上一帧的最大分类分数减小量大于Hocc，认为目标可能开始被遮挡，图3中虚线框所标位置为目标可能开始被遮挡的时刻。然后进行精判定，计算当前帧压缩跟踪得到的目标图像S与当前帧的模板图像T的MCD［12］距离D。

目标和模板图像的大小为M×N像素。定义目标图像与模板图像的相似度为D/（MN），当相似度小于阈值η，判定目标外观变化较大，已经被遮挡。当判定目标已经被遮挡后，停止更新分类器和模板，采用Kalman预测器的预测位置作为当前帧的目标跟踪结果。利用模板图像在当前跟踪位置的邻域内进行基于MCD距离的相关匹配［6］检测目标。当目标图像与模板图像相似度大于阈值η，匹配成功，判定目标已结束被遮挡状态。

3）改进的压缩跟踪算法流程与仿真

改进的算法不需要每一帧都计算跟踪结果与模板图像的相似度，大大减少判断遮挡带来的计算量。目标被遮挡后，停止更新分类器和模板，利用基于MCD距离的匹配算法检测目标是否结束被遮挡。改进的压缩跟踪算法流程如图2所示。

选取MIL跟踪算法，压缩跟踪算法和本文算法对具有典型遮挡过程的Jogging序列进行基于matlab平台的目标跟踪仿真比较，跟踪误差曲线如图3所示。在Jogging序列中的目标未发生遮挡时，文中算法的跟踪误差整体小于其他两种算法。在目标发生遮挡后，MIL算法和压缩跟踪算法持续学习到遮挡物的特征，从而导致跟踪失败。而文中算法检测出了遮挡的发生，停止更新分类器和模板，利用模板匹配检测出脱离遮挡的目标，实现了持续的跟踪。

图2 改进的压缩跟踪算法流程图

图3 Jogging序列的跟踪误差曲线图

2.2 目标实时跟踪的DSP实现

为了充分利用DSP的软硬件资源以提高算法的运行效率，使用如下优化策略。

1）浮点运算转定点运算

由公式（2）（3）（4），算法中存在除法、取对数以及开方运算等浮点数学运算。在定点DSP上直接使用ANSIC中的运算语句进行浮点数运算，会消耗大量的时钟周期［13］。为了在定点DSP上高效地进行浮点数运算，采用TI公司的IQmath库，其实质是将浮点数转化成Q格式定点数计算。为了扩大用Q格式数所能表示浮点数的范围，不可避免地需要折损精度。由于图像积分特征的均值与方差数量级变化较大，如果采用高精度的Q值表示方法，容易导致数据溢出。综合考虑数据范围和精度，程序中选用全局Q值为8。在计算分类分数的子程序中，对结果的精度要求更高，因此采用局部Q值为10。采用IQmath库中优化过的_IQdiv（）、_IQlog（）以及_IQsqrt（）函数代替ANSIC中相应的数学函数以提高代码运算速度。

2）内存管理的优化

文中采用的DSP平台DM6437的片上内存由32 kB的一级程序缓存（L1P）、80 kB一级数据缓存（L1D）和128 kB的二级存储器/缓存（L2 SRAM/cache）组成。程序代码和数据必须经过逐级搬移而被CPU访问。L1P、L1D和L2的合理配置可以有效提升系统性能［14］。文中将L1P全部设为cache，将L1D设为64 kB的cache和16 kB的SRAM，将L2设为64 kB的RAM和64 kB的cache。为了便于内存管理，将采样得到的样本集位置和特征，图像积分图等大数组定义为全局或静态变量；将其中使用频率最高的数组通过自定义段的方式存放在片上内存的L1D SRAM中，其余大数组则定义在外部内存DDR2中。使用16位short型变量代替32位int型变量定义样本的位置坐标和尺寸，减少近一半的存储空间。

3）采用VLIB函数

VLIB是TI提供的视频算法库，经过深度优化，运算效率很高［15］。计算样本的压缩后的低维特征，需要首先对整幅图像做积分图运算。使用TI的VLIB库中的高效积分图函数接口实现图像积分图运算。使用VLIB函数Kalman模块函数实现Kalman预测的计算。

3 实验结果及分析

实验基于DM6437S60 DSP开发平台，处理核心是一款C64x+内核的主频达594 MHz的32位定点DSP。

图4中运动目标的表观外形姿态缓慢变化。由于算法蕴含了在线学习的思想，不断学习到变化后的目标特征，对于目标外形和姿态的缓慢变化具有较高的鲁棒性，始终能对目标准确地跟踪。

图5为目标被遮挡下的本文算法与原算法的跟踪效果对比。黑色框和白色框分别为原算法和文中算法的跟踪效果。文中算法在第114帧时判定出目标开始被遮挡，利用Kalman预测结果作为被遮挡时的跟踪结果，在第141帧时检测出目标开始脱离遮挡，并且在结束被遮挡后仍能继续对目标进行持续的跟踪。而原算法在目标开始被遮挡后，学习错误的样本，跟踪框持续固定在遮挡物上，导致跟踪失败。

利用DSP的片上定时器对程序运行时间进行统计，结果如表1所示。目标在被遮挡阶段时加入了模板匹配检测目标，程序处理时间会相应增加。在视频图像尺寸为640×480像素，跟踪框尺寸为64×64像素时，在目标被遮挡下平均每帧处理时间为38.5毫秒，实现了对25帧/秒的视频的实时处理。

图4 改进的压缩跟踪算法对形变魔方的跟踪效果（跟踪框80×80像素，分别为第5，98，124，225，309帧）

表1 优化后的改进的压缩跟踪算法程序在DSP上的运行时间

4 结束语

文中在定点DSP平台上优化实现了基于改进压缩跟踪算法的目标实时跟踪，实验结果表明：目标跟踪效果稳定，在目标外形、姿态缓慢变化以及被遮挡时能准确的跟踪目标，满足实时性要求。

［1］Wu Y，Lim J，Yang M H.Online object tracking:A benchmark［C］//Proceedings of the IEEE conference on computer vision and pattern recognition.2013:2411-2418.

［2］Grabner H，Grabner M，Bischof H.Real-Time tracking via On-line boosting［C］//BMVC.2006，1（5）:6.

［3］Babenko B，Yang M H，Belongie S.Robust object tracking with onlinemultiple instance learning［J］.IEEE Transa-ctions on Pattern Analysis&Machine Intelligence，2011，33（8）:1619-1632.

［4］Kalal Z，Mikolajczyk K，Matas J.Tracking-learning-detection［J］.Pattern Analysis and Machine Intelligence， IEEE Transactions on，2012，34（7）:1409-1422.

［5］Zhang K，Zhang L，Yang M H.Real-time compressive tracking［C］//Computer Vision╞ECCV 2012.Springer Berlin Heidelberg，2012:864-877.

［6］石武祯，宁纪锋，颜永丰.压缩感知跟踪中的特征选择与目标模型更新［J］.中国图象图形学报，2014，19（006）:932-939.

［7］王松林，项欣光.基于压缩感知的多特征加权目标跟踪算法［J］.计算机应用研究，2014，31（3）:929-932.

［8］毛征，袁建建，吴珍荣，等.基于在线特征选择的实时压缩跟踪［J］.光学精密工程，2014，22（3）:730-736.

［9］高文，朱明，刘剑，等.基于DSP+FPGA框架的实时目标跟踪系统设计［J］.液晶与显示，2014，29（4）:613-616.

［10］孙航，韩红霞，郭劲，等.基于均值偏移快速算法的红外目标跟踪［J］.仪器仪表学报，2012，33（5）:1122-1127.

［11］夏轩，刘华平，许伟明，等.基于DSP的主动视觉系统［J］.机器人，2012，34（3）:354-362.

［12］任仙怡，廖云涛.一种新的相关跟踪方法研究［J］.中国图象图形学报:A辑，2002，7（6）:553-557.

［13］黄丙胜，秦红磊，丛丽.基于定点DSP的相对导航UKF算法优化研究［J］.计算机工程与设计，2014（7）:2582-2586.

［14］刘项洋，许勇.快速DCT修剪在DSP上的内存访问优化方法［J］.电子学报，2016，44（1）:227-232.

［15］李培平，杨进华，许新科.基于DSP的视频信号边缘提取算法实现 ［J］.长春理工大学学报:自然科学版，2010，33（4）:101-103.

Realization on DSP-based real-time target tracking of im proved com pressive tracking algorithm

YAN Jun-hua，JIANG Hui-hua，YANG Yong，XIE Tian-xia
（College of Astronautics，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China）

To solve the problems of shape change，pose variation and occlusion in target tracking，Compressive Tracking algorithm is improved bywaysbelow：taking the Kalman predictor'soutputas the center ofsearch area，a coarse-to-fine search strategy is used to quickly and accurately find the target position with the maximum classification score.We first roughly determinewhether occlusion happens according to the regular pattern of variation of themaximum classification score ofeach frame.Then we determine whether occlusion happens exactly by computing the similarity between object and template.The Kalman predictoroffers the predicted location of the objectwhen occlusion happens.The judgmentof the end ofocclusion and re-detection of target is completed by templatematching based on the MCDmethod.Real-time target tracking is realized based on the improved CT algorithm in DSP with optimization tactics such as changing float-point computation to fixed point computation.Experiments show that the result of target tracking is stable.The target can be tracked accurately when slow shape change，slow pose variation and occlusion happen.When the input video's size is 640×480 pixels and the tracking rectangle'size is64×64 pixel，theoccluded target is tracked with the speed up to 38.5msper frame，whichmeets the real-time requirements.

real-time target tracking；occlusion；compressive tracking；fixed-point DSP

TN919.82

A

1674－6236（2016）20-0009-04

2016-03-09 稿件编号：201603121

国家自然科学基金资助（61471194）；航空电子系统综合技术重点实验室和航空科学基金联合资助（20155552050）；中国航天科技集团公司航天科技创新基金资助

闫钧华（1972—），女，陕西兴平人，工学博士，副教授。研究方向：多源信息融合、目标检测跟踪与识别。