基于GMS与FPME的视频目标跟踪方法

张海涛，秦鹏程

（辽宁工程技术大学软件学院，辽宁葫芦岛125105）

0 概述

视频目标跟踪是当前计算机视觉领域的热门研究课题，在民用和军事的众多场景中有着广泛的应用［1-3］，而对目标特征点的提取和匹配是视频跟踪中的一项重要步骤［4-5］。视频跟踪中存在诸多影响因素，如尺寸变化、角度变化、光照变化、背景物杂乱、噪声、遮挡干扰等，这增加了特征点错误匹配对准的概率，极大地影响了后续视频跟踪的效果。因此，如何快速有效地剔除误匹配特征点以提高匹配精度，成为一项值得研究的问题。

当前对于误匹配特征点的剔除方法研究在点云配准［6］、三维对象识别［7-8］等方面应用较为广泛。文献［9］利用基于迭代最近点（Iterative Closest Point，ICP）的精确配准技术对前期误匹配结果进行后期校准，但是该算法过于依赖较为准确的初始姿态估计，且存在计算量大、耗时较长、收敛慢等问题。文献［10］在尺度不变特征转换（Scale Invariant Feature Transform，SIFT）算法的基础上增加了区域重叠核加权Hu 矩，将相似度较小的匹配点剔除掉，然而SIFT算法［11］需要建立高维度复杂的描述子，占用了大量的内存，运行时间较长。文献［12］采用随机抽样一致性（Random Sample Consensus，RANSAC）匹配点提纯算法剔除错误的关键点匹配对，提高了识别的精度，然而该算法在抽样时需要对所有的特征点进行迭代以得到最大化的局内点，导致效率较低，在一定程度上牺牲了算法的实时性。

针对特征点提取和匹配过程中速度慢、效率低的问题，文献［13］提出一种加速鲁棒特征（Speeded up Robust Feature，SURF）算法，对DoH 中的高斯二阶微分进行近似简化，加速了特征的提取和描述。然而，SURF 算法在计算主方向时过于依赖局部图像的梯度方向，导致匹配成功率降低。文献［14］提出一种二进制特征描述算法（ORB），有效地解决了计算和收敛速度慢的问题，提高了匹配的实时性，并且在图像识别的精度上有了进一步提高［15-16］，然而ORB 在匹配过程中容易受到目标外未知因素的干扰，导致匹配结果中存在大量的误匹配点。

文献［17］在邻域一致性约束的基础上，提出一种融合ORB 与网格统计的视频跟踪方法GMS，通过在特征点邻域范围内选择支持特征点集进行约束检验，以较小的时间代价增加了ORB 算法稳健匹配的数量。文献［18］提出一种基于稀疏表示的跟踪方法，但是该方法仅考虑整体而非局部外观来区分目标和背景区域，因此，当目标和背景区域相差不明显时，跟踪效果较差。文献［19］采用了深层卷积神经网络模型，但是在应对简易跟踪环境时，其跟踪速度很慢。文献［20］方法利用基于相关滤波的跟踪方法，在计算效率上有着优异的性能，然而该方法会因为匹配跟踪误差的累积而导致模型逐渐退化。

针对上述方法特征点匹配精度与匹配速度存在矛盾的问题，本文在视频目标跟踪方法GMS 的框架下，对ORB 特征匹配阶段产生的错误匹配对进行“粗-精”两阶段剔除，提出一种新的视频目标跟踪方法ME-GMS（Mismatch Elimination GMS）。利用K-means算法快速粗略地剔除误差较大的匹配关系，提高正确匹配对所占比例。在此基础上，依据分裂法的思想，参考匹配点到聚类中心的偏离程度，根据误差设定合适的阈值，从而对误匹配对进行精确剔除。

1 GMS 特征匹配方法

1.1 特征点提取

GMS 算法在特征匹配阶段采用ORB 算法进行特征点的检测与匹配。ORB 是一种基于FAST 特征点检测和Brief 描述子改良而成的图像特征匹配算法，其在应用于视频跟踪时具有极为优异的速度表现力，并具有尺度不变性和旋转不变性。ORB 算法主要通过以下步骤来完成特征点的检测：

1）采用FAST 算法粗提取大量的特征点。当以候选点p为圆心、r为半径的邻域范围内存在M个连续大于或小于候选点p处灰度值的点，则认为候选点p为FAST 特征点。

2）为消除图像边缘处存在的较强响应，利用Harris 算法的响应函数对步骤1）中提取的FAST 特征点执行排序，并保留前N个点。

3）为对提取的特征点赋予尺度信息，采用多尺度图像金字塔对图像分层提取FAST 特征点。

4）为对提取的特征点赋予方向信息，采用灰度质心法来计算FAST 特征点的主方向。当特征点邻域范围内的质心位置不与中心重合时，可通过质心与中心的位置坐标计算特征点的主方向。

特征点邻域范围内的质心可定义为：

特征点的邻域矩可定义为：

