基于特征点的典型目标跟踪算法性能分析

窦慧; 赵书斌; 王强

doi:10.3969/j.issn.1673-3819.2017.02.014

指挥控制与仿真 >

2017 , Vol. 39 >Issue 2: 67 - 75

DOI: https://doi.org/10.3969/j.issn.1673-3819.2017.02.014

理论研究

基于特征点的典型目标跟踪算法性能分析

窦慧 ,
赵书斌 ,
王强

展开

江苏自动化研究所, 江苏连云港 222061

窦慧(1992-),女,硕士研究生,陕西榆林人,研究方向为目标跟踪。

赵书斌(1968-),男,博士,研究员。

王强(1986-),男,硕士,工程师。

收稿日期: 2016-11-02

修回日期: 2016-12-04

网络出版日期: 2022-05-20

收起

Evaluation of Feature Points Based Object Tracking

DOU Hui ,
ZHAO Shu-bin ,
WANG Qiang

Expand

Jiangsu Automation Research Institute, Lianyungang 222061, China

Received date: 2016-11-02

Revised date: 2016-12-04

Online published: 2022-05-20

Fold

摘要

目标跟踪问题是当前计算机视觉领域中的热点问题之一。本文主要对基于特征点的目标跟踪进行介绍。首先,对目标跟踪的定义、过程和主要应用领域进行了概述;其次,阐述了运动目标跟踪算法的分类,并介绍了基于特征的跟踪算法的研究现状;随后介绍了典型的特征提取和描述方法,并从理论的角度分析各跟踪算法性能;针对基于特征点的典型跟踪算法,在目标尺度和形状的变化、跟踪过程中发生遮挡情况等方面的场景下进行实验,对算法性能进行分析比较。从理论和实验的角度相互验证了基于特征点的典型跟踪算法的性能并给出相关结论。

关键词： 目标跟踪; 性能分析; 特征点

本文引用格式

窦慧 , 赵书斌 , 王强 . 基于特征点的典型目标跟踪算法性能分析[J]. 指挥控制与仿真, 2017 , 39(2) : 67 -75 . DOI: 10.3969/j.issn.1673-3819.2017.02.014

Abstract

Object tracking is an important task within the field of computer vision. This paper introduces the feature points based object tracking. First, we summarize the definition and process and application of object tracking. Second, the classifications and current situation of object tracking are shown. In addition,we give a brief introduction on the typical methods of feature extraction and description. The performance of tracking algorithms is compared in various video sequences on Matlab. Meanwhile, some future directions of visual tracking are addressed shortly.

Key words： object tracking; performance evaluation; feature point

目标跟踪是计算机视觉领域中的重要研究课题^[1]。目标跟踪技术在人机交互^[2]、智能交通^[3]、无人驾驶^[4]等方面有广泛应用。目标跟踪是指目标在某种场景中运动时,建立其在此期间的运动轨迹。换句话说,目标跟踪的目的是在序列图像中的每帧中实时地确定运动目标位置、速度等信息^[5]。

目标跟踪算法分为量测部分、更新策略、预测部分^[6]。量测部分包括目标的表达和匹配过程;更新策略包括对模板、目标位置、速度等相关参数进行更新;预测部分是基于量测数据,利用滤波算法对目标状态进行预测。

运动目标跟踪算法根据目标的表达可分为基于区域的跟踪算法、基于轮廓的跟踪算法、基于模型的跟踪算法、基于特征的跟踪算法^[7]。

基于特征的跟踪算法使用目标的某个或某些局部特征表示目标。与基于区域的跟踪算法相比,基于特征的跟踪算法在目标发生部分遮挡时也可实现跟踪。与基于轮廓和基于模型的跟踪算法相比,基于特征的跟踪算法更具有普遍性,适用目标更广,计算复杂度更低^[8]。

基于特征的跟踪算法根据自身特性应用于不同情况。文献[9]采用基于Harris特征点的跟踪算法,提取目标上稳定性高的轮廓交叉点,不随目标姿态变化消失,从而确定目标模板进行跟踪,并通过实验证明跟踪具有极高的稳定性。文献[10]将简化SIFT算法应用于目标跟踪算法中,降低了算法复杂度和对内存空间的要求,并将算法应用到实际工程中。

