第一章 绪论
1.1 研究背景及意义
随着信息技术的迅猛发展，视频应用已渗透到人们生活中的各个角落。网络上的视频传输、视频聊天、视频监控等多方面的应用，让视频成为人们生活中不可缺少的一部分,而视频的广泛应用将视频的标准提升的越来越高。首先，人们对视频清晰度的要求越来越高，通过高清的视频带给我们更好的娱乐体验，因此视频分辨率从 270P 逐渐发展到 1080P 甚至更高。其次，对于当下各种小视频直播软件的应用，人们更希望视频能够实时的分享到网上，所以对视频传输的实时性又提高了要求。视频的实时传输以及视频的高清质量，要求对视频进行快速有效地压缩。原因在于，未经压缩的视频所含数据量非常庞大，即使硬盘的容量很大也存储不了几部电影，也很难将原始视频在网络上进行传输，更谈不上对其进行实时性传输。如果对视频进行合理压缩，进而减少视频中所含的冗余数据，将会大大减少视频的存储容量且能够满足视频的实时性传输要求。因此，视频压缩技术是科研人员致力于发展和改进的一项关键技术。视频压缩技术是指对视频进行压缩且在保证视频质量一定的情况下将原来表达视频信息的重复数据减少的一种技术[1]。
视频压缩包含多个步骤，其中帧间预测是视频压缩过程中的重要步骤。运动估计算法在帧间预测和视频压缩过程中具有重要作用，运动估计算法占视频压缩60%至 80%的运行时间[2]-[3]。因此，想要提升视频压缩效率，对运动估计算法的有效优化至关重要。运动估计算法的目的是通过消除相邻帧之间的时间冗余来进行视频压缩。一些视频应用存在实时处理的需求，这些需求需要很高的处理速度，这对运动估计的性能提出了挑战，如果不能对运动估计算法的性能进行有效的优化，将无法满足对视频实时处理的要求。如何解决好运动估计算法优化存在的问题，对视频压缩有着至关重要的作用。
............................
1.2 国内外研究现状
与本研究相关的研究工作主要分为以下几类（1）运动估计算法改进；（2）数据并行处理；（3）数据重用。
（1）运动估计算法改进
有一部分学者从运动估计算法改进的角度对其进行优化。为了解决 HEVC的耗时，Radicke 等人提出了一种具有一组算法的混合编码体系结构，探索图形处理单元以高度并行的方式执行单预测和双预测运动估计。这降低了中央处理单元上的单一预测和双向预测 ME 的复杂性，分别高达 99％和 95％，并且对低延迟和随机访问编码设置的总时间节省高达 57.65％和 54.16％。在这两种情况下，率失真性能仅受到轻微影响[6]。Wei Zhou 等人提出了基于预测的快速混合搜索算法（CPFMS），算法利用运动矢量的空间和时间相关性，以及所有零块的特征来加快搜索过程。随着初始搜索点预测、自适应搜索窗口的搜索方向的改变和决定，CPFMS 不仅能够减少块匹配过程的计算，效率也优于一些流行的快速算法[7]。张斌等人以视频编码标准 H.264 采用的运动估计算法为基础，提出一个快速整像素运动估计算法，将算法中的六边形搜索替换为八边形搜索，根据当前最佳运动矢量方向，决定将要搜索的子模板，该算法能在保证良好的率失真性能的情况下，平均节省 25.919%的运动估计时间[8]。曹雪情等人针对分布式视频压缩中非关键帧重建质量较差的问题进行了研究，提出了一种基于半像素插值技术的残差多假设块迭代重建算法。算法对关键帧进行半像素插值生成当前非关键帧的边信息，然后在测量域内对非关键帧与边信息求残差，并对残差进行多假设重建，最后将重建的残差与边信息进行融合得到重建的非关键帧，基于半像素插值改进的多假设块迭代重建算法提高了非关键帧的重建质量[9]。
有些研究工作是从搜索的自适应性方面对算法做了改进。王泉等人提出了一种使用具有方向偏向性搜索模板和基于预测模式自适应选择运动估计方案的EPZS(Enhanced Predictive Zonal Search)改进算法。该算法将运动估计过程与H.264/AVC 中多参考帧、多预测模式等编码工具紧密结合，充分利用视频中运动具有高度时空相关性的特点,综合考虑速度、图像质量及压缩效率等方面的性能[10]。沈燕飞等人在连续消除算法和多阶连续消除算法的基础上提出了一种自适应的快速全搜索运动估计算法,进一步的降低了视频编码中全搜索运动估计的计算需求,并且运动估计的精度和全搜索算法完全一样实验结果表明,该算法在 SEA和 MSEA 的基础上又进一步的降低了 15％-27％的计算需求,并且该算法可以和其他的任何一种快速运动估计算法相结合来减少视频编码的计算量及其 VLSI 的功耗[11]。
.............................
第二章 相关理论知识
2.1 GPGPU 与 CUDA 简介
2.1.1 GPGPU 简介
图形处理器（Graphics Processing Units，GPU）的通用计算能力(General Purpose GPU ,GPGPU)发展的越来越快。早先 GPU 主要针对图形图像进行处理，最近几年 GPU 随着时代的发展也得到了很大的改进,最重要的是 GPU 突破了CPU 在浮点计算能力上的限制，能够达到每秒万亿次的浮点操作。由于 GPU 的浮点运算能力比 CPU 更强，GPU 的通用计算能力的重要性受到人们越来越多的重视。CPU 一般包含多个重量级核心，主要用来处理非常复杂的控制逻辑，用于优化串行程序的执行；GPU 一般包含众多的轻量级核心，用于优化具有简单控制逻辑的数据并行任务，注重并行程序的吞吐量。另外，GPU 独特的存储架构使得 GPU 的存储访问能力优于今天的 CPU。故 GPU 不再仅仅只对图像进行处理，也能够对非图像应用进行计算处理或优化加速。
对 GPU 超强的计算能力的使用并不意味着要取代 CPU 计算，每个应用程序都有适合自己的计算方法。当处理控制密集型任务时采用 CPU 比较适合，当处理的数据需要并行计算时采用 GPU 更适合。如果将两者相结合，能有效提高大规模数据计算的速度。图 2.1 展示了 CPU 和 GPU 的应用范围。
.............................
2.2 运动估计
2.2.1 运动估计的定义
视频是由一系列的视频帧组成的，每一帧可以看成一幅图像，视频序列中相邻的两帧所包含的信息差别往往很小，甚至是相同的。比如常见的视频监控，如果仔细观察相邻帧中的信息，就会发现相邻帧之间的重复信息非常多，而这些重复的信息被称为时间冗余信息。因此，如果在视频处理中去除这些冗余信息，会大幅度提高视频编码的效率，且不会造成视觉上的影响。在对视频进行编码时，编码器可通过一种算法对视频帧内运动的图像区域生成它的运动矢量，对此运动矢量进行存储，这种方法所用的比特比存储运动图像区域少很多，从而达到视频压缩的目的。
运动估计算法就可以从视频序列中提取运动图像区域的运动矢量，但运动估计算法研究的主要是如何快速有效地获取精度比较高的运动矢量。基于像素块的匹配方法考虑了运动估计的精度和复杂度，是基于像素的运动表示和基于区域的运动表示的一个折中，故基于块的运动表示方法是目前最常采用的方法。这种方法的基本原理就是将视频中的每一帧分成多个大小相同的区域，称为当前块，并假定当前块内所有像素的运动矢量都相同，然后在参考帧中的搜索窗中找到当前块的最佳参考块，最后生成其运动矢量（MV），其匹配过程如图 2.4 所示。这种方式与其他匹配方式相比，实现比较简单，搜索运动矢量能力比较强，因而在本文中采用的是这种匹配方法。
............................
3.1 引言........................................ 15
3.2 基于 GPU 三种类型片上存储器的参考块之间的数据重用...................... 15
第四章 基于 GPU 多层次存储架构的全搜索运动估计数据重用方法.................. 29
4.1 引言........................... 29
4.2 参考块之间+参考块条带之间的双层数据重用....................... 30
第五章 总结与展望................................. 41
5.1 总结...................................... 41
5.2 展望.................................... 41
第四章 基于 GPU 多层次存储架构的全搜索运动估计数据重用方法
4.1 引言
第二章介绍了 CUDA 的存储模型，每种存储类型既有优点又有缺点。例如，共享内存比全局内存的访存速度要快，带宽大约为 1.5TB/s，访问延迟为 1~32 个周期。共享内存的容量虽然发展到 64KB~128KB，但共享内存的存储容量比全局内存的存储容量要小。寄存器的访存速度比共享内存的访存速度要快，带宽大约为 8TB/s，访问延迟为 1 个周期。寄存器的容量可以达到 32KB 甚至 64KB，但寄存器的存储容量比共享内存的存储容量要小很多。相关研究人员在算法优化时，主要考虑的是将搜索窗之间的数据重用和共享内存结合，把搜索窗中的数据存储到共享内存中，避免多次重复访问片外存储，节省了大量的时间。但单层数据重用优化方法存在以下几点不足：（1）若只采用参考块之间的数据重用，重用的数据比较少，优化之后算法运行效率提高不明显。（2）单层数据重用仅仅只对 GPU 片上的一种存储器进行利用，不能对 GPU 片上存储资源得到最大限度的利用，从而不能充分利用 GPU 多层次存储架构的优点。GPU 中不同层次的存储器可采用不同的数据重用方法，例如将寄存器中参考块之间的数据重用与共享内存中参考块条带之间的数据重用相结合。该方法可以充分利用 GPU 片上存储资源，提高算法运行速度。
..............................
第五章 总结与展望
5.1 总结
本文首先针对 GPU 的多类型片上存储器，提出了基于 GPU 多类型片上存储器的全搜索运动估计数据重用方法，然后针对 GPU 的多层次存储架构，提出了基于 GPU 的多层次存储架构的全搜索运动估计数据重用方法。本文的主要研究内容总结如下：
（1）提出了基于 GPU 多类型片上存储器的全搜索运动估计数据重用方法，分别为基于 GPU 的参考块之间的数据重用、基于 GPU 的参考块条带之间的数据重用、基于 GPU 的搜索窗之间之间的数据重用和基于 GPU 的搜索窗条带之间的数据重用。在参考块之间的数据重用方法中，将参考块数据分别存放在 GPU 中的寄存器、共享内存、本地内存以及高速缓存实现参考块之间的数据重用，并比较分析不同存储条件下运动估计算法的运行效率。将参考块条带数据、搜索窗数据以及搜索窗条带数据存放在共享内存中，在共享内存中完成对数据的重用。在GPU 平台上分别对上述四种数据重用进行了实验，并对四种数据重用的实验结果进行了比较分析。
（2）提出了基于 GPU 多层次存储架构的全搜索运动估计数据重用方法，分别为参考块之间+参考块条带之间的数据重用、参考块之间+搜索窗之间的数据重用和参考块之间+搜索窗条带之间的数据重用。参考块重用的数据较少，将参考块数据存放在寄存器中，将参考块条带数据、搜索窗数据和搜索窗条带数据存放到共享内存中。这种数据重用设计方法，不仅满足 GPU 对数据的存储要求，而且有效降低存储带宽的要求。为证明提出的双层数据重用方法对算法优化的力度，在 GPU 平台上对上述三种双层数据重用方法进行了实验，并对三种双层数据重用的实验结果进行比较。实验结果证明该优化方法可以有效避免多次将重复使用的数据从 GPU 片外读到 GPU 片上，能够有效提高算法的运行效率。
参考文献（略）