模板匹配跟踪的哈希增强算法

徐　珩　贺飞越

(昆明理工大学国土资源工程学院　云南 昆明 650093)



模板匹配跟踪的哈希增强算法

徐珩贺飞越

(昆明理工大学国土资源工程学院云南 昆明 650093)

摘要基于平方差匹配SSD(Sum of Squared Difference)、标准相关系数匹配NCC(Normalized Cross Correlation)的传统模板匹配跟踪算法十分依赖灰度信息。图像灰度剧烈变化或光照强度改变明显的情况下容易被图像的高频信息影响，导致产生目标偏移的现象，跟踪精度降低。提出一种模板匹配跟踪的哈希增强算法，用于减小灰度与亮度变化的影响，增强目标跟踪的精度。其具体过程是：以感知哈希提取感知特征，对提取的特征二值化生成跟踪目标的哈希序列；将哈希序列作为匹配跟踪的模板，通过比较汉明距离在每一帧中寻找最为相似的目标以达到跟踪的效果；运用抽屉原理缩短汉明距离比较的时间。给出一种基于汉明距离的自适应模板更新算法，保证了跟踪的连续性。仿真实验结果与基于SSD、NCC的模板跟踪算法比较，在目标灰度或亮度变化情况下匹配精度高出一个数量级，跟踪速度能够满足实时性需求。

关键词哈希增强模板匹配目标跟踪汉明距离

0引言

基于模板匹配的跟踪方法原理简单、便于实现，因此得到了广泛应用。模板匹配一般分为基于特征提取的方法以及基于灰度值的方法。基于特征提取的模板跟踪算法，如小波变换法[1,2]、SIFT特征提取算法[3,4]等，具有尺度不变性与仿射不变性，抗干扰能力较强，特别是小波特征可实现图像的多尺度分解匹配[5]。但一般包含特征提取和特征匹配两部分，涉及大量的几何与图像形态计算，运算量大，没有一般模型可参考。基于灰度值的模板跟踪算法[6-13]简单易行，有通用的数学模型对匹配进行误差估计、相似程度判定，如文献[6]对平方差匹配SSD进行了改进，使模板动态更新，并通过对数极坐标变换减小旋转与比例变化带来的影响；文献[7]介绍了一种快速的模板匹配跟踪算法。原理是通过粗糙到精细的方法CTF(Coarse to Fine)，先将图像分成若干区域，选出所含像素属于区域边界线的区域，再对这些精选区域进行标准相关系数匹配NCC或序贯相似性检测算法SSDA(Sequential Similarity Detection Algorithm)来达到模板匹配的效果。

以上基于灰度的模板跟踪方法都较为依赖灰度信息，图像灰度剧烈变化或光照强度改变明显的情况下容易被图像的高频信息影响，导致产生目标偏移的现象，跟踪精度降低。本文针对上述基于灰度值的模板跟踪算法的缺陷，采用跟踪目标的低频信息，通过感知哈希提取跟踪目标的感知特征，增强跟踪目标的轮廓结构，并对提取的特征进行二值化生成跟踪目标的哈希序列；将跟踪目标的哈希序列作为跟踪模板，在每一帧中寻找最为相似的目标；运用抽屉原理缩短汉明距离比较的时间，加快匹配速度；在匹配成功后对模板进行更新，提出一种基于汉明距离的自适应模板更新算法，保证了跟踪的连续性。

1哈希增强

图像感知哈希函数[14]能够考虑图像在视觉领域的变化，并且能够捕捉基本的感知属性。从理论上说，视觉内容相同的信息产生相同的感知哈希值，视觉内容不同的信息产生不同的感知哈希值[15]，记图像感知哈希函数为PH：

PH:I→Hp

(1)

图1　图像感知哈希的一般生成步骤

其中I为图像在计算机中的数字表示序列所构成的集合，Hp是感知数字摘要的集合，即感知哈希值，通过对感知特征降维得到。图像感知哈希函数是由图像数据到感知摘要集的单向映射，其一般生成步骤如图1所示，数字图像通过一系列操作能够得到哈希序列。因此，将匹配目标的感知哈希序列作为模板，与搜索区域内其他图像的哈希序列比较，若两个哈希序列之间的感知距离在规定范围内则认为匹配成功，反之则为匹配失败。

1.1低频信息提取

