一种基于率失真优化的GPU中视频编码快速搜索方法

摘要

本发明涉及一种基于率失真优化的GPU中视频编码快速搜索方法，包括64×64PU搜索步骤、其他PU搜索步骤及分数像素搜索步骤，在64×64PU搜索及其他PU搜索中，针对不同大小的PU提出了基于率失真优化的两步搜索，首先获取最佳匹配位置，然后利用率失真代价计算方法将MV、PMV及SAD对应的率失真代价计算出来，存进Shared Memory，再用迭代算法计算出最小的代价，将最小代价及其对应的SAD及MV都存入Global Memory中。与现有技术相比，本发明降低了计算复杂度，大大减小了计算时间。

权利要求

1.一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，该方法包括64×

64PU搜索步骤、其他PU搜索步骤及分数像素搜索步骤，其中，所述的64×64PU搜索步骤包括：

1a)、计算一帧高清视频中所有8×8块在32×32范围内的所有SAD，并将其存取Global Memory中，并对计算的所有SAD进行比较，找出率失真性能最小SAD及最佳MV；

1b)、以步骤1a)取得的最小SAD的位置为中心点进行169点全搜索，并以步骤1a)获得的最佳MV作为PMV；

所述的其他PU搜索步骤包括：

2a)、在GPU运动估计中，子PU选取母PU的最佳MV作为PMV，并以母PU取得最佳MV位置为起始点获取各种可能PU的PMV，母PU包含子PU，即母PU可进一步划分为若干子PU；

2b)、以步骤2a)的得出的最佳匹配位置为中心点，在9×9的范围内进行全搜索；

所述的分数像素搜索包括：

3a)、对分数像素图像进行二分之一插值，并将创建的每个线程块完成三个二分之一像素插值，将插值完成的图像保存到Global Memory中；

3b)、对步骤3a)插值后的图像进行四分之一插值，并存于Global Memory中；

3c)、在每种PU块的整数最佳匹配位置进行分数像素位置的SAD计算，采用全搜索的方式计算各个分数像素位置的率失真代价并比较，选出最佳值，完成视频帧的快速搜索。

2.根据权利要求1所述的一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，率失真代价J的计算表达式为：J＝SAD+λ*R(MVD

式中，MVD为当前块的真实运动向量和预测运动向量的差值，R为编码MVD所用bit，λ为拉格朗日乘子。

3.根据权利要求2所述的一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，步骤1a)具体包括下列步骤：

1)创建一个32条流水线的线程块，利用前五条流水线计算三个SAD，并利用其余每个流水线计算两个SAD；

2)将得到的32个SAD存入Shared Memory，创建包含16条流水线的线程块与32个SAD对比，并将16个SAD存入Shared Memory，依次迭代5次直至计算结束；

3)将得到的最小值SAD对应的MV保存到Global Memory中。

4.根据权利要求3所述的一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，步骤1b)具体包括下列步骤：

1)将提前计算的MVBT存入GPU的Constant Memory，若需要计算率失真代价，根据相应的MV查表获取运动向量的比；

2)创建具有169条流水线的线程块，并计算MV、PMV及SAD对应的率失真代价，存入Shared Memory；

3)将最小代价及其对应的SAD、MV存入Global Memory中。

5.根据权利要求2所述的一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，步骤2a)具体包括下列步骤：

1)计算64×32PU的SAD来寻找最佳64×32 PU；

2)取64×64PU的最佳MV64×64作为64×32PU的预测向量，通过计算率失真代价并进行率失真代价比较，获取最小的率失真代价及对应的MV和SAD，然后根据MV确定最佳匹配位置。

6.根据权利要求5所述的一种基于率失真优化的GPU中视频编码快速搜索方法，其特征在于，步骤2b)具体内容为：以步骤2a)获取的最佳匹配位置为中心，并将获取的MV作为本步骤的PMV，进行周围81点方形全搜索，找出率失真代价最低的块及其对应SAD和MV64×32，存入Global Memory中。

7.根据权利要求5所述的一种基于率失真优化的GPU中视频编码快速搜索方法，64×32 PU的SAD由64×32 PU对应的32个8×8 SAD相加计算得到。

说明书

一种基于率失真优化的GPU中视频编码快速搜索方法

技术领域

[0001] 本发明涉及GPU视频编码技术领域，尤其是涉及一种基于率失真优化的GPU中视频编码快速搜索方法。

背景技术

[0002] 为提高计算性能，HEVC(High Efficiency Video Coding)视频编码可以在异构平台并行架构基础上执行，并基于多核CPU和GPU框架。其中，HEVC视频编码器在GPU中执行运动估计时一般采用全搜索方法进行搜索，全搜索方法虽然能够找到最佳的划分模式，但是需要遍历所有的划分，计算复杂度很高，使运动估计过程消耗时间比较长。另一种搜索方法是TZSearch算法，TZSearch算法采用的是菱形搜索方式，其过程为：