基于特征的跟踪算法的跟踪流程包括:1)初始帧进行目标检测或直接选取目标;2)选取合适的模板并进行特征提取和表达;3)读取视频当前帧图像,根据滤波算法获得目标在当前帧的预测参数,确定搜索范围;4)在搜索范围内进行特征提取和表达,以一定的匹配算法对当前帧特征和模板特征进行匹配;5)验证匹配结果,若匹配成功则根据匹配特征对参数确定目标在当前帧的位置等信息,并按策略更新模板,若匹配失败则放弃该帧;重复过程2)~5)对目标进行跟踪。

由此可见,基于特征的跟踪算法最关键的问题之一是特征的选择、提取和描述,针对具体场景选取合适的目标特征,是目标跟踪成败的关键。本文主要讨论摄像机静止条件下采用不同特征点对目标跟踪算法的影响,故省略目标跟踪中的滤波过程。

影响目标跟踪技术的主要因素有:背景的光照变化;背景中存在与目标相似的区域;目标尺度和形状的变化;跟踪过程中发生遮挡情况等。故本文主要针对基于特征点的典型跟踪算法,在目标尺度和形状变化、跟踪过程中发生遮挡情况等方面的场景下进行实验,并对采用不同特征点的跟踪算法的性能进行分析比较。

1 图像特征点的提取和描述

特征点作为典型特征广泛应用于目标跟踪算法中。特征点主要分为角点和斑点。经典的角点检测方法如下:1980年,Moravec提出了利用灰度方差检测兴趣点的算法算子^[11];1988年,Harris和Stephens在Moravec 算子基础上改进提出Harris算子^[12];1997 年 Smith 等人提出的一种用最小核心值相似区域提取特征点的方法,即SUSAN算子^[13];用图像滤波响应的局部极值点表示的特征点称为斑点;2004年, Lowe 结合尺度空间相关特性,提出了具有尺度不变性和旋转不变性的SIFT 算子^[14];2008年,Bay在SIFT 算子基础上改进提出SURF算子^[15],在速度上极大地优于SIFT算子性能。

1.1 Harris算子

w(x,y)是高斯平滑因子,像素点(x,y)的灰度f(x,y),f_x,f_y为图像灰度在x和y方向梯度向量的分量,像素点(x,y)的灰度平均变化量E(u,v)利用泰勒级数沿x和y方向展开,则表示为

(1)E(u,v)=

∑ x, y

W(x,y)(f(x+u,y+v)-f(x,y))²

= ∑ x, y w (x, y) (u f x + v f y + O (u 2 + v 2)) 2

令对称矩阵M:

(2)M=

∑ x, y

w(x,y)

f x 2 f x f y f x f y f y 2

(3)E(u,v)≅[u,v]M

u v

E(u,v)=const,求取矩阵M的特征值λ₁和λ₂。当λ₁和λ₂值较大且大小相差不大时,E(u,v)在各个方向变化大,认为像素点为角点;故角点响应函数定义为:

(4)R=detM-k(trM)²

其中M与其特征值λ₁和λ₂具有如下关系:

(5)detM=λ₁λ₂

(6)trM=λ₁+λ₂

计算各像素点的R值,当R大于设定的阈值时,则认为该点为角点。通常k=0.04~0.06。灰度图像中,常采用角点所在像素的灰度值u(x,y)对特征点进行描述。

1.2 SIFT算法

SIFT算法实现特征提取主要有以下几个步骤:

1) 检测尺度空间极值点

在DOG尺度空间中定义函数为D(x,y,σ),G(x,y,σ)为高斯函数,常数k为尺度空间比例系数。

(7)D(x,y,σ)=(g(x,y,kσ)-g(x,y,σ))*I(x,y)=L(x,y,kσ)-L(x,y,σ)

SIFT算法通过 DOG 算子检测尺度不变特征点。在DOG金字塔空间中搜索函数在三维邻域取极值的点,确定为关键点。

2) 精确定位关键点

利用Hessian 矩阵去除边缘响应点。设λ₁和λ₂为 Hessian 矩阵的特征值,比值为r,则

(8)H=

D x x D x y D x y D y y

(9)det H=D_xxD_yy-(D_xy)²=λ₁λ₂

(10)trH=D_xx+D_yy=λ₁+λ₂

(11)ratio=

(t r H) 2 d e t H

(λ 1 + λ 2) 2 λ 1 λ 2

(r + 1) 2 r

设r,若ratio≤

