MPEG4视频编码算法的研究与实现

MPGE4 编码算法

国防科学技术大学

硕士学位论文

MPEG4视频编码算法的研究与实现

姓名：沈承东

申请学位级别：硕士

专业：计算机科学与技术

指导教师：谭庆平

2002.1.1

MPGE4 编码算法

国防科学技术大学研究生院学位论文

摘要

／多媒体技术正在迅速发展．应用领域不断拓广。与之相适应，各种多媒体数据压缩编码标准也在不断地发展和完善。ＭＰＥＧ４是现在最重要最有影响的多媒体数据压缩编码国际标准之一。基于对象的编码思想使其具有高压缩比、可扩展性、可交互性等许多优点。ＭＰＥＧ４代表着未来多媒体数据压缩编码的发展趋势。Ｌ尸一

本文的实际应用背景是实现一个基于ＭＰＥＧ４标准的远程视频监控系统／远程视频监控要求对视频图像进行实时的压缩编码以及根据网络状况自适应地对压缩视频流进行流化传输，因此视｛够鳗码器必须能够进行快速的编码和比特率控制。基于上面的背景厂本文第一部分针对ＭＰＥＧ４标准的核心部分一一视频的压缩编码进行了两方面的重点研究。ｆ首先在对传统的运动估计算法进行研究和改进的基础上，提出了四步搜索块匹配的运动估计算法，减少了运动估计的时间，提高了编码效率；其次在分析ＭＰＥＧ２比特率控制的基础上，提出了～种新的比特率控制算法——平均响应比特率控制算法，该算法能够快速有效的实现自适应编码。ｌ，，ｙ一

本文的第二部分以上面的研究成果为基础，结合ＰｒｏｊｅｃｔＭａｙｏ组织提供的视频压缩基本算法的实现代码，完成ＭＰＥＧ４视频编码器和解码器原型的软件实现，为远程视频监控系统的实现奠定基础。同时，为了将视频编码器和解码器原型更好的用于远程视频监控系统，本文提出了对原型进一步改进的方法，即在对视频图像压缩编码之前加入运动检测的预处理过程，从而进一步提高编码效率。

（另外，本文对ＭＰＥＧ４标准中静态Ｓｐｒｉｔｅ对象的生成和编码方法做了比较深入的研究，为将其用于背景图像变化少的一类问题的应用奠定了一定的理论基础。ｌ夕“一

关键词ＭＰＥＧ４‘视频压缩》视频监控￥震翥娇野ｒ１豳争翻馨盯１甄蕃专节衬固／’’一—————————————————７＜￡，、一

MPGE4 编码算法

国防科学技术大学研究生院学位论文

Ａｂｓｔｒａｃｔ

Ｒｅｓｐｏｎｄｉｎｇｔｏｍｕｌｔｉｍｅｄｉａｔｅｃｈｎｏｌｏｇｙｒａｐｉｄｌｙｄｅｖｅｌｏｐｉｎｇａｎｄａｐｐｌｉｃａｔｉｏｎｄｏｍａｉｎｐｒｏｍｐｔｌｙｅｎｌａｒｇｉｎｇ，ｍａｎｙｍｕｌｔｉｍｅｄｉａｃｏｍｐｒｅｓｓｉｏｎａｎｄｃｏｄｉｎｇｓｔａｎｄａｒｄｓｐｒｏｇｒｅｓｓａｎｄｐｅｒｆｅｃｔ

ａｎｃｏｎｔｉｎｕｏｕｓｌｙ．Ａｍｏｎｇｔｈｅｍ，ＭＰＥＧ４ｐｌａｙｓ

ｉｔ’ｓｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｔｈｅｍｕｌｔｉｍｅｄｉａｆｉｅｌｄ．Ｄｕｅｔｏｏｂｊｅｃｔ ｂａｓｅｄｉｄｅａ，ｉｔｈａｓｔｈｅ

ｕｓｅｒｓｖｉｒｔｕｅｏｆｈｉｇｈｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏ，ｓｃａｌａｂｉｌｉｔｙ，ｉｎｔｅｒ—ａｃｔｉｖｉｔｙｗｉｔｈａｎｄｓｏｏｎ．Ｆｏｒｔｈｉｓｒｅａｓｏｎ，ＭＰＥＧ４ｉｎｄｉｃａｔｅｓｔｈｅｔｅｎｄｅｎｃｙｏｆｔｈｅｍｕｌｔｉｍｅｄｉａｃｏｍｐｒｅｓｓｉｏｎａｎｄｃｏｄｉｎｇｔｅｃｈｎｉｑｕｅ．

Ｂａｓｅｄｔｈｅｒｅｓｅａｒｃｈｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｒｅｍｏｔｅｖｉｄｅｏｓｕｒｖｅｉｌｌａｎｃｅｗｈｉｃｈｍａｋｅｓｒｅａｌ．ｔｉｍｅａｎｄａｄａｐｔｉｖｅｃｏｍｐｒｅｓｓｉｏｎａｎｄｓｔｒｅａｍｉｎｇｖｉｄｅｏｓｅｑｕｅｎｃｅｎｅｃｅｓｓａｒｙ，ｔｈｉｓｐａｐｅｒｆｉｒｓｔｄｏｅｓｔｈｅ

ｉｓｔｈｅｈａｒｄｃｏｒｅｐａｒｔｏｆｄｅｅｐｒｅｓｅａｒｃｈＯＢｖｉｄｅｏｃｏｍｐｒｅｓｓｉｏｎａｎｄｃｏｄｉｎｇｗｈｉｃｈＭＰＥＧ４ｍａｉｎｌｙ

ｆｒｏｍｔｗｏｆａｃｅｔｓ．Ｔｈｅｆｉｒｓｔｆａｃｅｔｉｓｔｏｐｕｔｆｏｒｗａｒｄｆｏｕｒ－ｓｔｅｐｂｌｏｃｋｍａｔｃｈｉｎｇａｌｇｏｒｉｔｈｍｗｈｉｃｈｃａｎｄｅｄｕｃｅｔｈｅｔｉｍｅｏｆｍｏｔｉｏｎｅｓｔｉｍａｔｉｏｎａｎｄｉｍｐｒｏｖｅｔｈｅｃｏｄｉｎｇｅｆｆｉｃｉｅｎｃｙ，ｂａｓｅｄ

ａｏｎｔｈｅｔｒａｄｉｔｉｏｎａｌｍｏｔｉｏｎｅｓｔｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｓｅｃｏｎｄｆａｃｅｔｉｓｔｏｐｒｏｐｏｓｅ

ａｌｇｏｒｉｔｈｍ，ｔｈａｔｉｓａｖｅｒａｇｅ—ｒｅａｃｔｉｏｎｒａｔｅｃｏｎｔｒｏｌａｌｇｏｒｉｔｈｍ，ｂａｓｅｄ

１１１ｅｎｅｗｒａｔｅｃｏｎｔｒｏｌ

ＢａｓｅｄｏｎｏｎｎｅｗｒａｔｅｃｏｎｔｒｏｌｔｈｅｒａｔｅｃｏｎｔｒｏｌｏｆＭＰＥＧ２ａｌｇｏｒｉｔｈｍｃａｎａｃｈｉｅｖｅｒａｐｉｄａｎｄｅｆｆｉｃｉｅｎｔａｄａｐｔｉｖｅｃｏｄｉｎｇａｎｄｔｈｅｓｏｕｒｃｅｃｏｄｅｓｐｒｏｖｉｄｅｄｂｙｔｈｅｂａｓｉｃａｌｇｏｒｉｔｈｍｓｏｆｔｈｅａｂｏｖｅｒｅｓｅａｒｃｈ

ｖｉｄｅｏｃｏｄｉｎｇｐｒｏｖｉｄｅｄｂｙｔｈｅｏｒｇａｎｉｚａｔｉｏｎｏｆ

ｐｒｏｔｏｔｙｐｅｏｆｖｉｄｅｏｅｎｃｏｄｅｒ

ｏｎＰｒｏｊｅｉｃｔＭａｙｏａｎｄＭＰＥＧ４，ｗｅｉｍｐｌｅｍｅｎｔｔｈｅａｎｄｄｅｃｏｄｅｒ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｉｓｐａｐｅｒｄｏｅｓｓｏｍｅｉｍｐｒｏｖｅｍｅｎｔｔｈｅｐｒｏｔｏｔｙｐｅｓｏａｓｔｏｍａｋｅｉｔｂｅｕｓｅｄｉｎｔｈｅｒｅｍｏｔｅｖｉｄｅｏｓｕｒｖｅｉｌｌａｎｃｅｍｏｒｅｐｒｏｐｅｒｌｙＴｈｅ

ｔｏｉｍｐｒｏｖｅｍｅｎｔｍｅｔｈｏｄｗｈｉｃｈｃａｎａｃｈｉｅｖｅｈｉｇｈｅｒｅｎｃｏｄｉｎｇｅｆｆｉｃｉｅｎｃｙｉｓ

ｏｆｍｏｔｉｏｎｄｅｔｅｃｔｉｏｎｂｅｆｏｒｅｔｈｅｅｎｃｏｄｉｎｇｏｆｔｈｅｖｉｄｅｏｐｉｃｔｕｒｅｓ．ａｄｄｔｈｅｐｒｅｔｒｅａｔｍｅｎｔ

Ｆｉｎａｌｌｙ，ｔｈｉｓｐａｐｅｒｄｏｅｓｄｅｅｐｒｅｓｅａｒｃｈｏｎｔｈｅｓｔａｔｉｃＳｐｒｉｔｅｏｂｊｅｃｔｉｎＭＰＥＧ４．Ｉｔｗｉｌｌｂｅｔｈｅ

ｎｏｔｈｅｏｒｙｂａｓｉｓｏｆｔｈｅｓｐｅｃｉａｌａｐｐｌｉｃａｔｉｏｎｓｉｎｗｈｉｃｈｔｈｅｂａｃｋｇｒｏｕｎｄｏｆｖｉｄｅｏｐｉｃｔｕｒｅｓｄｏｅｓ

ｒａｐｉｄｍｏｔｉｏｎｓ．

Ｋｅｙｗｏｒｄ：ＭＰＥＧ４，ｖｉｄｅｏｃｏｍｐｒｅｓｓｉｏｎ，ｖｉｄｅｏｓｕｒｖｅｉｌｌａｎｃｅ，ｍｏｔｉｏｎｅｓｔｉｍａｔｉｏｎ．ｂｉｔｒａｔｅｃｏｎｔｒ０１．ｓｔａｔｉｃＳｐｒｉｔｅ

MPGE4 编码算法

国防科学技术大学研究生院学位论文

第１章绪论

§１．１课题的背景、目标和意义

近年来，多媒体技术飞速发展，在社会生活的许多领域得到了广泛的应用。为适应技术发展和应用的要求，各种多媒体数据压缩编码标准也在不断发展。从Ｈ．２６３、ＭＰＥＧｌ到ＭＰＥＧ２，到现在的ＭＰＥＧ４、ＭＰＥＧ７，标准越来越成熟，覆盖的应用领域越来越广。目前发展最迅速、影响最大的多媒体数据压缩编码国际标准是ＭＰＥＧ４。ＭＰＥＧ４标准的全称是音频和视觉对象的通用编码，它是伴随互联网产生和发展起来的。ＭＰＥＧ４定义了多媒体编码和解码、互联网上的传输以及人与媒体交互的一整套框架，涵盖了多媒体的绝大部分应用领域。ＭＰＥＧ４基于对象的编码思想使其具有高压缩比、可扩展性、可交互性等许多优点。ＭＰＥＧ４正在蓬勃发展，代表着未来多媒体数据压缩编码的发展趋势。及时跟踪和了解ＭＰＥＧ４的发展动态，掌握其核心技术，并结合实际应用在某些关键方向上有所创新和发展，是一项很有意义的工作。

本课题结合远程视频监控的实际应用背景，在全面了解ＭＰＥＧ４标准的基础上，抓住ＭＰＥＧ４标准的核心部分——视频的压缩编码进行重点研究。根据远程视频监控的实际特点，研究压缩编码的目标是实现对原始视频源进行实时的压缩编码和网上流化传输，因此，压缩编码的速度和根据网络状况自适应编码是两个最重要的指标。基于此本课题首先对编码中的关键算法——运动估计算法和比特率控制算法进行重点研究、优化和改进，以实现快速的编码和有效的比特率控制：然后完成视频编码器和解码器原型的软件实现：最后研究实际的应用问题，提出了将视频编码和解码器原型用于远程视频监控的优化和改进方法，并完成了相应的软件设计与实现。

本课题的意义在于：研究、改进和实现了ＭＰＥＧ４视频压缩编码的关键算法，掌握了视频压缩编码的核心技术；实现了编码器和解码器的原型，建立了继续研究的测试实验平台，奠定了实际应用和开发的基础；找到了将编码器和解码器原型进行改进以用于远程视频监控的方法。

§１．２课题完成的工作

课题主要完成了以下几个方面的工作。

１对视频编码的关键算法——运动估计算法进行研究和改进，在传统的运动估计算法的基础上，提出并实现了四步搜索块匹配的运动估计算法。实验结果表明，与传统的运动估计算法相比，四步搜索块匹配的运动估计算法的速度更快，精度更高。

２对视频编码的关键算法——比特率控制算法进行研究，在分析ＭＰＥＧ２标准的比特率控制算法的基础上，设计并实现了一种快速和有效的比特率控制算法，称之为平均响应比特率控制算法。实验结果表明，平均响应比特率控制算法能够使编码器具有自适应

MPGE4 编码算法

国防科学技术大学研究生院学位论文

编码的功能ａ

３视频编码器和解码器原型的软件实现。以ＰｒｏｊｅｃｔＭａｙｏ组织提供的部分实现源码为基础，对这些代码进行改进、扩充、移植、整合，实现了一个Ｗｉｎｄｏｗｓ平台下的视频编码器和解码器的原型。实验结果表明，该原型具有较高的编码效率和较好的编码质量。

４将视频编码器和解码器原型实现应用于远程视频监控。在深入分析编码器和解码器软件实现的基础上，根据远程视频监控中背景图像变化不大和运动区域易确定的具体特点，提出了进一步提高编码效率、提高压缩比的改进方法。其基本思路是对视频序列进行预处理，采用分区域递归估计的运动检测方法定位活动区域，然后仅对活动区域进行精确的运动估计和压缩编码。

