（测试计量技术及仪器专业论文）ccsds压缩算法的研究和blackfin解码实现.pdf

摘要 摘要 随着航空航天技术的发展，人们加快了对太空探索的脚步，这对于空间图像 的实时性、高速率传输提出了更高的要求。空间图像的特点是信息量大，对图像 重建质量要求高，这在传输带宽资源有限的情况下，对大容量的空间图像的压缩 既要实现高保真又要保证实时传输。c c s d s ( 空间数据系统咨询委员会) 于2 0 0 5 年1 1 月提出了c c s d s 空间图像压缩算法。该算法的应用定位于太空飞行器中的 高速设备，算法复杂度低，不需要复杂的算法知识就可以理解与应用，支持高速 低功耗硬件实现，支持有损和无损压缩，在空间探测领域具有良好的应用前景。 本文工作的目的就是在b l a c k f i n 上实现c c s d s 压缩算法。首先对c c s d s 算 法进行了深入理解，着重对算法进行了c 优化，成功完成了解码的d s p 移植；其 次，在b l a c k f i n 处理器上进行更一步的优化措施，包括对小波反变换进行了汇编 优化改进、数据存储结构进行调整等，并给出最后优化结果。 最后，对所做的工作进行总结和回顾，对未来的工作提出一些建议。 关键词：图像压缩c c s d sb l a c k f i n 移植优化 a b s t r a c t a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fa v i a t i o n ，t h e r ea r cm o r ed e m a n d sa b o u th i g h s p e e da n dr e a l - t i m ep r o p e r t yf o rs p a c ei m a g ec o m p r e s s i o n 。t h ec h a r a c t e r i s t i co fs p a t i a l i m a g ei st h a ti th a sp l e n t yo fi n f o r m a t i o na n dt h a tt h e r ea r eh i 【g hd e m a n d s a b o u ti m a g e r e c o n s t r u c t i o nq u a l i t y n o wt h ec h a n n e ib a n d w i d t hr c s o u r c c sa r ci i m i t e d ，a n dt h e c o m p r e s s i o na l g o r i t h ms h o u l db ee f f e c t i v ea n de x c e l l e n ti nr e a l - t i m ep r o p e r t y c c s d s ( c o n s u l t a t i v ec o m m i t t e ef o rs p a c ed a t as y s t e m ) f o r m a l l yp r o p o s e dt h es p a c ei m a g e d a t ac o m p r e s s i o na l g o r i t h ms t a n d a r di nn o v 2 0 0 5 t h i sa l g o r i t h ma p p l i c a t i o nl o c a t e s i nt h eh i g h - s p e e de q u i p m e n t so ft h eo u t e rs p a c ef l i g h tv e h i c l e o n ec a r lu n d e r s t a n da n d a p p l yi tw i t h o u tt h ec o m p l e xa l g o r i t h mk n o w l e d g e i ts u p p o r t sh i g h - s p e e dl o wp o w e r h a r d w a r ei m p l e m e n t a t i o na n ds u p p o r t sl o s sa n dl o s s l e s sc o m p r e s s i o n ，s oi th a st h e g o o da p p l i c a t i o np r o s p e c ti nt h eo u t e rs p a c ee x p l o r a t i o n t h em a i np u r p o s eo ft h i sp a p e ri st oi m p l e m e n tt h ec c s d sc o m p r e s s i o n a l g o r i t h mo nb l a c k f i n f i r s t , i tm a k e sad e e pu n d e r s t a n d i n go fc c s d si m a g ed a t a c o m p r e s s i o n ，a f t e rw h i c hi s t h e o p t i m i z a t i o n o ft h ecl a n g u a g ep r o g r a m ，t h e n s u c c e s s f u l l ya c c o m p l i s h e st h et r a n s p l a n t a t i o no ft h ed s p ；s e c o n d ，i tm a k e s af u r t h e r i m p r o v e m e n ta n do p t i m i z a t i o no nb l a c k i i np r o c e s s o r , i n c l u d i n g t h ea s s e m b l eo f r e v e r s i n gt h ew a v e l e tt r a n s f o r m ，t h ea d j u s t m e n to f t h ed a t ac o n f i g u r a t i o n f i n a l l y , t h e r ei sa s u m m a r i z a t i o no ft h ew o r kw h a th a sb e e nd o n ea n dp u tf o r w a r d t ot h ef u t u r ed i r e c t i o n k e y w o r d s ：i m a g ec o m p r e s s c c s d sb l a c k f i n t r a n s p l a n to p t i m i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：】! ) 显 日期丝! ! ! ! ：! 斗 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名： 导师签名： 日期鲨! ! ! ! ：! 生 日期丝z 复： 第一章绪论 第一章绪论 1 1 引言 随着信息时代的到来和计算机网络技术的飞速发展，人们需要存储、处理和 传输的信息越来越多，而图像作为这些信息中的重要表现形式，其具有数据量大、 带宽宽等特点，这就给图像的存储、处理和传输带来了很大的困难。尤其是图像 信息的传输，一方面需要增加信道，但这很有限，因为信道的增加永远赶不上信 息的爆炸式增长，况且还要受到环境的限制；另一方面，就必须减少表示图像的 数据量，以达到压缩图像数据的目的。 与此同时，当今航空航天技术的飞速发展，人们探索太空的脚步正在加快， 为了进行科研工作，往往需要大量的空间图像数据，基于此，对于空间图像的实 时压缩和传输也成了研究热点。现在的图像处理都是基于数字图像的，而图像进 行数字化之后的数据量是惊人的，空间图像的特点就是信息量大，空间冗余量低， 对图像恢复质量要求高，这在传输带宽资源有限和存储空间有限的情况下，对大 容量的空间图像既要实现高保真又要保证实时传输。在航天器存储器有限，信道 带宽极为珍贵的情况下，高效的图像压缩就变得十分必要。 1 2 图像压缩编码的概念 图像压缩编码就是图像数据的压缩和编码表示，是通过消除冗余来设法减少 表达图像信息所需数据的比特数。从统计意义上来说，就是将图像数据转换为尽 可能不相关的数据集合。图像压缩编码系统主要包括图像编码和图像解码两部分。 前者就是对图像信息进行压缩和编码，在存储、处理和传输前进行，也称图像压 缩。后者是对压缩图像进行解压以重建原图像或其近似图像。 1 3 图像压缩方法分类 根据不同的目的和不同的应用，图像压缩有不同的分类方法，比如可按压缩 前及解压后的信息保持程度和图像压缩的方法原理来分类1 们。 1 3 1 按信息保持程度分类 1 ) 信息保持型【1 2 】 减少或去除冗余数据，同时保持信息不变，即压缩、解压中无信息损失，也 称无失真无损可逆型编码。主要用于图像存档，其特点式信息无失真，但压缩 比有限。 c c s d s 压缩算法的研究和b l a c k f i n 解码实现 2 ) 信息损失型 以牺牲部分信息为代价，来获取高压缩比，也称有损压缩。解压后得到原图 像的近似。数字电视、图像传输和多媒体等应用场合常用这类压缩。其特点是通 过忽略人的视觉不敏感的次要信息来提高压缩比。 3 ) 特征抽取型。 在图像分析、分类与识别中，仅对于实际需要的( 提取) 特征信息进行编码， 而丢掉其他非特征信息，可大大压缩数据量。这实际属于信息损失型。 1 3 2 根据图像压缩的方法原理分类 1 ) 像素编码 所谓像素编码就是无论像素之间的相关性如何，编码时只对每个像素单独处 理。如脉冲编码调制( p c m ) ，熵编碉j ( e n t r o p yc o d i n g ) ，行程编码( r u nl e n l g t hc o d i n g ) 等。 2 ) 预测编码 像素的灰度是连续的，通常在一片图像去眼肿，相邻像素的灰度值之间有很 大的相关性，即相互之间差别可能很小。通过去除相邻像素之间的相关性和冗余 性，而只对新的信息进行编码，这就是预测编码，常用的预测编码是差分脉冲编 码调制( d p c m ) 。 3 ) 变换编码 所谓变换编码时指对给定图像采用某种变换，使得大量的信息能用较少的 数据来表示，从而达到压缩的目的。变换编码中通常采用的变换包括：离散傅立 叶变换( d f l ) ，离散余弦变换( d c l ) 和离散小波变换( d w l ) 。 4 ) 其他方法 其他方法包括早期的编码，如混合编码( h y b r i dc o d i n g ) 、矢量量化( v q ) 、l z w 算法。近年来也出现了很多新的压缩编码方法，如使用人工神经元网络( a n n ) 的 压缩编码算法、分形( f r a c t a l ) 、小波( w a v e l e 0 、基于对象( o b j e c tb a s e d ) 的压缩算法、 基于模型的压缩编码算法等。 1 4 编码系统的实现平台 ( 1 ) d s p 平台 在信号处理电路的设计中，以d s p 芯片为核心来构成完成算法所需的电路系 统是种较为方便的办法。可利用现成的微处理器开发系统，在算法己用c 语言验 证的基础上，在开发工具的帮助下，把该c 语言程序转换为d s p 芯片的汇编，然 后再编译为机器代码，最后加载到样机系统的存储区，即可以在开发系统工具的 第一章绪论 环境下开始相关算法的运算仿真。这种方法属于软件开发的方法，较为简单，设 计周期短，调试和修改方便，可利用的资源多。 本文采用a d i 公司推出的专门面向媒体处理的b l a c k f i n 系列定点d s p 作为 硬件平台。b l a c k f i n 处理器在单内核产品中可提供高达7 5 6 m h z 的性能。b l a c k f m 处理器系列中的新型对称多处理器成员在相同的频域条件下实现了性能的翻番。 b l a c k f i n 处理器系列还提供了低至0 8 v 的业界领先功耗性能。 ( 2 ) f p g a 平台 用f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 实际上最终将算法转换为实际的专 用数字电路来执行，虽然与d s p 软件开发的方法相比，具有很强的并行处理能力， 提高了效率，增强了灵活性和优化空间，但是其编程复杂，功耗比较大，开发周 期长等也是不能忽视的。 ( 3 ) a s i c 平台 a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r e u i 0 是指应特定用户要求和特定电子 系统的需要而专门设计、制造的集成电路。a s i c 的特点是面向特定用户的需求， 这种方法针对性强，优点是批量生产时单位成本较低，器件体积小，以及内部时 钟频率较高；缺点是开发周期较长，灵活性比较差。 1 5 论文主要内容 本文以实验室经过改进的c c s d s 算法为基础，在对算法进行深入分析的基 础上，对算法主要计算模块进行c 语言和汇编优化，使其对硬件的存储能力和计 算能力的要求有所降低，在此基础上，采用a d i 的b l a c k f m5 3 3 作为主处理平台， 研究图像编码算法向d s p 上的移植。 论文分为四章：各章的主要内容安排如下： 第一章，介绍空间图像压缩的必要性，以及压缩编码的概念和分类，算法的 选择和系统实现平台的选择。 第二章，叙述c c s d s 空间数据图像压缩编码的过程，针对里面的小波变换 和位平面编码的具体算法进行详细描述。 第三章，介绍d s p 硬件开发环境，主要包括a d i 公司的b l a c k f md s p 芯片 的结构特点、内核结构，存储器结构，d m a 控制器及其软件平台开发工具。 第四章，主要是基于b l a c k f i nd s p 的c c s d s 图像压缩系统的代码优化和移 植，首先介绍和分析整个解码算法，然后介绍整个开发过程中采用的各种优化的 方法及整体优化，最后给出优化后的结果。 第二章c c s d s 图像压缩算法 第二章c c s d s 图像压缩算法 c c s d s 图像压缩算法i ”1 2 】是有国际空间数据系统咨询委员提出的针对空间 图像进行压缩的一种算法。此算法支持有损和无损两种压缩方式：支持基于帧扫 描和基于带扫描两种扫描方式；最大支持1 6 比特的图像数据；算法复杂度低，结 构简单，支持空间数据的高速实时处理1 9 】。它主要包括离散小波变换、位平面编 码两个大部分，离散小波变换主要是去除图像数据的空间相关性，位平面编码是 根据变换后的小波数据的特点，对其进行编码，以达到压缩的目的。 压缩 图2 1c c s d s 图像压缩系统构成 2 1 小波变换 小波变换的主要算法是由法国的科学家s t e p h a n em a l l a t 在1 9 8 8 年提出的；。 他在构造正交小波基时提出了多分辨率的概念，从空间上形象地说明了小波的多 分辨率特性，提出了正交小波的构造方法和快速算法，叫做m a l l a t 算法i 引。该算 法同意了在此之前构造正交小波基的所有方法，其地位相当于快速傅里叶变换在 经典傅里叶分析中的地位。 i n f i dd a u b e c h i e s1 9 8 8 年最先揭示y d , 波变换和滤波器组( f i l t e rb a n k s ) 之间的 内在关系，使离散小波分析变成为现实。在信号处理中，自从s m a l l m 和i n r i d d a u b e c h i e s 发现滤波器组与小波基函数有密切关系之后，小波在信号( 如声音信 号，图像信号等) 处理中得到及其广泛的应用。这门新兴学科的出现引起了许多 数学家和工程技术人员的极大关注，是国际科技界和众多学术团体高度关注的前 沿领域。经过几十年的努力，这门学科的理论基础已经基本建立，并成为应用数 学的一个新领域。 在图像压缩算法中，通常使用小波变换对图像进行变换1 1 3 】，小波变换是针对 整个图像的变换，不存在块效应。变换后的小波图像的能量集中于低频部分，而 在垂直、水平和对角线部分的能量较少，c c s d s 算法根据小波系数的这个特点对 变换后的图像数据进行量化和编码达到数据压缩的目的。 c c s d s 图像压缩算法使用的是三级二维离散小波变换( d w t ，d i s c r e t e w a v e l e tt r a n s f o r m ) ，小波变换使用的是9 阶低通滤波器和7 阶高通滤波器，支持 6 c c s d s 压缩算法的研究和b l a c k f m 解码实现 浮点小波变换和整数小波变换。浮点d w t 需要浮点运算，硬件实现复杂度较高， 消耗资源多，在低比特率下压缩效果稍好，但不能实现无损压缩：整数d w t 只 需定点运算，硬件实现复杂度较低，消耗资源少，可以实现无损压缩。无论对于 整数小波变换还是浮点小波变换，对于输入图像的大小的要求都是8 的整数倍， 否则对图像进行扩充预处理【1 4 1 ，使之满足这个条件。具体的扩充方法如下：对于 列数不是8 的倍数的图像，将图像最右列复制到扩充的列；对于行数不是8 的倍 数的图像，将最后行复制到扩充的行。浮点变换和整数变换都能实现图像的有损 压缩，但是整数变换能实现图像的无损压缩，满足图像有损和无损压缩的要求l l l l 2 1 1 。 2 1 1 ( 9 ，7 ) 一维浮点小波变换 标准中一维浮点d w t 仅简单采用系数与像素点的乘积产生低通和高通小波 系数。即对于n 2 的2 n 个像素点 x 0x x 2 肛。) ，其低通系数c j 和高通系数 d j 分别为： 4 q = 毛巾；_ ，= o ，l ，2 ，一l 式( 2 1 ) 一 3 q = 岛j c 2 川+ ；_ ，= o ，1 2 n - i 即h ，3 式( 2 2 ) 其中9 7 浮点d w t 的两组滤波器系数为h 。和g l i 的值大小可以参考表2 1 。 表2 19 7 小波滤波器系数 l 低通滤波系数h i 高通滤波系数g i 00 8 5 2 6 9 8 6 7 9 0 0 9o 7 8 8 4 8 5 6l6 4 0 6 l0 3 7 7 4 0 2 8 5 5 6l30 4l8 0 9 2 2 7 3 2 2 2 士2o 1 1 0 6 2 4 4 0 4 4 1 80 0 4 0 6 8 9 4l7 6 0 9 3_ 0 0 2 3 8 4 9 4 6 5 0 2 00 0 6 4 5 3 8 8 8 2 6 2 9 40 0 3 7 8 2 8 4 5 5 5 0 7 采用这种方式虽然形式简单1 2 3 ) ，但每计算一组系数总共需要1 6 次乘法和1 4 次加法，对于一副1 0 2 4 x1 0 2 4 的图像来说，计算量也是不小的。但观察文献中的 表发现，h 。= h 。，而= g 。因而可把c j 和d j 变化成： 4 q = 勃+ 吃( b + 。+ 勃一。) ；，= d ，7 ，n j 式( 2 3 ) j 第二章c c s d s 图像压缩算法 3 q = g 口勃，+ 晶( 吻+ m + 如j - 。) ；_ ，= 仍j ，j 式( 2 4 ) ，n t l 这样变换后【15 1 ，计算一组系数仍有9 次乘法和9 次加法，但对于二维的图像来说， 要完成小波变换，需要先进行一维行运算，然后是一维列运算，对于3 级变换， 这样的操作还需要重复3 次，减小的计算量还是相当大的。 2 1 2 ( 9 7 ) 一维整数小波变换 为了实现无损压缩为了实现无损压缩【2 射，需要对( 9 7 ) 浮点小波进行非线性 化，这样在去相关的过程中能够产生整数输出。关于低通系数q 和高通系数q ， 需要首先计算q ，然后根据得到的q 求出q d o = 玉一| - 杀+ 毛) 一去“+ ) + 三lj 式( 2 - 5 ) q = 而，一【杀c x 2 j l - x 2 + 2 ，一去c 吃产：+ b p ，+ 三j ，= ，2 。j v 一3 巩。：= 毛m 一【素c x 2 n 4 + x 2 n _ 2 ，一去c 而。+ 恐m ，+ 刘 球：= x 2 n - ：- - l ；3 c 2 n - 2 - - 1 x 2 n _ 4 1 纠 其中：i j 表示取整，下面相同符合定义相同。 c o 愕+ 纠 = x = j - 【一半+ 纠j = 1 , 2 d v - i 2 1 3 二维小波变换 式( 2 6 ) 式( 2 - 7 ) 式( 2 8 ) 式( 2 - 9 ) 式( 2 - 1 0 ) 二维单级小波变换就是对一维小波变换的重复【2 0 1 。一幅图像可以看作一个数 据矩阵，它的每一行、每列都可看作信号向量，二维小波变换的过程如下：对 每行的数据进行一维小波变换，分别生成一个水平低通系数矩阵和一个水平高通 系数矩阵，矩阵的行数和原图像矩阵行数相同，列数是原图像矩阵列数的一半。 然后再对生成的系数矩阵的每一列进行一维小波变换，就得到如图2 2 所示的四 个子带的系数矩阵。这四个子带系数矩阵的大小是原图像的四分之一，自左向右， 自上而下，这四个子带分别为l l 、l h 、i l l 、h h 。 c c s d s 压缩算法的研究和b l a c k f m 解码实现 二维单级小波变换的反变换过程如下，首先是对小波系数矩阵的每一列进行 一维反变换，这时得到的一个系数矩阵，然后再对该系数矩阵的每一行进行一维 反变换，这时就得到原图像。 2 1 4 二维多级整数小波变换 图2 2 一级二维小波变换 为了增加压缩效率，对二维离散小波变换后得到的低频子带l l 继续进行变 换，以降低图像的相关性。c c s d s 标准支持三级小波变换。 图2 3 表示了三级二维小波变换的过程。每一级的变换，是对前一级的l l 子带作二维小波变换，再得到新的四个小子带。依此类推，每一级的小波变换得 到3 个新的子带，但是并不改变总的系数的个数。对于1 1 级的小波变换，得到的 子带数为3 n + l 。协议中的三级小波变换所得到的子带数为1 0 。 第一层变换 2 1 5 小波变换后的系数特点 图2 - 3 图像的三级二维小波变换 图像通过小波变换之后【3 】，可以得到一系列分辨率不同的子图像，能量主要 集中在了低频部分，而高频部分的能量相对较小：高频子图像上大部分点的能量 第二章c c s d s 图像压缩算法 9 很低，但是在高频子带部分的边缘和轮廓又集中了高频显著系数，而且频率越高， 子带的能量越低，因此对于小波系数的有效组织能提高编码效率。根据小波变换 后的系数特点，c c s d s 对于小波系数的组织采用的是四叉树结构【1 6 】，如图2 4 所 示，阴影部分称为一个“家庭”( f a m i l y ) 。这种组织系数的方法是基t - , j , 波多分辨 率的特点，利用各频带的相关特性，用四叉树结构来组织系数，这样充分利用了 系数的相关性。 鬯 麟 簿鹈 糜 瓣糍愁 麟粼 图2 4 小波系数四叉数组织方法 2 2 位平面编码( b p e ) 2 2 1 小波变换后图像系数结构 小波变换后的系数图像结构如图2 5 ，分为四级，d c 系数，父系数，子系数 和孙系数。一个直流系数对应三个p a r e n t s ，以每个p a r e n t 为根节点形成一个三级 四叉树，对应4 个c h i l d r e n 和1 6 个g r a n d c h i l d r e n ，各家族成员对应的子带如表2 2 。 因此，每个直流系数及其各频带对应系数形成一个8 8 的块( b l o c k ) ，如图2 5 阴 影部分形成单个块，其位置坐标对应关系如表2 3 ，比特平面编码正是以这样的块 为单位进行扫描处理的，所以本文也称之为扫描单元。 表2 2a c 家族成员对应的子带 族群系数族群f o 族群f l族群f 2 父系数肌3 l h 3h h 3 子系数 i - i l 2l h 2i - i h 2 孙系数i - i l ll h ih h i 1 0 c c s d s 压缩算法的研究和b l a c k f i n 解码实现 d c 系数 父系数 h1。系敝“ t 。w i 心k n 心孙系敲如 知系数父系数玮、，、c 、?心 刊喇小d 、弋 t b w h h，沁：心 、沁) 1：系数“ 1：系数( 夕乃 c 隆 杉 夕 e l 2hbh 刊- 系啦(孙系鼓(2 杉，夕 硷i x 夕 哆 多酗喷 夕，乡 狡聪袋 西 哆 乡瞄2还 坟 l“h h - 图2 5 变换后编码的数据组织 表2 3 块中系数坐标 家庭i 中的系数组系数坐标 双亲b ( ，c ) 孩子q( 2 r ，2 c ) ，( 2 r ，2 c + 1 ) ，( 2 r + 1 ，2 c ) ，( 2 r + l ，2 c + 1 ) 孙子e 。 ( 4 r 4 c ) ( 4 附1 ) ( 4 什l ，4 c + 1 ) ，( 4 忖l 时1 ) 孙子只。 ( 4 r ，4 c + 2 ) ，( 4 r , 4 e + 3 ) ，( 4 r + i , 4 c + 2 ) ，( 4 r + 1 , 4 c + 3 ) 孙子只2 ( 4 r + 2 , 4 c ) ，( 4 r + 2 , 4 c + 1 ) ，( 4 忖3 ，4 c ) ，( 4 r + 3 , 4 e + 1 ) 孙子珥3 ( 4 r + 2 ，4 e + 2 ) ，( 4 r + 2 ，4 c + 3 ) ，( 4 r + 3 , 4 e + 2 ) ，( 4 r + 3 ，4 c + 3 ) 小波变换后的图像首先被划分为若干个图像段s e g m e n t ，每个s e g m e n t 是s 个连续图像块b l o c k 组成的图像片段，其中1 6 i 时，需对t 编码 对于每段中连续的s 个量化d c 系数的第一个，不需要编码，仅作为参考值 直接写入编码后的数据流中而对于其余的s 1 个系数，则需要编码相邻系数的 差6 ： 表2 5f s 编码 需要编码的值f s 码字 ol 1 o l 20 0 l 2 ( n ) 1 0 0 0 o o o o l ( 共有2 ( n - k ) 1 个0 ) 瓦= c 二一0 。 为了便于编码，把吒转换为正整数屯： 式( 2 1 4 ) 第二章c c s d s 图像压缩算法 1 3 = 2 ( ) 假如o 0s 气； = 2 i 卜l ，假如一o o 6 2 so ； 式( 2 1 5 ) = 先+ l 瓦i ，其它 其中，吒= m i n ( c ：，一。一，一如) ，而= - 2 m ，= 2 - 1 一l 通过 上面的方法，就可以正确的得到量化的正系数吒。 在标准中编码的最小单位是群( g a g g l e ) 。通常每个群包含1 6 个瓦，而每段中 的第一个群仅包含1 5 个瓦值，这是由于第一个量化的d c 系数作为参考值而不 需要做差；其余每个群则包含1 6 个瓦值，但值s 不是1 6 的倍数时，则最后一个 群的大小为s 模1 6 的余数，即仅有j 个瓦值。 得到每段中所有的瓦后，需要对其进行编码。编码时以群为单位来进行。在 每个群中，通过参考表2 6 中的编码参数k 来选择采用的编码方式，一共包含l o 个选项，不编码也是选项之一。而其余9 个选项是简化的c c s d s 无损压缩标准p j 中的分裂采样的f s 编码。分裂采样是把n 位吒按照选择k 值分成两部分，一部 分是k 位，不编码，而另一部分为n k 位，进行f s 编码，如图2 7 所示。其中 m s b 是最高位，l s b 是最低位。f s 编码是一种简单的熵编码，它是把需要编码 值直接按照表2 5 所示转换为f s 编码。 表2 6 编码选项k 的取值与对应的码字 编码参数kn = 2 2 n 44 启发式获取方式：通过如表2 7 的计算公式来获取k 值，但这种方法并不能保 证每次取得的k 值都是使码流长度最短的。记= 瓦，j 为当前群中瓦的 数目。 ” 表2 7 编码选项标志符k 的选取规则 条件编码选项k 6 4 a 2 3 j 2 u n c o d e 2 0 7 j 1 2 8 ak = 0 ，2 i v q 1 2 8 a + 4 9 j七= 2 其它 ksn 一2 且满肋2 h 7s 1 2 8 a + 4 9 ， 通过上述方式对每个群中的瓯进行编码，得到最终码流。图2 8 为不编码选 项的情况。由于没有对吒编码，得到的编码长度是固定的。图2 9 为选择不同k 值的码流。第一个群的数据流包括4 部分，分别是编码参数k ，一个n 位参考值， 剩下的两部分是每个群中1 5 个剩余的瓦值。它通过选择的k 值分成两项，一项 是不编码的k 位，另一项是用f s 编码的n - k 位。这样得到的长度是不固定的。 在每段中，其它群与首群相比，除了不包括参考值外，结构类似。 编码选项n 位参考值1 5 个映射的差分量化系数6 i 丽奄辐麝 ( a ) 一段中的第一个群 编码选项其它映射的差分量化系数6 一 田审犯詹 ( b ) 其它群 图2 8 当选择不编码选项时的码流结构 第二章c c s d s 图像压缩算法 编码选项 第1 部分码字第2 部分码字 ( k ) n 位参考值 ( 1 5 个样值) ( k 1 5 位) 1r 百r 奋搀彦 ( a ) 一段中的第一个群 编码选项第l 部分码字第2 部分码字 ( k ) ( j 个样值)( k j 位) 1， 可蛮长摩 c o ) 其它群 图2 9 当选择编码选项时的码流结构 上面有效的编码了每个d c 系数的最前面的b i t d e p t h d c q 位，而对于 q b i t d e p t h a c 那部分，即d c 系数的q - b i t d e p t h a c 位，无需编码，只要对按位 平面的顺序紧跟着已经编码的数据流。即首先发送每段中的所有d c 系数的第口个 位平面，然后是g 1 个位平面，直到达到b i t d e p t h a c ，而d c 系数剩余的 b i t d e p t h a c 位与a c 系数一起处理。 2 2 3a c 系数位深度编码 交流系数比特位深度编码与d c 系数初始编码类似。根据不同的当前段a c 系数最大位深度b i t d e p t h a c 的值，交流系数位深度b i t d e p t h a c有如下几blcokm 种编码方式：当b i t d e p t h a c 等于0 时，说明当前段的b i t d e p t h a c 全为零， 就不需要对其进行编码，系数也不需要编码。当等b 于l c o k l m a c b i t d e p t h a c 时，说明 b i t d e p t h a c _ b l c o k m 等于0 或l ，可以只用l 比特来表示，直接将 b i t d e p t h a c b l c o l ( 1 1 l 的值写入编码码流中。当b i t d e p t h a c 不等于0 或l 时，采用 d c 系数初始编码的方法对b i t d e p t h a cb l c o k m 编码。 2 2 4a c 系数编码 一个段( s e g m e n t ) 包含s 个b l o c k 的系数【1 刀，各b l o c k 中直流系数量化余数和 其它的a c 系数进行位平面编码。位平面编码包含位平面扫描和熵编码两个部分。 对于量化余数和a c 系数组成的整个s e g m e n t ，首先判断量化余数是否高出直流 位深a c d e p t h 的部分，如果有，则按位顺次逐平面打入码流。之后，根据a c d e p t h ， 找到第一个可扫描平面( b = a c d e p t h 1 ) ，按照位平面由高到低，逐平面扫描及编码， 直至扫描到最后一个平面( 无损) 或者达到压缩控制( 有损) 要求。在个平面 中，扫描的顺序如图2 1 0 ： 1 6 c c s d s 压缩算法的研究和b i a c k f m 解码实现 d c c o f - r e m a i n d e r p a r e n t s c h i l d r e n g r a n d c h i l d r e n r e f i n e m e n t b l o c k 0b l o c k lb l o c ks 1 图2 1 0 一个位平面中的扫描顺序 1 转义字 位平面扫描形成了一系列的转义字，c c s d s 提供了码表，对这些转义字按照 查表法进行编码。 1 ) a c 系数字： p = p o ，p l ，p 2 ) 块中的p a r e n t s b = d o ，d l ，d 2 ) 一块中的c h i l d r e n 和g r a n d c h i l d r e n 日= g ，g f ) 2 ) a c 的类型： 块中家族i 的c h i l d r e n 和g r a n d c h i l d r e n t y p e t 6 ( x ) = 0 f l x i 】；其中- 0 ，l ，2 2 扫描算法 s t a g e 0 是对d c 系数中低于b i t d e p t h a c 位平面上的数据进行编码。若当前编 码位平面b 大于d c 系数量化因子q 或编码位平面b 小于d c 系数的加权值( 整 数d w t 的情况) ，在s t a g e 0 阶段不进行编码，否则在s t a g e 0 阶段把当前位平面未 编码的d c 系数位直接写入码流中。 在比特平面b ，b p e 用三个s t a g e 产生扫描字序列来更新块内所有的在前一个 比特平面为类型0 的a c 系数。 a ) s t a g el ( p a r e n t s ) t y p e 】，s i g n s b p 】( 分别表示为p 中系数x 第b 个比特位的信息和系数x 的符号 信息，符号位为l 表示负，o 表示正) b ) s t a g e 2 ( c h i l d r e n ) 1 ) t r a n 口； 2 ) t a l l d ；如果t r a i l a 0 且f m 。( b ) 一l 3 ) v p e s 6 c , 】和s i g n s d c , 】；对每个i 有k ( d ) o ，- 1 c ) s t a g e 3 ( g r a n d c h i l d r e n ) 如果知= 0 或者f 一( 占) = - 1 ，s t a g e 3 可以省掉，否则： 1 ) t r a n o ； 2 ) t r a n h , ；对每个i 有k ( q ) 0 ，一l 表2 8 最大长度和不可能的码字 码字 最大长度不可能出现的值 【用 3 t y p e s b c i 】 4 t y p e s b h i r 】 40 0 0 0 t r a n d 3 0 0 0 t r a n g 3 t r a n 。 4 0 0 0 0 3 ) t y p e s b h o 】和5 忉 】；对每个i 都有，眦( q ) 0 ，一1 ，对每个j 都有 1 8 c c s d s 压缩算法的研究和b l a c k f m 解码实现 f o ( 峨) 0 ，- 1 上述阶段产生的所有的转义字都是变长的，当【尸】，溉【c f 】， 【矾】，l r a n o ，t r a n g ，t r a n h , 的字长大于2 比特时，都应该被熵编码，用相 应的变长码字代替。符号不用进一步被编码( 因为a c 系数字正、负的概率大致 相等) ，转义字r r a n b 总是至多1 个比特，所以不需要编码。 对于某些码字来讲，并不是所有的可能值都会出现。如t r a n d 不可能为。0 0 0 ”， 因为这种情况可以由t r a n b 代表。表2 8 给出欲进行熵编码的码字的最大可能长度和 不能值。 表2 92 比特编码字整数映射表 编码字符号 0 00 o i2 1 0 l l l3 熵编码分两步进行：首先，将编码字查表映射为整数值，这些整数值称为符 - 号- ( s y m b 0 1 ) ；然后，将符号转化成变长码字表2 9 ，2 1 0 和2 i1 分别给出了将2 比特、3 比特和4 比特长度的编码字转化为符号的映射表。 表2 1 02 比特编码字整数映射表 编码 符号【毋0 , 烨s d c , 】， 符号 字 t y p e s b h , 】，l r a n a ，t r a n n 。)t r a n d o o ol 0 0 l43 0 1 0 oo 0 l l 54 1 0 02 l l o l 6 5 l l o 3 2 l l l 7 6 映射将产生一个按频率降序排列的符号值序列( 即出现最为频繁的字将被映 射为0 值，接下次出现频繁的被映射为1 ) 这将使高效编码成为可能，这是因为 第二章c c s d s 图像压缩算法 1 9 码长随着频率的降低而增加。关于各个码字出现频率高低的结论是依据多幅测试 图像实验的统计结果得到的。可预知，在下面的熵编码过程中，新的码字长度会 随着“符号”的增大而增加。 表2 1 l3 比特编码字整数映射表 编码 符号 符号 字 咖虹e 】，( 钟枷j 【风】，肋) 0 0 0 0 l o 0 0 0 l1 l 0 0 1 0 2 3 o o l l 6 6 0 1 0 032 0 1 0 15 5 o l l o 9 9 0 1 ll 1 2 1 l l 0 0 0oo 1 0 0 l88 l o l 077 1 0 ll1 31 2 l 1 0 04 4 l l o l1 41 3 1 1 l ol ll l ll l l1 51 4 表2 1 22 比特编码字的可变编码选项 符号编码选项0编码选项1 ( u n c o d e ) o l0 0 10 l o l 2o o l1 0 3 0 0 0 1 1 表2 1 2 ，2 1 3 和2 1 4 分别给出了将2 比特、3 比特和4 比特长度编码字对应 的符号转化为变长码的映射表。当每个映射表有多个编码选项时，需要选择一个 c c s d s 压缩算法的研究和b l a c k f m 解码实现 选项使编码长度最短。这个选择的过程有点类似与直流系数编码中确定选项标识 符k 的方法。它是以一个“群”为单位，选择一个选项使得变长码编码长度最短。 对于一个群来说这个选项在s t a g e l - s t a g e 3 中是同一个值，如表2 1 5 所示。 表2 1 33 比特编码字的可变编码选项 符号 编码选项0编码选项1 编码选项3 ( u n e o d e ) 0l1 00 0 0 l0 1 l ll 20 0 10 1 0 0 1 0 3o o o o o0 1 1o l l 40 0 0 0 10 0 l o1 0 0 5 0 0 0 1 00 0 l l1 0 l 6 o o l l 00 0 0 01 1 0 70 0 0 1 l l 0 0 0 ll l l 表2 1 44 比特编码字的可变编码选项 符号编码选项0编码选项l 编码选项2 编码选项3 ( u n c o d e d ) 0l1