(r + 1) 2 r

,保留关键点,反之去除。

3) 确定关键点方向

为特征点指定方向参数,使算子具有旋转不变性。

(12)m(x,y)=

(L (x + 1, y) - L (x - 1, y)) 2 + (L (x, y + 1) - L (x, y - 1)) 2

(13)θ(x,y)=arctan2((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y)))

当另一个峰值能量大于主峰值能量的80%,将这个方向认为是关键点的辅方向。至此,关键点检测完成,每个关键点具有3个信息:位置、尺度和方向。

4) 生成特征描述符

将坐标轴旋转为关键点的方向,以关键点为中心取8*8大小的窗口,在每4*4区域内计算8个方向的梯度方向直方图,生成一个2*2*8的32维的特征向量。实际计算时,采用4*4*8的128维的特征向量,形成特征描述子。

1.3 SURF算法

1) 构建Hessian矩阵

通过Hessian矩阵提取特征点。设像素I(x,y), Hessian矩阵的定义为:

(14)H(x,σ)=

L x x (x, σ) L x y (x, σ) L x y (x, σ) L y y (x, σ)

利用高斯函数滤波:

(15)L(x,t)=G(t)·I(x,t)

(16)G(t)=

∂ 2 g (x) ∂ x 2

式中,g(x)为高斯函数,t为高斯方差。为简化运算提升速率,用D(x,t)代替L(x,t)。所以Hessian矩阵判别式定义:

(17)det(H_approx)=D_xxD_yy-(0.9D_xy)²

权值0.9为经验值。根据判别式符号对像素点分类,确定是否为极值点。

2) 构建尺度空间

在SURF算法中,图片的尺寸是不变的,通过调整高斯模板的尺度处理图片,得到待处理图片。SURF算法可以并行处理不同多层图像,极大地提升运算速度。

3) 确定特征点

此步骤与SIFT算法相似,对经过Hessian矩阵处理过的像素点与其三维邻域内相邻的26个点比较,当其值为极值时保留为特征点,否则舍弃。

4) 确定特征点主方向

通过统计特征点邻域内的Harr小波特征确定方向。在特征点邻域内统计60°扇形区域内全部像素点的Haar小波特征。60°扇形区域以一定间隔旋转,将最大值的扇形方向作为特征点主方向。

5) 构造特征描述子

在特征点的周围取边长为20倍所在尺度的正方形框,方向为主方向,将其分为4*4的子块,每个子块取5*5的采样点,统计采样点的Haar小波特征dx和dy。对每个子块dx、dy、|dx|、|dy|分别求和。则每个特征点可以构成4*4*4=64维的特征描述子。

1.4 理论分析

各特征提取和表示算法的理论基础决定了基于特征的目标跟踪算法的根本性质。特征点是目标局部特征,目标部分遮挡情况下有机会利用其未遮挡的特征点实现跟踪,故基于特征点的跟踪算法均具有一定的抗遮挡能力。

Harris算法提取的角点特征,不受目标旋转变化影响,故基于Harris的跟踪算法可以一定程度上实现跟踪发生旋转变化的目标。Harris算法在不同尺度上提取的角点并不相同,故经典基于Harris的跟踪算法对尺度发生变化的目标无法实现跟踪。SIFT和SURF算子在尺度空间中构建,具有尺度不变性,故理论上基于SIFT和SURF的跟踪算法具有一定处理目标发生尺度变化的能力。SIFT和SURF的特征描述符分别为包含方向的128维和64维特征向量,算子具有旋转不变性,故理论上基于SIFT和SURF的跟踪算法具有一定处理目标发生旋转变化的能力。

2 实验及算法性能评估

基于上文的理论分析,对基于特征点的目标跟踪算法进行实验。本文主要讨论跟踪过程中目标出现各种变化时,各基于特征点的跟踪算法性能的优劣。

本文采用一段500帧的240*256的视频和一段482帧的360*240的视频作为测试序列,以Matlab2012a为仿真工具进行实验。下图图片为在不同跟踪算法实验中分别截取相同帧对跟踪结果进行观察。跟踪算法的评价主要考虑:①精确性,算法检测到的目标和真实的目标之间的符合程度;②距离误差,算法检测到的目标位置和实际目标位置间的距离。本文中均以矩形模板的中心点作为目标位置。本文主要用presicion和Err进行性能评价。

(18)score_t=

