基于GPU的块匹配运动估计技术研究

1、block-matching based on gpu for motion estimationconghuan yecollege of computer and information science, xiaogan university, xiaogan, hubei, china abstract：currently, more and more high-resolution video images video codec needs to be addressed also will dramatically increase the amount of data, as p

2、owerful gpu computing power, making the h264 gpu-based video coding technology, has great application value. as the cpu in dealing with massive network video coding and slow speed of existing bottlenecks, this paper presents an improved sub-pixel motion estimation algorithm, mainly sad sub-pixel mot

3、ion vector estimation exercise. the experiment confirmed that improved, high efficiency, feasibility, etc. experimental results show that the proposed gpu-based block-matching motion estimation algorithm could achieve good performance in comparion with the cpu-based method . keyword：gpu；block-matchi

4、ng；motion estimation 基于gpu的块匹配运动估计技术研究叶从欢 孝感学院 计算机与信息科学学院, 孝感，中国，432000【摘要】视频图像的分辨率越来越高视频编解码需要处理的数据量也随之急剧增大,由于gpu的强大运算能力，使得基于gpu的h264视频编码的技术研究，具有很大的应用价值。由于cpu在处理网络海量视频图像编码中存在的速度慢等瓶颈，本文提出了一种gpu上的块匹配运动估计技术。试验证实该方法大大提高编码的加速比。 【关键词】 gpu; 块匹配;运动估计 1 绪论随着网络通信技术和图形技术的飞速发展，互连网用户使用网上大容量的视频也变得越来越便利。但是要满足用户对高质

5、量视频的需求，要有很多工作要做。目前随着三网合一技术的推进，视频信号将广泛应用于日常生活中，则需要高效率的压缩算法。由于gpu图形处理器的快速发展，基于gpu的通用计算已经成为一个新的研究领域。通过对nvidia公司最新的通用计算gpu编程模型的研究，作为h.263之后新一代的视频通信标准，h.264理应具有更好的性能。h.264的编码框架与以往的视频标准类似，都是基于混合编码的框架。首先，将待编码宏块通过运动估计算法搜索帧内或帧间的相匹配宏块，再将匹配块和待编码宏块的图象差值经过dct变换、量化等处理，这大大提高了视频压效率。而h.264标准通过改进技术方案以及应用新的算法，使视频编码性在各

6、个部分又得到提升。在相同的视觉质量下，h.264标准的编码效率可提高50%1，但是h.264的高压缩率是以编码的高计算量为代价，例如，使用264编码器在intel双核cpu上编码高清视频(1920*1080分辨率)，平均每秒只编码1.2帧，一部两个小时的电影需要41个小时编码才能完，而实时高清视频传输更是困难，因此如何提高编码效率是目前的研究重点。在相同视频质量，h.264的编码复杂度是mpeg-4的510倍，而解码复杂度也是mpeg-4的24倍2。另外，图形硬件gpu的处理速度进来更是发展迅速，计算能力以每年2.8倍的速度增长，远远高于cpu的发展速度。gpu的体系架构是基于大规模并行的体系

7、架构，目前gpu已经采用强大而灵活的统一渲染架构3 ,其体系架构的设计主要围绕着两大要素:多层次的并行计算和高效率的数据访问。gpu 上的并行性主要体现在3 个层面:任务并行的多级流水线,数据并行的多线程技术以及指令并行的单指令多数据流( single instruction multiple data, simd)。在数据访问方面，gpu 上的内存系统由外部显示内存、内部高速缓存和寄存器3 个层次构成。由于gpu 高速缓存主要用于加速纹理过滤,因此其容量非常有限而且仅能只读。gpu 内存系统侧重追求单位时间的数据吞吐量，即带宽，并采用多线程技术来掩盖高达数百个时钟周期的主存访问延时。相对于c

