《图像无损压缩算法的 DSP 实现及优化.doc》由会员分享，可在线阅读，更多相关《图像无损压缩算法的 DSP 实现及优化.doc（9页珍藏版）》请在三一文库上搜索。
1、精品论文推荐图像无损压缩算法的 DSP 实现及优化李冠一 北京邮电大学信息与通信工程学院，北京(100876) E-mail：摘要： 随着数字图像通信技术的发展，大量图像数据的存储和传输，极大地制约了图像 通信的发展，并成为图像通信领域中的“瓶颈”问题。本文基于经典的 Huffman 编码算法，针 对其数据编码速度和解码速度都比较慢的缺点，给出了一种基于快速 Huffman 压缩、解压缩的图像无损压缩算法。这样，只需增加少量的存储码表空间就可以实现快速查找，比传统方式节省了大量的判断时间。接着在 TI 的 DSP 集成开发环境 CCS 的软仿真环境下实现了 该算法，并针对硬件平台特点进行了程序
2、优化，对比较耗时的关键代码段编写线性汇编程序 进行进一步优化。最后，使用 CCS 的代码剖析工具 profiler 对代码进行剖析，结果表明，该 方法在嵌入式平台上的压缩和解压缩所需的时间均达到了预期的目标，从而为数字图像的实 时性编码传输提供了保证。 关键词：Huffman；无损压缩；DSP；TMS320C6455；优化；线性汇编 中图分类号：TN911.731.引言近年来，随着数字图像通信技术的发展，大量的图像数据的存储和传输，极大地制约了 图像通信的发展，己经成为图像通信领域中的“瓶颈”问题。众所周知，图像进行有效的压缩 可以节省存储空间和传输带宽。利用图像数据中存在的各种冗余及人类视觉
3、特性，在保证一 定的图像质量的条件下，减少原始图像数据量的处理过程，称为图像编码压缩。根据恢复图 像的准确程度，可将图像的编码方法分为两大类123：一类是无损压缩法；另一类是有损 压缩法。有损压缩法压缩了熵，会减少信息量，造成一定程度的失真，而损失的信息不可恢 复，因此这种压缩法是不可逆的，并可获得较高的压缩比，可用于对图像、声音、动态视频 等数据的压缩，。无损压缩则是编码过程中仅仅去除图像的冗余，图像信息必须保证不丢失， 从而可以完整的重建原始图像。无失真编码的目的就是对给定的图像用较少的位数来表示， 同时又不丢失任何信息。无损压缩的压缩比比较低，一般只能获得 2: 1 5: 1 的压缩比。
4、图像无损压缩主要应用于一些需要对图像做进一步处理（特征提取、图像增强等）、重复压缩与解压缩、图像的获取代价昂贵、图像的要求质量未知等领域，如指纹图像、遥感图 像、医用图像处理等。现有的各种无损压缩算法普遍存在着压缩效率不高、运算速度很慢的 特点，不能满足图像实时压缩的要求。高效、实时的无损图像压缩技术一直是人们追求的目 标。因此研究基于嵌入式 DSP 芯片的高效、快速的图像无损压缩技术和算法有很重要的理 论意义和实用价值。本文主要研究基于 Huffman 编码的图像无损压缩算法及其 DSP 的实现与优化。2.Huffman 编码Huffman 编码4是 David. A. Huffman 于
5、1952 年提出的一种基于统计模型的无损压缩编 码方法。其主导思想是根据数据符号发生的概率进行编码，对于小概率的输入符号使用长码 字表示，而对于大概率的输入符号用短字码表示，从而达到较短的平均编码。理论研究表明 Huffman 编码具有非常接近理论极限的压缩比，该方法自提出后就成了数据压缩中的一个研 究主题并被广泛的应用于文本、图像及视频的压缩。如 JPEG、MPEG 标准中。- 9 -3.TMS320C6455DSP 的结构和特点TMS320C6455 是 TI 公司推出的一款高性能定点 DSP5。它是 TI 公司基于第三代先进 VelociTI TM VLIW（超长指令字）结构开发出来的新
6、产品，在通信、医疗图像、无线传输方 面都可以大有作为。TMS320C6455DSP 建立在增强型 C64x+DSP 内核基础之上，该内核添加了专用的新指令，与基于 TI 当前的高级 C64xDSP 架构的代码相比，代码尺寸平均缩短了20%至 30%，周期效率提高了 20%。新指令包括复杂的 32 位宽乘法以及同步加减法指令 (simultaneous add/subtract instruction)，提高了快速傅里叶变换(FFT)以及离散余弦变换(DCT) 的性能。内核每个周期可执行 8 个 16x16 乘法与加法指令，比当前 C64x DSP 内核的每周期 执行指令翻了一番。TMS320C
7、6455 主频达到了 1GHz，1ns 的指令周期。每周期执行 8 条 32 位指令，最大 峰值速度达到 8000MIPS。这意味着，在 1G 时钟频率下，8000 个 16 位*16 位的 MACs 能在1 秒钟发生。TMS320C6455 还带有 Serial RapidIO总线，互连速率每秒高达 25Gbits，实现 了极高的多处理性能，降低了系统消耗，比此前的外部存储器接口快 12 倍，这使得多 DSP 级连变得十分方便。TMS320CC6455 片内是基于 C64xx 内核的 L1/L2 存储结构，片上集成 有大量的存储空间。L1P 为 32K 字节，L1D 为 32K 字节，L2
8、为 2M 字节，比此前 C64x 的 存储器容量翻一番，其中 L1P 和 L2 都可直接映射到存储空间。由于新型 C64x+指令集是 C64x 指令的超集，因此新器件的软件对象代码与现有 C64xDSP 的代码可实现 100%的兼容性，使客户可继续充分利用其软件投资，并立即开始投 入新 C6455 DSP 的设计工作。4.基于 TMS320C6455 DSP 的软件开发与优化在编写和调试 C6000 代码时，如果遵循图 1 所示的代码开发流程，则能从 C6000 代码 获得最好的性能。C6000 的软件开发分为三个阶段：第一阶段产生 C 代码，第二阶段优化 C 代码，第三 阶段编写线性汇编。每
9、个阶段完成的任务如下67：第一阶段：在不考虑任何 C6000 相关知识的情况下，根据任务编写 C 代码。然后，使 用 C6000 profiling 工具确定代码中可能存在的低效率段。通常这个阶段的代码性能很低，为 进一步改进代码性能，则需要进入第二阶段。第二阶段：利用内联函数、外壳选项和其他优化方法改进 C 代码。使用 profiling 工具 检查其性能，如果代码仍不能达到所期望的效率，则进入第三阶段。第三阶段：从 C 代码中抽出对性能影响很大的代码段，用线性汇编重新编写这段代码， 然后使用线性汇编优化器优化该代码。上述的三个阶段不是必须都经过的。当在某一阶段已获得了期望的性能，就不必进入
10、下 一阶段。精品论文推荐第1阶段:产生C/C+代码写C/C+代码编译测试执行时间足够是完成 有效?第2阶段:优化C/C+代码否优化C/C+代码编译测试执行时间足够是完成 有效?否是有更多的C/C+优化 措施?第3阶段:写线性汇编代码否 写线性汇编代码汇编优化测试执行时间否足够有效?是完成图 1 C6000 的程序开发流程下面分别对每一个阶段进行介绍。4.1 写 C/C+代码（算法优化）Huffman 编码是一种可变字长编码(VLC)，压缩后产生的码字长度不固定。传统的编码 需要在编码的过程中建立编码树，并对原始数据扫描两遍，第一遍扫描要精确地统计出原始 数据中的每个值出现的频率，第二遍是建立
11、Huffman 树并进行编码。由于 Huffman 编码需 要建立 Huffman 二叉树，并遍历二叉树生成编码，因此其数据压缩速度和还原速度都较慢。 由于在本文需要解决的问题中，需要压缩的图像只有有限的几类，而每一类中的图像基本上 是一样的，具有几乎完全相同的统计特性，所以本文在编解码之前事先统计好每一类图像的 统计特性，并对其进行 Huffman 编码，得到其编解码时所需要的码表。采用查表法来进行 编解码，这样虽然浪费了内存，不过速度显著提升。传统的解码方法必须逐位读入码流，先判断码字长度，再进行解码，效率很低。所以在解码时，采用了分步查表法进行 Huffman 解码，其主要思路是每次读入
12、固定的比特数，如果命中则输出解码值，否则对剩余部分进行传统方式的解码。这样，只需增加少量存储码表 空间就可以实现快速查找，一次读入的比特数越多查找速度就越快，即使是不能立即完成解 码的码字，也比传统方式要节约大量的判断时间。Huffman 码表的每一项都由码字和码表构 成，且码表中的每一项都按照输入码字的顺序进行排列。在做具体的优化工作之前，对于整体结构的把握是很重要的，尤其是对代码中每个模块 的耗时部分。本文使用TI 公司的第三方集成开发环境CCS自带的Profile功能，对编写的 Huffman 无损压缩代码进行剖析，通过剖析，确定出代码中几个最耗时的部分。经过测试， 得到的结果如表1所示
13、，耗时最高是数据压缩函数Compress_Data。表1 对Huffman编码过程不进行任何优化时的耗时分析主要函数占用的指令周期数Compress_Data435457919FILE_Compress16322394HUFF_Compress4834.2 C/C+代码优化对于 C6000 硬件平台选用 C 语言编程时，可利用 C6000 优化方法优化 C 代码。这些方 法包括使用编译器选项、intrinsic 函数和代码转换(字型访问短型数据、软件流水和循环展开 等)。下面简要介绍本文所用的几个主要的优化方法。4.2.1 利用 C6000 C 语言编译器优化程序表 2 所示为本文所用的几个关
14、键的编译器优化选项。表 2 TMS320C6x C 语言编译器优化选项选项功能描述-o使能软件流水和其他优化方法，n 指示优化级别-pm使能程序级优化-mt使能编译器假设程序中没有数据存储混淆-mg使能 profile(分析)代码优化-mh允许投机执行，n 指示投机执行门限-k保留汇编文件供分析编译器反馈用其中，-o 是必需的自动优化选项，通常选择-o2 或-o3，则编译器将根据程序尽可能地安排软件流水线。所谓软件流水线，是对一个循环结构的指令进行调度安排，使多次迭代中的 指令进行流水线操作并行执行。在图像处理算法中存在大量的循环操作，因此充分地利用软 件流水线技术，能极大地提高程序的运行速度
15、。精品论文推荐4.2.2 对短字长的数据使用宽长度的存储器访问我们知道，C6000 访问存储器是很浪费时间的，要提高指令的执行效率，就应该使一条 Load/Store 指令能访问多个数据。C6000 有一些特殊的内联函数，可使用字（整型）一次访 问两个短型数据、4 个 8 位数据；使用双字一次访问两个 32 位数据、4 个 16 位数据，甚至 是 8 个 8 位数据。充分运用这种功能，一次可以进行多个数据的运算，速度将显著提升。这 种类型的优化，称为数据打包处理。在数字图像处理中，图像数据是一片连续的数据流，通常为 char 型数据(8bit、256 级灰 度图像)，所以充分利用这种方法，能有
16、效的提高代码的效率。4.2.3 软件流水 软件流水是一种安排循环内的指令运行方式，使循环的多次迭代能够并行执行的一种技术。使用-o2 和-o3 选项编译 C/C+程序时，编译器就从程序内收集信息，尝试对程序循环实现软件流水。其次，在编译 C 语言程序时，编译器在产生的.asm 文件里向程序员反馈了很多信息。 理解这些信息，按照它的提示修改 C 语言程序，对尽快地优化代码很有好处。用选项-k 令 编译器保留.asm 文件，就可以读到很多这种信息。还可以使用-mw 选项把软件流水循环中 单次迭代情况以及寄存器使用表放到生成的汇编文件中。4.3 通过线性汇编优化汇编代码在使用 C6000 编译器开发
17、和优化 C/C+代码以后，对 C/C+代码中的低效率段用线性 汇编重新编写，再用汇编优化器优化611。用线性汇编语言优化可以从以下的几个方面着手： 让代码尽可能并行执行。 对短字长的数据使用宽长度的数据访问。如用字访问短型数据和使用双字访问字型 数据。 采用软件流水。软件流水是编排循环指令，使循环的多次迭代能够并行执行的技术。 多周期循环的模编排。当循环的一次迭代里出现了资源冲突，即就是有多个指令使 用同一个资源时，要使用多周期编排的模编排。 如果循环的一个迭代所写出的值正是下次迭代要读的值，就会产生循环传递路径， 这样会影响软件流水的执行。所以应该消除循环传递路径的影响。 当循环的资源没有被
18、充分利用的时候，可以通过展开循环提高其性能。 通过线性汇编优化汇编代码时，首先要写出需要优化的 C 程序代码段的一般汇编形式，然后对应一般汇编形式画相关图并分配资源，然后写出与相关图对应的汇编代码。下面以 Huffman 无损压缩编码过程中最耗时的数据压缩为例说明通过线性汇编优化汇 编代码的方法。压缩数据的 C 代码：for ( i=0; inSrcLen; i+)code 16 )bitCount = bitCount-16;*p2+=(uint16_t)(codebitCount)&0xffff);code&=(0xffff(16-bitCount);if( bitCount!=0 )*p
19、2+=( uint16_t)(code(16-bitCount);len=(p2-pDes)*2;经过压缩数据的汇编程序对应的相关性图：LDBUoffset5 5LDBU LDHUconstbitCountADDADDbitCount*1lengthSHL 5codeTemp1ORcodeSHLORcodeSrc5SUBSUBbitCountTemp11code1CMPGT 1condMVbitCount1SHRUSHRUconst1SUBcodeTemp21STHSUBbitCountTemp0xffffSHRU1SHRUcodeTemp3*p211 AND ANDcode最终的线性汇编代码
20、图 2 Huffman 编码函数的相关性图.global_Compress_Data_SA_Compress_Data_SA:.cprocpSrc, codeLength, codeTable, nSrcLen, pDes.no_mdep.regmask,len, offset, length, code, codeSrc.regbitCount, const, nShift, p2, bitCountTemp1, bitCountTemp2LOOP:.regcond, cond1, codeTemp1, codeTemp2, codeTemp3MVpDes,p2ZEROcodeZERObit
21、CountMVKL0x0000ffff, maskMVKH0, maskMVK16, constLDBU*pSrc+, offsetLDBU*+codeLengthoffset,lengthSHLcode, length, codeTemp1LDHU *+codeTableoffset, codeSrc ORcodeTemp1, codeSrc, code ADDbitCount, length, bitCount CMPGT bitCount, const, condcondSUBbitCount, const, bitCountcondMVbitCount, bitCountTemp1co
22、ndSHRUcode, bitCountTemp1, codeTemp2 condSTHcodeTemp2, *p2+condSUBconst, bitCountTemp1, bitCountTemp2 condSHRUmask, bitCountTemp2, codeTemp3 condANDcode, codeTemp3, codenSrcLenBDECLOOP, nSrcLenCMPEQ bitCount, 0, cond1 !cond1 SUBconst, bitCount, nShift !cond1 SHLcode, nShift, codeTemp1 !cond1 STHcode
23、Temp1, *p2+SUBp2, pDes, len.returnlen.endproc最终的汇编代码循环核：$C$L4:; PIPED LOOP KERNEL$C$DW$L$_Compress_Data_SA$6$B:OR.L2XcodeTemp1,codeSrc$2,code ; |18| | condSHRU.S1mask,bitCountTemp2,codeTemp3 ; |30| |ROTL.M1codeSrc$1,0,codeSrc$2 ; |17| Split a long life|CMPGT.L1bitCount,const,cond ; |24| condSHRU.S2c
24、ode,bitCountTemp1,codeTemp2 ; |27| |MV.L2Xlength,length; |15| Define a twin register| condSUB.L1bitCount,const,bitCount ; |25| |LDBU.D1T1*pSrc+,offset; |14| condAND.L2Xcode,codeTemp3,code ; |31| |ROTL.M1cond,0,cond; |24| Split a long life| nSrcLen BDEC .S2$C$L4,nSrcLen; |35| | condMV.L1bitCount,bitC
25、ountTemp1 ; |26| |LDBU.D1T1*+codeLengthoffset,length ; |15| cond STH.D2T2codeTemp2,*p2+; |28| | condMV.L2XbitCount,bitCountTemp1 ; |26| Define a twin register|SHL.S2code,length,codeTemp1 ; |16| | condSUB.L1const,bitCountTemp1,bitCountTemp2 ; |29| |ADD.S1bitCount,length,bitCount ; |19| |LDHU.D1T1*+co
26、deTableoffset,codeSrc$1 ; |17| 可以看到，循环核的每个周期可以并行执行五条指令，大大提高了运行速度。表 3 对 Compress_Data 函数优化前后所用指令周期对比优化前指令周期数优化前指令周期数43545791925801148表2所示为Compress_Data函数优化前后所用的指令周期数，可以看到，经过后两个阶段的优化，数据压缩函数所用周期数大幅度减小，优化后的指令消耗周期不到原来的6%，优 化的效果比较明显的。5.结论实验结果表明，经过优化以后，编码和解码的时间均达到了预先的目标，从而为数字图 像的实时性编码传输提供保证。参考文献1David Salo
27、mon数据压缩原理与应用（第二版）M 吴乐南 等译北京：电子工业出版社，20032吴乐南数据压缩M北京：电子工业出版社，20053吴达军，李晔几种无损图像压缩方法的比较与研究J数字视频，1999，208 期：3-64DAVID. A. HUFFMANA Method for the Construction of Minimum-Redundancy Codes J Proceedings of the I.R.E.，1952，40（9）：1098-11015TexasInstrumentsIncorporatedTMS320C6455Fixed-PointDigitalSignalProce
28、ssorOL http:/ 年 10 月 2 日6Texas Instruments IncorporatedTMS320C6000 系列 DSP 编程工具与指南M 田黎育，何佩琨，朱 梦宇北京：清华大学出版社20067任丽香，马淑芬，李方慧TMS320C6000 系列 DSPs 的原理与应用M 北京：电子工业出版社20008TexasInstrumentsIncorporatedTMS320C6000OptimizingCompilerUsersGuideOL http:/，20049Texas Instruments IncorporatedTMS320C6000 Programmers
29、GuideOL http:/，200410 TexasInstrumentsIncorporated TMS320C6000AssemblyLanguageToolsUsersGuideOL http:/，200411 Texas Instruments Incorporated TMS320C64x/C64x+ DSP CPU and Instruction Set ReferenceGuideOL http:/，2007DSP Implementation and Optimization of Image LosslessCompression ArithmeticLi GuanyiSc
30、hool of Information and Telecommunications Engineering, Beijing University of Posts andCommunications, Beijing (100876)AbstractWith the development of the digital image communication technology, a large number of image datas storage and transmission greatly restricted the development of image commun
31、ication, and become a“bottleneck” problem of it. The purpose of lossless image compression is to reduce the amount of data used to represent the image without any information loss, so the original image can be recovered correctly when decoding. Huffman coding is a basic arithmetic of many image codi
32、ng standards, but ithas a shortcoming of slow coding and decoding. This paper gives a fast Huffman compress anddecompresses method based on the traditional Huffman coding method, and Implementation the method on the TI DSP Integrated development environment CCS, and optimize it according to the hardware. The experimental result shows that the time of compression or decompression is achieve the desired objectives, and it guarantees the real-time transmission and coding of digital image.Keywords: Huffman; Lossless Compress；DSP；TMS320C6455；Optimization；Linear Assembly