19:47:15 H.264中运动估计算法的研究 F99TR 刘伟峰 刘伟峰 Bell Lab

主要内容： 背景 H.264 层次搜索算法 自适应搜索算法 Bell Lab

背景介绍——谁是继承者？ MPEG2老了 谁是继承者？ Bell Lab

背景介绍——H.26L横空出世 Bell Lab

背景介绍——来龙去脉 H.26L—ITU-T Q.6/SG16 (VCEG - Video Coding Experts Group)的新宠，H.264的前身 2001 11：VCEG和 MPEG联合组建Joint Video Team (JVT)，共同制定H.26L标准 2002 10：完成标准草案 预计2003 标准最终在两个组织获得通过 H.264是该标准ITU-T的官方名称，MPEG方面称它为MPEG4-Part 10 Bell Lab

H.264——基于块的混合编码方式 Bell Lab

运动估计的原理 Bell Lab

H.264中运动估计 更为精细的块尺寸 ¼像素精度的运动矢量 多参考帧 4x4，4x8，8x4，8x8 8x16，16x8，16x16 6阶FIR滤波器插值1/2像素点 双线性插值1/4像素点 线性插值1/8色度像素点 多参考帧 周期运动 镜头、场景的来回切换 Bell Lab

多种多样的块尺寸 Bell Lab

多种多样的块尺寸 Bell Lab

¼像素精度的运动矢量 ½亮度像素点的插值 1/8色度像素点的插值 ¼亮度像素点的插值 Bell Lab

多参考帧 Bell Lab

H.264的性能 JVT/H.264/AVC MPEG-4 MPEG-2 H.263 Foreman QCIF 10Hz 39 38 37 19:47:15 H.264的性能 39 38 37 36 Quality Y-PSNR [dB] JVT/H.264/AVC 35 MPEG-4 34 MPEG-2 33 H.263 32 31 Foreman QCIF 10Hz 30 29 28 27 Bit-rate [kbit/s] 50 100 150 200 250 Bell Lab Bell Lab

H.264 Codec设计复杂度 相对MPEG-2 ，解码复杂度增加 2-3倍，编码复杂度增加 3-4倍 问题: 宏块分得更细（更多的搜索） 预测模式更多（更多的搜索） 多参考帧的运动估计（更多的内存，更多的计算） 更长的滤波器 …… Bell Lab

Lucent Technologies Proprietary and Confidential 编码器的硬件实现方案——ASIC Intra Pred. ME MC Transform Q Inverse T IQ Entropy Coding Pixel Data Pixel Interface Host API Embedded CPU Address Generator De-blocking Filter Output Interface Bit Stream 27MHz PLL Memory Controller Bell Lab Lucent Technologies Proprietary and Confidential

Lucent Technologies Proprietary and Confidential 编码器的硬件实现方案——DSP TMS320DM642 Pixel Intf. MC Reconst Transform Q Inverse T IQ Entropy Coding Controller De-blk Filter Internal Memory Pixel Data BUF Bit Stream ME Intra Pred. Memory Control Internal DDR SDRAM Xilinx FPGA Bell Lab Lucent Technologies Proprietary and Confidential

编码器的硬件实现方案——FPGA Pixel Controller Intf. Transform Q Entropy Coding FIFOs SRAMs Transform Q Inverse IQ De-blocking Filter Entropy Coding Output Ctrl. Internal Memory BUF Bit Stream Pixel Intf. ME Intra Pred. MC Reconst. Memory Ctrl. DDR SDRAM Controller Internal Pixel Data Bell Lab

我们的问题 性能，成本和计算复杂度 选择DSP方案 运动估计计算量无法承受 需要一种快速高效的搜索算法 Bell Lab

层次搜索算法 思想 通过下采样，将图像分辨率降低，先在低分辨的图像上作穷尽搜索，得到最优点X’。然后，回到原图像，在X’的邻域内作进一步的搜索，可以得到局部最优XL。 Bell Lab

层次搜索算法——举例 以下采样2倍为例，设搜索范围是正负48，当前编码块的大小是16x16，则原来要搜索9409个点，每个点的计算量是256次减法，255次加法，1次比较，2倍下采样之后，搜索点数下降1/4，为2401，每个点的计算量是64次减法，63次加法，1次比较，总的计算量只有原来的1/16。白点为下采样后剩下的像素，灰色点是被忽略的点。在得到最优点X’之后，对邻近的8个点（黑点）作进一步的比较，取其最小者作为匹配位置。 Bell Lab

