（通信与信息系统专业论文）基于sse技术的ccsds译码复杂度的研究与改进.pdf

摘要 随着人们对图像压缩算法的要求越来越高，实时性和复杂度成为衡量算法好 坏的重要标准。i n t e l 所发布的p e n t i u mi i i 以上的处理器增加了一些新的指令集： s t r e a m i n gs i m de x t e n s i o n s ( 单指令多数据流扩展指令集，简称s s e ) 。这些新指令 集极大地提升了计算机在图形、动画、音频和视频等方面的性能。同时增加了8 个1 2 8 位寄存器( x m m 0 x m m 7 ) ，能同时处理4 个单精度浮点变量，大大提升浮点 计算效率。空间数据系统咨询委员会( c c s d s ) 于2 0 0 5 年1 1 月发布了一套用于空 间领域的图像压缩算法标准，其基本单元包括离散小波变换( d w t ) 和位平面编码 器( b p e ) ，其中小波变换使用了9 7 小波。该算法主要用于空间领域，比如在航天 器上，这对算法的实时性有着严格的要求。因此，对c c s d s 算法复杂度的研究 十分重要，简单、快速且内存占用率小的算法将越来越满足空间领域的需求。 本文详细介绍了c c s d s 算法的基本原理以及s s e 技术的指令集和运算的基 本特点，并使用i n t e l v t u n e t mp e r f o r m a n c ea n a l y z e r 软件分析研究程序译码过程 中的时间复杂度，从中得出浮点运算较多的离散小波反变换( i d w t ) 是整个程序中 占用时间最多的模块。因此，本文结合s s e 指令系统的特点，从小波反变换作为 切入点，提出基于s s e 指令的c c s d s 译码算法优化方案，并予以实现，降低了 译码时间复杂度。经性能测试证明，在不改变译码图像质量的前提下，小波反变 换模块译码可节约时间高达8 6 以上，而整个c c s d s 译码可节约时间高达7 5 以e 。 关键词：图像压缩s s ec c s d s 时间复杂度小波反变换 a b s t r a c t a st h ed e m a n df o rb e t t e ri m a g ec o m p r e s s i o na l g o r i t h mr i s e s ，l o wd e l a ya n d c o m p l e x i t yh a v eb e c o m ei m p o r t a n tm e a s u r e m e n t sf o ra l la l g o r i t h m p e n t i u mi i ia n d e v e nn e w e r p r o c e s s o r , r e l e a s e db yi n t e l a d ds o m en e wi n s t r u c t i o n s ：s t r e a m i n gs i m d e x t e n s i o n s ( as i n g l ei n s t r u c t i o n , m u l t i p l ed a t as t r e a m se x t e n d e di n s t r u c t i o ns e t , c a l l e ds s e ) n l en e wi n s t r u c t i o ns e tg r e a t l yi m p r o v e st h ep e r f o r m a n c eo fg r a p h i c s ， a n i m a t i o n ，a u d i oa n dv i d e o a tt h es a m et i m e ，e i g h t12 8 一b i tr e g i s t e r s ( x m m 0 x m m 7 ) a r ea l s oa d d e d ，w h i c hc a ns i m u l t a n e o u s l yh a n d l ef o u rs i n g l e p r e c i s i o nf l o a t i n g - p o i n t v a r i a b l e st h u sg r e a t l ye n h a n c et h ee f f i c i e n c yo ff l o a t i n g - p o i n tc a l c u l a t i o n s n e 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 ( c c s d s ) i nn o v e m b e r2 0 0 5r e l e a s e d as e to fi m a g ec o m p r e s s i o na l g o r i t h ms t a n d a r du s e di nt h ef i e l do fs p a c e ，t h eb a s i cu n i t o fw h i c hi n c l u d e sd i s c r e t ew a v e l e tt r a n s f o t i n ( d w t la n db i t - p l a n ee n c o d e r ( b p e ) 9 7w a v e l e ti su s e di nd w t t h ea l g o r i t h mi sm a i n l yu s e df o rs p a c e ，f o re x a m p l e ，i n t h es p a c e c r a f t ，s oi th a ss t r i c tr e q u i r e m e n to nr e a l - t i m e t h e r e f o r e ，r e s e a r c ho nt h e c o m p l e x i t yo fc c s d sa l g o r i t h mi sv e r yi m p o r t a n t as i m p l e ，f a s ta n ds m a l lm e m o r y u s a g ea l g o r i t h mw i l li n c r e a s i n g l ym e e tt h en e e d so f t h es p a c e n l i sp a p e rp r e s e n t st h et h e o r yo fc c s d sa l g o r i t h m s s et e c h n o l o g yi n s t r u c t i o n s e ta n dt h er u l e so fc a l c u l a t i o n t h e ni n t e l 固v t l m e t mp e r f o r m a n c ea n a l y z e ri su s e dt o s t u d yt h et i m ec o m p l e x i t yo ft h ep r o c e s so fd e c o d i n g i ti sf o u n dt h a ti n v e r s ed i s c r e t e w a v e l e tt r a n s f o r m ( i d w t ) i n c l u d i n gm o r ef l o a t i n g - p o i n tc a l c u l a t i o n si st h em o d u l e t h a tt a k e st h em o s tt i m e o ft h ee n t i r ep r o c e s s a sar e s u l t ，a c c o r d i n gt ot h e c h a r a c t e r i s t i c so fs s ei n s t r u c t i o ns e ta n di df 住c c s d sd e c o d i n ga l g o r i t h m o p t i m i z a t i o ns o l u t i o nb a s e do nt h es s ei n s t r u c t i o ni sp r o p o s e da n dr e a l i z e di nt h i s p a p e r , w h i c hr e d u c e st h et i m ec o m p l e x i t yo fd e c o d i n g i ti sp r o v e nb yt h ep e r f o r m a n c e t e s tt h a ti d w td e c o d i n gm o d u l ec a l ls a v eu pt o8 6 o ft h et i m e ，a n dt h ee n t i r e c c s d sd e c o d i n gp r o c e s ss a v e st i m eu pt o7 5 w i t h o u tc h a n g i n gt h ed e c o d e dq u a l i t y o ft h ei m a g e k e y w o r d ：i m a g ec o m p r e s s i o n s s ec c s d st i m ec o m p l e x i t yi d w t 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何 贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 尊7 7 l 玺一 日期：笙! 竺：! ：丝 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。 ( 保密的 论文在解密后遵守此规定) 本人签名；酆 导师签名： 日期：丝! ：? ：丝 第一章绪论 第一章绪论 1 1 引言 随着计算机技术、现代通信技术、微电子技术、网络技术和信息处理技术的 发展，在人类社会进入信息化时代的今天，图像信息的处理、存储和传输在社会 生活领域和国防领域中的作用越来越突出，人们对接受图像信息的要求也越来越 迫切。已经可以断言，图像通信将是通信事业发展中面临的最大挑战，也是未来 通信领域的市场热点之所在。 如今数码相机、摄像手机等这一类具有拍照功能的数字摄影器材大规模地进 入人们的日常生活。以数字音视频为主要内容的多媒体技术在远程教育、远程医 疗、图像监控以及卫星资源普查等领域发挥着越来越重要的作用。电视信号正在 从模拟向数字过渡，由电缆传输向网络传输过渡，数字化的浪潮正在彻底改变我 们的生活。数字图像和视频信号有着模拟信号无法比拟的优点i l 】： ( 1 ) 抗干扰能力强，无噪声积累。由于在传输的中继节点可以对数字信号进行 再生，因而能够确保其后继节点的性能不受前面节点的噪声的影响。 ( 2 ) 便于存储、处理和交换。由于采用了数字0 和1 来表示信息，使得我们可 以用数学运算对信号进行复杂的处理，从而更加有效的提取所需信息，也 方便了存储和交换。 ( 3 ) 便于集成化，微型化。大规模集成电路的飞速发展，使得我们可以在微处 理器甚至是专用集成电路上实现各种处理算法，而不在需要复杂而笨重的 模拟器件。 ( 4 ) 便于加密处理。通过对数字信号进行加密，可以使未授权的用户无法获取 数字信号中所含有的信息。 然而，由于图像数字化以后的数据容量庞大，在传输、存储以及各种处理加 工过程中都遇到了许多难以克服的困难。以p a l 制( 2 5 帧秒) 的视频信息为例， 如果每帧具有中等分辨率( 6 4 0 4 8 0 个像素点) 、真彩色( 每像素用2 4 位信息来 描述) 的图像，则每帧数据量为7 3 7 兆位，并且要求传输速率大于1 8 4 兆位秒。 这种高比特率、大容量的要求，使得现在以至将来很长一段时间内的信道带宽和 存储容量都捉襟见肘。因而，高效图像数据压缩技术成为信息时代的迫切要求。 再者，算法复杂度又是衡量算法质量的一个重要标准，所以，对算法复杂度 的研究成为高效压缩技术开发的一个关键问题。算法复杂度主要包括时间复杂度 和空间复杂度，一个占存储空间小、运行时间短、其它性能也好的算法是很难做 到的。要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间 2基于s s e 技术的c c s d s 译码复杂度的研究与改进 可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：若该程序使 用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快 速的算法；若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要 考虑如何节省空间。 1 2 图像压缩编码技术的研究进展 图像压缩编码【2 】的目的是在保证图像质量的前提下，用尽可能少的比特数来 表示数字图像中所包含的信息。从信息论的角度来讲，图像压缩编码属于“信源编 码”。图像信息之所以能够压缩，在于原始图像中存在着大量的信息冗余，如时间 冗余、空间冗余、信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余 等等。图像编码技术是在信道和存储容量有限的条件下，解决由于图像数据量庞 大带来的存储和传输困难的主要措施，在军事和民用的许多领域中都具有重要的 研究价值。 迄今为止，已经研究出大量的图像编码方法。在图像编码技术研究的开始， 首先发展起来的是基于s h a n n o n 信息论的熵编码技术。熵编码技术是一种纯粹基 于信息的统计概率模型的无失真编码技术，其编码下限是为图像的信源熵。它既 可用于文本数据的编码，又可用于语音和图像的编码。这类编码技术的压缩效率 有限，压缩比徘徊在1 5 - 3 之间，其代表方法包括h u f f m a n 编码、游长编码、算 术编码和l e m p e l z i v 字典编码。 从2 0 世纪8 0 年代末到9 0 年代中期，大量崭新的数学理论成果被引入图像编 码领域，为图像编码技术的发展注入了巨大活力。这些数学工具是：小波理论、 分形几何理论、神经网络理论和计算机视觉理论。 小波理论在2 0 世纪9 0 年代受到众多领域科技工作者的高度重视。作为数学 和工程应用等学科共同研究的结晶，小波变换在信号分析、图像处理1 3 j 、地震勘 探、量子物理和非线性科学等诸多领域得到广泛应用。小波理论为各种信号及图 像处理方法提供了一种统一的分析框架，成为当前信号与图像处理等众多领域的 研究热点。 在图像编码领域，由于具有描述非平稳信号的独特优点，小波变换可将图像 信号分解成不同空间分辨率、不同频率特征和方向性特征的子图像信号，这便于 在失真编码中综合考虑人的视觉特性，同时也利于图像的逐渐浮现传输。另外， 它作用于图像的整体，在有效去除图像的全局相关性的同时，使量化误差分散到 整个图像中，避免了j p e g 方法带来的“马赛克”方块效应。所有的这些优势使 得它成为一种极有前途的编码方法，它所具备的高压缩潜力也正不断为各国学者 的研究成果所证实。近年来涌现出来的一些基于小波变换的压缩算法，结合特定 第一章绪论 的量化和编码方法，普遍能够在高压缩比下获得比j p e g 更为理想的压缩性能。 其中最为突出的是s h a p i r o 提出的内嵌零树( e z w ) 吲编码方法、s a i d 与p e a r l m a n 提出的基于多级树集合分裂( s p i h t ) 1 5 】编码方法以及由t a u b m a n 提出的e b c o t l 6 编码方法。e b c o t 编码方法已经成为最新静止图像压缩国际标准j p e g 2 0 0 0 7 】【8 】 的标准量化方法。 1 3c c s d s 图像压缩标准 空间数据系统咨询委员会( c c s d s ) 是多国空间组织组成的国际性标准化组 织。自1 9 8 2 年成立以来一直致力于数据系统标准化工作，负责开发和采纳适合于 通信和数据处理系统的各种通信协议、通用数据格式及数据处理规范等等，以支 持空间研究与应用，加强各空间局的相互合作和互操作性。c c s d s 的研究成果以 不同颜色封皮建议书的形式发表。 2 0 0 5 年9 月c c s d s 正式公布了空间图像数据压缩建议的蓝皮书，其中详细 描述了应用于有效载荷数据( 遥感图像数据) 的压缩标准及算法，并阐述了此算 法与j p e g 2 0 0 0 算法比较的四点不同： ( 1 ) 该标准推荐的压缩算法主要针对应用于高速的太空船等设备； ( 2 ) 该压缩算法成功的完成了航天软件所注重的性能与复杂度的转换； ( 3 ) 算法的低复杂度利于快速及低功耗的硬件实现； ( 4 ) 可选择的有限集保证了算法的有效执行而不需要更深的算法知识。 标准中推荐的压缩技术既可以用于无损压缩也可以用于有损压缩，且具有很低的 算法复杂度。最初该压缩技术并不是为图像压缩而定制，但由于其具有如此多的 优点而被c c s d s 所采用，最终成为新的应用于空间遥感图像压缩的标准。 1 4 本文研究的主要内容及章节安排 本文简要介绍了c c s d s 空间数据压缩标准，并在此基础上重点研究了 c c s d s 算法程序的译码复杂度。本文作者主要参与并负责c c s d s 译码复杂度研 究工作，通过对算法进行测试定位，分析算法中消耗资源较多、运行效率较低的 模块，并在原有算法结构和编码流程的基础上提出基于s s e 指令系统的c c s d s 算法优化方案，并予以实现，从而提高算法效率。并且比较优化前后所消耗的时 间，达到较好的优化效果。 本文的章节安排如下： 第l 章：绪论 首先简要回顾了图像压缩编码技术的历史、现状与发展趋势，并给出了本文 的研究内容。 4 基于s s e 技术的c c s d s 译码复杂度的研究与改进 第2 章：c c s d s 图像编码算法标准 介绍了c c s d s 静止图像压缩标准，阐述了该标准的核心算法及基本结构。 第3 章：s s e 技术 介绍了s s e 技术的概念、发展历史、s s e 指令集及其主要特点。 第4 章：c c s d s 译码复杂度的研究与改进 通过测试分析，得出算法的瓶颈，并对在算法中的小波反变换采用s s e 技术进 行可行性分析，介绍内嵌s s e 指令的算法结构及流程，并进行优化前后的性能分析。 第5 章：结束语 对全文进行了回顾和总结，并对s s e 技术在c c s d s 图像压缩算法中的应用提出 了进一步建议与展望。 第二章c c s d s 图像编码算法标准 第二章c c s d s 图像编码算法标准 2 1c c s d s 推荐图像压缩算法标准概述 c c s d s 于2 0 0 5 年1 1 月发布了一篇推荐标准：( ( i m a g ed a t ac o m p r e s s i o n r e c o m m e n d a t i o nf o rs p a c ed a t as y s t e ms t a n d a r d s ) ) 【9 】，该标准提出了一种基于小波 变换的二维数字图像压缩算法( 以下简称c c s d s 算法) ，并于2 0 0 7 年6 月发布 了关于c c s d s 图像压缩算法的技术报告：( ( i m a g ed a t ac o m p r e s s i o n r e p o r t c o n c e r n i n gs p a c ed a t as y s t e ms t a n d a r d s ) ) 1 0 】，该算法应用于空间领域，例如宇宙 飞船上的图像压缩，为了降低飞船的功率，需要权衡图像压缩性能与算法复杂度 从而能够通过低功耗的硬件快速实现压缩。 作为数据压缩的一种，c c s d s 图像压缩算法具备如下基本特点： ( 1 ) 减少传输带宽； ( 2 ) 降低存储和缓存需求； ( 3 ) 在给定传输速率下减少传输时间。 同时，作为应用于特殊领域的图像压缩算法，c c s d s 算法还具有如下独有特 点： ( 1 ) 该算法被明确指定用于航天器上； ( 2 ) 根据航天应用的侧重点不同，可以从算法的性能和复杂性之间均衡； ( 3 ) 该算法复杂性比较低，有利于快速和低功耗硬件实现； ( 4 ) 算法的选项很少，在实际应用时不需要很强的背景知识。 c c s d s 推荐算法的基本系统结构如图2 1 所示，主要包括两大模块，编码过 程首先对原始图像数据进行离散小波变换，然后小波系数通过位平面编码器 ( b i t p l a n ee n c o d e r ) 进行编码并组织成符合格式的输出码流。解码过程与编码过 程完全对称。 嘲l i 阻i d i s c r e t e l i w a v e l e t 、 b i t p i a n e k ， 。c 氮 l t r a n s f o r me i 删e r l d a u i 图2 1c c s d s 算法基本系统结构 2 2 离散小波变换d w t c c s d s 算法推荐使用3 级9 7 小波变换对图像进行处理。对于三级二维离散 6 基于s s e 技术的c c s d s 译码复杂度的研究与改进 小波变换【1 1 1 ，每次分解产生一个低频子图l l 和水平子图l h 、垂直子图h l 、对 角子图h h 三个高频子图。下一级小波变换是在前级产生的低频子图l l 的基础 上进行的，如此重复三次，可以得到如下1 0 个子带： 图2 2 三级二维小波生成子带图 离散小波变换具体实现方法是，通过一组分解滤波器h 和g 对信号进行滤波， h 是低通滤波器，g 是高通滤波器，然后对输出结果进行下二采样来实现正交小 波分解，分解的结果是长度减半的两个部分，一个是经低通滤波器产生原始信号 的平滑部分，另一个是经高通信号的原始信号的细节部分，如图2 3 。重构时使用 一组合成滤波器h 和雪对小波分解的结果滤波，再进行上二采样来生成重构信号， 如图2 4 。多级小波变换可以通过级联的方式进行，每一级的小波变换都是在前一 级分解产生的低频分量上的继续，合成是分解的逆运算。 图2 3 二维离散小波分解 列滤波 行滤波 图 图 图 图 图2 4 二维离散小波重构 第二章c c s d s 图像编码算法标准 7 1 9 9 4 年w i ms w e l d e n s 等人提出了提升小波 1 2 - 1 5 】的概念，它是一种不依靠傅 立叶变换构造小波的新方法。通过提升构造小波包括三个步骤。首先是“l a z y ”小 波变换，即把数据分为两个子集，偶数集合和奇数集合。第二步是对偶提升，即 用偶数集合来预测奇数集合，把产生的误差作为高通小波系数。最后是原始提升， 即用这些小波系数来更新偶数集合作为低通尺度函数系数。图2 5 所示为这三个 步骤的结构图。另外逆变换可从正变换快速得出，仅需把加号变为减号、数据流 反向即可。提升结构与传统方法的主要区别就是它不依赖傅立叶变换。这种提升 步骤能用来构造第二代小波，即不必从一个母函数经过平移和伸缩来得到小波函 数。 i d a u b e c h i e s 和w s w e l d e n s 利用e u c l i d e a n 算法证明了任意对偶f i r 滤波器 组( h ( z ) ，甙z ) ) 能分解为有限的提升和对偶提升的因子之乘积，即在l a z y 小波分 解后，交替使用原始提升和对偶提升来改进小波特性。 x 图2 5 预测和更新提升步骤结构图 假设x 是原始信号，。是第f 层原始提升的低通分量， 的高通分量，则提升小波变换实现如下： l a z y 小波：s o 。= x 2 。，d o 。= x 2 州 对偶提升：一，。= z - l 。一b ，。s 却一七 七 原始提升：，。= 墨1 。+ u t ，t 谚，。“ d s z 。是第i 层对偶提升 ( 2 - 1 ) ( 2 2 ) ( 2 3 ) 二维提升小波变换与二维m a l l a t 1 6 ”】分解一样，也是一维小波变换在水平和 垂直方向上的二维扩展。但提升小波比m a l l a t 更适合算法的并行实现，同时可节 省一半的存储器和一半的计算量。图2 6 为二维提升小波变换的实现方法： 8 基于s s e 技术的c c s d s 译码复杂度的研究与改进 原 列滤波 l l 子图 l h 子图 甩子图 删子图 图2 6 二维离散小波的提升实现 对于给定长度为2 n 的一维序列薯，其经过一维滤波器后生成两个长度为的 序列：低频序列e 和高频序列口。其浮点型9 7 小波变换公式为： 43 q = 吃恐m ；q = g x 2 川+ 。；j = o ，1 ，一， ( 2 4 ) n = - 4* = - - 3 其中变换系数如表2 1 ： 表2 19 7 滤波器变换系数 变换系数 低通系数乃i 高通系数吕 1 00 8 5 2 6 9 8 6 7 9 0 0 9- 0 7 8 8 4 8 5 616 4 0 6 士l0 37 7 4 0 2 8 5 5 6130 418 0 9 2 2 7 3 2 2 2 士2- 0 11 0 6 2 4 4 0 4 4 1 8 0 0 4 0 6 8 9 417 6 0 9 士30 0 2 3 8 4 9 4 6 5 0 2 0 一0 0 6 4 5 3 8 8 8 2 6 2 9 士4 0 0 37 8 2 8 4 5 5 5 0 7 浮点型9 7 小坡反变换公式为： rl1 i 恐，= q e c j 一p 2 川9 + 。 ”2 m - - 2 ， j = o ，l ，一，( 2 5 ) l x 2 川= q 2 , , - 1 q + 。+ 仍。哆+ 。 l? l m - - n = - - 2 其中反变换系数如表2 2 ： 表2 29 7 滤波器反变换系数 变换系数 低通系数q 高通系数n l 0 0 7 8 8 4 8 5 616 4 0 60 8 5 2 6 9 8 6 7 9 0 0 9 第二章c c s d s 图像编码算法标准9 士10 418 0 9 2 2 7 3 2 2 20 3 7 7 4 0 2 8 5 5 6 1 3 士20 0 4 0 6 8 9 417 6 0 90 1 1 0 6 2 4 4 0 4 4 18 士3o 0 6 4 5 38 8 8 2 6 2 90 0 2 3 8 4 9 4 6 5 0 2 0 士4- 0 0 3 7 8 2 8 4 5 5 5 0 7 整型9 7 小波变换公式为： d o = 五一1 杀( x o + x 2 ) 一去( 屯+ 毛) + j 1l q = 屯，门一i 景( x 2 j + x 2 y + 2 ) 一去( x 2 j _ 2 + x 2 j + 4 ) + 三1i 加，“，- 3 d n 一：= 屯一，一l 羔( 屯一+ j c 2 一：) 一去( 屯“+ 屯一：) + 三1l 嘞r b r 产1 一三i 嘞，l 杀( x 2 _ 4 + x 2 n _ 2 ) 一( x 2 n _ 6 - i - x 2 n _ 2 k ii c o = x o - - i 一了1 9 0 + j i c j = x 2 j - - l 一半+ 引1 舫川，删 整型9 7 小波反变换公式为： = c o + 愕+ 刭 铲q + 卜半+ 纠州山川 ( 2 6 ) 二j i i 。三1 p 【。9 ，t否。叉，一：jdj+l9(x2j+x：21 工，+ 。，三j a r ：= ，l ，3 c 2 - 7 ， 恐，= ) 一话( 而，一：+ 吃p 。) + 三i 扣r = 1 ，一3 而心= 巩一：+ l 杀c x 2 n _ 4 s t x 2 n _ 2 ，一去c 恐心+ 而心，+ 纠 。= 巩q + b r 知4 + _ 1 j 2 3 1 位平面编码概述 2 3 位平面编码 位平面编码( b p e ) 过程以一组6 4 个系数的方式处理小波系数，这6 4 个系 1 0 基于s s e 技术的c c s d s 译码复杂度的研究与改进 数称为一个块( b l o c k ) 。图2 7 中深颜色的区域给出了我们刚刚定义的图像中一个 块的说明。 p a r e n t p o 毒- ：二：，嘲n d 咖d 嘞强： l 囹：目。 ：b 萎 圜垂蓦 h 岛 避o；旨 妒峨p 2 ? 、：- ；砭 、- 心一 ；。c 1x 。， ：。4 h h z ：i ：吼、：x 曼，酒象量兰、堇蹲囊； 。一、一，r ：一；：，t 赫毛：z ：州；： 图2 7 小波变换后的图像 一个块的系数信息同该块信息一同进行位平面编码。从图2 7 中可以看出， 一个块由一个厶子带的单一系数，即d c 系数，和6 3 个a c 系数组成。一个块 的a c 系数被分为3 个簇( f a m i l i e s ) ，f o 、f 、e 。从图3 4 中我们可以看出系 数的单块和簇结构。每个簇f 都有一个父( p a r e n t ) 系数b ，一个由4 个子( c h i l d r e n ) 系数组成的集合c ，和一个由1 6 个孙( g r a n d c h i l d r e n ) 系数组成的集合q 。 每个块的d c 系数是作为厶子带中的单一系数出现的。d c 系数的参数也决 定了该块中其他系数的相应参数。从图2 7 中我们也可以看出各系数之间的紧密 关系。块由位平面编码器以光栅顺序连续扫描，其顺序与它们出现在三厶中的相 应顺序一致：一行接一行，每行从左到右的进行扫描。 一个段( s e g m e n t ) 定义为一组连续的s 个块( b l o c k ) 。d w t 系数的编码是 逐段进行的，并且各个段之间的编码是相互独立的。s 的范围为：1 6 s 2 2 0 ， 而对于最后一个段，s 的范围为：1 s 2 2 0 。在具体实现时，是将一幅图像作为 一个段来处理的。 段被进一步分为g a g g l e s ，每个g a g g l e 由1 6 个块( b l o c k ) 组成，但当段中块 数不是1 6 的整数倍时，最后一个g a g g l e 由s 模1 6 个块组成。 b i t d e p t h d c 定义为一个段中用来表示d c 系数所需的最大比特数，公式如 下： 第二章c c s d s 图像编码算法标准 斟l + f l o g ：2 ( 1 c 。坞1 , ) ，fc = b i t d e p t h a c 时，将对附加的q b i t d e p t h a c 比特平面进行编码，其 中的g 值我们将在下面定义： q = m a x ( q ，b i t s h i f i ( l l a ) )( 2 1 1 ) 从q 值的定义我们可以看出，g 值代表了d c 量化值中不编码的非重要的比 特平面个数。g 值要选取的合适才能保证d c 系数和a c 系数都能得到最大限度 的编码。d c 系数编码同a c 块深度熵编码所用技术相同，将在下一章节中给予 说明。 2 3 4a c 块深度熵编码 d c 系数及a c 块深度熵编码采用的是c c s d s 无损信源编码器。无损信源编 码器由两个分立的功能部分组成：预处理器和自适应熵编码器，参见图2 9 。参考 c c s d s 无损压缩算法，预处理器选择一阶单位延迟预测器；熵编码选择分裂编码 图2 9 无损图像数据的编码器结构 ( 一) 预处理器 预处理器的功能是将原始输入数据转换为能够进行更有效熵编码的数据，而 且预处理器的去相关性能是决定编码效率的重要环节之一。为保证压缩是无损的， 预处理必须是可逆的。为了得到有效的压缩，我们在预处理阶段将对原始数据做 一个变换，以使概率大的码字比概率小的码字短，这就是映射过程。如果有几种 第二章c c s d s 图像编码算法标准 1 3 预处理方法，我们应当选取一种平均码字长度最短的方法。 本文算法设计的预处理器由差分模块和映射模块组成。差分模块进行d p c m 预测，其思想是将输入图像数据进行单位延迟，将延迟得到的数据与其本身做差 得到残差值来优选预测值。当像素之间的相关性较强时，该预测器非常有效，如 图2 1 0 为线性一阶单位延迟预测器结构。映射变换公式如式( 2 1 2 ) 所示，其目的 是将差分得到的残差值映射成便于熵编码的数据。 图2 1o 线性一阶单位延迟预测器( d p c m ) 正= 2 f 2 | ，| _ 1 谚+ l ，1 0 a ，包 一谚a ，0 ， 其它 其中9 = m i n ( 是一。，。一毫)( 2 - 1 2 ) ( 二) 自适应熵编码器 自适应熵编码器是由一系列变长编码器组成的集合。对于每一个块单元自适 应选定一种编码效率最高的编码器，然后将其编码结果与编码器的标识符一起传 输来完成块单元的熵编码。由于每一个块单元均可自适应地选择最有效的熵编码 方法，所以熵编码算法能充分适应遥感图像信源统计特性分布的变化，进而提高 编码的效率。自适应熵编码器的编码模式包括以下四种：基本序列编码，分裂样 本编码，低熵值编码和无压缩编码。 从图像编码理论上说，比特平面越高，其所含信息的重要性越高，反映在实 际编码中，比特平面高的数据较比特平面低的数据失真要大。因此，本文算法将 图像数据按比特平面重要性划分为两个部分，其中较高的k 个比特平面为重要比 特平面，较低的- k 个比特平面为非重要比特平面。对于重要性比特平面进行可 变长编码，对于非重要性比特平面则直接输出，具体见图2 1 1 。 1 4 基于s s e 技术的c c s d s 译码复杂度的研究与改进 2 3 5a c 系数位平面编码 图2 i l 无损熵编码框图 在c c s d s 的标准中，对于编码统称为b p e ( b i t p l a n ee n c o d e r ) ，即位平面 编码。但实际上，只有a c 系数的编码是真正按照位平面进行编码的，它也是该 编码器最核心的部分，下面就对此编码模块进行详细说明。 c c s d s 标准中对位平面编码定义了5 个s t a g e ：即：s t a g e 0 - - s t a g e 4 。其中 s t a g e 0 用于d c 量化编码，s t a g e l s t a g e 4 用于a c 编码。具体为：s t a g e l 对小波 系数父节点的重要性进行编码，s t a g e 2 对子节点的重要性进行编码，s t a g e 3 对孙 节点的重要性进行编码，s t a g e 4 对非重要的系数进行量化编码。在具体实现中， 我们是按照位平面逐码块进行编码的，编码顺序如图2 1 2 所示。 图2 1 2 位平面编码单元的编码结构及顺序 第二章c c s d s 图像编码算法标准 下面将举例说明在位平面b 的一个码块的具体编码步骤： s t a g e 0 ：对于一个块来说最多由一个比特组成，这个比特是d c 系数二进制补码 表示的第b 曲个重要比特。但是当b 满足b q 时，说明这个比特的值从 d c 系数己编码的信息中可以获得，即在s t a g e 0 没有比特要编码，或者 当b b i t s h 驴( l & ) 时，s t a g e 0 也是空的。 在余下的s t a g e l将对a c 系数进行编码。在一个比特平面里，a c 系数将 在哪个s t a g e 编码取决于在该比特平面a c 系数的类型，其类型的定义如下：其 中x 代表a c 系数， ( x ) 表示在比特平面b ，a c 系数x 的类型。 厶( x ) = 0 ，矿ixi 2 6 ，说明x 在这个比特平面没有被选择； ，。f x ) = 1 ，矿2 6qxi 2 1 ，说明x 在这个比特平面被选择了； t b ( x ) = 2 ，矿2 6 + 1 司xl ，说明x 在前面的比特平面已经被选择过了； 乇( x ) = 一1 ，矿b b i t s h 驴( r ) ，说明由于子带量化x 在这个比特平面必须是 o ，r 代表包含x 的子带。 当类型为0 或者l 时，在s t a g e l 3 进行编码；当类型为2 时，在s t a g e 4 进行 编码；当类型为1 时，不被编码； s t a g e l 3 ：b p e 编码比特平面b ，也就是每个a c 系数x 的第b 个比特被编码，即： t h ( x ) = 1 ；乙+ l ( x ) = 0 。父系数的第b 个比特在s t a g e l 被编码；子系数在 s t a g e 2 ；孙系数在s t a g e 3 。在， ( x ) = 1 时，也将对每个系数的符号标志 比特进行编码。s t a g e l 3 的编码包括两个部分：一是定义一列变长二进 制w o r d s ，它完全描述了在这些s t a g e s 中将被编码的比特；二是对这些 w o r d s 进一步进行熵编码。 s t a g e 4 ：该s t a g e 由t b ( x ) = 2 的a c 系数的第b 个比特组成。这些比特被包含在输 出数据比特流中，但是不进行压缩。 2 4 本章小结 本章主要介绍了c c s d s 图像压缩算法标准的关键技术流程。c c s d s 算法主 要包括两个大模块，即离散小波变换( d w t ) 和位平面编码( b p e ) 。其中，离散小波 变换主要分析了9 7 小波变换提升结构的实现及其优点；位平面编码主要介绍了 其定义、d c 系数编码、a c 块深度熵编码和a c 系数编码。这一章为后续章节作 了理论铺垫。 第三章s s e 技术 1 7 第三章s s e 技术 3 1 概述 19 9 9 年2 月，i n t e l 发布了最新款处理器p e n t i u mh i 处理器，和以往的新处理器推 出一样，速度的提高是最主要的性能改善。i n t e l 在发布她的新处理器时一贯遵循着 摩尔定律，即每过1 8 个月处理器的速度将提高一倍( t h ep r o c e s s o rs p e e dd o u b l e s e v e r y1 8m o n t h s ) ，但是p e n t i u mi i i 处理器的并没有比p e m i u mi i 的速度提高一倍，在 p e n t i u mi i 和p e m i u mi ix e o n 处理器运行在3 3 3 m h z - 4 0 0 m h z 时，p e n t i u mi i i 也只不 过运行在4 5 0 m h z - 5 5 0 m h z 而已，处理器的速度并没有多大的提高，但是性能的提 升却是很明显的。 从本质上说，p e n t i u mi i i 处理器只不过是一个运行在更高速度的p e m i u mi i 处理 器，另外再增加了一些新的指令集：s t r e a m i n gs i m de x t e n s i o n s ( 单指令多数据流扩 展指令集，或者称为s s e ) 。这些新指令集的增加并不会影响原来的程序运行，因 为p e n t i u mi i i 处理器采用的是完全兼容于原来p e n t i u mi i 处理器的i a 3 2 构架。而且， 它极大地提升了电脑在高级图形、三维动画、数据流音频、视频、语音识别应用 等方面的性能。 s s e 指令集包括了7 0 条指令 1 8 - 2 0 ，其中包含提高3 d 图形运算效率的5 0 条 s l m d ( 单指令多数据技术) 浮点运算指令、1 2 条m m x 整数运算增强指令、8 条优化 内存中连续数据块传输指令。为了配合s s e 指令集，增加了8 个新的1 2 8 位单精度寄 存器( 4 3 2 位) ，能同时处理4 个单精度浮点变量，同时也添加了一个状态控制字 ( s t a t u s c o n t r o lw o r d ) 。为了充分发挥s s e 指令集和这些新寄存器的优势，i n t e l 又引 进了新的“处理器分离模式”，这是i m e l 继引入3 8 6 模式以来又一次推出新的处理 器模式。该模式允许并行使用s i m d f p 和m m x 或s i m d f p 和i a f p 双精度浮点代 码。s s e 兼容m m x 指令，它可以通过s i m d 和单时钟周期并行处理多个浮点数据来 有效地提高浮点运算速度。 3 2m a v i x 与s s e m m x 和s s e 都是在原来的处理器指令集的基础上添加的扩展指令集，都是 s i m d ( 单指令多数据) 指令，不同的是它们处理的数据类型不同。m m x 只能在整数 上支持s i m d ，而s s e 指令增加了单精度浮点数的s i m d 支持。m m x 可以进行同时 对2 个3 2 位的整数操作，而s s e 可以同时对4 个3 2 位的浮点数操作。 m m