HEVC帧间运动估算像素搜索改进方法

摘要

本发明提出的HEVC帧间运动估算像素搜索改进方法，基于整像素搜索模型的搜索核心过程和对应的优缺点，对搜索模型进行改进，采用不规则六边形搜索改进模型，更好的适应现实视频中运动倾向于水平和竖直方向运动的特征，利用临界值判定是否进行亚像素的搜索，有效减少亚像素搜索过程，提出亚像素运动估算快速判定方法，优化亚像素快速搜索模型，从搜索区域和曲面单峰特征缩小搜索范围，根据极值点和1/2亚像素最优点之间的距离来判定是否进行1/4像素的搜索，以此降低编码时间；本发明的关键创新点是能够大幅降低HEVC标准的编码运算量和提高编码效率。

说明书

技术领域

本发明涉及一种HEVC帧间像素搜索改进方法，特别涉及一种HEVC帧间运动估算像素搜索改进方法，属于HEVC帧间像素搜索技术领域。

背景技术

当今，移动互联网和通信技术飞速发展，多媒体已成为人们获取信息最主要的载体，多媒体信息数据量大，且信息丰富。视频影像作为重要的多媒体，能提供丰富的视觉和听觉感知，因此视频技术得到越来越多的重视。由于视频信息内容的丰富性，视频技术的应用范围很广，如现上视频通话、商业视频会议、体育娱乐直播、电子商务政务、互联网教学、短视频、远程医疗等等业务。因为传送的数据量很大，所用的视频应用数据必须压缩，压缩之后，不论是存储的比特数还是传送的比特数都将大幅减少，如此一来解决了存储问题和传送高带宽问题，视频编码的发展随着应用场景的需求而变化，近年来基于视频的应用服务不断提高和升级，而其重要的视频编码技术要想应对这种发展趋势，则更要升级和改进。

人们对于移动互联网所提供的生活学习方面的要求更多，人们也希望视频的分辨率越高越好，高清和超高清视频的分辨率越高，包含的信息量越大，也意味着传输量越大，这给传输通道和存储空间带来了很大的压力。未经压缩的数字视频比特数是一个不小的数目，应用于实际传输和存储，将耗费大量的传输带宽和存储空间。然而，高分辨率已是视频发展的必然趋势，为了使得有限的存储能力和一定的带宽取得更优的平衡，对压缩也提出更高的期待。面对视频发展的趋势，现有技术的视频编码出现了一些无法靠自身已有的技术解决的问题：

第一，高分辨率视频意味着每帧图像的宏块数目会成倍增加，同时编码单元的划分、预测单元的预测模式、参考帧和序列、变换单元信息、整像素和亚像素的运动矢量、量化参数等信息都将需要更多的编码信息来记录，假如依然采用H.264编码码率，用来表示残差部分的编码信息将明显减少，不能很好的表达视频信息；

第二，随着视频中图像分辨率的增加，H.264中的宏块尺寸表示的图像信息过于细节化，但无法表述很多图像信息，相邻的残差块的信息可能非常相近，经过变换和量化后的低频系数会相近，甚至相同，这样传输相近的信息会增加传输带宽；

第三，现有技术如H.264使用哥伦布指数编码，编码方式不使用固定的信号量表示运动矢量信息，而是根据值的大小决定信号量的大小，由于高分辨率的图像表示的信息更加细节化，统一运动矢量相对于之前的幅值会大幅增加，编码后的运动矢量比特数将大幅增加很多，压缩率将降低。

第四，高分辨率带来更大的信息量，压缩的同时还要考虑压缩效率，面对大量信息处理，最好的办法是将信息分成多个部分，同时并行化处理，然而现有技术很多算法不能很好的并行化，更多地采取串行编码。现有技术应用局限性和视频发展趋势的矛盾越来越明显。

视频压缩的目标是在保证使用尽量少的信息量表达内容的同时要获得原视频的效果，为了应对越来越庞大的传输信息量，对新的视频编码标准的要求越来越高，为了获得更好的压缩率，编码的计算量也对应提高，复杂度是和编码时间成正比的，基于此，为了能够使得编码算法编码效率更高和时间消耗最少，在这之间找到最优的平衡点。压缩能起到有效减少资源的作用，减少存储空间和降低传输容量，压缩是一个时间与空间之间的折中，设计数据压缩方案包括很多因素之间的折中，包括压缩程度，引入的失真量和压缩时需要的计算资源，来自于各种类型的数字视频由于高码率使得通过预期的通道变得很困难，即便是高带宽技术准备就绪，也要保证每字节的传输成本很低，这样才能将其应用到数据量惊人的高清视频和超高清视频。

数字视频诞生之后，视频编解码技术一代又一代不断发展，越来越成熟，数字视频的分辨率不断升高，也在推动编码技术的前进，每种视频编码标准都是在对应应用的推动下构建的，1990年VCEG制定了第一个较为实用的视频编码标准H.261，标准采用了对后来影响广泛的混合编码框架，主要是将其运用在ISDN，它能以64kbit/s的基础码率或数倍的码率进行传输，支持码率为64-2048kbit/s，同时，ISO/IEC推出了MPEG-1标准，压缩过程是有选择的丢失部分信息，主要用于数字音响信息系统的存储。为满足电视观众对于数字高清和标清的需求，VCEG和MPEG联合制定了MPEG-2/H.262标准，它的信息传输能力提高到30Mbps，为了使得可视电话和视频会议能够更清晰拥有更好的传输质量，ITU-T制定了H.263标准，在后来还推出了H.263+和H.263++两个增强性能的版本。为了更好地推动和发展我们的信息产业，由于移动互联网、网络视频和家庭影院对高清视频的需求，我国制定了与H.264编码效率相当的AVS标准，但其算法复杂度相对更低，而且能更好的适应当前的硬件。

MPGE和VCEG两大组织的专家成员共同组成了视频编码联合协作小组，共同制定了新一代视频标准，并进一步研究、制定与完善，将HEVC定为标准，HEVC的主要目标包括：在保证视频质量相同或相近条件下，与H.264相比平均减少50％的码流，在同码流条件下提供更高质量的视频，简化编解码部署，最大限度提高互操作性，以MPEG流进行传送将很好的利用互联网络传输设备。