层次搜索算法——实现 由（spiral_search_x[k]，spiral_search_y[k]）构成了一个可由k索引的点，随着k的增加，这个点沿着原点作类似于螺旋状的运动。0，1，2……数字即为k，数字所在的位置即为点的位置。 有了这样一个数组之后，下采样意味着调整步长，下采样2倍，只要加倍步长就可以了。邻域搜索也就轻而易举了。 Bell Lab

层次搜索算法——性能1 以dec作为输入视频文件 计算平均值 层次搜索算法有5%左右比特率的增加 但是编码时间却有50%—60%的减少 Bell Lab

层次搜索算法——性能2 以dec作为输入视频文件 SNR相差不超过0.1dB 穷尽搜索算法有5%左右比特率优势 但是编码时间却是以级数增长 Bell Lab

层次搜索算法——性能3 以sign_irene作为输入视频文件 观察每一帧性能变化。 性能差异不是十分明显。 Bell Lab

层次搜索算法——结论 适宜硬件以流水线方式实现 适合大屏幕，高分辨率的情况 图像质量不受影响，比特率增加5%左右，编码时间大约减少60% 系统带宽较为宽裕，瓶颈落在计算能力上，层次搜索算法是一种不错的选择 Bell Lab

自适应搜索算法 启发 对于穷尽算法，搜索范围并非越大越好的，如dec，在搜索范围取16时，已经达到了较佳的性能，再增加范围，就是浪费了；在sign_Irene和tempete中，也有类似情况。 对于层次算法，将会有一个最佳的搜索范围，再增加反而会使性能恶化，因为大的搜索范围会增加出错的概率。 如何寻找最佳？ Bell Lab

自适应搜索算法 思想 假设运动矢量的预测十分准确，则，只要小范围搜索就可以了。 当有运动物体突变，或镜头切换等情况时（预测失效），搜索范围又能及时地做出调整。 Bell Lab

自适应搜索算法 实现 关键在于这个反馈机制 我的想法：如果前一个宏块的运动矢量处于搜索范围的边缘，或者它的费用高出平均水平很多，就应该适当放大搜索范围，反之，则应缩小搜索范围。 Bell Lab

自适应搜索算法——举例 自适应算法 层次算法sr=16 穷尽算法sr=4,8 Bell Lab

自适应搜索算法——举例 可以看到 自适应算法具 有一定的跟踪 最佳搜索范围 的能力。 Bell Lab

自适应搜索算法 结论 这种想法与ADM是一样的，这样搜索范围能自动调整到最佳状态，始终保持在较小的水平。 在实现上，可以用硬件来实现搜索范围的调整，这样，对软件来说，省下了大量的JUMP指令，可以更快。 还处在探索阶段，有很多实际问题需要解决 Bell Lab

结束语 根据硬件特性，寻找合适的快速算法 本文实现了层次搜索算法，并对其性能作了测评，为工程开发提供了极有价值的参考 受到层次搜索算法的启发，本文又设计了一种自适应的搜索算法，此算法还在进一步的探索之中 但是，到目前为止，所有的工作还只是停留在PC上，没有进一步为特定的硬件，特定的视频内容作优化。 Bell Lab

结束语 视频编码的发展，已历四十年。近年来，又出现了很多新兴的图像压缩编码方法——模型基法，分形法，人工神经网络法等等。 算法同样存在着复杂度大的问题。如何调解性能和计算复杂这对矛盾，是一个很现实，很迫切的问题。 Bell Lab

结束语 相信，随着硬件速度的不断提高，编码算法的不断改进，多媒体网络将会得到更为迅速的发展。 Bell Lab

致谢 首先，向我的毕业设计的指导老师-朱杰表示我的感谢和敬意。在整个毕业设计的过程中，朱老师热情地对我的工作予以了指导，并尽可能地为我提供各种便利条件。同时，我更要感谢的是甘小莺学长和贝尔实验室的阎安、邓航师长，是他们给了我机会、指导和鼓励，并提供大量的资料和宝贵的建议。 Bell Lab

谢谢！ QUESTION？ Bell Lab