５结合视频监控、可视电话、视频会议等一类问题的应用背景（这类应用的共同特点是：大部分背景图像不动或运动很少），重点研究了ＭＰＥＧ４中Ｓｐｒｉｔｅ对象的生成和编码技术，为这类问题的实际应用和开发做了理论上的准备。

课题的理论和实现准备工作。首先全面了解了ＭＰＥＧ４这一多媒体编码国际标准，对其基本思想、整体框架、关键技术、涵盖的应用领域等有了完整的认识，奠定了课题开展的初步基础：然后结合ＭＰＥＧ４给出的参考校验模型，以及ＰｒｏｊｅｃｔＭａｙｏ组织提供的ＭＰＥＧ４视频编码和解码算法的部分实现代码，深入剖析了ＭＥＰＧ４视频编码和解码的原理，掌握了量化、离散余弦变换、运动估计与补偿、可变长编码等基本的视频数据压缩编码算法。

§１．３论文的组织结构

论文共分五部分。第一部分是绪论和理论知识准备；第二部分是运动估计与补偿算法、比特率控制算法的研究；第三部分是视频编码器和解码器的软件实现；第四部分是视频编码器和解码器在远程视频监控中的应用、静态Ｓｐｒｉｔｅ生成算法的研究；第五部分是全文总结。全文的内容组织如下：

第１章，绪论，阐述课题背景、目标、意义及完成的工作。

第２章，理论准备，介绍视频压缩及ＭＰＥＧ４标准的基本知识。

第３章，运动估计算法的研究与改进，提出了一种新的运动估计算法，并给出算法的实现方法。

第４章，比特率控制算法的研究与改进，提出了一种简单而有效的比特率控制算法，并给出算法的实现方法。

第５章，ＭＰＥＧ４视频编码器和解码器原型的软件实现。

第７章，ＭＰＥＧ４中静态Ｓｐｒｉｔｅ对象生成和编码算法的研究。

第６章，ＭＰＥＧ４视频编码器和解码器原型在远程视频监控中的应用，提出了结合实际应用背景进一步改进的思路和方法，并给出相应的实现方法。

第８章，总结本文的研究成果，明确了进一步的研究工作和主要方向。

MPGE4 编码算法

里堕型兰垫查奎兰堡窒尘堕兰垡笙兰＝Ｅ≈＝＝＝＝！Ｅ；ｔ＝＝＝＝＝＝ｊ＝＝；＝；＝＝＝＿＝＿Ｅ＝＝｝＝＝Ｅ＝＝＝＝＝ｌ－＿＝—ｉ；———————————————————一一

第２章视频压缩及ＭＰＥＧ４标准简介

§２．１视频信号处理

多媒体技术的～项重要内容即是：利用计算机综合处理声、文、图信息，而其首先需解决的问题应是把声音和视频信息数字化后送到计算机中。视频信号源一般是摄像机、录音机、扫描仪以及视频光盘等，而它们的输出大多数是标准的彩色全电视信号，因此视频信号获取主要是指标准的彩色全电视信号的获取Ｉｌ…。

目前通用的电视标准有ＮＴＳＣ制式、ＰＡＬ制式、ＳＥＣＡＭ制式三种，虽然说这三种制式的信号处理方式不同（如彩色空间、相位处理各不相同），但其视频获取的流程却是一样的，即需要：首先将彩色全电视信号经过采集设备分解成模拟的ＲＧＢ信号或ＹＵＶ信号，然后进行各个分量的Ａ／Ｄ变换、解码，将模拟的ＲＧＢ或ＹＵＶ信号变换为数字的ＲＧＢ信号或ＹＵＶ信号，存入帧存储器，主机可通过总线对帧存储器中的图像数据进行处理，帧存储器中的数字ＲＧＢ或ＹＵＶ信号经过Ｄ／Ａ变换转换成模拟的ＲＧＢ或ＹＵＶ信号，再经编码合成彩色全电视信号，输出到显示器上，其流程如图２．１所示。

图２．１视频获取流程

多数专用多媒体系统利用专用ＩＣ将视频获取部分做在系统主板上，而一般的应用系统常采用配备一块视频卡的方法来实现视频获取。

§２．２视频压缩的必要性及应用前景

在多媒体信息处理中，最基本的需求是能动态实时地处理声音、动画、视频信号，而图像的数据量是十分庞大的，若不对视频数据进行压缩处理，实时性根本就不能达到。例如，针对一幅具有中等分辨率（６４０×４８０）彩色（２４ｂｉｔｓ／ｐｉｘｅｌ）数字视频图像的数据量约７．３７Ｍｂｉｔｓ／帧，帧速率３０帧／秒（ＮＴＳＣ制式），则视频信号的传送速率大约为２２１．１Ｍｂｉｔｓ／ｓ，一分钟的视频表演则需要１３２６６Ｍ以上的硬盘空间。数据量大，难以寻求庞大的存储设备存储这些数据，而且计算机也难以实时地从存储器将这些数据传送到中央处理器，因此，视频数据压缩技术也就成了开发多媒体系统中视频处理的关键技术。

通过对视频数据的分析发现，原始视频数据存在的冗余度为数据压缩的实现提供了可能。首先，对于每帧图像数据存在很大的空间冗余，视频图像帧内邻近象素之间是空域相关的。其次，对于由每秒３０帧组成的视频序列信号，其相继帧之间也具有较强的相

MPGE4 编码算法

国防科学技术大学研究生院学位论文

关性，即存在时间冗余，例如，对于电视中的演讲人图像序列，相邻帧之间可能只有由头部、眼部、嘴部的微小变动而引起的细小差别。再次，因为在多媒体系统的应用领域中，人是主要接收者，眼睛是图像信息的接收端，这样就有可能利用人的视觉对于边缘急剧变化不敏感（视觉掩盖效应）和眼睛对图像的亮度信息敏感、对颜色分辨率弱的特点实现高压缩率，从而使由压缩数据恢复的图像信号仍有满意的主观质量。

一旦优秀的视频压缩技术投入使用，使得在低成本、较低速率要求、有限带宽的条件下得以动态实时地处理高质量的运动图像，它将对社会产生深远的影响并具有广阔的应用领域。多媒体与互联网相结合，使得多媒体通信系统能提供可视通信、远程监控、远程教学、集中图像管理和声像资料联网传输等功能，利用多媒体计算机系统进行教育、训练、演示、咨询、家庭娱乐等，将常规电视数字化及制造高清晰度电视（ＤＨＴＶ）、交互式电视系统等，而当前多媒体市场的繁荣也证实着这种发展前景正一步步向人们走近。

§２．３常用的视频数据压缩技术

数据压缩的分类方法繁多，在这里对分类方法等方面的问题不进行讨论，只讨论在视频压缩技术中涉及到的一些常用数据压缩技术。

§２．３．１预测编码

预测编码是基于统计冗余数据压缩理论的一种编码方法。它是按某一模型利用以往的样本值对新样本进行预测，然后将样本中的实际值与其预测值相减得到一个误差值，并对这一误差值编码，由于误差值远远小于实际值，从而达到压缩数据的目的，预测编码是一种无损压缩。

§２．３．１．１ＤＰＣＭ方法