HEVC的成果展现形式是编解码软件，数字视频的处理标准由软件执行，这个软件发布之后成为统一工具，发布的同时还有统一的不同分辨率的测试视频，之后在广州会议上推出了正式测试工具HM，HM随着每一次会议的召开，都会有新的成果加入标准中，使得HM版本不断更新，大量的新技术或者应用被提出，目的是寻找最大程度去除冗余信息和降低运算复杂度之间的平衡点，以达到压缩率尽量大和复杂度尽量低的要求。

视频压缩过程中尽可能去除视频中的冗余信息，降低传输所需的带宽和存储所需的空间，关键技术包括：增加帧内亮度与色度预方向数目、帧间预测分数插值更精细化、变换和量化、指定熵编码方法、像素自适应偏移等。帧间图像预测中的运动估算是编码中计算量较大的部分，其中整像素搜索是整像素矢量的查找，亚像素查找亚像素运动矢量，亚像素运动估算更耗时。运动补偿过程是对编码质量的进一步提高，而运动估算是整个编码过程比较耗时的一个过程，通过对运动估算优化减少计算量提高编码效率。

现有技术没有很好的解决HEVC帧间运动估算像素搜索问题，现有技术的难点和本发明解决的问题主要集中在以下方面：

第一，面对不断增长的高清视频需求，高效视频编码HEVC需要实现更高的目标，即在获得相同或者相近的画质的情况，码率能减少一半，虽然HEVC获得了更优越的压缩性能，却使得计算量显著增加并且编码复杂度增加，实验发现运动估算的计算量占整体过程的58％以上，本发明急需解决的问题在于降低HEVC标准的编码运算量和提高编码效率，现有技术还没有一种性能优异、追踪效果稳定的多目标追踪的解决方法；

第二，高分辨率视频意味着每帧图像的宏块数目会成倍增加，现有技术用来表示残差部分的编码信息将明显减少，不能很好的表达视频信息，传输相近的信息会增加传输带宽；由于高分辨率的图像表示的信息更加细节化，统一运动矢量相对于之前的幅值会大幅增加，编码后的运动矢量比特数将大幅增加很多，压缩率降低；现有技术很多算法不能很好的并行化，更多地采取串行编码，现有技术应用局限性和视频发展趋势的矛盾越来越明显；

第三，现有技术整像素运动估算搜索算法包括全搜索、三步搜索、新三步搜索，全搜索算法能较准确的找到最优匹配像素点，但计算量过大也是其无法在实际应用中使用的缺点，三步搜索方法先使用固定步长采取较大范围的搜索，找到最优点大致的范围，而后缩减步长，精细搜索，找到最优点，算法较稳定，但三步搜索算法的初始步长较大，往往会偏离正确的搜索方向，陷入局部最优，在匹配时容易出现匹配误差；

第四，虽然HEVC获得了更优越的压缩性能，却使得计算量显著增加并且编码复杂度增加，运动估算的计算量占整体过程的58％以上，现有技术缺少降低HEVC标准的编码运算量和提高编码效率的方法，存在编码时间长，同时编码质量得不到保证的问题，由于HEVC减少编码时间，同时主观效果好的实现本身就是一个复杂的困难过程，需要考虑的因素很多，简而言之就是在确保降低编码运算量和提高编码效率的同时，对高清视频质量进行较大提升存在诸多困难。

发明内容

针对现有技术的不足，面对不断增长的需求，新一代高效视频编码HEVC需要实现更高的目标，即在获得相同或者相近的画质的情况，码率能减少一半。虽然HEVC获得了更优越的压缩性能，却使得计算量显著增加并且编码复杂度增加，实验发现运动估算的计算量占整体过程的58％以上，本发明的关键创新点在于降低HEVC标准的编码运算量和提高编码效率。

为达到以上技术效果，本发明所采用的技术方案如下：

HEVC帧间运动估算像素搜索改进方法，解析HEVC运动估算对应的编码流程，对运动估算的对应流程进行改进，在整像素块匹配过程中，调整搜索方法，采用不规则水平和竖直六边形相结合的搜索方法，经过整像素估算后通过临界值和SAD的比较，判定是否进行进一步的亚像素估算；在亚像素估算中，首先构建单峰误差曲面模型，根据此模型确定亚像素最优点的搜索区域，减少搜索点数，然后利用距离临界值进行判定，中断一部分1/4像素的搜索；具体包括：

第一，改进整像素搜索方法，提出整像素搜索改进模型及方法，主要包括不规则六边形搜索改进模型及方法；在现有技术的整像素搜索方法的基础上改进六边形旋转搜索为不规则六边形搜索，在较为准确的整像素搜索之后，亚像素搜索可忽略跳过，通过对编码后的运动矢量及SAD值进行解析，设置适合的块临界值判定是否可以跳过亚像素估算；

第二，实现亚像素运动估算快速判定，主要包括亚像素快速搜索优化模型和条件、亚像素快速搜索步骤流程；亚像素在搜索区域内匹配曲面具有单峰极值的性质，亚像素的搜索区域在整像素最优点周围(-0.5,0.5)×(-0.5,0.5)区域内，由整像素最优点与其上下左右4个相邻点构建5点单峰曲面模型，误差曲面模型的曲面顶点确定最优搜索区域，有效减少亚像素搜索的点数，最优1/2像素点坐标与误差曲面的极值点坐标的距离值和1/4最优与1/2最优像素点的重合概率成近似反比例关系，根据重合概率选择适合的距离临界值，跳过一部分1/4像素运动矢量的估算；

本发明对HEVC帧间运动估算像素搜索模型进行改进，采用不规则六边形搜索改进模型，更好的适应现实视频中运动倾向于水平和竖直方向运动的特征，利用临界值判定是否进行亚像素的搜索，有效减少亚像素搜索过程，提出亚像素运动估算快速判定方法，优化亚像素快速搜索模型，从搜索区域和曲面单峰特征缩小搜索范围，根据极值点和1/2亚像素最优点之间的距离来判定是否进行1/4像素的搜索，降低编码时间。

