基于梯度投影的视频跟踪算法

李志军，陈 雪，李志刚，顾海军

(吉林大学通信工程学院，长春130012)

0 引言

视频跟踪是近年来新兴的一个研究方向，它融合了计算机视觉、模式识别和人工智能等学科技术，在安全监控，智能交通，电视制导，人机交互和机器人视觉导航等方面有广阔的应用前景［1-3］。视频跟踪系统以视频流(图像序列)为输入，对视频流中的运动目标进行检测、提取、识别和跟踪，以获得图像中目标的各种属性特征，如目标大小，位置，质心等作为输出。

实现对视频序列中运动目标的跟踪，首先要对运动目标进行精确检测［4-6］。目标检测是指运用目标先验知识或运动特性，基于目标几何或统计特征，提取序列图像中与背景相对运动的前景目标，是视频跟踪的基础。目前常用的视频目标检测方法有:帧间差分法、背景差分法和光流法。前两种方法原理简单、容易实现，但仅对静态背景的运动目标检测效果好。光流法利用运动目标随时间变化的光流特性，通过计算光流检测运动。光流法抗干扰性强，具有高精确率，可以直接获得运动目标的运动参数等优点，但其原理复杂，计算量较大，在没有专用硬件支持的情况下很难做到实时检测。

与目标物的检测相比，目标的跟踪属于更高级别的计算机视觉问题［7-9］。现有的视频跟踪方法主要分为两大类。第1类方法，是通过当前时刻目标运动状态量迭代预测下一帧目标的状态实现目标的跟踪。第2类视频跟踪方法是利用目标的不同特征，例如颜色或灰度信息、形状及运动信息等，通过预测帧与帧之间目标特征变化进行目标跟踪。

基于以上分析，结合常用目标检测算法的不足与跟踪算法的基本思路，针对每帧视频图像中的目标与背景之间的灰度变化的特点，以及当目标刚进入视场时，目标很小，目标的纹理、角点等特征不明显的问题，同时为了解决传统算法实时性不强的问题，笔者提出基于梯度投影的目标跟踪算法。

1 梯度投影的视频跟踪算法

梯度投影算法根据图像灰度分布的特点求取每帧图像中的目标区域(或疑似目标区域)，首先对图像进行区域分割梯度增强处理［10］，突出目标边界信息;通过部分灰度投影［11］寻找疑似目标(或目标)的位置信息，更新搜索窗(或跟踪窗)位置大小，在跟踪过程中，计算每帧灰度图像的质心，修正跟踪窗的位置大小信息。本算法主要分为2个过程，即基于区域分割的梯度增强与部分灰度投影。

1.1 基于区域分割的梯度增强

区域分割的梯度增强的实现过程，首先对图像帧中的相邻像素点间进行一阶差分运算，称为梯度运算，其次利用自适应阈值对梯度运算后的图像进行区域划分与增强运算。

这里根据图像像素点的一阶差分，对图像进行划分。

设视频流中的第n帧图像为In，In(i，j)为第n帧图像在(i，j)点处的灰度值，则图像的一阶水平差分定义为

根据dy的大小，可将图像划分成两个区域，即dy＞Ty与dy＜Ty。其中Ty为阈值，dy＞Ty为疑似目标区域(目标像素群);dy＜Ty为背景区域。目标检测的目的是提取目标区域，抑制背景区域。因此，根据不同区域设定图像增强的灰度值

若dy＞Ty，设定当前的像素点值为In(i，j)=dy，为目标像素群;否则In(i，j)=0。算法实现框图如图1所示。

图1 区域分割梯度增强实现框图Fig.1 Regional segmentation and gradient enhanced

阈值Ty的选取:当光照强度低时，目标与背景的区域分割梯度增强后的像素点灰度差值较小，故光照强度较低时希望Ty值相对小一点;而光照强时希望Ty值大一点。故Ty应为图像像素点的灰度值相关的值，根据大量的实验数据分析，Ty应该为窗体(搜索窗或跟踪窗)内的所有像素点灰度值和的平均除8加上修正值1。

自适应阈值的具体确定过程如下

自适应阈值的计算公式为

其中搜索窗(或跟踪窗)的高宽分别为H、W，则窗内的所有像素灰度值之和为

