分数像素精度运动估计的DSP优化方法.doc

第6期宋立锋等：分数像素精度运动估计的DSP优化方法119分数像素精度运动估计的DSP优化方法宋立锋，戴青云(广东工业大学 信息工程学院，广东 广州 510006)摘 要：分析了分数像素精度运动估计中出现过量数据Cache缺失的原因，并且由此提出一种相对于现有技术可以显著减少Cache缺失的1/4像素精度参考图像数据存储方法，从而实现高运算效率和高数据传输效率的1/4像素精度运动估计。关键词：视频编码；数字信号处理；视频编解码的DSP优化中图分类号：TN919.81 文献标识码：B 文章编号：1000-436X(2009)06-0114-06Technique of DSP optimization on fractional-pixel-accuracy motion estimationSONG Li-feng, DAI Qing-yun(College of Information Engineering, Guangdong University of Technology, Guangzhou, 510006, China)Abstract: The reason of excessive data cache miss was analyzed during the fractional-pixel-accuracy motion estimation, and then a new reference picture data storage approach was proposed for quarter-pixel-accuracy motion estimation, which was able to remarkably decrease the data cache miss comparing with the current techniques. By this approach, the quarter-pixel-accuracy motion estimation was implemented with high computational efficiency and high data transmission efficiency.Key words: video coding; DSP; DSP optimization on video codec1 引言随着视频编码技术的发展，运动补偿精度不断提高：H.2611为整像素，MPEG-12、MPEG-23、H.2634和MPEG-4第一版本5为半像素，MPEG-4第二版本、最新H.2646及其国内版本AVS7已经达到1/4像素。分数像素精度运动补偿和运动矢量的引入且精度不断提高，一方面令图像运动突破图像平面取样网格的限制而达到更高精度，另一方面随着信号在空间域的拉伸，低通性质得到改善8。两方面因素均促成压缩性能的提高，代价是实现复杂度大幅提高。收稿日期：2007-12-19；修回日期：2009-04-08数字信号处理器DSP的结构决定了其适合于大数据量且实时的应用。本文所用的TriMedia/ Nexperia处理器包含有助于视频编解码的结构包括大容量片内高速缓存器Cache、大量寄存器、多指令并行处理的超长指令字VLIW结构及众多的运算功能单元、32bit单指令多数据SIMD处理的运算功能单元及指令集9。运动估计在整个视频编码中占据超过50%的CPU时钟周期，精度达1/4像素的运动估计所占比例进一步增大。利用DSP加速运动估计对提高编码速度达到实时至关重要。本文对策是根据DSP内部结构安排合适的1/4像素精度参考帧图像数据存储方法，从而实现高运算效率和高数据传输效率的1/4像素精度运动估计。针对TriMedia处理器数据Cache块长64byte、寄存器读写数据最大位长32的结构，本文提出一种参考帧图像数据存储方法，把每4个同分数位置的水平坐标顺序相接的图像数据合并成为一个32bit的字，存储于存储图像平面内4byte对齐的字位置，不同分数位置的字交错排列。本文方法克服了现有分数像素精度参考帧图像数据存储方法应用于DSP执行实时视频编码时所出现的读取不便、传输效率低下的障碍，在基于TriMedia处理器的会议电视终端的开发过程中取得H.264编码速度的突破性提高。2 分数像素运动估计及相关技术存在的问题分数像素精度运动估计可视为围绕最佳整像素块匹配位置搜索帧间位移精确化位置或最佳低通滤波位置。通常算法是图1的逐级8邻点搜索10：在最佳整像素位置周围8个半像素位置邻点中搜索最佳位置，接着在最佳半像素位置周围8个1/4像素位置邻点中搜索最佳位置，由此类推。运动估计的主要运算是计算过去帧参考图像块与当前帧原始图像块之差的绝对值和SAD。加速运动估计的关键之一是加速SAD计算。许多面向多媒体应用的处理器都提供了专门加速SAD计算的指令。如TriMedia的UME8UU指令可算出4个连续位置上的SAD值，一个时钟周期内可同时执行2条UME8UU指令。图1 1/4精度分数像素运动估计的搜索路径运动估计还需要读取大量参考图像数据以及反复读取原始图像数据。加速运动估计的另一个关键是提高数据传输效率，包括从片外SDRAM至片内Cache的传输和从片内Cache至寄存器的传输。TriMedia的32bit读指令可从数据Cache中读入4个图像数据至一个寄存器, 一个时钟周期内可同时执行2条32bit读指令。TriMedia还拥有全速且分离的16kbyte数据Cache。CPU读内存数据时，如果Cache 命中，就直接从Cache装载数据入寄存器。只有当Cache缺失时，才启动内存读周期一次装载一段连续的数据（称为Cache块，长64byte），期间CPU处于停顿状况而不能执行后续指令，直到被读取数据装入寄存器为止。这段时间为Cache 缺失停顿时间。CPU恢复运行后，Cache块的后续数据继续装入Cache，类似于独立于数据处理的后台操作9。因此，运动估计的DSP优化方法为：用32bit读指令一次读4个图像数据；用UME8UU之类的SIMD指令计算SAD值；在多个搜索位置上重复读取同一Cache块内的数据。这些方法的实现取决于图像数据存储方法。下面分析现有的2种1/4像素精度参考帧图像数据存储方法。图2参考帧一是最简单的1/4像素精度参考帧图像数据存储方法，就是在16:1的1/4像素精度参考帧图像平面内按照一维光栅扫描顺序存储图像数据，存储位置与坐标位置一致，表示如下。1/4像素精度参考帧图像平面内坐标为的一个像素在存储空间的位置为像素存储位置=存储空间首地址+行位置(图像宽度+水平外延长度) 4+列位置(1)其中，行位置：；列位置：。图2 用于1/4像素精度运动补偿的参考帧一JVT官方的H.264参考软件JM使用参考帧一。在该参考帧中，同一分数位置的像素被3个其他分数位置的像素分隔开来，不能在运动估计中直接使用多读多操作SIMD指令：每次只能读入一个参考图像数据至寄存器，读入一个1616方块需要读256次；如欲使用UME8UU指令计算SAD值，需要把分开读入的4个参考图像数据拼装成一个32bit字。因此对于参考帧一，运算效率和从片内Cache传输数据至寄存器的效率太低，只能用作验证模型，不能实用。图3参考帧二1113把不同分数位置的像素分开存储，相同分数位置的像素组成一个1:1图像平面，16：1的1/4像素精度参考帧图像分成16个1:1子图像，在子图像平面内按照一维光栅扫描顺序存储图像数据。该方法特征在于通过式(2)唯一确定1/4像素精度参考帧图像平面内坐标为的一个像素在存储空间的位置，即像素存储位置=由子图像行与列属性确定的存储空间首地址+子图像行位置(图像宽度+水平外延长度)+子图像列位置(2)其中，子图像行属性：；子图像列属性：；子图像行位置：；子图像列位置：。图3 用于1/4像素精度运动补偿的参考帧二使用参考帧二需要一次读取位长大于8的数据，必须了解处理器存取不对齐数据的情况。存储阵列按处理器总线宽度分界，分界线内的数据为对齐数据，可一次存取完毕；跨过分界线的数据为不对齐数据，需要存取分界线两边的2个数据，然后拼接出一个数据。TriMedia 1300和1 500处理器不能自动存取不对齐数据，只能通过人工编程完成；TriMedia 1700、TI公司TMS320C64x、PC机的x86 处理器能够自动存取不对齐数据，对每条读写指令通过内部逻辑电路完成分界线两边的2个32bit数据的读写和拼接。使用参考帧二时可以使用多读多操作SIMD指令。例如用TriMedia处理器读取一个1616参考图像块，如果一行数据4byte对齐（出现概率1/4），分4次读入至4个整型局部变量（由编译器分配为寄存器）中，然后计算SAD，最佳情况下整个块需要读164=64次；如果一行数据4byte不对齐（出现概率3/4），需要分5次读入至5个整型局部变量中，然后根据不对齐的3个位置分3种情况处理，分别用TriMedia的FUNSHIFT3、FUNSHIFT2和FUNSHIFT1双字移位指令从5个整型变量中拼接出所需的4个32bit字，整个块需要读165=80次。平均数是164/4+380/4=76次。但是在图1逐级8邻点搜索的1/4像素精度运动估计中出现过量数据Cache缺失，如图4所示，在计算SAD的总时间中，数据Cache缺失停顿时间占82.95%，指令执行时间即有效运算时间仅占14.67%。也就是说在计算SAD过程中，CPU在82.95%的时间内处于停顿，用以等待数据从内存经过Cache加载到寄存器，有效运算时间只有14.67%。图4 TriMedia 1300处理器完成H.264编码的硬件Profile统计1/4像素精度运动估计需要搜索如图1所示的8个半像素位置和8个1/4像素位置。使用图3参考帧二时，这些搜索位置的数据位于11个1:1子图像内。结合图1和图3看出，在整像素搜索中装载入数据Cache的参考图像数据完全不能被后面的半像素搜索和1/4像素搜索所利用，在半像素搜索中装载入数据Cache的参考图像数据完全不能被后面的1/4像素搜索所利用，甚至1/4像素搜索中于前面搜索位置装载入数据Cache的参考图像数据也完全不能被后面的搜索所利用。其中1/4像素搜索中每个Cache块的数据利用率最大只有16/64。完成一个1616方块在图1的16个分数位置上的1/4像素精度运动估计，视图3参考帧二中每行参考图像块数据对于64byte地址对齐情况（64byte为内存阵列相对于Cache块装载的界线，如一行16个图像数据未跨过界线，装入一个Cache块；否则装入2个Cache块），最少需要从SDRAM装载16+17+17+816=178个Cache块，最多需要装载1782=356个Cache块。从片外SDRAM至片内Cache的传输效率非常低。相比之下使用参考帧一时，在不同搜索位置上读入的参考图像数据同处于一幅16:1图像内，并且交错融合在一起，在当前搜索位置上装载的Cache块数据可为以后的搜索重复利用。每个Cache块的数据利用率最大达到64/64。完成一个1616方块的1/4像素精度运动估计，最少需要从SDRAM装载(16+17)2+216=98个Cache块，最多需要装载(16+17+216) 2=130个Cache块。于是分数像素精度运动估计的DSP优化方法最后归结为寻找兼具高运算效率和高数据传输效率的参考帧图像数据存储方法。3 本文的1/4像素精度参考帧图像数据存储方法把参考帧一中每行图像数据重新组织，每4个同分数位置的水平坐标顺序相接的图像数据合并成为一个32bit的字，存储于存储图像平面内4byte对齐的字位置，不同分数位置的字交错排列，构成图5的参考帧三。图5只示意水平方向上一行图像数据排列方法。垂直方向上列的排列方法按垂直坐标排列，与参考帧一的列排列方法一致。1/4像素精度的宏块宽度64，恰好与TriMedia数据Cache块长一致。图5 用于1/4像素精度运动补偿的参考帧三本文的参考帧三的存储方法详述如下。1) 在主内存为视频信源编码的每个1/4像素精度的亮度分量参考帧分配一段连续存储空间，大小是16(图像宽度+水平外延长度)(图像高度+垂直外延长度)byte。令该段存储空间首地址64byte对齐，同时(图像宽度+水平外延长度)可被4整除。2) 在1/4像素精度参考帧图像平面内按照从左到右、自上而下的顺序存储图像数据，每个8bit像素数据存放到存储空间的一个字节位置上。3) 在1/4像素精度参考帧图像平面内每一行上，对于相同水平分数位置的像素，每4个水平坐标顺序相接的像素数据合并为一个32bit字，存储到存储空间的一个4byte对齐的字位置上，字的存储顺序为4个像素中为首的像素水平坐标值除4再加上分数值。例如，如图6所示，每行水平坐标16n, 16n+4, 16n+8, 16n+12的4个整像素数据合并为一个32bit字，存储顺序为4n；水平坐标16n+1, 16n+5, 16n+9, 16n+13的4个1/4像素数据合并为一个32bit字，存储顺序为4n+1；水平坐标16n+2, 16n+6, 16n+10, 16n+14的4个半像素数据合并为一个32bit字，存储顺序为4n+2；水平坐标16n+3, 16n+7, 16n+11, 16n+15的4个3/4像素数据合并为一个32bit字，存储顺序为4n+3。于是1/4像素精度参考帧图像平面内的一行图像数据存储完毕。4) 在1/4像素精度参考帧图像平面内按垂直坐标顺序一行接一行地存储数据。于是1/4像素精度参考帧图像平面内的全部图像数据存储完毕。图6 参考帧三每行图像数据的存储方法本文方法的特征还在于根据式(3)唯一确定1/4像素精度参考帧图像平面内一个坐标的像素在存储空间的位置，即存储位置=参考帧存储空间首地址+行位置 (图像宽度+水平外延长度)4+列位置(3)其中，行位置：；列位置：。令一段存储空间首地址64byte对齐的代码如下。ptr0和ptr1为无符号字符型指针。ptr0 = (unsigned char *)malloc(16(图像宽度+水平外延长度)(图像高度+垂直外延长度)+64)。ptr1 = (unsigned char *)(ptr0 + 63)&(63)。于是ptr1指向的存储空间首地址64byte对齐，目的是少占用Cache块。ptr0的数值必须保留以正确释放空间。令(图像宽度+水平外延长度)可被4整除，使得参考图像块各行4byte对齐情况一致，便于32bit读取和拼接。式(3)显得比式(1)和式(2)复杂，但是在实际应用中所增加的运算量可以忽略不计。因为所有视频编码标准均采用块匹配的运动估计与运动补偿方法，存取参考图像数据的单位是块而非像素，每个参考图像块仅需要利用式(3)计算一次块左上顶点的存储位置，其他点可根据各自在参考帧三内的二维偏移量被正确存取。更何况式(3)中运算对于TriMedia处理器为花销最小的操作。参考帧三与参考帧二一样方便32bit读指令一次读入4个图像数据，也同样方便运用SIMD指令加速运动估计中SAD计算。实际上使用参考帧三和参考帧二的SAD计算模块的源代码基本相同。唯一差异在于读取一行参考图像数据的32bit整型指针的递增量：参考帧三是4，参考帧二是1。例如用指向一行参考图像数据首地址的整型指针ref_ptr读入1616方块的一行数据，对参考帧三用ref_ptr0, refptr4, ref_ptr8, ref_ptr12, 以及行不对齐时的ref_ptr16读完，对参考帧二用ref_ptr0, refptr1, ref_ptr2, ref_ptr3, 以及行不对齐时的ref_ptr4读完。所以参考帧三在运算效率和从片内Cache传输数据至寄存器的效率上与参考帧二相同。参考帧三又与参考帧一一样不同分数位置像素同处于一幅16:1图像内，并且交错融合在一起，在当前搜索位置上装载的Cache块数据可为以后的搜索重复利用，适合围绕最佳整像素块匹配位置搜索帧间位移精确化位置或最佳低通滤波位置的逐级8邻点搜索。使用参考帧三执行1/4像素精度运动估计时，每个Cache块的数据利用率最大达到64/64。完成一个1616方块的1/4像素精度运动估计，最少需要从SDRAM装载98个Cache块，最多需要装载130个Cache块，与参考帧一的情况相同。所以参考帧三在片外SDRAM至片内Cache的传输效率与参考帧一相同。4 测试测试平台为插在PC机PCI槽的TriMedia 1300开发板（处理器PNX1302EH，主频200MHz，普通SDRAM速度100MHz），使用4个标准测试序列的磁盘文件，Foreman、Mobile & Calendar、News、Silent Voice，分辨率CIF（352288），长度300fame。从main()函数直入H.264编码模块，单任务运行，未使用TriMedia片内任何协处理器和外围部件，从磁盘读入图像数据，经PCI接口传输至TriMedia芯片，编码后生成H.264码流输出到磁盘。使用2个版本的H.264编码软件：Cache优化前版本使用参考帧二，最新版本使用参考帧三。用TriMedia 1300开发板对测试序列执行编码，额定码率为384kbit/s和768kbit/s，输出按各个函数分别统计的Profile文件，读出其中的数据，算出指令执行时间、数据Cache缺失停顿时间和指令Cache缺失停顿时间(三者之和即总编码时间)，如图4所示。5 结束语将3个参考帧在TriMedia处理器上完成一个1616块1/4像素精度运动估计时参考图像数据读取次数和数据Cache块装载数列于表1。表1显示参考帧三的从片外SDRAM至片内Cache和从片内Cache至寄存器的数据传输效率最高。图4的测试数据显示：在计算SAD部分，数据Cache缺失停顿时间降低了整一个数量级，总处理时间只有原来的1/5，其中数据Cache 缺失停顿时间下降到41.69%，指令执行时间上升到52.00%。包含本文数据Cache优化成果的H.264编码库在TriMedia PNX1502E芯片（主频300MHz，DDR SDRAM速度400MHz）上实现2Mbit/s以下所有码率对CIF视频信号的实时编码，使得相关的H.323会议电视终端在2005年中达到当时的业界先进水平。表1 一个1616块在使用不同参考帧完成1/4像素精度运动估计的效率比较参考帧一参考帧二参考帧三读一个1616块的读次数2567676完成1/4像素精度运动估计的装载Cache块数9813017835698130参考文献：1ITU-T Recommendation H.261, Video Codec for Audiovisual Services at 64p kbit/sS. Version 1: Nov 1990, Version 2: March 1993. 2ISO/IEC 11172-2, Coding of Moving Pictures and Associated Audio for Digital Storage Media at Up to 1.5Mbit/s: VideoS. 1993.3ISO/IEC 13818-2 and ITU-T Recommendation H.262, Generic Coding of Moving Pictures and Associated Audio Information: VideoS. 1995. 4ITU-T Recommendation H.263, Video Coding for Low Bit-Rate CommunicationS. Version 1: November 1995, Version 2: January 1998, Version 3: Nov 2000. 5ISO/IEC 14496-2, Generic Coding of Audiovisual Objects Part 2: VisualS. Version 1: January 1999, Version 2: January 2000, Version 3: January 2001. 6ITU-T Recommendation H.264, Advanced Video Coding for Generic Audiovisual ServicesS. 2005.7中国国家质量监督检验检疫总局. 中国国家标准GB/T200090. 2-2006, 信息技术先进视频编解码第二部分: 视频S.2006. Chinese National Standard GB/T200090.2-2006, Information Technology - Advanced Coding of Audio and Video-Part 2:VideoS. 2006.8WEDI T, MUSMANN H G. Motion- and aliasing-compensated prediction for hybrid video codingJ. IEEE Trans on CSVT, 2003, 13(7): 577-586. 9Philips Electronics North America Corporation TM1300 Preliminary Data BookR.North America: Philips,1999. 10王维东, 姚庆栋，刘鹏. 小数像素运动估计快速算法J. 通信学报, 2003, 24(4): 128-132. WANG W D, YAO Q D, LIU P. Fast