基于宏块运动信息的快速模式选择算法.pdf
http:/-1-基于宏块运动信息的快速模式选择算法基于宏块运动信息的快速模式选择算法1 李鹏飞，刘文予，韦耿，周刚 华中科技大学电子与信息工程系，武汉(430074)E-mail： 摘摘 要：要：H.264 对变块大小运动估计采用全模式搜索的方法，极大地增加了编码的计算复杂度，针对这一问题本文提出一种快速帧间宏块模式选择算法。首先搜索当前帧间宏块内 16个 44 块的运动矢量，获取当前宏块的运动信息，再据此确定分块模式，完成后续编码。该算法通过计算率失真代价函数，有效地利用了当前宏块的运动信息，能更简单有效地选择分块模式。实验结果表明，该算法结合快速运动估计算法，在保持与全模式搜索相近编码性能的同时，可节省编码时间 70%以上。关键词：关键词：模式选择，H.264，运动信息，几何结构 1引言引言 最新视频编码标准H.264采用了很多新的编码技术来提高编码性能。和以前的标准相比，在同等编码质量条件下，H.264可以节约大约50%的码率1。但这些技术也极大地增加了编码的计算复杂度，特别是在帧间宏块的模式选择和运动估计模块。对帧间宏块，H.264定义了7种编码模式，包括SKIP模式、4种帧间预测模式、以及2种帧内预测模式。如图1所示，在JM参考软件中，编码器依次遍历7种编码模式，并对其中的4种帧间模式进行精确地运动估计，选出率失真代价函数最小的模式作为最优分块模式，从而导致整个编码的计算量非常大。虽然JM参考软件提供了一种快速运动估计算法(FME)来提高单个运动估计的搜索速度，但模式选择仍需遍历7种模式，整体的计算量仍很大。因此，研究模式选择的快速算法成为了一个热点问题。图 1 H.264 模式选择算法 Fig 1 the mode decision algorithm of H.264 1 本课题得到国家自然科学基金无线移动环境下复杂度可分级联合功率率失真模型（No:60572063）；教育部博士点基金广义率失真理论及在无线通信中的应用（No:20040487009）的资助。http:/-2-目前，针对H.264快速模式选择方法已有不少的研究成果25。总体而言，这些方法可以分为两类，一是用周围已编码宏块的模式来预测，二是用当前宏块的内部信息来判断。用周围宏块预测的方法2，只能减少候选模式的个数，并不能有效地降低计算量，不是本文研究的重点。用宏块内部信息判断的方法345，由于考虑了当前宏块的运动和纹理特征，因而能够更准确地判断分块模式。其思想主要有：预先判断是否选用SKIP模式，判断是否将大块分裂或者将小块合并，剔除部分可选模式等。上述方法通常设定了多个分支，根据相应的阈值来选择分块模式。但预先设定的阈值却很难适应变化的视频内容，判断容易出错，进而影响编码性能。本文提出一种帧间宏块的快速模式选择算法，将当前宏块内44块的运动矢量作为候选运动矢量，采用率失真代价函数而非阈值作为判断准则，先选出最优的大分块方式（1616、168、816、以及88），再根据需要计算最优的小分块方式。由于代价函数综合反映了当前宏块内部的运动和纹理信息，因此模式选择更准确；而采用44块的运动矢量作为候选运动矢量来计算代价函数，避免了对每种帧间预测模式的运动估计，大大降低了编码的计算复杂度。本文内容安排如下：第 2 节介绍并分析本文提出的算法；第 3 节给出并解释实验结果；第 4 节是结论。图 2 文献6算法流程图 Fig 2 the flowchart of the reference paper 6 2提出算法提出算法 文献6指出宏块内 16 个 44 块运动矢量的分布与最优分块模式间有很强的对应关系，并且最优分块模式所对应的运动矢量有很大概率出现在这 16 个运动矢量中，据此提出了一种通过 44 块的运动矢量直接判断分块模式的方法，其算法流程如图 2 所示。但文献6认为http:/-3-只在大分块方式选择了 88 模式时才计算小分块方式，而 88 模式不一定是最优的小分块方式，因此会造成分块模式的误判，影响编码性能；文献6还认为在计算小分块方式时不需再计算 88 模式的代价函数，而实际上在大分块方式选择时，88 模式的代价函数只是由少数几个候选的 44 块运动矢量计算得到，并非 88 模式最小的代价函数，故仍需通过运动估计得到。2.1 理论分析理论分析 针对文献6中存在的不足，本文从分块模式的几何结构出发，提出一种改进的模式选择算法。首先将帧间预测模式分为大分块方式（1616、168、816、以及 88）和小分块方式（88、48、84、以及 44）两组。从几何结构上看，在大分块方式下各子块的分割方式都相同，组合结构简单，适合平缓运动和纹理较少的宏块；在小分块方式下允许各子块的分割方式不同，组合结构复杂，适合剧烈运动和纹理较多的宏块。如图 3 所示，88 模式可分别对应两种分块方式。两种分块方式适合不同的视频内容，因而相应率失真代价函数差别明显，可作为区分两种分块方式的准则。图 3 大小分块方式的区别 图 4 大小分块方式的联系 Fig 3 the difference between big and small mode Fig 4 the relation between big and small mode 从几何结构上，小分块方式还可看作是大分块方式的细分。如图 4 所示，假设大分块方式(a)为 816 模式，小分块方式(b)为任意分割。任意小分块方式都分别将两个 816 子块进一步细分，表明其内部仍存在相对运动，不能作为整体编码。因此，判断是否需考虑小分块方式，只需判断最优的大分块方式内是否还存在明显的相对运动，也就是将最优的大分块方式和小分块方式比较。由于小分块方式可任意选择，而大分块方式内部的运动情况未知，因而选择最细小分块方式（将一个宏块分为 16 个 44 小块）与最优的大分块方式比较。因此本文采用分步处理策略：首先选出最优的大分块方式，再根据需要对大分块方式进行细分。如果判断出当前宏块采用大分块方式更适合，则不需计算小分块方式，有效地减少了编码的计算量。2.1.1 大分块方式模式选择大分块方式模式选择 由于大分块方式仅有 4 种分割方式，可通过遍历方式选出最优的大分块方式。判断最优分块模式，首先需要得到各模式下最优的运动矢量。实验结果表明，最优分块模式对应的运动矢量有很大概率出现在 16 个 44 块的运动矢量中6，因此，可以用这 16 个运动矢量作为候选运动矢量来选择最优的大分块方式。选定一种模式就假定了该模式下各子块内运动是一致的，而各子块间运动有差别。因此，只需选取当前子块内各 44 块的运动矢量作为该子块的候选运动矢量，参与模式选择。另外，当前子块内相等的运动矢量都对应同一个预测位置，为避免重复计算，只需选取当前子块内http:/-4-不等的运动矢量作为该子块的候选运动矢量，参与模式选择。那么，对于大分块方式的模式选择，可公式化为：)1()()(minmin1,=+=jjkkNkkMkMmvjmvdRmvSADT 其中，T 代表最优的帧间预测模式；j 代表候选帧间预测模式，j(1,2,3,4)；Nj代表分块模式 j 中子块的个数；k 代表分块模式 j 中各子块的序号；Mk,j代表分块模式 j 中第 k 个子块内所有 44 块中不等的运动矢量 mvk组成的集合。公式(1)的含义是：遍历候选帧间预测模式 j(1616，168，816，88)，对当前分块模式 j 下第 k 个子块，将其区域内代价函数最小的 mvk作为当前子块的最优运动矢量，将其相应的代价函数作为当前子块最小的代价函数，并将各子块代价函数的和最小的分块方式作为最优的分块方式。2.1.2 大分块方式和小分块方式的选择大分块方式和小分块方式的选择 若最优大分块方式为 88 模式，表明当前宏块内存在明显相对运动，直接计算最优的小分块方式。否则，将最优大分块方式的代价函数和最细小分块方式代价函数比较。若最细小分块方式的代价函数较小，则继续计算最优的小分块方式；否则，最优帧间预测模式的选择结束，用最优的大分块模式完成后续编码。由公式(1)选出的最优大分块方式，其率失真代价函数为：)2()()(minbest_modemod1=+=NkkMkMmvbigmvdRmvSADJe,kbest_k 最细的小分块方式作为小分块组合方式的代表，其率失真代价函数为：)3()()(161kMkksmallmvdRmvSADJ+=即是 16 个 44 块率失真代价函数的和，而 44 块的代价函数在搜索 44 块运动矢量时已经计算出来，此处只是简单的求和运算。由于小分块组合方式只采用一个典型小分块方式作为代表，判决存在风险。若大小分块方式的代价函数差别明显，则风险可以避免；若差别不大，则可能出现误判，但由于大小分块方式的区别不明显，误判对编码性能造成的影响也是有限的。2.1.3 小分块方式模式选择小分块方式模式选择 若需要继续计算小分块方式，对每一个 88 子块，还需从 88、84、48、以及 44模式中选出一个最优的分块模式。44 模式对应的运动矢量和代价函数在搜索 16 个 44 块运动矢量时已经得到，故不再计算；而 84、48 在几何结构上相互对立，仍可用其内部 44块的运动矢量作为候选运动矢量从两种分块模式中去掉一个。两种模式的率失真代价函数分别为：)4()()(min214848,=+=kkMkMmvmvdRmvSADJkk)5()()(min218484,=+=kkMkMmvmvdRmvSADJkk 将代价函数大的分块模式舍去，则每个 88 子块只需对两种小分块模式进行运动估计，http:/-5-从余下的三种模式中选出最优模式，从而有效地减少了小分块模式的计算量。2.1.4 帧间模式与帧内模式选择帧间模式与帧内模式选择 帧间宏块还需将选出的帧间预测模式与帧内预测模式比较。帧间宏块的帧内预测模式有44 大小和 1616 大小两种。若帧间预测模式选择小分块方式，表明当前宏块内部存在明显的相对运动，只需检验 44 大小的帧内预测模式；反之，若帧间预测模式选择大分块方式，则只需检验 1616 大小的帧内预测模式。从而有效地减少了帧内模式选择的计算量。图 5 本文建议算法流程图 Fig 5 the flowchart of the proposed algorithm 为进一步降低计算量，在搜索得到 16 个 44 块运动矢量后，首先统计其中不等运动矢量的个数。若绝大部分运动矢量都不等，表明当前宏块内部相对运动明显，则直接计算最优的小分块模式，节省大分块模式选择的计算量。本算法设置不等的运动矢量个数大于 11 个，http:/-6-则直接计算最优小分块模式。根据上面的分析，得到算法流程图如图 5 所示。2.2 算法步骤算法步骤 step1 搜索 16 个 44 块的运动矢量。step2 统计 16 个运动矢量中不等运动矢量的个数。若大于 11，直接计算最优小分块模式，转到 step5，否则转到 step3；step3 选出最优的大分块方式。其判决公式如下：)1()()(minmin1,=+=jjkkNkkMkMmvjmvdRmvSADT step4 完成大分块方式与小分块方式的选择。对于大分块，其代价函数计算公式为：)2()()(minbest_modemod1=+=NkkMkMmvbigmvdRmvSADJe,kbest_k 对于小分块，其代价函数计算公式为：)3()()(161kMkksmallmvdRmvSADJ+=if(Jsmall Jbig)，转到 step5；if(JsmallJbig)，转到 step6；step5 对每个 88 子块，选择分块模式。先计算)4()()(min214848,=+=kkMkMmvmvdRmvSADJkk)5()()(min218484,=+=kkMkMmvmvdRmvSADJkk 舍去代价函数大的分块模式，再用遍历方式从余下 3 种小分块模式中选出最优的。其中，对 44 模式不需再进行运动估计，只需参与模式选择。step6 若最优帧间模式为大分块模式，则进一步与 1616 大小的帧内模式比较；若最优帧间模式为小分块模式，则进一步与 44 大小的帧内模式比较，选出最优的编码模式。step7 判断选出最优分块模式是否为 Skip 模式，并用选出的编码模式编码当前宏块。3实验及结果分析实验及结果分析 本文算法在 H.264 编码器 JM86 基础上实现，采用 6 个测试序列的前 300 帧进行测试，分别是“Container”，“Paris”，“Mobile”，“Foreman”，“Football”，“Stefan”；图像大小为 QICF（176144）；编码格式是 IPPP。实验中帧率为 30f/s，量化参数 QP 取 24，28，32，36。运动估计算法采用参考软件中的快速搜索算法（FME）而不是快速全搜索算法(FFS)，参考帧数为 1 帧；搜索范围为 16。由于本文算法用候选运动矢量直接判断最优的分块模式，因此率失真优化关闭。打开哈达码变换，采用统一变长编码（UVLC）进行熵编码。表 1、表 2、表 3 分别与 JM 参考软件的快速搜索算法(FME)比较了 PSNR、码率、计算复杂度。计算复杂度用编码占用时间表示，计算公式为：http:/-7-)6(100%=FMEproposedFMETTTT 由表 1、表、表可知，本文的模式选择算法结合快速搜索算法(FME)在保持编码性能变化不大的情况下，能进一步降低快速搜索算法(FME)44%以上的计算量。表 1 PSNR 比较 Table 1 Comparison of PSNR of the proposed algorithm PSNR(dB)QP=2436 测试测试 序列序列 图像图像 大小大小 24 28 32 36 Container qcif 0.03 0.01 -0.05 0.03 News qcif-0.05 -0.04 -0.05 -0.02 Mobile qcif-0.04 -0.03 -0.04 -0.05 Foreman qcif-0.06 -0.10 -0.11 -0.11 Football qcif-0.02 -0.02 -0.05 -0.08 Stefan qcif-0.02 -0.03 -0.04 -0.05 Avg -0.03 -0.04 -0.06 -0.05 表 2 码率比较 Table 2 Comparison of bit rate of the proposed algorithm Bit Rate(%)QP=2436 测试测试 序列序列 图像图像 大小大小 24 28 32 36 Container qcif-0.33 1.67 3.37 5.23 News qcif 0.85 0.8 1.78 3.48 Mobile qcif-0.92 -1.49 -1.59 0.13 Foreman qcif 2.31 2.86 3.49 6.30 Football qcif-0.01 0.26 0.97 2.26 Stefan qcif-0.22 -0.42 -0.31 0.63 Avg 0.28 0.61 1.29 3.01 表 3 编码时间比较 Table 3 Comparison of encoding time of the proposed algorithm T(%)QP=2436 测试测试 序列序列 图像图像 大小大小 24 28 32 36 Container qcif 52.50 55.56 56.63 57.83 News qcif 48.75 51.22 53.57 54.12 Mobile qcif 37.50 42.31 49.52 55.14 Foreman qcif 43.30 46.88 52.58 55.10 Football qcif 39.47 42.98 47.32 50.46 Stefan qcif 42.59 39.22 41.75 50.96 Avg 44.02 46.36 50.23 53.94 表 4 与文献6比较的结果 Table 3 Result of the proposed algorithm compared with reference paper 6 BDPSNR(dB)BDBR(%)TS T(%)测试序列测试序列 图像大小图像大小 文献文献 6 本文文献本文文献 6本文文献本文文献 6本文文献本文文献 6 本文本文 Container qcif-0.07 0.03 2.12-0.652.49 5.43 59.84 81.52 News qcif-0.05-0.010.95 0.11 2.45 5.10 59.18 80.26 Foreman qcif-0.15-0.143.12 2.76 2.18 3.78 54.13 73.89 Silent qcif-0.03 0.05 0.67-0.702.39 4.63 58.16 78.28 Paris cif-0.01 0.05 0.38-0.792.39 4.61 58.16 78.31 http:/-8-Mobile cif 0.02 0.02-0.17-0.302.19 3.29 54.34 69.93 Tempete cif 0.02 0.03-0.04-0.452.19 3.35 54.34 70.02 Avg -0.04 0.001.000.002.334.3156.88 76.03 为了验证本文算法的优越性，将本文算法和文献6进行了比较，表 4 列出了比较的结果。实验结果都表示为与快速全搜索算法(FFS)的相对值，用 BDPSNR 和 BDBR8表示本算法与快速全搜索算法(FFS)在编码性能上的差别，而计算复杂度的差别表示为计算时间的比值，公式如下：)7(proposedFFSTTTS=从表 4 可以看出，本文算法的编码性能更优，PSNR 平均上升 0.04dB，码率平均下降1%，而计算复杂度更低，平均下降了 20%。4总结总结 本文提出一种快速模式选择算法，实验结果表明该算法结合快速搜索算法(FME)与快速搜索算法(FME)相比，有几乎相同的编码性能，但编码时间下降 44%以上。这是因为直接选出最优的大分块方式，节省了大分块方式精确运动估计的计算量；判断是否需要计算最优的小分块方式，节省了小分块方式模式选择的计算量；仅对两种小分块模式进行运动估计，节省了小分块模式选择的计算量；根据帧间模式选择帧内模式，节省了帧内模式选择的计算量。该算法从分块模式的几何特点出发，利用宏块内部的运动信息，通过计算率失真代价函数完成分块模式的选择，不需要预先设定与序列相关的阈值，算法思路简单且更具鲁棒性。相对参考文献6的算法，该算法更简单有效地实现了模式选择，更适合于实时应用的环境。http:/-9-参考文献参考文献 1 Wiegand,T.and G.J.Sullivan,et al.(2003).Overview of the H.264/AVC video coding standard J.Circuits and Systems for Video Technology,IEEE Transactions on Circuits and Systems for Video Technology,IEEE Transactions on 13(7):560-576.2 冯镔,刘文予,朱光喜.基于空间相关性的H.264快速自适应模式选择算法J.通信学报,2006,(1)。3 林巍峣,方向忠,黄修超,等(et al).一种快速的H.264帧间模式选择算法J.上海交通大学学报,2006,(1)。4 Zhenyu,W.and N.N.King(2006).A Fast Macroblock Mode Decision Algorithm for H.264J.Circuits and Systems,2006.APCCAS 2006.IEEE Asia Pacific Conference on.5 Xiangjun,Z.and W.Hua,et al.(2006).Fast Mode Decision Based on Video Analysis for H.264/AVC Encoder J.Intelligent Control and Automation,2006.WCICA 2006.The Sixth World Congress on.6 Tien-Ying,K.and C.Chen-Hung(2006).Fast Variable Block Size Motion Estimation for H.264 Using Likelihood and Correlation of Motion FieldJ.Circuits and Systems for Video Technology,IEEE Transactions on Circuits and Systems for Video Technology,IEEE Transactions on 16(10):1185-1195.7 G.Bjontegaard,“Calculation of Average PSNR Differences Between RD-Curves”s.ITU-T Q6/SG16,Doc.VCEG-M33,Apr.2001.Fast Inter Mode Decision Algorithm for H.264 Using Motion Information of Current Macroblock Li Pengfei,Liu Wenyu,Wei Geng,Zhou Gang Dept.of Electronics&Information Engineering,Huazhong University of Sci.&Tech.Wuhan,Hubei,China(430074)Abstract Variable block size motion estimation uses full mode search to reduce the prediction error.However,the exhaustive search results in high computational complexity in motion estimation at the encoder.In this paper,a fast inter mode decision algorithm is proposed to reduce the complexity for H.264 encoder.The proposed method firstly searches the motion vectors(MVs)for 44 blocks within the current macroblock(MB),and then determines a suitable mode according to the obtained motion information,finally encode the MB using the chosen mode.The algorithm makes decision fully depended on the motion information of the current MB,so it is more robust.The experimental results show that the proposed method reduces the encoding time up to 70%,while maintaining the rate-distortion performance comparable to that of exhaustive search method.Keywords:mode decision,H.264,motion information,geometry structure
