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

《毕业论文（设计）_基于快匹配的人群运动估计.doc》由会员分享，可在线阅读，更多相关《毕业论文（设计）_基于快匹配的人群运动估计.doc（102页珍藏版）》请在三一文库上搜索。

1、本科生毕业论文（设计） 题 目 基于基于块块匹配的人群运匹配的人群运动动估估计计 学 院 软软 件件 学学 院院 专 业 软软 件件 工工 程程 教务处制表 二 一 年六月一日 四川大学本科毕业论文基于块匹配的人群运动估计 基于块匹配的人群运动估计基于块匹配的人群运动估计 软件工程 学生 舒禹铭 指导老师 李晓华 摘要摘要 智能化人群监控是智能视频监控研究中的一个重要课题，它作为智能监控中 的一项关键技术，在人群管理、公共场所设计、虚拟环境建模、视觉监控、智能环境模拟等 方面都有着重要的应用价值。 随着经济社会的发展，各种公共场地和设施中的人群流动越来越频繁。如何对公共场 合的人群进行有效管理

2、与控制，是不得不考虑的重大问题。智能化人群监控技术应运而生， 它主要包括人群的密度估计和运动估计两部分内容。本文着手解决人群运动估计这一块， 智能化运动估计可以用于人群的监测和管理，也可应用于商业领域，如市场调查、交通安 全以及建筑设计领域等。它们能够直接或间接地提高上述场合工作人员的工作效率和建 筑设施的利用率，因此对人群密度估计和运动估计方法的研究有着深远的意义和广阔的 前景。 本文结合 OpenCV，采用块匹配算法对人群的运动进行估计，并在功能实现前对 OpenCV 与块匹配各重要环节有具体分析。 主主题词题词 人群监控；人群运动估计；块匹配；OpenCV 四川大学本科毕业论文基于块匹配

3、的人群运动估计 3 Crowd motion estimation based on BMA Software Engineering Student： YuMingshu Adviser: XiaoHuali Abstract Intelligentized crowd surveillance tecllIlology is an important research sub field in intelligem video surveillance systemAs a key tecllnology of intelligent surveillarlce，it is of grea

4、t value in a large number of applications such as crowd management，public space design virtual environments simulate，visual surveillanlce，intelligent enviroments aIlalysis,etc With the development of economic society, the crowd in various kinds of public places flows more and more frequently. How to

5、 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. Int

6、elligentized 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 effic

7、iency 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

8、 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 1绪论绪论1 1 1.1 研究背景.1 1.1.1智能监控1 1.1.2人群监控的提出1 1.1.3运动估计2 1.1.4块匹配算法2 1.1.5OpenCV2 1.1.6论文工作构思3 1.2 国内外研究与

9、技术现状.3 1.2.1智能人群监控的研究现状3 1.2.2运动估计方法的研究现状4 1.2.3块匹配现状4 1.3 论文主要工作 5 1.4 论文组织与结构 5 2 2块匹配算法介绍及分析块匹配算法介绍及分析6 6 2.1 运动估计.6 2.2 块匹配基本思想.6 2.2.1 初始搜索点的选择7 2.2.2 块匹配准则8 2.2.3 搜索策略8 2.3 典型的块匹配算法.9 2.4 各模块拟采用的算法15 3 3人群运动估计的块匹配算法实现人群运动估计的块匹配算法实现1616 3.1 实现工具 OPENCV16 3.2 CXCORE.H17 3.2.1 CvPoint,CvSize.17 3

10、.2.2 CvMat.17 3.2.3 IplImage19 3.2.4 其他函数21 3.3 CV.H24 3.3.1 cvCvtColor24 3.3.2 cvSmooth26 3.3.3 cvCalcOpticalFlowBM.27 3.4 HIGHGUI.H28 四川大学本科毕业论文 基于块匹配的人群运动估计 2 3.4.1 CvCapture.28 3.4.2 窗口函数28 3.4.3 cvWaitKey31 3.5 算法实现 .31 3.5.1 图像处理（视频处理）32 3.5.2 块匹配37 3.5.3 过滤非运动的物体39 3.5.4 连线40 3.6 程序算法流程图 .41