一张图片就是一个二维信号，它包含了许多不同频率的成分。这里的高频和低频指的是图像的空间频率，所谓的空间频率是指特定频率在单位间距内重复的次数，图像细节越精细，单位间距内重复的次数越多，频率就高；反之，则越低。换句话说，高频部分主要是对图像边缘和细节的度量，对应的是亮度或灰度变化剧烈的区域，如物体的纹理，提供图像的详细信息。而低频部分主要是对整幅图像强度的综合度量，提供图像的一个轮廓框架。

为了减小图像灰度与亮度变化的影响，需要将图像转换到频域空间，选取重要的低频频域，丢弃影响低的高频频域。考虑到需要保留图像的低频信息，本文使用离散余弦变换DCT来获取图像的低频成分。离散余弦变换是与傅里叶变换相关的一种变换，经常被信号处理和图像处理使用，用于对信号和图像进行有损数据压缩。这是由于离散余弦变换具有很强的能量集中特性，大多数的自然信号的能量都集中在离散余弦变换后的低频部分。图2是对图像进行离散余弦变换的结果，可以看到经过变化后图像的能量几乎都集中在左上角的低频系数上，而越到右下方的高频系数能量越小。

图2　灰度图像的离散余弦变换

因此，可以对图像进行离散余弦变换后提取左上角的部分来降低图像的频率。为了简化离散余弦变换的计算，将选定的跟踪目标图像I(x，y)缩小为32×32的尺寸；接着将缩小后的图像转化为灰度图像G(x，y)进一步减少计算量；之后对G(x，y)进行离散余弦变换，N×N的图像进行离散余弦变换如式(2)所示：

(2)

其中：

u=1，2，…，N-1;v=1，2，…，N-1；F(u，v)是变化系数矩阵；u、v为频率域采样值；x、y为空间域采样值。

计算出32×32的离散余弦变换系数矩阵F(u，v)后，只需保留左上角的8×8矩阵f(x，y)，这部分图像呈现了整个图像中的最低频率，也是最重要的部分。接着将变化系数矩阵还原成灰度图像，需要用到逆离散余弦变换IDCT(Inverse Discrete Cosine Transform)，其效果如图3所示。

图3　灰度图像的逆离散余弦变换

对f(x，y)进行逆离散余弦变换，公式如下：

(3)

得到大小为8×8的跟踪目标低频分量g(x，y)，即跟踪目标最重要的部分。

1.2差异增强

图像均值对于目标跟踪有一定的贡献，但SSD与NCC方法受图像均值的影响非常大。图像颜色非线性比例变化导致图像均值改变会造成跟踪精度下降，需要考虑减小图像均值的影响。

图像灰度变化较大的边沿区域梯度值较大，灰度变化平缓的区域梯度值较小，而在灰度均匀的区域梯度值为零。一般图像增强过程使用图像的灰度变化梯度提取边缘，将梯度值大的像素设置为0，梯度值小的像素设置为1就可以强化边缘。为了简化计算，本文使用一种类似梯度但是更快速的差异增强方法：计算相邻两像素间的灰度值差异，当差异大于一定阈值时，将左侧像素设置为0；反之，将其设置为1，该方法能够更加快速地得到图像的轮廓结构信息。

将1.1节中得到8×8的图像低频信息g(x，y)，按行自第一个像素开始与下一元素进行比较，计算相邻像素的差异δg：

(4)

其中i=0，1，…，6；j=0，1，…，7；τ为预先设定的阈值，对于灰度图像一般取τ=5。对每一行的相邻像素点进行比较，若左侧与右侧像素灰度值之差大于等于τ，将它们的差异值设为1，否则设为0。将式(4)得到的56个相邻像素灰度差异值δg保存为8×7的矩阵。

1.3哈希序列生成

式(4)得到的差异值矩阵δg完全消除了图像均值的影响，但图像均值对于目标跟踪仍有一定的贡献。考虑到图像每一行像素与图像整体的相关性，计算g(x，y)每行均值μj与g(x，y)整体均值μ的差异δμ：

(5)

H=[δgδμ]

(6)

将δg与δμ横向合并得到8×8的矩阵H按照从左到右从上到下的顺序二进制保存，生成跟踪目标哈希增强后的64位感知哈希序列。

哈希增强利用DCT变换提取图像低频信息，确保图像重要信息的保留。通过差异增强抑制图像灰度均值的影响，同时加强图像每行像素与图像整体的相关性，最终得到基于感知特征的64位哈希序列。哈希增强能够良好地适应跟踪目标灰度或亮度剧烈变化的影响，其计算出的感知哈希值不会改变。