在整个跟踪过程中的阈值均由公式Sa=Sg/(HW)求解。区域分割梯度增强，扩大了图像中目标与背景特征之间的差别，突出目标的边界信息，便于边界提取。

1.2 部分灰度投影

对输入的二维图像进行梯度增强后，通过稀疏变换，将其灰度信息映射成两个独立的一维投影序列。Sr，Sc分别为投影区域行高、列宽的起点位置坐标。

图像第i行的灰度投影值为

图像第j列的灰度投影值为

投影曲线反映了图像灰度分布的特点，为方便描述，将图像行方向的投影曲线记为水平投影曲线，将图像列方向的投影曲线记为垂直投影曲线。传统灰度投影通常采用全投影，即将投影区域每行(列)进行映射，行(列)内的每个像素都参与投影。笔者提出的投影算法是基于部分图像的投影计算:目标检测阶段对每帧图像开窗，对窗体内的图像进行增强投影;在跟踪处理过程中对疑似目标区域进行投影。与传统灰度投影相比，该算法提高了运算速度。然而该算法对灰度值单一的图像处理效果不佳，当图像灰度值单一、对比度很差时，会造成投影曲线很平，提取的目标区域不精确，导致后续处理难度增大。

对投影曲线进行区域分割增强处理，在目标搜索或跟踪过程中降低非目标区域的干扰。对大于某个阈值的投影值保留，否则置为零。为避免目标区域投影后使目标投影曲线出现不连续的现象，该算法对投影曲线进行平滑处理，通过对投影曲线判断，对断点进行连通。

2 基于梯度增强投影视频跟踪算法的实现过程

视频跟踪过程主要分为目标检测与跟踪两个步骤［12］。通用的视频跟踪系统实现框图如图2所示。该算法实现视频跟踪的具体步骤如下。

图2 视频跟踪系统框图Fig.2 Frame of video tracking system

2.1 目标检测

1)区域检测。首先，进行区域分割增强与水平投影以及对投影曲线的平滑处理。其次，疑似目标区域的确定，搜索投影曲线的波峰波谷获得疑似目标区域在图像中的垂直方向位置信息，即获得搜索窗的位置信息。

2)图像二值化处理。采用自适应阈值(Ty)，对原图的疑似区域二值化处理。所有灰度值大于或等于阈值的像素群被判定属于疑似目标;否则这些像素群被排除在目标区域之外，表示为背景或干扰物体。图像二值化目的方便图像的进一步处理，使图像变得简单，而且数据量减小，能凸显出感兴趣的目标轮廓。

3)特征提取。将二值后的疑似区域进行特征提取与形态学分析，求解疑似区域中目标各种属性参数，如，质心、长短轴长和方向角等。

4)目标的判别。根据目标的特征组合成一些约束条件，滤除不符合要求的“假目标”。即通过对目标先验知识的理解认知，组合成不同的约束条件，输入到判别算法部分。判别函数根据输入条件，确定目标。如，实验限制目标的长宽比，方向角的范围以及相邻质心之间的距离确定目标。捕获成功目标后，触发跟踪处理进程，将目标的位置及目标区域的大小输出到跟踪部分。

2.2 目标跟踪

目标检测与判别成功后，触发跟踪处理进程，利用目标识别结果初始化跟踪部分，对视频流开小窗处理。首先，对图像进行水平投影，获得目标的垂直方向的大概位置坐标;其次，在水平投影获取的目标区域范围对图像进行垂直投影，获得目标水平方向的大致位置坐标;最后，利用水平、垂直投影获得的目标位置信息，对小区域内计算质心。利用当前帧目标质心坐标更新与修正下一帧跟踪窗位置的大小。目标跟踪过程如图3所示。

图3 目标跟踪框图Fig.3 Frame of target tracking

目标跟踪过程的具体步骤如下。

1)水平梯度投影。利用目标检测阶段输出的目标位置大小信息(仅执行一次，以后利用质心坐标更新目标位置信息，即跟踪窗的位置信息)，对视频流开窗，执行目标检测步骤1);根据投影曲线的波峰波谷位置确定目标在垂直方向的位置坐标。

2)垂直梯度投影。根据步骤1)中输出的位置坐标，对目标区域进行垂直梯度投影，同1)获取目标水平方向的位置坐标。