11、3.7 程序实现截图 .42 4 4软件的测试软件的测试4545 4.1 测试环境 .45 4.1.1 硬件环境45 4.1.2 软件环境45 4.2 测试步骤 .45 4.2.1 测试总体目标45 4.2.2 测试计划实施步骤45 4.3 测试用例 .45 4.3.1 分支测试45 4.3.2 集成测试55 4.4 测试结果分析 .57 5 5总结和展望总结和展望5858 5.1 工作总结 .58 5.2 心得体会 .58 致致 谢谢6262 附录附录 1 1 程序源代码程序源代码 6363 附录附录 2 2 翻译（原文和译文）翻译（原文和译文） 7676 四川大学本科毕业论文基于块匹配的人

12、群运动估计 1 1绪论绪论 1.1 研究背景研究背景 1.1.1智能监控智能监控 随着视频分析技术和人工智能技术的发展，智能视频监控已成为一个非常活跃的研 究领域，它涉及信号分析、图像处理、计算机视觉、机器学习、模式识别等多门学科， 主要研究图像序列中感兴趣目标的检测、跟踪、行为分析与识别等问题。目前，智能监 控的研究大多集中于少数目标个体上。如对单个人的检测、跟踪、行为识别，对车辆的 监控，以及人和车辆的交互行为等。 智能化人群监控是智能视频监控研究中的一个重要课题，它作为智能监控中的一项 关键技术，在人群管理、公共场所设计、虚拟环境建模、视觉监控、智能环境模拟等方 面都有着重要的应用价值1

13、。 1.1.2人群监控的提出人群监控的提出 随着社会的发展，公共安全需求的提高，群体运动分析受到越来越多人的关注,美国 人口普查局在 08 年的一份报告中指出，1999 年，世界人口达到 60 亿，比 1960 年翻了一 倍。08 年全球人口已达到 67 亿，预计到 2050 年，全球人口将超过 90 亿。随着人口的增 加，人群活动日益增加，相对应地，人群安全问题也越来越突出，对人群的分析研究分 别在社会学、心理学、建筑学、计算机等各个学科受到了极大的关注。 现代社会，伴随经济的发展 ,各种高层建筑、地下建筑和大型商业娱乐设施也越来越 多 ,同时出入或围绕这些建筑物的人群也在加大，一旦拥挤人群

14、发生突发事件,容易造成 群死群伤事故，因此必须考虑到人群的安全问题。人们经过探索，最终提出了人群监控 这一技术2。 人群监控是借助于数字图像处理技术对某一区域的人群进行监控,它在社会生活和生 产的许多领域有着广阔的应用前景3。 传统的人群监控通过监控场景所安装的闭路电视进行人工监控，费时费力且缺乏实 时性，不能做到每时每刻监控，且比较主观，不能做定量判断，起不到预防的作用且容 易发生漏报现象。随着智能化技术的发展，智能化的人群监控技术已成为研究的热点。 现代数字图像处理技术的发展 ,为解决上述问题提供了途径。将图像处理、模式识别、 计算机视觉等技术应用在人群监控中 ,可以达到对人群的自动、客观

15、、实时、定量分析。 自智能化人群监控技术提出以后 ,人们对其进行了广泛研究 ,目前已有许多算法 ,一些实 用的系统也开始应用在广场、车站等场合的人流监控中。 四川大学本科毕业论文 基于块匹配的人群运动估计 2 人群监控分为人群密度估计和人群运动估计，本文着手解决人群运动估计。 1.1.3运动估计运动估计 考虑到人群密度和运动的自动监测量和以及智能检测人群分布和流量的重要性，需 要一个不管在人群密度大或小都能正常测量的新技术，但是这是一个困难的问题，因为 在视频显示人群中，通常只会出现一部分人，重叠现象很严重4。 从而分别提出了密度估计法与运动估计法这两类技术。 密度估计法提出一种纹理法分析法，

