一种基于改进FAST 角点检测的LK 光流算法

朱代先，刁弘伟，刘树林

（1.西安科技大学 通信与信息工程学院，陕西 西安 710054；2.西安科技大学 电气与控制工程学院，陕西 西安 710054）

0 引 言

运动目标检测是目前机器视觉领域中的研究热点，其广泛应用于航空航天、机器人自主避障、人脸识别等领域。当前，常见的动态目标检测算法有三类：

1）背景差分法，即以摄像头固定为前提，运用目标帧图像与背景图像的差值来判断是否存在移动目标。该方法准确度高、运行速度快，但对于动态背景的改变，缺少有效的背景更新方法，并且对光照变化或外部环境改变较为敏感。文献[2]提出了基于背景差分法的多运动目标检测与分割的方法，虽然成功地将多个移动目标进行了标记与分割，但该算法实时性不高。

2）帧间差分法，即用连续的两帧或者三帧图像的像素差分值来计算图像中的动态区域。当差分值的绝对值小于阈值，即表示没有移动；反之，则有运动，所以该方法阈值的选取非常重要。

3）光流法，通过计算图像灰度值在时间上的改变和图像里目标结构及其运动关系来检测移动目标，该算法不需要提前知道场景的任何信息，从而避免了背景模型的更新以及帧间时间间隔的选取问题。但其无法有效地解决物体移动形成的背景遮挡和孔径小等问题。文献[7]将稠密光流法应用于运动目标检测，将光流信息转化到HSV 空间，并利用Sobel 算子进行边缘检测提高了检测的效果，避免了“重影”“空洞”及“拖尾”问题，具有优秀的识别精确性和抗干扰能力。文献[8]使用Sift角点融合Harris 角点检测函数值筛选特征点，可成功减少局部邻域中无效的约束点，同时提升基本约束方程解的鲁棒性。

但这些算法运行速度慢，实时性仍有待提高。针对传统LK 光流法无法有效跟踪快速移动的目标，跟踪时存在特征点选取实时性和准确性不足的问题，本文提出一种结合改进FAST 特征点检测的LK 光流法。该算法结合了FAST 角点检测，并改进筛选特征点方案，可以更快速地获取初始目标特征点；然后对每一帧图像进行金字塔图像分层；最终使用LK 光流法对其进行跟踪，从而能够实现快速且稳定的运动目标检测与跟踪。

1 特征提取

1.1 FAST 角点检测原理

FAST 是一种重要的角点检测方法，常用于检测局部灰度改变明显的像素点。FAST 角点检测的原理是：当一个像素点与其邻域中的像素点差别过大（太亮或太暗），即判定该点是一个角点。步骤如下：

1）从图片里选取一个像素点，设的亮度值为I。

2）设定一个合适的阈值（例如，20%的I）。

3）以为圆心，半径为3 像素作离散化圆，该圆的圆周上存在16 个像素点，如图1 所示。

图1 FAST 角点选取原理图

4）如果该圆周上有个连续的像素点，其像素值都比I+大，或者都比I-小，那么判定像素点就是一个角点，如图1 中的白色虚线所示。值可以设置为12 或9，实验表明设为9 计算效果更好。

1.2 改进FAST 角点检测

传统FAST 角点检测必须将图像里所有的点都要遍历它邻域圆周上的16 个点的像素，计算速率过低。为了更进一步提升角点检测的速度，本文使用了更高效的检测方法来快速排除大部分非特征点的像素。改进后的方法只用计算点离散圆周上1，5，9 和13 四点方位的像素，首先计算方位1，9 的亮度值，当其亮度值都比阈值亮或比阈值暗，再检测方位5，13 的亮度值。如果以上4 个像素点里最少有3 个亮度都大于I+或者小于I-，那么判定点是一个候选角点。对所有像素点做上面这一部分的初步检测后，再对所有候选的角点做完整的FAST 角点检测，此时得到的角点即为所需要的目标特征点。改进的FAST 角点检测算法流程图如图2 所示。

图2 改进的FAST 角点检测算法流程图

2 目标跟踪

2.1 LK 光流法基本原理