8、pu，gpu更适合进密集型运算，而h.264标准中的运动估计就属于密集型运算，非常适合在pu上进行并行处理。为了合理利用gpu通用计算的资源，cuda4（compute unified device architecture，统一计算设备架构）应运而生。cuda是一种并行编程模型，它将pu的可编程顶点渲染器和片元渲染器集成起来，组成统一的spmd(a single program muliple data)计算设备，所以，若能够将gpu并行计算的能力发挥在视频编解码领域，将会逐步满足用户对网上实时视频传输的需求。虽然现有的gpu为视频编码提供了并行计算的平台，提高了视频编码的效率，但是对于实时

9、视频技术而言，例如，视频会议，无线通信，实时体育赛事视频等一些对实时性要求比较高的，其视频质量并不能满足用户的需求。虽然网速越来越快，但是如果视频编码不好的话，经过网络传送到客户端的视频数据量同样会非常巨大，再加上网络环境的不稳定性，也即网络流量的突发性，都会对实时持续的传播视频造成非常大的影响，从而对用户的服务质量降低。虽然gpu的出现，为视频编码的并行可编程性在硬件层面提供了较好的支持，但是即使再好的硬件平台如果没有好的软件平台的话，其性能不仅得不到充分利用，而且在市场的占有率方面将会下降，从而使得gpu的研发成本难以下降。限制gpu等硬件设备性能的进一步提高。因此，为了充分利用gpu的性

10、能，并使得在线的实时视频技术得到提高，需要在软件方面同步优化，要充分挖掘视频编码方面的并行可编程性。h.264视频编码就是这样的一种典型的并行流处理应用,适合于在支持cuda的gpu上进行优化加速4.2 相关工作2.1 h.264编码的可并行性分析由于h.264编码需要进行大量的计算，目前已经有多种利用硬件平台的性加速h.264编码的方法，下文根据不同层次结构的特点介绍h.264的并行理的研究现状：(1) gop(group of pictures)级并行：h.264将图像序列分为多个gop，各gop之间相关性很低，不仅可以限制误码扩散，还可以进行并行编码处理 56。 (2) frame级并行

11、：编码时，p帧都是将已编码的i帧或p帧为参考帧，而b帧将前后两个已编码完成的帧作为参考帧。如果两相邻帧没有相性，就可以对它们并行编码78，加快编码速度，以用于对实时性要求比较高的场所。(3) 块级并行：h.264编码器也每帧图像划分多个块，对于若干独立的块，采用并行处理技术，这也是在gpu上实现h.264编码时采用较多的一种技术。2.2基本原理一般摄像机等图像采集设备采集的原始视频都是图像序列，由于背景是相同的，序列中相邻两帧图像之间差别往往很小，对于场景镜头变化不大的视频，甚至相同，如果能去除相邻帧之间的冗余信息，会大大提高编码的压缩率，且不会有明显的视觉误差。如何消除帧间的重复信息，就需要

12、进行帧间预测的技术。在进行视频编码时，编码器把图像帧内运动的图像区域通过一种算法提取其运动矢量，并且只存储运动矢量，这比存储运动图像区域所用比特少，对于h.264标准来说，帧间预测涉及到的核心技术主要是运动估计与补偿。而h.264的亮度运动补偿块则采用分形学原理，从大到小按树状结构分布，共有7种尺寸的运动补偿块:1616、816、168、88、48、84、44。这些也是目前算法复杂度最高、性能最好的基于混合编码框架的视频编码技术,它采用了多种在以前视频编码标准中不曾出现过的新技术。其中可变尺寸块、多参考帧和1/4像素精度是h.264运动补偿技术的三个新特征。分数像素运动补偿要求以原参考图像插值

13、后的图像作为新的参考图像,然后进行运动补偿预测,从而运动矢量的精度达到分数像素精度。运动矢量位移的精度越高,帧间剩余误差越小,传输码率越低,压缩比越高。运动补偿精度增加一倍,可以得到0.15 bit/sample的编码增益,但是实际越过1/8像素后,继续通过提高精度来改善运动补偿的性能的意义就不大了。目前的标准中, h.263的运动补偿精度达到1/2像素, h.264在指定过程中虽然尝试采用1/8像素精度的运动补偿,但最终亮度信号还是定为1/4像素。通常具有1/4像素精度的运动估计可以通过基本算法,sad(绝对误差和)值相关性估计的算法,或sad二次曲线分布的近似估计算法等实现，而为了达到快速

