一种基于分层运动估计的搜索方法及其实现系统

摘要

本发明公开一种基于分层运动估计的搜索方法及其实现系统，所述方法将当前帧和参考帧按照比例进行一次降采样，降采样层进行运动估计时，设置候选运动向量的步长为降采样后的2个整像素单位向量。所述系统包含亮度参考像素缓存模块，分层复用的PE阵列模块；PE阵列寄存器数据更新操作控制模块。本发明提出的方案仅通过一次4:1降采样，由原始图像层的16×16块变为8×8块，块匹配的特征较明显；同时设置降采样层的搜索步长为2来降低计算量，满足视频编码器的实时性。

说明书

技术领域

本发明属于多媒体的视频编码器硬件实现领域，具体地讲，是一种适用于FPGA与ASIC实现、基于分层运动估计的搜索方法及其实现系统。

背景技术

在视频编码器中，采用运动补偿的帧间预测编码是视频压缩的主要技术，而搜索窗大小、搜索策略、匹配准则直接影响编码器的性能。其中整像元运动估计是视频编码器中最复杂的模块之一，为了满足高清视频编码的实时性，可通过硬件加速来实现编码。视频编码器的硬件实现需要能在复杂度与性能间取得较好的平衡。

基于块匹配的搜索方法主要有全搜索，快速搜索，分级搜索等方法。其中全搜索是在搜索区内逐点搜索，通过准则函数例如SAD（Sum of AbsoluteDifference）值，即初始值和预测值的绝对误差和，通过对每一个候选运动向量进行计算而选取出SAD值最小的最佳匹配块。当图像分辨率较高，运动比较复杂情况下，需要在较大搜索窗内进行搜索,运算量是相当大的，为了实现实时运算，必须采取并行处理。为了减少搜索次数，又提出了多种快速搜索方法，如二维对数搜索方法、三步搜索法、共轭方向搜索法、正交搜索法、菱形搜索法等。快速搜索法的共同之处在于把使准则函数（SAD）趋于极小的方向视为最小失真方向，并假定准则函数在偏离最小失真方向时是单调递增的，即认为它在整个搜索区内是运动向量的单极点函数，有唯一极小值。快速搜索方法能减少大部分运算量，能显著提升搜索速度，但是率失真性能会有一定的下降，不利于硬件实现，主要是因为快速搜索方法的数据流控制不规整，不能有效利用片上的存储数据。

为此提出的分级搜索方法在减少运算量的同时，可取得接近全搜索的精度和性能，得到真实的运动位移矢量。在分级搜索方法中，先通过对原始图像低通滤波和亚取样得到该图像序列的低分辨率表示，再对所得的低分辨率图像进行全搜索。由于分辨率降低，搜索次数成倍减少，同时单次SAD计算需要计算资源也成倍减小，由此全搜索得到一个最优运动矢量。以该运动矢量作为在原始图像中搜索的起始点，开始进行精细搜索，此步搜索窗大小可相对减小，搜索次数相应减少，最终通过细搜索得到运动位移矢量的估计值。采用分级搜索的优点在于，搜索次数介于全搜索与快速搜索之间，且在各层搜索时可看成是全搜索，这样具有较规整的数据流和控制流，利于硬件实现。已有的基于分层运动估计的硬件通过两次降采样进行搜索，提高了搜索速度，但连续两次4:1降采样后得到的降采样层，由原始图像层的16x16块变为4x4块，这样导致块匹配时由于特征不够明显而容易找到伪最佳匹配块，影响了搜索性能。

发明内容

现有基于硬件实现的视频编码器无论采用全搜索方法还是分层搜索方法，均通过一定程度上牺牲硬件面积来换取速度，若搜索范围增加，则硬件消耗巨大，不利于FPGA或ASIC电路。本发的目的在于提出一种具有接近全搜索性能的分层搜索方法及相应的硬件实现系统，使其具有较高的搜索速度和较好的编码性能，满足高清编码器实时编码的要求。

为实现上述目的，本发明采取如技术下方案：

本发明所述的基于分层运动估计的搜索方法，具体为：将当前帧和参考帧按照比例进行一次降采样，降采样层进行运动估计时，设置候选运动向量的步长为降采样后的2个整像素单位向量。

进一步的，所述降采样得到4路降采样图像，多PE阵列在每一路降采样图像中进行4路并行搜索，同时另3路降采样图像并行搜索。

进一步的，所述方法中片上亮度像素缓存采用分类像素存储来实现降采样的搜索，即按降采样得到4种像素类型交错存储，同时分奇偶行与奇偶宏块列分开存储，共16种像素类型交错存储。