HEVC帧间运动估算像素搜索改进方法，进一步的，不规则六边形搜索改进模型及方法：基于HEVC标准的编码单元CU块大小和实际运动规律，对六边形旋转搜索模型进行改进，并对算法进行优化，采用不规则六边形模型中水平和竖直六边形，将六边形模型与菱形模型进行融合，让水平六边形更侧重水平方向的运动矢量，让竖直六边形更侧重竖直方向的运动矢量，然后通过水平、竖直六边形的融合完成快速搜索；

不规则六边形搜索改进搜索方法在搜索过程中，进行模型的选择，运动中水平运动的概率更高，默认的模型为水平六边形，搜索模型为水平六边形时，bMode的值设为1，为竖直六边形时，bMode的值设为0，具体搜索流程为：

步骤一：采用最大搜索步长进行水平六边形搜索，得到最优点，假如是中心点，则跳到步骤三；

步骤二：使用步骤一得到的最优点为中心，搜索步长减半，bMode取非，进行对应的六边形搜索，若搜索步长不为1转入步骤二；否则转入步骤三；

步骤三：搜索步长为1时，对周围4点进行匹配，得到整像素精度的最优运动矢量。

HEVC帧间运动估算像素搜索改进方法，进一步的，在帧间预测模式的运动估算判定中，引入绝对误差和SAD作为判定准则；在HEVC的帧间运动估算中，对当前编码单元CU遍历其可能的分割方式，而在每种分割方式之中确定其最优运动矢量：按照一定的搜索方法进行搜索，对每个候选位置计算SAD值，得到全局SAD最小的候选位置，也即得到了最优运动矢量，但在求当前块的最优SAD过程中，包含帧间运动估算中两个主要的耗时模块：整像素运动估算，包括运动矢量搜索过程；亚像素运动估算，包括1/2、1/4像素精度的插值过程及其对应的搜索过程，其中亚像素估算模块的耗时几乎是整像素估算模块耗时的2倍；但对于某些块，整像素估算得到的SAD

选定的临界值Ljz为经验值，如果当前块整像素估算得到的SAD满足以下条件：SAD＜Width×Height×Ljz，则跳过亚像素估算；否则继续做亚像素估算。

HEVC帧间运动估算像素搜索改进方法，进一步的，亚像素快速搜索优化模型和条件：亚像素的搜索区域误差匹配曲面有单峰极值，存在某一点，其周围各点的幅度值随着距离增大都不断增大，表明这一点是一个极值点，在块匹配时，匹配准确度随着与这一点的距离增大而误差增大，根据单峰曲面的性质，利用Rdcost匹配原则找到最优点所在的更小的区域，在更小的范围内搜索，提高搜索效率，最优整像素点及其周围4个点组成的5点误差曲面模型得出的极值点，这个极值点所在的范围始终在(-0.5,0.5)×(-0.5,0.5)的范围内。

HEVC帧间运动估算像素搜索改进方法，进一步的，亚像素的搜索范围的单峰曲面特征，二次曲面能很好的描述亚像素搜索范围内的误差函数，其中抛物面是很好的选择，抛物面的特征能很好的体现误差曲面的全局存在最小极值点、误差曲面具有单峰特征，亚像素运动矢量计算过程中，本发明采用5点误差曲面抛物面模型来近似计算误差曲面，数学式表示为式1：

g

其中，A、B、C、D、E在给定的模型上通过符合整像素点RDcost进行估算，RDcost的定义为：

RDCost＝SatD(m，n)+λT(m，n) 式2

其中，SatD(m,n)是代表运动矢量(m,n)的SatD值，T(m,n)是运动矢量的成本，并且λ是拉格朗日乘数，只需要5个点构建误差曲面，也就是指最优整像素点和附近的4个整像素点，最小化简单且最小的点的位置可计算为：

利用上式，带入对应值，计算出最小点之后，最小点所在的区域作为搜索最优点的搜索区域，也即找到最优匹配点所在的区域。

HEVC帧间运动估算像素搜索改进方法，进一步的，搜索区域模型中，假设Q

g

式中，g

为找到式4的极值点，分别对式4进行x和y一阶求导，解一元二次方程得到曲面的极值点，由极值点进一步缩小亚像素的搜索区域，如式3，结合式1，推出式6，

将各点的RDCost值代入式6中，得到曲面的极值点，亚像素在搜索区域内误差匹配曲面具有单峰曲面的特征，误差曲面模型的极值点始终在某个特定的小范围内；

融合单峰曲面特征和搜索范围的限定特征，对亚像素运动估算方法进行改进：根据已经找到的整像素最优点及临近的4点，构建5点单峰曲面模型，算出该模型的极值点，此极值点判定亚像素的搜索区域，较小区域表明较少的搜索点数，在已找到的搜索范围内进一步根据块匹配准则RDCost确定最优1/2像素点，再根据1/2最优像素点及其周围1/4像素点判定最优1/4像素点，根据判定条件是否中断1/4像素搜索。

HEVC帧间运动估算像素搜索改进方法，进一步的，在兼顾图像质量的同时，使得耗时减少，寻找一种更好的平衡，可以中断1/4像素的条件；当1/4最优像素点和1/2最优像素点重合时，再进行1/4最优像素点搜索完全无必要，已经不能增加精确度，同时两者相距很近时也不能提高精确度，会损失微小的质量，中断实施时合理选择两者的距离保证可接受的图像质量；

基于实验分析，1/2最优像素点与1/4像素最优像素点的重合或者相近跟极值点和1/2最优像素点之间的距离有关联，当误差曲面得到的极值点和1/2最优像素点越近，表明估算的精确度已经很高，当达到某个精确度时，不再进行1/4像素的搜索，由此对测试序列进行测试，解析亚像素最优点之间的重合概率与极值点和1/2最优整像素点距离之间的关系，两者距离越小，重合的概率越高。

