哈希编码和Kalman滤波的目标跟踪算法*

李 华， 李 莉， 郭育艳

(1. 河南工程学院 计算机学院， 郑州 451191； 2. 河南财经政法大学 科研处， 郑州 450046)

视频图像中运动目标的检测与跟踪是计算机视觉领域中的热点之一，广泛应用于军事侦察、精确制导、火力打击、战场评估及安防监控等领域[1-2].目标跟踪通过检测目标在视频图像序列中的位置信息来实现对目标的跟踪，常用的目标跟踪算法有Mean-shift、模板匹配法、KLT、光流法和CamShift等.其中，Mean-shift目标跟踪算法[3]计算量不大，在目标区域已知的情况下可实现实时跟踪，但当目标运动速度较快时，跟踪效果较差；基于模板匹配的目标跟踪算法[4]具有较强的鲁棒性，跟踪效果较好，但计算量大，算法复杂，跟踪速度较慢；KLT跟踪算法利用特征点实现目标跟踪，跟踪速度较快，但跟踪效果较差；光流法跟踪效果一般，计算量较大，速度较慢，不适用于目标跟踪；CamShift[5]是一种连续自适应的Mean-shift算法，主要是针对视频序列，该算法对单目标跟踪效果较好，但当目标与背景颜色相近时，跟踪效果较差.

哈希算法[6-7]是图像检索领域中一个重要算法，该算法将任意分辨率的图像数据转化为几百比特的二进制序列，大大减少了图像检索的计算量.由于运动目标跟踪的原理与图像检索的原理相似，即在每一帧中搜索与目标最相似的区域.针对现有的目标跟踪算法过于复杂、计算量大和遮挡无法跟踪等问题，将哈希算法改进后应用于目标跟踪领域，提出了基于哈希编码和Kalman滤波的目标跟踪改进算法.首先利用哈希算法对感兴趣区域进行编码；然后根据编码特征进行目标匹配跟踪；最后借助Kalman滤波算法对运动目标的位置进行预测.实验表明，本文方法跟踪效果较好，具有较强的抗干扰能力，提高了跟踪速率，但无法较好地实现遮挡情况下的目标跟踪，因此，本文方法的性能有待进一步提高.

1 哈希编码目标跟踪算法

鉴于哈希算法的抗碰撞性、鲁棒性和Kalman滤波算法的快速性[8]，提出了基于哈希编码和Kalman滤波的目标跟踪改进算法，算法实现过程如图1所示.

图1 算法实现框图Fig.1 Implementation block diagram of algorithm

首先输入视频序列帧，提取出待测区域的哈希编码值，与目标编码值进行比对，继而跟踪匹配；再采用Kalman滤波算法对运动目标位置进行最优估计；最后实现目标更新，输出结果.

1.1 编码特征提取

目标特征提取是目标跟踪过程中的核心部分.采用哈希编码对图像信息进行处理，映射为一维数字摘要.特征相同或相近的二维图像生成的一维数字摘要也相同或相近；反之，生成的一维数字摘要不同或区别较大[9].哈希编码生成过程分为以下几步：

1) 图像预处理，消除一些无关信息，如噪声.

2) 将彩色图转化为灰度图，减少计算量.YUV空间中的Y分量代表图像亮度，U、V代表色度分量，采用Y分量来近似代替灰度图，RGB空间向YUV空间转换的公式为

(1)

3) 将目标图像缩小为32×32像素，快速去除图像高频信息和细节，简化后续运算.

4) 对处理后的图像进行DCT变换，其表达式为

(2)

5) 计算上述64个DCT系数的均值E，即

(3)

6) 生成编码值.将DCT变换后的系数f(u，v)与均值E比较，若f(u，v)≥E，记为1；若f(u，v)

(4)

将比较结果串成长度为64的一维向量，组合次序无要求，但必须保证所有图像都采用同一个编码次序，得到一个64 bit编码数据，为该目标的编码值.

1.2 目标匹配

目标匹配有多种方法，如欧氏距离、汉明距离和范数等.本文通过计算目标的哈希编码值与图像的哈希编码值之间误码的个数，将误码个数最少的目标作为跟踪目标.设目标的哈希编码值为ho，待测区域的哈希编码值为ho′，图像的哈希编码值为hi，误码个数为Dis(ho，hi)，则有