3)质心计算。根据1)、2)中确定的区域位置大小信息，计算此区域质心。

4)更新目标的位置信息。利用当前帧质心坐标更新下一帧目标的位置信息以及跟踪窗的位置大小信息，当前帧质心坐标输出到跟踪输出进程。

2.3 算法流程图

算法流程图如图4所示。

图4 算法流程图Fig.4 Flow chart of algorithm

3 实验结果与分析

为验证系统架构，笔者对帧速为15帧/s、图像大小为270×216像素的视频序列进行测试。实验结果表明，该算法能可靠地对复杂场景下目标实时、准确地跟踪。

1)第345帧视频图像如图5所示。目标刚进入视场，未进搜索窗内。搜索窗位置坐标为(x=1∶216;y=200∶240)，此时Ty=28。

此帧处于搜索状态，目标未进入搜索窗内，对搜索窗内区域分割梯度增强(见图6)后的图像进行水平投影(为噪声的投影曲线，如图7所示)，获取疑似目标区域，对原视频帧图像进行二值处理，判断非目标，不进行跟踪标记。由此可知，非目标区域二值处理后经判断干扰噪声被滤除。

图5 第345帧Fig.5 345th frame

图6 梯度增强图像Fig.6 Gradient enhanced

图7 水平投影Fig.7 Horizontal projection

2)第375帧，如图8所示，目标进入搜索窗，捕获成功。

图9为梯度增强图像，图10为二值图像。根据图11中水平投影曲线，获取目标在垂直方向的位置信息(垂直方向上下坐标分别为70，76;阈值Ty=183)，对二值化处理的小区域图像进行特征提取与连通性分析，并判断是否为目标，判断成功，进行跟踪输出(见图12)。

图8 第375帧Fig.8 375th frame

图9 梯度增强图像Fig.9 Gradient enhanced

图10 二值图像Fig.10 Binary image

图11 水平投影图Fig.11 Horizontal projection

图12 跟踪图Fig.12 Tracking figure

3)第411帧视频图像如图13所示，梯度增强图像如图14所示，处于跟踪状态的跟踪结果如图15所示。

第411帧由图16中水平投影获取目标垂直方向上下点的坐标分别为56，62;由图17垂直投影获取目标水平方向左右点的坐标分别为184，192，目标的质心坐标为(59，187)。此时阈值Ty=212。

第412帧图像、梯度增强图像和跟踪图分别如图18～图20所示。由图21中水平投影获取目标垂直方向上下点的坐标分别为58，64;由图22垂直投影获取目标水平方向左右点的坐标分别为185，193，目标的质心坐标为(60，188)。此时阈值Ty=213。

由水平投影获得目标在垂直方向的坐标信息;对垂直方向进行投影获取目标在水平方向的坐标信息，在跟踪状态中，跟踪窗是小范围的，故第1波峰的起点与第2波峰的终点确定为目标在水平方向的大小。

图13 第411帧图像Fig.13 411th frame

图14 梯度增强图像Fig.14 Gradient enhanced

图15 跟踪图Fig.15 Tracking figure

图16 水平投影Fig.16 Horizontal projection

图17 垂直投影Fig.17 Vertical projection

图18 第412帧图像Fig.18 412th frame

图19 梯度增强图像Fig.19 Gradient enhanced

图20 跟踪图Fig.20 Tracking figure

图21 水平投影Fig.21 Horizontal projection

图22 垂直投影Fig.22 Vertical projection

在跟踪输出上显示当前帧目标的质心坐标［wr，wc］。根据质心坐标对目标进行标记，并更新下一帧的搜索范围。

4)采用两个标准的度量准则，即处理速度与跟踪正确率测试该算法。处理速度定义为跟踪算法每帧的处理时间，单位为ms/帧，其值越小，算法的实时性越强。跟踪正确率TA=NA/N，其中N为视频序列包含目标图像的帧数，NA为在N帧图像中准确跟踪目标的总帧数。其值越大，表明系统的稳定性越高，系统的鲁棒性强。表1为笔者算法与文献［5］算法的对比结果。由表1可看出，笔者算法能在当帧内完成运算，而传统算法则不能，由此可以看出，笔者算法的实时性较强;通过统计计算，算法的准确率较传统算法高，稳定性好。

