浅析特征点匹配的自适应目标跟踪算法
摘 要： 由于实际场景复杂多变，目标在运动过程中往往会出现形变、遮挡等问题，增加了跟踪的难度。为了解决上述问题，提出一种基于特征点匹配的自适应目标跟踪算法。算法初始化时在选定的目标区域内提取特征点，跟踪过程中通过对前后两帧的特征点进行匹配，计算出目标的位置、尺度和旋转变化，进而实现对目标的跟踪。同时通过对特征点的不断更新，可以使算法具有一定的抗遮挡能力。实验表明，该方法在实际应用中效果很好。
0 引言
目标跟踪算法作为视频分析的基本内容之一，受到了广泛的关注，近年来研究人员提出了很多具有针对性的方法，然而由于实际场景的复杂性，目标在运动过程中往往会发生剧烈的形变，部分或完全被遮挡，现有跟踪算法很难完全克服这些问题，还需要进一步研究［1］。由于目标的局部特征在运动过程中比全局特征具有更好的稳定性，且在遮挡情况下仍有一部分局部特征存在，为此研究人员相继提出了许多基于局部特征的目标跟踪算法［2］，希望从这个角度出发解决较大形变或者被遮挡目标的跟踪问题。
目前常用的局部特征包括harris［3］、sift［4］、fast［5］、brisk［6］等。参考文献［7-8］采用surf特征点匹配的方法实现运动目标跟踪，具有一定的抗形变和遮挡能力。参考文献［9］对sift特征点进行了研究，提出一种基于改进sift特征点匹配的目标跟踪算法。参考文献［10］对meanshift算法的跟踪结果进行fast-9特征点匹配，计算出目标的尺度变化，使得算法在原有高效率的基础上具有了更好的抗尺度变化的能力。
鉴于特征点在运动目标发生尺度、旋转变化或是被遮挡时仍能够被检测到，本文采用图像特征点作为运动目标的描述特征，提出一种基于特征点匹配的自适应运动目标跟踪算法，以达到在复杂环境下对目标进行稳定的跟踪。算法根据输入的初始目标矩形框，首先提取目标的特征点作为目标的初始特征。
获取一帧新的图像后，在搜索区域内提取特征点，然后与上一帧中的目标特征点进行匹配，根据匹配结果估计出目标的位置、尺度和旋转变化，使用这些变化值更新上一帧目标的跟踪结果，完成当前帧目标跟踪任务。同时更新目标特征点，以使得算法具有一定的抗遮挡能力。
1 特征点匹配
图像中的特征点通常是指与周围像素值存在明显差异，颜色值不连续的点，一般包括线段交点、重心点、高差异的点、局部曲率不连续点、曲线拐点、小波变换的局部极值点、角点以及兴趣算子点等[11]。通常特征点都具有一定的旋转、平移、尺度缩放不变性，对光照变化保持一定的不变性[12]。
考虑到跟踪算法实时性的要求，选用fast特征点来进行目标跟踪。fast特征点是由rosten e和drummond t于2006年提出的一种简单快速的特征点检测算法，相比于其他的特征点检测算法，它的计算速度有了很大程度的提高。fast特征点是指在该像素点的周围邻域内，有足够多的像素点与该点的颜色值相差较大，也就是说在图像中fast特征点与其周围像素点颜色值不同，如图1中的a、b两点。那么根据式（1）可以判断图像中的某像素点是否为fast特征点：
其中，p为要进行计算的像素点，x为p以为圆心、半径为3的圆上的任意一点，i（x）和i（p）分别为x和p的颜色值，εd为颜色差值的阈值，当n大于一定的阈值n0且圆上的n个点中至少有n0个点是连续无中断的，则认为p为fast特征点。对于半径为3的圆形邻域模板，通常情况下n0取12。
为了提高fast特征点的检测效率，还可以采用附件的加速技巧，首先判断候选点的圆周上被90°分割的4个顶点处的像素是否满足条件，参见图1中的1、5、9、13这4个点。若这4个点中至少有3个点满足条件，即与候选点的像素值相差大于设定的阈值，则继续判断圆周上其他的点；否则就认为该候选点不是fast特征点。
在算法的处理过程中，根据上一帧的跟踪结果确定当前帧中目标的搜索区域，再根据以上描述的方法提取出搜索区域的fast特征点，然后将当前搜索区域的fast特征点与上一帧中目标的fast特征点进行匹配。匹配方法如下：计算出要匹配的两个fast特征点集合中每一个特征点在另一个特征点集合中的最近邻和次近邻，若特征点和最近邻之间的距离与其到次近邻的距离之间的比值小于一定的阈值时，就认为此最近邻是样本的一个初始匹配。
为了提高特征点的近邻计算速度，将fast特征点集构造成beis j等人提出的一种改进k-d树（k-dimension tree），然后使用bbf（best bin first）算法计算特征点的最近邻和次近邻[13]。获得粗匹配结果之后，再使用ransac算法进一步剔除错误匹配，提高匹配正确率，最终得到精度较高的匹配结果。得到的高精度匹配结果可以更好地应用于后续的自适应目标跟踪算法。
2 自适应目标跟踪算法
通过手动选择或者采用运动目标检测算法选中要跟踪的目标之后，可以获得该目标的外接矩形框r1，采用上面叙述的方法提取目标的fast特征点集合o1，通过上述两步，完成算法初始化工作。在对目标进行跟踪的过程中，假设当前获取的视频图像为ii帧，第ii-1帧图像中算法获得的目标外接矩形框为ri-1，目标的fast特征点集合为oi-1，由于两帧之间的时间间隔有限，目标的移动范围也是小距离的，对ri-1进行适当放大可以获得ii帧中的目标搜索区域，在搜索区域中提取fast特征点集合o，o与oi-1进行匹配，获得匹配点集合对mi-1、mi。第ii-1与ii帧之间目标的位移可以通过下式估计出：
其中，pi-1和pi分别为mi-1和mi的重心。目标在运动过程中也时常会出现尺度和旋转变化，可以根据以下两个公式计算出目标在ii-1与ii帧之间的尺度和旋转变化：
其中，ai、aj为mi中任意两个点，bi、bj为mi-1中分别与ai、aj对应的两个点，s为估计出的目标尺度缩放因子，
为目标从第i-1到i帧发生旋转的旋转角度，r为旋转矩阵。
的计算方法如下：
估计出目标的位移、尺度和旋转变化之后，就可以计算出第ii+1中的目标。
式（6）中vi-1为ri-1的顶点，根据vi可以获得第ii帧中目标的外接矩形框ri。当mi中特征点个数小于一定阈值时，选取o中位于ri中的特征点添加到mi中，获得ii帧中的目标特征点集合oi。算法1中描述了该自适应目标跟踪算法。
算法1
输入：视频帧序列i1，i2，…，ii，…，in和初始目标的外接矩形框r1。
输出：每帧图像中的跟踪目标外接矩形框r2，…，ri，…，rn。
具体步骤为：
（1）获取一帧图像ii；
（2）若i=1，则在r1范围内提取fast特征点，获得o1，转到1；
（3）将ri-1适当扩大得到目标搜索区域，在该区域内计算o，o与oi-1进行匹配获得匹配点对集合mi、mi-1；
（4）根据式（2）~（4）计算出目标的位移
尺度变化因子s和旋转矩阵r；
（5）根据式（6）计算出目标新的外接矩形框ri，并更新目标特征点集合，获得oi；
（6）处理完成则算法结束，否则转到步骤（1）。
3 实验与结果分析
为了验证算法的有效性，选取了多种场景下的运动目标，对算法进行了多组实验，实验结果如图2所示。实验使用的硬件环境为：cpu为pentium（r）dual-coree6700（主频为3.2 ghz），内存2 gb，软件平台为：操作系统windows 7（32位），使用c++语言在microsoft visual studio 2010进行编程，调用opencv图像处理库，所提出的方法对非刚体的行人、刚体的汽车以及旋转角度很大的物体都能有较好的跟踪效果。
4 结论
针对跟踪目标在运动过程中会发生尺度和旋转变化导致跟踪失败的问题提出一种采用局部特征点匹配的运动目标跟踪算法，通过实验可以发现该算法能够很好地适应目标的缩放和旋转变化，对目标一直保持稳定的跟踪，且通过对跟踪过程中目标特征点的更新，使得该方法具有一定的抗遮挡能力，具有较好的实用性。不过未来还需要对算法进行更多的实验和改进，以进一步提高算法的鲁棒性和实时性。
参考文献
［1］ 高韬，刘正光，张军，等。基于特征点的多运动目标跟踪［j］。电子与信息学报，2010.5，32（5）：1111-1115.
［2］ nebehay g， pflugfelder r. consensus-based matching and tracking of keypoints for object tracking［c］。 winter conference on applications of computer vision， 2014： 862-869.
［3］ harris c， stephens m. a combined comer and edge detector［a］。 proceedings of the 4th alvey vision conference［c］。 manchester， uk， 1988：147-151.
［4］ lowe d g. distinctive image features from scale-invariant keypoints［j］。 international journal of computer vision， 2004，60（2）：91-110.
［5］ rosten e， drummond t. machine learning for high-speed corner detection［c］。 european conference on computer vision， 2006：430-443.
［6］ leutenegger s， chli m， siegwart r. brisk： binary robust invariant scalable keypoints［c］.computer vision-iccv，2011： 2548-2555.
［7］ 王露露，张洪，高忠国。基于surf的目标跟踪算法［j］。江南大学学报（自然科学版），2012，11（5）：515-518.
［8］ 梅振顺，战荫伟，钟左峰。基于surf特征的目标跟踪［j］。中国体视学与图像分析，2011，16（1）：28-32.
［9］ 李明。基于sift特征点匹配的目标跟踪算法研究［d］。合肥：合肥工业大学，2011.
［10］ song yi， li shuxiao， chang hongxing. scale adaptive mean shift tracking based on feature point matching［c］.2013 second iapr asian conference on pattern recognition， 2013：220-224.
［11］ 赵登科。立体视觉测量中的点特征提取与匹配算法［d］。沈阳：沈阳理工大学，2013.
［12］ 刘洁。基于特征点的目标检测与跟踪方法研究［d］。成都：电子科技大学，2008.
［13］ 王永明，王贵锦。图像局部不变性特征与描述［m］。北京：国防工业出版社，2010.
紫光展锐发布全新6G白皮书，展望泛在融合发展蓝图
农残快速检测仪对娃娃菜的农药残留检测
HS6606L高性能传感信号处理集成电路介绍
配电箱的接线方式/安装方法/分类/注意事项
基于RK3588平台的会议平板即将发布
浅析特征点匹配的自适应目标跟踪算法
Intel揭开14nm至强与凌动服务器芯片神秘面纱
天线计量的测试方法
怎样调整地磅万能遥控器的四角误差
认识电子管
F5G具备三大特性,部署规模领先世界
关于几款功能性GNSS G-mouse的简单介绍
物联网的潜力需要如何去挖掘
为什么PCIe向前迈出了一大步？
BP85928D芯片在智能语音家电的应用方案
智慧互通（爱泊车）技术驱动时代变革 勇做技术变革的引领者
IP联盟_中国IP联盟_TSMC软IP联盟
新芯片架构瞄准深度学习和视觉处理
YY1116皮肤缝合线线径测量仪的参数解析
灭蚊灯真的有用吗，无害环保灭蚊就靠它了
0 引言
目标跟踪算法作为视频分析的基本内容之一，受到了广泛的关注，近年来研究人员提出了很多具有针对性的方法，然而由于实际场景的复杂性，目标在运动过程中往往会发生剧烈的形变，部分或完全被遮挡，现有跟踪算法很难完全克服这些问题，还需要进一步研究［1］。由于目标的局部特征在运动过程中比全局特征具有更好的稳定性，且在遮挡情况下仍有一部分局部特征存在，为此研究人员相继提出了许多基于局部特征的目标跟踪算法［2］，希望从这个角度出发解决较大形变或者被遮挡目标的跟踪问题。
目前常用的局部特征包括harris［3］、sift［4］、fast［5］、brisk［6］等。参考文献［7-8］采用surf特征点匹配的方法实现运动目标跟踪，具有一定的抗形变和遮挡能力。参考文献［9］对sift特征点进行了研究，提出一种基于改进sift特征点匹配的目标跟踪算法。参考文献［10］对meanshift算法的跟踪结果进行fast-9特征点匹配，计算出目标的尺度变化，使得算法在原有高效率的基础上具有了更好的抗尺度变化的能力。
鉴于特征点在运动目标发生尺度、旋转变化或是被遮挡时仍能够被检测到，本文采用图像特征点作为运动目标的描述特征，提出一种基于特征点匹配的自适应运动目标跟踪算法，以达到在复杂环境下对目标进行稳定的跟踪。算法根据输入的初始目标矩形框，首先提取目标的特征点作为目标的初始特征。
获取一帧新的图像后，在搜索区域内提取特征点，然后与上一帧中的目标特征点进行匹配，根据匹配结果估计出目标的位置、尺度和旋转变化，使用这些变化值更新上一帧目标的跟踪结果，完成当前帧目标跟踪任务。同时更新目标特征点，以使得算法具有一定的抗遮挡能力。
1 特征点匹配
图像中的特征点通常是指与周围像素值存在明显差异，颜色值不连续的点，一般包括线段交点、重心点、高差异的点、局部曲率不连续点、曲线拐点、小波变换的局部极值点、角点以及兴趣算子点等[11]。通常特征点都具有一定的旋转、平移、尺度缩放不变性，对光照变化保持一定的不变性[12]。
考虑到跟踪算法实时性的要求，选用fast特征点来进行目标跟踪。fast特征点是由rosten e和drummond t于2006年提出的一种简单快速的特征点检测算法，相比于其他的特征点检测算法，它的计算速度有了很大程度的提高。fast特征点是指在该像素点的周围邻域内，有足够多的像素点与该点的颜色值相差较大，也就是说在图像中fast特征点与其周围像素点颜色值不同，如图1中的a、b两点。那么根据式（1）可以判断图像中的某像素点是否为fast特征点：
其中，p为要进行计算的像素点，x为p以为圆心、半径为3的圆上的任意一点，i（x）和i（p）分别为x和p的颜色值，εd为颜色差值的阈值，当n大于一定的阈值n0且圆上的n个点中至少有n0个点是连续无中断的，则认为p为fast特征点。对于半径为3的圆形邻域模板，通常情况下n0取12。
为了提高fast特征点的检测效率，还可以采用附件的加速技巧，首先判断候选点的圆周上被90°分割的4个顶点处的像素是否满足条件，参见图1中的1、5、9、13这4个点。若这4个点中至少有3个点满足条件，即与候选点的像素值相差大于设定的阈值，则继续判断圆周上其他的点；否则就认为该候选点不是fast特征点。
在算法的处理过程中，根据上一帧的跟踪结果确定当前帧中目标的搜索区域，再根据以上描述的方法提取出搜索区域的fast特征点，然后将当前搜索区域的fast特征点与上一帧中目标的fast特征点进行匹配。匹配方法如下：计算出要匹配的两个fast特征点集合中每一个特征点在另一个特征点集合中的最近邻和次近邻，若特征点和最近邻之间的距离与其到次近邻的距离之间的比值小于一定的阈值时，就认为此最近邻是样本的一个初始匹配。
为了提高特征点的近邻计算速度，将fast特征点集构造成beis j等人提出的一种改进k-d树（k-dimension tree），然后使用bbf（best bin first）算法计算特征点的最近邻和次近邻[13]。获得粗匹配结果之后，再使用ransac算法进一步剔除错误匹配，提高匹配正确率，最终得到精度较高的匹配结果。得到的高精度匹配结果可以更好地应用于后续的自适应目标跟踪算法。
2 自适应目标跟踪算法
通过手动选择或者采用运动目标检测算法选中要跟踪的目标之后，可以获得该目标的外接矩形框r1，采用上面叙述的方法提取目标的fast特征点集合o1，通过上述两步，完成算法初始化工作。在对目标进行跟踪的过程中，假设当前获取的视频图像为ii帧，第ii-1帧图像中算法获得的目标外接矩形框为ri-1，目标的fast特征点集合为oi-1，由于两帧之间的时间间隔有限，目标的移动范围也是小距离的，对ri-1进行适当放大可以获得ii帧中的目标搜索区域，在搜索区域中提取fast特征点集合o，o与oi-1进行匹配，获得匹配点集合对mi-1、mi。第ii-1与ii帧之间目标的位移可以通过下式估计出：
其中，pi-1和pi分别为mi-1和mi的重心。目标在运动过程中也时常会出现尺度和旋转变化，可以根据以下两个公式计算出目标在ii-1与ii帧之间的尺度和旋转变化：
其中，ai、aj为mi中任意两个点，bi、bj为mi-1中分别与ai、aj对应的两个点，s为估计出的目标尺度缩放因子，
为目标从第i-1到i帧发生旋转的旋转角度，r为旋转矩阵。
的计算方法如下：
估计出目标的位移、尺度和旋转变化之后，就可以计算出第ii+1中的目标。
式（6）中vi-1为ri-1的顶点，根据vi可以获得第ii帧中目标的外接矩形框ri。当mi中特征点个数小于一定阈值时，选取o中位于ri中的特征点添加到mi中，获得ii帧中的目标特征点集合oi。算法1中描述了该自适应目标跟踪算法。
算法1
输入：视频帧序列i1，i2，…，ii，…，in和初始目标的外接矩形框r1。
输出：每帧图像中的跟踪目标外接矩形框r2，…，ri，…，rn。
具体步骤为：
（1）获取一帧图像ii；
（2）若i=1，则在r1范围内提取fast特征点，获得o1，转到1；
（3）将ri-1适当扩大得到目标搜索区域，在该区域内计算o，o与oi-1进行匹配获得匹配点对集合mi、mi-1；
（4）根据式（2）~（4）计算出目标的位移
尺度变化因子s和旋转矩阵r；
（5）根据式（6）计算出目标新的外接矩形框ri，并更新目标特征点集合，获得oi；
（6）处理完成则算法结束，否则转到步骤（1）。
3 实验与结果分析
为了验证算法的有效性，选取了多种场景下的运动目标，对算法进行了多组实验，实验结果如图2所示。实验使用的硬件环境为：cpu为pentium（r）dual-coree6700（主频为3.2 ghz），内存2 gb，软件平台为：操作系统windows 7（32位），使用c++语言在microsoft visual studio 2010进行编程，调用opencv图像处理库，所提出的方法对非刚体的行人、刚体的汽车以及旋转角度很大的物体都能有较好的跟踪效果。
4 结论
针对跟踪目标在运动过程中会发生尺度和旋转变化导致跟踪失败的问题提出一种采用局部特征点匹配的运动目标跟踪算法，通过实验可以发现该算法能够很好地适应目标的缩放和旋转变化，对目标一直保持稳定的跟踪，且通过对跟踪过程中目标特征点的更新，使得该方法具有一定的抗遮挡能力，具有较好的实用性。不过未来还需要对算法进行更多的实验和改进，以进一步提高算法的鲁棒性和实时性。
参考文献
［1］ 高韬，刘正光，张军，等。基于特征点的多运动目标跟踪［j］。电子与信息学报，2010.5，32（5）：1111-1115.
［2］ nebehay g， pflugfelder r. consensus-based matching and tracking of keypoints for object tracking［c］。 winter conference on applications of computer vision， 2014： 862-869.
［3］ harris c， stephens m. a combined comer and edge detector［a］。 proceedings of the 4th alvey vision conference［c］。 manchester， uk， 1988：147-151.
［4］ lowe d g. distinctive image features from scale-invariant keypoints［j］。 international journal of computer vision， 2004，60（2）：91-110.
［5］ rosten e， drummond t. machine learning for high-speed corner detection［c］。 european conference on computer vision， 2006：430-443.
［6］ leutenegger s， chli m， siegwart r. brisk： binary robust invariant scalable keypoints［c］.computer vision-iccv，2011： 2548-2555.
［7］ 王露露，张洪，高忠国。基于surf的目标跟踪算法［j］。江南大学学报（自然科学版），2012，11（5）：515-518.
［8］ 梅振顺，战荫伟，钟左峰。基于surf特征的目标跟踪［j］。中国体视学与图像分析，2011，16（1）：28-32.
［9］ 李明。基于sift特征点匹配的目标跟踪算法研究［d］。合肥：合肥工业大学，2011.
［10］ song yi， li shuxiao， chang hongxing. scale adaptive mean shift tracking based on feature point matching［c］.2013 second iapr asian conference on pattern recognition， 2013：220-224.
［11］ 赵登科。立体视觉测量中的点特征提取与匹配算法［d］。沈阳：沈阳理工大学，2013.
［12］ 刘洁。基于特征点的目标检测与跟踪方法研究［d］。成都：电子科技大学，2008.
［13］ 王永明，王贵锦。图像局部不变性特征与描述［m］。北京：国防工业出版社，2010.
紫光展锐发布全新6G白皮书，展望泛在融合发展蓝图
农残快速检测仪对娃娃菜的农药残留检测
HS6606L高性能传感信号处理集成电路介绍
配电箱的接线方式/安装方法/分类/注意事项
基于RK3588平台的会议平板即将发布
浅析特征点匹配的自适应目标跟踪算法
Intel揭开14nm至强与凌动服务器芯片神秘面纱
天线计量的测试方法
怎样调整地磅万能遥控器的四角误差
认识电子管
F5G具备三大特性,部署规模领先世界
关于几款功能性GNSS G-mouse的简单介绍
物联网的潜力需要如何去挖掘
为什么PCIe向前迈出了一大步？
BP85928D芯片在智能语音家电的应用方案
智慧互通（爱泊车）技术驱动时代变革 勇做技术变革的引领者
IP联盟_中国IP联盟_TSMC软IP联盟
新芯片架构瞄准深度学习和视觉处理
YY1116皮肤缝合线线径测量仪的参数解析
灭蚊灯真的有用吗，无害环保灭蚊就靠它了