14、运动估计，本文采取了1/4像素级的运动估计算法。运动估计就是从图像序列中提取运动图像区域的运动矢量，而运动估计研究的主要内容就是如何快速有效地获得精度足够高的运动矢量。运动估计的基本原理是将视频中的每一图像帧分成多个相同大小的图像区域，称为宏块，并假定宏块内所有像素的运动矢量都相同，然后在参考帧中搜索与当前宏块最匹配的宏块，这就被称为块匹配法，而确定最佳匹配块的方法，被称为运动估计匹配准侧。与其他匹配方法相比，块匹配法实现最为简单，且运动矢量搜索能力强，h.264视频标准就采用了块匹配法。目前，有多种运动估计匹配准则，下面就简单介绍常见的四种匹配准侧：平均绝对误差准则(mae)，均方误差准则(

15、mse)， 绝对误差准则(sad)， 原始图像块和重构图像块间的误差平方和。如下（1），（2），（3）和（4）所示。 (1) (2) (3) (4)2.3经典的并行运动估计算法全搜索法(fs)也被称为穷尽搜索算法，是对搜索域内的所有位置计算sad值，并从中找出最小sad，其对应原点的偏移即为最佳运动矢量。目前，多数快速搜索算法都是基于搜索模板的，使用不同大小和形状的搜索模板其搜索速度和性能也不同。比如搜索模板中搜索半径过大，容易产生错误搜索方向；而搜索半径过小，则容易得到局部最优解。9提出了一个运行消除无用搜索点算法的并行结构，该算法主要用于块匹配运动估计，可以成功的清除搜索窗中的无用搜索点，

16、从而达到减少块匹配比较的数量。相对于全搜索，大大减少计算量，可以减少57%的计算量。该方法不仅提高搜索效率，而且为帧间预测的并行计算提供了更快更准的块匹配算法，同时为h.264的实时编码，以及实时视频应用提供了好的解决方案。10利用gpu的并行运算能力来解决图像处理中的密集型的计算问题，并行加速了图像处理的进程。正是基于快速提高视频的编码质量，当前，利用gpu解决h.264的编码问题成为一个非常热门的研究领域。11利用gpu的并行处理能力来加速块匹配进程。12,13在gpu上采取多通道和帧并行技术来加速视频编码中的运动估计，并使得整像素运动估计和分数精度像素的运动估计得加速比分别达到12倍和3

17、5倍左右。3 gpu上的并行运动估计h.264编码的时候，首先是将图像分割成很多个宏块，然后再对各个宏块选择最合适的编码模式进行编码，而编码模式又主要分为帧内预测和帧间预测。帧内预测模式是为了消除视频图像序列的空间冗余，主要采用44和1616子块的两种模式，其原理是利用周围已经编码的宏块预测当前宏块的系数，然后将当前宏块和预测值的差值进行变换编码，从而提高压缩效率。帧间预测是为了消除视频图像序列之间的时间冗余，h.264标准中，帧间预测采用了可变块的运动估计技术，比如亮度宏块可以分为1616、168、816、88的宏块分区，而每一个88的块，又可分为84、48、44的宏块子分区，每个分区都要进

18、行运动估计 对于44的块中，对于匹配块中每一个内插的像素点,都可以采用最相近邻整像素点进行内插,各亚像素的像素值是通过整像素像素值的线性计算得到。实际应用中, 1/2像素值由周边6个像素亮度值按(1,4,18,18,-4,1)加权中值滤波得到。然后用线性插值获得1/4像素样本。对于4:1:1的视频格式,亮度信号的1/4像素精度对应于色度部分1/8像素的运动矢量,对色度信号1/8像素的内插运算可用8抽头滤波器实现, 采用双线性内插. 整像素点与内插亚像素点之间存在相关性,因此可以通过整像素的sad值来估算内插亚像素点的sad值。先分别在x和y方向分别做1维的最佳匹配点计算, 得到运动矢量在x 方