16、它可以在重叠现象严重的视频中进行较精确的 估计5，这里略过。 运动估计法的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏 块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据 一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为 运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块。 运动估计和运动补偿是 AVS 中去除时间冗余的主要方法，作为视频压缩编码系统的 核心算法，占整个系统运算量的60%-80%，它采用多种宏块划分方式，1P4 像素插值、双 向估计和多参考帧等技术大大提高了编码效率，但同时也给编解码器

17、增加了一定的复杂度。 运动估计算法是视频压缩编码的核心算法之一。高质量的运动估计算法是高效视频 编码的前提和基础。其中块匹配法（BMA, Block Match Algorithm）由于算法简单和易于 硬件实现，被广泛应用于各视频编码标准中。 1.1.4块匹配算法块匹配算法 块匹配法的基本思想是先将图像划分为许多子块，然后对当前帧中的每一块根据一 定的匹配准则在相邻帧中找出当前块的匹配块，由此得到两者的相对位移，即当前块的 运动矢量。在 H.264 标准的搜索算法中，图像序列的当前帧被划分成互不重叠 1616 大 小的子块，而每个子块又可划分成更小的子块，当前子块按一定的块匹配准则在参考帧 中

18、对应位置的一定搜索范围内寻找最佳匹配块，由此得到运动矢量和匹配误差。运动估 计的估计精度和运算复杂度取决于搜索策略和块匹配准则。这里使用 H.264 推荐算法 UMHexagonS（Unsymmetrical-cross Multi-Hexagon-grid Search）作为 DSP 实现的算法参 考，与 FS 算法比较，它在保证可靠搜索精度的前提下大幅降低搜索复杂度。同时使用绝 对差和（SAD, the Sum of Absolute Difference）标准作为匹配准则，它具有便于硬件实现 的优点。 四川大学本科毕业论文基于块匹配的人群运动估计 3 1.1.5OpenCV 计算机视觉是

19、在图像处理的基础上发展起来的新兴学科，OpenCV(Open Source Computer Vision Library，开源计算机视觉库) 是一种数字图像处理和计算机视觉的函数库，它 是一个跨平台的开源计算机视觉库，最初由 Intel 公司微处理器实验室(IntelS Microprocessor Research Lab)的视觉交互组(The Visual Inter-activity Group)开发6，是 Intel 资助的两大图像处理 利器之一，以 BSD 许可证授权发行，可免费用于商业和研究领域，它可以在 Windows 系统、 Linux 系统、Mac0Sx 系统等操作平台上使

20、用，也可以和其他编程工具结合，以满足不同的使用要求。 它包含许多常用的算法，为图像处理、模式识别、三维重建、物体跟踪、机器学习和线 性代数提供了各种各样的算法7。它已经广泛应用于对实时性要求较高的计算机视觉和模 式识别系统的开发。截至 2009 年 8 月，在 的下载次数已经超过 2 200 000 次，大量用户来自中国。 1.1.6论文工作构思论文工作构思 关于人群运动估计，本文用到的方法是块匹配，工具有 OpenCV 和 vc6，程序用 C 和 C+编写。 为了更好的进行人群运动估计，前期准备必不可少， 1. 学习图像处理的基本原理，了解人群监控的意义，采集若干组实验用视频序列； 2.

21、了解现有图像处理的运动估计方法，学习 OpenCV 视频处理的基本知识，掌握块 匹配的主要方法，利用 OpenCV 实现块匹配的原理和技术。 完成以上两点后，利用 C 和 C+编写程序实现功能。 1.2 国内外研究与技术现状国内外研究与技术现状 1.2.1智能人群监控的研究现状智能人群监控的研究现状 目前，国内的安全防范工作中，智能人群估计领域基本还是一项空白，相关的文献 和技术资料很少，基础理论和相关技术不多，没有成熟的产品，国外在人群运动分析方 面研究较多。本文的研究对象是运动群体(这里的群体特指人群)，研究内容是运动人群的 运动估计。 传统的保障人群安全的途径主要有: 人群的密度估计与运