HEVC帧间运动估算像素搜索改进方法，进一步的，亚像素快速搜索步骤流程为：

第一步，找到1/2像素最优点；已经确认并分割搜索的区域，划分为4个分区域，计算极值点进一步确认搜索的区域，确定4个搜索区域中的一个，亚像素插值之后的区域较小且认为在区域(-0.5,0.5)×(-0.5,0.5)内，进一步将搜索区域锁定在像素搜索模型中；

第二步，由条件判定是否中断1/4像素搜索；找到中断进行1/4像素的条件，当1/4像素最优点和1/2像素最优点的距离很近或重合时，就可以跳过1/4像素的搜索，否则就要进行1/4像素过程的搜索，这样的情况能保证很高的精确度，设置一个适合的极值点与1/2最优像素点距离临界值，满足此条件时跳过部分1/4像素，同时保证编码的质量和效率，对编码质量造成了极小的损失，但换来更高的编码效率；

第三步，1/4像素的搜索，在划分的某一个区域中进行搜索，1/4像素值由插值得到，这个区域由最优1/2像素点的位置确定。

HEVC帧间运动估算像素搜索改进方法，进一步的，六边形搜索改进模型及方法：六边形搜索使用6点的六边形，假设现实运动中的各个方向的运动同等概率，六边形搜索算法的搜索流程为：

步骤一：设置搜索窗口的中心为中心点，根据匹配原则，计算六边形搜索模型的7个点(包含中心点)的SAD值，如果最优匹配点位于中心点，则转入步骤三，否则转入步骤二；

步骤二：将步骤一得到的最优点作为中心点并进行新的六边形搜索，如果得到的最优点为中心点则转入步骤三，否则继续步骤二；

步骤三：将步骤二得到的最优匹配点作为中心点，搜索与该点相邻的4个点，得到最优匹配点；

六边形搜索步骤：先进行标示为1的六边形搜索，得到左边的点为最优点，然后以这个点作为中心点进行标示为2的六边形搜索，得到左上点为最优点而后进行标示为3的六边形搜索，中心点为最优点，在邻近4个点和中心点之间找到最优点。

HEVC帧间运动估算像素搜索改进方法，进一步的，六边形旋转搜索改进模型及方法：将六边形搜索模型改进为六边形旋转搜索模型，采用水平六边形和竖直六边形相结合的方法，更加精准地找到运动矢量的方向，间接提高运动估算的准确率，流程为：

搜索模型为水平六边形时，bMode的值设置为1，搜索模型为竖直六边形时，bMode的值设置为0；

第1步：设搜索窗口的中心为中心点，默认先进行水平搜索，bMode的值为1，根据匹配原则，计算六边形搜索的7个点的SAD值，如果最优匹配点位于中心点，则转入第3步，否则转入第2步；

第2步：将第1步得到的最优点作为中心点并进行新的六边形搜索，步长减半，新的六边形采用与第1步不同的六边形，bMode的值取反；如果得到的最优点为中心点则转入第3步，否则继续第2步；

第3步：将第2步得到的最优匹配点作为中心点，搜索与该点相邻的4个点，得到最优匹配点。

与现有技术相比，本发明的贡献和创新点在于：

第一，本发明基于整像素搜索模型的搜索核心过程和对应的优缺点，对搜索模型进行改进，采用不规则六边形搜索改进模型，更好的适应现实视频中运动倾向于水平和竖直方向运动的特征，利用临界值判定是否进行亚像素的搜索，有效减少亚像素搜索过程，提出亚像素运动估算快速判定方法，优化亚像素快速搜索模型，从搜索区域和曲面单峰特征缩小搜索范围，根据极值点和1/2亚像素最优点之间的距离来判定是否进行1/4像素的搜索，以此降低编码时间；本发明的关键创新点是能够大幅降低HEVC标准的编码运算量和提高编码效率。

第二，本发明HEVC的整像素搜索模型和亚像素的搜索过程，在应用中有各自的好处，但不同的应用场合，对效果有着不同要求，为了达到一个平衡的效果，在改进的过程中适当的选择适合的临界值，Ljz的临界值取为5的测试结果表明，HEVC整像素运动矢量占总体运动矢量的32％左右，整像素的优化空间很大，也很有必要，同时亚像素的运动矢量的比例较高，能够利用临界值中断亚像素搜索，减少亚像素的搜索是优化运动估算的有效途径；本发明的整像素搜索改进模型及方法相对于菱形搜索、六边形搜索和六边形旋转搜索，在时间上能够有效的减少，整像素的比例能够明显上升，整体亚像素比例能够明显减少，而同时PSNR的减少只有平均0.079db；

第三，本发明算法和常见的几种整像素搜索模型进行比较发现，编码后的视频质量几乎没有损失，但却实现了帧间的快速算法，大幅减少了编码时间，与HEVC标准默认采用的菱形搜索模型相比，编码时间平均减少51.25％，使用的测试序列在时间优化的效果上基本一致，达到了实验预期的目标。此外，通过细节比较发现，视频的主观质量与初始编码效果几乎没有区别，通常PSNR的值大于32且主观质量良好时，表明当前图像能够很好的表示初始图像，实验的测试序列图像的PSNR均大于32且主观质量很好，从而验证了本发明方法的可靠性；

第四，本发明对六边形旋转模型进行改进，模型变为不规则的六边形，使得两个搜索模型在水平和竖直方向上更加能够体现实际运动的方向，这样能够更好的预测实际物体的运动方向，运动矢量更加准确，同时也根据找到最优整像素块的SAD值进行判定，当SAD值小于临界值时，表明当前的匹配已经达到预想的准确度，不再进行亚像素的搜索，由此设置实验得出的临界值，当最优匹配块的SAD值满足条件时，跳过亚像素搜索，节省编码时间；由于亚像素搜索的范围较小且能划定指定的范围，而且待匹配的像素点并没有整像素那么多，所以亚像素采取更为简单的搜索方法，基于融合亚像素搜索模型，采用较为简单的五点误差曲面构建误差匹配曲面，由极值点在已经划分的区域确定更小的范围，再根据判定原则RDCost判定最优1/2像素点，实验发现大量的1/2最优像素点和1/4最优像素点重合，重合概率和曲面极值点与1/2最优极值点的距离相关，根据实验测试序列得到两者之间的关系图，然后选择适合距离值来作为判定1/4像素搜索中断的条件，否则，还继续进行1/4像素的搜索；对本发明的整像素搜索模型和现有技术对比，记录整像素矢量和亚像素矢量的变化，反应出优化后整像素矢量增加，亚像素矢量减少，这样可以大幅优化编码时间，同时编码质量得到保证，然后对整个优化方法进行测试，发现优化之后的方法能够大幅减少编码时间，同时主观效果很好。