其中，I(x,y)表示(x,y)点处的灰度值。

特征点的主方向为：

1.2 特征点描述与匹配

ORB 算法采用Brief 描述子对每个特征点进行特征描述。Brief 描述子通过比较特征点邻域范围内像素点对的灰度差值，形成一个二进制码串，并采用汉明距离作为特征点匹配的相似性度量准则。ORB算法主要通过以下步骤来完成特征点的匹配：

1）在特征点p的邻域范围内选择n个像素点对，根据式（4）中的二元测试函数τ对这n个像素点对进行二值判决，得到一个包含n个二进制值的码串：

τ(p；ai,bi)表示特征点p邻域范围内的描述子分段函数，其定义如下：

其中，I(a)表示在特征点p邻域范围内a点处的灰度值。

2）为使Brief 算法生成的特征描述子具有旋转不变性，将式（3）得到的特征点主方向θ增加至描述子。

首先在特征点邻域范围内选择n对点集构建一个2×n维的矩阵，如式（6）所示；然后利用θ对应的旋转矩阵Rθ构造特征点对校正矩阵RθQ，得到具有旋转不变性的特征描述子，如式（7）所示。

3）利用贪婪搜索的方法找出相关系数小于设定阈值的邻域点对，构建包含256 个向量的最终特征描述子。

4）利用汉明距离计算特征描述子间的相似度进行特征匹配。假设步骤3）中的描述子K=b0b1…b255，则相似度D(K1,K2)可定义为：

2 特征点误匹配剔除方法

在进行前后两帧图像的特征点匹配时，得到的匹配关系中均含有一定数量的误匹配对，这会对视频跟踪产生一定程度的干扰，经累计会降低视频跟踪的准确性。为剔除这些误匹配对，本文采用由粗到精的方法，逐步对误匹配对进行剔除。首先利用K-means 算法的思想对匹配关系进行聚类划分，仅保留匹配对数量最多的那一类，从而剔除掉大部分误匹配对；然后在获得较多正确匹配对的基础上，以标准差和欧氏距离为准则，利用分裂法进一步剔除误匹配对。

2.1 基于K-means 的误匹配粗剔除方法

因此，对于集合C中的每一对匹配关系，利用2 个相对应的支持特征点集和，可计算从pi到qc(i)的旋转矩阵Ri和平移向量ti：

在此基础上，将旋转矩阵Ri和平移向量ti中的元素按顺序排列，得到1 个6 维向量。将集合C中的每1 对匹配关系都转化为1 个6 维向量v，全部匹配关系转换完成后，得到新的集合。

利用K-means 算法对Vtrans进行聚类，将其划分成η类（η取值范围通常为3～5）的步骤如下：

1）创建η个聚类集合和η个聚类中心，每个聚类中心都是一个6 维向量。

2）将Vtrans中的N个向量随机分配至η个聚类集合中。

3）更新每一类的聚类中心：

4）遍历Vtrans中每个向量vj，计算出与vj距离最近的聚类中心，并将vj划分至相应的中。

5）循环执行步骤3）和步骤4），当Vtrans中的所有向量在每一类中都不再变化时，聚类划分过程结束。

2.2 基于分裂法的误匹配精剔除方法

1）将标准差的阈值设置为Tthresh，将剔除系数设置为λ。

4）循环执行步骤2）和步骤3），直到满足这2 个步骤中任意一个停止条件，结束剔除。

经过上述过程，可以得到视频序列前后两帧图像特征点集间的正确匹配关系，消除视频跟踪中因误匹配对而造成的累计误差，进而利用这些正确的匹配关系进行快速稳健的视频跟踪。

3 实验仿真

为验证本文提出的ME-GMS 方法在处理特征点错误匹配时的有效性和高效性，下文分两部分进行配准跟踪实验。第一部分选择OTB-100［21］数据集中Rubik、Dog 和Skater 视频序列进行特征点的跨帧匹配实验，并将SIFT［11］、SURF［13］、ORB［14］和GMS［17］作为对比算法；第二部分选择OTB-100、VGG［22］和Strecha［23］数据集进行视频序列的连续跟踪实验，并选择主流的跟踪算法GMS、ASLA［18］、HDT［19］和DCFCA［20］作为对比算法。本文算法均利用Python代码实现，并运行在配置为Core i7-7700k 和16 GB RAM 的PC 机上。

3.1 视频序列的跨帧匹配实验

选择OTB-100 数据集中的Rubik、Dog 和Skater 视频序列进行特征点的跨帧匹配实验，统计SIFT［11］、SURF［13］、ORB［14］、GMS［17］和ME-GMS 算法的正确匹配数量和错误匹配数量，以计算匹配精度，同时比较各算法的运行速度，实验结果如图1 和表1所示。

图1 不同算法对Rubik、Dog 和Skater 视频序列的跨帧匹配结果Fig.1 Cross-frame matching results of different algorithms for Rubik，Dog and Skater video sequences

