一种融合感知哈希的快速压缩跟踪算法

简献忠，唐章源

(上海理工大学 光电与计算机工程学院 教育部及上海市现代光学系统重点实验室，上海 200093)

1 引 言

目标跟踪是计算机视觉领域中最热门的研究方向之一，被广泛的应用于智能汽车监管、目标识别和军事制导等领域.近年来，虽然许多目标跟踪的算法已被提出，但是可以有效解决光照变化、遮挡、形状变化、运动模糊、目标再出现等问题的鲁棒和快速的算法仍然是一个具有挑战性的问题.

压缩感知理论表明高维的数据可以通过随机矩阵映射到低维空间，而低维空间的数据包含了足够的信息用于重建原始高维数据.基于这个优点，压缩感知被广泛的应用于计算机视觉领域.Zhang等[1]提出了一种快速压缩跟踪(Fast Compressive tracking，FCT)算法，该算法提出了一种从粗到精的滑动窗口采样方式，使用一个非常稀疏的随机矩阵和积分图实现了图像的低维表示，再通过朴素贝叶斯分类器对目标和背景分类，实现目标的快速实时跟踪，但该算法仍存在一些缺陷.Chen等[2]提出多个稀疏测量矩阵方案并通过权重图选择最优测量矩阵的方法，提高了压缩感知在低分辨率或者小目标跟踪准确性；Chan等[3]提出融合局部敏感直方图的方式，改善了压缩感知跟踪算法的抗光照变化性能；Che fang等[4]提出Y通道采样Haar-like特征的方式，提高了压缩感知跟踪的精确度.但是，对于分类器参数盲目更新、目标尺寸变化和完全遮挡再出现的情况，还没有较好的解决方案.

感知哈希算法[5-7]在其他领域已经体现出了很好的效果，包括相似图片匹配，编码[8]等.近年来，得益于感知哈希算法计算量小的优点，它开始被应用于目标跟踪[9]领域.Fei等[10]提出一种基于感知哈希描述子的差分拉普拉斯算法，实现了目标的实时跟踪；Chen等[11]提出采用pHash特征代替haar-like特征，提高了跟踪的准确性.

针对快速压缩跟踪算法(FCT)分类器参数更新盲目、目标尺寸固定和未能跟踪目标完全遮挡再出现的问题，本文提出了一种融合感知哈希的快速压缩跟踪算法.该算法使用感知哈希匹配度实现目标尺寸自适应和约束分类器更新；同时对于上一帧没有检测到目标的情况，当前帧使用全图等间隔采样方式实现目标自找回功能.

2 快速压缩跟踪算法

快速压缩跟踪算法(Fast Compressive Tracking)是基于压缩感知理论和贝叶斯分类器的目标跟踪算法.算法对目标和背景区域提取多尺度Haar-like特征，利用高斯随机矩阵将其投影到低维空间获得压缩特征，进而构建朴素贝叶斯分类器.之后对输入的图像进行粗到精的方式采样，利用贝叶斯分类器找出响应值最高的样本视为目标.

2.1 压缩感知和测量矩阵

压缩感知(Compressive Sensing)[12]理论指出，通过稀疏矩阵R∈Rn×m可将高维数据向量x∈Rm用低维数据向量v∈Rn表示：

v=Rx

(1)

其中n≪m，x表示包含样本多尺度的所有Haar-like特征，v表示低维空间的压缩特征.FCT算法中，稀疏矩阵满足随机高斯矩阵、等距 (RIP)和计算量较小的特性，矩阵R(i，j)=r(i，j)满足如下要求：

(2)

2.2 朴素贝叶斯分类器的构建和更新

FCT算法采用朴素贝叶斯分类器分类目标和背景，从而实现目标跟踪.假设每个样本的压缩特征向量v=(v1，…，vn)∈Rn相互独立且先验概率相同，则分类器模型如下：

(3)

其中y=1代表目标，y=0代表背景.p(vi|y=1)和p(vi|y=0)都服从高斯分布，即：

(4)

(5)

(6)

(7)

3 感知哈希和改进快速压缩跟踪算法

3.1 图像样本感知哈希描述子生成

感知哈希(Perceptual Hashing)[13]是多媒体数据集到感知摘要描述的一类单向映射，主要用于音频处理、视频处理、图像处理等.感知哈希算法包含均值哈希和基于离散余弦变换(DCT)的哈希(pHash)两种方法.相比于均值哈希算法易受噪声等因素的影响，pHash算法采用DCT代表像素均值，使之更具鲁棒性，基本流程如图1所示.算法的具体步骤如下：

图1 图像样本生成感知哈希描述子示意图

1)输入图像样本并转换为灰度图；

2)将灰度图缩小或者放大为32×32像素的块，简化DCT的计算；

3)将像素块进行DCT变换，得到32×32的DCT系数矩阵；

