运动估计快速搜索算法的研究

　　摘要：h.264是itu-t的vceg(视频编码专家组)和iso／iec的mpeg(活动图象编码专家组)的联合视频组(jvt：joint videoteam)开发的一个新的数字视频编码标准，它既是itu-t的h.264，又是1so／iec的mpeg-4的第10部分。新一代标准h.264可以得到更好的压缩图像效果、拥有更多的功能和更大的灵活性。本文主要从实时视频应用的角度，对h 264／avc编码过程中运动估计模块快速搜索算法进行了研究。
　　关键词：视频编码　h 264／avc　运动估计　快速搜索算法
　　
　　随着信息技术的发展和社会的不断进步，人类对信息的需求越来越丰富，人们希望无论何时何地都能够方便的、快捷、灵活的通过语音、数据、图像与视频等多种方式进行通信。数字信号处理技术、物理媒体与网络技术、超大规模集成电路技术突飞猛进的发展，使得多媒体通信成为研究和应用的热点。本文主要是针对视频压缩中的运动估计快速搜索算法的研究。视频压缩后的数据流大小的关键因素在于能否较好的去除其时间相关性，寻找到最佳的匹配块。
　　
　　1.h.264／avc概述
　　
　　与早期的视频编码标准(h.261，mpeg-1，mpeg-2，h.263，mpeg-4)类似，h.264／avc也是建立在块匹配的混合编码框架上。基本算法依然是通过帧间预测和运动补偿来消除视频序列中的时域冗余，经过变换编码消除频域冗余。因此基本的功能模块：例如预测、变换、量化、编码都没有发生根本的变化。
　　
　　2.运动估计原理
　　
　　2.1运动估计概述
　　在基于块匹配的混合视频编码体系中，运动搜索是其中计算复杂性最高的模块。h.264／avc为了获得更精确的预测和更高的压缩比，采用了多种块模式的运动估计，多参考帧和更高分辨率的运动矢量。虽然这样可以增加预测的精度，提高压缩比，但h.264／avc中运动估计的计算复杂性却因此急剧增加。

　　运动搜索快速算法的实质是基于某种策略在减少搜索点数提高搜索效率的同时，尽可能保持编码图像质量不变(与fs的情况相比)。但简单的减少搜索点数的算法(例如tts，2-d对数等快速算法)通常都假设匹配误差曲面是单峰的，而实际的视频图像是非常复杂的，常常不能满足这样的假设，因此容易在搜索起始阶段落入局部最小点。为解决局部最小点的问题，通常可以采用相邻块预测的方法获得更好的搜索起点。但有些情况下特别是在运动复杂度高的序列中，相邻块会包含与当前块不同的运动对象，因此也会产生错误的运动矢量。更好的策略是采用覆盖整个搜索区域的全局搜索(global search)的概念，即搜索点在整个搜索区域的稀疏网格上选择。虽然这种策略增加了搜索点数，但可以有效的避免在搜索起始阶段落入局部最小点以及可能的错误起始点预测。

　　2.2运动搜索的步骤
　　最佳匹配块的确定是通过运动搜索来实现的，运动搜索包含整数运动搜索和小数运动搜索，具体的流程图如图2.1所示：
　　2.2.1参考帧的选取
　　在h.264协议中，定义了三种基本的帧类型，即i、p、b帧类型，其中i帧只能作为其他帧的参考帧，它本身在编码的时候，帧内宏块根据已经编编码的相邻块的数据来编码，不参考其它帧；p帧在编码的时候，只能参考在时间轴上靠前的帧，包括之前已经编码的i帧以及p帧，即前向预测；b帧则可以双向预测，它的参考帧可以是时间上“过去”的帧。也可以是时间上“将来”的帧，它的参考帧也可以是i帧以及p帧，b帧只能参考其它帧，其本身不能作为其他帧的参考帧，所以他不会引起预测误差扩散。在具体的编码中，当遇到b型帧时，先把它读到缓存中，编码后面的p帧，当前后的参考帧都被编码以后，再编码b帧。在解码端，当解码解到b帧时，则先将它读入缓存，待到解码完它后面的p帧，再解码b帧。
　　2.2.2预测运动向量的获取
　　如果对每个块的运动矢量进行编码，那么将花费相当数目的比特数，特别是在选择小尺寸的块的情况下。由于一个运动物体会覆盖多个分块，所以空间域相邻块的运动矢量具有很强的相关性。因此，每个运动矢量可以根据临近先前已编码的块进行预测，预测得到的运动矢量用mvp表示，当前矢量和预测矢量之间的差值用mvd表示。同时由于物体运动具有连续性，运动矢量在时间域也存在一定的相关性，因此也可以用临近参考帧的运动矢量来进行预测。
　　2.2.3搜索范围的确定
　　当获取了预测运动向量以后，在参考帧中找到当前块的对应块，此点即对应运动向量(o，o)，并以此为基点，向其上下左右扩出运动搜索范围大小，此即我们需要的运动搜索范围。
　　搜索区域的选择一般是相对于当前块对称得，左边和右边各有d个像素，上边和下边各有d个像素。
　　
　　3.一种新的运动估计快速搜索算法
　　
　　这些年来，许多的快速搜索算法都被提了出来，其中比较好的有三步法，四步法，菱形搜索法等等，它们与全搜索算法相比节省了大量的运动时间。可是这些算法中大部分不论在水平还是在垂直方向上都是规则对称的，三步法和四步法等等都是如此，但是在实际的运动图像当中都是水平方向的运动要远比垂直方向的运动要剧烈的多，这是因为对于一个以常见的现实世界为内容的视频序列来说，它的前后帧之间的差异来源主要有两个方面：视频目标的运动和视频获取设备的运动。视频目标的常见运动集中在水平方向，如汽车和火车的行驶，行人在路上走等；而摄像机的运动一般以平动和水平转动为主，所以运动向量就应该是以水平方向的运动向量为主。
　　从运动向量的搜索过程中我们可以得知，后步的搜索都是建立在前一步的基础上的，每一步都为下一步指出了运动向量所在的大致方向，而运动向量又是以水平方向的运动向量为主，所以本算法中第一步以偏水平方向的十字搜索模板作为搜索基础。
　　基于偏水平十字及偏向双钻石搜索算法(dhcdds)主要是将两种搜索模版相结合尽可能的以最小的搜索时间准确的确定最佳匹配点，一种是偏水平十字型搜索模板，另一种是偏向双钻石搜索模板，其中第一个偏水平十字搜索模板主要是根据视频图像的运动变化主要是集中在水平方向上的特点来初步确定搜索的基本位置，第二个偏向双钻石搜索模板是根据偏水平十字搜索模板的初步定位，进一步使用搜索效果比较理想的双钻石搜索模板来确定当前最佳匹配点，直到当前最佳匹配点在中心点或偏中心点才结束搜索过程，然后通过比较几个候选点的sad值的大小来确定最佳匹配点的位置。该快速运动估计搜索算法所要搜索的点数较少，提高了编码效率。
　　
　　4.结语
　　
　　本文主要对于视频压缩中的运动估计快速搜索算法进行了简单的研究。视频压缩后的数据流大小的关键因素在于能否较好的去除其时间相关性，寻找到最佳的匹配块。实验表明在信噪比和比特率变化很小的情况下，搜索时间大为缩短。文中提出的算法仅仅采用了搜索模板的改变来提升搜索速度，相信再结合其他提升搜索速度的办法，比如说提前终止技术等，就能在此基础上进一步的提高搜索速度。由于运动估计占了h.264编码时间中的大部分，所以运动估计搜索速度的提高对于h.264的编码效率是很重要的。 本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/245131.html