ＰｕｌｓｅＣｏｄｅＭｏｄｕｌａｔｉｏｎ）实际应用中用的最多的预测编码方法为ＤＰＣＭ（Ｄｅｆｆｅｒｅｎｔｉａｌ

方法【７】【８１，其工作原理为：

假定已有样本值序列Ｘｔ、Ｘ２…．ｘ。．１，预测值为Ｘ。’，实际值为Ｘ。，ｏｉ（ｉ＝ｌ…２．．，ｎ．１）为系数，ｅ。为误差值，则：

ｎ－Ｉ

Ｘｎｌ＝∑ｎ｜Ｘ。

，ｌｌ

ｅ，＝ｘ，一Ｘ？

最优线性预测就是选择预测系数ａｉ（ｉ＝１，２，．，ｎ－１），使“的均方值最小，即联（８：））最小。

在该预测模型的数学推导中发现，预测模型的复杂程度和预测系数的个数有关，也即与预测中使用的样本的数目有关，样本数越少越简单，故一般采用前三点预测或前一点预测，如视频编码帧内ＤＣＴ系数的ＤＣ系数编码即为采用前一点预测（即将其前一个值作为预测值）。

MPGE4 编码算法

国防科学技术大学研究生院学位论文

§２．３．１．２帧间预测

帧间编码技术处理的对象是序列图像（也称为运动图像），它是把几帧的图像存储起来作实时处理，利用帧间的时间相关性进一步消除图像信号的冗余度，提高压缩比，其技术基础是预测技术，这种帧间预测原理的概况如图２．２所示。

图２．２帧间预测

如果是简单帧间预测，则预测误差为：

ｓ＝Ｘ—Ｘｊ

如果是复合差值预测，则预测误差为

占＝（Ｘ—Ｘ’）一（Ａ一４’）

当后帧相对于前帧其图像亮度变化相同时（即ｚ—ｚ’＝（Ｚ—Ｘ。）一（４一Ａｔ）＝占＝０），式中的Ａ可以用任意的帧内预测函数ｆ（Ａ…Ｂ．．）来代替，例如ｆ（Ａ，Ｂ，ｃ）＝Ａ＋Ｂ—Ｃ。

常用的两种帧间预测编码方法为：条件补充法和运动补偿技术【ｌ０１。

ｌ条件补充法

由Ｍｏｕｎｔｓ，Ｐｅａｓｅ等人提出的条件象素补充法规定，若帧间各对应象素的亮度差超过阈值，则认为该象素值位于图像的运动物体区，需把这些象素存在缓冲存储器中，并以恒定的传输速度传送；而阈值以下的象素则认为该象素位于图像的背景区或相对静止区，不传送该值，在接收端用上一帧相应象素值来代替。这样一幅电视图像可能只传送其中较少部分的象素，且传送的只是帧间差值，以得到较好的压缩比。据统计，在可视电话应用中，用条件补充法需要传送的象素只占全部象素的６％左右，但它在影视等运动变化剧烈的应用场合中应用效果尚不是很好。

２运动补偿技术

运动补偿方法是跟踪画面内的运动情况对其加以补偿之后再进行帧间预测，它能较好的提高编码压缩比，在近十年来，得到特别的重视和广泛的应用。运动补偿预测技术通常由以下几方面组成：

１）首先把图像分割为静止和运动的两部分，这里假设运动物体仅作平移：

２）估计物体的位移值；

３）用位移估值（即运动矢量）进行运动补偿预测；

MPGE4 编码算法

国防科学技术大学研究生院学位论文

４）预测信息编码。

在这里，图像分割是运动补偿预测的基础，实际上要把图像分割成不同运动的物体比较困难，从而通常采用两种较简单的方法：一种是把图像分为矩形子块，适当选择块的大小，把子块分为动和不动两种，估计出运动子块的位移，进行预测传输；另一种方法是对每个象素的位移进行递归估计。

在图像分割的基础上，对运动子块的估计（或者说运动估值ＭＥ）便成了运动补偿预测的关键技术，一旦求得运动物体的运动矢量后，即可将其送入ＭＣ预测器（如图２．３所示），进行编码传输。

输入当

图２．３运动补偿预测编码器

由于在运动图像编码中较多的关心由被摄物体和摄像机二者之间的运动共同造成的物体图像的二维运动，高效而简捷的运动矢量求取算法就成了运动补偿技术中的焦点问题，目前常用的几种对运动矢量进行估值的方法有：

块匹配算法：ＢＭＡ（Ｂｌｏｃｋ．ＭａｔｃｈｉｎｇＡｌｇｏｒｉｔｈｒｎ）是目前最常用的运动估计算法，它假设块内各象素只作相等地平移。在该算法中要求确定块尺寸大小的选择，只有在块小时才可近似认为块内各点作相等地平移，以满足ＢＭＡ的基本假设。但若块太小，则估计结果易受干扰噪声影响不够可靠，且传送运动矢量所需比特数过多；块取大则可减轻其影响，但ＢＭＡ法的基本假定难以满足，影响估计精度，且大块中常包含多个不同运动的物体，块内运动一致性更难满足。作为折衷考虑，ＭＰＥＧ４标准选取１６＇１６象素点阵作为块匹配单元。

象素递归法：它能适应运动补偿帧内插中对每个象素的运动进行精确到亚像元级的估计要求，由于每个象素都有一个对应的运动矢量，为了降低码率而避免将其所有的运动矢量都进行传输，提出了许多解决的办法。如：让接收端在与发射端同样的条件下用与发射端相同的方法进行运动估计、Ｎｅｔｒａｖａｌｉ象素递归法的迭代修正、将块递归和迭代修正相结合的运动估计算法等。

相位相关法：由于物体的空间位移与其相位变化相对应，从而可将运动估计转至频率域进行，这其中需要进行傅立叶变换求得相位相关函数，利用相位相关函数的尖峰求取运动矢量估值。

MPGE4 编码算法

国防科学技术大学研究生院学位论文

在当前的视频数据压缩中运动补偿技术是关键，而运动矢量的求取又是关键中的关键，运动估计的实时性和估计精度是一对基本矛盾。在现时的技术条件下及常见应用中，块匹配算法基本上能同时满足实时性和精度的要求，因而也是我们进行视频压缩编码主要运用的运动估计方法。随着应用的不断扩大，对运动估计的速度和精度提出的要求也将更高，从而需要研究更好的运动估计算法以适应新的需要。

§２．３．２正交变换编码

变换编码的基本思想是通过焚换操作除去由于坐标轴的选掸小当而引起的相关性，而且有可能将难以处理的各种小局部相关集中到一起处理。常见的正交变换编码方法有：ＫＬ变换、ＤＣＴ变换、傅立叶变换、哈尔变换、Ｗａｌｓｈ．Ｈａｄａｍａｒｄ变换等，在图像压缩中常用ＤＣＴ变换【７１。

ＤＣＴ变换的进行过程是在编码端将原始图像分割成许多子像块，对每一个像块进行ＤＣＴ正交变换，生成频域中的系数阵，它是一种无损压缩方法。

当以｛ｆ（ｘ））表示Ｍ个其值有限的一维实数信号序列的集合时，ｘ＝０…１．．，ｎ一１，则其一维ＤＣＴ定义为：