附图表明

图1是HEVC标准使用的各类搜索模型示意图。

图2是大模型被重复利用时相邻检测点的3种覆盖情况示意图。

图3是本发明的不规则六边形模型中水平和竖直六边形示意图。

图4是本发明的单峰曲面模型和划分的搜索区域示意图。

图5是本发明的距离与搜索重合率的关系示意图。

图6是本发明的亚像素快速搜索流程示意图。

图7是亚像素快速搜索的1/4像素搜索模板示意图。

图8是整像素搜索模型实验测试结果视频的截图。

具体实施方式

下面结合附图，对本发明提供的HEVC帧间运动估算像素搜索改进方法的技术方案进行进一步的描述，使本领域的技术人员能够更好的理解本发明并能予以实施。

HEVC标准帧间预测有Skip、Merge、Normal三种模式，其中Skip模式为Merge模式的一种，当采用Skip模式时，不对编码单元CU进行分割，而且与Merge模式一样，其运动矢量、参考图像索引及参考图像列表使用标志都由运动合并得到，当且仅当在Normal模式下存在运动估算过程，由AMVP得到邻域最优运动矢量后，进行运动搜索确定整像素最优运动矢量，然后以该矢量为中心进行1/2、1/4像素精度的插值，而后进行亚像素搜索，综合得到全局最优运动矢量。

本发明针对HEVC运动估算算法的理论和流程提出新的优化方法，在整像素块匹配过程中，调整搜索方法，采用不规则水平和竖直六边形相结合的搜索方法，经过整像素估算后通过临界值和SAD的比较，判定是否进行进一步的亚像素估算，在亚像素估算中，首先构建单峰误差曲面模型，根据此模型确定亚像素最优点的搜索区域，减少搜索点数，然后利用距离临界值进行判定，中断一部分1/4像素的搜索。

本发明解析HEVC运动估算对应的编码流程，为了提高编码效率，降低编码复杂度和计算量，对运动估算的对应流程进行改进，第一，改进整像素搜索方法，在现有技术的整像素搜索方法的基础上改进六边形旋转搜索为不规则六边形搜索，实验结论表明，在较为准确的整像素搜索之后，亚像素搜索可忽略跳过，通过对编码后的运动矢量及SAD值进行解析，设置适合的块临界值判定是否可以跳过亚像素估算；第二，对亚像素运动估算过程的解析发现，亚像素在搜索区域内匹配曲面具有单峰极值的性质，亚像素的搜索区域在整像素最优点周围(-0.5,0.5)×(-0.5,0.5)区域内，由整像素最优点与其上下左右4个相邻点构建5点单峰曲面模型，误差曲面模型的曲面顶点确定最优搜索区域，有效减少亚像素搜索的点数，最优1/2像素点坐标与误差曲面的极值点坐标的距离值和1/4最优与1/2最优像素点的重合概率成近似反比例关系，根据重合概率选择适合的距离临界值，跳过一部分1/4像素运动矢量的估算；第三，整个帧间运动估算分法优化整合之后，统一视频源在相同码率下，主观效果与初始未经编码效果相近，与HEVC中默认的菱形搜索模型相比，虽然平均PSNR基本相同，但平均编码时间减少了51.23％。

一、整像素搜索改进模型及方法

(一)菱形搜索改进模型及方法

HEVC标准默认使用的搜索模型为全搜索、菱形搜索和平方搜索，其中菱形模型分为8点大模型和4点小模型，如图1(a)所示，特别当搜索步长大于8时，采用图1(b)所示模型；平方搜索模型如图1(c)所示，HEVC默认搜索模型为菱形搜索，菱形搜索的性能要优于其它两种搜索模型。

HEVC标准菱形搜索为8点(加上中心点即为9点)LDSP大模型和4点(加上中心点即为5点)SDSP小模型，HEVC标准先采用大模型进行粗定位，然后使用小模型进行精细定位，具体流程为：

步骤1：粗搜索，确定搜索范围的搜索边界，搜索起始的中心点由AMVP确定，搜索步长从1开始直至最大搜索步长，步长逐次以二次幂增长；当步长Dist为1时即对应于小模型，否则采用大模型，在每一次搜索后，保存当前最优候选位置(i,j)，继续搜索三次，(i，j)依然为最优点，则停止搜索，即第一次搜索停止方法；

步骤2：光栅搜索，当第一次搜索结束后，如果步长Dist＞iRaster(默认设置为5，可更改)，则进行光栅搜索：将搜索窗口分为若干个iRaster×iRaster的方形，搜索步长设置为iRaster，并对每个方形的左上角进行匹配，然后得到最优候选位置，采用光栅搜索能在搜索窗口内快速确定理想的候选位置，同时也将搜索步长迅速减小至iRaster，进一步缩小搜索范围，减小此后进行精确定位的计算量；

步骤3：精细搜索，采用Start Refinement精细搜索方法，搜索步长的选取从1开始，以二次幂形式增长进行菱形搜索，以最优候选位置为中心进行下一次搜索，其对应的步长为最优步长，搜索直至最优步长为最大步长，此过程中采取快速停止方法；

搜索过程中，当大模型被重复利用时，需要注意相邻的步骤之间检测点间部分重叠，如图2为相邻检测点的3种覆盖情况，当之前的最小块失真点位于大模型的角落或边界上，只有5个或3个新的检测点需要被检测，如图2(a)和2(b)，若大模型的中心点是最小块失真，在最后的搜索中搜索模式从LDSP大模型变化到SDSP小模型，只有4个点需要检测，如图2(c)。

