毕业论文基于快匹配的人群运动估计.doc

本科生毕业论文（设计）题 目 基于块匹配的人群运动估计学 院 软 件 学 院专 业 软 件 工 程学生姓名 舒 禹 铭学 号 0643111170 年级 2006指导教师 李 晓 华教务处制表二一年六月一日基于块匹配的人群运动估计软件工程学生 舒禹铭 指导老师 李晓华摘要 智能化人群监控是智能视频监控研究中的一个重要课题，它作为智能监控中的一项关键技术，在人群管理、公共场所设计、虚拟环境建模、视觉监控、智能环境模拟等方面都有着重要的应用价值。随着经济社会的发展，各种公共场地和设施中的人群流动越来越频繁。如何对公共场合的人群进行有效管理与控制，是不得不考虑的重大问题。智能化人群监控技术应运而生，它主要包括人群的密度估计和运动估计两部分内容。本文着手解决人群运动估计这一块，智能化运动估计可以用于人群的监测和管理，也可应用于商业领域，如市场调查、交通安全以及建筑设计领域等。它们能够直接或间接地提高上述场合工作人员的工作效率和建筑设施的利用率，因此对人群密度估计和运动估计方法的研究有着深远的意义和广阔的前景。本文结合OpenCV，采用块匹配算法对人群的运动进行估计，并在功能实现前对OpenCV与块匹配各重要环节有具体分析。主题词 人群监控；人群运动估计；块匹配；OpenCV Crowd motion estimation based on BMASoftware EngineeringStudent： YuMingshu Adviser: XiaoHualiAbstract Intelligentized crowd surveillance tecllIlology is an important research subfield in intelligem video surveillance systemAs a key tecllnology of intelligent surveillarlce，it is of great value in a large number of applications such as crowd management，public space design virtual environments simulate，visual surveillanlce，intelligent enviroments aIlalysis,etcWith the development of economic society, the crowd in various kinds of public places flows more and more frequently. How to manage and control the crowd effectively comes to be an important issue which we have to consider nowadays. Intelligentized crowd surveillance technology arises at the very moment. It mainly includes both density estimation and motion estimation.This paper set about the crowd motion estimation. Intelligentized crowd motion estimation can be used for monitoring and managing the crowd, at the same time, it can also be used for market survrey in the commercial field，traffic safety and architectural design field,etc. it can help staff members in the above mentioned occasions improve working efficiency and improve utilization ratio of building facilities directly or indirectly,so there is far-reaching meaning and wide prospect in crowds density and motion estimation research.According to OpenCV, this paper use BMA(Block Matching Algorithm) for crowd motion estimation，and before the function running ,it has a specific analysis about OpenCV and the important case of BMA.Key Words crowd surveillance；crowd motion estimation；Block Matching Algorithm；OpenCV目 录1绪论11.1研究背景11.1.1智能监控11.1.2人群监控的提出11.1.3运动估计21.1.4块匹配算法21.1.5OpenCV21.1.6论文工作构思31.2国内外研究与技术现状31.2.1智能人群监控的研究现状31.2.2运动估计方法的研究现状41.2.3块匹配现状41.3 论文主要工作51.4 论文组织与结构52块匹配算法介绍及分析62.1运动估计62.2块匹配基本思想62.2.1 初始搜索点的选择72.2.2 块匹配准则82.2.3 搜索策略82.3典型的块匹配算法92.4各模块拟采用的算法153人群运动估计的块匹配算法实现163.1 实现工具OpenCV163.2 cxcore.h173.2.1 CvPoint,CvSize173.2.2 CvMat173.2.3 IplImage193.2.4 其他函数213.3 cv.h243.3.1 cvCvtColor243.3.2 cvSmooth263.3.3 cvCalcOpticalFlowBM273.4 highgui.h283.4.1 CvCapture283.4.2 窗口函数283.4.3 cvWaitKey313.5 算法实现313.5.1 图像处理（视频处理）323.5.2 块匹配373.5.3 过滤非运动的物体393.5.4 连线403.6 程序算法流程图413.7 程序实现截图424软件的测试454.1 测试环境454.1.1 硬件环境454.1.2 软件环境454.2 测试步骤454.2.1 测试总体目标454.2.2 测试计划实施步骤454.3 测试用例454.3.1 分支测试454.3.2 集成测试554.4 测试结果分析575总结和展望585.1 工作总结585.2 心得体会58致 谢62附录1 程序源代码63附录2 翻译（原文和译文）761 绪论1.1 研究背景1.1.1 智能监控随着视频分析技术和人工智能技术的发展，智能视频监控已成为一个非常活跃的研究领域，它涉及信号分析、图像处理、计算机视觉、机器学习、模式识别等多门学科，主要研究图像序列中感兴趣目标的检测、跟踪、行为分析与识别等问题。目前，智能监控的研究大多集中于少数目标个体上。如对单个人的检测、跟踪、行为识别，对车辆的监控，以及人和车辆的交互行为等。智能化人群监控是智能视频监控研究中的一个重要课题，它作为智能监控中的一项关键技术，在人群管理、公共场所设计、虚拟环境建模、视觉监控、智能环境模拟等方面都有着重要的应用价值1。1.1.2 人群监控的提出随着社会的发展，公共安全需求的提高，群体运动分析受到越来越多人的关注,美国人口普查局在08年的一份报告中指出，1999年，世界人口达到60亿，比1960年翻了一倍。08年全球人口已达到67亿，预计到2050年，全球人口将超过90亿。随着人口的增加，人群活动日益增加，相对应地，人群安全问题也越来越突出，对人群的分析研究分别在社会学、心理学、建筑学、计算机等各个学科受到了极大的关注。现代社会，伴随经济的发展 ,各种高层建筑、地下建筑和大型商业娱乐设施也越来越多 ,同时出入或围绕这些建筑物的人群也在加大，一旦拥挤人群发生突发事件,容易造成群死群伤事故，因此必须考虑到人群的安全问题。人们经过探索，最终提出了人群监控这一技术2。人群监控是借助于数字图像处理技术对某一区域的人群进行监控,它在社会生活和生产的许多领域有着广阔的应用前景3。传统的人群监控通过监控场景所安装的闭路电视进行人工监控，费时费力且缺乏实时性，不能做到每时每刻监控，且比较主观，不能做定量判断，起不到预防的作用且容易发生漏报现象。随着智能化技术的发展，智能化的人群监控技术已成为研究的热点。现代数字图像处理技术的发展 ,为解决上述问题提供了途径。将图像处理、模式识别、计算机视觉等技术应用在人群监控中 ,可以达到对人群的自动、客观、实时、定量分析。自智能化人群监控技术提出以后 ,人们对其进行了广泛研究 ,目前已有许多算法 ,一些实用的系统也开始应用在广场、车站等场合的人流监控中。人群监控分为人群密度估计和人群运动估计，本文着手解决人群运动估计。1.1.3 运动估计考虑到人群密度和运动的自动监测量和以及智能检测人群分布和流量的重要性，需要一个不管在人群密度大或小都能正常测量的新技术，但是这是一个困难的问题，因为在视频显示人群中，通常只会出现一部分人，重叠现象很严重4。从而分别提出了密度估计法与运动估计法这两类技术。密度估计法提出一种纹理法分析法，它可以在重叠现象严重的视频中进行较精确的估计5，这里略过。运动估计法的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。 运动估计和运动补偿是AVS 中去除时间冗余的主要方法，作为视频压缩编码系统的核心算法，占整个系统运算量的60%-80%，它采用多种宏块划分方式，1P4 像素插值、双向估计和多参考帧等技术大大提高了编码效率，但同时也给编解码器增加了一定的复杂度。运动估计算法是视频压缩编码的核心算法之一。高质量的运动估计算法是高效视频编码的前提和基础。其中块匹配法（BMA, Block Match Algorithm）由于算法简单和易于硬件实现，被广泛应用于各视频编码标准中。1.1.4 块匹配算法块匹配法的基本思想是先将图像划分为许多子块，然后对当前帧中的每一块根据一定的匹配准则在相邻帧中找出当前块的匹配块，由此得到两者的相对位移，即当前块的运动矢量。在H.264标准的搜索算法中，图像序列的当前帧被划分成互不重叠16×16大小的子块，而每个子块又可划分成更小的子块，当前子块按一定的块匹配准则在参考帧中对应位置的一定搜索范围内寻找最佳匹配块，由此得到运动矢量和匹配误差。运动估计的估计精度和运算复杂度取决于搜索策略和块匹配准则。这里使用H.264推荐算法UMHexagonS（Unsymmetrical-cross Multi-Hexagon-grid Search）作为DSP实现的算法参考，与FS算法比较，它在保证可靠搜索精度的前提下大幅降低搜索复杂度。同时使用绝对差和（SAD, the Sum of Absolute Difference）标准作为匹配准则，它具有便于硬件实现的优点。1.1.5 OpenCV计算机视觉是在图像处理的基础上发展起来的新兴学科，OpenCV(Open Source Computer Vision Library，开源计算机视觉库) 是一种数字图像处理和计算机视觉的函数库，它是一个跨平台的开源计算机视觉库，最初由Intel公司微处理器实验室(IntelS Microprocessor Research Lab)的视觉交互组(The Visual Inter-activity Group)开发6，是Intel资助的两大图像处理利器之一，以BSD许可证授权发行，可免费用于商业和研究领域，它可以在Windows系统、Linux系统、Mac0Sx系统等操作平台上使用，也可以和其他编程工具结合，以满足不同的使用要求。它包含许多常用的算法，为图像处理、模式识别、三维重建、物体跟踪、机器学习和线性代数提供了各种各样的算法7。它已经广泛应用于对实时性要求较高的计算机视觉和模式识别系统的开发。截至2009年8月，在的下载次数已经超过2 200 000次，大量用户来自中国。1.1.6 论文工作构思关于人群运动估计，本文用到的方法是块匹配，工具有OpenCV和vc6，程序用C和C+编写。为了更好的进行人群运动估计，前期准备必不可少，1. 学习图像处理的基本原理，了解人群监控的意义，采集若干组实验用视频序列；2. 了解现有图像处理的运动估计方法，学习OpenCV视频处理的基本知识，掌握块匹配的主要方法，利用OpenCV实现块匹配的原理和技术。完成以上两点后，利用C和C+编写程序实现功能。1.2 国内外研究与技术现状1.2.1 智能人群监控的研究现状目前，国内的安全防范工作中，智能人群估计领域基本还是一项空白，相关的文献和技术资料很少，基础理论和相关技术不多，没有成熟的产品，国外在人群运动分析方面研究较多。本文的研究对象是运动群体(这里的群体特指人群)，研究内容是运动人群的运动估计。传统的保障人群安全的途径主要有:人群的密度估计与运动估计采用物理方法修正建筑物。在一些容易发生人群聚集的地方，采取适当地修正现有建筑物的方法，比如在人多的地方增加出入口等。利用闭路电视监控某一场景。闭路电视对周围环境进行例行地扫描来查找发生危险的地方，并有专门的工作人员盯着屏幕，以便发生情况及时通报并采取措施。但是这样做主要有如下缺点:不能起到预防的作用。即使人可以根据经验来发出危险警告，但由于人的主观性太强，很容易发生预告太晚或者错误预告的情况。易造成漏报。当人群己经发生拥塞时，一般采取的方法是:关闭人群正在大量涌入的入口。这种方法虽然解决了建筑物某个入口处的拥挤问题，但是人群很可能又涌向别的入口造成新的拥挤。所以这种做法往往不能从根本上解决问题。近年来，对人群的研究越来越引起人们的关注，对人群状态和行为的研究也越来越多，而人群研究的前提是要弄清如何对人群进行适当的描述。虽然人群由独立个体组成，而每一个个体又有他自己的行为模式，但作为总体的人群有它整体性的特征，且可被描述出来。要想用精确的数学模型来描述人群的状态和行为非常困难，但我们仍然看到了一些能够逼近人群真实行为的数学模型的出现，如stliiG.K.的人群动力学，Corwd Dynamic Limted公司依据StlilG.K.的数学模型应用AuotCAD做出了一些建筑设施的设计方案。1.2.2 运动估计方法的研究现状作为视频编码器中计算量最大的一个模块，运动估计能够有效地减少帧问相关性，因此被广泛用于各种视频编码标准中，如MPEG-1、MPEG-2、MPEG-4、H26l、H263和H264/AVC等8。人群运动估计的传统方法是人工估计，但这种方法比较主观，不能做定量判断。二十世纪以来，人群人群密度和运动估计的自动方法逐渐发展起来。在密度估计上主要有Davies，Chow，Marana等人的方法；在运动估计上主要有Rourke等人的方法。这些方法各有不足。Davies和Chow的方法在人群密度较高时，由于人群遮挡现象，测量值与人群人数之间的线性关系消失，导致误差很大，且这些方法要求提供场景的背景图像。Marana的方法虽然可以解决高密度人群的估计问题，但计算量较大，处理时间较长，而且该方法没有考虑摄像机透视效应问题。Rourke等人的人群运动估计的方法都限于低密度人群，如果人群密度较高，出现个体间的相互遮挡使得个体信息提取不全对，就会遇到困难9。1.2.3 块匹配现状在主流视频压缩标准(如 H.26x，MPEG 系列等)中，视频系统编码器的效率主要取决于运动估计算法，而运动估计的效率主要体现在图像质量、压缩码率和搜索速度3个方面10， 这些由采用的搜索策略、匹配准则和初始搜索点的选择等因素决定。块匹配运动估计算法算法简单，便于 VLSI 实现，被广泛应用。目前，其研究主要集中在：1)利用不同帧相同位置块和相同帧内相邻块运动矢量的相关性，从同帧中左上、上、左等块的运动矢量及前一帧或前几帧相同位置块的运动矢量中挑选出当前块运动矢量的最优初始值 然后再按照某一种算法进行搜索；2)不断改进运动估计匹配模板的形状和大小，旨在减少搜索点数，从而减少搜索时间，提高编码速度；3)通过数学不等式来改进目标函数，通过判断提前结束搜索，达到节约运算量和运算时间的目的。其中第2点通过改进模板的方法来减少搜索点数更是当前的研究热点，出现了许多算法。研究方向。1.3 论文主要工作在视频运动估计方面，相关技术比较多，也比较成熟，而在人群运动估计方面，主流技术则显得较不成熟，各种算法层出不穷，用得最多的只有几种，其中关键就在于对时间性和空间性的要求，随着科学技术的发展，对这两点的要求已不再那么强烈，注意力已转移到性能上，一般来说，性能越好，算法越复杂，而OpenCV作为一个开源视觉库，全部由C语言写就，因此，这是一个十分强大的图像视觉处理工具，对细微处的处理很好，其功能接口都为函数，程序员只需调用函数便可完成一系列高效高质量的操作。而本程序在人群运动估计这一方面运用了一种全新的处理方法，即利用OpenCV完成块匹配法运动估计，其真正达到了高性能高密度。1.4 论文组织与结构第1章：绪论。主要介绍了人群监控发展和应用，以及本论文的研究背景和研究工作，利用OpenCV实现基于块匹配的人群运动估计的设计目的；第2章：块匹配法各模块算法背景与分析。介绍运动估计，把块匹配法分为各个模块，并对其算法进行介绍与分析，同时在最后得出各个模块最合适的算法；第3章：算法分析与设计。说明运动估计视频处理的各个步骤所需处理，并分析处理所需算法，介绍背景建模；第4章：算法的实现。介绍实现该算法的工具，并对程序各模块一一实现；第5章：算法的验证和评价。对算法进行测试，对结果进行分析；第6章：结论。本章对全文工作以及毕业收获进行总结，指出了还需改进的地方。2 块匹配算法介绍及分析本章主要介绍块匹配算法的各个模块，及各模块所用到的算法。2.1运动估计运动估计已发展得较为成熟，最常用于人群监控与视频压缩编码。基于块的运动估计和补偿是视频编码中最通用的算法。它把图像域分割成互相不重叠的称为块的小区域，并且假定每一个块内的运动都可以用一个简单的参数模型特征化，如果快足够小，那么这种模型是相当合理的。目前这种方法被广泛用于视频标准变换运动补偿滤波和采用基于块的运动补偿进行的数字视频压缩 1112 。在一幅幅复杂的人群图像中，如果依靠每个步行者的个体信息来估计人群总体的运动，必须要分离出每个个体的运动。但要做到这点并不容易，因为在开放的空间中，一个步行者可能向各个方向移动，且步行者的身体各部分的移动方式也各不相同，进而，当人群密度较大，个体之间有相互遮挡时，这就变得更加困难，甚至是不可能的。因此，本文提出基于块匹配的人群运动估计（BMA）。这种方法由于实现较简单且容易而受到广泛关注。BMA并不借助人群中个体的信息，而是通过统计视频中各宏块的运动矢量估计出人群整体的运动 13 。2.2块匹配基本思想基于块匹配法的运动估计的基本思想就是将当前帧分成互不重叠的大小为M×N的宏块(一般情况下M=N)，然后对当前帧中的每一个块都在参考帧中的一定区域，即搜索窗口内，按照一定的匹配准则搜索与之具有最小匹配误差的块(Minimal DistortionBlock，MDB)，该块即为当前块的匹配块，由匹配块与当前块的相应位置计算出运动位移，所得运动位移即为当前块的运动矢量。并且假定每一个块内的运动只做相等的平移同时可以用一个简单的参数模型特征化。如果块足够小，那么这种模型是相当合理的。匹配块与当前块之间的坐标位移就是运动矢量，匹配块与当前块的对应象素点逐个做差就的到差值块。基于这样的方法这样，当前帧中的每一个块都可以用一个差值块和一个运动矢量来表示，对当前帧的编码就转化为对每一块的差值块和运动矢量的编码。块匹配的原理如图2-1。运动估计算法的整体效率主要体现在初始搜索点的选择、匹配准则和运动搜索策略三个方面。本程序主要用基于块的运动方式开发出的运动估计算法块匹配算法。块匹配算法由于它具有较少的硬件复杂度，容易在超大规模集成电路中实现，因此被认为是最通用的算法。 图2-1 块匹配原理图为了提高图像质量，加快估计速度是运动估计算法的研究目标之一。通常是通过研究初始搜索点的选择、匹配准则和运动搜索策略等来提高算法效率的13。2.2.1初始搜索点的选择(1)直接选择参考帧对应块的中心位置。这种方法简单，但容易陷入局部最优点。如果采用的算法初始步长太大，而原点(以下均指待搜索块的中心点在参考帧中的相同位置的对应点，而不是坐标位置的真正原点)又不是最优点，有可能使快速搜索跳出原人群的运动估计点周围的区域(这些区域可能包含最优点)而去搜索远距离的点，导致搜索方向的不确定性，这就有可能陷入局部最优。(2)选择预测的起点。由于相邻块之间和相邻帧之间具有很强的相关性，因而许多算法都利用这种相关性先对初始搜索点进行预测，以预测点作为搜索起点。大量实验证明预测点越靠近最优匹配点，越会使得搜索次数减少。下面举例说明几种常见的预测方法。方法1:基于SAD(the Sum of Absolute Differences)值的起点预测方法。分别求出当前块与其相邻块间的SAD值，然后选取SAD最小的块的运动矢量作为预测值。这种方法预测精度高，但计算SAD值的时间开销大。改进的方法是利用运动矢量的相关性来预测起点。方法2:利用相邻块和相邻帧对应块的运动矢量来预测当前块的搜索起点。序列图像的运动矢量在空间、时间上具有很强的相关性。由于保存前一帧运动矢量信息在解码端需要占用大量内存，使得系统复杂化，故大多算法仅考虑同帧块的空间相关性来预测运动。比较典型的是“平均预测”，在H.263中使用三个相邻块的运动矢量的中值作为当前块的运动矢量的预测值。方法3:基于相邻运动矢量相等的起点预测方法。如果当前块的各相邻块的运动矢量相等，则以其作为当前块运动矢量的预测值;否则，使用方法1求出当前块与其相邻块间的SAD值，然后选取SAD值最小的块作为预测起点。这种方法在保证精度的基础上利用运动矢量相关性从而大大减少了计算量。运动估计的复杂度主要取决于匹配计算量和所采用的搜索算法这两个方面14。在下一节中将介绍在运动估计常用的一些匹配准则。2.2.2块匹配准则运动估计算法中常用的匹配准则有三种，即最小绝对值差(MAD)、最小均方误差(MSE)和归一化互相关函数(NCCF)，它们分别定义如下:(1) 最小绝对值差: （1）式中，B代表M×N宏块，(dx,dy)为运动矢量，fk与fk-1分别为当前帧和前一帧的灰度值，若在某一个点(x，y)处MAD(dx,dy)达到最小，则该点为要找的最优匹配点。若在某一个点(x,y)处MAD(dx,dy)达到最小，则该点为要找的最优匹配点。(2)最小均方误差: （2）能够使MSE值最小的点为最优匹配点。(3)归一化互相关函数： （3）式中NCCF的最大值点为最优匹配点。在运动估计中，匹配准则对匹配的精度影响不是很大，由于MAD准则不需要作乘法运算，实现简单、方便，所以使用最多，通常使用ASD代替MAD。SAD即求和绝对误差，其定义如下: （4） 2.2.3 搜索策略搜索策论选择恰当与否对运动估计的准确性，运动估计的速度有很大的影响。有关搜索策略的研究主要是解决运动估计中存在的计算复杂度和搜索精度这一矛盾。如全搜索法，它对搜索范围内的每一个像素点进行块匹配运算以得到一个最优的运动矢量。不过，较大的搜索窗通常会使得搜索点增多，从而加大计算量，因此，搜索距离的设定需综合考虑具体视频的运动特性、运动估计的质量以及算法的计算量等因素，以获得最佳的估计性能15。另外三步法、二维对数法、交叉法等主要是通过限制搜索位置的数目来减少计算量。这以后的许多搜多策略都是为了平衡搜索精度与计算速度而产生的。2.3典型的块匹配算法在MPEG2-4视频编码算法中，运动估计(ME)的计算量占整个编码计算量的2/3以上16。在视频编码系统中，运动估计处理消耗近50%的功耗16。为了减小运动估计计算量，出现了各种块匹配算法，它们只是搜索策略各有不同，其中搜索精度最高的是全搜索法，但由于计算复杂度高，不宜于实时应用，为此人们提出了各种改进的快速算法。下面介绍几种常用的经典算法。 (l)全搜索法(FS，Full Seacrh method)算法思想:全搜索法也称为穷尽搜索法，或螺旋向外搜索法，是对搜索范围内所有可能的候选位置计算其SAD(i，j)值，从中找出最小SAD，其对应偏移量即为所求运动矢量。此算法计算量虽大，但最简单，可靠，找到一定是全局的最优点。算法描述:Setpl:从原点出发，按顺时针方向由近及远，在每个像素处计算SAD值，直到遍历搜索范围内的所有点。StPe2:在所有的SAD中找到最小块误差(MBD)点(即SAD最小值的点)，该点所在位置即对应的最佳运动矢量。模板及搜索过程图示:如图2-2所示。 图2-2 全搜索法搜索过程算法分析:FS算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但它的计算量很大，这就限制了在需要实时性较强的场合的应用，所以有必要进一步研究其它快速算法。(2)二维对数法(TDL，Two-Dimensional Logarithmic)二维对数搜索法由J.R.Jain和A.K.Jaini提出，它开创了快速算法的先例，分多个阶段搜索，逐次减小搜索范围直到不能再小时结束。基本思想:二维对数搜索法是由原点开始，以“十”字形分布的五个点构成每次搜索的点群，通过快速搜索跟踪加MBD点。算法描述:Step 1:从原点开始，选取一定的步长，在以“十”字形分布的五个点处进行块匹配计算并比较。Step 2:若MBD点在边缘四个点处，则以该点做为中心点，保持步长不变，重新搜索“十”字形分布的五个点;若为MBD点位于中心点，则保持中心点位置不变，将步长减半，构成“十”字形点群，在五个点处计算。Step 3:若步长为1，在中心及周围8个点处找出MBD点，该点所在位置即对应最佳运动矢量，算法结束;否则，重复Step 2。搜索过程图示:如图2-3所示。算法分析:TDL算法搜索时，最大搜索点数为2+7lbW，这里W表示最大偏移量max(dxmax,dymax)。若发现新的“十”字形点群的中心点位于搜索区域的边缘，则步长也减半。后来有人提出应该在搜索的每个阶段都将步长减半。所有这些改动都是为了使算法搜索范围很快变小，提高收敛速度。TDL算法的前提是假设搜索区域内只有一个极小值点，如果搜索区域内存在多个极小值点时，该方法找到的可能是局部最小点。不能保证找到全局最优点也正是大部分快速搜索算法的缺点。 图 2-3 二维对数法过程 (3)三步搜索法(TSS，而Three Step Search)三步搜索法与TDL类似，由于其简单、健壮、性能良好的特点，已被人们所重视。若最大搜索长度为7，搜索精度取1个像素，则步长为4、2、1，共需要三步即可满足。基本思想:TSS算法的基本思想是采用一种由粗到细的搜索模式，从原点开始，按一定步长取周围8个点构成每次搜索的点群，然后进行匹配运算，跟踪最小块误差MBD点。.算法描述:Step 1:从原点开始，选取最大搜索长度的一半为步长，在中心点及周围8个点处进行块匹配计算并比较。Step 2:将步长减半，中心移到上一步的MBD点，重新在中心点及周围的8个点处进行块匹配计算并比较。Step 3:在中心点及周围8个点处找出加MBD点，若步长为1，该点所在位置即对应最佳运动矢量，算法结束;否则，重复Step 2。搜索过程图示:一个可能的搜索过程如图2-4所示。图2-4中点+4，+4、 +6，+4是第一、第二步的最小块误差点。第三步得到最终运动矢量为+7，+5，每个点上的数字表明了每个阶段搜索时计算的候选块的位置。 图2-4 三步搜索法搜索过程算法分析:TSS算法搜索时，整个过程采用了统一的搜索模板，使得第一步的步长过大，容易引起误导，因此对小运动模式的效率较低。最大搜索点数为1+8blW，当搜索范围大于7时，仅用三步是不够的，搜索步数的一般表达式为lb(dmax+1).(4)交叉法(CSA，Cross Search Algorithm)1990年，Chanbari提出了交叉搜索算法，它也是在TDL和TSS基础上为进一步减小计算量而发展起来的快速搜索法。本思想:CSA是从原点开始，以“×”字形分布的五个点构成每次搜索的点群，以TDL的搜索方法检测为MBD点，仅在最后一步采用“十”字形点群。算法描述:Step l:从原点开始，选取最大搜索长度的一半为步长，在以“×”字形分布的五个点处进行块匹配计算并比较，然后移动中心点。Step 2:以上一步的MBD点为中心点，步长减半，继续进行“×”字形的五点搜索。若步长大于1，则重复Step 2;若步长为1，则进行Step 3。Step 3:最后一步根据为MBD点的位置，分别进行“十”字形和“×”字形搜索。若上一步MBD点处于中心点、左下角或右上角，则做“十”字形搜索;若上一步MBD点处于左上角或右下角，则做“×”字形搜索。由当前为MBD点得到的最佳运动矢量，算法结束。搜索过程图示:图 2-5是CSA搜索的一个具体实例。图中每个点上的数字表明了每个阶段搜索时计算的候选块的位置，点+4，+4、+6，+21是第一、第二步搜索的MBD点。第三步箭头说明了两种不同的搜索模式。算法分析:CSA的最大搜索点数为5+4lbW，搜索速度很快，但是运动补偿的效果不是太好。在搜索区域的边界上有四分之一的点CSA没有考虑到，因此它不适用于较复杂的运动模式。 图2-5 交叉法搜索过程(5)四步搜索法(FSS，Four Step Search)四步搜索法是1996年由Lai一man Po。和Wing-Chung Ma提出的，该算法类似三步法，但它基于现实中序列图像的一个特征，即运动矢量大多都是中心分布的，从而在5×5大小的搜索窗口上构造了有9个检测点的搜索模板。本思想:TSS算法第一步用了9×9的搜索窗，这很容易造成搜索方向的偏离，FSS算法首先采用5×5的搜索窗口，每一步搜索窗的中心移向MBD点处，且后两步搜索窗的大小依赖于MBD点的位置。算法描述:Step 1:以搜索区域原点为中心选定5x5的搜索窗，然后在9个检测点处进行匹配计算，如图 2-6a所示。若MBD点位于中心点，则跳到Step 4;否则进行Step2。Step 2:窗口保持5x5大小，但搜索模式取决于上一步的MBD点位置。若上一步为MBD点位于窗口的四个角上，则另外再搜索5个检测点，如图2-6b所示;若上一步MBD点位于窗口的四边中心点处，则只需再搜索3个检测点，如图2-6c所示;若上一步MBD点在窗口中心，则跳到Step 4，否则，进行Step 3。Step 3:搜索模式同Step 2，但最终要进行Step 4。Step 4:将窗口缩小到3×3，这时计算出最小误差点的位置即对应最佳运动矢量，如图2-6d所示。 图 2-6 四步搜索法的搜索模块（a,b,c,d）搜索过程图示:图2-7是FSS搜索的一个具体实例。首先搜索点0，2，由于该点处于边的中心点处，故采用图2-6c的模板进行搜索，结果为2，4;由于该点处于搜索窗的角上，故用图2-6b的模板进行搜索，结果为模板中心点2，41;接着采用图 2-6d的模板进行搜索，得到的结果为3，5，故最终得到的运动矢量为3，5。图中每个点上的数字表明了每个阶段搜索时计算的候选点的位置。 图2-7 四步搜索法搜索模板算法分析:FSS是快速搜索算法的又一次进步，它在搜索速度上不一定快于TSS，搜索范围为±7时，FSS最多需要进行27次块匹配。但是FSS的计算复杂度比TSS低，它的搜索幅度比较平滑