进一步的，所述PE阵列从亮度参考缓存读取数据复用，一次读取两种像素类型的16字节宽数据用于4路PE阵列的数据更新。

本发明中分层搜索的思想是：先将当前帧和参考帧按照比例降采样，L1层是L0层4:1降采样得到的图像，L0层是原图像层。搜索时先在第L1层上进行，候选MV搜索步长为2，计算SAD时候，用了4:1降采样精度，即64个像素点参与了SAD值计算。本发明提出的方案仅通过一次4:1降采样，由原始图像层的16x16块变为8x8块，块匹配的特征较明显；同时设置降采样层的搜索步长为2来降低计算量，满足视频编码器的实时性。

本发明中，降采样后得到4路降采样图像，通过对四个区域的降采样图像采取不同类型的像素点来实现4个区域的并行搜索。同时在L1层对每一个区域搜索时，进一步采用了4路并行搜索，提高搜索速度。采用基于率失真优化的支持可变大小块运动估计，块匹配代价函数取当前块与参考块的SAD值与运动矢量的编码比特消耗的加权和。在L1层块大小为8x8，通过求取最小的匹配代价函数便可以得到最优的运动矢量。在L0层搜索时，将以L1层最优运动矢量和视频编码器的运动预测模块得到的运动矢量为运动搜索起始点，在一个较小的搜索窗内进行全搜索，便可得到可变大小块的块匹配代价函数值，各种模式的匹配代价将用于编码器的亚像元运动估计与预测模式的选择。

本发明所述的一种基于分层运动估计的搜索方法的实现系统，包括：

亮度参考像素缓存模块：采用了Zigzag扫描顺序编码以及片上数据交错存储的缓存方式即按降采样得到4种像素类型交错存储，同时分奇偶行与奇偶宏块列分开存储，共16种像素类型交错存储；

分层复用的PE阵列模块：降采样得到4路降采样图像，多PE阵列在每一路降采样图像中进行4路并行搜索，同时另3路降采样图像并行搜索；所述PE阵列能在每一个时钟从亮度参考像素缓存模块得到有效的数据并进行SAD值计算；

PE阵列寄存器数据更新操作控制模块：用于控制PE阵列从亮度参考像素缓存模块读取参考像素到寄存器，一次读取两种像素类型的16字节宽数据用于4路PE阵列的数据更新，PE阵列的当前亮度像素寄存器的数据更新操作通过对不同的当前像素寄存器采用移位实现快速更新。

亮度参考像素缓存模块是硬件实现的核心，亮度缓存通过像素交错存储的方式来满足PE阵列读取数据的需要，使之适合硬件实现。亮度缓存首先要易于PE阵列计算时进行数据的读取与更新操作；同时易于将片外的数据按亮度缓存的存储格式进行存储。本发明采用了Zigzag扫描顺序编码以及片上数据交错存储的缓存方式。当视频编码器从片外存储器DDR SDRAM读取原始视频序列时，不采用传统的按光栅顺序进行宏块编码，而是采用Zigzag宏块顺序编码，可以减少约2/3的外部存储器访问带宽。通过将参考像素按4类像素（正方形、三角形、圆形、五角形），分奇偶行，奇偶宏块列分开存储，共16路片上RAM存储亮度参考像素，每路RAM的位宽为64比特，RAM的每一地址线对应8个像素点值。

分层复用的PE阵列模块是运动估计的计算模块，本发明根据运动估计搜索方法设计对应的阵列分布，充分利用每一个PE单元。在这里假定一个PE单元将仅用于两个8比特像素值的绝对差值运算，本发明共采用了2*1024个PE单元，其中前后向预测各采用1024个PE单元。计算16x16的匹配块需要256个PE，则同时有4路16x16块SAD值并行计算，16路8x8块SAD值并行计算。PE阵列从亮度参考像素模块读取参考像素到寄存器，最后由PE阵列来完成计算工作，需要尽可能保证PE阵列在每一个时钟能从亮度缓存得到有效的数据并进行SAD值计算，保证流水线的时钟周期约束。

分层复用的PE阵列模块中，PE阵列分布呈三级：PEA_32pels阵列单元，PEA_64pels阵列单元，PEA_256pels阵列单元。其中PEA_32pels单元是最基本的阵列单元，由32个PE单元构成，用于计算4x8块的SAD值；PEA_64pels单元包括两路PEA_32pels单元，由64个PE单元构成，用于计算8x8块的SAD值；PEA_256pels单元包括四路PEA_64pels单元，由256个PE单元构成，用于计算16x16块及其可变大小块的SAD值。