在经过以上过程后，即可得到整像素级别的最优运动矢量，但在这个过程中，尤其是Start Refinement，在搜索结束前，虽然此过程采用了快速停止方法，但每次搜索均是从1直至最大搜索步长，以较高的计算复杂度来获取优异的性能，在优化方法上需对此做出改善，或提出新的搜索方法，菱形搜索模型被MPEG-4标准采纳，搜索模型不仅制约搜索速度，还影响整体匹配精度：搜索窗口太小，会出现局部最优匹配，搜索窗口太大，会导致额外的计算量并有可能出现误匹配，菱形搜索算法采用5点的小模型和9点的大模型两种搜索模型。

(二)六边形搜索改进模型及方法

六边形搜索核心算法与菱形搜索算法类似，但六边形搜索使用6点的六边形，而不是8点菱形大模型和4点小模型，假设现实运动中的各个方向的运动同等概率，六边形搜索算法的搜索流程为：

步骤一：设置搜索窗口的中心为中心点，根据匹配原则，计算六边形搜索模型的7个点(包含中心点)的SAD值，如果最优匹配点位于中心点，则转入步骤三，否则转入步骤二；

步骤二：将步骤一得到的最优点作为中心点并进行新的六边形搜索，如果得到的最优点为中心点则转入步骤三，否则继续步骤二；

步骤三：将步骤二得到的最优匹配点作为中心点，搜索与该点相邻的4个点，得到最优匹配点。

六边形搜索步骤：先进行标示为1的六边形搜索，得到左边的点为最优点，然后以这个点作为中心点进行标示为2的六边形搜索，得到左上点为最优点而后进行标示为3的六边形搜索，中心点为最优点，在邻近4个点和中心点之间找到最优点。

六边形模型充分考虑了更多的方向，搜索精度较高；同时相比于菱形搜索，它所采用的点数更少，搜索速度更快，在仅考虑搜索点数的情况下，对于64×64的搜索窗口(搜索步长为64)，当使用菱形搜索时，需计算的点数为52(6×8+4)；而如果采用六边形模型，则需要计算的点数仅仅为40(6×6+4)。理论上，对于每个搜索窗口，采用六边形模型后搜索效率提高了四分之一，而且这种计算效率的提高只是以PSNR的略有减少为代价的，这也是模型本身所能提供的估算精度决定的，在菱形模型中可以估算的方向为8个，而六边形模型只能提供6个估算方向，由于估算方向上精度的降低导致了PSNR的减少。

(三)六边形旋转搜索改进模型及方法

六边形搜索模型适用于H.264/AVC中的宏块，而HEVC标准对应的编码单元CU的大小增加至64×64，在这种搜索方法中对于不同运动复杂度的图像以固定步长进行搜索，导致搜索速度不稳定，而且水平、竖直六边形模型分别只侧重与水平、竖直方向的运动矢量，将六边形搜索模型改进为六边形旋转搜索模型。

为了使竖直和水平运动的表现无损失，六边形旋转采用水平六边形和竖直六边形相结合的方法，更加精准地找到运动矢量的方向，间接提高运动估算的准确率，六边形旋转的搜索方法和六边形的搜索方法相近，流程为：

搜索模型为水平六边形时，bMode的值设置为1，搜索模型为竖直六边形时，bMode的值设置为0；

第1步：设搜索窗口的中心为中心点，默认先进行水平搜索，bMode的值为1，根据匹配原则，计算六边形搜索的7个点(包含中心点)的SAD值，如果最优匹配点位于中心点，则转入第3步，否则转入第2步；

第2步：将第1步得到的最优点作为中心点并进行新的六边形搜索，步长减半，新的六边形采用与第1步不同的六边形，bMode的值取反；如果得到的最优点为中心点则转入第3步，否则继续第2步；

第3步：将第2步得到的最优匹配点作为中心点，搜索与该点相邻的4个点，得到最优匹配点。

(四)不规则六边形搜索改进模型及方法

本发明基于HEVC标准的编码单元CU块大小和实际运动规律，对六边形旋转搜索模型进行改进，并对算法进行优化，采用的不规则六边形模型中水平和竖直六边形如图3所示，现有技术的六边形模型采用类似圆的结构，该结构是基于运动矢量在各个运动方向都均匀分布的假设。但该假设并不符合实际运动规律，实际运动过程水平运动占据了较多的情形，比如走路、跑步、打篮球等，但竖直运动也有一定比例，比如打篮球中的跳投、扣篮和跳水等。

本发明将六边形模型与菱形模型进行融合，让水平六边形更侧重水平方向的运动矢量，让竖直六边形更侧重竖直方向的运动矢量，然后通过水平、竖直六边形的融合完成快速搜索。

不规则六边形搜索改进搜索方法在搜索过程中，进行模型的选择，运动中水平运动的概率更高，默认的模型为水平六边形，搜索模型为水平六边形时，bMode的值设为1，为竖直六边形时，bMode的值设为0，具体搜索流程为：

步骤一：采用最大搜索步长进行水平六边形搜索，得到最优点，假如是中心点，则跳到步骤三；

步骤二：使用步骤一得到的最优点为中心，搜索步长减半，bMode取非，进行对应的六边形搜索，若搜索步长不为1转入步骤二；否则转入步骤三；

步骤三：搜索步长为1时，对周围4点进行匹配，得到整像素精度的最优运动矢量；

不规则六边形三步搜索方法与HEVC标准采用的搜索算法相比，在搜索模型上使用的搜索点数少，在搜索方法上更简单，计算复杂度更低，模型方向更符合实际运动方向，在客观上减少了搜索过程的计算量和复杂度，而这些只是以PSNR略有减少为代价。

