毕业论文设计智能视频监控中目标跟踪算法研究及应用

毕业论文设计智能视频监控中目标跟踪算法研究及应用毕业论文设计智能视频监控中目标跟踪算法研究及应用/毕业论文设计智能视频监控中目标跟踪算法研究及应用智能视频监控中目标跟踪算法研究与应用学生：指导教师：淮南师范学院物理与电子信息系摘要：视频监控中目标跟踪算法的研究与应用是实现视频监控系统的关键技术之一。实际视频监控系统中的场景往往是错综复杂、变化无常的，实现具有鲁棒性、准确性和实时性的运动目标检测和跟踪是当前智能视频监控技术努力的方向。本文研究了静态场景下运动目标跟踪的相关算法，给出了运动目标跟踪的实现方案，由于LucasKanade光流跟踪算法对目标仅仅跟踪其质心，存在跟踪目标容易丢失且鲁棒性不高的缺点；最小绝对差算法企图搜索目标模板、计算量大、实时性差；针对这两种算法在目标跟踪方面的不足，对其进行了相应的改进和完善。通过LucasKanade光流跟踪算法预测目标质心位置、并设定目标搜索区域减小最小绝对差算法计算量；将模板匹配定位之后更正的目标质心做为下一帧LucasKanade光流跟踪算法跟踪的特征点，可以减小单一光流法预测目标质心带来的误差，实现可靠的跟踪。关键词：运动目标跟踪；LucasKanade光流法；模板匹配Abstract：VideotargettrackingalgorithmresearchandApplicationisoneofthekeytechniqueswhichimplementsintelligentvideosurveillancesystem(IVSS).Therealvideosurveillancesystemappliedenvironmentisusuallycomplex,fullofvariety.Therealizationofmovingobjectdetectionandtrackingwithveracity,real-timeperformanceandrobustnessisthedirectionforcurrentIVSSstudy.Thispaperstudiedunderstaticscenetrackingalgorithmsmovementaregiven,andtheimplementationschemeofmovingobjecttrackingKanadelightflow,becauseLucastotargettrackingalgorithmonlytrackingitsexistingtrackthetargetcentroid,easytoloseandrobustnessisnothighweaknesses;Minimumabsolutedifferencealgorithmmapsearchtargettemplate,largeamountofcalculation,real-timepoor;Inviewofthesetwoalgorithmintargettrackingdeficiency,analysesthecorrespondingimprovementandperfection.ByLucasKanadelightflowforecasttargetcentroidpositiontrackingalgorithm,andsetatargetofreducingthesearchareacomputationminimumabsolutedifferencealgorithm;WillthetemplatematchingafterthetargetcentroidpositioncorrectionasthenextframeLucasKanadelightstreamingtrackingalgorithmtrackingfeaturepointscanreduceasinglelightflowmethodforforecastingtheerrorscausedbytargetcentroid,achievereliabletracking.Keywords：Sportstargettracking;LucasKanadelightflowmethod;Backgroundmodel1．引言1.1研究背景和意义随着计算机技术、通信技术、图像处理技术的不断发展，目标检测与跟踪技术在移动机器人、战车与坦克、飞机、导弹、舰船等军事领域和航空航天、科学探测、天文观测以与视频监控等民用领域具有越来越广泛的应用，也称为自动控制、信号与信息处理、计算机视觉和模式事变等领域的研究热点。视频监控系统是公共安全技术防范系统的重要组成部分，它被广泛应用于国防、国家安全、治安等多个方面，主要涉与军工、公安、交通、金融、电力、电信、供水、供气等重要部门。由于视频图像监控具有很强的直观性、实时性和可逆性，使得它在解决经营纠纷、预防和制止犯罪、处理治安和刑事案件、为公安侦察破案提供线索等方面有着其他防范设施难以发挥的作用。目前，基于视频序列的目标检测与跟踪技术在国内外各个领域和方面均得到了十分广泛的应用。在军事方面，军用卫星、战区导弹防御、侦察机、导弹制导、火控系统与小型自寻的导引头等军事武器均广泛应用了图像目标的识别与跟踪技术，大大提高武器系统的运动攻击性能与作战指标。美国空军“幼畜”导弹是最著名的一种电视制导导弹，由于目标的识别与跟踪技术的应用，该导弹可做到自动发现并锁定目标，并对目标实施摧毁，大大提高了作战效能；武装直升机和现代坦克战车队也都借助到高性能光电稳定瞄准具等先进光电设备，如高清晰度前视红外传感器、高分辨率和高倍率的CCD传感器等光电设备，结合目标的识别与跟踪技术大大提高了其再战场中的生存能力、提高有效打击力、增加全天候作战效能。在民用方面，图像目标的识别与跟踪在科学探测、航空和航天对地观察、摄影和地形测绘上同样发挥着十分重要的作用。随着科学的发展和生活水平的提高，一些高档的手持、肩扛拍照和摄像系统也广泛地应用了人脸识别与跟踪技术，提高了系统的成像质量。运动目标的识别与跟踪在智能交通、身份识别等领域也得到了十分广泛的应用，创造了很好的社会价值。因此，目前世界各国政府和学者，密切关注新一代的监控技术——智能视频监控技术。它同以往的监控技术有着本质的区别，其主要特征是采用计算机视觉的方法，在几乎不需要人为干预的情况下，赋予计算机类似于人的理解动态场景的视觉能力，通过对视频序列中运动物体的检测与跟踪以与对运动行为与语义概念之间关系的表达与分析，形成对场景中运动物体行为与其相互关系的高层次语义上的解释，使计算机知道什么时候，在什么场景中，是什么人在做什么，并用自然语言来描述所发生的一切。更形象地说，智能视频监控系统[1]能够看，看被监控场景中目标物体的行为；能够想，理解目标物体的行为以为着什么；能够说，把想的结果用自然语言的形式表达出来。因此只能视频监控系统具有看、思考和表达的能力。目前，智能视频监控系统取代了监控任务中人的大部分工作，是新一代的具有高度智能的监控技术[2]。1.2国内外研究现状国外对基于视频的目标检测与跟踪的理论研究与应用研究起步较早，尤其在美国、英国等国家已经开展了大量相关项目的研究，并取得了一定的成果。现举例如下：1997年美国国防高级研究项目署(DefenseAdvancedResearchProjectsAgency)设立了以卡内基梅隆大学(CarnegieMellonUniversity)为首、麻省理工学院(MassachusettsInstituteofTechnology)等高校参与的视觉监控重大项目VSAM(VisualSurveillanceandMonitoring)[3]，VSAM的目标是为未来城市和战场监控应用开发的一种自动视频理解技术，用于实现未来战争中人力监控费用昂贵、非常危险或者人力无法实现等场合下的监控。美国的麻省理工学院(MassachusettsInstituteofTechnology)在智能视觉监控方面也进行了深入的研究，其开发的监控系统[4]己成功实现了对行人和车辆的检测与跟踪。英国的雷丁大学(UniversityofReading)己开展了对车辆和行人的跟踪与其交互作用识别的相关研究[5,6]。美国的马里兰大学(UniversityofMaryland)开发了W4(What，Where，When，Who)实时监控系统[7,8,9]，该系统不仅能够定位人和分割出人的身体部分，而且通过建立外观模型来实现多人的跟踪，可以检测和跟踪室外环境中的人，同时可以检测人是否携带物体等简单行为，并对他们之间的简单交互进行监控。IBM与Microsoft等公司也正逐步将基于视觉的手势识别接口应用于商业领域中[6]；在我国，这方面的研究起步较晚。目前，在国内的相关研究机构中，中科院自动化研究所下属的模式识别国家重点实验室成立的视觉监控研究小组处于该领域的领先地位。该实验室在交通场景的视觉监控、人的运动视觉监控和行为模式识别等方面作了深入的研究，并取得了一定的成果[10,11]。模式识别实验室己经开始与英国雷丁大学就视觉监控项目开展了合作研究，并得到了英国皇家协会的支持；与法国波尔多第三大学EGID研究所在交通视觉监控等方面也展开了一系列的合作。除此之外，国内还有一些高校，如上海交通大学航空航天信息与控制研究所，华中科技大学图像识别与人工智能研究所,西安电子科技大学电子工程学院模式识别与智能控制研究所，桂林电子科技大学图像所等研究机构，都对该领域进行了相关的研究。1.3运动目标与运动目标跟踪的概述运动目标是日常生活中常见的，如活动的动物、行驶的运载工具等。在现实生活中，尽管人类的视觉既能看见运动的物体又能看见静止的物体，但是在许多场合，比如气象分析中的云图、安全监视中的人或动物、交通流量的控制等，大量有意义的视觉信息都包含在这些运动之中，人们往往只对运动的物体或目标感兴趣。因此，研究运动目标的检测问题，有着很大的现实意义和应用价值。目标跟踪一直是计算机视觉领域的一个经典问题，其基本任务可简述为在视频序列中对感兴趣的目标或对象的位置、速度等运动特征进行有效的确定或估计。目前，目标跟踪技术已经被广泛应用于众多生活和科研领域中。例如在视频编码、智能交通、视频监控等应用中，目标跟踪技术都起着非常重要的作用。对于目标跟踪算法，目前没有较为明确的分类方法。目前，几种性能较好、较受关注的跟踪算法如下：1）粒子滤波（ParticleFilter）即蒙特卡罗（SequentialMonteCarlo）滤波在计算机视觉领域中的应用研究，它正在受到国内外的广泛关注[12]。它的基本思想是用随机样本来描述概率分布，这些样本称为粒子，在测量的基础上通过调节各粒子权值的大小和样本的位置来近似实际概率分布，以样本的均值作为系统的估计值。这种方法可以用于任意非线性、非高斯随机系统的状态估计，克服了卡尔曼滤波的缺点。然而由于该算法的复杂性，降低了目标跟踪的实时性。诸如粒子退化、实时性差等问题需要进一步解决[13,14]。2)卡尔曼滤波[15,16]在运动估计和预测中的运用较为常见。可将已知的目标运动规律作为跟踪算法建模的前提条件，对目标整体运动可用仿射模型来描述。如果已知目标的运动轨迹是光滑的，或者目标的运动速度或加速度是恒定的，而且假设图像噪声是高斯噪声，卡尔曼滤波器便可以用来预测和估计目标下一帧的位置，完成对目标的跟踪。如果目标的运动不可视为线性的，可以使用扩展卡尔曼滤波器跟踪目标。3）基于边缘轮廓的跟踪。边缘是指周围像素有灰度阶跃变化的像素集合或强度值突然变化的像素点集合，边缘对运动很敏感，对灰度的变化不敏感。Blake等用自适应边缘模型，而Curwen等用Snake算法[17]，都实现了对非刚性物体运动轮廓的跟踪。4)光流（opticalflow）的概念是Gibson于1950年首先提出的。所谓光流是指图像中模式运动的速度。1981年，Horn等人在相邻图象间的时间间隔很小，并且图象灰度变化也很小的前提下，推导出灰度图象光流场计算的基本等式，这是经典光流方法[18,19]。光流法用于目标跟踪常用的算法有：检测和跟踪特征点[20]、跟踪好的特征点[21]、金字塔图像的LucasKanade特征点跟踪算法[22]。在这三种光流跟踪方法中，跟踪性能最优的是金字塔图像的LucasKanade特征点跟踪算法，本文就是采用此方法进行目标跟踪，并对其进行改进。5）基于模板的目标建模方法直接采用目标图像的像素集合对目标进行描述，已被广泛用于基于模板匹配的跟踪算法中[23-24]。该算法实质是在图像中找到一块区域，使这块区域与模板之间对应像素灰度差的绝对值之和为最小。算法需在整幅图像上搜索出与原模板最匹配的区域，因此耗时较大，本文将其和光流法结合起来用于目标跟踪，提高算法实时性和鲁棒性。6）MeanShift算法是一种概率密度梯度函数的估计方法。1995年YizongCheng发表的一篇重要文献[25]将其引入计算机视觉领域后，渐渐引起人们的兴趣。国内最近几年才展开该算法研究，它在跟踪领域中的应用是目前研究的热点。该算法采用核函数直方图建模，对边缘遮挡、目标旋转、变化以与背景运动都不敏感；运算速度快，实时性好；但是，该算法也存在一定的缺点。比如：运动目标的颜色相同或者背景中存在大片的与目标颜色相同的区域，如果目标产生重叠，则在目标重新分开后将不能确定原来目标的编号。1.4运动目标跟踪研究的难点目前，运动目标跟踪所遇到的主要问题是：1)应用面单一，缺乏适用性很广的算法。2)运动目标阴影和运动目标混淆，消除阴影。3)在跟踪过程中出现运动目标消失或受到遮挡。4)基于检测和跟踪算法的复杂性如何保证处理的实时性。5)目标做复杂运动或形变时的跟踪和分类问题。为了有效实现视频序列中目标跟踪任务，本文重点研究了光流法和模板匹配跟踪方法，金字塔图像的LucasKanade光流法跟踪目标容易丢失，传统的模板匹配跟踪方法由于对图像利用率高，其跟踪比较准确，但计算量大、实时性差；针对这两种算法在目标跟踪方面的不足，对其进行了相应的改进和完善。通过LucasKanade光流跟踪算法预测目标质心位置、并设定目标搜索区域减小最小绝对差算法计算量；将模板匹配定位之后更正的目标质心做为下一帧LucasKanade光流跟踪算法跟踪的特征点，可以减小单一光流法预测目标质心带来的误差，实现可靠的跟踪。2．常用运动目标跟踪方法运动目标检测可以从图象中得到运动目标的位置、形状等信息，但这些信息是孤立的，并没有提供图象序列之间的联系，本章将对检测出的目标进行运动跟踪，对这些数据进一步处理，获得跟踪目标的标号和运动轨迹。目标跟踪的作用非常重要，因为它是衔接运动目标检测和目标行为分析与理解的一个重要环节。在实际应用中，目标跟踪不仅可以提供目标的运动轨迹、运动参数和准确的位置，也为进行场景中运动目标的运动分析和场景分析提供了可靠的数据来源，同时运动目标的跟踪信息也反过来为运动目标的正确检测以与运动目标的识别提供了帮助，从而更有利于运动目标的跟踪。2.1常用运动目标跟踪算法2.1.1金字塔图像的LucasKanade特征点跟踪算法光流的概念是Gibson于1950年首先提出的。所谓光流是指图像中模式运动的速度。1981年，Horn等人在相邻图象间的时间间隔很小，并且图象灰度变化也很小的前提下，推导出灰度图象光流场计算的基木等式，这是经典光流方法[18,19]。光流法用于目标跟踪常用的算法有：检测和跟踪特征点[20]、跟踪好的特征点[21]、金字塔图像的LucasKanade特征点跟踪算法[22]。在这三种光流跟踪方法中，跟踪性能最优的是金字塔图像的LucasKanade特征点跟踪算法，由于该算法仅跟踪少量的特征点、迭代法收敛速度也很快而且算法的计算量不大，已被广泛的应用于运动车辆跟踪和人脸特征点跟踪[26,27]；下面介绍之。1、问题提出我们用I和J来代表两个灰度图像。那么I(x)=I(x,y)和J(x)=J(x,y)代表了这两个灰度图像在点的灰度值，x和y是图像的点X坐标。这里，我们称图像I为第一幅图像，称J为第二幅图像。从实际的图像来说，I和J是两个离散的函数，并且左上角的像素点坐标是。用和表示图像的宽度和高度。那么右下端的图像的坐标是。考虑第一幅图像上的一点，跟踪的目的就是在第二幅图像上找到与之相对应的一点,是在点X处图像的速度，即点X处图像的光流。令和表示两个整数，我们假定图像速度d是使得下面的残差函数最小的函数：（2-1）根据上面的定义，相似度的函数被在的区域内定义。这个区域也称之为积分窗口。典型的、是2、3、4、5、6、7个像素。2、跟踪算法的描述基于特征点的跟踪的两个关键问题是准确度和鲁棒性。准确度是从直觉上来说，为了不抹去图像中的细节，需要小的积分窗口。鲁棒性因素需要考虑光照变化，图像运动时对尺寸变化的敏感性。特别的，为了了解大矢量运动的问题需要一个大的积分窗口。实际上，仅仅考虑等式（2-1），理想的情况是。这样我们就必须兼顾准确度和鲁棒性来选择积分窗口。为了更好的解决这个问题，采用了基于金字塔图像的光流跟踪方法。这个方法对局部跟踪的准确性提出了一个很好的解决方案。(1)、金字塔图像表示描述一个的图像I，令表示第0层图像（原始图像），那么金字塔图像表示是以一种回归形式而建立的：根据计算，计算，计算，以此类推；令L=1,2,…表示一系列金字塔图像层次，图像的大小为：，图像通过对图像隔行隔列采样得到。采用金字塔图像表示方法的主要目的是处理大矢量的运动问题(处理大于积分窗的目标运动的问题)。因此应当用图像中最大期望的光流来恰当的确定金字塔图像的高度。在大多数的情况下，超过4的金字塔图像层次没有太大的意义。(2)、基于金字塔的图像跟踪回到前面说的跟踪问题：对于图像I中的一个给定的点u，找到它在图像J中对应的位置v=u+d，或者找到目标运动的矢量d。对于，定义是点u在金字塔图像中的映射。根据前面关于金字塔图像定义的描述，则向量的计算公式如下：（2-2）等式（2-2）中的除法是对两个坐标分别进行的。基于金字塔图像LucasKanade光流法跟踪的处理过程如下：首先在最深的一个层次Lm计算光流，然后，这个计算结果转递到Lm-1层；根据最初的假定，在Lm-1层计算出新的光流并把它转到Lm-2层，这样一直操作直到回到第0层（原始图像）。现在让我们用数学公式详细的介绍一下从第L+1层到第L层的递归过程。假定在第L层有对被跟踪目标的位置有个大致估计，而从最高层Lm到第L+1层传递过来的运动矢量是。这样，为了计算出在第L层的光流，需要找到一个使得下面的残差函数：（2-3）达到最小的偏移向量：（2-4）注意到，在第L层的积分窗口的大小是保持恒定的尺寸的，即：在第二幅图像中,用这里得到的最初估计作预平移。这样，求得的残余流向量就足够小，因此能够通过标准的光流法来求出这个运动矢量。计算残余光流的细节将在下一节介绍。现在，我们假定这个向量已经计算出来(为了说明算法的完整性)。然后，这个计算过程的结果就传送到第L-1层，传递的向量是：（2-5）下一层次的残余光流，也可以通过同样的步骤计算出来。这个通过光流法计算出来的这个向量，使得下列残差函数达到最小值。将此计算过程一直继续，直到算到最底层(L=0)。此算法的初始化过程是通过设定最高层()的初始运动估计为零开始的：（2-6）最终的光流d通过对最底层(原始图像)作光流法计算得到偏移量，这个偏移量的大小是：（2-7）注意到这个偏移量也可以用下列的式子来表示：（2-8）使用金字塔图像计算光流的一个明显的好处是，对于一个有着较大的像素偏移的矢量d，可以通过计算几个比较小的残余光流来得到。注意到每个层次基本的光流法可以搜索得到的运动矢量达到，这样运用金字塔图像的方法最多能够处理的运动矢量范围达到。例如，如果金字塔图像的层次有3层的话()，这意味着像素的偏移量可以达到15层。这就是我们能够使用较小的积分窗口来计算较大的像素运动矢量的原因。2.2迭代的光流法计算过程现在介绍一下光流法计算的详细过程。在金字塔图像的每个层次L，找到偏移向量实际上就是找到使得残差函数最小的d。因为这个计算步骤对各个层次都是一样的，现在我们丢掉上标L，且定义新图像A、B如下所示：（2-9）（2-10）注意到A(x,y)和B(x,y)的定义域稍微有些差异。实际上，A(x,y)是在窗口大小为的范围内定义的，而不是。在后面运用中心差分算子计算A(x,y)的导数时，这个差异将变得更加明显。为了说明的清晰起见，我们改变运动向量的表示方法，新的表示方式为,而图像位置新的表示方式为。依据新的表达方式，我们的目的是找到一个偏移向量，它使得下面的残差函数取得最小值：（2-11）对这个式子可以采用标准的光流法处理。为了优化这个问题，对的一阶导数为零：（2-12）通过将这个式子展开以后，我们得到：（2-13）我们把用它在点的一阶泰勒展开式来代替(因为采用了金字塔图像的方法，每层的运动偏移量比较小，因而采用一阶泰勒展开是一个很好的解决方案)：（2-14）注意到A(x,y)-B(x,y)可以看作是在点的一个导数，所以：（2-15）矩阵仅仅是一个梯度向量，我们在这里对表示方法作一个小小的改变：（2-16）注意到图像的梯度和可以不必考虑第二幅图像B，而只需根据图像在点P的邻域的信息求得(在迭代法求光流的过程中，这一点的重要性是很明显的)。如果我们使用了差分近似微分算子，这两幅图像的导数的形式如下所示：（2-17）实际上，根据上面的记号方式，我们得到：（2-18）（2-19）其中：（2-20）（2-21）这样，计算公式可以简写为：（2-22）这样，简化后得到所求的光流向量为：（2-23）2.3金字塔图像的LucasKanade特征点跟踪算法总结图2.1为Lucas-Kanade光流跟踪流程图；下列各式子的详细定义可以在前面几节中找到。Lucas-Kanade光流跟踪的目标是：已知图像I中的点u在图像J中找到与之相对应的点v。图2.1Lucas-Kanade光流跟踪流程图2.4特征点选取在上面，我们已经总结了整个跟踪流程，即通过光流法找到图像I中的点u在图像J中的对应点v；然而，我们还没有给出如何求取图像I中的特征点u。实际上，跟踪的关键步骤是如何求取光流向量（详见上述的跟踪流程），在这一步中，G矩阵必须是可逆的，或换句话说，G的最小特征值必须够大（大于某一阈值）。这个像素点的特征才容易被跟踪。因此，特征点的选取过程如下所示：在图像I中的每个像素点计算矩阵G的最小特征值；在整个图像I中，求出的最大值；保留图像中特征值大于最大特征值的10%或5%的像素点；从这些像素点中保留局部特征值最大的像素点（如果一个像素点的特征值大于3×3领域内的其他像素点的特征值，则这个像素点被保留）；保留下来的这些像素子集中的任何两个像素点之间的距离必须大于给定的阈值（比如5或10个像素）。经过上述处理过程，被保留下来的像素点是比较容易跟踪的特征点。2.5实验结果与分析实验过程分三个模块：视频读入、目标检测模块和光流跟踪模块；首先，读入视频图像；然后，采用目标检测模块来进行目标检测，通过目标检测得到目标的质心位置；最后，将目标质心当作光流跟踪的特征点，采用Lucas-Kanade光流跟踪算法，进行目标跟踪。在VC++6.0环境下对采集的视频做了Lucas-Kanade光流跟踪实验，该视频图像大小为320×240、帧率为15帧/秒、RGB24真彩色图像。实验中采用的参数是：积分窗口为11×11（即公式（2-1）中的、均采用5个像素），金字塔层数L为3，迭代次数K为20次。第11帧第43帧第68帧第78帧第93帧第107帧图2.2LucasKanade光流法跟踪结果图2.2为LucasKanade光流法跟踪结果。图中绿色的“1”和蓝色的“2”为目标的ID，同一个目标标注了同一ID，红色的方框为跟踪框，红色“+”为光流预测的目标质心。从图中可以看出：目标1和目标2在第68帧之前，跟踪效果比较理想；目标1的跟踪框在第78帧之后开始偏离目标，到达第93帧时，由于目标模糊不清、并且与背景较为相似，所以跟踪框偏离加大，并停止跟踪；但由于目标2比较清晰，故始终能稳定跟踪。通过大量实验发现，LucasKanade光流跟踪要求图像质量比较高，图像纹理丰富，对质量较差的图像跟踪效果并不理想，主要表现在以下几点：1)不容易选定一个固定的邻域大小，使其适合不同的视频段和不同的特征点；2)容易出现特征点跟踪不稳定的情况；3)某些点处的矩阵G病态或者不可逆，此时方程的解不可靠从而发生跟踪漂移现象；4)光流跟踪依靠的是特征点的局部信息，每个点都是独立跟踪的结果，其跟踪结果并不稳定。通过计算稀疏特征点处的光流即可跟踪目标，光流法用于目标跟踪已基本解决了计算速度慢的缺点，而且对图像质量比较高、图像纹理丰富的慢速运动目标跟踪的效果还是不错。但仍然存在跟踪目标容易丢失且鲁棒性不高的缺点。3．模板相关匹配算法3.1模板相关匹配算法基本原理模板相关匹配算法的基本原理如图3.1所示。设目标模板T为一个的参考图像，搜索图S为一个图像。T在S上平移，模板覆盖的部分叫做子图，为子图左上角点在S中的坐标，叫参考点。比较T和的内容，若两者一致，或极其相似，则点为所寻找的最佳匹配点。图3.1模板相关匹配算法原理图二维最小绝对差累加和算法(MinimumAbsoluteDifference,以下简称：MAD)[26][27]是一种在工程系统中应用较为普遍的相关跟踪算法，它与上述归一化互相关的模板相关跟踪算法相似，该相关匹配算法采用二维最小绝对差累加和作为子图和目标模板相似度的度量。即：(3-1)在图像匹配跟踪过程中，参考模板图像在当前帧搜索区内滑动，与实时子区图像作相关运算，寻找最佳匹配点，当使D(i,j)取得最小值时的(i,j)即为所求的最佳匹配点。由于MAD算法直接采用图像各像素点的灰度值作绝对差累加和运算，虽然计算量比归一化互相关运算要少，但需要做相关计算的点数是不变化的，即为(N-M+1)×(N-M+1)；而且MAD算法对图像灰度变化较敏感，在图像低对比度区域或对比度变化情况下，目标跟踪性能将下降，甚至丢失目标。所以在使用MAD算法之前，一般都需要对搜索区与目标模板图像进行灰度归一化预处理。3.2模板匹配的搜索方法模板匹配的搜索方法众多，常用的有二维对数搜索法(TwoDimensionalLogarithmic,简称TDL)、三步搜索法(ThreeStepSearch,简称TSS)和菱形搜索法(DiamondSearch，简称DS)。其中，性能最优的是菱形搜索法，下面简单介绍之。DS算法最早由ShanZhu和Kai-KuangMa两人提出[28]，后经过多次改进，已成为目前快速块匹配算法中性能最优异的算法之一，该算法已被MPEG-4VM标准所接受。搜索模板的形状和大小小但影响整个算法的运行速度，而目也影响也搜索的准确性。搜索窗口太小，就容易陷入局部最优，而搜索窗口太大，又容易产生错误的搜索路径。另外，统计数据表明，视频图像中进行运动估值时，最优点通常在零矢量周围(以搜索窗口中心为圆心，两像素为半径的圆内，如图3.2(a)所示)，即具有中心倾向。基于这两点事实，DS算法采用了两种搜索模板，分别是有9个检测点的大模板LDSP(LargeDiamondSearchPattern)和有5个检测点的小模板SDSP(SmallDiamondSearchPattern)，如图3.2(b)和3.2(c)所示。搜索时先用大模板计算，当最小块误差MBD(MinimumBlockDistortion)点(即MAD值最小的点)出现在中心点处时，将大模板LDSP换为SDSP，再进行匹配计算，这时5个点中的MBD点即为最优匹配点。(a)最优点分布规律(b)大模板LDSP(c)小模板SDSP图3.2DS的搜索模板DS具体算法描述如下：①用LDSP在搜索区域中心与周围8个点处进行匹配计算，若MBD点位于中心点处，则转到步骤③，否则，进行步骤②。②中心点移到上一步的MBD点处，继续用LDSP来计算。若MBD点位于中心点处，则转到步骤③，否则，重复步骤②。③以上一次找到的MBD点为中心点，将LDSP换为SDSP，在5个点处计算，找出MBD点，该点所在的位置即对应最佳运动矢量。如图3.2是DS算法搜索过程的一个例子，(-4,-2)是最终搜索到的运动矢量，搜索共进行了5步，MBD点分别对应为(2，0)、（-3，-1）、（-4，-2），使用4次LDSP和1次SDSP，共搜索了24个点。图3.3DS的搜索路径举例DS算法的特点在于它分析了视频图像中运动矢量的基木规律，选用了大小两种形状的搜索模板LDSP和SDSP。先用LDSP搜索，由于步长大，搜索范围广，可以进行粗定位，使搜索过程小会陷于局部最小；当粗定位结束后，可以认为最优点就在LDSP周围8个点所围成的菱形区域内，这时再用SDSP来准确定位，使搜索不至于有大的起伏，所以它的的性能优于其它算法。另外，DS搜索时各步骤之间有很强的相关性，模板移动时只需在几个新的检测点处进行匹配计算，可以进一步提高搜索速度。3.3目标模板的选择与更新3.3.1目标模板的选择使用模板匹配算法进行目标跟踪时，目标模板的大小选择也是一个很重要的问题。如果模板过小，所包含的信息少，得出的最佳匹配位置容易不可靠；反之，如果模板过大，模板中将包含有更多的背景信息，背景信息的变化将给相关运算带来误差，而这些误差会随着相关处理逐帧累积，如果累积到足够帧数，模板会完全偏离目标。而且，模板的增大会带来模板相关运算量的急剧增大。本文目标模板选取的原则为：使用目标的最小外接矩形框来做为目标模板。3.3.2模板的更新随着被跟踪目标的运动，目标将出现大小、形状、姿态等变化，所以必须在跟踪过程中不断的更新目标模板。而且由于实际环境中的光照、天气变化等因素的影响，相关跟踪得不到绝对最佳的匹配位置，存在匹配误差。这些误差随着模板的更新而逐渐积累并向后续图像传递，因此模板更新和修正是保证长时间稳定跟踪的关键。考虑到系统的实时性问题，本文没有采用基于跟踪置信度的自适应模板更新算法来更新和修正模板[27]，而是采用了较为简单的模板更新方法，即每隔1S提取一次目标模板，并对目标模板进行更新。3.4实验结果与分析模板匹配法跟踪的过程分为视频读入、运动目标检测模块、相关匹配运算和模板更新四个部分；首先，通过目标检测模块，可以提取到运动目标即目标模板；然后，采用基于归一化互相关的模板相关匹配算法和基于最小绝对方差累加和的模板匹配法分别对目标模板进行跟踪；最后，在自动跟踪目标的过程中，我们可以根据前面介绍地运动目标检测方法检测出运动目标，然后截取目标图像作为下一帧图像的模板。实验中，采用每隔1S提取一次目标模板，并对目标模板进行更新。下面给出序列图像中的单一运动目标（行人）的跟踪结果与其分析。（a）(b)(c)第120帧第150帧第180帧图3.4目标模板图3.5MAD算法跟踪结果图3.4为目标模板；其中，图（a）、（b）和(c)分别表示第120、150和180帧目标模板。可以看出，提取的目标模板精确、可靠。图3.5为MAD算法的跟踪结果。实验中采用基于最小绝对方差累加和的模板匹配法（MAD）跟踪目标，结果表明MAD算法对图像灰度变化较敏感，在图像低对比度区域或对比度变化情况下，目标跟踪性能将下降，甚至丢失目标，而且出现目标被遮挡或目标的灰度直方图与背景相似时，匹配误差最大，跟踪框完全偏离目标。因此，如何减少匹配算法的运算量和提高目标定位精度是关键。4.改进的目标跟踪算法4.1改进的目标跟踪算法描述图4.1改进的目标跟踪算法框图图4.1为系统框图，这是文章设计的基于单摄像机的运动目标检测与跟踪系统框图。在本节中，重点介绍系统框图中的目标跟踪模块，即改进的目标跟踪算法。在目标跟踪模块中，光流法跟踪采用图2.1Lucas-Kanade光流跟踪流程图，目标模板的更新时间T为1S。故改进的目标跟踪算法简述为：通过目标检测模块和新目标检测模块，可以得到目标个数、目标质心位置、目标大小与目标ID（最先出现的目标为1、其次为2、再次为3，以此类推）。将目标质心做为特征点，利用金字塔图像的LucasKanade特征点跟踪算法对其进行跟踪；经LucasKanade光流法跟踪后，可以得到目标质心的新位置，在新位置的领域内（这个搜索区域比目标模板要大一些），利用基于最小绝对方差累加和的模板匹配法搜索目标模板，并对目标进行定位，将模板匹配法之后得到的目标质心位置做为下一帧光流法跟踪的特征点，以此类推，从而实现目标跟踪。下面以图形的形式加予说明。（a）(b)(c)(d)（e）（a）第k帧光流法跟踪结果（b）第k+1帧光流法跟踪结果（c）第k+1帧光流法和模板匹配法相结合（d）第k+1帧光流法和模板匹配法相结合的跟踪结果（e）目标模板图4.2光流法和模板匹配法相结合示意图图4.2中，蓝色矩形框为跟踪框，黄色虚线矩形框为设定的搜索区域，“人”为目标，图4.2(a)、（b)和(c)中的红色十字架为光流法预测的目标质心，图4.2（d）中的红色十字架为光流法和模板匹配法相结合后更正的目标质心。光流法和模板匹配法所存在的问题与本文改进之处：1、光流法之所以跟踪目标容易丢失且鲁棒性不高缺点，是因为光流法预测的目标质心与实际的目标质心出现偏差，故跟踪框偏离目标（见图4.2（b）），并且将第k+1帧光流法预测的目标质心做为下一帧光流法跟踪的特征点，显然，在第k+n（n大于等于2）帧时，跟踪框偏离目标必定会加大并停止跟踪。文中对光流法的改进是：将模板匹配定位之后更正的目标质心（见图4.2（d）红色十字架）做为下一帧光流法跟踪的特征点，这样可以避免单一光流预测目标质心所带来的误差，从而实现可靠的跟踪。2、基于最小绝对方差累加和的模板匹配法由于全图搜索目标模板对图像利用率高，其计算量大，处理一帧图像耗时约1S，实时性差，不能单独用于目标跟踪。本文对MAD算法的改进是：经光流法跟踪之后得到的目标质心，在这一目标质心邻域（图4.2（c）中黄色虚矩形框，这是搜索区域）内，利用MAD算法搜索目标模板，实现目标跟踪；显然，本文通过减小搜索区域来减少计算量，从而提高实时性和跟踪的精度。3、在目标匹配时，第i个（i为目标的ID）目标搜索的起始点设置为光流法预测的第i个目标的目标质心位置，用公式(4-1-1)表示；第i个（i为目标的ID）目标的搜索区域比第i个目标的大小略大，用公式(4-1-2)表示，其中和为设定的阈值。(4-1)(4-2)通过大量的实验发现，在一帧时间里光流法预测的目标质心位置偏离实际的目标质心位置最大为10个像素（比如在人跑步、高速行驶的车等情况下），通常为0至3个像素，因此，和设置为：、；如果目标的运动预测可靠，则逐渐缩小阈值和，当目标丢失时，则逐渐增大阈值和。综合上述三点，光流法和模板匹配法相结合的跟踪方法,即改进的目标跟踪算法概括为：在第k帧，将目标质心（图4.2（a）中的红色十字架）做为特征点，利用金字塔图像的LucasKanade特征点跟踪算法对其进行跟踪；经LucasKanade光流跟踪后，在第k+1帧，可以得到目标质心的新位置（图4.2（b）、（c）中的红色十字架），在新位置的领域（图4.2（c）中黄色虚线矩形框，这是搜索区域）内，利用MAD算法搜索目标模板（图4.2（e））；搜索结果如图4.2（d）所示，蓝色矩形框为跟踪框，可见跟踪结果准确；红色十字架为光流法和模板匹配法相结合后更正的目标质心，将这一目标质心做为下一帧光流法跟踪的特征点，以此类推，从而实现稳定、可靠的目标跟踪。4.2实验结果与分析在VC++6.0环境下对2.5节的视频做了改进的目标跟踪算法实验。实验中，我们采用的参数是：积分窗口为11×11（即公式4-3-1中的和均采用5个像素），金字塔层数L为3，迭代次数K为20次，目标模板更新时间T为1S，设定的搜索区域为4080（实验中最大的目标模板为：2666）。第10帧第10帧ABCDEF图4.3原图像与目标检测结果图4.4目标模板图4.3为原图像与目标检测结果。二值图像中红色十字架为目标质心。可以看出在摄像机静止情况下，本文设计的目标检测算法可以准确、快速的检测出运动目标，这为后续跟踪提供了准确可靠的目标质心与目标模型，克服了其他系统要手动圈出待跟踪目标的缺陷。图4.4为目标模板。其中，图A、B和C分别表示第10、55和85帧目标1模板，图D、E和F分别表示第10、55和85帧目标2模板。可以看出，提取的目标模板精确、可靠。第11帧第43帧第68帧第78帧第93帧第107帧图4.5改进的目标跟踪算法跟踪结果图4.5为跟踪结果。图中，红色的方框为跟踪框，数字“1”和“2”为目标的标号，红色的“+”为改进的目标跟踪算法更正的目标质心，绿色的曲线为目标1的运动轨迹，蓝色的曲线为目标2的运动轨迹；可以看出，改进的目标跟踪算法能较好的跟踪目标和绘制目标运动轨迹，并且1S至少可以处理15帧图像，基本满足了实时跟踪的要求。单一使用金字塔图像的LucasKanade特征点跟踪算法其跟踪结果如图4.3所示，目标1的跟踪框在第78帧之后开始偏离目标，到达第93帧时，由于目标模糊不清、并且与背景较为相似，所以跟踪框偏离加大，并停止跟踪；而单一使用MAD算法跟踪目标，由于该方法全图搜索目标模板，计算量过大，处理一帧图像耗时约1S，实时性差。这两个实验更好的证明了本文改进的目标跟踪算法合理性与可行性。5.结论金字塔图像的LucasKanade光流跟踪算法通过计算稀疏特征点处的光流即可跟踪目标，因为每一个目标仅仅跟踪其质心，而且对图像质量比较低、图像纹理不丰富的运动目标，存在跟踪目标容易丢失且鲁棒性不高缺点；MAD算法由于全图搜索目标模板，其计算量大，实时性差，不能单独用于目标跟踪；针对上述两种算法存在的问题，文章将金字塔图像的LucasKanade光流法跟踪算法和基于最小绝对方差累加和的模板匹配法结合起来，可以避免上述问题，实验结果表明改进的目标跟踪算法能实现各种复杂场景条件下的目标稳定跟踪、获得目标运动轨迹，且具有良好的实时性和鲁棒性。针对上述两种算法在跟踪中存在的问题，文中将金字塔图像的LucasKanade光流法跟踪算法和模板匹配法结合起来，可以避免这两种算法存在的问题，结果表明，改进的目标跟踪算法能较好地实现目标跟踪、获得目标运动轨迹，且具有良好的实时性和鲁棒性。致谢时光荏苒，转眼间又到了栀子花开的季节，随着毕业日子的日益临近，毕业论文也已收稿。值此之际，要对曾经给予我支持和帮助的所有老师、同学、朋友和家人表示最诚挚的谢意！首先要感谢我的导师王健老师，向他致以最崇高的敬意。王老师严谨的治学态度、敬业务实的奋斗精神、默默无闻的奉献精神都在潜移默化中影响着我。感谢物电系的所有老师，感谢你们在学习和工作中给予我的诸多帮助。你们的指导和关心一直鼓励着我前进。感谢所有和我一起奋斗和努力过的同学，感谢你们在生活