LK 光流法（Lucas-Kanada 稀疏光流法）是一种基于两帧图像差分的光流运动估计算法。一个图像序列()可以用一个三维的列向量=(,,)表示，式中：和分别是方位和方位的空间分量；是时间分量。

假设获取上一帧和下一帧图像的时间分别为和+d，则根据灰度不变假设有：

式中：d和d表示像素在d时间内沿，方向的位移增量。

根据小运动模型假设，将式（1）泰勒展开：

由灰度不变假设可得：

把图像灰度对时间的改变量写为I，写成矩阵形式为：

式（4）有两个未知数，根据空间的一致性假设，设某一区域中的像素具有统一的运动，区域大小为×，像素个数为，则：

可得：

式（6）为关于，的超定线性方程。

将式（7）使用最小二乘法求解可得光流的计算公式为：

2.2 金字塔LK 光流法

LK 光流法的第二条假设针对的是小位移运动，当运动目标速度过快时，该算法会出现不小的偏差，而使用金字塔图像分层的LK 光流法可以有效解决该问题。设有两帧灰度图像和，(,)和(,)分别为图像和上(,)位置处的灰度值。设图像的像素点= [u,u]匹配到图像上的像素点=+=[u+d,u+d]，使(u,u)和(u+d,u+d)误差最小。位移= [d,d]被称为和光流。通常在以点为中心的图像区域[2w+1,2w+1]内，通过最小灰度匹配误差的平方和来求解。此损失函数为：

对图像进行金字塔分层，原始图像位于金字塔最底层，上一层图像的长和宽每次缩小为下层图像的一半，最终分辨率最低的图像位于金字塔的最顶层；然后从最顶层开始，向下递归求解直到原始图像为止。

设第层的损失函数为：

重新定义：

对(+v,+v)进行泰勒展开：

同时，令：

得：

得：

2.3 改进的光流跟踪算法

本文算法的核心部分主要由改进的FAST 角点检测、金字塔图像分层、LK 光流法等部分组成。FAST 角点检测是计算机视觉领域的一类经典算法，相比其他角点检测算法，FAST 在运行效率和计算速度等方面都有一定的优势，因此在图像处理问题上得到了广泛的应用。算法的跟踪过程分为两部分：角点检测和光流估计。对于角点检测，改进的FAST 用于快速提取第一帧中最强的灰度变化角点，通过设定阈值筛选目标特征点。对于光流估计，根据首帧检测到的特征点，通过LK金字塔估计第二帧与首帧的匹配点位置，然后将获得的位置用作第三帧的初始预估位置。操作一直进行到获得最后一帧的匹配点位置为止。最终算法成功跟踪运动目标，改进的跟踪算法流程图如图3 所示。

图3 改进的跟踪算法流程图

改进的FAST 角点检测算法相比传统FAST 方法拥有两次特征点筛选。第一次筛选候选角点时能够快速剔除图像上非角点的像素点，极大提高了算法的运行速度。第二次目标特征点的提取在第一次筛选的候选角点基础上进行小阈值筛选，减少了特征点的数量并且提高了特征点提取的准确性。传统光流法跟踪运动速度过快的目标时会导致跟踪失败，因此引入图像分层模块。金字塔图像分层主要解决了运动目标帧间变化较大的问题，将原本较大位移运动通过降低图像像素变成小位移运动，使泰勒展开式仍能够进行计算，从而提升光流算法的有效性。

3 实 验

3.1 实施方案

为了充分说明改进方法的有效性和优越性，设计了两个实验方案，具体方法如下：

1）对运动目标分别提取Sift 特征点、Harris 特征点、FAST 角点和改进后的FAST 特征点，然后分别使用金字塔LK 光流法对其运动目标进行跟踪，验证不同特征点对算法的影响。

2）考虑到FAST 特征点本身具有的优点，为验证改进后的FAST 特征点作为LK 光流法跟踪时的目标特征点能否继续保留FAST 角点原本的性能。通过一段小球铅摆运动的实时视频，来对比验证FAST 光流算法与改进后的FAST 光流算法跟踪运动目标的实时性与准确性。

