0 概述

视频图像特征点匹配与常见的视频目标跟踪算法相比具有更高的配准精度要求。目标跟踪算法通常基于纹理^[1-2]、颜色^[3-4]、卷积特征^[5-7]实现区域内容的理解和识别, 并不要求对准确点进行匹配与识别, 而视频特征点匹配基于确定特征点进行识别, 依赖快速的特征点配准算法实现视频实时处理, 完成准确的特征点集跟踪^[8-10]。

为增强特征点配准的准确性与稳定性, 研究人员针对旋转、伸缩、明暗等变换提出Harris Corners^[11-12]、SIFT^[13]、SURF^[14]、HOG^[15]、A-SIFT^[16]和ORB^[17]等算法实现特征不变性描述。在实时性表现上, 其中部分算法能实现与视频帧同步匹配, 例如ORB算法具有较高的计算速度。然而, 仅依赖图像特征点自身单一的特征描述符, 不可避免地会出现较多错误匹配。针对该问题, 文献[18-19]利用邻域特征点的几何信息, 在保证绝大多数周围点正确的前提下实现特征匹配。然而, 在相邻匹配中存在较多不确定匹配时, 该方法的匹配精度较差。文献[20]基于邻域一致性约束提出一种基于ORB与网格统计的解决方法GMS(Grid-based Motion Statistics, GMS), 通过特征点邻域内的支持特征点进行群智决策以检验配对准确性, 该方法以较小的时效代价提高了ORB算法的鲁棒性。上述各类视频特征匹配算法为了保证视频图像特征点匹配的精度与鲁棒性, 均在实时性方面做出了牺牲。

为在提升图像配准时效性的同时保证配准的精度与鲁棒性, 本文提出一种基于特征位置预测与邻域一致性约束的视频特征快速配准方法(Fast Registration based on Location Prediction and Neighbor Consistency, FRLPNC)。

1 本文算法框架

本文算法框架如图 1所示, 首先通过多项式拟合, 根据历史帧目标位置进行区域预测, 进一步缩小特征搜索区域, 大幅减少配准工作量, 同时, 由于减少了非相关配准区域, 可有效避免错误匹配。当发生运动变换时, 由于运动无法瞬时改变, 在同样的步进时间上存在连续性。即便在未能实现配准的情况下, 以预测中心为基准依次进行扩张匹配, 可提高匹配精度与匹配速度。更进一步地, 针对区域内的特征匹配, 采用ORB算法生成特征描述点集, 根据GMS算法局部邻域的一致性约束设定模板标注点邻域范围, 通过统计模板标注点邻域范围内支持特征点的匹配情况, 得出目标图像匹配的邻域, 并根据目标图像上被匹配的支持特征点进一步确定待匹配标注点坐标。本文通过近邻帧的稳健匹配, 在运动连续性的约束下保障特征模板的稳健传递, 以实现多姿态运动配准。本文算法基于运动的连续性与局部邻域约束的一致性进行配准, 尤其适用于运动目标的配准, 能有效减少配准时间, 提升配准精度, 丰富配准姿态, 增强算法的稳健性。

2 基于多项式回归的图像特征位置预测

通过标定点坐标与GMS全局特征进行搜索匹配, 获得前n帧的n个已知位置信息, 利用最邻近的n个位置进行多项式回归预测, 得到当前n+1帧的预测位置, 在预测位置周围进行局部搜索以获得准确位置。以此类推, 通过当前位置帧最邻近n帧的真实位置预测当前位置。

问题描述如下:当下一帧图像为第t+1帧(t>n)时, 位置预测的目的是得到第t+1帧图像中特征点的预测位置p′_t+1=[a′(t+1), b′(t+1)], 其中, 真实位置为p_t+1=[a(t+1), b(t+1)]。

通过GMS匹配得到第t+1帧图像之前的最邻近n帧图像{[a(r_i), b(r_i)]}, 其中, r_i=t－n+i, i=1, 2, …, n表示前n帧图像对应的帧号。为了预测第t+1帧图像中目标预测位置p′_t+1的分量a′(t+1), 利用前n帧图像配准得到的位置分量a(r_i)及其对应的帧号r_i, 构造由n个点组成的数据组{[r_i, a(r_i)]}, 则预测的特征点位置分量a′(t+1)的m阶多项式回归预测值f_a(r_i)可表示为:

$ {f_a}\left( {{r_i}} \right) = \sum\limits_{k = 0}^m {{\theta _k}} r_i^k, i = 1, 2, \cdots , n $

(1)

其中, θ_k是多项式回归模型的系数。

令R为设计矩阵, θ是系数向量, A是观测值向量, 则可将多项式回归模型表示为如下形式:

$ \mathit{\boldsymbol{A}} = \mathit{\boldsymbol{R\theta }} $

(2)

θ可以利用正规方程得到, 具体如下:

$ \mathit{\boldsymbol{\theta }} = {\left( {{\mathit{\boldsymbol{R}}^{\rm{T}}}\mathit{\boldsymbol{R}}} \right)^{ - 1}}{\mathit{\boldsymbol{R}}^{\rm{T}}}\mathit{\boldsymbol{A}} $

(3)

由已知的n个点可以计算得到系数向量θ, 即可训练得到多项式回归模型。将r_n+1=t+1代入式(3), 可以得到下一帧图像中的预测位置分量a′(t+1), 如式(4)所示。

$ {a^\prime }(t + 1) = {f_a}\left( {{r_{n + 1}}} \right) = \sum\limits_{k = 0}^m {{\theta _k}} r_{n + 1}^k $

(4)

同理, 构造由n个点组成的另一位置分量数据组{[r_i, b(r_i)]}, i=1, 2, …, n, 训练得到预测位置分量b′(t+1)的m阶多项式回归模型${f_b}\left( {{r_i}} \right) = \sum\limits_{k = 0}^m {{\rho _k}} r_i^k$。利用式(5)计算预测分量b′(t+1), 从而得到下一帧图像中目标的预测位置。

$ {b^\prime }(t + 1) = {f_b}\left( {{r_{n + 1}}} \right) = \sum\limits_{k = 0}^m {{\rho _k}} r_{n + 1}^k $

(5)

3 基于位置预测与邻域一致性的特征配准 3.1 配准搜索区域的划定

为进一步细化第t+1帧目标特征的配准区域, 以第t+1帧目标的预测位置p′_t+1=[a′(t+1), b′(t+1)]为中心, 作矩形待匹配区域l_t+1, 其中, 第t帧标注点及邻域支持特征点集的最小外包矩形尺寸为w_t×h_t, 搜索扩张系数为λ(λ>1), 则待配准区域l_t+1的尺寸为λw_t×λh_t。如果未在当前区域l_t+1中检测到配准点, 则令λ=λ²并继续配准, 直至匹配到特征集合或匹配区域覆盖第t+1帧的全帧区域。

对于第t帧的特征点集P={p_j}_j=1^N和第t+1帧的特征点集Q={q_j}_j=1^N, 采用SVD分解^[21]的方法可以计算两帧特征点集之间的尺度因子s_t和平移向量t_t:

$ \left( {{s_t}, {\mathit{\boldsymbol{t}}_t}} \right) = \mathop {{\mathop{\rm argmin}\nolimits} }\limits_{\begin{array}{*{20}{c}} {{s_t}, \mathit{\boldsymbol{R}}_t^{\rm{T}}{\mathit{\boldsymbol{R}}_t} = {\mathit{\boldsymbol{I}}_m}}\\ {\det \left( {{\mathit{\boldsymbol{R}}_t}} \right) = 1, {\mathit{\boldsymbol{t}}_t}} \end{array}} \sum\limits_{j = 1}^N {\left\| {{s_t}{\mathit{\boldsymbol{R}}_t}{\mathit{\boldsymbol{p}}_j} + {\mathit{\boldsymbol{t}}_t} - {\mathit{\boldsymbol{q}}_j}} \right\|_2^2} $

(6)

3.2 ORB图像特征描述子生成与匹配

ORB算法采用FAST方法进行图像特征检测, 利用具有旋转不变性的BRIEF进行特征描述, 通过比较特征点周围指定数量像素点对的灰度值, 形成二进制码串形式的特征描述子, 并将汉明距离作为匹配依据。具体步骤如下:

步骤1     采用FAST方法进行图像特征检测。针对图形边缘的强响应, 利用Harris角点检测方法对特征点进行排序, 保留前n个点。

步骤2     为实现特征点的尺度不变性, 结合多尺度金字塔对图像分层提取FAST特征点。