22、动估计 采用物理方法修正建筑物。在一些容易发生人群聚集的地方，采取适当地修正现 有建筑物的方法，比如在人多的地方增加出入口等。 四川大学本科毕业论文 基于块匹配的人群运动估计 4 利用闭路电视监控某一场景。闭路电视对周围环境进行例行地扫描来查找发生危 险的地方，并有专门的工作人员盯着屏幕，以便发生情况及时通报并采取措施。 但是这样做主要有如下缺点: 不能起到预防的作用。即使人可以根据经验来发出危险警告，但由于人的主观性 太强，很容易发生预告太晚或者错误预告的情况。 易造成漏报。 当人群己经发生拥塞时，一般采取的方法是:关闭人群正在大量涌入的入口。这种方 法虽然解决了建筑物某个入口处的拥挤问题，

23、但是人群很可能又涌向别的入口造成新的 拥挤。所以这种做法往往不能从根本上解决问题。 近年来，对人群的研究越来越引起人们的关注，对人群状态和行为的研究也越来越 多，而人群研究的前提是要弄清如何对人群进行适当的描述。虽然人群由独立个体组成， 而每一个个体又有他自己的行为模式，但作为总体的人群有它整体性的特征，且可被描 述出来。要想用精确的数学模型来描述人群的状态和行为非常困难，但我们仍然看到了 一些能够逼近人群真实行为的数学模型的出现，如 stliiG.K.的人群动力学，Corwd Dynamic Limted 公司依据 StlilG.K.的数学模型应用 AuotCAD 做出了一些建筑设施的设计

24、方案。 1.2.2运动估计方法的研究现状运动估计方法的研究现状 作为视频编码器中计算量最大的一个模块，运动估计能够有效地减少帧问相关性， 因此被广泛用于各种视频编码标准中，如 MPEG-1、MPEG-2、MPEG- 4、H26l、H263 和 H264/AVC 等8。 人群运动估计的传统方法是人工估计，但这种方法比较主观，不能做定量判断。二 十世纪以来，人群人群密度和运动估计的自动方法逐渐发展起来。在密度估计上主要有 Davies，Chow，Marana 等人的方法；在运动估计上主要有 Rourke 等人的方法。这些方法 各有不足。Davies 和 Chow 的方法在人群密度较高时，由于人群遮

25、挡现象，测量值与人群 人数之间的线性关系消失，导致误差很大，且这些方法要求提供场景的背景图像。 Marana 的方法虽然可以解决高密度人群的估计问题，但计算量较大，处理时间较长，而 且该方法没有考虑摄像机透视效应问题。Rourke 等人的人群运动估计的方法都限于低密 度人群，如果人群密度较高，出现个体间的相互遮挡使得个体信息提取不全对，就会遇 到困难9。 1.2.3块匹配现状块匹配现状 四川大学本科毕业论文基于块匹配的人群运动估计 5 在主流视频压缩标准(如 H.26x，MPEG 系列等)中，视频系统编码器的效率主要取决 于运动估计算法，而运动估计的效率主要体现在图像质量、压缩码率和搜索速度

26、3 个方 面10， 这些由采用的搜索策略、匹配准则和初始搜索点的选择等因素决定。块匹配运动 估计算法算法简单，便于 VLSI 实现，被广泛应用。目前，其研究主要集中在： 1)利用不同帧相同位置块和相同帧内相邻块运动矢量的相关性，从同帧中左上、上、 左等块的运动矢量及前一帧或前几帧相同位置块的运动矢量中挑选出当前块运动矢量的 最优初始值 然后再按照某一种算法进行搜索； 2)不断改进运动估计匹配模板的形状和大小，旨在减少搜索点数，从而减少搜索时间， 提高编码速度； 3)通过数学不等式来改进目标函数，通过判断提前结束搜索，达到节约运算量和运算 时间的目的。其中第 2 点通过改进模板的方法来减少搜索点

27、数更是当前的研究热点，出 现了许多算法。研究方向。 1.3 论文主要工作论文主要工作 在视频运动估计方面，相关技术比较多，也比较成熟，而在人群运动估计方面，主 流技术则显得较不成熟，各种算法层出不穷，用得最多的只有几种，其中关键就在于对 时间性和空间性的要求，随着科学技术的发展，对这两点的要求已不再那么强烈，注意 力已转移到性能上，一般来说，性能越好，算法越复杂，而 OpenCV 作为一个开源视觉 库，全部由 C 语言写就，因此，这是一个十分强大的图像视觉处理工具，对细微处的处 理很好，其功能接口都为函数，程序员只需调用函数便可完成一系列高效高质量的操作。 而本程序在人群运动估计这一方面运用了