脚，＝√寺ｃ∽篓ｍ徊ｓ与产，删＾…肛－；

一维逆变换（ＩＤＣＴ）定义为：

ｍ，－Ｊ寺篓ｃ∽脚。ｓ％产，删＾……

舯ｃ∽＝臀’其菩。

由此扩展得二维ＤＣＴ的定义，设数字图像ｆ（ｘ，ｙ）是具有Ｍ行Ｎ列的～个矩阵，运用ＤＣＴ将其从空间域（Ｘｙ平面）转换到ＤＣＴ变换域（ｕｖ平面）：

ＦＤＣＴ．＂脚，＝击ｃ∽ｃ∽Ｍ萎－Ｉ荟Ｎ－Ｉ似川ｃｏｓ笺产ｃｏｓ％产

其相应的ＤＣＴ逆变换为：

嘲：ｍ∽＝击篓篓ｃ∽ｃ∽脚炳笺产ｃｏｓ％笋

其中：ｘ，ｕ＝０…１．．Ｍ－ｌ；ｙ，ｖ＝０…１．．Ｎ－１；

∞，＝惜’其箸。“∽＝臀’其善。

在视频编码中，通常需要研究二维ＦＤＣＴ、ＩＤＣＴ的快速算法。

§２．３．３量化编码

二墼塑壹：墨些墨垡垫焦昱型墼兰堡曼盟墼塾：耍二星茎墼至蠼塑堕曼茎塑圭丝星：

MPGE4 编码算法

国防科学技术大学研究生院学位论文

量化则是指由数字量到数字量的多对一映射。量化器所要完成的功能是按一定的规则对表达式作近似表示，即指量化器用一组有限的实数集作为输出，其中每个数代表一群最接近于它的取样值，量化编码为有损编码。

量化常分为三类：标量量化（零记忆量化或一维量化）、向量量化（分组量化）和序列量化。在标量量化中，所有采样使用同一个量化器进行量化，每个采样的量化都和其它所有采样无关。向量量化（多维量化）则是从称为码本的码字集合中选出最紧密适配于序列的一个码字来近似一个采样序列（即一个向量），这种方法以输入序列与选出的码字之间失真最小为依据。

在视频编码中较多应用量化的过程是对二维ＤＣＴ系数的量化处理，由于对于信号矩阵实施正交变换后，系数的能量分布一般比较集中，如二维ＤＣＴ变换后的系数矩阵，能量集中在左上角，从而可想办法对于能量或能量差分重新量化以达到信息压缩的目的。在这里，量化时对于人眼最敏感的空间频率及能量分布比较大的系数分配较多的比特数。§２．３．４信息熵编码

信息是用不确定的量度定义的，所谓信息量则是指从Ｎ个相等可能事件中选出一个事件所需要的信息度量或含量，而熵则是指将信源所有可能事件的信息量进行平均。香农信息论认为．信源所含有的平均信息量（熵）是进行无失真编码的理论极限，信源中或多或少的含有自然冗余度，这些冗余度既来自于信源本身的相关性，又来自于信源概率分布的不均匀性中，只要找到去除相关性或改变概率分布不均匀性的方法和手段，也就找到了信息熵编码的方法。这种编码也是基于统计冗余数据压缩理论的一种编码方法，为无损压缩。

在多媒体视频压缩中常用的两种信息熵方法为：哈夫曼（Ｈｕｆｆｍａｎ）编码方法、游程（行程）编码方法。

１哈夫曼编码

该编码方法是基于如下定理：在变长字码中，对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码，如果码字长度严格按照符号出现概率大小排列，则平均码字长度一定小于按任何其它符号顺序排列得到的码字长度。

在该编码方法中，先必须进行概率统计，在此基础上对所有信源中的符号赋一特定变长字码，从而求得哈夫曼表，在Ｈｕｆｆｍａｎ表的基础上进行变长码的编码和解码。

２游程编码

其主要思路为：将一个相同值的连续串用一个代表值和串长来代替。例如，有一信源符合序列６６６９９００００００，则其游程编码为（６，３），（９，２），（Ｏ，６）。

在视频压缩中，游程编码和ＤＣＴ变换及Ｈｕｆｆｍａｎ方法一起使用。对分块做完ＤＣＴ变换及量化后的频域图像数据做“Ｚ”形扫描，然后进行游程编码，对其结果再做Ｈｕｆｆｍａｎ（变长）编码。

MPGE4 编码算法

里堕型兰茎查奎兰竺耋尘堕兰垡笙兰

§２．４ＭＰＥＧ４标准简介

§２．４．１ＭＰＥＧ４标准概述

ＩＳＯ的ＭＰＥＧ４标准的第一版于１９９９年１月『Ｆ式公靠，标准的第二版于１９９９年１２

月公布ｐ１。较之ＭＰＥＧ前两个图像压缩标准而言，ＭＰＥＧ４为多媒体数薪ｉ：压缩提供了一

个Ⅲ为广阔的平台，它更多定义的是～种格式和框架，而不是其体的算法。ＭＰＥＧ４的

…发点就是希望建立起一个更自山的通信与研发环境，人们可以在系统ｒｌＩ加入许多新的

算｝』ｉ，为用计算机软件做编码、解码提供了更大的方便。它可以将各种各样的多媒体技

术允分用于编码中，除包括压缩本身的一些工具、算法，还包括图像分析和合成、计算

机视觉、计算机图形、虚拟现实和语音合成等技术。ＭＰＥＧ４设计之初足为了在电话线

上ｆｅ输视频和音频数据，是一个超低比特率运动图像和语音的压缩标准，但是随着研究

Ｔ作的深入，它所包含的内容和将要起的作用已经远远超出了最初的设计心想。

采纳了基于对象（ｏｂｊｅｃｔ－ｂａｓｅｄ）的编码、基于模型（ｍｏｄｅｌ－ｂａｓｅｄ）的编码等第二二代编码技

术是ＭＰＥＧ４标准的主要特征，所谓的对象是在一个场景中能够访问和操纵的实体，对

象的划分可以根据其独特的纹理、运动、形状、模型和高层语义为依据。这种编码是…

利－Ｊ占于内容的数据压缩方式，以前的压缩算法只是去掉帧内和帧问的冗余，ＭＰＥＧ４则

要求对图像和视频作更多的分析，甚至是理解。如将图像分割为运动物体对象和静止不

动的背景对象平面，并对这两个对象进行分别处理。背景对象采用压缩比较高、损失比

较火的办法进行编码，运动物体对致采用压缩比较低、损失较小的办法，这样就在压缩

效率和解码图像质量问得到较好的平衡。ＭＰＥＧ４编码和解码的基本尊元是对象，这些

对象可以是单声道、立体声和多声道音频，２Ｄ和３Ｄ或者单目、立体或多目视频、计算

机蚓形、动画、文字等。基于对象的编码除了能提高数据的压缩比，还能实现许多基ｒ

内窬的交互性功能”１１。

基于对象的分级功能是ＭＰＥＧ４提供的又一个新的助能，同时兼容于ＭＥＰＧ．２标准

中的图像分级功能，分级工具主要用于互联网和无线网等窄带的视频通信、多质量视频

服务和多媒体数据库预览等服务。ＭＰＥＧ４提供了两种基本的分级工具：时域分级和审

