基于嵌入式GPU的相关滤波跟踪算法改进及实现

徐 卓，康隽睿，袁 博，韩冬艳，党清新

(1 西安现代控制技术研究所，西安 710065； 2 西安科技大学管理学院，西安 710065)

0 引言

随着精确制导技术的快速发展，基于图像的目标跟踪技术成为了制导领域的一项关键技术。然而在实际使用场景中，目标跟踪任务存在以下重点和难点：1) 目标被局部或全部遮挡时，造成目标特征信息变化，导致目标丢失；2) 目标发生尺度变化时，跟踪框无法适应目标变化，导致出现跟踪到目标局部或背景；3) 当视场出现抖动，目标在搜索区域以外时，无法锁定目标，导致跟踪失败；4) 由于军事侦察、精确制导等领域的特殊性，对目标跟踪技术有着强实时性的要求，但是嵌入式设备计算能力相对较弱，在基于嵌入式设备的高速跟踪场景下表现差强人意，因此需要进行算法并行加速设计保证目标跟踪算法的运算速度。

目前目标跟踪算法中性能较好的主要有两类，分别是深度学习类算法和相关滤波类算法。深度学习类算法的主要特点是生成具有深层特征的跟踪器，极大地提高了跟踪精度，但由于其计算量大，对设备要求较高，很难在嵌入式设备上实现。相关滤波类算法诞生之初就以速度著称，这类算法将计算从时域转换到频域，很大程度减少了计算量，但相关滤波类算法在尺度变换、目标遮挡等方面仍有不足。

针对上述问题，对相关滤波跟踪算法进行深入研究，提出一种基于多尺度特征自适应更新的相关滤波跟踪算法，在特征提取阶段引入特征金字塔，实现对目标尺度变化的处理，在模型更新阶段引入自适应更新策略，判断目标遮挡及丢失状态，确保目标重入视场时的重新捕获，并在嵌入式图形处理器(graphic processing unit，GPU)上进行了算法加速，经过算法仿真，实验表明文中算法在目标遮挡及视场抖动情况下跟踪精度有明显提升，可以综合满足了跟踪精度和实时性的要求。

1 基于多尺度自适应更新策略的相关滤波跟踪算法

2014年Henriques等在相关滤波基础上提出了核相关滤波(kernelized correlation filter, KCF)算法，主要思想是利用相关滤波器对图像进行度量，衡量两个信号的相似度，如果两个信号越相似，那么其相关值就越高。而在目标跟踪领域的应用里，就是需要设计一个滤波模板，使得其作用在跟踪目标上时，得到的响应最大，得到的最大响应值位置就是目标的位置。

KCF相关滤波跟踪算法属基于背景学习的跟踪算法，基于背景学习的跟踪算法主要包括两大步骤：模型训练和目标判别。相关滤波跟踪算法采用循环矩阵来构造与目标具有一定差异的样本，而不是通过按照采样方式一个样本一个样本地在图像中裁取。在模型训练阶段，这样的构造方法能够通过矩阵运算避免大量数据的重复采集、存储、以及计算。在目标判别阶段，这样的构造方法能够避免判别样本单个逐一计算判别值，达到了预测目标位置的效果。相关滤波跟踪算法利用循环矩阵构造训练样本，并结合快速傅立叶变换，提高了跟踪速度；通过核函数对多通道的方向梯度直方图(histogram of oriented gradient, HOG)特征进行融合，提高目标跟踪的准确率。算法流程如图1所示。

图1 相关滤波跟踪算法流程图

KCF算法基于相关滤波跟踪框架设计，跟踪精度和跟踪速度均有较好的表现，但由于其模板更新策略为逐帧更新，且有搜索区域的限制，当目标的尺度发生变化、目标被局部或全部遮挡、视场发生剧烈抖动时跟踪精度会极度下降，容易导致目标丢失，因此，需要对其模板更新策略及目标搜索策略进行优化，提升算法跟踪性能。

1.1 目标遮挡优化