3.2 算法跟踪性能的分析

为了体现算法的有效性，实验采取以下数据衡量算法性能：实验1 中使用初始动态目标检测耗时、初始时识别的特征点个数NUM、每秒处理的图像帧数FPS（反映算法的实时性）等指标；实验2 中使用跟踪路线和实际路线在轴方向上的误差、跟踪路线和实际路线在轴方向上的误差（反映算法的准确性）作为指标。若改进FAST 光流算法相比未改进的FAST 光流算法在运行速度上有一定程度的提高，并且能够使跟踪误差基本保持不变，则说明改进后的算法拥有更好的性能。

3.3 实验结果与分析

实验硬件平台为个人PC，具体参数如下：

处理器：AMD Ryzen 5 3550H with Radeon Vega Moblie Gfx 2.10 GHz ，RAM 16.0 GB，Windows 10，Visual Studio 2017，Matlab 2018。

实验1 依次使用Sift 特征点、Harris 特征点、FAST 角点和改进FAST 特征点融合LK 光流法对运动目标进行跟踪，类比数据指标分析算法的性能，具体指标统计见表1。其中，为初始运动目标检测耗时；NUM 为初始识别的特征点个数；FPS 为每秒处理的图像帧数。

表1 四种跟踪效果的指标统计

从表1 可以看出，运动目标跟踪算法运行速度分别是改进FAST 光流法＞FAST 光 流法＞Harris 光 流法＞Sift光流法。改进FAST 特征点结合LK 光流法相比未改进FAST 特征点结合LK 光流法初始运动目标检测耗时降低了8 ms，且特征点数量基本保持不变，但每秒处理的图像帧数提高了22.4%。可以得到结论：采用改进后的FAST 角点检测作为LK 光流法的目标特征点，可以使跟踪算法的运行速率得到更进一步的提升。

四种特征点检测效果如图4 所示。

图4 四种特征点检测效果

实验2 因为FAST 特征点自身拥有快速检测的特点，为判断改进后的FAST 光流算法能否继续保持良好的稳定性，设计追踪小球铅摆运动的实验，判断小球实际运动轨迹与算法跟踪轨迹在轴方向和轴方向的偏差是否满足精度要求。

图5 分别展示了改进算法在跟踪移动小球的第5，25，50，75 帧时的跟踪情况。图6、图7 显示了传统FAST角点结合LK 光流法与改进FAST 角点结合LK 光流法分别跟踪动态目标的轨迹与动态目标实际移动轨迹的方位与方位的跟踪误差。传统算法轴方向与轴方向的平均跟踪误差为0.778 8 像素和0.705 0 像素，改进后的算法轴方位与轴方位的平均跟踪误差为0.741 3 像素和0.720 4 像素，可以看出算法改进后的跟踪误差略有减小。将改进后的算法取75 帧作为测试样本，原始图像的分辨率为720×480 像素，金字塔的数量层为4 层，迭代阈值为0.5 像素，即迭代次数为20 次。改进跟踪算法平均4 次迭代就可以满足收敛，而未改进的方法平均需要5 次迭代才能满足收敛。综合而言，可以证明改进后的FAST 角点检测结合光流法相比传统算法在精度变化不大的情况下运行速度得到了明显提高，能够准确而实时地跟踪移动目标。

图5 改进后的跟踪算法不同时间的跟踪结果

图6 x 轴方向的跟踪误差

图7 y 轴方向的跟踪误差

4 结 论

针对传统LK 光流法无法跟踪快速移动的物体，跟踪过程中存在特征点选取实时性和准确性不足的问题，本文提出了结合改进FAST 算法进行特征选取和融合金字塔LK 光流法进行特征追踪的综合算法。实验证明改进后的算法可以更快速地提取较优的特征点，使算法运行速度提高的同时也能保持较低的跟踪误差，能够满足实时且稳定的跟踪效果。如今计算机视觉有良好的发展前景，该算法还有进一步发展的空间，怎样突破光流法灰度不变假设的局限；当环境整体明暗改变时如何避免可能会出现光流法跟踪失效的情况，这些都是今后研究的重点方向。