域分级，时域分级是降低原视频序列的帧率，空域分级是降低原视频序列的分辨率。在

每类分级工具中，视频序列都可以分为两层：基层和增强层，基层提供了视频序列的基

本信息，增强层提供了视频序列更高的分辨率和细节，基层可以单独传输和解码，而增

强联则必须与基层一起传输和解码。ＭＰＥＧ４也支持时域和空域的混合分级。

…于移动通信的迅速发展，通过无线网传输音频和视频信息变得越水越重要了，这

需－婴提供在易错的通信环境下实现安全的低码率编码和传输。ＭＰＥＧ４的编码具有鲁棒

性和纠错功能，它采用３个策略来达到此目的：再州步（ｒｅｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ）、数据恢复（ｄａｔａ

ｒｅｃｏｖｅｒｙ）、错误隐藏（ｅｒｒｏｒｃｏｎｃｅａｌｍｅｎｔ）。再同步工具在检测到误码时重新存解码器和码

流ｎＵ建立同步点，前一个同步点和新建立的同步点间的码流就足发生误码的数据：数据

恢复是通过标准中提供的一种可逆变长编码技术来恢复两个同步点之间的数据；错误躲

减通过空间的纹理相关性和视频丽后帧的相关性舯错误的图像区域进行隐藏。第９页

MPGE4 编码算法

国防科学技术大学研究生院学位论文

图２．４ＭＰＥＧ４的一个应用场景

图２．４是用ＭＰＥＧ４的各种音频和视频对象组成场景的例子，它包括一个正在讲课的

人以及对应的声音组成的新的组合音视频对象、２Ｄ的背景对象、Ｓｐｒｉｔｅ对象、３Ｄ的桌

子和３Ｄ的地球仪等。在ＭＰＥＧ４中不仅容许作者以这些对象为素材组成新的场景，也容

许使用者操作这些对象，如把各种对象按一定的顺序和位置放在一个特定的场景坐标系

中，改变３Ｄ对象的视角，交互式听或看场景中的某一对象，通过动画参数使某一虚拟

对象产生动画感。

§２．４．２ＭＰＥＧ４视频编码中的数据结构类

ＭＰＥＧ４中有以下四个层次的数据结构，它们都以类的形式定义【６１。

ＶＳ（ＶｉｄｅｏＳｅｓｓｉｏｎ）：视频场景，它位于数据结构层次的最高层，一个完整的视频序

列可以由几个ＶＳ组成。

ＶＯ（ＶｉｄｅｏＯｂｊｅｃｔ）：视频对象，它是场景中的某个物体，它是有生命期的，由时间

上连续的许多帧构成。

ＶＯＬ（ＶｉｄｅｏＯｂｊｅｃｔＬａｙｅｒ）：视频对象层，ＶＯ的三种属性信息编码于这个类中，这

个类的引入主要用来扩展ＶＯ的时域或空域分辨率。

ＶＯＰ（ＶｉｄｅｏＯｂｊｅｃｔＰｌａｎｅ）：视频对象平面，它可以看作是ＶＯ在某～时刻的表象，

即某一帧Ｖ０。

第１０页

MPGE4 编码算法

国防科学技术大学研究生院学位论文

以上四个类的关系可以用图２．５表示：

ｒｉｄｅｏＳｅｓｓｉｏｒｔＶＳ０ＶＳＩ

…一………………：７△＼：：………

ＶｉｄｅｏＯｂｊｅｃｔ

ＶｉｄｅｏＯｂｊｅｃｔＬａｙｅｒ………７＼……………．Ｖ００Ｖ０１ＶＯＬＯＶＯＬＩ

……………八……＿一入…………ｗ出础严伊１蛆。｜！！！！！：！！二ＩＺ竺：！！∑］

Ｌａｙｅｒ０Ｌａｙｅｒｌ

图２．５ＭＰＥＧ４中的数据结构

§２．４．３ＭＰＥＧ４视频编码和解码框架

ＭＰＥＧ４编码和解码是针对ＶＯＰ进行的，其逻辑结构如图２．６所示。编码时首先由输入的视频序列定义出ＶＯＰ，针对每一个ＶＯＰ分别进行编码，将所有ＶＯＰ编码的结果合成在一起，形成压缩视频数据流。解码时首先将压缩视频数据流分解，得到每一个ＶＯＰ的编码数据流，针对它们分别进行ＶＯＰ解码，解码结果组合在一起形成输出视频‘“。

—＿一ｖｏ舢Ｌｌ—ｌ

ｌ

ｌｃｏｄｉｎｇｆｌＩ—一ｖ０¨Ｌ—ＣｏｄｉｎｇＭＵＸ—．１Ｊ∞陀Ｌ—Ｃｏｄｉｎｇ

。。。。。一Ｉ。。。。。。。

—ＤⅧｅｃｏＭＩｉｎｇ卜

—－一哪！Ｌ—

ＤＥＭＵＸｌＤｅｃｏｄｉｎｇｌ

—＿一ｖ０阳Ｌ一一ＩＤｅｃｏｄｉｎｇｌ

’’’。。。＿ｆ。。。。。。－

图２．６ＭＰＥＧ４编码和解码原理图

MPGE4 编码算法

国防科学技术大学研究生院学位论文

§２．４．４ＭＰＥＧ４的框架和级别

ＭＰＥＧ４提供了大量的、丰富的音频视频对象的编码工具，能够满足各种各样的应用需要”１。对于某一特定的应用，只有一部分系统、视频和音频的编码工具被采用，框架（ｐｒｏｆｉｌｅ）就是针对特定的应用确定要采用的编码工具，它是ＭＰＥＧ４提供的工具集的一个子集。每一个框架又有一个或多个级另ｌＪ（１ｅｖｅｌ）来限制计算的复杂度。ＭＰＥＧ４共有４类框架：视频框架、音频框架、图形框架和场景描述框架。其中视频框架又包含５个级别，如下【６１：

（１）ＳｉｍｐｌｅＶｉｓｕａｌＰｒｏｆｉｌｅ：提供矩形视频对象高效有容错能力的编码功能，适合应用于移动网络。

Ｐｒｏｆｉｌｅ：在ＳｉｍｐｌｅＰｒｏｆｉｌｅ基础上增加了对象时域和空域

扩展编码功能，应用于提供多级服务质量的应用，如Ｉｎｔｅｒｎｅｔ和软件解码。（２）ＳｉｍｐｌｅＳｃａｌａｂｌｅＶｉｓｕａｌ

（３）ＣｏｒｅＶｉｓｕａｌＰｒｏｆｉｌｅ：在ＳｉｍｐｌｅＰｒｏｆｉｌｅ基础上增加了任意形状对象编码和时域扩展编码功能，适用于相对简单的内容交互应用，如Ｉｎｔｅｍｅｔ多媒体应用。

（４）ＭａｉｎＶｉｓｕａｌＰｒｏｆｉｌｅ：在ＣｏｒｅＰｒｏｆｉｌｅ基础上增加了Ｓｐｒｉｔｅ对象编码功能，适用于交互和娱乐质量广播和ＤＶＤ应用等。

（５）Ｎ－ＢｉｔＶｉｓｕａｌＰｒｏｆｉｌｅ：在ＣｏｒｅＰｒｏｆｉｌｅ基础上增加了具有不同像素深度（４．１２ｂｉｔｓ）视频对象编码功能，适用于监控应用。