本发明的硬件系统主要解决了片上亮度像素缓存的数据组织格式，采用分类像素存储来实现降采样的搜索；设计出复杂度适中的数据流和控制流，使得硬件实现简单；在不增加额外存储空间的前提下，增加PE阵列实现高吞吐量的计算。

本发明由于采取以上技术方案，其具有以下优点：

1、降采样层数少，搜索精度高；

2、设置降采样层候选运动向量的搜索步长为2，提高搜索速度；

3、充分利用片上亮度缓存同一时刻所有可读取的像素数据，多PE阵列并行处理；

4、片上RAM与Register充分考虑数据复用，降低带宽需求；

5、减少同一PE阵列与不同RAM的数据交互，降低硬件实现复杂度。

附图说明

图1是分层搜索的整体硬件构架示意图；

图2是分层搜索的两层像素关系示意图；

图3是两层运动估计的原理图；

图4是Zigzag宏块编码顺序示意图；

图5是片上亮度缓存的存储结构；

图6是PEA单元的结构；

图7是PEA_64pels与PEA_256pels单元结构的组成；

图8是PE阵列当前像素寄存器的存储方式；

图9是降采样层的其中一路降采样图像的搜索示意图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例以本发明技术方案为前提，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

本实施例提供一种适用于FPGA与ASIC实现、基于分层运动估计的搜索方法，具体为：将当前帧和参考帧按照比例降采样，L1层是L0层4:1降采样得到的图像，L0层是原图像层。本例以L0层搜索范围为[-160 160)x[-104 104)为例进行说明，则L1层的搜索范围变为[-80 80)x[-52 52)。搜索时先在第L1层上进行，候选MV搜索步长为2，全搜索[-80 80)x[-52 52)区间内共160x104/4=4160个候选MV，计算SAD时候，用了4:1降采样精度，即64个像素点参与了SAD值计算。两层像素关系示意图如图2所示。

本实施例上述方法中，降采样得到4路降采样图像，多PE阵列在每一路降采样图像中进行4路并行搜索，同时另3路降采样图像并行搜索。

如图2所示，（b）是（a）水平垂直各2:1降采样后得到的四路降采样图像（正方形、三角形、圆形、五角形），通过对四个区域的降采样图像采取不同类型的像素点来实现4个区域的并行搜索。同时在L1层对每一个区域搜索时，进一步采用了4路并行搜索，提高搜索速度。如图3所示，采用基于率失真优化的支持可变大小块运动估计，块匹配代价函数取当前块与参考块的SAD值与运动矢量的编码比特消耗的加权和。在L1层块大小为8x8，通过求取最小的匹配代价函数便可以得到最优的运动矢量。在L0层搜索时，将以L1层最优运动矢量和视频编码器的运动预测模块得到的运动矢量为运动搜索起始点，在一个较小的搜索窗内进行全搜索，便可得到可变大小块的块匹配代价函数值，各种模式的匹配代价将用于编码器的亚像元运动估计与预测模式的选择。

如图1所示，用于实现上述搜索方法的硬件系统由多个不同的功能模块组成，主要有亮度参考像素缓存模块，分层复用的PE阵列模块，PE阵列寄存器数据更新操作控制模块。

亮度参考像素片上缓存如图5所示，图中一个圆圈代表一个参考像素点，其中的字符代表像素类型。将参考图像的划分为0～f共16类参考像素，其中0～7类参考像素为偶宏块列参考像素，8～f为奇宏块列参考像素，每一类参考像素对应一个相应类型RAM，亮度参考像素缓存由16个位宽为64比特的RAM构成。本实施例采用了如图4所示的Zigzag宏块扫描顺序编码，每次更新数据时只读取一列宏块列的数据，只需一次更新8个偶（奇）宏块列RAM即可。

PEA_32pels结构如图6所示，该单元是最基本的阵列单元，计算4x8块的SAD值；同时产生4个2x4块的SAD值（4x8块的左上、右上、左下、右下单元），用于可变大小块的SAD值计算。PEA_32pels单元构成如下：5个8字节宽的参考像素移位寄存器，4个8字节宽的待编码像素的移位寄存器，32个PE基本单元，5个累加器。如图7所示，2个PEA_32pels单元构成PEA_64pels单元，4个PEA_64pels单元构成PEA_256pels单元。当前宏块像素在寄存器中的存储方式如图8所示，在L1层或L0层进行块匹配运动估计时，PEA_32pels单元的当前宏块像素寄存器始终存储0～7类当前像素类型中的一种像素。

下面分别对在L1层和L0层运动估计步骤进行详细的说明。以下描述仅是针对1024个PE基本单元，涉及一帧的处理。对于P帧，另1024个PE单元并行处理另一参考帧；对于B帧，另1024个PE基本单元并行处理相反方向参考帧。