在帧间预测模式的运动估算判定中，引入绝对误差和SAD作为判定准则；在HEVC的帧间运动估算中，对当前编码单元CU遍历其可能的分割方式，而在每种分割方式之中确定其最优运动矢量：按照一定的搜索方法进行搜索，对每个候选位置计算SAD值，得到全局SAD最小的候选位置，也即得到了最优运动矢量。但在求当前块的最优SAD过程中，包含帧间运动估算中两个主要的耗时模块：整像素运动估算，包括运动矢量搜索过程；亚像素运动估算，包括1/2、1/4像素精度的插值过程及其对应的搜索过程，其中亚像素估算模块的耗时几乎是整像素估算模块耗时的2倍；但对于某些块，整像素估算得到的SAD

选定的临界值Ljz为经验值，如果当前块整像素估算得到的SAD满足以下条件：SAD＜Width×Height×Ljz，则跳过亚像素估算；否则继续做亚像素估算。

二、亚像素运动估算快速判定

(一)亚像素快速搜索优化模型和条件

亚像素的搜索区域误差匹配曲面有单峰极值，存在某一点，其周围各点的幅度值随着距离增大都不断增大，表明这一点是一个极值点，在块匹配时，匹配准确度随着与这一点的距离增大而误差增大，根据单峰曲面的性质，利用Rdcost匹配原则找到最优点所在的更小的区域，在更小的范围内搜索，提高搜索效率，最优整像素点及其周围4个点组成的5点误差曲面模型得出的极值点，这个极值点所在的范围始终在(-0.5,0.5)×(-0.5,0.5)的范围内；

亚像素的搜索范围的单峰曲面特征，二次曲面能很好的描述亚像素搜索范围内的误差函数，其中抛物面是很好的选择，抛物面的特征能很好的体现误差曲面的全局存在最小极值点、误差曲面具有单峰特征。亚像素运动矢量计算过程中，本发明采用5点误差曲面抛物面模型来近似计算误差曲面，数学式表示为式1：

g

其中，A、B、C、D、E在给定的模型上通过符合整像素点RDcost进行估算，RDcost的定义为：

RDCost＝SatD(m，n)+λT(m，n) 式2

其中，SatD(m,n)是代表运动矢量(m,n)的SatD值，T(m,n)是运动矢量的成本，并且λ是拉格朗日乘数。9整像素点的位置如图4，最优整像素Q

利用上式，带入对应值，计算出最小点之后，最小点所在的区域作为搜索最优点的搜索区域，也即找到最优匹配点所在的区域，有效地缩小搜索区域，提高搜索效率。

如图4所示的搜索区域模型中，假设Q

g

式中，g

为找到式4的极值点，分别对式4进行x和y一阶求导，解一元二次方程得到曲面的极值点，由极值点进一步缩小亚像素的搜索区域，如式3，结合式1，推出式6，

将各点的RDCost值代入式6中，得到曲面的极值点，亚像素在搜索区域内误差匹配曲面具有单峰曲面的特征，误差曲面模型的极值点始终在某个特定的小范围内；

融合单峰曲面特征和搜索范围的限定特征，对亚像素运动估算方法进行改进：根据已经找到的整像素最优点及临近的4点，构建5点单峰曲面模型，算出该模型的极值点，此极值点判定亚像素的搜索区域，较小区域表明较少的搜索点数，在已找到的搜索范围内进一步根据块匹配准则RDCost确定最优1/2像素点，再根据1/2最优像素点及其周围1/4像素点判定最优1/4像素点，根据判定条件是否中断1/4像素搜索。

亚像素运动估算耗时占比很大，假如能在兼顾图像质量的同时，使得耗时减少，寻找一种更好的平衡，基于实验分析，可以中断1/4像素的条件；

当1/4最优像素点和1/2最优像素点重合时，再进行1/4最优像素点搜索完全无必要，已经不能增加精确度，同时两者相距很近时也不能提高精确度，会损失微小的质量，中断实施时合理选择两者的距离保证可接受的图像质量。基于实验测试序列结果分析，1/4最优像素点和1/2最优像素点重合的概率平均达到51％，这样大的比例如果能提前中断搜索过程，将能够显著减少编码时间。

基于实验分析，1/2最优像素点与1/4像素最优像素点的重合或者相近跟极值点和1/2最优像素点之间的距离有关联，当误差曲面得到的极值点和1/2最优像素点越近，表明估算的精确度已经很高，当达到某个精确度时，不再进行1/4像素的搜索，由此对测试序列进行测试，解析亚像素最优点之间的重合概率与极值点和1/2最优整像素点距离之间的关系，如图5所示，图5中纵轴代表1/2像素最优点的实际位置与极值点的距离，横轴代表1/4像素最优点与1/2像素最优点的重合的概率，由此图得出，两者距离越小，重合的概率越高。

(二)亚像素快速搜索步骤流程

如图6的亚像素快速搜索流程图所示，亚像素快速搜索步骤流程为：

