运动目标检测与跟踪的研究与实现

硕 士 学 位 论 文论文题目 运动目标检测与跟踪的研究与实现 作者姓名 郑志洵 指导教师 杨建刚教授 学科(专业) 计算机应用技术 所在学院 计算机学院 提交日期 2006年5月15日 摘 要在道路交通管理中，为了获得车辆的运动数据，早期经常采用的是感应线圈等硬件测量的方法。而如果采用摄像头拍摄的道路视频，再用计算机软件处理的方法，则可以极大的增加方便性和灵活性。本文运动目标检测与跟踪研究如何让计算机从视频图像序列中获得物体运动数据。运动目标检测与跟踪分为背景提取、运动点团提取、运动点团位置提取、运动物体跟踪这几个步骤，本文对每一个步骤的各种算法做了实验分析比较研究，并提出了改进算法。在背景提取步骤提出了改进的基于均值的背景提取算法以及减少图像像素的兴趣区提取算法。在运动点团提取的阴影处理步骤提出了改进的基于RGB空间的阴影处理算法。在运动点团位置提取步骤提出了改进的线段编码算法。在运动物体跟踪步骤提出了基于预测的运动跟踪算法。实验与分析说明本文提出的算法优于原算法。本文还通过实验分析比较了基于灰度图像序列的运动目标检测与跟踪、基于边缘图像序列的运动目标检测与跟踪，它们都没有基于彩色图像序列的运动目标检测与跟踪效果好。最后，本文得到了一整套运动目标检测与跟踪的方法，它们的健壮性和实时性都符合实际运用的要求。关键词：背景提取、阴影处理、运动目标检测、运动跟踪、彩色图像、灰度图像、彩色边缘检测AbstractIn a traffic control system, in order to achieve the data of moving vehicles, hardware is installed to directly measure them in the early days. If we use computer software to calculate the data from traffic video, we can gain more convenience and flexibility. This thesis is focused on the research of the methods of achieving the data of moving vehicles from traffic video by computer.Moving object detection and tracking can be divided into these steps: background extraction, moving blob extraction, moving blobs position achieving and moving object tracking. This thesis shows our experiments and analysis on many algorithms in each of the steps. It also shows the improvement of the algorithms made by us. The experiments and analysis demonstrate that the improved algorithms are better then the original ones.Experiments and analysis also demonstrate that moving object detection and tracking based on color images is better than based on the gray images or edge images.In the end we obtain a whole method of moving object detection and tracking. The robustness and real-time property of the method can reach the acquirement of the real application. Keywords:Background Extraction, Shadow Elimination, Moving Object Detection, Moving Object Tracking, Color Image, Gray Image, Color Edge Detector目 录摘 要IAbstractII目 录III第一章 引言1第二章 运动目标检测和跟踪的流程2第三章 背景提取73.1 彩色图像的背景提取73.1.1 基于均值的彩色图像背景提取83.1.2 改进的基于均值的彩色图像背景提取93.1.3 基于中值滤波的彩色背景图像提取113.1.4 基于共同区域的彩色图像背景提取133.1.5 彩色图像背景提取的实验分析163.2 灰度图像的背景提取243.2.1 彩色图像转换成灰度图像243.2.2 灰度图像的背景提取253.3 边缘图像的背景提取263.3.1 彩色图像的边缘提取273.3.2 边缘图像的背景提取28第四章 运动点团提取和背景更新314.1 彩色图像的运动点团提取314.1.1 基于马氏距离的运动点团提取324.1.2 基于欧氏距离的运动点团提取354.2 阴影处理384.2.1 基于RGB空间的阴影处理394.2.2 改进的基于RGB空间的阴影处理404.2.3 基于HSI空间的阴影处理424.3 灰度图像的运动点团提取444.4 边缘图像的运动点团提取474.5 基于帧间差的运动点团提取及其与背景差法比较494.6 背景更新50第五章 兴趣区提取515.1 兴趣区的提取和实验515.2 道路繁忙度获取53第六章 运动点团的位置提取546.1 数学形态学处理546.2 轮廓追踪566.3 线段编码576.4 改进的线段编码586.5 运动点团层运动跟踪59第七章 运动跟踪627.1 卡尔曼滤波627.2 基于预测的运动跟踪647.3 运动跟踪算法的计算复杂性分析与改进687.4 基于边缘图像的运动跟踪结果697.5 基于预测的运动跟踪算法在不同采样率下的健壮性707.6 运动跟踪的最终结果74第八章 总结与展望75参考文献76致 谢78IV第一章 引言在道路交通控制管理领域，管理部门需要掌握道路上车辆的速度、车辆的数量等等数据以控制红绿灯平衡道路车流量、对超速和闯红灯的车辆进行处罚。早期，人们一般采用感应线圈的方式获得车辆的速度、车辆的数量等数据。这种方法，需要在检测路段埋入感应线圈，这需要对道路施工，会影响交通，严重影响道路寿命，并且感应线圈设备容易被重型车辆压坏，维护起来又要对道路施工，非常麻烦1。随着计算机技术的发展，道路交通数据获取不再需要复杂的线圈设备了。只需在检测路段固定摄像头，摄像头拍摄的道路数字化视频压缩后通过传输线路（如光纤）传输到监控中心，监控中心的计算机采用数字图像处理的方法将道路交通的数据计算出来2。与早期的方法相比，这种方法利用了软件算法通过计算机的强大计算能力得到我们需要的数据，而不是复杂的硬件设备（如感应线圈）对数据直接测量。这极大的增加了方便性和灵活性。如何让计算机从视频图像序列中获得道路交通数据，例如车辆的速度等，近年来很多人对此展开了研究。从视频图像序列中获得运动物体的数据的方法除了能运用在道路交通外，也能运用于各种监控领域，例如小区防盗、银行监控等等，用以检测和跟踪进入场景的人或物体，应用范围非常广泛。本文就是研究如何让计算机从视频图像序列中获得物体运动数据视频图像序列中运动物体的检测和跟踪。研究以道路交通作为实验场景，单摄像头且摄像头固定的情况。输入是RGB色彩空间的视频图像序列，目标是实现对视频图像序列中运动物体的跟踪，获得其在图像坐标下的速度。而多摄像头的情况和摄像头跟随物体运动的情况，比单摄像头且摄像头固定的情况复杂，例如多摄像头的多个二维图像序列中如何重构三维场景等。单摄像头且摄像头固定的情况是最基本的情况，因此本文集中精力研究单摄像头且摄像头固定情况下的运动目标检测和跟踪。第二章 运动目标检测和跟踪的流程在道路视频图像序列中获得车辆的速度，可以使用简单的方法，就是在图像中的道路位置设置虚拟检测线，模拟感应线圈，根据虚拟检测线上的像素颜色的变化得到经过虚拟检测线的车辆的速度，同时也可以对经过虚拟检测线的车辆计数3。这种方法有很大的局限性。首先，它需要人工标定虚拟检测线，摄像头一旦换位置，就需要重新设定一次虚拟检测线，很不方便；其次，它只能检测通过虚拟检测线的车辆，而对图像其他区域的车辆一无所知，图像的大量信息丢失掉了。因此，本文不采取虚拟检测线的方法，而以运动物体（车辆）为目标，跟踪每个运动物体在视频图像序列中的位置，进而得到每个物体的运动速度和运动物体总数。运动目标检测与跟踪的流程有三个层次，如图一4。每个层次再细分，可以得到图二的几个步骤。图像像素层运动点团层运动物体层图一 运动目标检测与跟踪的层次 视频图像序列 边缘检测 背景提取 运动点团提取 运动点团位置提取 数学形态学处理 物体运动跟踪 兴趣区获取 灰度转换 道路繁忙度 车型车牌识别 道路事件检测 摄像头标定物体真实速度获取 背景更新 图二 运动目标检测和跟踪的步骤系统的输入是彩色视频图像序列。检测运动物体需要无运动物体的背景图像，而视频图像序列中的每帧图像一般都有运动物体，因此需要提取背景。背景图像提取出来后，将每一帧图像与背景图像作差，然后二值化，得到前景像素构成的运动点团图像，这就是背景差法。背景提取有很多种算法，第三章将详述与比较各种背景提取算法，并提出一种改进的算法，实验证明改进的算法有更好的效果。除了直接将视频图像序列做处理外，还可以先将视频图像序列转换成灰度图像序列，然后在灰度图像序列上做运动目标检测和跟踪；或者，因为前景、背景分离的最重要的信息是边缘信息，可先将视频图像序列转换成边缘图像序列，然后在边缘图像序列上做运动目标检测和跟踪5。第三章也讲述了彩色图像转变成灰度图像的方法以及提取彩色图像的边缘图像的方法。第四章讲述并比较了每一帧图像与背景图像作差的不同方法。由于阴影的存在，背景差法会把阴影作为运动物体的一部分，而阴影会把不同的运动物体连成一片，影响之后的处理，因此需要对阴影做特别处理。第四章讲述和比较了阴影处理的不同方法，并提出一种改进的算法，实验分析其优于其他算法。第四章也指出了基于灰度图像的运动点团提取无法解决阴影的问题，因此基于灰度图像的运动目标检测与跟踪方法没有基于彩色图像的方法好。提取运动前景像素除了上面所述背景差法外，还可以采用相邻两帧图像作差的帧间差法6，第四章接着讲述帧间差法，并将其与背景差法比较。图像会随时间而变化，得到前景和背景像素后，就可以对背景图像做更新，第四章最后讲述背景更新的策略。并不是图像的每一个像素都会出现运动物体，关注区是图像中可能会出现运动物体的部分。在背景提取的时候可以同时获取关注区，之后的处理就集中在关注区中，这是减少图像像素数，减少处理时间的好方法。第五章讲述了关注区的提取方法和利用关注区数据计算道路繁忙度的方法。前面讲述的处理方法都是基于图像像素的，属于图一中的图像像素层，这一层处理的结果是运动点团二值图像，1代表运动前景像素，0代表背景像素。接下来到了运动点团层处理。第六章讲述运动点团层的处理。首先是对运动点团二值图像做数学形态学处理，去除微小的噪声物体。然后提取运动点团的位置和大小。提取运动点团的位置和大小有多种算法，第六章比较了不同的算法，并且提出了改进算法，改进算法更适合运动目标检测和跟踪。第六章还讲述了运动点团层的运动跟踪，并指出了其存在的几个问题，为解决这些问题，必须在运动点团层上增加运动物体层（见图一），从而引出了第七章。另外，在运动跟踪时，我们是先确定一帧图像中所有运动点团的位置，然后和前一帧图像中的运动点团位置关系判断是否为同一运动物体。还有一种运动跟踪的方法7：在当前运动点团邻域搜索匹配下一帧中的运动点团，这种方法不需要提取运动点团的位置和大小，可以称之为基于像素的运动跟踪，然而图像的像素数量是很大的，这种像素点搜索匹配的方法所需的时间远远多于我们的方法，因此我们没有采用这种像素点搜索匹配的方法。第七章讲述运动物体层的运动跟踪。首先，介绍了卡尔曼滤波器，其可以用于运动跟踪4，但其存在一些问题，由卡尔曼滤波器启发，本文提出了一种基于预测的运动跟踪方法，其实质是一种简化的卡尔曼滤波器，很好的解决了卡尔曼滤波器存在的问题。我们做了很多实验验证了此算法的健壮性。这一章还比较了基于边缘图像的运动跟踪与基于原始的彩色图像的运动跟踪的效果，指出了基于边缘图像的运动跟踪差于基于原始彩色图像的运动跟踪的原因。图二中虚线框的步骤，是物体运动跟踪之后可以继续进行的后续步骤，本文把精力集中放在运动目标检测和跟踪的研究上，没有对这些后续步骤做更多研究，在这里做简单说明：运动物体真实速度获取的目的是把运动跟踪得到的物体在图像二维坐标下的速度转换成真实空间三维坐标下的速度，其涉及到摄像头标定；车型车牌识别、道路事件检测是将运动跟踪得到的车辆和道路数据作进一步的处理，以得到诸如车型、车牌、车辆是否闯红灯、车辆是否超速等等，其涉及到很多研究方向，如模式识别等。我们研究运动目标检测和跟踪使用道路交通作为实验场景。我们对多组实验数据进行实验，每组实验数据是一段彩色的视频图像序列，所有实验视频数据的分辨率都归一到像素。下文所说的“实验数据一”是交通管理部门摄制的15秒道路视频，图三是其中的一帧；“实验数据二”是我们用数码相机到天桥上摄制的23秒道路视频，图四是其中的一帧。图三 实验数据一的一帧图像图四 实验数据二的一帧图像第三章 背景提取背景提取是在视频图像序列中提取出背景。背景就是场景中静止不动的景物。因为摄像机不动，因此图像中的每个像素点都有一个对应的背景值，在一段时间内这个值比较固定。背景提取的目标就是根据视频图像序列，找出图像中每一点的背景值。这是下一步运动点团提取的基础。在运动点团提取中，背景提取这一步提取出来的背景图像将作为参考图像，每一帧图像都要与背景图像作差，把背景去除，以得到运动点团前景。因此，这一步提取出的背景图像的好坏将直接影响到之后每一帧的运动点团提取的质量。背景会随着时间的变化而发生变化，例如光照变化导致背景亮度、色度变化；运动物体停止运动成为背景的一部分；又如背景的一部分运动起来成为运动前景等。因此背景需要不断更新，而背景的更新一般需要运动前景的信息，所以背景的更新将在第四章讲述。本章讲述背景初始化的方法，即在没有运动前景的任何信息的情况下提取背景图像，输入是视频图像序列，每帧图像都包括运动物体和静止景物，输出是只含静止景物的背景图像。第3.1节讲述原始彩色图像的背景提取，处理对象是彩色图像序列；第3.2节讲述灰度图像的背景提取先把彩色图像序列转换成灰度图像序列，再对灰度图像序列提取背景；第3.3节讲述边缘图像的背景提取先对彩色图像提取边缘，再对边缘图像序列提取背景，这是考虑到为将运动前景和静止背景分离，边缘信息起到的重要作用。3.1 彩色图像的背景提取原始彩色图像的背景提取，基本思想是，图像中的某个像素按时间抽样，其作为背景像素的时间比作为运动前景的时间长，即其作为背景的概率比作为前景的概率大，而且背景和前景在颜色上和亮度上都有很大不同。这是因为，对于固定场景，运动物体在运动，其转瞬即逝，大多数时间我们看到的都是静止背景，因此图像上某个像素点作为前景的时间相对作为背景的时间短得多；而且，运动物体和静止背景在色彩上有明显区别，人能轻易分辨出前景物体，即使在一张静止图像上。不论何种方法，都是基于这个思想。下面分别讲述不同方法。各个方法的实验对比分析在第3.1.5节。3.1.1 基于均值的彩色图像背景提取这是背景提取的最简单的方法。因为视频中的某个像素对时间采样，背景出现的次数比前景多，因此，将一定的时间段中的视频序列采样，比如2.5帧/秒，对每一个像素，将这一段时间中的所有图像帧取平均，那么这个平均值会接近背景，背景出现的次数比前景越多，则这个平均值就越接近背景。前面已经说过，运动前景是转瞬即逝的。就以这个平均值作为这个像素的背景值。同时，求取平均值还可以在一定程度上抑制噪声。具体算法如下：1)在某时间段采样得到N个图像帧Fi, i=1,2N；2)对每一个像素点(x,y)，背景设图像的总像素数为M，对每一个像素都要遍历N个图像帧，因此这个算法的时间复杂度是O(MN)。实验数据一2.5帧/秒采样10秒得到的背景如图五，实验数据二2.5帧/秒采样10秒得到的背景如图六。从图中我们可以看到前景的痕迹，特别在车辆较密的车道。此方法和其他方法的实验对比分析见第3.1.5节。图五 实验数据一基于均值的背景图像图六 实验数据二基于均值的背景图像3.1.2 改进的基于均值的彩色图像背景提取在第3.1.1节我们只是简单的使用了平均值求取背景。在求平均值之前，如果能去除不大可能是背景的像素，那么求出来的平均值会更加接近背景。然而，这个时候前景还没不知道，用什么方法可以简单有效的得到不大可能是背景的像素呢？根据背景出现的次数比前景多，且前景颜色和背景不同，可以知道，对于某个像素点，其对时间的采样点在彩色RGB空间中会以背景点为中心点聚集在一起，而前景点会离中心点比较远。可以认为，像素颜色矢量的一个分量离中心点的距离超过这个分量的标准差的点不大可能是背景，即使是背景，也叠加了比较大的噪声。标准差计算公式为，c=r,g,b表示矢量的红、绿、蓝三种颜色分量，X0是样本的平均值。因此，可以对基于均值的彩色图像背景提取算法做改进：在求平均值之后求标准差，然后把与均值大于标准差的采样点去除，最后再求余下的点的平均值，把此值作为背景值。改进的算法如下：1)在某时间段采样得到N个图像帧Fi, i=1,2N；2)对每一个像素点(x,y)：a)求中心点；b)求标准差，c=r,g,b；c)求集合中所有元素的平均值，这个值就是所求背景B(x,y)。设图像的总像素数为M，则对每一个像素都要遍历3次N个图像帧求中心点一次，求标准差一次，最后再求均值一次，因此这个算法的时间复杂度是O(3MN)=O(MN)，比原来的单纯求平均值的算法费时。实验数据一2.5帧/秒采样10秒得到的背景如图七；实验数据二2.5帧/秒采样10秒得到的背景如图八。可以看到，此方法得到的背景图像比单纯求平均值的算法好，单纯求平均值的方法得到的背景图像留有不少运动前景的痕迹，而此改进算法得到的背景图像中运动前景痕迹就少多了。此方法和其他方法的实验对比分析见第3.1.5节。图七 实验数据一改进的基于均值的背景图像图八 实验数据二改进的基于均值的背景图像3.1.3 基于中值滤波的彩色背景图像提取中值滤波器能有效的去除图像的噪声。它的一般算法为8：遍历图像的每一个像素，将它和与它相邻的八个像素的灰度排序，取排在中间的像素的灰度值作为输出图像的这个像素的灰度。因为噪声点的灰度与非噪声点差别大，而且图像有空间局部性，也就是说，对于没有被噪声污染的图像，里面的每一个像素和它相邻的像素的灰度差别不大。我们将这个像素和它相邻的像素排序，噪声点将被排到两边，排在中间的像素就是没被噪声污染的像素，把它作为滤波结果。这就是中值滤波器能有效去除图像噪声的原因。上面说的是灰度图像的中值滤波，如何将其扩展到彩色图像呢？彩色图像一般使用RGB空间表示，每个像素点是一三维矢量，各个分量分别代表红、绿、蓝三个颜色的灰度。可以分别将这三种颜色的灰度图做中值滤波，然后合成。然而这种方法将导致滤波后一个像素的三个分量来自不同的像素点，合成后的颜色不可避免的被扭曲。可以采取另外一种方法。考虑到噪声点的颜色与非噪声点差别大，在滤波时的排序中排到两边，可以将彩色图像转换成灰度图像，在转换后的灰度图像中噪声点和非噪声点也会有较大的差别，排序后，取排在中间的像素对应的原始彩色图像的像素矢量作为滤波结果。这样滤波结果的每一个像素都是原始彩色图像中真实存在的像素，避免了同一个像素的三个颜色分量来源于不同的像素导致的颜色扭曲。彩色图像转换成灰度图像的方法详见第3.2.1节。将中值滤波扩展到彩色图像的算法如下：将彩色图像转换成灰度图像，遍历灰度图像的每一个像素，将它和与它相邻的八个像素的灰度排序，取排在中间的像素对应的原始彩色图像的像素矢量作为输出图像的这个像素。中值滤波是对单幅图像在空间采样点上的滤波，不能直接用于背景提取。对于背景提取，我们需要将此算法扩展。视频中的某个像素对时间采样，背景出现的次数比前景多，可以认为前景是“噪声”，这样我们就可以对一个像素在时间上采样得到的样本进行滤波对它们排序，噪声将排在两边，即前景排在两边，排在中部的是背景，取排在中间的像素作为背景结果9。我们处理的是彩色图像序列，因此如前所述，将彩色图像转换成灰度图像，然后在滤波的排序后，选择排在中间的像素对应的原始彩色图像的像素矢量作为滤波结果。具体算法如下：1)在某时间段采样得到N个图像帧Fi, i=1,2N；2)对每一个像素点(x,y):a)将彩色像素矢量Fi(x,y)转换成灰度Gi(x,y)，i=1,2N;b)将集合Gi(x,y)|i=1,2N中的元素排序；c)设排在中间的是Gk(x,y)，则像素矢量Fk(x,y)作为滤波结果。对n个元素排序的时间复杂度是O(nlogn)或者O(n2)，取决于算法，其不是线性的，随着n的增大迅速增大。设图像的像素数是M，对每个像素都要对采样的N个样本进行排序，因此此算法的时间复杂度是O(MNlogN)或者O(MN2)，是比较耗时的算法。实验数据一2.5帧/秒采样10秒得到的背景如图九，实验数据二2.5帧/秒采样10秒得到的背景如图十。此方法和其他方法的实验对比分析见第3.1.5节。图九 实验数据一基于中值滤波的背景图像图十 实验数据一基于中值滤波的背景图像3.1.4 基于共同区域的彩色图像背景提取在一个像素的所有随时间采样的样本中，在求均值之前，如果能去除不大可能是背景的样本，那么求出来的平均值会更加接近背景。关键问题是在不知道前景的情况下，如何决定哪些样本不大可能是背景。第3.1.2节讲了一种基于标准差的方法：认为离中心点距离大于标准差的点不大可能是背景点。有没有不用计算标准差的方法呢？考虑前后相隔一定时间的两图像帧，因为前景在运动，其转瞬即逝，因此同一个像素在有一定时间间隔的两帧中如果差别不大，则它很大可能是背景前景在这段时间中必然运动变化了；如果这个像素在这两图像帧中差别很大，则至少有一帧中的这个像素不是背景。称在有一定时间间隔的两图像帧中差别不大的像素点的集合为共同区域，认为共同区域就是背景区域。在一定的时间段中，采样得到若干有一定时间间隔的图像对，每个图像对找共同区域，然后对共同区域求平均值得到最后的背景图像10。这时还要考虑某些像素不在任何背景区域中的情况如果前景运动变化过于频繁，某像素在任何图像对中都有很大差别，这种情况将出现。这时，这个像素的背景值采用所有采样图像帧求均值的方法得到。像素在图像对中的差别用像素矢量（彩色图像，像素是RGB空间的矢量）的欧氏距离来量度，如果其大于一阈值，则认为差别大，否则认为差别小。这个阈值可以和第四章运动点团前景提取的二值化阈值相同，因为它们的内涵都是前景和背景差别的量度。这个阈值如何确定将在第四章详细讲述。另外，考虑阈值的极端情况，如果这个阈值很小，任何像素在图像对中的差别都大于这个阈值，则找不到任何共同区域，这时每一个像素的背景都是单纯用所有采样图像帧的平均值得到；如果这个阈值很大，任何像素在图像对中的差别都小于这个阈值，则每个图像对中的所有像素都是共同区域，这时每一个像素的背景也是由所有采样图像帧的均值得到。在这两种极端情况下，这个方法都蜕变成第3.1.1节的基于均值的图像背景提取算法，所以基于均值的图像背景提取算法是基于共同区域的图像背景提取算法的特殊情况。详细算法如下：1)在某时间段采样得到N个图像帧Fi, i=1,2N；2)对每一个像素点(x,y): a)集合A=； b)对每一个图像对Fi(x,y)和Fi+N/2(x,y)，i=1,2N/2 如果，则将Fi(x,y)和Fi+N/2(x,y)加入集合A，其中Ta是阈值； c)计算集合A中所有元素的均值作为像素点(x,y)的背景值。设图像的总像素数为M，则对每一个像素都要遍历2次N个图像帧产生集合A的点一次，求平均值一次，因此这个算法的时间复杂度是O(2MN)=O(MN)。实验数据一2.5帧/秒采样10秒得到的背景如图十一；实验数据二2.5帧/秒采样10秒得到的背景如图十二。从图中可以看到，提取出的背景并不平滑，这是因为每个像素计算均值的集合的大小不一样所致。此算法每个像素计算均值的集合（即上述集合A）的大小的变化范围要比改进的基于均值的方法大得多，这导致了其提取出的背景图像在这几种方法中最不平滑。此方法和其他方法的实验对比分析见第3.1.5节。图十一 实验数据一基于共同区域的背景图像图十二 实验数据二基于共同区域的背景图像3.1.5 彩色图像背景提取的实验分析实验采用10秒道路交通视频数据，在上面做均匀采样，例如采样率是1帧/秒（1f/s），就是每秒取1帧，总共在10秒中均匀取10帧；采样率5帧/秒（5f/s），就是每秒取5帧，总共在10秒中均匀取50帧。实验在赛扬1.0G CPU、384兆内存的计算机上进行。表一是前述四种方法在不同采样率下处理完毕实际所需的时间，只包括处理时间，不包括图像序列读取和背景图像输出的时间。不同采样率意味着处理的总图像数不同，采样率与时间（这里10秒）之积就是总图像数。采样率越高，处理的时间越长，见表一。采样率(f/s)122.556.2512.525基于均值(s)0.75 0.93 1.10 1.72 2.16 3.82 7.13 改进的基于均值(s)1.56 2.97 3.50 6.44 8.28 17.72 34.37 基于中值滤波(s)0.57 1.10 1.28 3.28 4.69 14.90 47.85 基于共同区域(s)0.57 0.84 0.97 1.53 1.69 3.25 6.03 表一 不同方法提取背景实际所需处理时间我们可以由表一作出不同算法处理时间与采样率的关系图。基于均值的背景提取方法的时间与采样率关系图见图十三；改进的基于均值的背景提取方法的时间与采样率关系图见图十四；基于中值滤波的背景提取方法的时间与采样率关系图见图十五；基于共同区域的背景提取方法的时间与采样率关系图见图十六。图十三 基于均值的彩色图像背景提取时间与采样率关系图图十四 改进的基于均值的彩色图像背景提取时间与采样率关系图图十五 基于中值滤波的彩色图像背景提取时间与采样率关系图图十六 基于共同区域的彩色图像背景提取时间与采样率关系图从表一和图十三至图十六可以看到，背景提取所需时间随采样率的增加而增加；除了基于中值滤波的背景提取方法外，其他方法处理时间随采样率增加线性增加；而基于中值滤波的背景提取方法，处理时间随采样率增加显著增长；基于均值的背景提取方法和基于共同区域的背景提取方法所需时间差别不大；改进的基于均值的背景提取方法比基于均值和基于共同区域的方法需要时间多。这个和前面每种方法的时间复杂度分析是一致的。为了比较不同算法求得的背景图像的效果，需要获得标准背景作为比较标准。标准背景采用同一场景尽可能多的图像帧使用第3.1.2节的改进的基于均值的背景提取算法取得。这是因为此算法根据标准差先将不大可能是背景的像素去除了，比单纯用平均值准确，同时在一定程度上抑制了噪声，并且由于使用了尽可能多的图像，比只使用10秒的图像有更多信息。实验数据一所有376帧图像得到的标准图像见图十七；实验数据二所有576帧图像得到的标准图像见图十八。图十七 实验数据一的标准背景图像图十八 实验数据二的标准背景图像确定了标准图像后，考虑比较标准。越接近标准图像的背景图像越好。如何比较两幅图像是否接近？我们使用峰值信噪比PSNR来衡量图像的接近程度。峰值信噪比的计算公式如下：其中，对数中分子的255表示像素灰度最大的差值，在256级灰度中，这个最大差值是255（255-0=255）；对数中分母的M是图像的像素总数，F1(i)、F2(i)表示两幅图像中的某个像素，整个分母表示两幅图像的所有对应像素的差的平方的平均值，如果是彩色图像，“对应像素的差的平方”用对应像素矢量的分量的差的平方和除以3计算。可以看到，当两幅图像越接近，对数中的分母就越小，峰值信噪比就越大；当两幅图像差别越大，对数中的分母就越大，峰值信噪比就越小。极端情况，当两幅图像一样时，峰值信噪比为无穷大；两幅图像差别最大时，峰值信噪比为0。我们就以峰值信噪比衡量两幅图像的相近程度，峰值信噪比越大，图像越接近。实验数据一不同方法在不同采样率下得到的背景的图像与标准背景图像比较的PSNR见表二。采样率(f/s)122.556.2512.525基于均值34.83 37.05 37.25 37.42 37.40 37.65 37.62 改进的基于均值36.26 40.65 40.75 40.82 40.82 41.41 41.36 基于中值滤波35.19 37.53 37.71 37.80 37.61 37.83 37.76 基于共同区域34.58 38.10 38.33 39.05 39.14 39.95 40.01 表二 实验数据一不同方法得到的背景与标准背景图像比较的PSNR比较同一采样率下不同方法的PSNR不能说明问题，因为同一采样率下不同方法需要的实际处理时间不相同。在处理时间一定的情况下，PSNR越大的方法越好。因此，结合表二和表一，得到不同方法的PSNR随处理时间变化关系图。实验数据一不同方法的PSNR随处理时间变化关系图如图十九。图十九 实验数据一不同提取背景的算法PSNR与处理时间关系图将图十九中横坐标0，10区间部分作局部放大，得到图二十。图二十 实验数据一不同提取背景的算法PSNR与处理时间关系图（局部）实验数据二不同方法在不同采样率下得到的背景的图像与标准背景图像比较的PSNR见表三。采样率(f/s)122.556.2512.525基于均值24.05 24.63 24.76 24.88 24.88 24.95 24.94 改进的基于均值27.77 29.13 29.43 29.83 29.86 29.97 30.01 基于中值滤波26.39 28.28 28.72 29.23 29.24 29.40 29.47 基于共同区域25.10 26.25 26.49 27.07 27.14 28.02 28.16 表三 实验数据二不同方法得到的背景与标准背景图像比较的PSNR实验数据二不同方法的PSNR随处理时间变化关系图，如图二十一。图二十一 实验数据二不同提取背景的算法PSNR与处理时间关系图将图二十一中横坐标0，10区间部分作局部放大，得到图二十二。图二十二 实验数据二不同提取背景的算法PSNR与处理时间关系图（局部）从图二十和图二十二这两组实验数据的结果中，我们可以得到以下结论：1、并不是采样率越高（处理时间越长），PSNR就越高。不同的方法在4秒之后，尽管采样率不同，但PSNR值都基本不变了。这是因为不同的图像帧区别只在于运动前景不同，背景是相同的，因此不同图像帧之间存在着信息冗余，增加采样率，只会增加处理时间，不会增加PSNR，也即不会提高背景提取的质量。也就是说，在背景提取的时候，我们不需要很高的采样率即可得到不错的背景图像。2、基于均值的算法是效果最差的算法，因为其只是简单的平均，没有做更多的处理。3、共同区域法需要更高的采样率才能得到好效果。这是因为要找到更多的共同区域，就需要更高的采样率。从提取出来的背景图像的人眼视觉效果来说，基于共同区域的算法的背景图像最不平滑。4、基于中值滤波的背景提取算法，只是取排序中位于中间的元素作输出，舍弃掉了其他元素，没有充分利用其他元素的信息，并且排序比较耗时，因此基于中值滤波的背景提取算法不是很好的算法。5、效果最好的算法是改进的基于均值的背景提取算法。综上所述，对于10秒的视频图像序列，采用每秒2帧的采样率，使用改进的基于均值的背景提取算法，不到4秒就可以得到优秀的背景图像。而背景提取对实时性本来要求就不高，不需要像物体运动跟踪那样对所有输入帧都进行处理，这种方法完全能达到应用的要求。3.2 灰度图像的背景提取运动目标检测和跟踪可以不直接使用原始彩色图像序列，而使用灰度图像序列，即将彩色视频图像序列转换成灰度图像序列，然后在灰度图像序列上提取背景，以及之后提取运动点团、运动跟踪等。这一节首先讲述彩色图像转换成灰度图像的方法，然后再讨论灰度图像的背景提取。3.2.1 彩色图像转换成灰度图像彩色图像每个像素点在RGB空间中是一个三维矢量，每个分量分别代表红、绿、蓝三种颜色的灰度。最简单的将彩色图像转换成灰度图像的方法是将这三个分量取平均值。但是这种方法和人眼视觉感知不符。人眼感知红、绿、蓝三种颜色的权重是不一样的。JPEG图像压缩格式采用的是YUV空间，YUV空间是RGB空间的线性变换。转换公式是11R、G、B分别表示红、绿、蓝三种颜色分量的灰度值。Y分量表示图像的亮度，这是符合人眼对颜色感知的。我们就以Y分量作为图像像素的灰度。将彩色像素转换为灰度像素的公式为将彩色图像转换为灰度图像的算法如下：遍历彩色图像的每一个像素矢量，设矢量的红、绿、蓝三色分量值为R、G、B，则输出的灰度图像的对应像素的值为0.299R+0.587G+0.114B3.2.2 灰度图像的背景提取前面所述的所有彩色图像背景提取的算法都能用在灰度图像的背景提取上，只要在计算距离的时候将矢量的欧氏距离改为标量差的绝对值即可。图二十三至图二十六分别是实验数据一的灰度图像序列的基于均值的背景提取、改进的基于均值的背景提取、基于中值滤波的背景提取和基于共同区域的背景提取结果。图二十三 灰度图像序列的基于均值的背景图像图二十四 灰度图像序列的改进的基于均值的背景图像图二十五 灰度图像序列的基于中值滤波的背景图像图二十六 灰度图像序列的基于共同区域的背景图像3.3 边缘图像的背景提取背景提取的目的是为了去除背景，取得每一帧图像的运动前景。而前景背景分离最重要的信息是物体的边缘信息。因此，可以首先将每一帧原始图像做边缘提取，得到边缘图像序列，然后提取边缘图像背景，再提取运动前景、做运动跟踪。3.3.1 彩色图像的边缘提取对灰度图像，边缘提取就是求每个像素的梯度，以梯度大小作为边缘的量度。用x、y两个方向的离散偏微分算子边缘检测算子对图像做卷积，就得到这两个方向上的梯度，以这两个方向的量为分量的矢量就是这个像素的梯度矢量，这个矢量长度的大小就是这个像素的边缘值。设f(x,y)是离散灰度图像，g(x,y)是卷积核，f和g的卷积是如果卷积核是的矩阵，则此卷积运算的时间复杂度是O(9M)，M是图像的像素总数。常用的边缘检测算子是Prewitt边缘算子和Sobel边缘算子。图二十七和二十八是Prewitt边缘算子，图二十九和三十是Sobel边缘算子。它们都是的矩阵12。-1-1-1000111图二十八 y方向的Prewitt边缘算子之一-101-101-101图二十七 x方向的Prewitt边缘算子-1-2-1000121图三十 y方向的Sobel边缘算子-101-202-101图二十九 x方向的Sobel边缘算子对彩色图像，如果将其三个颜色分量的图像分别计算梯度，然后将得到的三个颜色的梯度叠加作为边缘提取的结果，则等价于先将彩色图像转换成灰度图像，再在灰度图像上作边缘提取。因为卷积运算和彩色转换成灰度运算都是线性运算。然而，这么做就将彩色信息给丢失了，彩色图像的边缘，并不是三个颜色分量边缘的简单叠加。下面讲述如何将边缘提取推广到彩色图像中13。用Prewitt算子举例说明。对灰度图像，将Prewitt边缘检测x方向算子带入卷积公式中，可以得到即一个像素的梯度是它附近三对像素的灰度差的和。将这个式子扩展到矢量空间，认为一个像素的梯度是它附近三对像素的矢量欧氏距离的和，即可得到式子中f(x,y)是图像中像素矢量，|a-b|是计算矢量a和b的欧氏距离。这样，对每一个彩色像素，都考虑了整个彩色像素矢量，也就是同时考虑了每个像素的三个颜色分量。同理，Prewitt边缘检测y方向算子扩展到矢量空间，可得上面的两个方向的算子就是Color-Prewitt边缘检测算子。同样的，Color-Sobel边缘检测x方向的算子是Color-Sobel边缘检测y方向的算子是需要指出的是，边缘值是梯度长度的大小，因此边缘值是个标量，边缘图像是灰度图像。3.3.2 边缘图像的背景提取因为边缘图像是灰度图像，前面所述的所有图像背景提取的算法都能用在边缘图像的背景提取上。图三十一和图三十二分别是实验数据一的Color-Prewitt边缘图像序列和Color-Sobel边缘图像序列的基于均值的背景提取结果，图三十三和图三十四分别是Color-Prewitt边缘图像序列和Color-Sobel边缘图像序列的改进的基于均值的背景提取的结果。改进的基于均值的背景提取算法依然是这几种算法中效果最好的。Color-Prewitt和Color-Sobel边缘检测算法算法得到的边缘图像差不多。图三十一 Color-Prewitt边缘图像序列的基于均值的背景图像图三十二 Color-Sobel边缘图像序列的基于均值的背景图像图三十三 Color-Prewitt边缘图像序列的改进的基于均值的背景图像图三十四 Color-Sobel边缘图像序列的改进的基于均值的背景图像第四章 运动点团提取和背景更新运动点团提取也称背景去除、背景抑制，就是把每一帧的非背景部分提取出来。非背景部分就是运动前景，但这里不称其为前景是因为这一步处理的是第二章所说的点团层，我们在点团层上面还有一层运动物体层，这是为了提高运动跟踪的效果，详见第七章。根据运动物体和场景中的静止背景在亮度、色度上的不同，将图像序列的每一帧图像与背景图像作差，然后二值化，就可以得到每一帧的运动点团：图像中的一个像素，如果它与背景图像对应像素的距离大于一个阈值，则认为它是前景，输出1，否则为背景，输出0。最后得到的二值图像就是运动点团图像。阴影的处理是运动点团提取这一步重要的一环。阴影不应该作为前景的一部分，然而阴影与背景有差别，背景差法会把阴影归到前景中去，这样就会导致阴影将不同的运动物体连接成一个物体，降低运动目标检测的精确度。因此需要对阴影做专门的处理。第4.1节叙述彩色图像的运动点团提取。第4.2节叙述阴影的处理。第4.3节叙述灰度图像的运动点团提取。第4.4节叙述边缘图像的运动点团提取。运动点团提取可以不采用背景差法，而采用帧间差法，第4.5节讲述基于帧间差法的运动点团提取并且将其与背景差法比较，指出其存在的问题。背景提取出来后，并不是不变的。它会随时间变化而变化。光照的改变、原来作为背景的物体运动出去或者运动物体静止下来成为背景等情况，都会导致背景的变化。因此背景需要不断的更新。第4.6节将简述背景更新的一些策略。4.1 彩色图像的运动点团提取彩色图像的基于背景差的运动点团提取，根据前景与背景的颜色不同，将原始彩色图像序列的每一帧图像与彩色背景图像作差，然后将结果图像二值化。第3.1节详述了背景提取的算法。两帧彩色图像的差是指两帧中对应像素矢量的距离。常用的矢量距离是欧氏距离和马氏距离，下面分别叙述。4.1.1 基于马氏距离的运动点团提取设随机矢量x的均值是，协方差矩阵是，则x与的马氏距离是对彩色图像的像素矢量，假设每一个颜色分量相互独立，则不同分量的协方差为0，即协方差矩阵非对角线元素都为0，对角线元素就是对应分量的方差，上式可以写成14其中x.r、x.g、x.b分别表示像素矢量红、绿、蓝三种颜色分量的值，、分别表示背景像素矢量的红、绿、蓝三种颜色分量，、分别表示红、绿、蓝三种颜色分量的方差，也就是矩阵的对角元素。在背景提取的时候可以把每个像素的方差计算出来。像素点(x,y)的方差计算方法如下：,c=r,g,b其中Fi是采