L1层分别对由原图像4:1降采样得到的4路降采样图像并行运动估计，其中每路降采样图像进行8x8块的4路并行运动估计。降采样后，i、（i+4）、（i+8）、（i+12）（i=0，1，2，3）共4类像素各构成1路降采样图像。在本例中约定采取二维坐标系，原点为当前待编码宏块的左上角像素点，水平向右为x轴正方向，垂直向下为y轴正方向。设候选运动向量（x，y），其中x、y均为负时，由i=0构成的降采样图像进行运动估计；x为非负，y为负时，由i=1构成的降采样图像进行运动估计；x为负，y为非负时，由i=2构成的降采样图像进行运动估计；x、y均为非负时，由i=3构成的降采样图像进行运动估计。下面仅对其中一路降采样图像进行分析，取i=0即可，设PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels用于4路并行运动估计。如图9所示，PEA1_64pels，PEA2_64pels，PEA3_64pels，PEA4_64pels是水平并行处理，对候选运动向量的SAD值计算采用蛇形扫描的方式进行搜索。

T=cycle1时刻，PEA1_64pels计算候选运动向量（-160，-80）的SAD值；PEA2_64pels则相对于PEA1_64pels的运动向量x轴正方向移动4个整像素单位向量，计算（-156，-80）的SAD值；同理，PEA3_64pels，PEA4_64pels分别计算（-152，-80）、（-148，-80）候选运动向量的SAD值。4个PEA_64pels单元在下一周期内将计算的候选运动向量均向y轴正方向移动4个整像素单位向量。PEA1_64pels由两个PEA单元构成，PEA1_64pels_PEA0与PEA1_64pels_PEA1；PEA1_64pels在下一周期计算（-160，-76），所需数据与计算（-160，-80）的参考像素数据相比只需要更新8byte的数据即可，PEA的参考像素寄存器为5x8bytes，则其中4个8bytes寄存器用于参与运算，第5个8bytes寄存器用于读入需要更新的8byte数据即可，保证PE阵列在T=cycle2时刻可以立即参与运算。对于当前像素寄存器不需要更新。对PEA2_64pels，PEA3_64pels，PEA4_64pels同此操作即可。

T=cycle2时刻，PEA1_64pels计算候选运动向量（-160，-76）；PEA2_64pels计算候选运动向量（-156，-76）；PEA3_64pels计算候选运动向量（-152，-76）；PEA4_64pels计算候选运动向量（-148，-76）。更新参考像素寄存器8bytes数据，当前像素寄存器不需要更新。

同上操作，继续向y轴正方向扫描，则T=cycle19时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-160，4）、（-156，-4）、（-152，-4）、（-148，-4）的SAD值。

在T=cycle20时刻，若继续向y轴正方向移动的运动向量（-160,0）、（-156，0）、（-152，0）、（-148，0）属于另一路降采样图像的候选运动向量的范围，这里需要向x轴正方向移动16个整像素单位向量，不能数据复用，PE阵列需要空等，直至需要的数据读入参考像素寄存器。同时更新4个8字节宽的数据需要4个周期，减去上一个周期内第5个8字节宽的寄存器已更新的操作时间，共需等待3个周期。不需更新当前像素寄存器。

T=cycle23时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-144，-4）、（-140，-4）、（-136，-4）、（-132，-4）的SAD值。在下一个周期内各PEA_64pels阵列计算的候选运动向量相对于T=23cycle时刻的运动向量沿y轴负方向移动4个整像素单位向量，故在此周期内更新8字节狂的参考像素数据，不需更新当前像素寄存器。

T=cycle24时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-144，-8）、（-140，-8）、（-136，-8）、（-132，-8）的SAD值。同时更新参考像素寄存器8bytes数据，不需更新当前像素寄存器。

同上操作，继续向y轴负方向扫描，则T=cycle41时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-144，-80）、（-140，-80）、（-136，-80）、（-132，-80）的SAD值。在下一个周期内需要计算向x轴正方向移动16个整像素单位向量的候选运动向量的SAD值，数据不能有效复用，PE阵列需要空等，直至需要的数据读入参考像素寄存器。不需更新当前像素寄存器。同上，需要等待3个周期。

T=cycle45时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-128，-8）、（-124，-8）、（-120，-8）、（-116，-8）的SAD值。同时更新8byte的数据，不需更新当前像素寄存器。

同上操作，至T=cycle217时刻，PEA1_64pels、PEA2_64pels、PEA3_64pels、PEA4_64pels分别计算候选运动向量（-16，4）、（-12，4）、（-8，4）、（4，-4）的SAD值。至此，该路降采样图像的块匹配运动估计结束。