由于相关滤波跟踪算法的目标模板基于实时更新策略进行更新，因此当目标被遮挡时，很容易将遮挡物误认为目标。针对这一问题，要及时在目标被遮挡时停止更新模板，同时扩大搜索区域，以在遮挡结束时快速找到目标。因此，需要在算法中添加目标是否被遮挡的判断。

相关滤波跟踪算法将学习到的目标特征滤波器与当前帧特征图进行卷积处理得到响应图如图2所示。图中轴、轴分别表示特征图的两个维度，轴表示特征图中该点的响应值。响应图中的响应极大值点代表当前帧特征图与目标特征滤波器最相似的点，其值表征了二者的相似程度。当跟踪目标未受到遮挡时，目标的检测响应与二维正态分布类似，响应最大点为图2(a)中响应图最高点，响应极大值在0.2左右；而当目标被遮挡时，响应最大点为图2(b)中的响应图最高点，响应极大值在0.1左右，同时周围点的响应值升高，在图中表现为主响应峰周围出现其他响应峰。

因此，可以用响应极大值的变化来判断目标是否被遮挡，但针对不同目标其响应极大值差距较大，因此不能直接使用阈值来进行判断。通过标准差来衡量当前跟踪结果的置信度，分析响应图的峰值分布，对当前帧是否被遮挡进行评估，具体算法如下：

1)从当前帧中提取个相关响应，并记录响应值()及其出现概率()。

2)计算个响应值的期望：

(1)

式中：()为第个响应值；()为第个响应值出现的概率。

3)使用标准差计算当前跟踪结果的置信度：

(2)

4)将与阈值进行比较，如果>阈值，则判定跟踪正常，继续更新跟踪模型参数；如果<阈值，则判定目标被遮挡，停止更新跟踪模型参数。

图2 目标响应图

1.2 尺度变化优化

在目标跟踪场景下，由于目标会有相对相机的轴向运动，因此随着目标与相机的位置变化，在成像时尺度变化。然而原始的KCF算法跟踪窗口的大小是固定的，当目标尺度变大时，会导致跟踪目标的局部特征，导致跟踪位置偏移；而当目标尺度缩小时，会引入过多的背景信息，导致跟踪精度降低。因此，需要引入多尺度信息来应对目标的尺度变化。

考虑到跟踪算法的实时性，提出一种快速尺度估计算法。根据目标尺度变化情况设定1.3、1.1、1、0.9、0.7五个尺度，在下一帧图像中提取5个尺度的目标框，将5个尺度的目标通过双线性插值缩放为模板尺寸，并分别进行特征提取及互相关矩阵计算，将响应值最大的尺度确定为新的目标尺度。计算流程如图3所示，其中，…，，…，分别为不同尺度的输入图像，，…，，…，分别为不同尺度的输出特征图。

图3 尺度变化策略

1.3 视场抖动优化

相关滤波跟踪算法在目标周围邻域内进行目标的匹配和判别，然而当视场出现抖动时，目标的帧间位移变大，使目标位置跳出搜索区域，导致无法匹配到目标，跟踪失败。针对此类问题，提出一种分阶段目标搜索策略。

1)当目标占据视场比例较小时(≤10像素×10像素)，轻微抖动(帧间像素偏差≥25像素×25像素)即会导致跟踪框丢失，将目标及其周围背景作为搜索对象，提取目标及其周围背景的特征进行判别，根据响应极大值判断目标是否丢失，当目标出框时停止更新模板，并扩大搜索区域进行目标的重捕。

2)随着相机逐渐接近目标，当目标扩大至50像素×50像素时，采用角点检测算法对跟踪区域进行处理，对目标及背景进行区分，实现对目标的重定位，同时对目标中心点位置进行确定，解决跟踪末端的中心漂移问题。

2 基于嵌入式GPU的跟踪算法加速

2.1 相关滤波跟踪算法并行性分析