[0003] (1)确定起始搜索点；

[0004] (2)以步长1开始，按菱形模板在搜索范围内进行搜索，其中步长以2的整数次幂的形式递增，选出率失真代价最小的点作为该步骤的搜索结果；

[0005] (3)若步骤2选出的最优点对应的步长为1，则需要在该点周围进行二点搜索，目的是补充搜索最优点周围尚未搜索的点；

[0006] (4)若步骤2得到的最优点对应的步长大于某个阈值，则以该最优点为中心，在一定范围内做全搜索(搜索范围内的所有点)，选择率失真代价最小的做为该步骤的最优点；

[0007] (5)以步骤4得到的最优点为起始点，重复步骤2～4，细化搜索。当相邻两次细化搜索得到的最优点一致时停止细化搜索。此时得到的MV(MotionVector，运动向量)即为最终MV。

[0008] 按照TZSearch快速搜索算法的原理，GPU中也会设计菱形搜索算法以降低计算复杂度，但是这种方法无法获取PMV(Motion Vector Prediction，预测运动向量)，因为PMV是从相邻的CTU(CodingTreeUnit，编码树单元，大小为64×64)的运动预测得到的运动向量，而在GPU运动估计中相邻的CTU处理是同时并行处理的，无法从相邻CTU获取相应的PMV，因此无法使用率失真优化技术选择最佳的CTU划分模式，导致率失真性能下降，为此找出PMV是在GPU中解决率失真优化问题的关键。

[0009] 因CPU具有很强的通用性来处理各种不同的数据类型，同时逻辑判断又会引入大量的分支跳转和中断的处理，这些都使得CPU的内部结构异常复杂。而GPU面对的是类型高度统一、相互无依赖的大规模数据和不需要被打断的纯净的计算环境，这也使得GPU不能像CPU那样具有高效的逻辑判断性能，所以在GPU中很难实现TZSearch一样具有大量逻辑判断的搜索算法，即使能实现也会花费大量的时间，这与降低计算复杂度提升编码速度的初衷是相违背的，所以GPU中的快速搜索算法不能完全采用TZSearch快速算法，需进行改善。

发明内容

[0010] 本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种基于率失真优化的GPU中视频编码快速搜索方法。

[0011] 本发明可以通过以下技术方案来实现：

[0012] 一种基于率失真优化的GPU中视频编码快速搜索方法该方法包括64×64PU搜索步骤、其他PU搜索步骤及分数像素搜索步骤。

[0013] (一)64×64PU搜索步骤包括：

[0014] 1.1)、计算一帧高清视频中所有8×8块在32×32范围内的所有SAD，并将其存取Global Memory中，并对计算的所有SAD进行比较，找出率失真性能最小SAD及最佳MV，具体步骤包括：

[0015] 1)创建一个32条流水线的线程块，利用前五条流水线计算三个SAD，并利用其余每个流水线计算两个SAD；

[0016] 2)将得到的32个SAD存入Shared Memory，创建包含16条流水线的线程块与32个SAD对比，并将16个SAD存入Shared Memory，依次迭代5次直至计算结束；

[0017] 3)将得到的最小值SAD对应的MV保存到Global Memory中。

[0018] 1.2)、以步骤1.1)取得的最小SAD的位置为中心点进行169点全搜索，并以步骤1.1)获得的最佳MV作为PMV，具体内容为：

[0019] 1)将提前计算的MVBT存入GPU的Constant Memory，若需要计算率失真代价，根据相应的MV查表获取运动向量的比；

[0020] 2)创建具有169条流水线的线程块，并计算MV、PMV及SAD对应的率失真代价，存入Shared Memory；

[0021] 3)将最小代价及其对应的SAD、MV存入Global Memory中。

[0022] (二)其他PU搜索步骤包括：

[0023] 2.1)、在GPU运动估计中，子PU选取母PU的最佳MV作为PMV，并以母PU取得最佳MV位置为起始点获取各种可能PU的PMV，具体包括下列步骤：

[0024] 1)计算64×32PU的SAD来寻找最佳64×32PU，64×32PU的SAD由64×32PU对应的32个8×8SAD相加计算得到；

[0025] 2)取64×64PU的最佳MV64×64作为64×32PU的预测向量，通过计算率失真代价并进行率失真代价比较，获取最小的率失真代价及对应的MV和SAD，然后根据MV确定最佳匹配位置。