步骤3     为实现特征点的旋转不变性, ORB算法采用邻域矩阵计算FAST特征点的方向, 将特征点的灰度I(x, y)和质心间偏移向量的方向定义为特征点方向, 计算过程如下:

$ \theta = \arctan \left( {\frac{{\sum\limits_{x, y} y I(x, y)}}{{\sum\limits_{x, y} x I(x, y)}}} \right) $

(7)

步骤4     选择n个(x, y)测试点对, 定义特征描述子为一个包含n个二进制比较准则的码串, 如式(8)所示。

$ {f_n}(p) = \sum\limits_{1 \le i \le n} {{2^{i - 1}}} \tau \left( {p;{x_i}, {y_i}} \right) $

(8)

其中, τ为图像邻域p的描述子分段函数。

步骤5     针对旋转不变性, 增加特征描述子的方向。根据式(7)得到特征点质心方向信息, 并将其添加至描述子中。在测试点对(x, y)位置处, 定义一个2×n的矩阵如式(9)所示。

$ \mathit{\boldsymbol{Z}} = \left[ {\begin{array}{*{20}{l}} {{x_1}, {x_2}, \cdots , {x_n}}\\ {{y_1}, {y_2}, \cdots , {y_n}} \end{array}} \right] $

(9)

将特征点方向θ对应的旋转矩阵定义为R_θ, 构造特征点对校正矩阵为R_θZ, 最终具有旋转不变性的描述子如下:

$ {g_n}(p, \theta ) = {f_n}(p)|\left( {{x_i}, {y_i}} \right) \in {\mathit{\boldsymbol{Z}}_\theta } $

(10)

步骤6     采用贪婪搜索方法找出相关性最低的像素块对, 直到R_θ中有256个坐标为止, 构成所需的最终特征描述子K=d₀d₁…d₂₅₅。

步骤7     特征点匹配。特征描述子间的相似度依据汉明距离进行判断, 则相似度D(K₁, K₂)的计算如下:

$ D\left( {{K_1}, {K_2}} \right) = \sum\limits_{i = 0}^{255} {{d_i}} \oplus d_i^\prime $

(11)

通过上述步骤获得带描述子的图像预选特征集, 其中, 模板图像区域l_a的特征点全集为{IA_i}_i=1^N, 标注特征集合为{M_i}_i=1^k, 目标图像区域l_b对应的特征点全集为{IB_i}_i=1^N。

3.3 基于支持特征点的图像标注点识别

对于局部GMS图像特征匹配算法, 运动的平滑性导致特征点的轨迹具有一定的连续性, 而运动物体的邻域一致性使得正确匹配点附近邻域里的特征点也是一一对应的。基于ORB的快速图像配准算法, 对框定的图像区域l_a和l_b进行特征点的提取与描述子生成。在进行第i个标注特征M_i的匹配时, 首先以模板图像区域l_a中的M_i为中心, 画一个圆作为邻域Mdom。邻域Mdom中通过ORB算法得到的特征点是中心M_i的支持特征, 利用ORB匹配得到目标图像区域l_b上的支持特征并计算其重心, 以该重心为圆心, 作与模板邻域Mdom大小一致的圆, 即为目标图像邻域, 当两个邻域内有足够多的支持特征点, 即近邻得分S_i大于阈值τ_i时, 该匹配被判定为正确。假设邻域特征分布均匀, 则目标邻域重心即为目标图像待匹配的标注点。

文献[20]推导出了正确匹配点附近的邻域中正确匹配和错误匹配的概率分布, 如式(12)所示。