§２．５小结

这一章第一部分介绍了视频处理及视频压缩方面的基本知识、方法和理论，包括视频信号的获取过程、视频压缩的必要性和常用的视频数据压缩技术，其中常用的视频数据压缩技术包括预测编码、正交变换编码、量化编码和信息熵编码；本章第二部分对ＭＰＥＧ４标准作了简要介绍，首先对ＭＰＥＧ４作总体概述，包括其发展沿革、基本思想、主要特征等；接着重点介绍视频编码的基本概念、视频编码和解码框架；最后介绍ＭＰＥＧ４框架级别分类。本章是课题的基本概念和基本理论基础。

MPGE4 编码算法

国防科学技术大学研究生院学位论文

第３章运动估计算法的研究与改进

帧问运动补偿技术是视频编码国际标准技术框架的重要组成部分，从Ｈ２６３到ＭＰＥＧｌ和ＭＰＥＧ２无一例外都采用了帧问运动补偿技术，它是消除时问冗余的最基本和最ｒＲ要的方法。帧间运动补偿压缩编码大致分为三步：第一步是在相邻帧中估计运动物体的位移值，称为运动估计（ＭｏｔｉｏｎＥｓｔｉｍａｔｉｏｎ，ＭＥ）；第二步是利用所得到的运动估值进行帧间预测编码，即运动补偿（ＭｏｔｉｏｎＣｏｍｐｅｎｓａｔｉｏｎ，ＭＣ）；第三步是预测信息如运动矢量、预测误差的编码。实现上述编码的关键足运动估计。运动估计算法的优劣直接影响视频编码的效率和质量。实验表明在编码一段视频序列时运动估计所耗用的时问约为烂个压缩时间的一半，而且运动估计的精度也影响省编码的视频质量。

本课题的应用背景是远程视频：临控，远程视频ｎ在控要求实时地刈’视频帧进行压缩编码，对视频编码的效率要求很高。为适应这种要求，有必要对视频压缩中最影响压缩效率的运动估计算法做深入研究，并在不影响视频质量的情况下，在传统运动估计算法的基础上寻求改进的方法，以提高编码效率。目时使用最广泛的运动估计算法是块匹配算法和ｌ象素递归算法。

本爷首先讨论了传统的运动估计算法，即象素递归算法及几种块匹配算法的原理及其优缺点，然后在传统算法的基础上，提Ⅲ了四步搜索块匹配算法，接下水给…以四步搜索块匹配算法为基础的完整运动估计算法的实现，最后根据实验测试结果对算法进行评价。

§３．１传统的运动估计算法

象素递归算法

象素递归算法（Ｐｅｌ－－ＲｅｃｕｒｓｉｖｅＡｌｇｏｒｉｔｈｍ，ＰＲＡ）的出发点是通过对狄度的梯度变化来求象素的位移。由于ＰＲＡ算法的最小搜索单元是象素点，因而对物体的运动有较高的灵敏度，位移估值的精度也高，对复杂运动画而具有较强的适应性。但它跟踪的位移范幽搬小。另外，由于ＰＲＡ算法对位移的估值是通过梯度运算得到的，因而运算代价大，硬什实现的复杂度高，导致ＰＲＡ算法的实用化程度不如块匹配算法【ｔ２１。

块匹配算法

块匹配算法ＩＩ副（ＢｌｏｃｋＭａｔｃｈｉｎｇＡｌｇｏｒｉｔｈｍ）通过对ｌ刘像序列中两帧图像问了块的匹都被认为是相同的。块匹配算法的几何结构如图３．１所示。当前帧图像被分割为ｉ．ｎＺｒｔ

§３．１．１§３．１．２配米进行运动估计。块匹配算法中，图像被分割成子块，予块ｒｌ－的所有象素的运动矢量象鬃大小的矩形块（称为子块，通常取ｍ＝ｎ），每一个子块只需计算一个运动矢量（ＭＶ），每一个子块ｗ在参考帧内预先确定的一个搜索区域ｓ内进行块匹配运算，搜索区域大小ｓ＝（ｍ＋２ｄ）ｘ砌＋列Ｊ，其中ｄ为垂直和水平方向的最大位移。块匹配算法由于算法简

MPGE4 编码算法

国防科学技术大学研究生院学位论文

单，实现容易，额外开销小，所以成为目前使用最多的运动估计算法。Ｈ．２６１、ＭＰＥＧｌ、ＭＰＥＧ２和Ｈ．２６３等国际标准的运动估计都采用了块匹配算法。传统的块匹配算法大致有全搜索法、三步搜索法、二维对数搜索法、共轭方向搜索法等。

图３．１块匹配算法的几何结构

§３．１．２．１全搜索算法

全搜索算法对搜索区域ｓ内的所有位置都进行位移匹配运算，搜索过程可以是从左到右，从上到下，按扫描顺序搜索：也可以采用以位移巾，Ｄ）点中心的螺旋型搜索。全搜索算法虽然能取得令人满意的结果，但其搜索所需的运算量极大。为了进一步减少匹配算法的搜索次数，降低运算量，人们研究出一些快速搜索算法如三步搜索算法、二维对数搜索法、共轭方向搜索法等。

§３．１．２．２三步搜索算法【９】

三步法是一种由粗到精的搜索方法。其算法如下：

（１）以搜索窗口原点为中心，以Ｌｔ＝ＩＮＴ似２＋Ｄ．Ｊ）为步长构造一个九点点阵。

（２）计算上述各点的误差值，找出误差最小的点，并以此点为中心，以Ｌ？＝ＩＮＴ（Ｌｄ２＋ｎ习为新的步长构造新的九点点阵。

（３）以Ｌｎ＋ｌ＝ＩＮＴ（Ｌ，／２＋ｎ纠为步长重复第（２）步，直到搜索步长减至１。此时的九点中误差最小的点即为最佳匹配点，对应的坐标即为运动矢量。

图３．２给出了三步的搜索过程。搜索区域为±７个象素，经过三次搜索（步长依次为４，２，１），最后得到运动矢量（５，３）。

MPGE4 编码算法

１ｌ１

２２２

１１２

３

２３ｌ３３３２、

３

１２３】１３

图３．２三步搜索法

§３．１．２．３二维对数搜索算法

二维对数搜索法的基本思想是匹配误差函数值Ｄ“，ｊ离开最小匹配误差点后是单调上升的，如果以，）为匹配点，那么Ｄｎ，）最小。以搜索区域为±８个象素为例，搜索过程如下：

（１）初始步长为４，首先共有５个候选点参加匹配，找出最小误差点。

（２）以同样的步长比较在最小误差方向上的３个点的值，当最小误差点位于搜索位置的中心或位于搜索范围的边界时，搜索步长减半。

（３）重复第（２）步直到步长为１。

图３．３中，首先比较Ｄ似∥、Ｄ（ｉ—ｔ∥、Ｄ一＋ｔ∥、Ｄ—ｊ－钏和Ｄｒｆ，／＋纠这五个点的值，

找到最小匹配误差点以，一砂；然后比较Ｄ（ｉ＋４，ｊ－钏、Ｄ（ｉ—Ｚ产砂，Ｄ一／一砂三点的值，找到最小误差点“产占上该点位于搜索区域的边界，此时步长减半，继续进行搜索，最后找到最佳匹配点以＋３。／－７ｊ。