2基于哈希增强的模板跟踪

2.1模板匹配

第一帧得到跟踪目标的感知哈希序列，随后对目标进行跟踪。将目标的感知哈希序列视为目标模板，对之后每一帧通过扫描上一帧目标周围图像区域，计算每个搜索窗口图像的感知哈希序列，寻找最接近目标感知哈希序列的窗口。使用汉明距离表示感知哈希值的相似度：

(7)

考虑到跟踪目标可能发生的变化，将与目标模板汉明距离在7以内的搜索窗口图像视为候选跟踪目标，汉明距离超过7的视为非跟踪目标。如图4所示，图中一个方块代表4位，黑色区域表示x与x′不同的部分，白色区域表示相同的部分。根据抽屉原理将64位哈希序列平均分为8段子序列，若汉明距离不超过7，说明匹配的两串哈希序列之间至少有一段子序列是完全相同的。因此若搜索窗口内图像的哈希序列x′与模板x没有任何一段子序列完全一致，则可视为此搜索窗口没有匹配到跟踪目标，继续计算下一个搜索窗口的感知哈希序列；若至少有一段子序列完全一致，再对其他子序列计算汉明距离；若汉明距离不超过7，保存为候选目标；如此循环最终找到汉明距离最小的候选目标，即为最终匹配目标。

图4　汉明距离的快速对比

2.2模板自适应更新

通过计算汉明距离找到与目标模版最为相似的搜索窗口，即当前帧匹配窗口。为了适应目标的变化，需要动态更新目标模板。

设当前帧模板为M，当前帧匹配目标为T，更新后的模板为M′，模板更新的基本公式如下：

M′=αT+(1-α)M

(8)

其中α为更新参数，α = Dh/ n，Dh为当前帧的模板M与匹配目标T之间的汉明距离，Dh∈[0，7]，n=max(Dh+ 1)，即Dh的可能取值个数。α取值与当前帧匹配窗口与目标模版感知哈希序列的汉明距离成正比。Dh大，则M与T的差异大，跟踪目标发生了一定的变化，T的权重α大；Dh小，则M与T差异小，跟踪目标基本无变化，T的权重α小。将α = Dh/n代入式(8)得：

(9)

模板更新公式可根据当前帧模板M与匹配目标T间的汉明距离进行自适应调整。实验结果表明，模板更新的自适应调节能够良好地适应跟踪目标的灰度或亮度变化，提高跟踪的精度以及鲁棒性。

2.3算法过程

整个实验的算法过程如图5所示。首先在输入视频中选取跟踪目标，利用离散余弦变换DCT提取目标的低频信息；通过图像感知哈希增强生成跟踪目标的哈希序列；在目标周围区域进行扫描，通过比较汉明距离寻找感知哈希序列与跟踪目标最接近的扫描窗口，也就是该帧的目标所在位置；最后为了适应目标的变化，在成功跟踪后每一帧都要更新跟踪的目标。

图5　模板匹配跟踪的哈希增强算法步骤

输入：一组视频序列，跟踪目标的坐标

输出：跟踪结果的坐标

1) 输入视频序列，选取跟踪目标I(x，y)；

2) 将I(x，y)转化为灰度图像G(x，y)，并根据式(2)计算离散余弦变换系数矩阵F(u，v)；

3) 选取F(u，v)左上角8×8矩阵f(x，y)，根据式(3)得到跟踪目标的低频分量g(x，y)；

4) 根据式(4)得到g(x，y)相邻像素灰度差异值δg，根据式(5)得到g(x，y)每行像素与整体均值的差异δμ，之后根据式(6)得到模板的哈希序列H；

5) 根据式(7)计算模板哈希序列H与搜索区域内其他窗口图像的哈希序列H′的哈希距离Dh，若得到哈希距离最小的窗口坐标，且Dh≤7，即为跟踪目标的坐标，进行步骤6；若Dh>7，则结束跟踪；