表1 不同算法对Rubik、Dog 和Skater 视频序列的跨帧匹配性能Table 1 Cross-frame matching performance of different algorithms for Rubik，Dog and Skater video sequences

从图1 和表1 可以明显看出：SIFT 算法与SURF算法的匹配精度较差，匹配结果中存在大量的错误匹配；ORB 算法的匹配精度略高于SIFT 算法和SURF 算法，但是仍有一定数量的错误匹配，并且容易出现匹配对簇集于一点的情况；相比于ORB 算法，GMS 算法错误匹配的数量有所减少，匹配精度进一步提高；而ME-GMS 算法借助ORB 算法高效的匹配效率，匹配速度仅仅稍低于ORB 算法，但大量地剔除了错误的匹配点，保留下正确的部分，因此匹配精度得以提高，且即使在处理难度较大的跨帧匹配时，也没有出现错误匹配现象。对比实验结果证明了ME-GMS 算法在视频序列的跨帧匹配时仍具有较好的匹配效果。

由表1 还可以看出，ORB 算法的平均匹配精度为73.88%，ME-GMS 算法的平均匹配精度为98.15%，匹配精度提高了约33 个百分点，并且高于GMS 算法的平均匹配精度94.20%，这证明ME-GMS算法在进行视频序列的跨帧匹配时比传统的特征点匹配算法适应能力更强，匹配效果更好。

3.2 视频序列的连续跟踪实验

选择OTB-100，VGG 和Strecha 数据集进行视频序列的连续跟踪实验。采用中心位置误差（Center Location Error，CLE）、距离精度（Distance Precision，DP）和重叠精度（Overlap Precision，OP）［21］作为评价指标，中心位置误差阈值设置为10 像素，重叠率阈值设置为0.7。本文算法与当前主流跟踪算法GMS［17］、ASLA［18］、HDT［19］和DCFCA［20］的性能对比如表2所示。

表2 ME-GMS 算法与当前主流跟踪算法的性能对比Table 2 Comparison of performance between ME-GMS and current mainstream tracking algorithms

从表2 可以看出，ME-GMS 算法在3 个视频数据集上的平均跟踪结果均优于其他4 种主流跟踪算法，其中：平均CLE 达到4.13 像素，相比于其他4 种跟踪算法平均提高了18%；平均DP 达到92.1%，相比于其他4 种跟踪算法平均提高了9%；平均OP 达到90.1%，相比于其他4 种跟踪算法平均提高了8%。ASLA 算法在目标与背景相似的情况下，出现了较多的误匹配；HDL 算法由于其复杂结构，导致处理速度最低；DCFCA 算法的计算效率极高，但是随着误差的积累导致其他指标效果较差。实验结果表明，ME-GMS 算法通过引入由粗到精的误匹配对剔除策略，可以大幅减少不必要特征点的生成与匹配工作，对视频序列实现更加稳定的跟踪效果。在平均运行速度上，ME-GMS 算法排第二，略微低于DCFCA 算法，这也反映了ME-GMS 算法以较小的时间代价换取了跟踪性能的较大提升。

图2 是ME-GMS 算法与其他4 种主流跟踪算法在3 个视频数据集上测试的距离精度曲线对比。可以看出，ME-GMS 算法的距离精度曲线位置最高，说明该算法的跟踪定位能力最强。图3是ME-GMS算法与其他4 种主流跟踪算法在3 个视频数据集上测试的重叠精度曲线对比。重叠精度曲线可有效反映目标跟踪算法的跟踪精度，它与坐标轴围成区域的面积越大，说明对应目标跟踪算法的跟踪性能越好。

综合图2 和图3 可知，与其他4 种对比算法相比，ME-GMS 算法的距离精度曲线和重叠精度曲线位置都最高，说明ME-GMS 算法的跟踪性能优于所对比的其他跟踪算法，进一步验证了基于K-means的误匹配粗剔除方法和基于分裂法的误匹配精剔除方法的有效性。

图2 ME-GMS 算法与主流跟踪算法的距离精度曲线对比Fig.2 Comparison of distance accuracy curves between ME-GMS and mainstream tracking algorithms

图3 ME-GMS 算法与主流跟踪算法的重叠精度曲线对比Fig.3 Comparison of overlapping accuracy curves between ME-GMS and mainstream tracking algorithm

4 结束语

本文提出一种新的视频目标跟踪方法ME-GMS。在GMS 方法框架下，对ORB 算法特征匹配阶段产生的错误匹配对进行“粗-精”两阶段剔除，借助ORB算法高效的计算速度，在保证视频序列跟踪时效性的同时提高匹配精度。视频序列的跨帧匹配和连续跟踪实验验证了本文方法稳健高效的匹配性能。但是该方法在进行特征点误匹配剔除时易受特征点提取质量的影响，即视频目标在复杂环境下，如受到光照、遮挡等因素的干扰，会导致特征点本身提取效果较差，从而影响剔除的效果，使视频跟踪的整体性能下降。下一步将优化特征点提取方法，以实现更好的跟踪效果。