$ {S_i}\sim\left\{ {\begin{array}{*{20}{l}} {B\left( {{K_n}, {p_t}} \right), M为真}\\ {B\left( {{K_n}, {p_f}} \right), M为假} \end{array}} \right. $

(12)

其中, S_i分布的均值与标准差分别如下:

$ m = \left\{ {\begin{array}{*{20}{l}} {{K_n}{p_t}, }&M为真\\ {{K_n}{p_f}, }&M为假 \end{array}} \right. $

(13)

$ s = \left\{ {\begin{array}{*{20}{l}} {\sqrt {{K_n}t\left( {1 - {p_t}} \right)} , M}为真\\ {\sqrt {{K_n}{p_f}\left( {1 - {p_f}} \right)} , M为假} \end{array}} \right. $

(14)

通过阈值τ_i进行判断的公式如下:

$ \mathit{cell}{\rm{ - }}\mathit{pair }\{ i, j\} \in \left\{ {\begin{array}{*{20}{l}} {T, {S_{ij}} > {\tau _i} = \alpha \sqrt {{n_i}} }\\ {F, 其他{\rm{ }}} \end{array}} \right. $

(15)

为了实现快速评估,文献[20]对图像进行网格划分。将包含10 000个特征的图像划分为20×20的网格,平均每个网格内的特征点个数约为25时,具有较好的匹配效果。将网格四周的3×3=9个网格作为匹配紧邻,用于特征的平滑约束。

3.4 特征模板点集更新

在视频帧配准检索之前要进行目标圈定与标注。视频是目标运动的近似连续性采样, 帧与帧之间的变化具有一定的连续性, 而三维物体在二维视频帧上的投影具有多样性。为了使标注点能长期配准, 保证目标跟踪的长效性, 在邻近帧稳健匹配的前提下, 将配准后的帧更新为模板帧用于下一帧目标匹配, 从而在运动目标具有较大动作的情况下实现准确配准。

本文FRLPNC算法的具体流程如算法1所示。

算法1     FRLPNC算法

输入    第t+1帧图像, 第t帧目标特征点集, 第t帧目标尺寸w_t×h_t, 前n个目标位置

输出    第t+1帧图像的目标位置p_t+1, 目标尺寸w_t+1×h_t+1

1) 将第t+1帧图像之前的n个目标位置{[a(r_i), b(r_i)]}, i=1, 2, …, n和对应的帧号r_i构成回归输入。

2) 利用式(4)和式(5)预测出目标大概位置p′_t+1。

3) 在第t+1帧中以p′_t+1为中心取λw_t×λh_t的待检区域z_t+1。

4) 通过GMS计算模板即第t帧目标特征点集与第t+1帧中区域z_t+1的匹配情况。

5) 如果未能匹配到, 令λ=λ²并扩大匹配区域z_t+1继续进行匹配, 直至匹配成功或匹配区域覆盖第t+1帧全帧区域。

6) 计算t+1帧匹配点集的最小外包矩形w_t+1×h_t+1。

7) 更新t+1帧特征点集, 并将其作为模板, 更新当前帧目标尺寸w_t+1×h_t+1和前n个目标位置。

从算法1可以看出, 本文结合目标位置区域进行预测, 进一步缩小特征搜索区域, 大幅减少配准工作量。在未能实现配准时, 以预测中心为基准依次进行扩张匹配, 利用运动合理性避免不必要的错误匹配。另外, 本文根据近邻帧的稳健匹配, 在运动连续性的约束下, 保障特征模板的稳健传递, 以实现多姿态的运动配准。本文所采用的GMS特征配准方法是当前较为稳定和高效的特征配准方法。根据理论分析可知, 本文算法能有效减少配准时间, 增加目标配准姿态, 提高配准精度和稳健性。

4 实验结果与分析

为验证本文算法的精确性、实时性和鲁棒性, 选择OTB-100、TUM、VGG和Cabinet数据集^[22-24]进行实验, 并与GMS算法^[20]、ORB算法^[17]、SIFT算法^[13]和SURF算法^[14]进行对比。本节设置了两组实验, 第1组实验进行视频序列的跨帧匹配, 以验证本文算法中引入位置预测的有效性, 第2组实验进行视频序列的连续跟踪, 以评估本文算法的整体性能。本文算法采用Python代码实现, 并在配置为Core i7-7700k和16 GB RAM的电脑上运行。通过大量实验可知, 当搜索扩张系数λ=1.5, 多项式回归中的阶数m=2, 并基于前n=6帧图像的目标位置进行位置预测时, 算法的跟踪效果较好。

4.1 视频序列的跨帧匹配对比

由于视频序列中前后两帧的目标姿态变化不大, 为了增加视频跟踪的难度, 验证本文算法在目标姿态变化较大时的跟踪效果, 本文选取跨越的视频帧进行视频序列的跨帧匹配。选择OTB-100数据集中的Surfer和Bird2视频序列进行实验, 每一次实验在连续的视频序列中随机进行帧跳跃, 跳跃的帧数从5帧到25帧不等, 需要注意的是Surfer和Bird2视频序列各进行50次实验, 每次仅对视频序列进行一次随机帧跳跃。

