毕业设计（论文）-多视点视频编码研究.doc

保密类别 编 号 20091001* 毕 业 论 文多视点视频编码研究2013年 5月 20日2 多视点视频编码研究摘要本文在详细研究JMVC编码器（包括对JMVC代码的阅读调试、对各个编码参数的提取及显示）的基础上，对JMVC编码器进行改进使其在PSNR和码率几乎不变的情况下编码时间明显减少。本文在详细阅读JMVC代码的基础上，首先提取编码参数并创建了一个非常直观的编码参数显示界面，利用ChartDirector库和opencv库，将所有的以帧为单位的参数都显示在图表之中，所有的以宏块为单位的参数都显示在图像控件上。可以观察到整个序列的码率、PSNR等参数的整体波动情况，并可以把一帧图像所有运动矢量、宏块划分等信息直观显示在图片上。然后针对JMVC代码的运动估计算法，本文提出了一种新的改进方法，以往的改进都是通过各种方法确定菱形算法的步长阈值，当步长大于阈值时即直接退出，这种方法虽然明显减少了编码时间，但由于减少了搜索模板的搜索范围，PSNR和码率也会有一定程度的下降。本文从另外的角度来改进菱形算法，即不设定某个确定的步长阈值作为提前终止的条件，而是根据运动搜索中最优点是否多次没有变化来作为提前终止的判断条件。另外借鉴JM模型内的UMHexagonS算法的思想，本文还引采用入了更多地预测矢量；引入基于SAD的提前终止策略。通过以上多种方法的结合，可以实现在PSNR和码率几乎不变的情况下，编码时间减少20%左右。关键词：多试点视频编码，运动估计，JMVC，视差估计目 录（有）摘要IABSTRACTII目 录1一、绪 论2（一） 课题研究的背景和意义2（二） 多视点视频编码技术概况（以JMVC模型为例）2（三） 本文章节安排4二、单视点视频编码技术简介5（一） 视频编码技术概况5（二） 基于H.264标准的JM编码器介绍6三、JMVC代码阅读及编码参数提取10（一） JMVC代码基本流程10（二） 编码参数的提取11（三） 编码参数的显示与分析13（四） 本章小节19四、各种运动算法的分析及比较21（一） 运动估计算法简介21（二） 运动算法比较平台的搭建27（三） 各种运动估计算法实现和的性能分析27五、JMVC运动搜索算法改进38（一） JMVC中的TZsearch算法38（二） 改进方法38（三） 改进效果39六、结论42参考文献43后记44附录45一、绪 论本章首先介绍了本论文的选题背景及意义，然后介绍了单视点视频编码和多视点视频编码的主要技术和研究现状。（一） 课题研究的背景和意义多视点视频是利用不同位置的摄像头对同一场景进行拍摄得到的视频数据，它包含了丰富的3D场景信息，可以为用户提供传统单视点视频无法比拟的视觉感受。多视点视频被广泛应用于3D电视、自由视点电视 (FreeViewPoint Television，FTV)、视频会议、远程医疗和虚拟现实等领域1。多视点视频的数据量随着视点个数的增多而成倍增加，为了解决其传输和存储的问题，多视点视频编码 (MultiviewVideoCoding，MVC)对多视点视频数据进行高效的压缩。随着新一代显示设备的出现以及用户对真实视觉感受的需求，MVC逐渐成为视频编码领域的研究热点之一。传统的视频编码算法主要是利用了编码信息在时间和空间上的相关性来降低计算量。而在MVC中，多个视点的视频来源于同一场景，它们除了在视频内容上相似之外，还在编码信息上具有很强的相关性，因此MVC可以充分利用视点间编码信息的相关性来加速编码过程。通过编码参数显示界面分析编码器的性能，可以直观的反映各个视点的码率的大小、编码时间的长短以及每一帧的各种类型宏块的分布、运动矢量和视差矢量的分布。从中可以找到编码器需要改进的方面。比如编码时间曲线显示I帧编码时间远远小于B帧和P帧的编码时间，而B、P帧与I帧的最主要不同就是进行了大量的运动估计，因此提高运动估计的效率是本文减少编码时间的关键；另外通过视差矢量的分布可以发现视差矢量的水平位移远大于垂直位移，所以搜索最优视差矢量时的水平位移范围要远大于垂直位移范围等等。（二） 多视点视频编码技术概况（以JMVC模型为例）JMVC模型的视点内编码部分与JM模型的架构几乎完全相同。即帧内预测部分、熵编码部分的算法并没有改变。所以并对JMVC的帧内预测和熵编码做单独介绍。本小节只介绍JMVC和JM模型的主要不同。（1） 预测结构由于JM模型模型面向单视点，所以预测结构是简单的IPBBIPBB.类型，其中B帧的数量可变，由于只有一个视点，所以GOP序列是一维的，只有在时间方向上的延伸。但是JMVC由于引入了视点间预测，其预测结构也必然发生改变。JMVC的预测结构如下图1.1所示图1.1 JMVC的预测结构（该图引自文献5）图中总共有八个视点，每个视点的GOP长度均为8（编码时GOP长度可以在配置文件中修改）。在时间方向上，该结构采用了分层B帧结构来提高时域预测效率;在视点方向上，该结构使用了IBP预测结构来提高视点间预测效率。图中T0时刻以及T8时刻各视点的帧只需要同时刻的参考帧就可以进行重建，将这些帧称为锚定帧;图中Tl时刻到T7时刻的帧需要其它时刻的参考帧才可以进行重建，将这些帧称为非锚定帧。在时间方向上，锚定帧以及锚定帧和前一锚定帧之间的帧组成一个图像组 (GOP)。视点S0只采用时间方向预测，称为基本视点(Baseview)，可以直接用H.264解码器进行解码，实现向下兼容H.264功能的要求。非基本视点（non-baseview)可以采用视点间的预测。可以在编码配置文件中设置视点的依赖关系（即编码顺序，比如途中的依赖关系就是0-2-1-4-3-6-5-7），某一视点的参考视点必须在该视点之前编码。并且设定锚定帧和非锚定帧是否采用视点间预测。（2） 参考帧由于JMVC采用了视点间预测，所以必须将当前时刻参考视点的图像放入参考帧列表中，然后对参考帧列表中的所有参考帧（包括同一视点和不同视点的）都进行运动搜索，在所有参考帧中得到一个最优匹配块，由于来自不同的视点，所以采用的运动估计算法最好有所区别，比如在不同视点参考帧中加入视差矢量作为预测矢量等。而JM模型的参考帧列表中的参考帧都是来源于单一视点，并无区别。（3） 运动搜索算法目前JM模型采用UMHexagonS （非对称十字型多层次六边形格点搜索算法）作为其快速搜索算法，而JMVC模型采用TZsearch算法作为其快速搜索算法。两种算法的详细说明及简单比较见第三章。（三） 本文章节安排第一章介绍了课题研究的背景和意义，包括多视点视频的应用，以及多视点视频编码的主要技术和研究现状。第二章介绍了单视点视频编码的主要技术和研究现状，因为单视点编码是多视点编码技术的基础，而且JM模型是非常成熟的编码器，对JM代码的研究可以为JMVC代码的阅读打下良好基础第三章利用JMVC编码器对测试序列进行编码，并将各种编码参数通过ChartDirector库以各种图表的形式显示出来。根据显示的编码参数对JMVC编码器性能进行分析。第四章分析各种运动估计算法并对其进行比较，因为一般来说，运动估计是编码器中复杂度和运算量最高的部分，而且JMVC运动估计所采用的TZsearch算法的运算复杂度非常高，速度特别慢，有较大提升空间。通过深入分析各种运动估计算法为优化编码器做基础。第五章对编码器进行优化，希望在几乎不降低比特率和PSNR的基础上加少编码时间。主要方法有：新增预测矢量（同前一帧相同位置宏块的MV、视差矢量）、 利用相邻宏块的Sad评价值作为TZsearch算法的提前退出阈值、用最优预测适量连续三次不同步长的菱形搜索模板搜索后没有改变这一条件作为钻石搜索的提前终止条件等。实验结果表明，在几乎不降低码率和PSNR的基础上，改进后JMVC编码器减少编码时间20%25%左右二、单视点视频编码技术简介虽然多视点视频编码和传统的单视点视频编码相比有较多不同，但是基本思想是一样的，毫无疑问单视点编码是多视点编码的基础，全面了解单视点编码技术对分析和改进多视点编码器的性能有很大帮助。（一） 视频编码技术概况原始视频的数据量虽然巨大，但它们在时间、空间、以及统计上都存在大量的信息冗余。从20世纪中期以来，由于数据压缩技术的发展和完善，极大的推动了视频编码技术的前进。一些经典的视频编码技术随之出现，主要技术分为以下几个方面23:1.预测编码预测编码是根据离散信号之间存在着一定关联性的特点，利用前面一个或多个信号预测下一个信号进行，然后对实际值和预测值的差（预测误差）进行编码。如果预测比较准确，误差就会很小。在同等精度要求的条件下，就可以用比较少的比特进行编码，达到压缩数据的目的。预测编码指的是利用像素的时间上或者空间上的相关性计算预测值，并对实际值和预测值之间的差值进行编码，如果预测比较准确，误差就会很小，因此可以用较少的比特进行编码。预测编码按预测方法可以分为线性预测编码和非线性预测编码。线性预测编码由于算法简单、易于硬件实现，在视频编码中更加常见。其中最为常见的线性预测编码方法是差分脉冲编码调制 (DiffereniialPulse CodeModulation，DPCM）。预测编码分为帧内预测编码和帧间预测编码（按预测方向划分）。帧内预测编码利用帧内已预测像素的信息，帧间预测编码利用时间上更早编码的帧上的像素进行预测。通常情况下，视频内容变化和摄像头运动都比较平缓，相邻帧像素之间的相关性要比帧内像素的相关性要大。因而帧间预测编码的整体效率比帧内预测编码的效率要高。在帧间预测编码中，每帧被分成若干个块，每个块到邻近重建帧中搜索对应的匹配块，然后计算当前块和匹配块在空间位置上的相对偏移量，最后对当前块和匹配块的残差以及空间位置相对偏移量进行编码。得到的相对偏移量称为运动矢量，获取运动矢量的整个过程称为运动估计或运动搜索。2.变换编码变换编码指的是将原本的二维空间方向上的像素值通过变换映射到到另一个正交矢量空间中，然后对转换后的系数进行量化和编码。在目前视频编码标准中，最为常见的就是离散余弦变换 (DiscretecosineTransform，DCT)。虽然DCT算法复杂度较高，但随着一些针对DCT的快速算法（FFT）的提出，DCT很快被各种视频编码标准所采用。在每帧图像在经过帧内和帧间预测之后，得到的残差数据的数值已经较小，但这些残差数据之间仍然存在很强的相关性。使用DCT变换可以将残差数据从空间域变换到频域，大多数能量都集中在低频部分，量化之后可以有效的解除残差系数之间的相关性，以达到数据压缩的目的。3.嫡编码嫡编码的原理是利用信源的统计特性对数据进行压缩，它是一种无损压缩编码技术。常用的嫡编码有霍夫曼编码、算术编码和游程编码。霍夫曼编码是根据变字长编码 (variableLengtnCode，VLC)理论设计，它被广泛用于视频编码标准。霍夫曼编码根据输入符号的统计概率大小分配不同长短的码字，使用的时候需要相应的码表。算术编码较霍夫曼编码复杂，但不需要为一个符号单独设定码字，也不需要在通信过程中传送码表。当信源各信息符号的概率分布不能确定的时候，适合于用算术编码。H.264/AVC视频标准就将算术编码作为一种可选的嫡编码方法。游程编码也称行程编码，是用一个符号值替代具有相同值的连续符号，以减少符号的长度。在静止图像压缩标准中，游程编码经常被用来压缩数据;在视频编码标准中，游程编码与霍夫曼编码相结合用于对DCT系数量化后的稀疏矩阵进行编码。目前绝大部分视频编码器的设计都是以上述经典视频编码技术为基础。（二） 基于H.264标准的JM编码器介绍H.264（JM是其标准模型）是目前使用最为广泛的单视点视频编码标准，H.264采用了传统基于预测和变换的混合视频编码架构。与以往视频编码标准类似，H.264采用帧间预测技术来消除时域上视频帧间的相关性，采用帧内预测和变换编码技术来消除空间域上视频数据的相关性，采用嫡编码技术来消除统计域上量化系数的相关性。但H.264标准为了提高编码效率，采用了更为细致的宏块划分，更为精细的运动估计，更多的参考帧，并引入了去块效益滤波器等先进技术。其编码框架如图2.1。基本流程为：编码器以宏块为单位对输入图像（假设当前帧为P帧）进行编码，当前宏块先进行预测模式的选择，便利帧内、真间各种预测模式后，选择RdCost最低的模式作为当前模式，计算当前宏块和参考宏块的差值（残差块）并对其进行变换、量化、编码（如果为Direct模式，则不对残差快进行编码），然后形成编码码流进行存储或者传输。另外，量化后的残差块经过反量化、反变换（如果为帧间预测模式还要经过去块效应滤波）后，产生重建图像，以用于后续帧的预测以及PSNR的计算。 图2.1 H264编码框架（该图引自文献6）(1)帧间预测帧间预测是一种充分利用视频数据的时域相关性来去除时域冗余的编码方法，它是提高视频编码压缩效率的关键技术4。H.264中的帧间预测仍然是利用已编码帧和基于块运动补偿的预测模式，但与以往的视频标准相比，引入了更为精细的块划分模式，更高像素精度的运动矢量以及多参考帧帧间预测。如图2.2所示，每个亮度宏块有4种分块方式:16xl6，16x8，8x16和8x8，并且8x8块可以进一步划分成3种子块:8x4，4x8和4x4，因此总共有7种分块方式。在运动估计的时候，每个宏块可以有不同大小的子块，并且每个子块具有单独的运动矢量，因此可以更为精确的描述宏块内部的运动状态，从而降低整个宏块的预测残差。色度块的划分模式和亮度块相同，只是色度块的分辨率是亮度块的一半，因此色度块可以划分为:8x8，8x4，4x8，4x4，4x2，2x4和2x2等7种子块，它们相应的运动矢量也是亮度块的一半。不同的宏块划分适应于不同的图像内容，对于图像细节丰富的区域，一般有较为精细的的宏块划分，对于平坦区域，宏块划分一般为16x16等较大的块。H.264中亮度块运动矢量采用了1/4像素精度，色度块运动矢量的采用了1/8像素精度。而之前的视频编码标准(H.263和MPEG一4)亮度块运算矢量只采用半像素精度，色度块运动矢量只采用1/4像素精度。由于H.264采用了更高精度的运动矢量，因此可以提供更为精细的运动补偿，补偿之后得到的残差也更小。另外在1/2像素和1/4像素进行插值的过程中，H.264采用了6阶有限脉冲响应滤波器，可以有效改善运动补偿的性能。H.264除了采用以上精细块划分和更高精度运动矢量之外，还支持多参考帧预测。运动估计不再局限于前一帧或后一帧，可以在选择前向或后向多个不同参考帧中进行搜索，从而提高运动估计的准确性。图2.2 宏块划分方式（该图引自文献5）(2)帧内预测在之前的视频编码标准中，宏块进行帧内编码的时候，都是直接对其原始像素进行DCT变换，没有考虑空间上的相关性进行帧内预测，整体压缩效果不是太好。为了提高帧内编码效率，H.264引入了帧内预测编码。它利用了当前宏块周围已重建的像素值从空间方向预测对当前宏块的像素值，可以很好的降低像素值的相关性5。H.264中亮度块可以分16x16块和4x4块两类大小的块进行帧内预测。16xl6亮度块有4种预测模式:垂直预测，水平预测，DC预测和平面预测，它适合于对图像中平坦区域进行预测。4x4亮度块具有9种预测模式:垂直预测、水平预测、DC预测、下左对角线预测、下右对角线预测、右垂直预测、下水平水平、左垂直预测、上水平预测4。4x4亮度块预测模式更为精细，适合于对图像中纹理丰富区域进行预测。(3)熵编码H.264使用了三种熵编码方法:基于上下文的自适应变长编码 (CAVLC）、基于上下文的自适应二进制算术编码 (CABAC)、以及指数哥伦布(ExP一Golomb)编码。对slice层以上的数据编码采用指数哥伦布编码、对于残差数据编码采用CAVLC或CABAC。由于本文只是对运动估计算法进行研究改进，并没有深入研究熵编码有关内容，所以只是简单介绍，详细内容请参考文献4。三、JMVC代码阅读及编码参数提取本章在仔细阅读JMVC代码的基础上，对其进行修改，使编码器进行编码的同时将各种编码参数输入到参数文件中，并利用MFC界面显示编码参数。以往的参数分析软件，主要是利用基于节点的树进行参数的显示。比如单击某一节点，就可以显示某一帧的大小、PSNR、各种类型的宏块个数等参数信息。这种界面虽然易于实现，但是并不直观，很难一眼看出不同帧之间各个参数有那些不同因为这需要分别单击两个帧的节点，记录里面的各种数据并进行比较。本文通过ChartDirector库，把以帧为单位的参数放入图表之中，进行非常直观的显示，对于以宏块为单位的参数，也不是仅仅向传统软件哪样只是提取宏块类型的统计、运动矢量的均值，或者需要打开许多级节点之后才能找到某一宏块的运动矢量本文利用opencv库，将重建图像(YUV文件)中我们指定需要详细显示宏块参数的某一帧显示在MFC的Picture控件上，然后在该Picture控件上绘制各种宏块信息，比如运动矢量。宏块划分等。通过上文所述的方法，可以将出了SPS、PPS之外的所有信息非常直观的显示在界面上。（一） JMVC代码基本流程JMVC基本流程图如图3.1所示图3.1 JMVC流程图（该图来自网络）其中H264AVCEncoderTest.cpp中的init函数主要作用是读取配置文件encoderMVC.cfg的参数。然后开始对序列进行处理。PicEncoder.cpp中的init函数是初始化参数序列集和图像序列集以及编码所需缓冲区等。6然后遍历所有的图像帧，对每帧调用picEncode.cpp中的process处理函数，该process函数调用xEncodePicture函数对图像进行编码。在xEncodePicture函数中，将图像帧分为片组，对每个片进行编码。片再分为宏块，宏块为编码的最小单位，接下来就根据宏块的类型采取遍历各种编码方式，根据RdCost选择最优的模式作为最终模式。（二） 编码参数的提取（1）以帧为单位将编码序列的每一帧的类型、PSNR、编码时间、编码后大小等参数提取出来并进行显示。通过阅读调试代码可以知道，存储以上参数的变量分别为： 帧类型 rcSliceHeader.getSliceType () PSNR xGetPSNR( rcRecPicBufUnit, dPSNR ) 所需比特数 uiBits 编码时间 自定义time_t类型变量获取修改JMVC代码的PicEncoder.cpp文件，在编码每帧图像结束后添加写文件函数，使得每当编码完一帧，就将上述参数写入文件。一开始的写入文件格式非常简单，按照自己定义的写入顺序，各个数据以空格为分割符，第一个数据为第一帧帧类型，第二、三个数据分别为该帧的编码和解码顺序.第七个参数为编码时间、第八个参数为下一帧的帧类型。这种方法实现起来非常简单，读取编码参数文件时也非常方便，但是得到的编码参数文件非常不方便阅读，而且如果手动打开文件观察参数时误删了某条数据，读取时不但该数据丢失，之后的数据也会由于错位而造成读取错位，这种错误扩散会一直持续到文件结尾。为了使得写入编码参数的文件方便阅读，避免读取文件时的错误扩散，本文采用各帧参数用分隔符隔开、并且参数前都加入参数名称的方法标识参数类型，防止错误的发生且易于阅读。得到的文件内容如下页图3.2所示 图3.2 帧编码参数文件内容（部分）（2） 以宏块为单位将每一帧的各个宏块信息如宏块坐标、宏块类型 、宏块划分 、 参考宏块等信息进行提取并显示。通过阅读调试代码可以知道，存储以上参数的变量分别为：宏块位置：rcMbDataAccess.m_uiPosX rcMbDataAccess.m_uiPosY宏块类型：rcMbDataAccess.m_rcMbCurr.getMbMode()宏块划分：rcMbDataAccess.m_rcMbCurr.getBlkMode()参考宏块：rcMbDataAccess.m_rcMbCurr.getMbMotionData().m_ascRefIdx0运动矢量：rcMbDataAccess.m_rcMbCurr .getMbMotionData().getMv()修改JMVC代码，使得每当编码完一个宏块，就将上述参数写入文件。得到的文件内容如图3.3所示图3.3 宏块编码参数文件按内容（部分） （3） 编码参数的显示与分析利用MFC程序和ChartDirect库对获取的编码参数进行处理和显示。大致流程如下图3.4：将各个类型的宏块进行统计并显示在窗口CK2上根据界面上的按键判断需要显示的目 标视点（0 or 1 or 2?）根据按钮判断是否显示宏块预测类型 读取目标视点的 帧编码参数文件 将编码参数 存到变量中在窗口CK3上显示宏块预测类型分布 根据界面上的按键判断需要显示的帧编码参数类型（编码时间 or 比特率 or PSNR） 是否显示宏块划分？ 将需要显示的参数写入ChartDirector窗口CK1进行显示CK3上显示宏块划分 是否显示运动矢量？ 鼠标是否在CK1上？ CK3上显示运动矢量通过鼠标位置获取当前用户关注的帧序号 读取该帧的宏块级编码参数文件图3.4 MFC显示界面流程图以ballroom测试序列为例，将其的前三个视点进行编码并提取编码参数，然后通过界面进行显示，可以得到效果图如下： 图2.5-1 图2.5-2 图3.5-1 ：帧编码参数之码率效果图 图3.5-2 ： 帧编码参数之编码时间效果图 图3.5-3 ： 帧编码参数之PSNR效果图图2.5-3 由图3.5可以看到 ：视点0作为基本视点，码率最高，PSNR也最高，编码时间也最长。视点2由视点0预测得到，所以码率减少，PSNR略微降低，但是编码时间显著增长。视点1由视点0和视点2双向预测得到，码率最小，说明去除了更多的冗余，编码时间和PSNR和视点2没有太过明显的差别。从三个十点的整体趋势来看，每个序列的锚定帧所需编码时间明显小于非锚定帧，码率和PSNR明显高于非锚定帧。而通过后面分析可以发现锚定帧和非锚定帧的主要区别在于帧内编码宏块的有无，也就是说，如果仅仅进行帧内预测，编码时间会减少很多。从另一角度来说，这证明帧间预测的耗时非常巨大。 图3.6 宏块类型统计左上：视点0 第0帧 宏块类型统计右上：视点0 第10帧 宏块类型统计左下：视点1 第0帧 宏块类型统计右下：视点1 第10帧 宏块类型统计由图3.6可以看出：I帧（视点0 第0帧）宏块类型多为INTRA16，INTRA8和INTRA4 即帧内4x4 帧内8x8 帧内16x16，因为I帧仅采用帧内预测模式，所以不可能出现INTER16x16等模式P帧（视点1 第0帧）大多数为帧间模式如帧间16x16，帧间8x8，SKIP等，少数为帧内模式宏块B帧（视点0 第10帧以及视点1 第10帧）几乎全部为帧间预测宏块。在不是I帧的情况下，大多数宏块为SKIP模式。通过宏块统计分布图和编码时间图，可以更清晰地发现，帧内预测宏块较多时，编码时间就较短，帧间宏块较多时，编码时间飞速增长。图3.7-1 视点0 第0帧宏块预测类型分布 图3.7-2 视点0 第7帧宏块预测类型分布图3.7-3 视点1 第0帧 宏块预测类型分布 图3.7-4 视点1 第7帧宏块预测类型分布紫色：帧内预测宏块 绿色：视点间预测宏块 黄色：帧间预测宏块由图3.7可以看出各种预测类型的分布对于基本视点，没有视点间预测，它的锚定帧必然是I帧，只有帧内预测，所以全为紫色，如图3.7-1，它的非锚定帧绝大多数采用帧间预测（黄色），极少数采用帧内预测（紫色），如图3.7-2所示。对于非基本视点，它的锚定帧需要其它视点相同时刻的图像作为参考帧，所以不止由帧内预测（紫色），还有视点间预测（绿色），而且视点间预测占大多数。如图3.7-3所示，对于非锚定帧，三种预测方式均由可能，而实验证明，非基本视点的非锚定帧中视点内帧间预测宏块的数量最多，视点间的其次，帧内预测的宏块最少。 图3.8-1 视点0 第0帧 宏块划分 图3.8-2 视点0 第25帧 宏块划分 图3.8-3 视点2 第0帧 宏块划分 图3.8-1 视点2 第5帧 宏块划分由图3.8可以看出，I帧（视点0，第0帧图3.8-1、视点0，第25帧图2.8-2）帧内预测宏块较多，INTRA4x4 和INTRA8x8宏块较多，划分比较精细，而P帧（视点2，第0帧图2.8-3）和B帧（视点2，第5帧图2.8-4）大多采用帧间或者视点间预测，多数宏块划分为INTER16x16类型。图 3.9-1 视点0 第20帧 运动矢量分布 图3.9-2 视点0 第30帧 运动矢量分布图 3.9-3 视点1 第0帧 运动矢量分布 图 3.9-4 视点2 第0帧 运动矢量分布 由图3.9-1、3.9-2可以看出， 当仅采用视点内帧间预测时，非零的运动矢量所占比例较少且集中在运动物体附近，大面积的背景部分运动矢量为0（上图中不显示运动矢量有两种情况：运动矢量为0或者没有运动矢量，即采用帧内预测。 但是参考图3.7-2可知 视点0的B帧绝大多数采用帧间预测，只有极少宏块采用帧内预测，所以对于视点0来说不显示运动矢量可以大致等价于运动矢量为0）。而观察图3.9-3和3.9-4可以发现，当采用视点间预测时大多数宏块都有一个非零的运动矢量，并且在一定范围内具有各个宏块的运动矢量具有一致性。图下图所示图3.10 运动矢量的一致性示意图因此可以考虑把这些运动矢量统一趋向的值作为一个新的运动矢量预测值，在运动搜索过程中，在把左、上、右上方的宏块作为运动矢量预测值计算SAD之后，再把这个统一趋向的值作为运动矢量预测值计算SAD，然后选取SAD最小的点作为运动搜索的起始点。通过这种方法可以提高运动搜索的准确度并缩短运动搜索时间，具体效果见第四章。（4） 本章小节本章主要实现了对编码器参数的提取与显示，通过对编码参数的分析，可以发现许多可以改进的方面。例如：编码时间曲线显示I帧编码时间远远小于B帧和P帧的编码时间，而B、P帧与I帧的最主要不同就是进行了大量的运动估计，因此提高运动估计的效率是本文减少编码时间的关键；通过视差矢量的分布可以发现视差矢量的水平位移远大于垂直位移，所以搜索最优视差矢量时的水平位移范围要远大于垂直位移范围；通过运动矢量的分布以及宏块类型的分布可以发现，P帧和B帧的绝大多数宏块都是采用帧间预测模式，但是可以画出运动矢量的宏块较少，这说明采用帧间预测的宏块有一大部分的运动矢量为0，因此JMVC把零运动矢量作为预测矢量之一；观察相邻两个编码帧的运动矢量分布可以发现他们具有一定的相似性，因此可以考虑把前一帧的相同位置的运动矢量也作为预测矢量。总而言之，通过观察编码参数，可以得到JMVC编码器的许多方面性能和特点，这为以后对JMVC的改进提供了依据。四、各种运动算法的分析及比较由之前的分析可知，减少视频序列编码时间的关键在于减少P、B帧的编码时间，而减少P、B帧编码时间的关键则在于使用高效的运动估计算法。因此为了改进JMVC中的TZsearch算法，本章对各种基本的运动估计算法如三步法、四步法、菱形算法以及一些提高运动估计效率的常用方法如提前终止策略、增加预测矢量等进行了C+程序上的实现，以及性能的比较，为第5章改进JMVC的算法做准备。（一） 运动估计算法简介运动估计的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以恢复出当前块。由于编码时需要对残差块进行量化，所以通过运动搜索所找寻的匹配块与原始块相越小，量化噪声就越小，重建图像的质量也越高。1.全搜索算法全搜索算法FS(Full Search)是一种穷尽式的搜索算法，对给定搜索范围内所有的可能点都计算一次SAD值，从中找到最小值，该宏块即为匹配宏块9。全搜索算法的特点是一定能得到全局最优的运动矢量，但最耗时间巨大。以搜索范围为129x129为例，每一个宏块要找到其最佳匹配块，就要计算129x129=16641次原始宏块和参考宏块的SAD值，耗时极为漫长。2. 快速搜索算法因为全搜索耗时非常漫长，很多运动估计的快速算法从降低计算复杂度和降低搜索点数等方面进行了改进来减少编码时间。快速搜索算法大多数都基于这样一个假设：在搜索范围内有且只有一个最优点（谷点），以该点作为运动矢量所得的SAD最小，并且距离改点越远，SAD值越大5。在这种假设下SAD与运动矢量的关系如图4.1所示。图4.1 理想情况下的SAD与运动矢量的关系图在这种假设下，多种运动算法被提出，例如三步法、四步法、菱形搜索算法等。但是这些算法虽然加快了运动搜索的速度，其准确度也有了一定程度的下降。原因就在于实际情况下的SAD与运动矢量的关系并没有图4.1所示的那么理想。以ballroom测试序列第2视点第0帧为例（其参考帧为第0视点第一帧）。对所有宏块都做全搜索，并将每个宏块的搜索范围内的所有SAD值都输入到参数文件中，然后利用ChartDirector库进行显示。可以得到如下三维图表：图4.2-1 宏块（21，15）的SAD与运动矢量关系图图4.2-2 宏块（21，17）的SAD与运动矢量关系图图4.2-3 宏块（21，18）的SAD与运动矢量关系图图4.2-4 宏块（21，22）的SAD与运动矢量关系图图4.2-5 宏块（22，5）的SAD与运动矢量关系图由图4.2可以看出，SAD与运动矢量的关系并不是理想情况，每一个宏块的SAD分布都有很多“谷点”，快速搜索可以找到这些“谷点”中的其中一个，但是不能保证该“谷点”是所有谷点中的最低点。所以快速搜索算法的准确度比全局搜索算法有一定程度的下降。具体性能比较见本章第三节3. 三步法 在快速运动估计算法中，三步法的应用十分广泛。三步法在搜索过程中，每次对中心点及其相邻的八个点进行计算。起始搜索距离为最大搜索距离的一半。在每一步搜索中搜索距离减半，在最大搜索距离为8时，只需要三步就可得到运动矢量，因此称之为三步法6。对于现在分辨率较高的图像，搜索步数实际会远超过三步。如图4.3所示，当搜索距离为8时，以SAD为匹配准则。第一步，收搜索点的搜索距离为4，假设a点SAD值最小；第二步时，搜索距离则减半为2，周围8个测试点与中心a点比较，其中b点SAD值最小；第三步时，搜索距离再次减半为1，比较结果C点SAD值最小，则C点对应的运动矢量即为最佳运动矢量6。由于三步法旳运算时间明显减少，很多情况加均可以得到较为理想的运动矢量，因此应用十分广泛。其性能分析见本章第三节。图4.3 三步法步骤示意图（该图引自文献6）4. 四步法四步法反复使用5*5模板进行搜索 直到模板中心出误差最小或者到达搜索边界 ，然后再用3*3小模板进行一次精细搜索具体步骤如图4.4所示，其性能分析见本章第三节。图4.4 四步法 步骤示意图（该图引自文献5）5. 菱形搜索算法菱形搜索法采用的是非矩形搜索模板，在搜索过程中，所选用搜索模板的形状影响整个搜索算法的速度和性能13。在进行块匹配的过程中，利用误差匹配函数确定误差最小点，这个误差函数全局最小点就是最有运动矢量。在全搜索过程中，对所有点进行遍历测试，通过误差函数可以找到全局最小点。但是在快速搜索算法中，并不是对所有测试点进行遍历测试，如果搜索窗口选择的过小就会，在搜索过程中就容易陷入局部最小点；如果搜索窗口过大，在搜索过程中就容易错过全局最小点。因此，在菱形搜索算法中，采用了拥有9个测试点的大菱形模板和拥有5个测试点的小菱形模板，如图3.5所示。根据不同情况分别利用者两种模板进行快速运动估计。在搜索过程中，先采用大菱形模板进行搜索计算，当最小误差点出现在中心点时，再采用小菱形模板进行下一步匹配计算，这是5个测试点中误差最小点即为最佳匹配点。图4.5 大小菱形搜索模板（该图引自文献6）菱形搜索法具体搜索步骤如图4.6所示。首先，在给定的搜索范围内，采用大菱形搜索模板对中心点己经周围8个点进行测试计算，如果最小误差点出现在大菱形模板中心，则采用小菱形模板继续搜索。小菱形模板进行搜索时，以前面得到的最小误差点为中心，按小菱形模板对所有测试点进行计算，得到的误差最小点即为最佳匹配点。在采用大菱形模板搜索时，如果误差最小点不在大菱形模板的中心点是，则以该误差最小点为中心点，继续采用大菱形模板进行搜索，知道最小误差点出现在大菱形模板中心点位置时，改用小菱形模板，得到最佳匹配点。该点所在位置多对应的矢量即为最佳运动矢量。另外，为了提高菱形法的性能，可以采用更大的搜索模板,JMVC的TZsearch算法就采用了步长从一到六十四的73点菱形搜索模板。其性能分析见本章第三节。图4.6 菱形法 步骤示意图（该图引自文献6）（二） 运动算法比较平台的搭建本章主要对各种经典的运动估计算法（如三步法、四步法、菱形搜索算法、非对称十字型多层次六边形格点搜索算法）进行粗略实现并进行比较。由于如果将各种算法直接放入编码器中运行并进行比较的话要花费巨大的时间，所以本文设计了一个可以快速验证运动算法性能的小程序。程序流程图如下图 3.7 运动搜索算法性能分析程序流程图该程序仅实现了编码器的运动估计部分，并没有实现运动补偿、变换、量化、和熵编码。但是该程序输出的COST（计算宏块SAD的函数被调用的次数，即搜索的点数）和PSNR（原始图像和直接根据运动矢量和参考帧（而未经运动补偿）重建的图像的峰值信噪比）可以较好的反应运动估计算法的性能COST越少，说明运动搜索算法计算SAD的次数越少，复杂度越低，耗费的时间越少；PSNR越高，运动搜索的准确度越高。 而运动搜索算法的复杂度和准确度恰恰可以较好的反映编码器的性能，所以利用该软件比较编码器的性能可行的。（三） 各种运动估计算法实现和的性能分析1. 三步法、四步法、菱形算法的实现和比较本小节对以上三种算法进行了实现，考虑到TZsearch算法中菱形模板的点数不止是9点大模板和5点小模板，所以菱形算法中又分为9点、17点、25点、41点、57点、73点6种。分别以ballroom、exit、vassar测试序列的第0视点前100帧作为测试对象，利用第二节介绍的运动算法分析平台，可以得到以下数据 图4.8-1不同运动搜索方法的代价（ballroom） 图4.8-2不同运动搜索方法的代价（exit） 图4.8-3 不同运动搜索方法的代价（vassar）由以上数据可以看到，全搜索算法所需的计算SAD的次数最多，耗时也就最长，三步法、四步法、菱形算法相对与全搜索算法在复杂度上有很大的简化。左上：ballroom序列 左上：exit序列 左下： vassar序列图4.9 不同运动搜索方法的PSNR由图4.9可以看出，在大多数情况下（ballroom序列所有帧，exit序列所有帧，vassar序列后半部分）全搜索算法的PSNR都高于快速搜索算法，只有少数情况于快速搜索算法的PSNR几乎相同，通过YUV播放器播放vassar序列可以发现，PSNR几乎相同的地方画面差不多是静止的，几乎没有运动。所以可以说，画面只要有明显的运动发生，全搜索得出的PSNR要高于快速搜索得出的PSNR。左上：ballroom序列 左上：exit序列 左下： vassar序列图4.10 不同运动搜索方法的PSNR-COST关系图由图4.10可以看出对于ballromm序列和exit序列，三步法、四步法、9点菱形算法没有太明显的区别，但是随着菱形算法点数的增加，在计算复杂度（COST）的增加可以容忍的范围内，PSNR有了明显的提升。这也就解释了TZsearch采用的菱形算法模板的点数远多于9点很多的原因。而vassar序列的提升并不明显，这是因为vassar序列的运动很不明显，利用三步法等较简单算法已经可以得到很好的效果，PSNR没有更大的提升空间。因此可以考虑通过判断相邻宏块平均运动矢量的大小来确定采用的运动搜索方法，以实现对TZsearch算法的改进 。2. 向菱形算法中加入起始始搜索点的预测最简单的菱形算法的起始搜索点都是（0，0），但是由于运动矢量的空间和时间上的相关性可以对运动矢量进行预测，从而减少SAD计算次数并提高PSNR。在本文中，加入的预测矢量的方法如下：根据空间相关性 当前宏块左、上、右上宏块的MV作为预测矢量； 根据时间相关性 前一帧当前位置宏块的MV作为预测矢量；由于一般情况下静止部分较大 将0，0作为预测矢量；分别计算以上预测矢量的SAD值；然后将SAD最小的预测矢量作为搜索起点； 可以有效减少SAD计算次数并提高PSNR，具体效果见下图。左上：ballroom序列 左上：exit序列 左下： vassar序列图4.11 加入预测矢量后的菱形算法性能比较由图4.11可以看出，加入预测矢量后，COST-PSNR曲线明显向左上方移动，说明该方法可以明显的提高PSNR并降低SAD的计算次数。TZsearch中也对运动矢量进行了预测，但是只考虑了空间相关性并没由利用前一帧相同位置的宏块的运动矢量，也没有利用前一视点对应位置的宏块的运动矢量。因此可以加入以上两种预测矢量，以实现对TZsearch算法的改进。3. 在菱形搜索中采用提前终止策略场景中一般都是以某一对象为单位的运动,那么在该对象内部，不仅是运动矢量，残差应该也是有很高的相关性，因此可以利用相邻块的SAD值作为阈值，如果某点的SAD小于阈值 则提前终止。这种方法通过利用SAD值的相关性，以牺牲小部分PSNR为代价，减少了SAD的计算次数，具体牺牲了多少PSNR，缩短了多少SAD的计算次数，与阈值的选择有关。在本文中，实现方法如下：根据空间相关性 当前宏块左、上、右上宏块的SAD值作为预测值； 根据时间相关性 前一帧当前位置宏块的SAD值作为预测值；将所有的预测值求均值，设其为SADav ；选取系数a，令阈值为SADTH=a*SADav；如果某点的SAD值小于SADTH，则提前终止。本文令a分别取值为0.95，1.00，1.05，1.10，1.15，1.20，1.25，1.30，1.35分析以上系数下的运动估计算法性能，结果如下图3.12-1 ballroom序列采用不同系数的提前终止运动搜索性能比较图4.12-2 exit序列采用不同系数的提前终止运动搜索性能比较图4.12-3 vassar序列采用不同系数的提前终止运动搜索性能比较由图4.12可以看到随着a取值的增加，曲线向左下方移动，即PSNR略微下降的同时SAD的计算次数也下降。由于没有做主观测评实验，很难确定两者的平衡点，目前只是暂定a=1.15。并尝试把提前终止测略加入TZsearch算法中。4