[0026] 2.2)、以步骤2.1)获取的最佳匹配位置为中心，并将获取的MV作为本步骤的PMV，进行周围81点方形全搜索，找出率失真代价最低的块及其对应SAD和MV64×32，存入Global Memory中。

[0027] (三)分数像素搜索包括：

[0028] 3.1)、对分数像素图像进行二分之一插值，并将创建的每个线程块完成三个二分之一像素插值，将插值完成的图像保存到Global Memory中；

[0029] 3.2)、对步骤3.1)插值后的图像进行四分之一插值，并存于Global Memory中；

[0030] 3.3)、在每种PU块的整数最佳匹配位置进行分数像素位置的SAD计算，采用全搜索的方式计算各个分数像素位置的率失真代价并比较，选出最佳值，完成视频帧的快速搜索。

[0031] 率失真代价J的计算表达式为：

[0032] J＝SAD+λ*R(MVD)

[0033] 式中，MVD为当前块的真实运动向量和预测运动向量的差值，R为编码MVD所用bit，λ为拉格朗日乘子。

[0034] 与现有技术相比，本发明具有以下优点：

[0035] (1)本发明方法在64×64PU搜索及其他PU搜索中，针对不同大小的PU提出了基于率失真优化的两步搜索，首先获取最佳匹配位置，然后利用率失真代价计算方法将MV、PMV及SAD对应的率失真代价计算出来，存进Shared Memory，再用迭代算法计算出最小的代价，将最小代价及其对应的SAD及MV都存入Global Memory中，与现有的全搜索算法、单步搜索算法相比，运用两步搜索算法和率失真算法，在保证视频质量的前提下可降低计算复杂度，大大减小了计算时间；

[0036] (2)本发明方法在其他PU的搜索中，将母PU的最佳MV作为子PU的PMV，并以母PU取得的最佳MV作为获取各PU的PMV的起始点，进行细化搜索，子PU可以以母PU的最佳匹配位置为起点，极大地减少子PU的搜索点数，有效的降低了计算复杂度，进一步提高搜索匹配的准确度。

附图说明

[0037] 图1为TZSearch算法的搜索过程图；

[0038] 图2为D≤16下的64×64PU搜索中菱形搜索模式图；

[0039] 图3为64×64PU搜索中HD视频64×64块SAD生成过程图；

[0040] 图4为64×64PU搜索中69点搜索最小SAD及最佳MV判决过程图；

[0041] 图5为64×64PU搜索中率失真代价最佳MV判决过程图；

[0042] 图6为分数像素运动向量率失真代价最佳MV判决过程图。

具体实施方式

[0043] 下面结合附图和具体实施例对本发明进行详细说明。显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。

[0044] 本发明涉及一种基于率失真优化的GPU中视频编码快速搜索方法，包括：(1)64×64PU搜索；(2)其他PU的搜索；(3)分数像素搜索。

[0045] 一、64×64PU(Prediction Units，处理单元)搜索：

[0046] MVP为运动估计指定了一个中心位置，在这个中心位置适度的范围内可以找到最佳预测块。为了避免缺少MVP造成的编码效率损失，使运动搜索找到更好的中心位置，针对64×64CTU的整数进行搜索。

[0047] 步骤1.1、为方便计算每个搜索位置的64×64CTU的SAD(绝对差和)，在运动估计时，首先计算出一帧高清视频中所有8×8块在32×32范围内的所有SAD(绝对差和)，并将其存取Global Memory中。

[0048] 对于1920×1088(填充8行)高清视频，由510个64×64的CTU组成，每个CTU搜索69个位置，需计算69个SAD，因此在GPU Kernel中分配510个线程块，每个线程块分配69个线程计算相应的SAD，并存入Global Memory中，图3所示为HD视频预搜索生成64×64块SAD的过程。

[0049] 对上述计算出69个点的CTU SAD进行比较，找出率失真性能最小SAD及最佳MV。又由于此时没有PMV存在，故设PMV＝0，选择最优位置就变成选择最小SAD，决策过程如图4所示：

[0050] a)创建一个32条流水线的线程块，其中，利用前五条流水线(T0，T1，T2，T3，T4)计算三个SAD，利用其余流水线每个计算两个SAD。

[0051] b)为提高存取速度，将得到的32个SAD存入Shared Memory。然后创建包含16条流水线的线程块对比32个SAD，并将16个SAD存入Shared Memory，依次迭代5次直至计算完。最后将得到的最小值SAD对应的MV1保存到Global Memory中。

[0052] 步骤1.2、以步骤1.1取得的最小SAD的位置为中心点进行169点全搜索，并以步骤1.1获得的MV1作为PMV。