对于另3路降采样图像执行同样的操作即可。根据选择最小的块匹配代价，可得到16个最优候选运动向量。对这16个最优候选运动向量的块匹配代价进行比较，在满足限制条件：该向量在L0层作为搜索起始点的搜索区域和以预测运动向量作为搜索起始点的搜索区域不发生相互重叠，选取匹配代价最小的运动向量作为L1层的最后候选运动向量。

至此，L1层的运动估计结束，下面对L0层运动估计进行相关说明。

L0层以L1层搜索得到的最优运动向量与预测运动向量分别为搜索起始点，设为（cenx，ceny），在[-8 8)x[-6 6)的搜索窗内进行运动估计，找到整像元运动估计的最优运动向量。L0层计算每一个候选运动向量需要256个PE单元，即一个PEA_256pels单元，由4个PEA_64pels单元构成，前后向各4个PEA_256pels单元，记为PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels。L0层运动估计将四路并行搜索，同L1层蛇形扫描原理相同。

首先确定由于数据读取的需要，需要将搜索扩展为：[-8-(cenx mod4),12+(cenx mod 4))或者[-12-(cenx mod 4),8+(cenx mod 4))，二者无实质差别，可根据实际情况选择两者之一即可。为简化后续说明，这里假定cenx=16，ceny=16，扩展搜索窗为[-8,12）。

T=cycle1时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（-8，-6）、（-7，-6）、（-6，-6）、（-5，-6）的SAD值。其中PEA1_256pels由四个PEA_64pels结构单元组成，记为aPEA1_64pels，aPEA2_64pels，aPEA3_64pels，aPEA4_64pels，并假定它们各自存储的当前宏块像素类型为（0、4），（1、5），（2、6），（3、7）。候选运动向量（-8，-6）对应的参考宏块的左上角的像素坐标为（8，10），此点像素类型为3。aPEA1_64pels，aPEA2_64pels，aPEA3_64pels，APEA4_64pels各自计算以（8，10）、（9，10）、（8，11）、（9，11）为左上角的8x8降采样块的SAD值，累加可得L0层可变大小块的SAD。同时，在此周期内，各PE阵列需要对寄存器的像素进行更新。假设aPEA1_64pels由aPEA1_32pels，aPEA2_32pels组成，分别存储当前待编码宏块的像素类型为（0、4），参考像素寄存器的对应类型为（3与b、7与f）。这2个PEA_32pels阵列更新当前宏块的编码像素类型为（2、6），参考像素对应的类型为（3与b、7与f），需要更新8字节宽的数据。aPEA1_256pels的另3个PEA_64pels阵列以及另3个PEA_256pels的PEA_64pels阵列同此操作。

T=cycle2时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（-8，-5）、（-7，-5）、（-6，-5）、（-5，-5）的SAD值。同时，在此周期内，各PE阵列需要对寄存器中像素值进行更新。

同上操作，继续向y轴正方向扫描，则T=cycle12时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（-8，5）、（-7，5）、（-6，5）、（-5，5）位置SAD值。这里需要向x轴正方向移动4个整像素单位向量，数据不能有效复用，PE阵列需要空等，直至需要的数据读入参考像素寄存器。共需等待3个周期。

T=cycle16时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（-4，5）、（-3，5）、（-2，5）、（-1，5）的SAD值。同时，在此周期内，各PE阵列需要对寄存器的像素值进行更新。下一个时钟周期需要向y轴负方向移动一个整像素单位向量进行运动估计。

T=cycle17时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（-4，4）、（-3，4）、（-2，4）、（-1，4）的SAD值。同时，在此周期内，各PE阵列需要对寄存器的像素值进行更新。下一个周期需要向y轴负方向移动一个整像素单位向量进行运动估计。

同上操作，T=72cycle时刻，PEA1_256pels，PEA2_256pels，PEA3_256pels，PEA4_256pels分别计算候选运动向量（8，5）、（9，5）、（10，5）、（11，5）的SAD值。

至此，基于该搜索起始点的L0层局部精细搜索运动估计结束，根据选择最小的块匹配代价，可得到4个最优候选运动向量，再对这4个最优候选运动向量的块匹配代价进行比较，可以得到1个对应该搜索起始点的最优运动向量。

同理，对另一搜索起始点执行同样操作，可以得到1个对应该搜索起始点的最优运动向量。最后将对应两搜索起始点的各自最优运动向量的代价进行比较，可以得到整像元运动估计的最优运动向量。至此，整像元估计结束。

尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。