表1 测量准则Tab.1 Metrics

4 结论

笔者提出了梯度投影的跟踪算法。通过区域分割与灰度投影获取目标位置信息。该算法解决了目标很小时，其纹理、角点等特征不明显，利用传统的检测算法无法识别目标的困扰。该算法利用目标的先验知识，对目标进行自动检测。在整个目标检测与跟踪的过程中，该算法绕开常规的目标检测算法对整帧图像进行处理，对视频流中单帧图像进行开窗处理与稀疏变换，减小了运算量，提高系统的运算速度。该算法原理简单，实时性强，实现了对目标的可靠性与稳定性跟踪。

［1］王书朋.视频目标跟踪算法研究［D］.西安:西安电子科技大学电子工程学院，2009.WANG Shupeng.Research on Methods of Visual Object Tracking［D］.Xi'an:College of Electronic Engineering，Xidian University，2009.

［2］黄欣欣.复杂场景下视觉目标跟踪方法研究［D］.广州:华南理工大学计算机科学与工程学院，2010.HUANG Xinxin.Visual Target Tracking Method Study in Complex Scene［D］.Guangzhou:College of Computer Science and Engineering，South China University of Technology，2010.

［3］李波.视频序列中运动目标检测与跟踪算法的研究［D］.北京:北京交通大学电子信息工程学院，2011.LI Bo.Study on Moving Object Detection and Tracking in Video Sequences［D］.Beijing:College of Electronic Information Engineering，Beijing Jiaotong University，2011.

［4］SIMON DENMAN，CLINTON FOOKES，SRIDHA SRIDHARAN.Improved Simultaneous Computation of Motion Detection and Optical Flow for Object Tracking［J］.Digital Image Computing:Techniques and Applications，2009，35(9):175-182.

［5］徐瑞，王睿，李怡，等.动态场景下基于Bayesian分类光流法的运动目标检测［J］.仪器仪表学报，2011，32(12):66-70.XU Rui，WANG Rui，LI Yi，et al.Moving Objects Deteetion Using Optical Flow Based on Bayesian Classifier in Dynamic Scence［J］.Chinese Journal of Scientific Instrument，2011，32(12):66-70.

［6］施家栋，王建中.动态场景中运动目标检测与跟踪［J］.北京理工大学学报:2009，29(10):858-860，876.SHI Jiadong，WANG Jianzhong.Moving Objects Detection and Tracking in Dynamic Scene［J］.Journal of Beijing Institute of Technology，2009，29(10):858-860，876.

［7］DAN SCHONFELD.Dynamic Proposal Variance and Optimal Particle Allocation in Particle Filtering for Video Tracking［J］.Circuits and Systems for Video Technology，IEEE Transactions on，2008，18(9):1268-1279.

［8］WANG Junxian，GEORGE BEBIS，RONALD MILLER.Robust Video-Based Surveillance by Integrating Target Detection with Tracking［C］∥Computer Vision and Pattern Recognition Workshop Conference on Digital Object Identifier.New York，USA:［s.n.］，2006:137-144.

［9］CHEN Ken，ZHANG Meng，BATUR C.Gaussage and Online Parameter Based Video Tracking Mode Transition from KF to PF for Optimal Performance［C］∥Control and Decision Conference 24th Chinese Digital Object Identifier.Taiyuan，China:［s.n.］，2012:1331-1336.

［10］齐蕴光，安钢，龚正波.基于梯度投影法的电子稳像算法［J］.计算机工程，2012，38(6):230-232，235.QI Yunguang，AN Gang，GONG Zhengbo.Electronic Image Stabilization Algorithm Based on Gradient Projection Method［J］.Computer Engineering，2012，38(6):230-232，235.

［11］解梅，俞成浦.基于梯度投影和形态学的指纹图像分割方法［P］.中国:200810045690，2008-12-24.XIE Mei，YU Chengpu.The Fingerprint Image Segmentation Method Based on Gradient Projection and Morphology ［P］.China:200810045690，2008-12-24.

［12］HUANG SHIH-CHIA.An Advanced Motion Detection Algorithm with Video Quality Analysis for Video Surveillance Systems［J］.Circuits and Systems for Video Technology，2011，21(1):1-14.