a r e a R O I T ⋂ R O I G a r e a R O I T ⋃ R O I G

(19)presicion=

∑ t

score_t/n

其中,score_t表示t时刻检测目标和真实目标面积的交集和并集的比。presicion是score_t的平均值,其范围在0-1,值越靠近1,算法性能越好。

(20)Err=

∑ t (x t - x^t) 2 + (y t - y^t) 2

其中,Err为目标的位置平均误差,x_t,y_t为目标t时刻的真实位置的质心位置,

x^t

y^t

为跟踪位置算法t时刻跟踪得到的质心位置。n为总帧数。Err表示以像素为单位的距离,值越小表示算法性能越好。

1) 目标遮挡情况下的性能评估

第一段实验视频的实验结果如图1-3所示。

	实验数据一		实验数据二
	帧间旋转5°	帧间旋转10°	帧间旋转5°	帧间旋转10°
harris	0.8791	0.8113	0.8574	0.7923
SIFT	0.8920	0.8275	0.8956	0.8859
SURF	0.8837	0.8163	0.8823	0.8646

	实验数据一		实验数据二
	缩放比例小	缩放比例大	缩放比例小	缩放比例大
harris	0.5485	0.4387	0.3884	0.3541
SIFT	0.9246	0.8308	0.9175	0.8429
SURF	0.9103	0.8952	0.9163	0.8759

	实验数据一	实验数据二
harris	0.8590	0.8797
SIFT	0.9146	0.9245
SURF	0.9156	0.9285

	实验数据一	实验数据二
harris	2.0051	1.8548
SIFT	1.4055	1.2563
SURF	1.3112	1.3254

	实验数据一		实验数据二
	帧间旋转5°	帧间旋转10°	帧间旋转5°	帧间旋转10°
harris	3.7808	4.5284	3.4815	4.0257
SIFT	1.6742	1.9138	1.7528	2.0548
SURF	1.6999	2.4618	1.8169	2.4875

模态框（Modal）标题

摘要

本文引用格式

Abstract

1 图像特征点的提取和描述

1.1 Harris算子

1.2 SIFT算法

1.3 SURF算法

1.4 理论分析

2 实验及算法性能评估

图1 实验一遮挡情况下基于harris的目标跟踪算法

图2 实验一遮挡情况下基于SIFT的目标跟踪算法

图3 实验一遮挡情况下基于SURF的目标跟踪算法

图4 实验二遮挡情况下基于harris的目标跟踪算法

图5 实验二遮挡情况下基于SIFT的目标跟踪算法

图6 实验二遮挡情况下基于SURF的目标跟踪算法

表1 精确性1 presicion

表2 距离误差1 Err

图7 帧间旋转5°基于harris的目标跟踪算法

图8 帧间旋转5°基于SIFT的目标跟踪算法

图9 帧间旋转5°基于SURF的目标跟踪算法

图10 帧间旋转10°基于harris的目标跟踪算法

图11 帧间旋转10°基于SIFT的目标跟踪算法

图12 帧间旋转10°基于SURF的目标跟踪算法

图13 帧间旋转5°基于harris的目标跟踪算法

图14 帧间旋转5°基于SIFT的目标跟踪算法

图15 帧间旋转5°基于SURF的目标跟踪算法

图16 帧间旋转10°基于harris的目标跟踪算法

图17 帧间旋转10°基于SIFT的目标跟踪算法

图18 帧间旋转10°基于SURF的目标跟踪算法

表3 精确性2 presicion

表4 距离误差2 Err

图19 缩放比例小时基于harris的目标跟踪算法

图20 缩放比例小时基于SIFT的目标跟踪算法

图21 缩放比例小时基于SURF的目标跟踪算法

图22 缩放比例大时基于harris的目标跟踪算法

图23 缩放比例大时基于SIFT的目标跟踪算法

图24 缩放比例大时基于SURF的目标跟踪算法

图25 缩放比例小时基于harris的目标跟踪算法

图26 缩放比例小时基于SIFT的目标跟踪算法

图27 缩放比例小时基于SURF的目标跟踪算法

图28 缩放比例大时基于harris的目标跟踪算法

图29 缩放比例大时基于SIFT的目标跟踪算法

图30 缩放比例大时基于SURF的目标跟踪算法

表5 精确性3 presicion

表6 距离误差3 Err

3 结束语

参考文献