第一步，找到1/2像素最优点；已经确认并分割搜索的区域，如图4所示，划分为4个分区域，计算极值点进一步确认搜索的区域，确定4个搜索区域中的一个，亚像素插值之后的区域较小且认为在区域(-0.5,0.5)×(-0.5,0.5)内，进一步将搜索区域锁定在如图7所示的像素搜索模型中，其中圆点、方形和三角形分别代表整像素、1/2像素和1/4像素，中心点为最优整像素点，例如极值点(x

第二步，由条件判定是否中断1/4像素搜索；找到中断进行1/4像素的条件，当1/4像素最优点和1/2像素最优点的距离很近或重合时，就可以跳过1/4像素的搜索，否则就要进行1/4像素过程的搜索，这样的情况能保证很高的精确度，设置一个适合的极值点与1/2最优像素点距离临界值(比如0.05像素)，满足此条件时跳过部分1/4像素，同时保证编码的质量和效率，对编码质量造成了极小的损失，但换来了更高的编码效率；

第三步，1/4像素的搜索，在如图7所划分的某一个区域中进行搜索，1/4像素值由插值得到，这个区域由最优1/2像素点的位置确定，例如，当1/2像素最优点为点3时，1/4像素搜索模型如图7(b)所示，搜索区域1内的1/2像素最优点和距离该点最近的3个1/4像素点，其它的1/2像素最优点的1/4像素搜索模型如图7的像素搜索模型所示。

三、改进方法测试结果

HEVC标准的整像素搜索模型和亚像素的搜索过程，在应用中有各自的好处，但不同的应用场合，对效果有着不同要求，为了达到一个平衡的效果，在改进的过程中适当的选择适合的临界值，采用标准的视频测试序列进行测试。

(一)整像素搜索改进模型及方法测试结果

首先先对几种不同的整像素搜索模型进行测试，测试序列采用JCT-VC提供的标准测试序列，所有测试序列均为YUV420序列，测试时采用不同的码率，对PSNR-Mean、IntMV、1/2MV、1/4MV进行统计，其中PSNR-Mean为平均PSNR，IntMV为整像素级别MV、1/2MV、1/4MV分别为1/2、1/4像素精度级别MV，主要记录3种像素的百分比结果，这些方法包括菱形搜索模型，六边形搜索模型，六边形旋转模型和本发明改进的搜索算法。这些方法Ljz的临界值取为5的测试结果表明，HEVC整像素运动矢量占总体运动矢量的32％左右，整像素的优化空间很大，也很有必要，同时亚像素的运动矢量的比例较高，能够利用临界值中断亚像素搜索，减少亚像素的搜索是优化运动估算的有效途径。

经过整像素搜索优化和临界值中断之后，运动矢量的结构发生了明显变化，整像素运动矢量相对于初始HEVC模型中菱形搜索模型中的矢量，上升的平均比例达到51％，而其它两种整像素搜索模型也有明显的增加，由于六边形搜索模型的估算方向较少，而整像素矢量的基数较小，整像素的变化比较明显，是在HEVC标准，为了提高估算的精确度，亚像素运动矢量在总体运动矢量中占有更大的基数，而且在同一搜索方法视频序列和不同码率下，随着码率的升高，整像素运动矢量的比例都在增加，这也是因为随着码率的升高，需要进行的运动估算量较小。

本发明的整像素搜索改进模型及方法相对于菱形搜索、六边形搜索和六边形旋转搜索，在时间上能够有效的减少，整像素的比例能够明显上升，整体亚像素比例能够明显减少，而同时PSNR的减少只有平均0.079db。

(二)整体方法改进测试结果及解析

采用HM中整像素搜索模型作为参照，对本发明提出的方法进行对比测试，验证其有效性。测试序列采用JCT-VC提供的标准测试序列，所有测试序列均为YUV420序列，依次采用5种不同类型的测试序列，每一个类型代表某一类型的视频信息，测试采用8比特深度的lowdelay_P.cfg配置，考虑到应用视频编码中需传输一定量的I帧来保证编码传输的稳定性，提高抗噪性，故在lowdelay_P.cfg配置文件修改I帧周期为96，最大编码单元设置为64×64，编码单元的最大划分深度为4，量化参数(QP)为32。

图8是实验中测试结果视频的截图，分别是整像素搜索模型菱形模型、六边形模型、六边形旋转模型和本发明改进模型，相同帧数和相同码率的情形下的主观效果展示，由以上实验结果可得，本发明算法和常见的几种整像素搜索模型进行比较发现，编码后的视频质量几乎没有损失，但却实现了帧间的快速算法，大幅减少了编码时间，与HEVC标准默认采用的菱形搜索模型相比，编码时间平均减少51.25％，使用的测试序列在时间优化的效果上基本一致，达到了实验预期的目标。此外，通过细节比较发现，视频的主观质量与初始编码效果几乎没有区别，通常PSNR的值大于32且主观质量良好时，就表明当前图像能够很好的表示初始图像，实验的测试序列图像的PSNR均大于32且主观质量很好，从而验证了本发明方法的可靠性。

四、发明点总结

新一代视频编码标准HEVC自从制定以来，得到前所未有的发展，HEVC在编码效率和压缩效率之间找到平衡点，逐步得到广大开发者和用户的认可，将优秀的视频编码技术应用到实际设备中，视频编码技术将不断向前发展。如今，随着计算机技术和硬件设备的不断升级，HEVC的应用前景广泛，尤其是在网上购物、超高清电视电影、图形游戏、高清网络视频、异地教学医疗、网络名声古迹游览等多方面影响人们的学习、生活、娱乐和健康等。

HEVC编码的初始视频源首先按照标准规定进行图像分割形成编码单元，依据分割信息进一步划分，然后分别进行帧内预测和帧间预测，其中帧内预测包括亮度和色度预测，形成预测单元，保存参考序列的索引和预测模式信息，帧间预测包括运动估算和运动补偿，运动估算根据当前帧和参考帧的信息进行匹配找到最优匹配块，包括整像素和亚像素的搜索，分别找到最优像素点，记录运动矢量和参考帧索引以及预测模式信息，滤波及运动补偿，预测单元和编码单元做差找到残差块，进行变换和量化，而后将量化后的数据进行熵编码，形成比特流进行传输和储存。

本发明对六边形旋转模型进行改进，模型变为不规则的六边形，使得两个搜索模型在水平和竖直方向上更加能够体现实际运动的方向，这样能够更好的预测实际物体的运动方向，运动矢量更加准确，同时也根据找到最优整像素块的SAD值进行判定，当SAD值小于临界值时，表明当前的匹配已经达到预想的准确度，不再进行亚像素的搜索，由此设置实验得出的临界值，当最优匹配块的SAD值满足条件时，跳过亚像素搜索，节省编码时间；由于亚像素搜索的范围较小且能划定指定的范围，而且待匹配的像素点并没有整像素那么多，所以亚像素采取更为简单的搜索方法，基于融合亚像素搜索模型，采用较为简单的五点误差曲面构建误差匹配曲面，由极值点在已经划分的区域确定更小的范围，再根据判定原则RDCost判定最优1/2像素点，实验发现大量的1/2最优像素点和1/4最优像素点重合，重合概率和曲面极值点与1/2最优极值点的距离相关，根据实验测试序列得到两者之间的关系图，然后选择适合距离值来作为判定1/4像素搜索中断的条件，否则，还继续进行1/4像素的搜索。