∃ho′∈hi，Dis(ho，ho′)

(5)

哈希编码值ho′对应的图像区域为搜索到当前的目标区域.

1.3 目标校正

搜索视频图像目标难免存在误差，随着搜索视频帧数的增加，误差也逐渐增多[10].为了避免误差的引入，本文采用反馈方式对目标位置进行校正.

设上一帧视频图像为ft-1(x，y)，目标位置为(xt-1，yt-1)，采用Kalman滤波算法在当前帧中搜索目标位置，得到新位置(x′t，y′t).再以新位置为起点在上一帧中用Kalman滤波算法反搜索目标，得到上一帧中目标位置(x′t-1，y′t-1).若(x′t-1，y′t-1)≠(xt-1，yt-1)，则对当前帧中搜索到的目标位置(x′t，y′t)进行校正，即

(6)

式中，(xt，yt)为当前帧中搜索到的目标位置(x′t，y′t)校正后的最终位置.

2 Kalman加速策略

视频图像处理的关键问题是实时性问题.在整张图像上搜索目标非常耗时，缩小搜索范围，可大大提升搜索效率.利用Kalman滤波算法对运动目标下一帧可能出现的位置进行预测，再将预测位置作为搜索的起点，对其周围图像进行搜索，从而缩小搜索范围[11].当目标被部分短暂遮挡时，将Kalman预测的位置看作真实位置来完成对目标的稳定跟踪.

Kalman滤波算法包含两个子模型：状态模型和预测模型[12].状态模型可用一个线性随机微分方程描述，即

X(k)=AX(k-1)+BU(k)+W(k)

(7)

系统的测量值为

Z(k)=HX(k)+V(k)

(8)

式中：X(k)为k时刻系统状态向量；U(k)为k时刻驱动输入向量；A为状态转移矩阵；B为系统控制输入矩阵；Z(k)为k时刻测量结果矢量；H为状态向量与观测向量之间的联系矩阵；W(k)和V(k)分别为过程与测量的噪声，服从高斯分布.

状态向量预测方程为

X(k|k-1)=AX(k-1|k-1)+BU(k)

(9)

式中：X(k|k-1)为利用上一时刻状态预测当前状态的结果；X(k-1|k-1)为上一时刻状态的最优结果.

X(k|k-1)的协方差P预测方程为

P(k|k-1)=AP(k-1|k-1)A′+Q

(10)

式中：P(k|k-1)为X(k|k-1)对应的协方差；P(k-1|k-1)为X(k-1|k-1)对应的协方差；A′为A的转置矩阵；Q为系统过程的协方差.结合预测值与观测值，对X(k|k-1)进行最优化估计，即

X(k|k)=X(k-1|k-1)+kg(k)·

(Z(k)-HP(k|k-1))

(11)

式中，kg为卡尔曼增益，其表达式为

(12)

式中，R为观测噪声协方差.当前状态协方差P(k|k)的预测方程为

P(k|k)=(I-kg(k)H)P(k|k-1)

(13)

式中，I为单位矩阵.对于单模型测量值I=1，当系统进入k+1状态时，P(k|k)即为P(k-1|k-1).

在每一帧搜索目标时，以预测值X(k|k-1)作为起始点，在其周围进行目标搜索.相邻两帧图像时间间隔非常短，如果目标做匀速运动，那么状态转移矩阵A与系统控制输入矩阵B为

其中，Δt为时间间隔，状态向量与观测向量之间的联系矩阵为

3 实验结果与分析

3.1 实验对比

为了验证本文算法的有效性，在MATLAB2012b环境下运行，对视频背景静止且较为单一的专用测试视频“Sample.avi”(总帧数为80帧)分别采用经典均值偏移(Mean-shift，MS)算法和本文提出的改进算法进行对比.Mean-shift算法对“Sample.avi”视频中的第1帧、第9帧、第16帧和第23帧的跟踪结果如图2所示.

图2 Mean-shift算法视频跟踪结果Fig.2 Results of video tracking with Mean-shift algorithm

由图2可知，Mean-shift算法以目标颜色直方图作为特征，采用窗口固定方法对“Sample.avi”视频进行跟踪，跟踪效果较差，易丢失目标.第16帧跟踪目标已严重跟偏；第23帧已完全丢失目标.Mean-shift算法耗时11 s，跟踪效果较差.采用本文方法对“Sample.avi”视频的第1帧、第26帧、第45帧和第80帧进行跟踪，结果如图3所示.