28、一种全新的处理方法，即利用 OpenCV 完成块 匹配法运动估计，其真正达到了高性能高密度。 1.4 论文组织与结构论文组织与结构 第 1 章：绪论。主要介绍了人群监控发展和应用，以及本论文的研究背景和研究工 作，利用 OpenCV 实现基于块匹配的人群运动估计的设计目的； 第 2 章：块匹配法各模块算法背景与分析。介绍运动估计，把块匹配法分为各个模 块，并对其算法进行介绍与分析，同时在最后得出各个模块最合适的算法； 第 3 章：算法分析与设计。说明运动估计视频处理的各个步骤所需处理，并分析处 理所需算法，介绍背景建模； 第 4 章：算法的实现。介绍实现该算法的工具，并对程序各模块一一实现；

29、第 5 章：算法的验证和评价。对算法进行测试，对结果进行分析； 四川大学本科毕业论文 基于块匹配的人群运动估计 6 第 6 章：结论。本章对全文工作以及毕业收获进行总结，指出了还需改进的地方。 2块匹配算法介绍及分析块匹配算法介绍及分析 本章主要介绍块匹配算法的各个模块，及各模块所用到的算法。 2.1 运动估计运动估计 运动估计已发展得较为成熟，最常用于人群监控与视频压缩编码。 基于块的运动估计和补偿是视频编码中最通用的算法。它把图像域分割成互相不重 叠的称为块的小区域，并且假定每一个块内的运动都可以用一个简单的参数模型特征化， 如果快足够小，那么这种模型是相当合理的。目前这种方法被广泛用于视

30、频标准变换运 动补偿滤波和采用基于块的运动补偿进行的数字视频压缩 1112 。 在一幅幅复杂的人群图像中，如果依靠每个步行者的个体信息来估计人群总体的运 动，必须要分离出每个个体的运动。但要做到这点并不容易，因为在开放的空间中，一 个步行者可能向各个方向移动，且步行者的身体各部分的移动方式也各不相同，进而， 当人群密度较大，个体之间有相互遮挡时，这就变得更加困难，甚至是不可能的。因此， 本文提出基于块匹配的人群运动估计（BMA） 。这种方法由于实现较简单且容易而受到广 泛关注。BMA 并不借助人群中个体的信息，而是通过统计视频中各宏块的运动矢量估计 出人群整体的运动 13 。 2.2 块匹配基

31、本思想块匹配基本思想 基于块匹配法的运动估计的基本思想就是将当前帧分成互不重叠的大小为 MN 的宏 块(一般情况下 M=N)，然后对当前帧中的每一个块都在参考帧中的一定区域，即搜索窗 口内，按照一定的匹配准则搜索与之具有最小匹配误差的块(Minimal DistortionBlock，MDB)，该块即为当前块的匹配块，由匹配块与当前块的相应位置计算 出运动位移，所得运动位移即为当前块的运动矢量。并且假定每一个块内的运动只做相 等的平移同时可以用一个简单的参数模型特征化。如果块足够小，那么这种模型是相当 合理的。匹配块与当前块之间的坐标位移就是运动矢量，匹配块与当前块的对应象素点 逐个做差就的到

32、差值块。基于这样的方法这样，当前帧中的每一个块都可以用一个差值 块和一个运动矢量来表示，对当前帧的编码就转化为对每一块的差值块和运动矢量的编 码。 四川大学本科毕业论文基于块匹配的人群运动估计 7 块匹配的原理如图 2-1。运动估计算法的整体效率主要体现在初始搜索点的选择、匹 配准则和运动搜索策略三个方面。本程序主要用基于块的运动方式开发出的运动估计算 法块匹配算法。块匹配算法由于它具有较少的硬件复杂度，容易在超大规模集成电 路中实现，因此被认为是最通用的算法。 图 2-1 块匹配原理图 为了提高图像质量，加快估计速度是运动估计算法的研究目标之一。通常是通过研 究初始搜索点的选择、匹配准则和运