嵌入式GPU基于统一计算设备架构(compute unified device architecture, CUDA)提供了并行计算支持，利用嵌入式GPU具备的多线程优势，可以同时对大量数据进行计算。将图像获取、显示等逻辑部分在中央处理器(central processing unit，CPU)上进行处理，将特征提取及核相关计算放到并行计算能力强大的嵌入式GPU中实现。相关滤波跟踪算法的CUDA实现处理流程如图4所示。

图4 相关滤波跟踪算法CUDA实现处理流程

相关滤波跟踪算法主要包括目标检测和模型训练两部分，检测部分主要在图像搜索区域内进行多模板特征提取，并与模型训练参数进行互相关匹配，当响应极大值超过一定阈值时，确定目标位置，实现目标跟踪。训练部分需要提取匹配到的目标特征，并进行特征的自相关计算，将计算结果更新到模型参数中。

目标检测和模型训练的主要计算步骤具有很大的相似性，可以总结为5个部分：图像提取、特征提取、FFT变换、核相关计算、模型训练。为统计算法各部分耗时，使用Visual Studio 2015软件对相关滤波跟踪算法进行了实现，并对各部分函数耗时进行了统计，统计结果如图5所示。

图5 相关滤波跟踪算法耗时分析

整体程序主要耗时在特征提取及核相关计算部分，其中特征提取函数getFeatures占据总体耗时的16.4%，核相关计算函数gaussianCorrelation占据总体耗时的11.4%，因此，基于嵌入式GPU重点对特征提取及核相关计算两个部分进行并行加速。

2.2 HOG特征提取并行加速

HOG特征的提取步骤为：计算梯度值、计算各梯度方向权值、计算Block的梯度直方图、对梯度特征图进行标准化和阈值截断、进行特征图降维，得到31维的PCA-HOG特征。完整的HOG特征的求解过程如图6所示。

图6 HOG特征提取流程图

进行HOG特征提取时，梯度方向和幅值的计算、梯度图标准化、阈值截断、特征图降维等都是逐像素计算的过程，都可以直接使用CUDA进行加速；统计梯度直方图部分需要进行累加操作，对并行计算的同步性有一定要求，因此采取并行规约的方式进行计算。

在计算过程中，需要建立线程到像素点的一一映射，给每个线程分配一个固定内存位置的像素进行处理，线程块、线程和图像的对应关系如图7所示。

图7 线程块、线程和图像对应关系

每个线程格执行不同的程序，由多个线程块组成。线程块里包含多个线程，为了适配目标跟踪算法，将线程块设置为有二维的线程组成。线程是最小的处理单元，每个线程处理一个像素点的计算。GPU调度线程的最小单位是16个线程，因此将每个线程块中线程的数量设置为(16，16)。设图像的宽度为，高度为，则线程格中线程块的数量为((+16+1)16,(+16+1)16)。建立好二维的线程格后，可以通过线程的索引映射到图像中的每个像素点，计算方式为：

(3)

式中：、为像素点索引；、为线程索引；、为线程块索引；、为线程块尺寸。

介绍了图像块与线程的映射方案以及线程的索引方法后，各个部分的关键点为：

1)梯度计算

进行梯度计算时，需要分别对当前像素点的梯度幅值及方向进行计算，并根据梯度方向的计算结果，将该点划分到对应的区间中。由于各个像素点的梯度计算与其他点的结果没有相关性，因此可以直接使用GPU进行并行计算。

2)计算梯度方向直方图

图8 并行归约示意图

经过并行归约，可以实现累加操作的部分并行，相比于串行操作的次累加，并行操作可以将累加速度提升8倍。

3)梯度图归一化和阈值截断

对××27的梯度直方图进行归一化，使用×个线程对包含当前元胞的4个线程块进行操作。首先分别计算每个线程块(除去边界)的前9维无符号方向特征向量的平方和，然后分别计算每个线程块在各个方向上的前9维无符号方向特征向量的2-范数，之后用各个属性(共27维)除以包含当前元胞的4个线程块的2-范数，得到归一化的27×4个属性，每个线程仅处理当前元胞内部的16个点，由于不存在访存冲突的问题，可以直接进行计算，得到××27×4维的特征图，然后根据设定的阈值进行阈值截断。