图3 本文方法视频跟踪结果(1)Fig.3 Results of video tracking with as-proposed method (1)

通过实验分析，采用本文方法在“Sample.avi”视频跟踪全程中，并无出现跟踪目标偏离的情况，跟踪效果较好.在相同实验环境下，耗时7 s，速度优于经典Mean-shift算法.

对比实验结果表明，本文提出的基于哈希编码与Kalman滤波的目标跟踪改进算法在背景单一的情况下跟踪效果较好，在视频第80帧(最后一帧)时仍能有效跟踪，而Mean-shift算法在第16帧时已严重跟偏，跟踪效果较差.

为进一步验证本文方法的优越性，分别采用Mean-shift算法和本文方法对“Sample.avi”视频的定位偏差进行分析.偏差大小使用位置分量的和方根误差(root sum square error，RSSE)来描述，即

(14)

式中：xi、yj分别为目标x、y方向上位置估计值；xp、yp分别为目标x、y方向上位置真实值.

若目标的位置估计值与位置真实值相同，则对应时刻的和方根误差RSSE为0；反之，则越大.采用Mean-shift算法和本文方法对“Sample.avi”视频进行定位偏差分析，结果如图4所示.

图4 定位偏差Fig.4 Location deviation

Mean-shift算法从第16帧开始，位置分量的和方根误差(RSSE)呈上升趋势，跟踪效果较差；本文方法的误差曲线呈细微波动状态，跟踪效果较好.

3.2 复杂环境目标跟踪

由于跟踪效果受拍摄环境、目标位置、目标大小等因素影响较大，所以实验采取主观评判的标准，不进行偏差分析.采用本文方法对拍摄的一个骑摩托车小视频“Motorcycle.avi”进行跟踪，该视频总帧数为17帧，视频图像大小为640×480像素，跟踪时间共1.5 s，跟踪目标为摩托车驾驶员.采用本文方法对“Motorcycle.avi”视频第1帧、第8帧、第13帧和第17帧进行跟踪，结果如图5所示.

图5中，“Motorcycle.avi”整个视频背景复杂，跟踪目标处于快速运动中，选取的任意四帧跟踪结果表明对于快速运动的目标，本文方法跟踪效果较好，并能准确计算出目标在每一帧中的位置.

采用本文方法对小视频“Target with Cover.avi”的第1帧、第25帧、第70帧和第84帧进行跟踪实验，跟踪目标为行人，视频总帧数为84帧，视频图像大小为640×480像素，跟踪时间共7 s，得到的实验结果如图6所示.

图5 本文方法视频跟踪结果(2)Fig.5 Results of video tracking with as-proposed method (2)

图6 本文方法视频跟踪结果(3)Fig.6 Results of video tracking with as-proposed method (3)

从图6a中可以看出，本文方法在无遮挡时跟踪效果较好；当目标渐渐被遮挡时，仍能有效地跟踪，如图6b所示；当目标慢慢地抽离被遮挡的部分时，该方法仍能较好跟踪，如图6c所示；跟踪一直持续到视频的最后一帧(第84帧)，如图6d所示.该实验表明，本文方法在目标遮挡后仍能有效跟踪，且跟踪效果较好.

4 结 论

针对经典的Mean-shift目标跟踪算法计算量大，计算复杂，不利于硬件实现等问题，提出了基于哈希编码和Kalman滤波的目标跟踪改进算法.该方法利用哈希函数的抗碰撞性和摘要性提取目标的哈希特征值并进行编码，跟踪匹配，借助Kalman滤波算法对运动目标位置预测，缩小目标搜索范围，加快目标跟踪速度，实现将二维图像转变为一维数字摘要，大大减少了匹配运算量.在MATLAB2012b，图像大小640×480像素的环境下，跟踪速率可达12帧/s.通过分析不同的视频，实验结果表明，基于哈希编码与Kalman滤波的目标跟踪改进算法有效地提高了目标跟踪速度，并在背景复杂、目标快速运动、完全遮挡等情况下仍能稳定跟踪，针对以前很多遮挡后无法进行继续跟踪的算法进行了很好的补充.