4)选取系数矩阵左上角8×8大小区域构成低频系数矩阵，并计算低频系数矩阵的均值；

5)将低频系数矩阵中每个值与均值比较，小于均值记0，其他记1；

6)输出64维的感知哈希描述子.

3.2 感知哈希值匹配与目标尺寸自适应

汉明距离(Hamming distance)[14]是计算不同感知哈希描述子相似度的一种简单而有效方法.两个图像样本HP1、HP2的汉明距离计算如下：

(8)

其中⊕表示异或运算，HP1、HP2分别表示两个图像样本的感知哈希描述子，感知哈希描述子为64维的2进制数，h1、h2等于1或0，代表HP1、HP2中某1维2进制数值.公式表明d(HP1，HP2)越小，表示两个图像样本越相似，反之越不相似.

FCT算法使用固定不变的目标尺寸，这严重的降低了算法的稳定性和鲁棒性.当目标尺寸逐渐变大，算法所采集的样本会丢失目标特征；当目标尺寸逐渐变小，算法所采集的样本会引入过多背景成分.这两种情况都会降低分类器性能，进而造成跟踪漂移或丢失跟踪目标.

本文提出一种简单且快速的目标尺寸自适应策略，如图2所示.以当前帧检出响应值最高的样本p1为模块，分别取尺寸大小为p1的0.4、0.6、0.8、1、1.2、1.4、1.6倍的样本集S，计算S中每个样本与目标的汉明距离，若最小汉明距离小于阈值，对应样本s1的尺寸和位置视为目标当前帧的尺寸和位置，然后更新目标的感知哈希描述子.

图2 目标尺寸自适应示意图

3.3 约束分类器参数更新

FCT算法对分类器参数更新没有设置约束，从而导致跟踪过程容易出现跟踪漂移和目标丢失.对于目标被遮挡的情况，随着遮挡区域变大，采样样本包含的背景成分也将变多，此时更新分类器参数会逐渐增多背景特征的引入，造成跟踪漂移，当背景特征叠加较多时，造成目标丢失.

本文提出一种基于感知哈希匹配度约束更新分类器参数的策略，通过第t帧检出响应值最高的样本和第t-1帧的目标计算汉明距离，若汉明距离小于阈值T，则更新分类器参数，否则不更新.分类器参数更新公式如下：

(9)

(10)

3.4 全图等间隔采样的目标自找回策略

FCT算法采集样本是通过局部区域使用粗到精的滑动窗口方式，但是当上下两帧图像目标所在位置的距离差大于采样圆形的半径，就会发生跟踪漂移或者丢失目标.文献[15]提出一种三步搜索策略改善了样本采样方式，但是未能解决目标因完全遮挡后再出现的跟踪问题.

目标消失后再出现的因素是目标持续跟踪的难点之一.目标消失可以分为目标被背景遮挡、目标被其他目标遮挡和目标离开视线三种情况.目标被背景短暂的遮挡再出现是目标跟踪中较为常见的因素，常用的解决办法是采用卡尔曼滤波预测目标可以再出现的位置，然后对候选位置进行检测实现目标找回，但是这种方法鲁棒性不强且不适合用于找回目标长时间被背景遮挡的因素；目标被其他目标遮挡也可归结为多目标干扰因素，是其他非感兴趣的目标处于成像器件和感兴趣目标之间，导致遮挡感兴趣目标的成像，从而造成感兴趣目标消失；目标离开视线再回来因素因不知目标从哪个方位回到视线，所以基于历史信息预测目标再回来的方法将失效.

图3 目标自找回过程示意图

本文提出一种基于全图等间隔采样的目标自找回策略，以应对上一帧图像未检出目标的情况，如图3所示.该策略包括两个过程：首先选择合适的采样间隔d3，在全图进行等间隔采样，确保样本个数与粗采样一致，通过分类器得出响应值最高的样本a1；然后以a1中心为圆心，半径为r1的圆形区域，等间隔为1采样，得出响应值最高的样本s1视为最有可能是目标的样本，若样本与目标的汉明距离小于阈值，则视为目标.

3.5 算法流程

具体算法流程如下：

