（信号与信息处理专业论文）基于通用gpu的jpeg2000算法的并行实现.pdf

南京邮电大学硕士研究生学位论文 中文摘要 摘要 随着数字图像的应用越来越广泛，对图像质量的要求越来越高。在数字电影用领域， j p e g 2 0 0 0 被d c i ( d i g i t a lc i n e m ai n i t i a t i v e s ) 选定为数字存储的图像格式，但电影数据量庞 大，如果用c p u 来压缩，效率低且成本高。 本文首先介绍了j p e g 2 0 0 0 标准及实现方法以及g p u ( g r a p h i cp r o c e s s i n gu n i t ) 和 c u d a ( c o m p u t eu n i f i e dd e v i c e a r c h i t e c t u r e ) 的工作原理。然后，根据g p u 并行计算的特 点，提出了以g p u 作为协处理器加速j p e g 2 0 0 0 编码的技术方案。为了充分利用g p u 的 计算能力，本文提出了一种g p u 结合c p u 的并行编码架构，设计了d w t 分段提升和交 替存储的实现方案，并在此基础上实现了m c t ( m u l t i c o m p o n e n tt r a n s f o r m ) 和d w t ( d i s c r e t ew a v e l e tt r a n s f o r m ) 算法。接着，对本文设计的编码器与传统编码器在编码速度 和解压缩图像的峰值信噪比等方面作了性能比较，实验结果表明，在无损和有损压缩模式 下，本文提出的架构、算法和实现方案，相对于传统的编码器，可以在不升级硬件的情况 下，大大提高了高分辨率图像的编码速度，同时又保持了编码质量。 随着g p u 的可编程和计算能力进一步增强，将g p u 作为c p u 的协处理器应用在更多 领域，这种二者协同工作的架构必将会越来越被人们广泛接受。 关键词：j p e g 2 0 0 0 ；并行计算；图形处理单元；计算统一设备体系结构 南京邮电大学硕士研究生学位论文 a b s t r a c t c u r r e n t l y , d i g i t a li m a g eh a v eb e e nm o r ea n dm o r ew i d e l yu s e di na l lf i e l d so fp e o p l e sl i v e s a n dt h ei m a g eq u a l i t yr e q u i r e m e n t sa r ea l s og e t t i n gh i g h e ra n dh i g h e r i nt h ed i g i t a lf i l m a p p l i c a t i o n s ，j p e g 2 0 0 0w a ss e l e c t e db yt h ed c i ( d i g i t a lc i n e m ai n i t i a t i v e s ) f o rt h ed i g i t a l s t o r a g eo fi m a g ef o r m a t h o w e v e r , t h eq u a n t i t yo fd a t ai sv e r yl a r g e ，i tw o u l db el o we f f i c i e n c y a n d h i g hc o s ti fc o m p r e s s e d b yc p u t h et h e s i sb r i e f l yi n t r o d u c e st h ej p e g 2 0 0 0s t a n d a r da n di t sa l g o r i t h ma n dt h eo p e r a t i o n p r i n c i p l e o fg p u ( g r a p h i cp r o c e s s i n gu n i t ) b a s e do nc u d a ( c o m p u t eu n i f i e dd e v i c e a r c h i t e c t u r e ) a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fg p u ，w ep u tf o r w a r das c h e m et h a tu s e sg p u a sa l le f f i c i e n tc o p r o c e s s o rt os p e e du pt h ej p e g 2 0 0 0e n c o d i n g t om a k ef u l lu s eo ft h e c a l c u l a t i o nc a p a c i t yo fg p u ，w ed e v e l o pap a r a l l e la r c h i t e c t u r ef o re n c o d i n gb a s e do ng p ua n d c p us y s t e m ，a n das e r i e so ft h ec o d i n ga l g o r i t h mw e r ep r o p o s e d ，s p e c i f i c a l l ya n a l y z ea n d i n n o v a t et h em c ta n dd w t a l g o r i t h m sb a s e do ng p u m e a n w h i l e ，w ea n a l y z ea n dc o m p a r e t h e p e r f o r m a n c eb e t w e e no u re n c o d e ra n dc o n v e n t i o n a le n c o d e rb a s e do nt h ee n c o d i n gs p e e da n d p s n r , a n ds p e c i f i c a l l ya d d r e s s e dt h ep r o p o s e ds c h e m ew h i c hi sd w ts e g m e n tl i f t i n ga n d a l t e r n a t es t o r a g e t h r o u g ht h er e s u l t so fe x p e r i m e n t sa n ds e r i o u sa n a l y s i s ，w ea r r i v ea tt h e c o n c l u s i o nt h a tt h ep a r a l l e le n c o d e rb a s e do ng p uh a sm o r eh ig he n c o d i n gs p e e df o rh i g h r e s o l u t i o ni m a g e sc o m p a r e d 、析廿lc o n v e n t i o n a le n c o d e r m e a n w h i l et h en e we n c o d e rs t i l lc a n k e e pt h eh i g hc o d i n gg a i n ： w i t hf u r t h e re n h a n c eo ft h ec o m p u t i n gp o w e ra n dp r o g r a m m a b l ec a p a b i l i t yo fg p u ，w h i c h w o u l db eu s e da sac o p r o c e s s o ro fc p ui nm o r ef i e l d sa n dt h ef r a m e w o r kw h i c ht h et w o w o r k i n gt o g e t h e rw i l lb em o r ea n dm o r ew i d e l ya c c e p t e d k e y w o r d s ：j p e g 2 0 0 0 ；p a r a l l e lc o m p u t i n g ；g p u ；c u d a 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：导师签名：夕1 0 低日期：砂曲矿心 南京邮电大学硕士研究生学位论文 第一章引言 第一章引言 1 1 课题研究背景、目标及意义 j p e g 2 0 0 0 作为新一代的静止图像压缩国际标准，具有丰富的特性，能够进行单分量 或多分量的有损和无损编码，还同时支持s n r 和分辨率渐进传输、感兴趣区( r o i ) 编码、 码流随机访问，提供灵活的文件格式，支持内置用户信息( 如版权信息) 、图像序列( m o t i o n j p e g ) ，并具有良好的抗误码特性。 j p e g 2 0 0 0 主要特点包括： 高压缩率：在d w t 算法中，图像数据可以转化为可以更加有效存储的小波系数，因 此，j p e g 2 0 0 0 格式的图像压缩比可以比j p e g 提高约1 0 - - 3 0 ，d w t 变换可以是基于 整帧图像进行的，所以不会产生方块效应，使得压缩后的图像看起来更加细腻平滑。 无损压缩：预测法作为对图像进行无损压缩的成熟方法被集成到j p e g 2 0 0 0 中，因此 j p e g 2 0 0 0 能实现无损压缩，此外，由于j p e g 2 0 0 0 的抗误码特性也比较好，能更好地保证 图像的质量。 渐进传输：采用j p e g 2 0 0 0 格式的图像支持渐进传输，即可以先得到图像的低频直流 分量，然后逐步传输得到高频分量，也就是图像细节部分，有助于快速了解图像信息。 感兴趣区域压缩：可以在压缩时对特定区域指定压缩质量或在恢复时指定某些区域的 解压缩要求，这也是因为小波在空间和频域上有区域性，所以要完全恢复图像中的某个局 部，并不需要将所有编码都被精确保留。 正因为j p e g 2 0 0 0 具有诸多适宜的优点，在2 0 0 2 年4 月，好莱坞7 大电影制作公司宣 布成立名为d c i 组织共同制定数字电影技术的标准，鼓励电影院采用数字式放映设备，并 且决定将j - p e g 2 0 0 0 作为数字电影的图像压缩标准。数字电影指的是电影从制作工艺、制 作方式、到发行及传播方式上均全面数字化。与传统电影相比，数字电影与传统胶片电影 的最大的区别是不再以胶片为载体、以拷贝为发行方式，而是以数字文件形式发行或通过 网络、卫星直接传送到影院、家庭等终端用户。数字化播映是由高亮度、高清晰度、高反 差的电子放映机依托宽带数字存储、传输技术实现的【l 】。与传统的胶片电影相比，数字电 影具有多方面的优势，例如图像更加清晰、亮丽，声音更具感染力，避免了后期制作、发 行中的失真，以及多次放映造成的拷贝磨损等。另外，电影制作中的数字特技为艺术家提 南京邮电大学硕士研究生学位论文 第一章引 言 供了更广阔的制作空问，而数字加密技术也是数字电影具有更强的防盗版能力。未经压缩 的数字电影数据量十分巨大，以2 k 大小的数字电影为例，一部2 小时的电影的数据量约 为7 1 2 g 。这个数据量对于当前的存储技术而言显得过于庞大，因此高质量的图像压缩是实 现数字电影技术关键之一。 j p e g 2 0 0 0 具备诸多优良特性的代价是算法复杂度的大幅提高。经过测试，作为其核 心编码部分，m c t 、d w t 和e b c o t ( e m b e d d e db l o c kc o d i n gw i t ho p t i m i z e dt r u n c a t i o n ) ， 这三个处理过程就占了整个编码时间的9 0 左右。因此，m c t 、d w t 和e b c o t 的设计 与实现就成为g p u 并行化的重要部分，对能否高效、实时处理起着至关重要的作用。 1 2 本文研究思路和方法 首先，查阅j p e g 2 0 0 0 标准相关文献资料，深入了解j p e g 2 0 0 0 标准系统结构和原理、 关键技术，熟悉各个模块实现方法和相关实现代码；研读c u d a 的编程开发指导，熟悉并 掌握g p u 和c u d a 的概念；然后，研究c u d as d k 的例程，选取具有针对性的程序进行 编译、跟踪、调试，自主编写c u d a 程序以实现一般算法的并行运算，并分析性能；接着， 结合j p e g 2 0 0 0 开源代码深入理解其实现流程、原理等，并初步拟定相关模块的并行化方 案；最后，对系统进行整合，得出研究结论并分析性能提升，并总结工作过程中的经验 和遇到的困难及应对策略，展望下一步工作。 1 3 作者的主要工作与文章结构 1 3 1 主要工作 结合j p e g 2 0 0 0 标准文档和开源代码深入研究j p e g 2 0 0 0 标准，理解其编码流程、各 个模块实现的算法、研究并行实现可行性。广泛查阅j p e g 2 0 0 0 标准的相关资料，深入了 解系统结构原理，熟悉关键模块实现的关键技术，初步设计系统的总体框架，进行需求分 析，做充分的理论准备工作等。 采用g p u 设备和c u d a 规范实现对图像编码的并行加速，有别于v l s i 等d s p 实现 方法，是一个崭新的研究领域。通过研究g p u 和c u d a 编程开发指导，编译调试c u d a s d k 例程进步理解g p u 运行机制、d e v i c e 设备各个存储空间的使用、库函数的调用方 法等。分别针对j p e g 2 0 0 0 中运算复杂度较高的其中两个模块m c t 和d w t ，深入分析并 2 南京邮电大学硕士研究生学位论文 第一章引 言 提出并行实现方案并编程实现。 详细设计，完成m c t 和d w t 两个模块在g p u 上的并行实现，对结果做对比分析。 对上述两个模块进行整合，并做进一步优化，并着手开始对e b c o t 部分进行并行实现的 研究。 1 3 2 文章结构 本课题主要内容分四部分阐述。 j p e g 2 0 0 0 图像编解码标准( 第二章) 。着重阐述m c t 和d w t 的标准建议实现原理、 算法。 g p u 和c u d a ( 第三章) 。重点介绍g p u 通用计算的应用潜力，概要讲述g p u 的发 展，以及和c p u 相比具有那些优势，应用领域等。然后详细介绍c u d a 体系结构的相关 概念，包括编程模型、硬件实现、应用程序接口、性能优化等方面内容。 g p u 实现( 第四章) 。详细介绍m c t 和d w t 的g p u 实现思路、原理框图、程序流 程图等。作者对提出的方案进行详细分析并实现，包括无损压缩和有损压缩两种情况下的 m c t 和d w t 两个模块。 实验结果及分析( 第五章) 。给出在当前实验平台上进行的测试的实验结果，并进行 详细的性能对比分析，最后给出性能提升及图像峰值信噪比曲线。 南京邮电大学硕士研究生学位论文 第二章j p l 3 g2 0 0 0 图像编解码标准 第二章j p e g 2 0 0 0 图像编解码标准 j p e g 2 0 0 0 是j p e g 工作组制定一个新的静止图像压缩编码的国际标准，标准号为 i s o i e c1 5 4 4 4 l i t u tt 8 0 0 ，该标准和其他标准一样，由多个部分组成。其中，第一部分 在2 0 0 0 年1 2 月正式公布，其他部分则在之后被陆续公布f 2 1 。 在j p e g 2 0 0 0 工作之前，前面一个( 连续色调) 静止图像的压缩编码标准j p e g 已经 颁布了多年。特别是它的基本系统，已经被广泛应用，并且取得了巨大成功。其主要原因 包括技术上和实现上的优点，标准的开放性( 无需付版税) ，以及独立j p e g 小组i j g 提供 的免费软件等因素。然而，随着其在医学图像、数字图书馆、多媒体应用、i n t e m e t 和移动 网络的推广，他的一些缺点也日益明显。显然j p e g 的扩展系统解决了某些缺陷，但也仅 仅是在非常有限的范围内，而且有时还受到专利等知识产权i p r 的限制。为了能够用单一 的压缩码流提供多种性能、满足更为广泛的应用需要，j p e g 工作组于1 9 9 6 年开始探索一 种新的静止图像压缩编码标准，并在2 0 0 0 年正式颁布，称为j p e g 2 0 0 0 。 j p e g 2 0 0 0 主要有6 个部分组成。其中，第一部分为编码的核心部分，具有相对而言 最小的复杂性，可以满足约8 0 的应用需要，其地位相当于j p e g 标准的基本系统，也是 公开并可免费使用的。它对于连续色调、二值的、灰度或彩色静止图像的编码定义了一组 无损和有损的方法。具体的说，它有以下规定： ( 1 ) 规定了解码过程，以便于将压缩的图像数据转换成重建图像数据； ( 2 ) 规定了码流的语法，由此包含了对压缩图像数据的解释信息； ( 3 ) 规定了j p 2 文件格式； ( 4 ) 提供了编码过程的指导，由此可以将原图像数据转变为压缩图像数据； ( 5 ) 提供了在实际进行编码处理的实现的指导。 第二至第六部分则定义了压缩技术和文件格式的扩展部分，以便满足一些特殊的应 用，或者提供一些复杂的功能，但计算的复杂度大大增加。其中包括：编码扩展( 第二部 分) ；m o t i o nj p e g 2 0 0 0 ( m j p 2 ，第三部分) ；一致性测试( 第四部分) ；参考软件( 第五部 分) ；混合图像文件格式( 第六部分) 。 需要强调的是，j p e g 2 0 0 0 不仅提供了比j p e g 基本系统更高的压缩效率，而且提供了 一种对图像的新的描述方法，可以用单一码流提供适应多种应用的性能。特别是第一部分， 它与j p e g 2 0 0 0 基本系统比较主要具有以下优点： 南京邮电大学硕士研究生学位论文第二章j p e g2 0 0 0 图像编解码标准 ( 1 ) 更高的压缩比； ( 2 ) 同时支持无损和有损压缩； ( 3 ) 支持多分辨率表示； ( 4 ) 嵌入式码流( 渐进式显示解码和s n r 可分级) ： ( 5 ) 叠置( t i l i n g ) ； ( 6 ) 感兴趣区域编码( r o i ) ； ( 7 ) 抗误码； ( 8 ) 码流的随机存取和处理； ( 9 ) 对多重压缩解压缩循环的性能改进； ( 1 0 ) 更灵活的文件格式。 为了达到以上性能，j p e g 2 0 0 0 采用了许多新的压缩编码技术。首先，j p e g 标准中的 基于子块的d c t 被基于全帧的离散小波变换( d w t ) 取代。由于d w t 自身具有多分辨 率图像表示性能，而且它可以在大范围内去除图像的相关性、将图像能量分布更好的集中， 因此压缩效率得到提高。其次，由于使用整数d w t 滤波器，在单一码流中可以同时实现 有损和无损压缩。第三，通过使用一种带中央“死区( d e a d z o n e ) 的均匀量化器实现嵌 入式编码。对于量化系数各比特面进行基于上下文的自适应算术编码，这些由比特面提供 的嵌入式码流同时又提供了s n r 的可分级性。进一步，每个子带的比特面被限制在独立的 矩形块中通过三次扫描完成编码，由此得到最佳的嵌入式码流、改进的抗误码能力、部分 空间随机存取能力，简化了某些几何操作，得到了非常灵活的码流语法。 以下将着重介绍j p e g 2 0 0 0 基本档次的基本组成及核心算法部分的工作原理。这部分 内容可以满足目前大多数图像压缩的要求，而且由于具有免费公开的优点，将会受到广泛 的应用。j p e g 2 0 0 0 第二部分属于扩展部分，其中包含许多增加图像编码效率和提供新的 编码功能的关系内容，但在应用中将会涉及到专利等问题。 2 1j p e g 2 0 0 0 基本组成及工作原理 j p e g 2 0 0 0 的基本模块组成，其中包括预处理、离散小波变换、量化、自适应算术编 码以及码流组织等五个模块，如图2 1 所示。 离怒w 波t 孝换h 量化( d)l 一 自适应二进制 算术编码 ( t i e r - i ) 图2 1j p e g 2 0 0 0 基本编码模块组成 2 码流组织怛 1 压缩图像 ( t i e r - 2 )i 南京邮电大学硕士研究生学位论文 第二章j p e g2 0 0 0 图像编解码标准 输入图像可以包含多个分量。通常的彩色图像包含三个分量( r g b 或y 、c b 、c r ) ， 但是为了适应多频段图像的压缩，j p e g 2 0 0 0 允许一个输入图像最高有1 6 3 8 4 ( 2 1 4 ) 个分量。 每个分量的采样值可以是无符号数或有符号数，位深为1 3 8 ，每个分量的分辨率、采样 值符号以及比特深度可以不同。 2 2 预处理 叠块的尺寸可以是任意的，它们的数值可以大到整幅图像、或小到单个像素。每个叠块使 第二步是对每个分量的采样值进行电平位移，使值的范围关于0 电平对称。设比特深 度为b ，当采样值为无符号数时，则每个采样值减去2 昏1 ，当采样值是有符号数时则无需 比特深度相同。j p e g 2 0 0 0 第一部分有两种变换可供选择，它们假设对图像的前面三个分 刚纛- 016875-n0驯33126：5甜00g500-0 4 1 8 6 9 - 0 0 8 1 3 1 ) igi _ 1 o | |l ( 1 ) l c l o l 召j 耋=i兰三0773244，3吕1470244多 c 2 ， 另一种是无损彩色变换r c t ，它是对i c t 的整数近似，既可以用于有损编码也可以用 y = l - 半j ，u = r g ，矿= b g c 3 ， 式中，l w j 表示取小于等于w 的最大整数，即f l o o r 运算。反变换为： 1 半卜肛 南京邮电大学硕士研究生学位论文第二章j p e g2 0 0 0 图像编解码标准 2 3 离散小波变换 在j p e g 基本系统中，使用的基于子块的d c t 被基于全帧的d w t 取代。如果图像被 分为小的叠块，则对各叠块分别进行d w t 。 d w t 有很多特性利于实现j p e g 2 0 0 0 的一些需求。例如，多解析度图像的表示符合了 d w t 的本身固有的特性；此外，全帧特性在高压缩率情况下，d w t 以较大尺度的去除图 像相关性并且可以防止产生方块效应；最后，单一压缩的比特流可以同时允许使用整数 d w t 滤波器，适用于无损和有损压缩。接下来首先介绍1 dd w t ( 一维离散小波变换) ， 然后将概念扩展至二维2 dd w t ( 二维离散小波变换) 。 2 3 1 一维离散小波变换 在编码器端的前向1 dd w t 可以理解为一对低通和高通滤波器的逐次应用，接着在 每个滤波操作之后进行因数为2 ( 例如忽略奇数位置的采样值) 的下采样。低通和高通的 滤波器对被称作分析或分解滤波器组。 啼鹏 善( 刀) ； 巅吣 l 鹏 图2 - 21 - d ，2 - b a n d 小波分解和合成滤波器组 低通滤波器保留了信号的低频部分同时去除或消减了信号的高频部分，最终得到一个 原始信号的“模糊 形式。相反的，高通滤波器保留了信号的高频部分同时去除或消减了 信号的低频部分，而这部分通常为图像的边缘、纹理或细节部分。 考虑一个维信号x ( n ) ( 如图像某一行采样值) ，低通和高通的滤波器分别表示为h o ( n ) 和啊( 刀) 。例如，可以定义一个低通滤波器为h o ( n ) = ( - 1262 - 1 ) 8 ，这是一个对称结构 并有五个整数抽头系数，定义一个高通滤波器为j j l ( 功= ( 一l2 - 1 ) 2 ，这也是一个对称结 构并有三个整数抽头系数。这里采用的分解滤波器组通常被称为( 5 ，3 ) 滤波器组，表示低通 j 4 南京邮电大学硕士研究生学位论文 第二章m e g2 0 0 0 图像编解码标准 和高通滤波器的长度分别为5 和3 。为了确保滤波器操作不会越过信号的边界，首先需要 将信号进行延拓，这里采用的是双向对称周期延拓方式。当使用奇数抽头滤波器，信号将 如图2 3 所示方式进行周期延拓。偶数抽头滤波器的延拓方式相对复杂，在标准文档的第 二部分有所阐述【3 】。 原始信号样值 图2 - 3 输入信号在边界进行的对称周期延拓操作 从前向d w t 变换输出的采样滤波值被称为小波系数。由于采用下采样的方式，所以 小波系数的总数与原始信号采样值的数目相比保持不变。当d w t 应用于数据量为奇数的 采样值序列情况下，低通或高通序列会有个额外的采样以保证小波系数和原始信号数量保 持一致。在j p e g 2 0 0 0 标准中，这种选择是取决于输入信号在画布( c a n v a s ) 坐标系的位 置。滤波器输出值在以2 为因数的下采样后，原始信号仍然能够在剩余采样缺少任何量化 误差的情况下完全恢复，( ，如) 滤波器对就是以这种考虑而设计的，这种方式被称作理想 重建特性。 在解码端x c d , 波系数重建是采用另外一对低通和高通滤波器( 岛，g 。) ，即所谓的合成滤 波器组。如图2 2 所示。对于小波系数首先分别对低通和高通系数进行因数为2 的上采样， 上采样采用的方式是在两个采样之间插入一个零值。所得的结果再分别送入两个合成滤波 器g o ( r t ) f f g l ( i t ) ，二者所得结果进行相加得到重建信号圣( 刀) ，如果有充分的精度，因为理 想重建特性，重建信号可以和原信号x ( n ) 保持一致。 对于理想重建，分解和合成滤波器必须满足以下条件： 风( z ) g o ( z ) + h i ( z ) g 1 ( z ) = 2 ( 5 ) h o ( - z ) g o ( z ) + 只( - z ) g l ( z ) = 0 ( 6 ) 其中，h o ( z ) 是 ) 的z 变换，g o ( z ) 是孙( ，z ) 的z 变换，等。上述等式成立条件是： g ，o ( ，z 、) = - c z ，- 1 1 , ( - 、z ) ( 7 ) g l ( z ) = 凹叫n o ( - z ) 其中，是整型常量，1 7 是尺度因数。 南京邮电大学硕士研究生学位论文 第二章j p e g2 0 0 0 图像编解码标准 结合上述等式( 7 ) 和等式( 5 ，6 ) ，可以推出分解滤波器对( l d ，红) 必须满足： - - c z 一风( z ) h i ( - z ) + c z 日( z ) 风( 一z ) = 2 ( 8 ) 常量，代表延时选项，其在分解和合成滤波器的空间对齐上引入了限制；而变量c 则影 响滤波器的归一化。满足上述条件的滤波器组被称为双正交( b i o r t h o g o n a l ) 滤波器组。实 际上，和蜀相互正交并且啊和g o 也相互正交。一种特殊的双正交滤波器的分解和合成滤 波器是f i r 和线性相位( 例如，它们满足某种对称条件) 的情况。为了要满足等式( 8 ) ，分 解滤波器和啊的长度就不能相同。如果滤波器有奇数个抽头，它们的长度差别可能仅为 2 的奇数倍。 ( 5 ，3 ) 滤波器组是一个整数抽头双正交滤波器组具有代表性的例子，而那些采用浮点型 抽头的滤波器组则会具有较高的压缩效率。其中此类滤波器最知名的是d a u b e c h i e s ( 9 ，7 ) 滤 波器组，文献【4 】进行了介绍，滤波器抽头系数如表2 1 所示。为了便于对比，将( 5 ，3 ) 滤波 器组列于表2 2 。容易证明，在，= 1 和c = 1 0 情况下满足等式( 7 ，8 ) 。从表2 1 和表2 - 2 明 显看出，滤波器是以0 为中心，而滤波器啊是以一1 为中心，下采样操作可以在低通输 出中非常有效的保留偶采样值，同时也可以在高通滤波输出序列中非常有效的保留奇采样 值。 表2 1d a u b e c h i e s ( 9 ，7 ) 浮点滤波器组的分解和合成滤波器抽头系数 n l o w - p a s s ，( 以) l o w - p a s s ，g o ( n ) o+ o 6 0 2 9 4 9 0 1 8 2 3 6 3 6 0 + 1 1 1 5 0 8 7 0 5 1 4 5 7 0 0 0 1+ o 3 6 6 8 6 4 1 1 8 m 2 8 7 - 5 + o 5 9 1 2 7 1 7 6 3 1 1 4 2 5 0 20 0 7 8 2 2 3 2 6 6 5 2 8 9 9 0- 0 0 5 7 5 4 3 5 2 6 2 2 8 5 0 0 3 0 0 1 6 8 6 4 1 1 8 4 4 2 8 7 5 - 0 0 9 1 2 7 1 7 6 3 1 1 4 2 5 0 4+ o 0 2 6 7 4 8 7 5 7 410 810 n h i g h p a s s ， ( 聆) n h i g h p a s s ，g l ( n ) - l + 1 1 1 5 0 8 7 0 5 2 4 5 7 0 0 01+ o 6 0 2 9 4 9 0 1 8 2 3 6 3 6 0 - 2 , 0 - 0 5 9 1 2 7 1 7 6 3 1 1 4 2 5 0 0 , 2 - 0 2 6 6 8 6 4 1 1 8 4 4 2 8 7 5 - 3 ，10 0 5 7 5 4 3 5 2 6 2 2 8 5 0 0 1 , 3 0 0 7 8 2 2 3 2 6 6 5 2 8 9 9 0 - 4 ，2 + 0 0 9 1 2 7 1 7 6 3 1 1 4 2 5 0 - 2 , 4 + 0 0 1 6 8 6 4 1 1 8 4 4 2 8 7 5 3 , 5 + o 0 2 6 7 4 8 7 5 7 410 810 6 南京邮电大学硕士研究生学位论文 第二章 p e g2 0 0 0 图像编解码标准 表2 - 2 整数( 5 。3 ) 滤波器组的分解和合成滤波器抽头系数 n ( ，z ) g o ( n ) n 啊( 疗) n g i ( n ) 13 4 + 11 + 1 l+ 3 4 21 4+ 1 2 - 2 , 0 1 2 0 , 2 - 1 4 1 8 1 , 3 - 1 8 在1 d 信号已经分解为2 个频段后，低通的输出仍然具有较高的相关性，可以进一步 的进行2 阶分解从而去除更多的相关性。相对而言，对于高通输出系数进行进一步的分解 的意义很小。在绝大多数的d w t 分解的方法中，都是仅对低通输出结果进行进一步的分 解，如2 阶和8 阶分解。j p e g 2 0 0 0 标准的p a r t1 仅支持2 阶分解，而p a r t2 则允许对高频 系数进一步分解。 2 3 2 二维离散小波变换 采用可分离的方式可以容易的将1 dd w t 扩展为2 dd w t 。每一级的小波分解，2 d 图像首先采用l d 水平滤波器组( ，矗) ，然后对输出的子采样数据再用相同的滤波器对每 一列进行滤波。这样一级小波分解就被分离成四个子采样图像，称为子带( s u b b a n d ) 。既 然滤波过程是线性的特性，则水平和垂直滤波器的应用次序不会影响到2 d 子带的最终数 值。在2 d 二阶分解中，最低频率子带( 用l l 表示，即水平和竖直方向上都经过低通滤波) 进一步的分解为四个较小的子带，这个过程可以一直应用到没有效率可言的阶段。图2 _ 4 显示一个3 级，2 d 二阶分解图例及各个子带的表示。例如，子带标记为k h l 表示在d w t 分解的第k 级，行采用水平高通滤波，然后列采用垂直低通滤波，按照惯例，0 l l 代表原 始图像。图2 4 显示了一个使用( 9 ，7 ) 滤波器组( 如表2 1 ) 3 级，2 dd w t 分解的l e n a 图 像，可以很清楚的看出d w t 在低频率子带区域能量集中的特点。为了更好的表示子带的 能量，a c 子带( 例如，除了l l 子带的其他子带) 的能量都进行了4 倍的放大，为了显示 每个子带对图像能量的实际贡献，每个子带的小波系数应当用表2 3 中的对应的值进行加 权。 南京邮f n 硕 研究学位论文 第二章j p e g2 0 0 0 图像编解码标准 掣到：。 3 l h l 掘“f ：。l ：。 l 图2 42 - d ，3 纽小波分解殛l e n a 图像用( g 7 ) 滤波器组分解图倒 表2 - 3 2 - d ，3 级d w t 后各于带的n o r m 值 d w r 分解的固有特性正好解决了j p e g 2 0 0 0 标准对多解析度的需求最低应以解析度 为0 的系数进行重建图像。例如，见表2 - 3 ，3 l l 子带对应于3 级分解的解析度为0 。对 于n l 级d w t 分解来| 兑图像可以在n l + 1 级解析度进行重建。般的，为r 重建解析度 r ( r 0 ) 的图像需要综合解析度为p i ) 的各子带( 虬一r + 1 ) h l ，( _ 一r + i ) z h 和 ( m r + i ) h h 。这些子带都属于解析度r 。解析度为0 仅包含_ v 。工子带。如果分别对于 带进行编码，图像可以在任一解析度上重建，只需要简单的对码流中包含的当6 口解析度对 s i；i 2 ；i i 2 6 3 3 9 6 6 70ij；2 i；l 5 8 4 4 2 1 0 1 1 0 o 6 6 4 2 2 8 3 3 5 口6 6 9 2 2 8 3 3 7 i i i 8 j i i i i i 7 5 2 2 1 1 1 0 1 1 0 i i i 4 1 i i 4 2 5 5 9 8 8 7 o i i?4 0 0 0 o 9 9 9 o 0 o iill 0 0 01l 8 2 2 7 1 l 8 3 3 o i i i目 ，9 9 2 6 6 ，8 8 7 ；i 3 ；i i 4 0 0 o 0 0 0 0l兰紧裟篇 南京邮电大学硕士研究生学位论文 第二章j p e g2 0 0 0 图像编解码标准 应的子带以及之前的解析度子带进行解码。例如，对图2 - 4 ，图像可以综合解析度为l 的 图像以及在解析度2 的3 个标记为2 h l ，2 l h 和2 h h 的子带进行重建。 2 3 3 滤波器归一化 无损前向变换的输出数据可以采用任一尺度的归一化，只要确保反变换进行相应反归 一化最u , - i 。考虑d w t 滤波器，分解滤波器j l z d 和啊就可t ；一、a - - 任意归一化。对于等 式( 8 ) ，分解滤波器的归一化选择会影响到c 的值，它将决定合成滤波器岛和g 。的归一化。 d w t 滤波器的归一化通常以低通分解滤波器的d c 增益和高通分解滤波器啊的n y q u i s t 增益来表示，分别用和g 忡纽表示滤波器办( ，z ) 的d c 增益和n y q u i s t 增益，定义为： = 降刀，i ，垃= 陪矿坳) l 表2 1 ，表2 2 定义的( 9 ，7 ) 和( 5 ，3 ) 分解滤波器组，已经归一化，低通滤波器获得d c 增益为l ，高通滤波器的n y q u i s t 增益为2 ，将其记作( 1 ，2 ) 归一化，被j p e g 2 0 0 0 标准的p a r t l 所采用。其他常用的归一化方法有( 2 ，2 ) 和( 1 ，1 ) 。只要分解滤波器组的归一化方法确 定了，合成滤波器组则由反序来确定并乘以等式( 8 ) 的尺度常量c 。当前的j p e g 标准，前 向d c t 的缩放目的为了建立标准正交变换，它具有的特性就是，图像的采样值的平方和 等于变换后系数的平方和( p a r s e v a l 法则) 。并且，d c t 的标准正交归一化还有一个有用的 特性，那就是d c t 量化系数的均方误差( m s e ) 等于重建图像的均方误差。这样就提供 了一种简便的方法用来将系数量化对重建图像m s e 的影响进行数值化。不幸的是，这个 特性在d w t 分解中并不适用。 每个在1 dd w t 产生的小波系数可以和一个基函数相关联。重建信号i ( n ) 是这些基函 数的加权和，这里的权重就是小波系数( 量化或未经量化) 。用叱( 挖) 代表与系数( m ) 相 对应的基函数，m 表示第m 个小波系数，b 表示子带，则： 三( n ) = ( 聊) 叱( 刀) ( 1 0 ) b疗 对于相对简单的一级d w t ，除了子带边界附近外，低通和高通子带的小波系数的基 函数实际上是相应低通和高通合成滤波器的位移形式。一般的，d w t 分解的基函数不是 相互正交的，因此，p a s e v a l 法则也不适用。w o o d s 和n a v e e n 5 1 展示了量化小波系数在某种 9 南京邮电大学硕士研究生学位论文 第二章 p e g2 0 0 0 图像编解码标准 假设量化噪声影响下，重建图像的m s e 大约是小波系数m s e 加权和的1 0 倍左右，这里 子带b 的权是： 2 = 妙( 门) 1 2 对于子带b 来说，与厶一厅d 删相关。对于标准正交变换来说，所有的的值都将 是统一的。对于编码器来说，厶- n o r m s 必须已知，因为它们代表了每个子带的量化噪声 对于整体m s e 的贡献，并且在设计量化器或编码器时对量化结果数据的优先级方面是一 个重要的影响因素。 d w t 滤波器归一化同时影响厶一n o r m 和每个子带的动态范围。已知l d 分解滤波器 组的归一化，那么2 d 子带的标准动态范围可以从原始图像的采样位深r i 得到。特殊的， 对于( 1 ，2 ) 归一化，l ( l l 子带将会具有r i 比特的标准动态范围，然而实际的动态范围可能会 稍大一些。在j p e g 2 0 0 0 标准中，是使用若干保护比特来处理的，以避免子带数值的溢出。 对于( 1 ，2 ) 归一化，k l h 和k h l 子带的标准动态范围是r i + 1 ，而k h h 子带则为r i + 2 。 表2 3 显示在使用( 2 ，2 ) 或( 1 ，2 ) 滤波器归一化的( 9 ，7 ) 或( 5 ，3 ) 滤波器组进行3 级小波 变换之后的d w t 子带的厶- n o r m s 。显然的，使用( 2 ，2 ) 归一化的d w t 结果更接近于 标准正交变换( 尤其是对于( 9 ，7 ) 滤波器组) ，而( 1 ，2 ) 归一化则避免了在每级分解后的动态 范围的扩大。 2 3 4 离散小波变换实现方法以及提升方案 在基于d c t 的j p e g 标准的发展过程中，着重强调的是编码器和解码器的实现复杂度。 其中存在的问题主要包括，内存的需求，对每个采样值执行操作的数量，对硬件和软件实 现适应性程度( 如变换精度、并行处理等) 。对于诸多上述的考虑，才选择8 x8 作为d c t 块的大小。 相比较8 x 8 的d c t 变换所使用到较有限的缓存而言，2 dd w t 分解的直接实现方式 需要较大内存来缓存整幅图像。当然也可以使用较小的叠块为单位进行变换，从而可以减 少内存的需求，但不会大幅度的降低压缩效率。并且，有学者提出的一些巧妙的设计，那 就是基于行或列的小波变换的方式，可以有效的减少内存需求，主要取决于滤波器的核 ( k e r n e l ) 【6 】。近年来，有文献提出一种可替代的d w t 实现方式，就是所谓的提升方案 1 0 南京邮电大学硕士研究生学位论文 第二章t p e g2 0 0 0 图像编解码标准 7 , 8 , 9 , 1 0 】。为了有效减少d w t 的计算复杂度和内存使用量，基于提升的方法提供了原地( i n p l a c e ) 计算的方式，即用小波系数结果来覆盖原内存中存放的输入采样值。用提升方式所 计算得到的小波系数的值与直接用滤波器组卷积方式所计算的结果是一致的，非常类似于 快速傅立叶变换的结果对比于强制方式的d f t 变换的结果的对应关系。正因为提升有上述 诸多优点，所以j p e g 2 0 0 0 标准在d w t 变换核心部分只采纳了基于提升的方式，而非卷 积滤波器的方式。 提升包含下述几个步骤。首先，基本思想是首先进行直接( t r i v i a l ) 小波变换，即所谓 的懒惰( 1 a z y ) 小波变换，它将原始1 d 信号分离为奇采样值和偶采样值序列，然后交替预 测( a l t e r n a t i n gp r e d i c t i o n ) 和更新( u p d a t i n g ) 。图2 - 5 显示了一个( 5 ，3 ) 滤波器组提升的示例。 其中