5种特征点匹配跟踪算法对Surfer和Bird2视频序列的部分跨帧匹配结果如图 2、图 3所示。以图 2中Surfer视频序列的一次实验为例, 前59帧是连续出现的, 在第59帧时令该序列直接跨越到第67帧, 以检验各特征点匹配跟踪算法的跨帧匹配性能。由图 2、图 3可以看出, 与其他4种特征点匹配跟踪算法相比, 本文算法的错误匹配对较少, 所有匹配对基本达到正确的对应关系, 实现了最佳匹配。

统计本文算法与GMS、ORB、SIFT和SURF这4种算法每一次随机帧跳跃后的正确匹配数量和错误匹配数量, 计算匹配精度并记录运行时间, 结果如表 1所示。可以看出, 本文算法、GMS算法、ORB算法的平均匹配精度分别为98.72%、77.45%和94.22%, 本文算法的平均匹配精度比ORB算法提高了约27%, 说明在进行视频序列的跨帧匹配时, 引入融合前序视频帧的位置预测可有效提高视频目标跟踪的准确性。此外, 受益于ORB算法的高匹配速度, 本文算法的运行速度比GMS算法、SIFT算法和SURF算法更快, 证明了本文算法的实时性。

4.2 视频序列的连续跟踪对比

本文选择OTB-100、TUM、VGG和Cabinet这4个数据集进行视频序列的连续跟踪对比。采用文献[4]中的评价标准, 即中心位置误差(CLE)、距离精度(DP)、重叠精度(OP)对算法的跟踪效果进行评价。其中, 中心位置误差阈值取10像素, 重叠率阈值取0.7, 5种算法的跟踪性能对比如表 2所示。

从表 2可以看出, 与其他4种特征点匹配跟踪算法相比, 本文算法的连续跟踪结果较好。其中, 本文算法的平均CLE为3.71像素, 相对于其他4种跟踪算法有所下降, 平均DP、平均OP分别达到93.4%和90.2%, 高于其他4种跟踪算法。实验结果表明, 本文方法引入的位置预测机制使得跟踪算法能够对目标进行精确的位置估计, 获得更加稳健的跟踪效果。在平均FPS上, 本文算法排在第2位, 说明GMS算法在引入多项式回归位置预测方法后, 对目标有精确的定位能力, 减少了特征点的匹配时间。由于GMS算法和本文算法的核心都是ORB算法的特征点提取、描述子生成与初步配准, 因此ORB算法的配准速度更快。GMS算法在ORB算法的基础上增加配准校验过程, 以较小的时间代价使得配准的稳健性大幅提升, 而本文算法在视频特征点配对过程中引入位置预测, 能大幅减少不必要特征点的生成与配准检测工作, 缩短配准时间。

图 4、图 5分别是5种特征点配准跟踪算法在4个视频数据集上的距离精度曲线和成功率曲线。从图 4和图 5可以看出, 本文方法的距离精度曲线和成功率曲线均高于其他跟踪方法, 说明帧间的稳定匹配与模板传递可以改善多姿态目标特征点的配准性能, 验证了本文算法的优越性。结合表 2可知, 本文算法能有效减少配准时间, 提升配准精度, 丰富配准姿态, 使得配准更加稳健。本文算法与其他4种特征点配准跟踪算法的部分跟踪结果如图 6所示。

5 结束语

本文提出一种基于特征位置预测与邻域一致性约束的视频特征快速配准算法FRLPNC。通过ORB特征匹配与邻域一致性检验获得帧间标注点集配准, 应用点集间的仿射变换与多项式回归确定当前搜索区域, 以减少不必要特征点的生成与配准检测工作。同时采用ORB算法生成特征描述点集, 根据GMS算法的局部邻域一致性约束, 设定模板标注点邻域范围, 通过统计模板标注点邻域范围内支持特征点的匹配情况确定待匹配标注点坐标。实验结果表明, 与GMS、ORB等算法相比, 该算法的视频目标特征点配准的实时性、准确性与鲁棒性均有所提升。对视频目标特征点的遮挡进行有效恢复并对目标进行跟踪将是下一步的研究方向。