6) 将I(x，y)与Dh代入式(9)，得到更新后的模板I((x，y)，转至步骤2。

3实验与分析

为了验证本文提出的模板匹配跟踪的哈希增强算法的跟踪效果，将其用于对人脸的跟踪，与基于SSD和基于NCC的模板跟踪方法比较。实验一数据为自摄视频序列，实验二与实验三数据源于Visual Tracker Benchmark的David视频(https://sites.google.com/site/trackerbenchmark/benchmarks/v10)，包含存储目标真实位置的groundtruth_rect.txt文件。

实验环境：处理器Intel Core i7 2.10 GHz，内存4 GB RAM，显卡NVIDIA NVS 5400M，开发软件采用VS 2010和Windows 7系统，用到软件开发库为Opencv 2.4。

实验一是对静止背景下灰度亮度变化微小的目标跟踪。在分辨率为640×480像素、背景稳定且光照不变的视频序列中，跟踪一张大小为193×179像素的移动人脸，选取第20、40、70和80帧作为参考，如图6所示。可以看到，在视频的前40帧三种方法都能较好地跟踪目标；从第70帧起，SSD跟踪产生了一定的偏移，而NCC与本文方法则能准确地跟踪目标。相对于目标真实位置，平均每帧SSD模板跟踪偏移30个像素，NCC模板跟踪偏移16个像素，本文方法则仅偏移9个像素，可见NCC模板跟踪与本文方法均能在静止背景下良好地跟踪灰度与亮度变化微小的目标。

图6　静止背景下三种算法跟踪结果

实验二是对复杂背景下灰度亮度变化剧烈的目标跟踪。如图7所示，视频序列分辨率为640×480像素，背景保持变动并且光照变化明显，一个面部尺寸为80×85像素的行人面对移动的手持摄像机快速地不规则走动，同时摘下眼镜后再戴上，跟踪目标的灰度与亮度均产生剧烈的变化。分别选取视频序列的第30、110、167、311以及398帧作为参考，可以看到视频前30帧三种方法均能准确地跟踪目标，之后到110帧附近时SSD与NCC方法跟踪已经产生偏移；从第167帧跟踪目标开始摘下眼镜起，到第311帧目标重新戴上眼镜，SSD与NCC方法跟踪的偏移量十分巨大，已经无法进行精确跟踪；而本文方法从始至终十分精准地跟踪目标。实验二中SSD与NCC方法平均每帧偏移35与30个像素，跟踪精度大幅降低，不能准确跟踪目标；本文方法平均每帧偏移3个像素，能在复杂背景下精准地跟踪灰度亮度变化剧烈的目标。

图7　复杂运动情况下三种算法跟踪结果

实验三为室外场景下对运动目标的跟踪。如图8所示，频序列分辨率为640×480像素，跟踪场景为室外小路；跟踪目标为慢跑的路人，大小为55×185像素。选取视频序列的第40、78、165以及221帧进行比较，可以发现随着时间的推移，SSD方法偏移量逐渐增大，到221帧时只能跟踪住目标的半个身体；NCC方法能够较为准确地跟踪目标，但跟踪窗口也逐渐偏移；本文方法则自始至终能够精确地跟踪目标。相对于目标真实位置，平均每帧SSD模板跟踪偏移37个像素，NCC模板跟踪偏移11个像素，本文方法则仅偏移8个像素，可见本文方法能在室外背景下良好地跟踪运动的目标。

图8　室外场景下三种方法目标跟踪结果

通过手工获取实验一视频中目标真实位置，实验二与实验三视频中目标真实位置从groundtruth_rect.txt文件得到。表1中陈列了三种方法跟踪的目标与目标真实位置的平均差与标准差，三种方法的跟踪速度则在表2中可见。

表1　三种算法跟踪的平均差与标准差(像素)

表2　三种算法跟踪的平均匹配时间

从表1能够看出，本文提出的哈希增强方法跟踪精度高于SSD与NCC方法，拥有距目标真实位置最小的平均差与标准差，跟踪精度比SSD与NCC方法高出一个数量级。通过分析表2发现，哈希增强方法的运行速度与SSD方法接近，高于NCC方法，能满足实时性跟踪的要求。综合两种因素考虑，本文提出的哈希增强方法表现最为优异。

4结语

传统基于灰度值的模板跟踪算法对图像的灰度与光照变化极为敏感，影响了跟踪的适用范围和效果。针对以上缺点，本文提取跟踪目标的低频信息，运用哈希增强的方法生成跟踪目标的哈希序列；计算哈希序列的汉明距离匹配跟踪目标，并使模板自适应更新。经实验证明，本文算法有效克服了目标灰度与光照变化对图像均值带来的影响，达到更好的跟踪效果。图像的整体结构保持不变，其计算出的感知哈希序列就不会变化，增强了对跟踪目标灰度亮度变化的适应性，提高了跟踪精度。若跟踪目标整体结构变化，跟踪精度会有所下降，速度也会有所下降，解决这些问题是今后研究的方向。

参考文献

[1] Singh R,Purwar R K,Rajpal N.A better approach for object tracking using dual-tree complex wavelet transform[C]//2011 International Conference on Image Information Processing (ICIIP 2011),2011:1-5.

[2] Qi Zhang,Jinlin Zhang,Ting Rui.Target Tracking Based on Wavelet Features in the Dynamic Image Sequence[C]//2011 Sixth International Conference on Image and Graphics (ICIG),2011:811-815.

[3] Haopeng Li,Flierl M.Sift-based multi-view cooperative tracking for soccer video[C]//2012 IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP),2012:1001-1004.

[4] Kai Du,Yongfeng Ju,Gang Li,et al.Object tracking based on improved MeanShift and SIFT[C]//2012 2nd International Conference on Consumer Electronics,Communications and Networks(CECNet),2012:2716-2719.

[5] Cho H J,Park T H.Template Matching Method for SMD Inspection using Discrete Wavelet Transform[C]//2008 SICE Annual Conference,2008:3198-3201.

[6] Qiang Zhu,Kwangting Cheng,Hongjiang Zhang.SSD Tracking Using Template and Log-polar Transformation[C]//Fifth International Conference on Multimedia and Exposition,2004:723-726.

[7] Sahani S K,Adhikari G,Das B K.A Fast Template Matching Algorithm for Aerial Object Tracking[C]//2011 International Conference on Image Information Processing (ICIIP 2011),2011:1-6.

[8] Di Caterina G,Soraghan J J.Adaptive Template Matching Algorithm Based on SWAD for Robust Target Tracking[J].Electronics Letters,2012,48(5):261-262.

[9] Hager G D,Dewan M,Stewart C V.Multiple Kernel Tracking with SSD[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2004:790-797.

[10] Schreiber D.Robust Template Tracking with Drift Correction[J].Pattern Recognition Letters,2007,28(12):1483-1491.

[11] Zhen Jia,Balasuriya A,Challa S.Target Tracking with Bayesian Fusion Based Template Matching[C]//2005 International Conference on Image Processing (ICIP 2005),2005:826-829.

[12] 任仙怡,廖云涛,张桂林,等.一种新的相关跟踪方法研究[J].中国图象图形学报,2002,7(6):553-557.

[13] 朱永松,国澄明.基于相关系数的相关跟踪算法研究[J].中国图象图形学报,2004,9(8):963-967.

[14] Venkatesan R,Koon S M,Jakubowski M H,et al.Robust Image Hashing[C]//2000 International Conference on Image Processing (ICIP 2000),2000:664-666.

[15] 牛夏牧,焦玉华.感知哈希综述[J].电子学报,2008,36(7):1405-1411.

收稿日期：2015-01-13。国家自然科学基金项目(41161061，4090 1197)。徐珩，硕士生，主研领域：图像模式识别。贺飞越，硕士生。

中图分类号TP391.41

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.039

HASH ENHANCEMENT ALGORITHM FOR TEMPLATE MATCHING TRACKING

Xu HengHe Feiyue

(FacultyofLandResourceEngineering,KunmingUniversityofScienceandTechnology,Kunming650093,Yunnan,China)

AbstractTraditional template matching tracking algorithms based on sum of squared difference (SSD) and normalised cross-correlation (NCC) depend on grey information very much. In circumstance of dramatic greyscale change or significant illumination intensity variation in image, they are prone to be affected by high-frequency information of the image and this leads to the phenomenon of target drifting followed by the decrease in tracking accuracy. We proposed a hash enhancement algorithm for template matching tracking used to reduce the impacts of greyscale and luminance variations, and to enhance the tracking accuracy as well. The specific progress is as follows: It extracts the perceptual features of the target with perceptual hashing, and binarises the extracted features to generate hash string of the tracking targets. Then it saves the hash string as a template of matching tracking, by comparing the hamming distances it searches the most similar targets from each frame so as to reach the effect of tracking. By using drawer principle it shortens the time of hamming distances comparison. We also proposed a hamming distance-based adaptive model updating algorithm which guarantees the continuity of tracking. Comparing the results of simulative experiments with SSD-based and NCC-based template tracking algorithms, the matching accuracy reaches an order of magnitude higher in the case of target’s greyscale and luminance varying. What’s more, the tracking speed is able to meet the requirement of real-time property.

KeywordsHash enhancementTemplate matchingTarget trackingHamming distance