基于类间方差和离散余弦变换的模板匹配哈希目标跟踪

李海彪, 黄 山

(四川大学,a.电气信息学院; b.计算机学院，成都 610065)

0 引言

基于哈希算法的图像处理技术是最近几年研究的热门话题。哈希算法具有鲁棒性强、实时性好、原理通俗易懂、运算量少、适用于大多数场景等优势，逐渐在内容搜索、图片搜索、数字水印、模式识别等领域被广泛应用[1-2]。压缩感知哈希算法是哈希算法中最经典、最实用的算法之一。由于压缩感知哈希算法生成的哈希序列具有唯一性、安全性、快速性、鲁棒性等优势，从而被广泛应用于图片搜索领域。最近，一部分学者鉴于感知哈希算法的优势，提出将此算法运用于目标跟踪领域。例如文献[3]提出了基于均值图像块的感知哈希算法来克服跟踪过程中的光照变化、遮挡问题，但是由于没有模板更新策略，跟踪时间稍长就会发生目标漂移和跟踪失败的现象；文献[4]提出基于前景学习的感知哈希目标跟踪算法，能够一定程度上解决跟踪目标漂移后的目标重定位问题,但是在光照发生变化、背景与目标颜色相近时，就会跟踪失误；文献[5]提出了基于改进Adaboost特征检测的感知哈希跟踪算法,对于克服目标跟踪过程中出现的漂移问题、目标丢失后重定位和恢复跟踪等问题有效，但是对于目标发生形变、遮挡等问题，实时跟踪准确性较差。针对跟踪时间较长、目标形变、光照变化、局部遮挡导致难以跟踪的问题，本文提出了一种基于类间方差和离散余弦变换的模板匹配的增强哈希目标跟踪算法。利用类间方差阈值分割和离散余弦变化进行特征提取，根据汉明距离的大小来决定是否更新目标模板，运用抽屉原理来缩短搜索匹配模板的时间，加快匹配速度，从而达到实时跟踪目标的目的。该算法与压缩感知哈希目标跟踪算法相比，鲁棒性更强，提高了目标跟踪成功率。

1 基于DCT的压缩感知哈希算法

基于DCT的压缩感知哈希算法[6-10]是在哈希算法中加入了离散余弦变换函数。离散余弦变换(DCT)是一种图像压缩算法，它将图像从像素域变换到频率域。一般图像都存在很多冗余和相关性，所以转换到频率域之后，系数的特点是:从左上角到右下角，从低频到中频，再到高频，系数的绝对值逐渐变小，能量集中在低频部分，如图1所示。

图1 DCT函数运行结果图Fig.1 Results of DCT function

基于DCT的压缩感知哈希算法的工作过程如下：1) 将目标附近的图像进行压缩，滤掉高频部分，得到图像的大概轮廓，将图像像素压缩成32×32；2) 灰度化，进一步简化计算；3) 通过DCT变换压缩，得到像素大小为32×32的DCT系数矩阵，只保留左上角8×8的矩阵；4) 比较灰度值，将每一个像素的灰度值与平均值进行比较，小于均值记0，大于均值记1，得到哈希序列；5) 将得到的哈希码与模板的哈希码进行与运算，计算不同位的个数，即汉明距离；6) 循环比较，得到最小的汉明距离，此时的窗口即为目标所在位置。

2 本文的改进算法

2.1 提取目标特征

本文在基于DCT的压缩感知哈希算法的基础上加入了类间方差阈值分割算法，利用使图像中目标物和背景分割错误最小的像素阈值自动将背景与目标分割出来，增加目标特征的权重，滤掉环境因素的影响，从而降低环境因素对算法目标跟踪的影响。其原理如下。

设原始灰度图像灰度级为L,灰度级为i的像素点数为n，则图像的全部像素数为N=n0+n1+…+nL-1，归一化直方图，则

(1)

按灰度级将阈值t划分为两类，即C0=(0,1,2，…，t)和C1=(t+1,t+2,…，L-1)。

(2)

(3)

(4)

(5)

定义类内方差为

(6)

类间方差为

(7)

总体方差为

(8)

(9)

2.2 求取哈希序列

利用图像均值来求哈希序列对目标跟踪有一定实际作用，但是当目标物受到不均匀的光照时，采用图像均值的办法来跟踪会造成跟踪精度下降，所以需要避免图像均值带来的不利影响。本文采用快速增强差异的方法：计算相邻两列像素的差值，设定一个阈值，若超过此值，将左边像素设为0，反之设为1。按此方法将像素大小为16×16的图像化简为16×15的矩阵。考虑到图像每一行的像素与整体像素的相关性，对于最后一列，采用行均值与整体均值的差值，若超过设定阈值，赋值为1，否则为0，得到了像素大小为16×16矩阵的哈希序列。

2.3 搜索匹配目标

在第1帧时得到目标的哈希序列(像素大小为16×16的矩阵)即为目标模板，之后在目标周围进行搜索，计算每个搜索框的哈希序列，与上一帧的模板哈希序列进行比较，得到差异性最小的搜索框。在寻找目标模板的最佳匹配模板时，需要循环比较目标周围各个搜索框内的哈希序列，统计不同的位数。这个计算量比较复杂繁琐，为了提高运行效率，采用抽屉原理来提高比较汉明距离的效率。