33、动搜索策略等来提高算法效率的13。 2.2.1 初始搜索点的选择初始搜索点的选择 (1)直接选择参考帧对应块的中心位置。这种方法简单，但容易陷入局部最优点。如 果采用的算法初始步长太大，而原点(以下均指待搜索块的中心点在参考帧中的相同位置 的对应点，而不是坐标位置的真正原点)又不是最优点，有可能使快速搜索跳出原人群的 运动估计点周围的区域(这些区域可能包含最优点)而去搜索远距离的点，导致搜索方向的 不确定性，这就有可能陷入局部最优。 (2)选择预测的起点。由于相邻块之间和相邻帧之间具有很强的相关性，因而许多算 法都利用这种相关性先对初始搜索点进行预测，以预测点作为搜索起点。大量实验证明 预测点

34、越靠近最优匹配点，越会使得搜索次数减少。 下面举例说明几种常见的预测方法。 方法方法 1:基于 SAD(the Sum of Absolute Differences)值的起点预测方法。分别求出当前 块与其相邻块间的 SAD 值，然后选取 SAD 最小的块的运动矢量作为预测值。这种方法 预测精度高，但计算 SAD 值的时间开销大。改进的方法是利用运动矢量的相关性来预测 起点。 方法方法 2:利用相邻块和相邻帧对应块的运动矢量来预测当前块的搜索起点。序列图像 的运动矢量在空间、时间上具有很强的相关性。由于保存前一帧运动矢量信息在解码端 四川大学本科毕业论文 基于块匹配的人群运动估计 8 需要占用

35、大量内存，使得系统复杂化，故大多算法仅考虑同帧块的空间相关性来预测运 动。比较典型的是“平均预测”，在 H.263 中使用三个相邻块的运动矢量的中值作为当前块 的运动矢量的预测值。 方法方法 3:基于相邻运动矢量相等的起点预测方法。如果当前块的各相邻块的运动矢量 相等，则以其作为当前块运动矢量的预测值;否则，使用方法 1 求出当前块与其相邻块间 的 SAD 值，然后选取 SAD 值最小的块作为预测起点。这种方法在保证精度的基础上利 用运动矢量相关性从而大大减少了计算量。 运动估计的复杂度主要取决于匹配计算量和所采用的搜索算法这两个方面14。在下 一节中将介绍在运动估计常用的一些匹配准则。 2.

36、2.2 块匹配准则块匹配准则 运动估计算法中常用的匹配准则有三种，即最小绝对值差(MAD)、最小均方误差 (MSE)和归一化互相关函数(NCCF)，它们分别定义如下: (1) 最小绝对值差: （1） 式中，B 代表 MN 宏块，(dx,dy)为运动矢量，fk与 fk-1分别为当前帧和前一帧 的灰度值，若在某一个点(x，y)处 MAD(dx,dy)达到最小，则该点为要找的最优匹配点。 若在某一个点(x,y)处 MAD(dx,dy)达到最小，则该点为要找的最优匹配点。 (2)最小均方误差: （2） 能够使 MSE 值最小的点为最优匹配点。 (3)归一化互相关函数： （3） 式中 NCCF 的最大值

37、点为最优匹配点。在运动估计中，匹配准则对匹配的精度影 四川大学本科毕业论文基于块匹配的人群运动估计 9 响不是很大，由于 MAD 准则不需要作乘法运算，实现简单、方便，所以使用最多， 通常使用 ASD 代替 MAD。SAD 即求和绝对误差，其定义如下: （4） 2.2.3 搜索策略搜索策略 搜索策论选择恰当与否对运动估计的准确性，运动估计的速度有很大的影响。有 关搜索策略的研究主要是解决运动估计中存在的计算复杂度和搜索精度这一矛盾。如 全搜索法，它对搜索范围内的每一个像素点进行块匹配运算以得到一个最优的运动矢 量。不过，较大的搜索窗通常会使得搜索点增多，从而加大计算量，因此，搜索距离 的设定需