4)特征图降维

使用主成分分析进行特征降维，将108维的特征图压缩为31维，仍然以元胞为单位进行处理，每个线程进行一个元胞的特征压缩，对有符号梯度方向的18维向量分别做累加求和得到4维纹理特征，得到归一化后的无符号方向特征、有符号方向特征向量和纹理特征向量后，一次存储到全局内存中，得到31维HOG特征。

2.3 核相关计算并行加速

核相关计算是将当前目标特征图与模板目标特征图进行相关计算的操作，评估当前目标与原始目标的相似度。在进行处理时，需要先将特征图通过快速傅里叶变换(fast fourier transform，FFT)转到频域，求得响应图，之后再通过FFT逆变换转回时域。

FFT变换在总时间中占比很大，在目标检测阶段需要进行的是二维傅立叶变换，使用CUDA加速FFT时，直接调用CUDA提供的函数cufftExecC2C及cufftExecC2R进行傅立叶正变换及傅立叶逆变换。在求解响应图时，需要对两张特征图进行对应点乘操作，可参照HOG特征提取部分，建立线程到图像的一一映射关系，使用多线程进行并行计算。

3 实验分析

3.1 跟踪性能分析

为评估算法的跟踪精度，在嵌入式平台上对算法进行验证，部分结果如下：

1)目标遮挡效果

如图9所示，视频第126帧时正常跟踪目标，第135帧时目标开始被局部遮挡，此时算法模板停止更新，开始扩大搜索区域进行目标搜索，第142帧时目标被完全遮挡，第149帧当目标重回视场后，实现对目标的重新捕获。

图9 目标遮挡测试

2)尺度变化

如图10所示，视频第370帧中初始目标尺寸为11×11，第1 482帧中目标尺寸为174×174，目标尺度变化达到10倍，本算法仍能稳定跟踪目标。

图10 尺度变化测试

3)视场抖动

图11中，目标大小为8×8，515帧到520帧之间出现目标连续4帧丢失，丢失时相邻帧目标偏差像素数达到20，相邻3帧最大偏差像素数35，已经超出了原始相关滤波算法的搜索区域，此时算法开始逐渐扩大搜索区域，经过4帧后实现了对目标的重新捕获。

图11 视场抖动测试

3.2 加速效果分析

实验使用Nvidia TX2开发板进行测试，实验环境如表1所示。

表1 实验环境

实验选取了图像尺寸和目标框尺寸不同的5组视频进行测试，实验结果如表2所示。

表2 测试结果

从实验结果可以看出，GPU相比于CPU的加速比在3.3～4.1之间。一般情况下，图像块尺寸越大，加速比越大。实验结果表明，使用GPU加速KCF算法效果明显，对比原算法各个模块的执行时间、整体的帧率及时延均得到大幅改善，测试视频中帧率均达到了50 帧/s，能够实现高速实时的目标跟踪。

4 结论

传统相关滤波算法尺度单一、模板更新策略简单、搜索区域固定，因而在目标尺度变换、目标遮挡、视场抖动情况下跟踪效果不佳。针对上述问题，提出多尺度下特征自适应更新的相关滤波算法，通过多尺度框架对目标进行尺度缩放，基于响应极大值的标准差来判断目标被遮挡情况，当目标发生遮挡时停止模板更新，扩大搜索区域进行目标的重新捕获。同时将改进后的算法在嵌入式GPU上进行了实现，对算法进行并行加速，达到了平均4倍的加速比，极大地提高了跟踪算法的效率，在嵌入式设备上达到了50 帧/s以上的跟踪速度。

对改进相关滤波算法进行了验证，结果表明文中算法在尺度变化、目标遮挡、视场抖动等方面均表现良好，提升了相关滤波算法的应用价值，为目标跟踪在实际应用中提供了可靠有效的现实方案。