19、向的分量和y方向的分量, 最后对两个分量进行合成得到最佳运动矢量.运动矢量合成的具体过程是，搜索整像素最优匹配点,可以通过菱形算法等。对当前重建的参考帧, 进行二次内插建立1/4像素精度的参考帧。gpu的体系架构属于单指令流，多数据流。而对视频的某一单一场景帧可以通过关键帧之间的插值进行运动估计，这些帧的运动估计可以在gpu上进行并行处理，并行处理是指将数据或指令并发处理，主要分为空间上和时间上的并行。空间上的并行是指在多处理器或多核上并发的执行代码，gpu上sads的并行计算模型如图1所示。而时间上的并行则通常指流水线技术。 figure 1. the block matching rame

20、work for me图1. 块匹配流程 4 实验与讨论为了评估本文提出的方法，我们在实验环境为：intel(r) pentium（r）d cpu 2.80ghz，1gb的内存，microsoft visual studio 2005，以及nvidia geforce 7800gt，显存256mb, cuda toolkit，对stefan，格式为cif（352 288）系列进行测试，对cpu与gpu的处理性能运行时间统计如图2所示。 figure 2. the performance of the proposed method图2. cpu与gpu编码速度统计 在试验中，我们对大小为161

21、6的块匹配过程分别在cpu上，以及cpu+gpu上，试验效果如图3所示，横轴1，2，3对应的搜索区域大小为1616，3232，6464，而纵轴为编码的速度（帧/秒）。由图2可知，基于gpu+cpu的块匹配过程性能明显优于cpu， 1616搜索区域在块匹配进行搜索时加速比最高，可达到5，其他两种搜索区域的加速比接近5。 5 结论由于现阶段人们对高质量实时的视频需求越来越高，而传动的视频编码技术根本达不到互联网用户的日益增长的需求，正式因为如此，h.264可以在编码方面取得较高的效率，但是该效率是以牺牲编码的复杂度为前提的，不利于视频的实时编码。本文采取一种基于gpu的并行块匹配算法来估计运动矢量

22、，该方法相对于传统的全搜索算法，都可以成比例的减少计算量。 references (参考文献)1 ostermann j.，bormans j.，list p.et al.video coding with h.264: tools，performance and complexity.ieee circuits and systems magazine，2004，4(1):7282 m.ravasi，m.mattavelli,c.clere.a computational complexity comparison of mpeg-4 and jvt codecs.joint video t

23、eam(jvt)of iso/iec mpeg&itu-t vceg，jvt-dl53rl-l，2002,(7):22-263 blythe d. the direct 3d 10 system j. acm transactions on graphics, 2006, 25(3): 724-7344 nvidia,nvidia cuda compute unified device architecture -programming guide version 2.1，5 denilson m.barbosa，joao paulo kitajama，wagner meira jr.et a

24、l,“parallelizing mpeg video encoding using multiprocessors”，proceedings of the xii brazilian symposium on computer graphics and image processing，19996 e.b.vander，e.g.t.jaspers，r.h.gelderblom，“mapping of h.264 decoding on a multiprocessor architecture”，spie conf.on image and video communications and

25、processing，2003.5(7):707-7187 yen-kuang chen，eric q.li，xiaosong zhou，steven ge，“implementation of h.264 encoder and decoder on personal computers”，2005,10(8):960-9838 yen-kuang chen，matthew holliman，eric debes，sergey zheltov，alexanderknyazev，stanislav bratanov，roman belenov，ishmael santos，“media app

26、lications on hyper-threading technology”，intel technology journal q1，2002,6(1):960-983，9 srinivasarao, b.k.n.; chakrabarti, i.; a parallel architecture for successive elimination block matching algorithm . computer vision, graphics & image processing, 2008. icvgip 08. sixth indian conference on 2008 , page(s): 226 - 23110 nan zhang;