在距离目标模板的汉明距离为15的范围内进行搜索，将像素大小为16×16矩阵的哈希序列平均分为16段子序列，根据抽屉原理可知，在汉明距离为15的范围内搜索，匹配的两串哈希序列至少有一段子序列是完全相同的。若此搜索窗口内图像的哈希序列与目标模板没有任何一段子序列完全一致，则可视为此搜索窗口没有匹配到跟踪目标，继续计算下一个搜索窗口的感知哈希序列;若至少有一段子序列完全一致，再对其他子序列计算汉明距离; 如此循环最终找到汉明距离最小的匹配目标。这样可以节省大量的循环比较时间，提高运行效率。

2.4 模板自适应更新

通过循环比较，得到最佳匹配目标，预设a值和b值两个阈值。汉明距离若是小于a值，则进行目标跟踪，更新模板，下一帧采用类间方差进行跟踪；若是大于a值且小于b值，则进行目标跟踪，更新模板，下一帧采用DCT提取低频信息的方法进行跟踪；若是大于b值，不更新模板，直接进入下一帧，首先采用类间方差进行跟踪。

3 算法实现

本文提出了一种融合两种不同算法来提取目标特征信息，以设定的阈值来决定是否更新目标模板的增强哈希目标跟踪算法。其中，类间方差阈值分割算法能够增加目标权重，降低背景环境的影响，有效地提高了目标在复杂环境下的跟踪成功率。DCT提取低频信息算法具有一定的抗遮挡和抗光照的能力。本文利用两种特征信息来跟踪目标。本文算法流程如图2所示。

图2 算法流程图Fig.2 Flow chart of the algorithm

4 实验结果与分析

本实验在CPU为AMD A8- 4500M、内存为4 GB的PC机上使用VS2013的开发平台与OPENCV2.4.9以及C/C++语言进行编程实现。以下3个实验均采用本文算法、基于DCT的压缩感知哈希算法和传统哈希算法进行对比验证，以检验算法的优劣。实验的视频均自OTB2013的视频库。

实验1 在灰度亮度变化较大的复杂环境下进行目标跟踪。采用公开的David 视频进行实验，实验结果如图3所示。

图3 David视频实验结果Fig.3 Experimental results of David video

从实验结果可以直观地看出：本文算法的跟踪一直很稳定，跟踪准确度很高；而基于DCT的压缩感知哈希算法和传统哈希算法在第380帧左右就跟踪失败，跟踪过程受背景环境的影响很大，跟踪准确度较低。比较可知，本文算法在复杂环境有光照变化的情况下优于其他两种哈希算法。

实验2 在室内目标发生形变、有遮挡的情况下进行目标跟踪。采用公开的Girl视频进行实验，实验结果如图4所示。

图4 Girl视频实验结果Fig.4 Experimental results of Girl video

从实验结果可以直观地看出：传统哈希算法在第100帧之前跟踪效果较好，但在目标发生形变之后，跟踪效果就很差，不能自动修复，跟踪准确性很低；基于DCT的压缩感知哈希算法采用目标的低频信息，跟踪过程很受目标背景环境的影响，所以刚开始就出现跟踪失败，之后偶尔跟踪上，但不能更新模板，跟踪基本失败；本文算法在跟踪过程中，基本上受到环境和遮挡物的影响很小，跟踪效果一直保持较好，由于自动更新模板，对目标的形变、遮挡具有很好的适应性。比较可知，本文算法在目标发生形变、有遮挡的情况下优于其他两种哈希算法。

实验3 汽车在公路上行驶，在汽车的影像大小发生变化且有遮挡的情况下进行目标跟踪。采用公开的CarScale视频进行实验，实验结果如图5所示。

图5 CarScale视频实验结果Fig.5 Experimental results of CarScale video

从实验截图中可以看出：传统哈希算法在目标影像大小变化不大时基本能跟踪上，随着目标影像逐渐变大，其跟踪算法基本上失效；基于DCT的压缩感知哈希算法受周围环境影响很大，其跟踪效果不好；而本文算法却有很好的鲁棒性，虽然跟踪框内有效信息的比例越来越小，仍能保持良好的跟踪效果。比较可知，本文算法在室外运动的场景中以及在目标发生形变、有遮挡的情况下表现均优于其他两种哈希算法。

为了定性地评判跟踪效果，采用了跟踪成功率这个指标，其定义为中心位置误差小于某一个阈值的帧数占视频总帧数的百分比。本文设置的阈值为18像素长。

根据以上3组实验，可以得出这3种跟踪算法分别在David，Girl和CarScale视频中的跟踪成功率，如表1所示。

表1 跟踪成功率

在运行每一个视频跟踪程序时，都输出了每帧匹配的时间，根据输出的数据可以统计出每一种算法在每个视频中的匹配时间，如表2所示。

表2 跟踪平均匹配时间

由表1可以清楚地看到，本文算法比其他两种哈希算法在跟踪成功率方面有提高；由表2可知，本文算法的匹配速度一般，但是基本上能满足视频跟踪要求。

5 结束语

本文提出了基于类间方差和离散余弦变换的模板匹配增强哈希目标跟踪算法，两种算法提取了目标的两种特征，优势互补，克服了其他哈希算法在复杂环境下目标发生形变、有遮挡物、光照发生变化等跟踪障碍，并在实验中取得了较好的效果。本文算法的综合性能较好，鲁棒性较强,提高了基于DCT的压缩感知哈希跟踪算法的成功率。但本文算法的跟踪框不能达到自适应，还有待改善。