umhexagon算法的分析与改进

umhexagon算法的分析与改进

1运动估计模块h.264的编码效率可以比现有的h.263或h.4的编码效率提高50%。这是近年来h.263和mpeg-4的主要发展趋势之一。虽然H.264的基本编码框架与以往类似标准如H.263相比没有作出重大改变，但各个部分的技术方案引进了当前视频编码的许多新技术。可以说，它的高性能是以增加计算复杂性和存储能力为代价获得的。这种高复杂度对于H.264的实现和应用将是一个瓶颈。尽管编码标准中并未指定运动估计算法，但由于运动估算的速度和准确性对整个编码器性能的影响较大，因此H.264一直在寻找一种更优秀的快速运动估计算法。目前H.264已正式采纳了“非对称十字型多层次六边形格点搜索”（UMHexagonS）算法，它的运算量相对于快速全搜索算法可节约90%以上，同时能保持较好的率失真性能。本文对UMHexagonS算法提出了一种改进方法：引入一个调节因子βStop，并在原算法的预测起点部分增加一个自适应的中止搜索判断，在保证原算法良好的率失真特性的前提下，进一步降低运算量，从而提高整个H.264编码器的编码效率。本文第2节将介绍和分析UMHexagonS算法，第3节提出改进算法，第4节为计算机模拟结果以及对此所作的分析，结论将在第5节给出。2umhexagon算法2.1mvst算法已有的块匹配算法中，搜索精度最高的是全搜索法，但存在搜索时间长和运算量大等缺点，难以满足实时要求。为了减少搜索时间，已提出多种快速搜索方法，如三步法（TSS）、菱形算法（DS）等。这些经典快速搜索算法简化了计算，却是以牺牲图像质量为代价的，且降低了预测精度，相应的码率较高。因此，需要对这些经典算法作进一步的改进。这里介绍一种新的运动估计算法：非对称十字型多层次六边形格点搜索算法（UMHexagonS）。它的基本步骤如下：步骤1起始搜索点的预测：五种预测模式求预测运动矢量MVpred:(1）中值预测：利用空间相关性，取已求出的、当前帧的左、上、右上邻块的运动矢量的中间值MVpred＿sp=MVspace;(2）原点预测（考虑到在固定背景上的物体边界的情况）：MV2=(0,0);(3)uplayer预测：利用H.264运动估计多宏块划分等特点，采用从模式1(16×16）到模式7(4×4）的分级搜索顺序，取已求出的、同位置、上一级（uplayer）、大一倍块的运动矢量（图1)MVpred＿up=MVuplayer;(4）相应块预测：利用时间相关性，取已求出的、前一帧同位置块的运动矢量MVpred＿time=MVtime;(5）相邻参考帧预测：利用时间相关性，取已求出的、前一参考帧中当前块的MV按比例进行预测（参见图2）:对以上MV所指向的点进行十字模板（见图3(c））搜索，获得当前的最佳预测起点；类似MV，相应的SAD也具有很强的相关性。因此将MVpred＿sp、MVpred＿up、MVpred＿ref所指向点的率失真值分别称为Pred＿space＿mincost、Pred＿uplayer＿mincost、Pred＿ref＿mincost，作为当前mincost是否足够准确的标尺，使用阈值判断公式（详见第3节）判断此处属于不甚满意还是满意或很满意区，并跳到相应的步骤2或步骤3或步骤4。步骤2不甚满意区的块搜索：(1）以目前最佳点为中心，用不对称十字型搜索模板（见图3(a））进行搜索；获得目前最佳点，判断此处是否属于满意或很满意区，跳到相应的步骤3或步骤4；或继续搜索；(2）以目前最佳点为中心，在（-2,2）的方形区域（见图3(b））中进行逐点搜索；获得目前最佳点，判断此处是否属于满意或很满意区，跳到相应的步骤3或步骤4；或继续搜索；(3）用不断扩大一倍直径的大六角形模板（见图3(c））进行搜索，直至搜索到能符合相应阈值而进入步骤3或步骤4的点为止；或者搜索模板完全超出search＿range，也结束步骤2的搜索。步骤3满意区的块搜索：以目前最佳点为中心，用中六角形模板（见图3(c））进行搜索，直至最佳点在中六角形的中点为止。步骤4很满意区的块搜索：以目前最佳点为中心，用十字形模板（见图3(c））进行搜索，直至最佳点在十字形的中点为止。2.2运动估计搜索结果笔者认为，该算法主要有以下几个特点：(1）多种尺寸运动估计H.264的“运动估计多宏块划分”采用了7种块尺寸划分，分步进行块匹配，通过一个逐渐减小的过程来实现由粗到细的运动估计，从而获得可靠性高、一致性好的运动矢量场。这是UMHexagonS算法提高搜索精度、降低码率的原因之一，但也相应地提高了计算复杂度。(2）起点预测准确UMHexagonS算法所采用的起点预测综合利用了帧内、帧间相邻块（包括H.264的多参考帧带来的优势）的运动矢量相关性，以及H.264采用的宏块划分技术所带来的不同尺寸块的运动矢量相关性，因而可以选出最能反映当前运动块趋势的点作为初始搜索点，准确率相当高。以序列Akiyo的前30帧为例，步骤1预测后，就有79.46%的点可直接进入步骤4；未搜索到足够满意点而需要进行步骤2的只占总点数的6.48%。(3）内容自适应的搜索模板和搜索方式UMHexagonS算法每步的搜索都与图像内容有关。它的搜索摸板和搜索方式分为三种：大范围粗搜索混合模板（见步骤2）；细搜索中六角形模板（见步骤3）；精细搜索十字模板（见步骤4），对不同内容的块进行不同的搜索（判断选择方法见第3节），搜索性能得到进一步改善。(4）匹配准则采用率失真最优化准则为了在编码比特率和图像失真之间选择一个恰当的折衷，H.264对运动估计使用了率失真最优化（RateDistortionOptimization）准则，达到在目标数据率的条件下使传输的视频信号的失真最小。此优化操作即为下面的拉格朗日函数最小化：m=（mx,my)T为当前运动矢量，p=（px,py)T为预测运动矢量，λMOTION为拉格朗日乘法因子；R(m-p）代表运动信息。UMHexagonS算法的运算量相对于快速全搜索算法可节约90%以上。特别是在这种低运算量下，率失真性能明显优于其他快速算法，能很好地满足低码率和实时性要求，已经被H264协议正式采用。3筛选组合点的方法，将点分为3个自适应区域UMHexagonS算法在步骤3与步骤4上，都是以“最佳点在模板中心”为准则来判断是否最优、是否可结束搜索。也就是说，即使所得点已经是最佳点，却仍要按模板搜索一到两轮才能结束搜索，而这些点数都是浪费的。尤其对高准确率的起点预测而言，开始就找到最佳点的概率较大，则浪费在该结束而未结束搜索上的点数也就不可小视。以30帧的carphone序列为例，有76.1%的点在步骤1预测后就直接进入步骤3或步骤4；而其中的96.1%、95.8%的点其实已找到了最佳点，却仍需再搜索4或10个点才能结束搜索。因此本文提出了一个改进方法：在步骤1预测部分再增加一个与内容相关的自适应阈值，以判断是否可立即结束搜索。在UMHexagonS算法中，基本判断方法为：设当前最佳值为mincost（含义见式（1））:其中调整因子：数组Bsize为当前块尺寸；αSec、αThird为常数组，其值的选取请见文献。判断找到的点是否满意的方法有两种：这里称作A类判断与B类判断。在A类判断中，与mincost作比较的pred＿mincost=pred＿uplayer＿mincost（含义见2.1节），仅用在步骤1中的由MVpred＿up所指向的点求出比特率mincost后进行；其余地方的判断都使用B类判断。B类判断的pred＿mincost则视情况而定：笔者将各类标准序列在步骤1中进行判断而进入步骤2、步骤3、步骤4的点按blocktype的不同归类，并进行了大量的数据分析。提出改进方法如下：在步骤1的使用A类判断的地方，再增加一个类似B类判断的、内容自适应的新阈值来判断是否可停止搜索（考虑到判断本身的耗时，只在预测准确率最高处增加该停止判断）：mincost<（1+βStop）×pred＿mincost，则判为可停止搜索，其中pred＿mincost取B类判断中的pred＿mincost。根据实验数据，按其概率分布规律，本文将αStop[blocktype]取值选为：将上述改进引入UMHexagonS算法之后，结果表明，在对比特率、图像质量均影响不大的前提下，可比原UMHexagonS算法减少10%到30%的搜索点数。4两种算法比较本文采用H.264的JM8.6（取30帧/s,ref=5,search＿range=32，第1帧为I帧，其他帧为P帧），所得实验结果摘录如下。实验采用的标准运动序列分别为大运动序列Mobile，中运动序列Foreman、Trevor和缓慢运动序列MissAmerican、Akiyo的前80帧。表1为两种算法的总搜索点数比较。可见改进算法较有效地降低了搜索点数，特别对于缓慢运动序列效果更为明显，减少点数可达30%之多。表2为两种算法的平均比特率的比较。可看出，改进后对运动估计的准确性影响较小，因此编码产生的比特数变化较小。图像质量一般使用亮度峰值信噪比PSNR来评价，PSNR定义如下：式中，Ik(s）,Ik′（s）分别表示原始图像与解码图像中对应的像素，M,N分别表示图像的长宽尺寸。表3分别给出了使用两种算法后的平均峰值信噪比（dB）的比较。可看出，改进