1、本科毕业设计（20届）基于MIPS的H264编码器设计及优化研究所在学院专业班级计算机科学与技术学生姓名学号指导教师职称完成日期年月1摘要【摘要】H264编码标准是2003年5月制定的新一代视频编码标准。H264编码标准与以往标准相比有许多新技术，例如1/4，1/8精度的子像素运动估计，多参考帧技术，去块滤波，加强的熵编码，小块的整数变换。但由于其编码性能是以在增加编码复杂度为代价的，很难达到实时编码、传输的要求，很大的限制了H264编码标准在移动设备上的视频应用。本文对H264原理进行分析，并以H264官方测试模型JM86为参考，对运动估计搜索算法进行详细阐述，实现H264编码器运动搜索算法
2、及其优化。【关键词】H264；编码器；优化。2ABSTRACT【ABSTRACT】H264ISTHENEWESTVIDEOCOMPRESSIONSTANDARDJOINTLYPUBLISHEDIN2003H264CODINGSTANDARD,COMPAREDWITHPREVIOUSSTANDARDSTHEREAREMANYNEWTECHNOLOGIES,SUCHAS1/4,1/8SUBPIXELMOTIONESTIMATION,MULTIPLEREFERENCEFRAMETECHNIQUE,DEBLOCKINGFILTER,ENHANCEDENTROPYCODING,INTEGERTRANSF
3、ORMSMALLPIECESBUTBECAUSEOFITSCODINGPERFORMANCEISINCREASINGTHECOSTOFCODINGCOMPLEXITY,ITISDIFFICULTTOACHIEVEREALTIMEENCODING,TRANSMISSIONREQUIREMENTS,AGREATLIMITONAMOBILEDEVICEAPPLICATIONSTHISPAPERANALYZESTHEPRINCIPLEOFH264,ANDH264TESTMODELJM86OFFICIALREFERENCE,THEMOTIONESTIMATIONSEARCHALGORITHMINDETA
4、IL,IMPLEMENTATIONANDOPTIMIZATIONALGORITHMOFH264ENCODER【KEYWORDS】H264ENCODEROPTIMIZATION3目录摘要1ABSTRACT21绪论511选题背景512选题目标及意义513开发思路614论文结构说明62数字视频理论基础721视频源格式722数据库需求分析7221主观视频质量评定7222客观视频质量测量83H264编码原理931H264概述932编码器933帧内预测1033144亮度预测103321616亮度预测1133388色度预测1134帧间预测11341树状运动补偿11342运动矢量12343MV预测1335整数
5、变换与量化1435144DCT整数变换15352量化16353HADAMARD变换17354完整的变换、量化过程1936熵编码19361哥伦布指数编码20362基于上下文自适应可变长编码CAVLC2137小结234H264编码器分析实现2441编码器结构2442运动估计代码分析2543经典运动搜索算法分析及实现27431全搜索法FS27432三步法TSS284433四步法FSS29434菱形法DS30435梯度下降法BBGDS31436六边形法HEXBS3244小结325H264编码器优化研究3351算法复杂度分析3352算法优化3353MIPS平台移植3554MIPS平台优化3655小结37
6、致谢错误未定义书签。51绪论11选题背景随着互联网的普及，数字视频技术在网络通讯和广播领域得到了广泛的应用，视频和多媒体信息在INTERNET网络和移动网络中处理和传输成为信息化过程中的热点技术。视频信息有直观性、确切性、高效性、广泛性等特点1，但其信息量过大不易于存储和传输。要使网络视频得到广泛应用，必须解决视频编码压缩问题。从1984年CCITT公布第一个视频压缩编码以来，至今已有20多年。ITU/ISO等国际标准化组织陆续颁布了近十个编码标准，极大推动了视频通讯的发展。2003年3月ITUT/ISO正式公布了H264编码标准，由于其相比以往标准出色的编码性能，被称为新一代视频编码标准。H
7、264编码标准与其上一个标准H263已被广泛应用于视频会议相比，码率降低一半左右；或者说相同码率下图像质量明显提高。2但H264编码标准优良的编码性能是以增加编码算法复杂度为代价的。在一些低频处理器上编码速度较慢，很难达到实时编码、传输的要求，很大的影响了H264编码标准在移动设备上的应用。在处理器处理能力有限的基础上，如何降低其运算复杂度,快速实现其算法已成为其标准进入实用阶段的关键问题。12选题目标及意义信息资源中，视频信息的开发、利用更具有重要的理论意义和应用价值。近年来，INTERNET的迅猛发展，使IP技术应用普及到各个方面，网上教育、远程医疗、电子商务、电子政务、电子游戏、网上证券
8、等等。通信业务从电话、传真、电报发展为可视电话、会议电视、视频点播等，即由音频为主发展到以视频为主的多媒体通信。网络中视频应用以越来越多的融入到日常生活中。4H264编码性能优于现有其他视频编码标准,和MPEG2和MPEG4ASP等压缩技术相比，在同等图像质量下，采用H264技术压缩后的数据量只有MPEG2的1/8，MPEG4的1/3,H264压缩技术的采用将大大节省用户的下载时间和数据流量收费。由于其基本信源编码框架与原来类似,性能的提高来源于各个特定的编码工具。但H264的编码运算复杂度6制约了其进入实用阶段。2,3本编码器的主要目标是对H264编码的参考模型进行MIPS平台的移植和针对平
9、台对其算法进行编码速度优化。13开发思路H264编码器以VISUALSTUDIO2005做为开发平台，用C/C语言进行编写，以JM86为参考模型进行算法实现及编码优化。编码器对YUV420视频序列进行编码。14论文结构说明本文第一章简要介绍了项目背景、目标和开发思路。第二章、第三章为视频编码基本知识和H264编码标准的基本原理。第四章为H264官方测试模型的分析及实现。第五章阐述对H264编码器优化实现。72数字视频理论基础21视频源格式常见的彩色图像记录的格式有RGB、YUV、CMYK等格式。彩色电视格式最早的构想是使用RGB三原色来同时传输。这种设计方式是原来黑白带宽的3倍，并不是很好的设
10、计。RGB着重于人眼对色彩的感应，YUV则着重于视觉对于亮度的敏感程度，Y代表的是亮度，UV代表的是色度（因此黑白电影可省略UV，相近于RGB），分别用CR和CB来表示，因此YUV的记录通常以YUV的格式呈现。YUV有4种常见的格式444,422,420,411444表示每4个亮度像素相应的有4个CB和4个CR色度像素。422表示每4个亮度像素相应的有2个CB和2个CR色度像素。411表示每4个亮度像素相应的有1个CB和1个CR色度像素。420表示每行4个亮度像素对应2个色度像素，隔行CRCB。即此行YUV为420下一行YUV为402。YUV和RGB的转换公式矩阵表示为BGRVUY100010
11、5149806150436028886014713011405870299021VUYBGR003211215806003946501139831012222数据库需求分析对压缩后图像质量的评价大体上分为主观视频质量评定和客观视频质量测量。221主观视频质量评定主观视频质量的评定由若干名专家和“非专家”作为评分委员，共同利用五项或七项评8分法对视频图像进行评定，最后按加权平均对压缩后图像质量进行主观评定。222客观视频质量测量主观的视频质量评分接近人的真实视觉感受，但需耗费人力和时间。客观质量的测定方法速度快、易实行，但往往不会太符合人眼的视觉感受，只能说大体上的质量。客观质量测定方法应致力于
12、改进其测试标准和测试方法，使其符合人的视觉感受。最常用的测试标准是峰值信号与噪声之比（PSNR）MSENPSNRDB/12LOG1021023MSE为原始图像和编解码后图像的均方差，212N为图像最大可能的信号值平方，N表示每个像素的比特数。PSNR越高视频质量越好。93H264编码原理31H264概述MPEG（MOVINGPICTUREEXPERTSGROUP）和VCEG（VIDEOCODINGEXPERTSGROUP）已经联合开发了一个比早期研发的MPEG和H263性能更好的视频压缩编码标准，这就是被命名为AVC（ADVANCEDVIDEOCODING）的，也被称为ITUTH264建议和M
13、PEG4的第10部分的标准，简称为H264/AVC或H264。这个国际标准已于20033正式被ITUT所通过并在国际上正式颁布。332编码器H264并不明确地规定一个编解码器如何实现，而是规定了一个编码的视频比特流的语法。H264编码器的功能组成见图31。图31编码器3编码器由两条路径组成一条正向路径，一条反向重构路径。正向路径蓝色FN为当前要编码宏块，有2种预测方式帧间和帧内预测，预测后得到一个残差块DN,DN经过44DCT整数变换和量化后得到，一个编码系数矩阵X，再对系数矩10阵X进行熵编码后与之前编码的参数包括量化参数，预测方式等参数写入NAL片。反向重构路径红色重构路径从编码系数矩阵X
14、开始，经过反量化、反变换得到残差块DN，根据宏块的预测方式预测参考宏块FN1或当前帧已编码宏块UFN得预测矩阵，加上残差块DNDN和DN不完全相同，量化过程会造成精度丢失得到UFN，再经过过滤器去块滤波重构参考宏块FN。33帧内预测在帧内预测模式中，预测块P是基于已编码重建块和当前块形成的。亮度块分为1616块和44子块，44子块有9种可选预测模式，用于大量细节的图像编码；1616亮度块有4种预测模式，预测整个1616亮度块，用于图像平滑区域；色度块有4种预测模式，与1616亮度块预测模式类似。33144亮度预测如图31,32所示，亮度44子块帧内预测由上部、左部的13个像素点AQ预测得。1个
15、模式中并非AQ中每个像素都用到图32用AQ对AP进行帧内预测预测的八个方向3图32帧内44预测9种模式311例如，模式4中，DROUNDB/4C/2D/4。模式2DC为所有预测值为AD及IL平均值。3321616亮度预测1616的亮度宏块的预测有4种，用于图像平滑区域，如图33所示。图33帧内亮度1616预测4种模式333388色度预测88色度预测由帧内已编码的上部和左部的像素预测而得。两种色度用同一种预测模式，类似于帧内1616色度预测的4种模式，只是编号不同。34帧间预测H264帧间预测是基于已编码的块运动补偿的预测模式。有亚像素运动矢量、多参考帧等新技术特征。341树状运动补偿每个161
16、6宏块有4种划分方式,每个88的子块还可以有4种方式划分，如图34所示。图34帧间预测分割方式3每个划分或者子划分都有独立的运动补偿。每个MV都被编码传输。色度与亮度的划分模式相同，尺寸减半高度宽度均为一半。12342运动矢量帧间编码宏块的每个划分都是从参考帧预测而得。他们的运动矢量MV对亮度采用1/4像素精度，色度采用1/8像素精度。亚像素在参考帧中并不存在而是由邻近点内插得。图351/2像素点计算方式3例如图35所示半像素点B由对应整像素点6抽头滤波得，权重1/32,5/32,5/8,5/8,5/32,1/32,公式如下BROUNDE5F20G20H5IJ/32剩余的半像素点由垂直或水平方
17、向的半像素点滤波得，J由CC,DD,H,M,EE,FF滤波得。半像素点得出后，1/4像素点可由半像素点线性内插而得。如图36所示。A由邻近半像素点内插得，公式如下AROUNDGB/2剩余1/4像素由对角半像素点内插得，如13EROUNDBH/2图361/4像素计算方式3色度像素的1/8精度的像素点，由整像素线性内插得，如图37所示。图37色度1/8像素计算方式3343MV预测每个划分的MV传输需要相当数目的比特。MV可以由邻近已编码的MV预测得。E为当前宏块或宏块分割子宏块。A、B、C分别为E的左、上、右上方的三个相对应块。如果E的左边不止一个分割，取其中最上的一个为A；上方不止一个分割时，取
18、最左边一个为B。如14图38显示所有分割有相同尺寸时的邻近分割选择。图39给出了不同尺寸时临近分割的选择。图38所有分割有相同尺寸时3图39不同尺寸时临近分割的选择31传输分割不包括168和816或跳跃宏块（SKIPPEDMB）时，MVP为A、B、C分割MV的中值；2168分割，上面部分MVP由B预测，下面部分MVP由A预测；3816分割，左面部分MVP由A预测，右面部分MVP由C预测；35整数变换与量化变换编码是将图像时域信号变换成频域信号。H264编码对预测残差采用的是44整数离散余弦变换，量化根据图像的动态范围大小确定量化参数。H264的整数DCT变换中只有整数运算，消除了浮点运算，减少
19、了运算量，并且精确的整数排除了编码器和解码器反变换之间的误匹配问题。H264的基本档次要根据编码图像的残差块数据进行3种变换1帧内预测44的亮度直流系数1616预测模式222的色度直流系数3其他44的残差块。如图310，所示。1、2的残差块还要组合成一个1616的整体块进行一次HADAMARD变换，进一步压缩编码。15图310编码变换和量化过程35144DCT整数变换输入数组X的44DCT变换公式为CABABACABACACABAXCBBCAAAABCCAXAYTBAAAA其中21A8COS21B83COS21C这个矩阵乘法可以被转化为以下等式2222222211111111111111111
20、1111111BABBABABAABABABBABABAABADDDDXDDDDECXCYT符号表示每一个CXCT中的元素被E标量相乘而不是矢量乘。AB如前，D等于C/B近似为0414。为了简化变换，D近似为05。为了保持正交，B要被修正为52。为了避免计算CXCT中精度的丢失，最终变换式为4/2/4/2/2/2/4/2/4/2/2/2/1121211121111121122111112112111122222222BABBABABAABABABBABABAABAXEXCCYFTFF16这个变换是一个近似的44DCT变换。因为改变了元素D和B，输出的矩阵和DCT变换不会完全相同。相应的其反变换
21、式为2/1112/1111112/12/1111112/1111112/11112/111/211122222222BABBABABAABABABBABABAABAYCEYCYFFTF正反变换时正交的，即T1TXX。H264把DCT中后面EF放到后面的量化过程中，实际的DCT输出是WCXCT352量化H264使用标量量化。这样定义和实施是为了避免进行除法或浮点计算。基本的量化公式如下STEPIJIJQYROUNDZ/IJY是变换后得系数，STEPQ是量化步长。H264标准一共支持52个值的量化步长STEPQ，以一个量化参数QP为索引。每个QP对应的STEPQ值在表31中。注意QP每6个增量QS
22、TEP扩大两倍；QP每增量1STEPQ增量125。量化步长的宽范围使编码器能准确灵活的控制码率和图像质量之间的平衡。色度和亮度的QP值可能会不同。QP0123456789101112QSTEP0625068750812508751112512513751625175222525QP18243036424851QST5102040801602217EP4表31QP值对应表H264把变换和量化的过程放在一起，变换中的标量矩阵乘在量化过程中，公式如下PF/QROUNDWZSTEPIJIJPF根据I,J在变换中标量矩阵的位置是2A,2/AB或4/2B。元素STEPPF/Q以乘以一个MF（乘数）和一个右
23、移来避免除法操作MF/2ROUNDWZQBITSIJIJ这里STEPQBITSPF/QMF/2，6/15QPFLOORQBITS整数量化的公式为QBITSFMFWZIJIJIJIJWSIGNZSIGN其中F在帧内块是3/2QBITS,在帧间块是6/2QBITS作用是偏移量改善视觉效果。MF实现时可查表得。这样量化的过程可以避免除法操作，并且确保用16位算法来处理数据，在PSNR没有降低的情况下实现。353HADAMARD变换如果当前处理的图像宏块是色度块或帧内1616预测模式的亮度块，则需要将其中各图像块的DCT变换系数矩阵W中的直流分量或直流系数W00按对应图像块顺序排序，组成新的矩阵WD，
24、再对WD进行HADAMARD变换及量化。在这种情况下，不需要对变换后系数矩阵单独量化。图311所示，为1616宏块的传输顺序，每个44块的左上角为直流系数，首先被传输。18图311宏块编码顺序3对亮度块DW的HADAMARD变换为2/11111111111111111111111111111111DDWY对YD量化输出1QBITS2FMFYZ00,JI,DJI,D00,MF是位置0,0的MF系数值。对色度块DW的HADAMARD变换为11111111DDWY对DY量化输出1QBITS2FMFYZ00,JI,DJI,DWSIGNSIGNZJDI,JDI,19354完整的变换、量化过程编码器完整的
25、变换、量化编码过程1输入44残差块X244DCT变换TFFXCCW3量化QBITSSTEPQPFWZ2/36熵编码熵编码是无损压缩，解码后不会有数据的丢失，熵编码是建立在随机过程的统计特征基础上的。片层上要编码的元素如下表所示要编码的元素描述SEQUENCE,PICTUREANDSLICELAYERSYNTAXELEMENTSMACROBLOCKTYPEMB_TYPEPREDICTIONMETHODFOREACHCODEDMACROBLOCKCODEDBLOCKPATTERNINDICATESWHICHBLOCKSWITHINAMACROBLOCKCONTAINCODEDCOEFFICIENT
26、SQUANTIZERPARAMETERTRANSMITTEDASADELTAVALUEFROMTHEPREVIOUSVALUEOFQPREFERENCEFRAMEINDEXIDENTIFYREFERENCEFRAMESFORINTERPREDICTIONMOTIONVECTORTRANSMITTEDASADIFFERENCEMVDFROMPREDICTEDMOTIONVECTORRESIDUALDATACOEFFICIENTDATAFOREACH44OR22BLOCK表32熵编码元素描述片层上，语法元素被编码成定长或可变长的二进制编码，语法元素根据熵编码模式用可20变长编码CAVLC或自适应上
27、下文算术编码CABAC。在H264基本档次中，残差块使用自适应上下文可变长编码CAVLC，其他的可变长编码单元使用哥伦布编码。361哥伦布指数编码哥伦布指数编码是有重构规则的可变长编码。表33列举了前9种码字；从表中可以看出，每一个码字被如下构造INFOZEROSM1INFO是一个携带了M位信息的区域。CODEN_UM0不带前缀0,CODE_NUM1、2有1位INFO区域；CODE_NUM36有2位INFO区域。编码长度为2M1位。CODE_NUMCODEWORD01101020113001004001015001106001117000100080001001表33哥伦布指数编码码字对应表参
28、数V要被编码映射到CODE_NUM用如下3种方式中的一种UEV不标记直接映射，CODE_NUMV。用在编码宏块类型、参考帧索引等。SEV标记映射，用在运动矢量差，量化参数等，V映射如下表34VCODE_NUM00111223243521表34SEV码字对应表MEV映射符号，参数V根据标准中指定的表被映射到CODE_NUM。如下表所示CODED_BLOCK_PATTERNINTERPREDICTIONCODE_NUM0NONONZEROBLOCKS016CHROMADCBLOCKNONZERO11TOPLEFT88LUMABLOCKNONZERO22TOPRIGHT88LUMABLOCKNONZ
29、ERO34LOWERLEFT88LUMABLOCKNONZERO48LOWERRIGHT88LUMABLOCKNONZERO532CHROMEDCANDACBLOCKSNONZERO63TOPLEFTANDTOPRIGHT88LUMABLOCAKSNONZERO7表35MEV码字对应表每个映射（UE，SE和ME）都是设计以较短的码字给高频率的值，较长的码字给低频率的值。362基于上下文自适应可变长编码CAVLC在H264的CAVLC基于上下文自适应的可变长编码中，通过根据已编码句法元素的情况动态调整编码中使用的码表，取得了极高的压缩比。CLVAC被设计利用如下几个44块量化的特点1在预测，变换
30、和量化后，块通常是稀疏矩阵主要包含零。CAVLC用运行等级编码简洁的表示0的字符串。2在ZIGZAG扫描后最高的非零系数常有/1序列。CAVLC用一种简洁的方式表示高频率的/1系数“拖尾”或“TLS”的数字。3邻近块非零系数的数字是相关的。编码系数的数字是用查表；查表的选择根据邻近块中非零系数的数字。4在重新排列数组的开始直流系数附近和频率更低向更高中非零系数的等级幅度变高。CAVLC利用他根据最近编码LEVEL大小适应VLC对LEVEL参数查表的选择。在CAVLC中上下文模型的选择主要体现在两个方面,非零系数编码所需表格的选择以及22拖尾系数后缀长度的更新。CAVLC非零系数的数模是从0到1
31、6，拖尾系数的数目范围是0到3。如果/1的个数大于3只有最后3个作为拖尾系数，其余作为非零系数。对非零系数数目和拖尾系数数目的编码是通过查表得到的，共有4个变长表和一个定长表可选择。表格的选择是根据变量NC的值来选择的，除了色度直流系数外，其他的系数类型的NC值是根据当前块左边44的非零系数数目NA和当前块上面的44块的非零系数数目NB求得的。当输入的系数是色度的直流系数时，NC1。当NA，NB都可用NCNANB/2,都不可用时NC0，当只有1个可用时NC等于可用的值。当08时使用定长表格。对于拖尾系数只须1比特表示其符号0为，1为。编码的顺序是按照反向扫描的顺序，从高频数据开始。用以编码每个
32、等级的VLC表的选择适应根据每个编码（上下文）的大小来确定。7个VLC表可供选择LEVEL_VLC0到LEVEL_VLC6。LEVEL_VLC0偏向于低程度；LEVEL_VLC1偏向于稍高程度等等。表的选择有如下规则A初始化LEVEL_VLC0表除非超出10个非零系数并少于3个拖尾系数在此情况下在LEVEL_VLC1中查表。B编码高频率非零系数。C如果系数的大小比预定义的阈值大，移到下一VLC表。这样，级别的选择匹配到最近编码系数的大小。阈值列在表36中；第一个阈值是0意味着表总是递增的在第一个系数级被编码后。CURRENTVLCTABLETHRESHOLDTOINCREMENTTABLEVL
33、C00VLC13VLC26VLC312VLC424VLC548VLC6N/AHIGHESTTABLE23表36VLC阈值表TOTALZEROS是所有重新排序过数组中最高非零系数过程中所有零的总数。用VLC编码。发送一个单独的VLC去显示TOTALZERO是因为很多块包含了很多非零系数在数组的开始，这种方法意味着在数组头部的零不需要编码。37小结本章介绍了H264的帧内、帧间预测，变换量化，熵编码等的原理和技术细节。244H264编码器分析实现JM模型是JVT发布的源代码公开的H264编解码软件，用C语言编写而成。JM86是JM的一个版本，尽管JM86下文简称JM没有引进最新的一些运动搜索以及快
34、速模式选择算法，但研究它的工作方式和程序结构对H264算法研究和在JM基础上的代码剪裁仍然很有意义。41编码器结构图41编码器编码预测模式如图41所示，H264编码标准并非是以帧为编码单元的，而是以宏块为编码单元，其核心函数ENCODE_ONE_MACROBLOCK完成了包括包括运动搜索，参考帧选择，帧间模式选择，帧内模式选择，帧内帧间判定，残差数据的计算，变换和量化，反变换和反量化，重建图像的计算。重点分析运动搜索部分，并实现6种经典运动搜索算法。开始P1616P168P816P88INTRA1616INTRA44选择最佳P模式亚像素运动估计选择最佳编码模式结束2542运动估计代码分析运动估
35、计相关数据结构和变量声明INTALL_MV对应一个6维数组ALL_MVBLOCK_XBLOCK_YLISTREFBLOCKTYPEDIRECTIONBLOCK_X,BLOCK_Y表示44块在整个宏块1616宏块内的水平和垂直位置，所有保存的运动矢量都是44块的，84的块的运动矢量会被保存为相同的两个44的运动矢量。LIST表示参考帧列表。REF表示参考帧序号。BLOCKTYPE表示宏块的类型分为1616,168,816,88,84,48,44。DIRECTION表示运动矢量水平和垂直方向分量，分别为0和1。ALL_MV的初始化JM86中调用了GET_MEM_MV函数对运动估计数组初始化，代码如
36、下INTGET_MEM_MVINTMVINTI,J,K,L,MIFMVINTCALLOC4,SIZEOFINTNULLNO_MEM_EXIT“GET_MEM_MVMV“FORI0IMAX_NUM_REFERENCES,SIZEOFINTNULLNO_MEM_EXIT“GET_MEM_MVMV“FORL0LMAX_NUM_REFERENCESLIFMVIJKLINTCALLOC9,SIZEOFINTNULLNO_MEM_EXIT“GET_MEM_MVMV“FORM0MMAX_NUM_REFERENCES92SIZEOFINT整像素点运动相关函数为FULLPELBLOCKMOTIONSEARCH。
37、亚像素点运动估计相关函数为SUBPELBLOCKMOTIONSEARCH，先通过已找到的整象素点为搜索中心，进行半象素点运动估计；然后再通过找到的半象素匹配点，再进行1/4象素点的运动估计。/HALFPELREFINEMENT/CONVERTSEARCHCENTERTOQUARTERPELUNITSMV_X1/ADDUPSATDFORY00,ABORT_SEARCH0Y0BLOCKSIZE_YY04。IFMCOSTMIN_MCOSTMIN_MCOSTMCOSTBEST_POSPOS1/4像素点搜索与半像素点搜索过程类似。43经典运动搜索算法分析及实现本节分析并实现6种经典运动搜索算法。实现代码
38、详见附录。431全搜索法FS全搜索法在一个预定义的搜索块中与所有的块进行比较，得到一个最小的误差的SAD的匹配块。块之间的位移即为所估计的MV。由于要与所有的块进行比较，全搜索法带来极大的计算量，使H264编码很难实时处理，所以必须使用运动估计快速算法。28432三步法TSS图42三步搜索法TSS如图42所示，在1616搜索区域内以半径8的一半4为步长进行第一步搜索，搜索起点周围8个点，找到MAD值最小的点，以找到的点为第二步的起点，步长减少为前一步的一半，以此类推。到第三步，再把步长减少一半到1，计算其周围8点的MAD值，MAD值最小的点与第一步起点的位移为运动矢量。三步法的搜索速度较快，但
39、不一定全局最优。1129433四步法FSS图43四步法FSS四步法与三步法类似，算法过程如图42所示，分为四步1从搜索区域中心开始，搜索搜索区域中心步长为2的8个邻近的点，如果匹配误差最小的点为中心点，跳至步骤4；否则跳至步骤2。2如果1中最佳匹配的点在四边形顶处，则引入另外5个点；如果1中最佳匹配点在四边形的边的中点处，引入另外3个点；新引入的点在计算后得到最佳匹配点在中心位置则跳至步骤4；否则跳至步骤3。3重复执行步骤2。4搜索半径减小为1，搜索附近9个点，误差最小的点为最佳匹配的点。30434菱形法DS图44菱形法DS菱形算法认为大部分运动矢量是分布在中心位置2个像素为半径的圆范围内的，
40、菱形搜索法使用了2种搜索的菱形大、小菱形。如图44所示大菱形为搜索中心8个半径为2的点，小菱形为离搜索中心半径为1的4个点。所搜步骤如下1以搜索块中心为起点，按大菱形的搜索方式搜索包括搜索中心的9个点，如果中心点为最佳匹配点，跳至步骤3；否则跳至步骤22以1的最佳匹配点为中心，按大菱形的搜索方式检测周围没有被搜索过的点，如果最佳匹配点位于中心跳至步骤3否则重复步骤23以最佳匹配点为中心，按小菱形的搜索方式搜索周围4个点，误差最小的点为最佳匹配你点。31435梯度下降法BBGDS图45梯度下降法BBGDS梯度下降算法，很适合搜索小运动量图像和静止图像。过程步骤为1）以搜索区域中心为起点，搜索周围
41、半径为1的9个点，如果最佳匹配点不在中先跳至步骤2；如果在中心跳至步骤32）以1中的最佳匹配点为中心加入其周围未检测过的点，找到最佳匹配点，重复步骤2直到最佳匹配点为搜索中心或搜索到图像边缘跳至步骤33）得到的最佳匹配点为块所求的点，与起点间的位移为运动矢量。该算法容易造成局部最优，不适合大运动量图像。32436六边形法HEXBS图46六边形法HEXBS六边形搜索法与菱形搜索法类似，只是前2步搜索的大菱形所搜的方式换成了大六边形，其过程与菱形搜索法相同。44小结本章分析了H264编码器的结构，并重点分析和实现了6种经典运动搜索算法。335H264编码器优化研究H264编码能够很好地适应IP和无
42、线网络的应用,因此基于H264压缩算法的无线视频传输系统将具有广阔的应用前景,但是H264压缩算法的编码复杂度太高,很难实现实时编解码,目前很多学者和研究人员提出多种快速算法实现编码中时间复杂度较高的部分,如快速运动估计,快速整数变换等,在很大程度上提高了编码速度,这是从算法级改进的角度来提高编码速度。851算法复杂度分析对软件进行时间复杂度分析，JM编码器在运动估计、RDO模式选择、熵编码等耗时较多，测试结果为运动估计占70左右，模式选择占20左右，熵编码占5左右，其他3左右，运动估计所需的编码时间最长。运动估计中包括整像素运动估计，1/2像素运动估计和1/4运动估计，其中1/2像素值和1/
43、4像素值内插属于段数据重复运算，非常耗时。在RDO模式选择中需要反复多次进行SATDSAD计算、整数变换和量化等操作，这些计算也占了很大比例的编码时间。91052算法优化在JM86中FASTSUBPELBLOCKMOTIONSEARCH函数中使用快速搜索算法。原搜索算法为全搜索，其过程为搜索最佳整像素点周围的8个1/2像素点和最佳1/2像素周围的8个1/4像素位置点，共搜索16个点。JM使用快速搜索法简化搜索过程，过程为搜索最佳匹配点周围的4个1/4像素位置点，如果最佳匹配点为中心则停止搜索，否则继续搜索该最佳匹配点的周围的4个1/4像素点，并限制搜索的次数为ICURRSEARCHRANGE2
44、SEARCH_RANGE_DYNAMIC17次，除第一次4个点外，每次3个点，最坏情况下搜索了43622次比全搜索算法还多。对此考虑使用一种更合理的搜索点选择方式，为了减少搜索点不使搜索范围太宽，采用六边形搜索法，过程为在只搜索最佳初始预测像素点周围的6个1/4像素点（如图51所示），如果中心为最佳搜索匹配点停止搜索，否则选择最小代价点为中心再搜索一次，最优情况下搜索6次，最差情况下搜索12次，在保证图像质量的情况下，减少了搜索的次数。34图51左为优化前搜索点位置右为优化后搜索点位置测试方法对两种算法使用同一视频序列，同一参数编码，比较编码时运动搜索所耗时间。测试结果图52优化前35图53优
45、化后对比优化前后运动估计时间从1488秒减少到1327秒，运动搜索时耗减少10左右。亮度信噪比从3390降低到3372降低不到1,码率增加5左右。53MIPS平台移植在做JM86在MIPS平台上的优化前先必须做MIPS平台上WINCE的移植（项目工程见附录）。PC上用的环境WIN32与嵌入式_WIN32_WCE有一定的差别，在JM工程中具体表现在一些函数和头文件的宏定义中，如SYS/TIMEBH,CONIOH等。当WINCE中一些函数不能使用时刻适当的删减函数，或用相同功能的函数替换。方法步骤1新建工程JM86_WCE（创建空工程并把SRC和INC目录下文件加入工程）,设置平台为STANDAR
46、DSDK_500MIPSII。2工程属性C/C常规属性包含附加目录为LENCODINC。3加入预编译头文件STDAFXH,STDAFXCPP。4把代码中原宏定义WIN32开关替换成_WIN32_WCE。365根据编译器提示错误修改语法，宏定义等错误。（与编码内核无关的输出错误，如计算编码时间等，删减代码，与编码器内核有关用WINCE下可用函数替代）54MIPS平台优化本节主要阐述对MIPS平台的优化，使用VS2005性能分析找出单个执行耗时较多的函数，如图54所示。图54性能分析报告其中_DCT_LUMA为亮度块DCT变换，_SATD为参差块绝对值求和（根据需求可能先求一次HARDMARD变换
47、）。主要对这些多次被调用耗时较多的函数进行汇编级优化。INTSATDINTDIFF,INTUSE_HADAMARD函数中的C语言代码FORK0K16KSATDBYTE_ABSDIFFK生成MIPSII汇编代码LUIT0,BYTE_ABSLWT6,BYTE_ABST0T6BYTE_ABSADDIUT5,ZERO,0X10T501616LL3SATD37LWT0,0S7T0DIFFKSLLT1,T0,2T1T02（BYTE_ABSINT数组4字节）ADDUT2,T1,T6T2T1T6LWT3,0T2T3INT0T20为DIFF数组首地址ADDIUT4,S7,4T4S74ADDUS6,T3,S6S6
48、T3S6ADDIUT5,T5,0XFFFFT5BNET5,ZERO,LL3SATDORS7,T4,ZERO优化汇编代码LUIT0,BYTE_ABSLWT6,BYTE_ABST0ADDIUT5,ZERO,0X10LWS7,0X3CK15LL3SATDLWT0,0S7SLLT1,T0,2ADDUT2,T1,T6LWT3,0T2ADDUS6,T3,S6S6T3S6ADDIUT5,T5,0XFFFFT5BNET5,ZERO,LL3SATDSUBUS7,4S7从3916次计算减少为4816次计算。55小结本章介绍了H264编码器测试模型JM86的算法优化，MIPS平台WINCE上的移植，和MIPS平台上的指令优化。38参考文献1ISO/IECIS1449610INFORMATIONTECHNOLOGYCODINGOFAUDIOVISUALOBJECTSPART10ADVAN