步骤1.读入起始帧图像并初始化参数.初始化当前帧有目标存在标识符Flag为真，汉明距离阈值T，采样区域半径r1、r2(r2

步骤2.初始化目标信息.设定目标中心位置gT、尺寸大小wT*hT，根据式(1)-(3)构建分类器B，根据3.1节的算法过程生成目标的感知哈希描述子PHT.

步骤3.读入下一帧图像，判断标识符Flag，如果为真，执行步骤4，否则执行步骤5.

步骤4.以gT为中心，采样半径为r1，采样间隔为d1，采集样本集A，接着执行步骤6.

步骤5.基于全图采样，水平采样间隔为d3x，垂直采样间隔为d3y，采集样本集A，接着执行步骤6.

步骤6.在低维空间中提取压缩特征，使用分类器B获得最大响应样本a1，其中样本中心为ga.

步骤7.以ga为中心，采样半径为r2，采样间隔为d2，采集样本集S，在低维空间中提取压缩特征，使用分类器B获得最大响应样本s1，其中样本中心为gs.

步骤8.以gs为样本中心，分别取k个不同尺寸大小的样本保存于样本集Q，根据3.1节的算法过程计算Q中每个样本的感知哈希描述子PHi，i=1，2…k；根据式(8)计算PHi与PHT的汉明距离，记最小汉明距离dmin(PHn，PHT)对应的样本为qn.

步骤9.若dmin(PHn，PHT)小于T，则更新目标信息(中心位置，尺寸大小，感知哈希描述子)，根据式(9)和式(10)更新分类器B参数，Flag设置为真；否则，不更新信息和参数，Flag设置为假.

步骤10.如果当前帧不是最后一帧，重复步骤(3)-步骤(9)；否则结束.

4 实验结果

为了验证PH-FCT算法的性能，选取5个图像序列进行结果验证，这些序列包含尺度变化、完全遮挡再出现、目标离开视线再回来和多目标干扰等具有挑战性的因素.实验环境为Intel Core i5四核处理器、2.7GHz主频、4GB内存、Windows7操作系统、开发平台为VS2013 + opencv2.4.10.实验结果与FCT算法进行比较.跟踪结果中实线和虚线框分别表示为PH-FCT与FCT算法的跟踪结果.

图4 飞机尺度变化跟踪结果图(plane3)

图4为plane3的跟踪结果，该序列包含飞机尺度变化的因素.在第1帧中，手动选择目标所在位置和尺寸大小.在第8帧时，目标成像尺寸变大，采用固定样本尺寸的FCT算法在更新分类器的时候开始出现少量的目标特征丢失，而采用目标尺寸自适应的本文算法检出过程更新了目标尺寸，再基于新的目标尺寸更新分类器参数，这样可以很好的保留目标特征.从第15帧可以发现，随着目标成像尺寸继续增加，FCT算法丢失的特征也在增加，此时仅基于目标的部分区域更新分类器参数，从而降低了分类器的性能；而本文算法因持续更新目标尺寸，可以很好的保证分类器中包含大多数目标特征.实验结果表明，本文算法对目标尺度变化的鲁棒性优于FCT算法.

图5为plane1的跟踪结果，该序列包含的飞机目标较大且有飞机完全遮挡后再出现的因素.在第1帧中，手动选择目标所在位置和尺寸大小.第28帧时，飞机开始进入云层，此时两种算法都可以跟踪到目标， FCT算法因目标遮挡开始出现跟踪漂移.第29帧时，云层完全遮挡了飞机，FCT算法因没有约束分类器参数所以将背景识别为目标并更新了分类器，而本文算法因为加入了约束条件，判断当前帧没有检测到目标，于是不更新分类器参数和目标信息，图像没有目标位置的标记.

图5 飞机完全遮挡后再出现跟踪结果图(plane1)

图6 飞机离开视线再回来跟踪结果图(plane4)

图6为飞机离开视线再回来的图像序列跟踪结果.在第1帧中，手动选择目标所在位置和尺度大小.第25帧时，飞机开始离开视线，此时两种算法都可以跟踪到目标.第31帧时，飞机完全离开视线，此时FCT算法丢失目标，将背景视为目标而更新分类器参数，本文算法没有检测到目标，图像没有目标位置的标记.第40帧时，飞机从另一个位置重新进入视线，

表1 算法运行时间比较

本文算法所采用的全图等间隔采样算法成功找回了目标并进行跟踪.实验结果表明，本文算法在目标遮挡方面的鲁棒性优于FCT算法.

为了测试PH-FCT的平均单帧处理时间及其与FCT算法比较实时性，选定上述5个飞机图像序列，通过多次(15次)运行测试序列后取平均值，结果如表1所示.

5 结 论

本文提出一种融合感知哈希的快速压缩跟踪算法.针对目标尺寸发生变化的问题，提出以分类器检出响应最强的样本中心为中心，采集不同尺寸的区域与目标计算感知哈希汉明距离，汉明距离最小的区域视为当前帧检出最有可能是目标的新尺寸和位置；针对分类器盲目更新的问题，设置汉明距离阈值，若当前帧检出最有可能是目标的样本与目标的汉明距离小于阈值，则更新分类器，否则不更新；针对目标完全遮挡再出现的问题，提出全图等间隔采样的目标自找回策略，设置采样间隔使样本数与目标未遮挡情况一致，使得目标出现后算法仍可继续跟踪.实验结果表明，PH-FCT算法具有较好的有效性、抗遮挡性和鲁棒性，且具备目标自找回能力.