38、综合考虑具体视频的运动特性、运动估计的质量以及算法的计算量等因素， 以获得最佳的估计性能15。另外三步法、二维对数法、交叉法等主要是通过限制搜索 位置的数目来减少计算量。这以后的许多搜多策略都是为了平衡搜索精度与计算速度 而产生的。 2.3 典型的块匹配算法典型的块匹配算法 在 MPEG2-4 视频编码算法中，运动估计(ME)的计算量占整个编码计算量的 2/3 以上16。在视频编码系统中，运动估计处理消耗近 50%的功耗16。为了减小运动估 计计算量，出现了各种块匹配算法，它们只是搜索策略各有不同，其中搜索精度最高 的是全搜索法，但由于计算复杂度高，不宜于实时应用，为此人们提出了各种改进的 快

39、速算法。下面介绍几种常用的经典算法。 (l)全搜索法全搜索法(FS，Full Seacrh method) 算法思想:全搜索法也称为穷尽搜索法，或螺旋向外搜索法，是对搜索范围内所 有可能的候选位置计算其 SAD(i，j)值，从中找出最小 SAD，其对应偏移量即为所求 运动矢量。此算法计算量虽大，但最简单，可靠，找到一定是全局的最优点。 算法描述: Setpl:从原点出发，按顺时针方向由近及远，在每个像素处计算 SAD 值，直到遍 历搜索范围内的所有点。 StPe2:在所有的 SAD 中找到最小块误差(MBD)点(即 SAD 最小值的点)，该点所在 位置即对应的最佳运动矢量。 模板及搜索过程图示

40、:如图 2-2 所示。 四川大学本科毕业论文 基于块匹配的人群运动估计 10 图 2-2 全搜索法搜索过程 算法分析:FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全 局最优的结果，通常是其它算法性能比较的标准，但它的计算量很大，这就限制了在 需要实时性较强的场合的应用，所以有必要进一步研究其它快速算法。 (2)二维对数法二维对数法(TDL，Two-Dimensional Logarithmic) 二维对数搜索法由 J.R.Jain 和 A.K.Jaini 提出，它开创了快速算法的先例，分多个 阶段搜索，逐次减小搜索范围直到不能再小时结束。 基本思想:二维对数搜索法是由原点开始，

41、以“十”字形分布的五个点构成每次搜 索的点群，通过快速搜索跟踪加 MBD 点。 算法描述: Step 1:从原点开始，选取一定的步长，在以“十”字形分布的五个点处进行块匹配 计算并比较。 Step 2:若 MBD 点在边缘四个点处，则以该点做为中心点，保持步长不变，重新 搜索“十”字形分布的五个点;若为 MBD 点位于中心点，则保持中心点位置不变，将步 长减半，构成“十”字形点群，在五个点处计算。 Step 3:若步长为 1，在中心及周围 8 个点处找出 MBD 点，该点所在位置即对应 最佳运动矢量，算法结束;否则，重复 Step 2。 搜索过程图示:如图 2-3 所示。 算法分析:TDL 算

42、法搜索时，最大搜索点数为 2+7lbW，这里 W 表示最大偏移量 max(dxmax,dymax)。若发现新的“十”字形点群的中心点位于搜索区域的边缘，则步长 也减半。后来有人提出应该在搜索的每个阶段都将步长减半。所有这些改动都是为了 使算法搜索范围很快变小，提高收敛速度。TDL 算法的前提是假设搜索区域内只有一 个极小值点，如果搜索区域内存在多个极小值点时，该方法找到的可能是局部最小点。 不能保证找到全局最优点也正是大部分快速搜索算法的缺点。 四川大学本科毕业论文基于块匹配的人群运动估计 11 图 2-3 二维对数法过程 (3)三步搜索法三步搜索法(TSS，而，而 Three Step Se

43、arch) 三步搜索法与 TDL 类似，由于其简单、健壮、性能良好的特点，已被人们所重视。 若最大搜索长度为 7，搜索精度取 1 个像素，则步长为 4、2、1，共需要三步即可满 足。 基本思想:TSS 算法的基本思想是采用一种由粗到细的搜索模式，从原点开始， 按一定步长取周围 8 个点构成每次搜索的点群，然后进行匹配运算，跟踪最小块误差 MBD 点。. 算法描述: Step 1:从原点开始，选取最大搜索长度的一半为步长，在中心点及周围 8 个点处 进行块匹配计算并比较。 Step 2:将步长减半，中心移到上一步的 MBD 点，重新在中心点及周围的 8 个点 处进行块匹配计算并比较。 Step