§３．１．２．４共轭方向搜索算法

共轭方向搜索算法如下：

（１）寻找ｉ方向的最小误差值。方法是比较ｎ．Ｌ，）、“，，ｊ、以＋』，，）三点的误差值，如果０＋１，，ｊ的误差值最小，则计算０＋２，＿，ｊ，这样可以找到ｍ，ｊ、０＋１，，）、０＋２，，ｊ中的最小误差值。

（２）重复第（１）步直到误差值最小点位于三点之间。

（３）用（１）、（２）的方法寻找Ｊ方向的最小误差值。

在图３．４中，首先找到点（ｉ＋３，ｊ），在此基础上找到点（ｉ＋３，ｊ．７），为最佳匹配点。

MPGE4 编码算法

国防科学技术大学研究生院学位论文

‘２ｌ

图３．３二维对数搜索法

图３．４共轭方向搜索法

§３．１．３相位相关法

块匹配算法是在空间域直接进行运动估计。由于物体的空间位移与其相位变化相对应，因而运动估计也可在频率域进行ａ设％一，似ｙ）和％（工，力分别为两帧图像中大小为Ｎ×Ｎ的子块。记吼一。（ｘ，ｙ）得傅立叶变换为Ｆｂ。（ｘ，ｙ）】＝Ｅ一．（“，ｖ）。则根据傅立叶变换的性质，Ｓｋ－１（工，ｙ）的空间平移＆（ｚ，ｙ）＝ｓ¨０一ｄ，，Ｙ—ｄｙ）的傅立叶变换为

Ｆｂ★（ｘ，ｙ）】＝Ｅ—ｌ＠，ｖ）ｅｘｐ［－ｊ２石（ｕｄｘ＋ｖｄｙ）】＝Ｅ＠，ｖ）

它与屯一。（ｘ，ｙ）之间的相位差为

MPGE4 编码算法

国防科学技术大学研究生院学位论文

△口＝一ｊ２ｘ（ｕｄｘ＋ｖｄｙ）

显然，如果在主频率（“．，ｖ。）和（“：，ｖ：）处计算出相位差，则从上式很容易求得平移运动量ｄｘ和ｄ，。根据进一步的观察，对于平移运动，相位相关函数将产生比互相关函数尖锐得多的尖峰。因而用相位相关函数进行运动估计更加有利。相位相关函数的定义为［９ｌ

叭训广ｐｓｋ＿ｌ（Ｘ，ｙ）＝Ｆ－＇器舞尚

其中Ｆ“为傅立叶反变换符。”Ｐ为相位相关算子。

通常将相位相关法与匹配法结合起来进行运动估计，运动估计的步骤如下：

（１）将帧划分为ＮＸＮ大小的相位子块，计算每块的相位相关函数；

（２）选择相位相关函数中的几个高峰作为候选运动矢量；

（３）用块匹配法逐小块（或逐点）的在这些候选运动矢量中选定一个，作为运动

矢量的最终估计值。

§３．１．４传统运动估计算法的性能分析

象素递归算法虽然能够实现最精确的估计，但由于计算复杂度过高难以在软件编码中使用。相位相关法同样具有较高的运算复杂度，且估计的精确度不高，也没有得到广泛的应用。相比而言块匹配算法具有算法简单，实现容易，额外开销小等优点，但仍有其不足的地方：全局搜索算法能够保证找到匹配误差函数的全局最小值，保证得到正确的结果，但其算法的复杂度很高，搜索过程极其耗费时间；快速搜索算法虽然在搜索速度上提高了很多，但却无法保证得到全局最佳匹配。在目前的技术条件下，对许多应用而言，块匹配算法基本能够满足实时性和精度的要求，因而是一种实用的运动估计算法。

§３．２四步搜索算法的设计与实现

由上一节的讨论可知，在视频编码中应该采用块匹配的运动估计算法，但传统的块匹配算法在匹配速度上仍达不到满意的效果，因此本文在传统块匹配算法主要是三步搜索算法的基础上，提出了一种四步搜索的块匹配算法，在保证一定搜索精度的前提下，进一步减少匹配点，提高搜索的速度。下面介绍四步搜索块匹配算法及其实现方法。§３．２．１四步搜索算法

同三步搜索算法一样，四步搜索算法也是一种由粗到精的搜索方法。它首先以九个点开始匹配（其中包括一个搜索窗口中心点），以后搜索的匹配点根据一定的原则进行选择，具体原则在下面说明。四步搜索算法描述如下：

（１）搜索匹配点组成一个菱形窗口，如图３．５所示。初始的９个匹配点为菱形的四个顶点、四条边的中点以及菱形的中心点，如图３．５中的实心点。对每个点计算ＳＡＤ（绝对误差和，ＳｕｍｏｆＡｂｓｏｌｕｔｅＤｉｆｆｅｒｅｎｃｅ）的值，选取ＳＡＤ最小的点。如果该点是此次搜索窗口的中心则到第４步，否则到第２步。

MPGE4 编码算法

国防科学技术大学研究生院学位论文

（２）以ＳＡＤ最小的点为新的菱形匹配点窗口的中心点，其余的匹配点的选取按下面的原则进行。如图３．５所示。

Ｕ

ｈ■’，

Ｂ

ＣＡ

图３．５４步搜索中匹配点的选择示意图

ａ）如果ＳＡＤ最小的点是当前搜索窗口的角上的点，如Ａ点，则取与Ａ点不相邻的另外５个点，如图３．５中的形如０的点。选取ＳＡＤ最小的点，并到第３步；

ｂ）如果ＳＡＤ最小的点是当前搜索窗口的边上的中点，如Ｂ点，则取与Ａ点不相邻的另外３个点，如图３．５中的形如①的点。选取ＳＡＤ最小的点，并到第３步；

ｃ）如果ＳＡＤ最小的点是在当前搜索窗口的中点Ｃ点，则到第４步。

（３）搜索模式同２，最后都到第４步。

（４）选取周围的四个点作为匹配点，步长改为１，如图３．５中的空心点。选取ＳＡＤ最小的点作为最终目标点。

将四步搜索算法与三步搜索算法相比较，可以得到如下结论：

（１）第一次搜索时，三步搜索算法的搜索匹配点组成一个矩形窗口，而四步搜索算法的搜索匹配点组成一个菱形窗口，搜索点更靠近中心点：

（２）以后的每一次搜索中，三步搜索算法都要搜索９个点，而四步搜索根据上一次搜索匹配点的位置不同，只需搜索５个、３个或４个点，由此可知，四步搜索算法比三步搜索算法的搜索匹配点要少；

（３）三步搜索算法的搜索步长由大到小的递减，因此搜索精度也是由粗到精，而四步搜索算法的步长在最后一次搜索（最后一次搜索步长为１）之前，步长为恒定值２，由此可知，四步搜索算法的精度比三步搜索算法要高。

由以上分析可知，四步搜索算法比三步搜索算法的复杂度更小，但搜索精度并未降低。图３．６所示为四步搜索收敛示意图，起点为ｌ（Ｉ），收敛点为５（Ｏ）。

本文来源：https://www.bwwdw.com/article/99d4.html