[0053] 为便于计算率失真代价及提高计算速度，将提前计算的运动向量比特表(MVBT)存入GPU的Constant Memory，需要计算率失真代价时根据相应的MV查表即可得到运动向量的比特。

[0054] 本步骤计算169点64×64CTU的SAD的过程与步骤1.1相似，只是将线程块的69条水流线改为169条流水线，但是找出最佳位置不再是单纯比较169点的SAD，而是计算率失真代价来选择最佳位置及最佳MV。率失真代价J的计算采用下式：

[0055] J＝SAD+λ*R(MVD)

[0056] 其中，MVD表示当前块的真实运动向量和预测运动向量的差值。R为编码MVD所用bit，λ为拉格朗日乘子。

[0057] 率失真代价的计算及寻找最优MV的计算过程如图5所示。首选创建具有169条流水线的线程块，并利用J＝SAD+λ*R(MVD)将MV、PMV及SAD对应的率失真代价计算出来，存进Shared Memory。再用迭代算法计算出最小的代价，将最小代价及其对应的SAD及MV都存入Global Memory中。

[0058] 二、其他PU的搜索：

[0059] 步骤2.1、运动估计过程中子PU的运动趋势往往和其对应的母PU的运动趋势相同，且子PU最佳匹配位置距离母PU的最佳匹配位置一般很近，故子PU选母PU的最佳MV作为PMV，并以母PU取得最佳MV位置为起始点。子PU在运动估计寻找最佳匹配位置时，可以以母PU最佳匹配位置为起点，在周围进行搜索，极大地减少子PU搜索最佳位置所需搜索点数，降低搜索复杂度。各种PU的PMV如表1所示。

[0060] 表1 PU处理顺序及相关参数

[0061]Step PU大小 PU数量 PMV
1 64×64 1 0
2 64×32 2 MV64×64
3 32×64 2 MV64×64
4 32×32 4 (MV64×32+MV32×64)/2
5 32×16 2 MV32×32
6 16×32 2 MV32×32
7 16×16 4 (MV32×16+MV16×32)/2
8 8×16 2 MV16×16
9 16×8 2 MV16×16
10 8×8 4 (MV8×16+MV16×8)/2

[0062] 表1中MVN×M表示N×M块的最佳运动向量。

[0063] 除64×64CTU块外的其他整数块的两步搜索点的获取公式为：

[0064]

[0065] 上式表示的37个点为搜索点，其对应位置如图2所示，图2画出了D≤16的搜索点。

[0066] 计算64×32PU的SAD来寻找最佳64×32PU。64×32PU的SAD由64×32PU对应的32个8×8SAD相加计算得到。

[0067] 然后取64×64PU最佳MV作为64×32PU的预测向量，并用图5计算率失真代价和比较率失真代价的方法，找出最小的代价及对应的MV和SAD，确定最佳匹配位置。

[0068] 步骤2.2、以步骤2.1得出的最佳匹配位置为中心点，在9×9的范围内(81点)实施全搜索。具体步骤为：

[0069] 以步骤2.1得出的最佳匹配位置为中心，和其最佳MV作为本步骤的PMV，进行周围81点方形全搜索，并找出率失真代价最低的块及其对应SAD和MV64×32，存入Global Memory中，此计算过程与64×64PU搜索中步骤1.2类似。其余的PU的处理同64×32PU一样，且各种PU处理顺序按表1中顺序处理，最终得到的所有最小的率失真代价对应的MV和SAD均存于Global Memory。

[0070] 三、分数像素搜索：

[0071] 进行分数像素搜索前必须进行插值，首先进行二分之一插值，创建的每个线程完成三个二分之一像素插值，并将插值完成的图像保存到Global Memory中。然后对二分之一插值图像进行四分之一插值，并存于Global Memory中。

[0072] 完成插值后每个整数像素对应24个分数像素，在每种PU块的整数最佳匹配位置进行24个分数像素位置的SAD计算，然后用全搜索的方式计算各个分数像素位置的率失真代价并比较选出最佳值，完成视频帧的快速搜索。

[0073] 为高效选取最佳的分数像素位置，采用如图6所示的计算方式，即：将分数像素SAD计算与率失真代价结合起来在一个线程块内完成。对于一个64×64CTU总共需计算10种PU(64个8×8PU、32个16×8PU、32个8×16PU、16个16×16SADs、8个32×16PU、8个16×32PU、4个32×32PU、2个32×64PU、2个64×32PU、1个64×64PU)的分数像素运动估计，故需创建169个线程块，每个线程块创建24个线程计算，每个流水线计算一个分数像素位置的SAD及率失真代价，然后在线程块内进行迭代比较，选出最优分数像素位置，将对应的SAD及MV存入Global Memory中。

[0074] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的工作人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。