44、3:在中心点及周围 8 个点处找出加 MBD 点，若步长为 1，该点所在位置即对 应最佳运动矢量，算法结束;否则，重复 Step 2。 搜索过程图示:一个可能的搜索过程如图 2-4 所示。图 2-4 中点+4，+4、 +6，+4是第一、第二步的最小块误差点。第三步得到最终运动矢量为+7，+5，每 个点上的数字表明了每个阶段搜索时计算的候选块的位置。 四川大学本科毕业论文 基于块匹配的人群运动估计 12 图 2-4 三步搜索法搜索过程 算法分析:TSS 算法搜索时，整个过程采用了统一的搜索模板，使得第一步的步 长过大，容易引起误导，因此对小运动模式的效率较低。最大搜索点数为 1+8blW， 当搜

45、索范围大于 7 时，仅用三步是不够的，搜索步数的一般表达式为 lb(dmax+1). (4)交叉法交叉法(CSA，Cross Search Algorithm) 1990 年，Chanbari 提出了交叉搜索算法，它也是在 TDL 和 TSS 基础上为进一步 减小计算量而发展起来的快速搜索法。 本思想:CSA 是从原点开始，以“”字形分布的五个点构成每次搜索的点群，以 TDL 的搜索方法检测为 MBD 点，仅在最后一步采用“十”字形点群。 算法描述: Step l:从原点开始，选取最大搜索长度的一半为步长，在以“”字形分布的五个点 处进行块匹配计算并比较，然后移动中心点。 Step 2:以上一

46、步的 MBD 点为中心点，步长减半，继续进行“”字形的五点搜索。 若步长大于 1，则重复 Step 2;若步长为 1，则进行 Step 3。 Step 3:最后一步根据为 MBD 点的位置，分别进行“十”字形和“”字形搜索。若上 一步 MBD 点处于中心点、左下角或右上角，则做“十”字形搜索;若上一步 MBD 点处 于左上角或右下角，则做“”字形搜索。由当前为 MBD 点得到的最佳运动矢量，算法 结束。 搜索过程图示:图 2-5 是 CSA 搜索的一个具体实例。图中每个点上的数字表明 了每个阶段搜索时计算的候选块的位置，点+4，+4、+6，+21是第一、第二步搜索 的 MBD 点。第三步箭头说

47、明了两种不同的搜索模式。 算法分析:CSA 的最大搜索点数为 5+4lbW，搜索速度很快，但是运动补偿的效 果不是太好。在搜索区域的边界上有四分之一的点 CSA 没有考虑到，因此它不适用于 较复杂的运动模式。 图 2-5 交叉法搜索过程 四川大学本科毕业论文基于块匹配的人群运动估计 13 (5)四步搜索法四步搜索法(FSS，Four Step Search) 四步搜索法是 1996 年由 Lai 一 man Po。和 Wing-Chung Ma 提出的，该算法类似 三步法，但它基于现实中序列图像的一个特征，即运动矢量大多都是中心分布的，从 而在 55 大小的搜索窗口上构造了有 9 个检测点的搜

48、索模板。 本思想:TSS 算法第一步用了 99 的搜索窗，这很容易造成搜索方向的偏离，FSS 算法首先采用 55 的搜索窗口，每一步搜索窗的中心移向 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:将窗口缩小到 33，这时计算出最小误差点的位置即对应最佳运动矢量， 如图 2-6d 所示。 图 2-6 四步搜索法的搜索模块（a,b,c,d） 搜索过程图示:图 2-7 是 FSS 搜索的一个具体实例。首先搜索点0，2，由于该 点处于边的中心点处，故采用图 2-6c 的模板进行搜索，结果为2，4;由于该点处于搜 索窗的角上，故用图 2-