（计算机应用技术专业论文）基于小波变换的图像编解码优化算法研究.pdf

中文摘要 图像编解码是图像处理领域的重要研究课题之一。借助高性能的图像编解码 算法，能够使得大规模的图像数据在有限存储空间中的存储以及有限带宽上的传 输成为可能。虽然图像压缩编解码算法在图像处理领域内已经得到了广泛的关注 和深入的研究，但是现有算法依然存在诸多缺陷，重构图像的质量和编解码速度 依然有待提高。本文在小波域图像编解码算法的理论基础上，论述了当前小波域 图像编解码算法的研究现状，并对小波域图像编解码算法的性能进行了研究和改 进。 首先，本文在小波变换的基础上，对图像的高频部分进行了方向滤波，使得 小波系数对二维图像的几何轮廓以及纹理信息的刻画更加精确。实验证明，与小 波变换方法相比，该方法在对富含纹理信息等的图像进行处理时能够获得更高的 图像能量聚集效果。基于该方法的图像编解码算法在对图像纹理及几何轮廓的描 述上具有更好的视觉效果。 其次，针对目前多核计算平台的高性能优势，本文提出了一种高速缓存性能 感知的h a a r 小波变换算法。通过对小波变换的原始数据进行相应的重组，并更 改变换结果的计算顺序，使得高速缓存的性能及潜力得到了更大的发挥。同时， 本文的h a a r 小波变换算法具有较小的数据相关性，利用多核平台的多线程并行 优势，可以进一步提升算法的性能。实验证明，算法在不同计算平台上都能够获 得较高的性能，并随着平台计算能力的增强，算法的性能会得到更大的提升。 最后，将本文提出的快速h a a r 小波变换算法与图像编解码算法相结合，实 验数据证明，在对高分辨率图像进行高压缩比编解码时，算法性能可以得到较大 的提升。同时，本文针对原有图像编解码算法中存在的内存管理较为复杂的问题， 实现了一种基于状态数组的编解码算法。结果分析表明，基于状态数组的方法内 存维护简单，算法拥有更小且稳定的内存消耗。 关键词：图像压缩小波变换w b c ts p e c kh a 盯多核 a b s t r a c t i i l l a g ec o d i n gi so n eo fm ei n o s ti i n p o r t a n tr e s e a r c ht o p i c so fi m a g ep r o c e s s i n g w i t l lm em 曲一p e r f o m a n c e 证l a g ec o d i n ga l g o r i t l l m s ，w ec a nm a k el a r g e s c a l ei i n a g e d a t as t o r e di nt h el 砌t e ds t o r a g es p a c ep o s s i b l e a l 廿l o u g hm ei r r l a g ec o d i n ga l g o r i t l l i n h a sb e e nc o n c e m e da i l ds t u d i e di 1 1t h ef l e l do fi i l l a g ep r o c e s s m g ，t l l e r ea r es t i l lm 锄y d e f e c t si i lt h ee x i s t i i 唱a l g o r i t l l i ：衄b a s e do nm ew a v e l e td o m a i nh a g ec o d i i 培 a l g o r i t l l mt h e o r i e s ，t h i sp a p e rd i s c u s s e st h ec m r e n ti n l a g ec o d i i l ga l g o t 1 1 i 玛s t u d i e s a n di i i l p r o v e s 也ep e r f o n n 柚c eo fi t f i r s t ，w e 娜o r tt h ew b c t 仃a n s f o n n t oi i l l a g ec o d i l l ga l g o r i t h ! 1 1 ，t h j sm a k e s “ m o r ep r e c i s et od e s c r i b et l l eg e o m e t r i cc o m o u ro fm ei m a g e t h ee x p e r i m e mr e s u l t s p r o v em a t ，c o i n p a r e dw i n lw a v e l e t 仃a n s f o 姗，t h i sm e m o d c a i lh a l l d l eal l i 曲e ri m a g e e n e 玛ya c c u m “a t i o ne f i e c ta i l dg e tab e t t e rd e s c r i p t i o no fh 啪a nv i s u a le a e c t s s e c o n d l y ，b a s e do nm e1 1 i g h - p e r f o m l a n c e sa d v a n t a g e so fm u l t i c o r ec o m p u t 协g p l a t f o 加啮，ac a c h e a w a r ea l g o r i t h mo fn l eh a a rw a v e l e t 仃a i l s f o 衄i sp r o p o s e di 1 1m i s p 印e r t h r o u g hr e c o n s 协j c t i n gt h er a wd a t aa 1 1 dc h a n g i i 培m ec a l c u l a t i o no r d e r ，w e l l i g l l l yi i n p r o v e 廿l ep e r f 0 i l a n c ea r l dp o t c m i a lo ft 1 1 ec a c h e a tt 1 1 es 锄et i i i l e ，w eu s e t l l ea d v a n t a g e so f 舢l t i - t 1 1 r e a d e dp a r a l l e lt e c h l l i q u e s e x p e 血i l e n t ss h o wt h a t ，t h e a l g o r i n l mc a l la c c e s sah i g h e rp e r f o n i l a n c eo nd i 日 e r e mc o m p u t i i l gp l a t f o m s a tl a s t ，w ec o m b i n et l l e r a p i dh a a rw a v e l e t 仃a n s f o 咖锄di 1 i l a g ec o d i n g a l g o r i t h m t h ee x p e r i m e n t a ld a t as h o w st h a tt l l ea l g o r i 廿l mc a ng e tal a 唱e ri l l c r e a s e w h e nc o m p r e s s i n gn l e1 1 i g h r e s o l u t i o n 曲a g e sw i t hl o wb p p i i lt h eo r i g i l l a li i l l a g e c o d i i l ga l g o n t h 地l em e m o r ym a n a g e m e n ti sag r e a td i 伍c u l tf o rp r o 静锄瑚e r i nt b j s p a p e r ，w ea l s or e a l 讫eai i l l a g ec o d i n ga l g o r i l mb a s e do nas t a t e 戤r a yn o tt h eo r i g i l l a l l i s ti i r l l ( t h ee x p e r i i n e n ts h o w st h a tm em e t l l o db a s e do ns t a t ea r r a yn e e d sl e s sa n d s t a b l es t o r a g ea n de a s yt om a n a g em e m o r y 1 蚀yw o l m s ： 硫a g ec o m p r e s s i o n ，w a v e l e tt r a 【1 1 s f o m ，、7 忸c t s p e c k ，h a 碣 m u l t i c o r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁鲞蠢堂或其恐教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：瓠立阁1 签字网期：埘年莎月箩日 学位论文版权使用授权书 本学位论文作者完全了解丞盗盘堂有关保留、使用学位论文的规定。 特授权墨奎盘篁可以将学位论文的全部或部分蠹容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文 乍者签名：孤立坷 导师签名： 签字目期：勘d 艿年参月s 曰 签字日颦：疹孑年厶月j 日 、竹 第一章绪论 l 。董课题研究背景 第一章绪论 人类在自然界中所能感受到的信息很多，包括视觉、听觉、触觉、嗅觉等， 其中通过视觉获得的信息量最大，占至l 总信息量的2 3 。视觉所箍感受到的是外 部世界中各种立体和彩色的物体图像。图像是物体反射或投射的光能量或者发光 物体本身发出的光能量被人视觉系统接受后在人大脑中所形成的认识 1 】。 近些年来计算机技术、现代通信以及多媒体等技术迅速发展，多媒体作为先 进视频、音频以及通信等高辩技技术的产物，已经逐渐渗透到入们的露常生活中。 对于目前多媒体技术来说，所设计到的数据源主要包括：图像、语音、视频等， 这些数据源全都具有耗费存储空间、传输缓慢的特点。在这一类多媒体数据源中， 图像信息是能够给予人类最直鼹印象的信息载体，且动态图像、视频等多媒体都 是静态图像的变体，最终反映到人类的大脑中也都是一张张静态的图像数据，因 此，图像数据是多媒体数据源中最普通也是最重要的数据类型。对静态图像数据 的科学研究可以带动视频等其他技术的发展。 现代图像和多媒体技术的发震需要大量地存储和记录海量的图像信息，健是 未经处理的图像信号的数据量是巨大的，这就使得图像信息的存储以及图像信息 在网络通道中的传输等都受到了很大的限制，因此，稳定高效的图像压缩算法就 显鼐至关重要。图像数据压缩编码技术已经成为多媒体以及通讯领域中的关键技 术之一。目前，图像压缩技术已经成为图像处理学中很重要的一个研究方向，且 在众多领域中都起着至关重要的作用，因此，对图像压缩编码技术的研究及改进 对于图像处理算法来说是相当重要且有意义的。 1 2 图像压缩的必要性 以一副分辨率为l0 2 4 1 0 2 4 的图像为例，每个像素必飚b 三个颜色通道， 郎需要8 3 比特，如果不经过压缩处理，这样一幅普通的图像将会占据约3 m 的存储空间。对这种分辨率的图像进行存储的话，每1 0 0 0 张阌像，所需存储空 间将会达到约3 g b 。而如果需要在网络上传输张这样的照片，假设每秒钟传 输5 硒，那么这样一张图片的传输就需要大概6 秒的时阆。这种巨大的存储 第一章绪论 空间以及缓慢的传输速度对于现代计算机来说都是不可忍受的。 虽然人类可以通过高速带宽或者高存储量的硬盘来解决这一问题，但这并不 是问题解决的根本之道。因此只有对图像数据进行压缩编码处理，去除图像中大 量的冗余信息，大幅度地压缩图像的数据，使其适应目前的数据传输通道的带宽 容量以及存储介质的空间才是目前解决这一问题的切实可行的途径。通过图像数 据压缩技术能够最大限度地节省图像的存储空间，而且可以最大限度地减小图像 远程传输过程中对带宽的消耗，从而提高图像的传输率，减少不必要的能源消耗。 1 3 国内外研究现状 图像压缩的理论起源于2 0 世纪4 0 年代香农的信息理论。香农的信息论表明， 在不产生任何失真的前提下，通过合理的编解码算法，对每一个信源符号分配不 等长的码字，平均码长可以任意接近信源的熵 2 1 。著名的无失真编码方法霍夫曼 编码以及算术编码方法，都是在该理论的指导下产生的。但在实际应用中，无失 真编码压缩效率小，因而并不能完全满足实际应用的需求，为了进一步提高图像 数据的压缩比，人们对图像数据压缩的研究转移到了有损压缩方法上。 有损图像压缩的目的是去除图像像素之间的冗余信息，以尽可能少的码字来 表示所处理的图像。频域压缩算法是目前常用的有损图像压缩方法。在通信数字 信号处理中最经典的频域变换算法为傅立叶变换，但是傅立叶变换并不适合作为 数字图像变换方法。经过大量的研究结果表明，具备最理想去相关和最强能量聚 集特性的k l ( k a r h u n e i ll o e v e ) 变换是一种变换系数互不相关的变换方法，但是 k l 变换不适用于计算机离散实现，因此，学术界又找到了一种很好的逼近k l 变换的频域变换算法，称为离散余弦变换( d c t ) 【3 】o 正是由于d c t 变换的优越性 使得d c t 变换在图像压缩领域中得到了广泛的利用，成为图像变换编码方法的 主流工具。 2 0 世纪8 0 年代中期，静止图像国际编码标准组织利用d c t 变换制定了j p e g 图像编解码标准1 4 j 。j p e g 图像编解码标准采用d c t 作为频域分析工具，并采用 易于处理的8 8 的数据块来进行分块编码。同时，口e g 编码过程中也引入了量 化的观点。通过对原始图像的数据块进行色度量化和亮度量化，使得原始图像的 像素幅度值发生了很大的降低，并且产生了很多接近于零的像素点。最后，j p e g 采用霍夫曼编码方法来对所有的量化结果进行编码。旧e g 标准的出现，使得图 像压缩编码技术在实际应用中真正得到了统一，并得到了普及。 与此同时，图像压缩算法的其他分支也相继发展开来。基于数学形态学的压 缩算法、基于空间域的图像压缩算法以及基于统计理论的图像压缩算法等都发展 第一章绪论 成为图像压缩领域中的重要编码方法。 2 0 世纪8 0 年代后期，小波变换逐渐发展为图像处理领域中重要的工具。小 波变换的发展提供了一种新的有效的多分辨率信号分析工具，也为各种可分级图 像编解码算法的实现奠定了基础p 】。正是由于小波变换的多分辨率以及能量聚集 等特性，使得小波变换在图像压缩领域中也逐渐风靡起来。小波图像压缩算法的 研究表明，现代应用所需要的许多特征如多分辨率、多层质量控制以及嵌入式码 流等思想都与小波变换的结构非常接近。通过大量的实验数据表明，基于小波变 换的图像压缩算法其图像重构质量明显要好于基于d c t 变换的图像编码算法。 因此，国际图像编码标准组织与2 0 0 0 年制定了新一代静止图像压缩标准 j p e g 2 0 0 0 。j p e g 2 0 0 0 采用小波变换代替了原来口e g 中的d c t 变换，并结合上 下文熵编码方法，使得用j p e g 2 0 0 0 编解码后的图像具有更好的图像视觉效果【6 1 。 目前基于小波变换的图像压缩算法中，除了图像压缩标准j p e g 2 0 0 0 外，还 相继出现了利用小波变换空间特性来去除图像冗余的嵌入式小波编码算法。这一 类图像编解码算法的计算复杂度、算法运行时间以及重构图像的质量都得到了很 大的改善，且在实际商业应用中已经得到了很大的市场。嵌入式小波编码算法的 出现使得基于小波变换的图像压缩编码理论在很大程度上得到了完善，也使得小 波变换这一有效图像处理工具在图像压缩编码领域大放光彩。 虽然一直以来对图像编解码问题的研究比较火热，但是还有许多的技术难题 没有解决或者亟需解决。图像编解码算法本身可能并不复杂，但是面对大干世界 千千万万种不同类型的图像，很难找到一种适合于所有图像的编解码算法。且迫 于人类飞速认知世界所带来的海量数据处理的需求，在当前压缩算法性能上继续 提高算法压缩比的研究依然会是一个热点和难点。 1 4 主要工作和框架结构 1 4 1 本文工作 本文主要研究在目前个人计算机平台上，如何快速且高质量地对二维图像数 据进行压缩编码。主要研究工作和创新之处包括以下几个方面： 针对小波变换在对二维图像表征过程中的缺点，将c o n t o u r l e t 变换【7 】与小波 变换相结合，形成一种基于小波变换的类似c o n t o 训e t 变换的无冗余变换方 法，并加入到图像编码过程中。为了更好地说明变换的性质，本文从高频系 数的空间分布以及高频系数能量分布两个角度通过统计数据比较了该变换 与小波变换的优势，并且对编解码后的图像数据进行比较分析。 第章绪论 针对盈前多核计算平台的普及性以及多核平螽的强大计算能力，本文通过充 分利用高速缓存的工作原理以及多线程程序设计的优势，提出了一种在多核 平台上高速缓存优化的并行h a a r 小波计算算法。通过测定算法运行过程中 高速缓存缺失率以及算法在不同多核计算平台上的运算性能，证明了本文提 出的算法具有高速且可移植的特性。 在目前编码方法的基础上，本文针对编码算法的两个关键环节：小波变换和 编码过程分别进行了优化操作。首先将第二部分工作中的快速h a a r 小波变 换引入到图像编码过程中，这使得在对高分辨率图像编码时大大提高了速 度。然后实现了一种内存优化的小波域图像编解码算法。由于原有的算法采 用链表结构来维护小波系数的饿置信息，且随着编码层数的加大链表节点数 会急剧增长，因此，本文实现种基于状态标记的数组减少了编解码过程中 昀内存消耗，有利用特殊硬件平台的实现。 1 4 2 本文结构 第一章，介绍了本文的研究背景和意义，概括叙述了本文所做的工作。 第二章，主要介绍了与本文研究工作相关的图像压缩算法棚关技术、图像压 缩算法的分类以及小波域图像压缩算法的优化平台。 第三章，将方向滤波与小波变换相结合，并引入到图像编解码算法中，通过 对变换结果的统计分析以及对重构图像质量豹比较，验证了该变换方法的有效性 和优越性。 第网章，充分利用目前的多核计算平台，提出一种在多核平台上高速缓存性 能感知的珏a a r 小波运算优化设计，并分析了在多种计算平台上的运行结果。 第五章，针对霉前的图像编熊磷算法的两个不同环节分别提出了优化算法， 并通过具体的实验证明了两种优化算法在性能和内存消耗上的改进。 第六章，对全文研究工作进行总结，并对今后的工作做出展望。 4 第二章基础知识 2 1 图像压缩算法基础 第二章基础知识 在数字图像处理过程中通常会遇到分辨率很高或者图像数据文件很大的海 量图像数据源，这些图像文件经常需要在不同的用户以及各种传输通道中进行传 播，这就需要一种快速有效的方法来存储以及传递这些文件。针对海量数据的问 题，最直接的办法就是对原始数据进行压缩。 图像压缩技术通常利用消除图像数据之间的冗余性以及不相关性，将一个较 大的数据文件编码成一个较小的文件【8 1 。从本质上来说，图像压缩就是对要处理 的图像数据运用一定的规则进行变换或者重新组合，从而达到可以使用尽可能少 的比特位来表示尽可能多的图像原始数据的目的。 2 1 1 图像压缩的可行性 数字信号之所以能够进行压缩，主要原因在于：图像信号像素之间存在大 量的冗余信息，这些冗余信息对于图像的细节来说并不重要，且冗余信息在利用 一定的编解码方法后可以近乎无失真地恢复【9 1 。人眼的视觉特性决定了人类在 观看图像数据的时候会忽视图像的一些数据特征。充分利用人眼的视觉特性，可 以进一步加大图像的压缩力度且能够提供更好的视觉效果【1 0 】。 图像的冗余信息主要有： 空间冗余：图像数据之间具有很强的数据相关性，通常可以通过某一个 具体像素的性质获得其邻域像素的性质，因此这些相关的像素之间就存在着很大 的数据冗余，这种冗余称为空间冗余或者图像数据几何冗余。 结构冗余：有些图像尤其是自然图像中经常会出现大面积或者整体看上 去存在重复出现、相同或者相近的纹理结构，或者有些图像的纹理像素值存在着 明显的分布模式，这种冗余情况称为结构冗余。 时间冗余：这种冗余特点是针对图像序列而言的。在图像序列中，相邻 帧的图像之间其数据上存在很大的相关性，一副图像中的某些物体或场景可以由 前一帧图像中的物体和场景通过一定的规律便可以计算出来。这种在图像时间序 列中的冗余信息称为时间冗余。 视觉冗余：视觉冗余是指信源中存在很多处于人们视觉分辨能力以下的 第二章基础知识 信号。如果在编解码的过程中舍去这些信号，虽然会导致解码后的信号产生一定 的率失真，但这些失真信息却并不能为人所感知。这种不处于人类视觉范围以内 的信号则被称为视觉冗余信息。 另外，还有针对信源理论的信息熵冗余，针对知识发现的图像知识冗余等冗 余信息。正是由于图像数据之间存在这些冗余信息，才使得图像数据能够被压缩， 也才使得图像压缩技术能够得到如此巨大的发展。 2 1 2 图像压缩算法评价指标 一般来说，图像压缩算法的评价主要可以分为三个方面：编解码压缩率、编 解码后的图像质量以及编解码算法的运行时间。 ( 1 ) 编解码压缩率。对于图像压缩来说最需要的就是一个高压缩比的性能， 因此压缩算法所追寻的都是尽可能高的压缩比。 压缩率= 压缩后原始图像文件的比特数压缩前图像文件的比特数 压缩比= 1 压缩率 另外一种常用的表征图像压缩率的参数为b p p ( b i tp e rp i x e l ) ，表示平均每个像 素分配到的比特数，计算方法为： b p p = 压缩后图像文件的总比特数图像文件的像素总个数 ( 2 ) 编解码后的图像质量。图像压缩算法可以根据算法的实际需要进行有损 编码或者无损编码。无损编码是指编码和解码过程中算法不得损失原始图像中的 信息，有损压缩是指为了获得更高的压缩比，在牺牲一定图像质量的基础上进行 的压缩。有损压缩会使得图像压缩前后发生一定的失真，而我们所说的图像质量 评价标准基本上是针对有损压缩而言的。 对于有损图像压缩算法，通常采用客观和主观共用的办法来对其解码后的图 像质量进行评定。 客观评价准则 客观评价准则是对图像压缩还原后的重构图像与原始图像的误差进行定量 计算，一般是对针对整个图像或者图像中一个指定的区域进行某种平均计算而得 到。通常采用的客观评价标准有：均方误差( m s e ) 和峰值信噪比( p s n r ) 。 设定待评测的解码后图像为厂( z ，少) ，原始图像为g ( z ，y ) ，图像大小都为 m 木，那么解码后图像的均方误差可以表示为： 艘= 击篓卦几川叫w ) 2 ， 6 第二章基础知识 峰值信噪比可以表示为： 删：1 0 x l o g 丝 。m s e ( 2 2 ) 最常用的评价标准是峰值信噪比p s n r ，当p s n r 值超过3 0 时，人类的肉眼 就很难发觉图像之间的差异了。 主观评价准则 人类的视觉特性有很多特殊的性质。如人类视觉系统对图像像素值灰度的突 变特别敏感，这使得发生于图像边缘或轮廓附近的误差比发生于一般背景上的误 差对图像的质量影响更大，而这种误差用客观评价指标是无法有效衡量的，此时 就需要人为主观地来进行评价。目前国际通常采用五级标准如表2 1 ： 表2 1 图像质量主观评价标准 图像质量级别图像失真度级别 1非常好丝毫看不出图像质量变坏 2 好能看得出图像质量变化 3 一般看得出图像质量有变化，对图像理解稍有妨碍 4 较差 影响图像理解 5 差非常影响图像理解 一般来说在评定图像的质量的过程中都是采用主观和客观共用的方法来进 行评测。首先利用客观p s n r 来进行评定，给出图像质量的一个初步判定，然后 利用主观评价再加以区分【l l 】。 2 2 图像压缩算法分类 图像数据压缩编码技术可以有多种分类方法。根据编码对象的不同，可以分 为静止图像编码、活动图像编码、传真文件编码等；根据压缩过程中有无信息损 失，可以分为有损编码和无损编码，或称为可逆编码和不可逆编码。最常见的分 类方式是按照编码的原理进行分类，图2 1 总结了目前常见的几种图像压缩编码 方法。其中所列举的皆为目前图像编解码领域内著名且具有重要影响的编解码算 法，在此本文选取其中4 个编码作为代表作简要介绍。 ( 1 ) 统计编码 第二章基础知识 静态图像编解码技术 耋li 茎i i 奏li 雾ij 茎l i 耋ii 蓁 图2 1 图像压缩编码分类 j p e g 等编 码标 准 这类编码算法通过对图像的像素值进行统计，然后根据图像的统计特性利用 信息熵等原理，让出现概率大的像素幅度值用较短的码字表达，反之用较长的码 字表示，如霍夫曼编码和算术编码【1 2 】。 ( 2 ) 预测编码 二维图像的相邻像素之间存在着空间上的冗余信息，预测编码就是利用了这 一特点，通过之前已经传输的像素值来预测当前位置像素值。预测编码是最早采 用的图像编解码技术之一，也是目前数据压缩技术在空间域的一个重要分支【1 3 1 。 ( 3 ) 分形编码 分形几何可以用于描述自然界中一些景物的自相似性。目前分形编码主要是 利用“拼贴定理”和“不动点理论”将图像的自相似性结构用一组仿射变换的迭 代码来表示，编码器只需对这组迭代码进行编码传输 1 4 】。 ( 4 ) 变换编码 变换编码是将一组像素值经过某种形式的正交变换转换成一组变换系数，然 后根据人的主观视觉特性对各变换系数进行不同精度的量化后编码的技术1 5 】。正 交变换的作用是消除图像像素之间的空间相关性，降低图像的冗余度。目前图像 编码常用的正交变换有离散余弦变换( d c t ) 、离散傅立叶变换( d f t ) 等。 ( 5 ) 子带编码 子带编码是将图像在频率域上划分成不同的子频带，然后根据他们的统计特 性进行不同的处理。由于高频子带只携带较少的图像信息能量，同时对人的视觉 影像也较小，因此对高频子带可以进行高步长的量化，而对于含有重要信息的低 频子带来说则需要进行较为精细的量化，以此达到压缩的目的 1 6 】。 第二章基础知识 ( 6 ) 小波编码 小波编码是在子带编码思想的基础上提出的一种编码方法。小波变换具有很 强的时频分析能力，能够把图像信号的能量最大限度地聚集到图像低频子带中 去，而把图像的细节信息放到高频子带中，小波变换的这种能量聚集特性特别适 合于压缩编码的算法设计【1 7 】【1 8 】。 2 3 小波分析基础 小波分析是建立在泛函分析、傅立叶分析等基础上的新型信号分析处理工 具，作为多个学科共同研究的成果，小波分析理论正在日益受到密切关注。小波 变换克服了傅立叶变换的缺点，具有良好的时域和频域局部化特征，正是凭借着 小波分析在时频方面的优越特性，使得小波成为信号处理领域强有力的研究工具 1 9 1 。“数学显微镜”这一称号当之无愧。 2 3 1 小波变换的定义 设z ( f ) 是平方可积函数，记作石( f ) r ( r ) ，y ( f ) 被称为基本小波或小波母函 数，则 暇 6 ) - 击卜( r 砂) 出= ( 北) 批) ( 2 - 3 ) 称为z ( f ) 的小波变换，口 o 为小波尺度因子，6 是位移，6 r ，其中 圳= 击y 睁) v 口 口 ( 2 4 ) 尺度因子口的作用是对基本小波进行伸缩。口越大，y ( f 肠1 越宽；口越小， j l f ，f f 口) 越窄，通过改变口的大小，可以改变小波变换的分析空间，从时域角度来 看，改变口的值就相当于改变小波变换的时域分辨率。 对连续小波离散化可以通过对尺度参数口和位移参数6 的离散化取样来实 现。为了能够对信号进行全面、完整的表示，对口和6 的离散化必须满足完全覆 盖整个时频相平面。经证明，如果对尺度参数口进行指数取样，对位移6 进行均 匀采样的话，可以满足小波函数时频窗覆盖整个相平面的要求。对口、6 的离散 化如下： 9 第二章基础知识 口= 口i 7，= 0 ，l ，2 ( 2 5 ) 6 = 筇7 尼露= 0 ，1 ，2 则由此得到的离散化的小波母函数为： j ，。( f ) = 菇少( 口扣一尼) ，七z ( 2 6 ) 以此为基函数，所构造的小波变换就是离散小波变换，定义如下： | 设 f ，( f ) r ( 尺) ， o ，。( f ) = 菇少( 口扣一后) ，后z ， 则称 为厂( f ) 的离散小波变换。 2 3 2 多分辨率分析 ( ，忌) = l 厂( f ) 吩，。( f ) 出 ( 2 7 ) m a l l a t 在1 9 8 6 年将计算机视觉领域内的多分辨率分析的思想巧妙地引入到 小波分析中，从而统一了在此之前各种小波基的构造方法，并给出了一种子带滤 波器结构的离散小波分解与重构算法。这一算法在小波分析中的地位相当于经典 傅里叶分析中的f f t ，奠定了离散小波变换在图像处理、图像编码等领域中的应 用基础 1 9 1 。 多分辨率分析m 州m u l t i r e s o l u t i o n a n a l y s i s ) 又称多尺度分析，它是在r ( 尺) 函数空间内，将函数厂( 石) 描述为一系列近似函数的极限，每一个近似函数都是 厂( x ) 在不同分辨率子空间上的投影。 我们采用理想滤波器组来粗略地介绍多分辨率分析的概念。 当信号x ( ，z ) 的采样频率满足采样定理时，其频带处于一万到万之间。定义理 想低通滤波器为三f w ) ，理想高通滤波器为日( w ) ，通过低通滤波器和高通滤波 器，可以将信号分解成频带在。一万2 的低频部分和频带在州2 一万的高频部分， 分别反映了原始信号的主体信息和细节信息，两种输出后的信号频带均减半。类 似的过程可以对每次信号分解后的低频部分重复分解，即每一级分解把该级输入 信号分解成一个低频的低分辨率版本和一个高频的细节部分信息，且每级数出的 采样率会再次发生减半。所有级别的低频版本就构成了原始信号在不同尺度下的 多分辨率版本，而这个过程也就成为多分辨率分析。整个过程可以如图2 2 所示， 1 0 第二章基础知识 其中h 表示高通滤波器，l 表示低通滤波器，圆圈表示二进滤波。 信号 图2 2 多级小波变换 高频 低频 图像数据属于二维信号，对于二维图像信号的小波变换称为二维小波变换。 通过分别在水平和垂直两个方向上进行滤波的方法可以实现二维小波变换多分 辨率分解。原始图像信号进行一级小波分解被划分成4 个子带，分别为：l l 子 带，对应图像的低频成分，反映图像的低分辨率版本；l h 子带，对应水平低通 垂直高通，反映图像在垂直方向的高频细节；h l 子带，对应水平高通垂直低通 子带，反映图像在水平方向的高频细节；h h 子带，对应水平和垂直两个方向的 高通信息，反映图像在对角线方向的高频细节。图2 3 所示为相应的二维小波变 换一级和二级变换的频带划分示意图。 乙l 2h l 2 h l l l 2 h 拄2 l 。雅1雕1 图2 3 二维小波分解。左图为一级变换，右图为二级变换。 2 4 小波域图像压缩算法 由于小波变换具有很好的图像去冗余性和去相关性，因而基于小波变换的图 像数据压缩编码算法的探索已成为当前的研究热点。时间内，出现了很多基于 小波变换的图像压缩编码算法。基于小波变换的图像压缩方法目前已经逐步取代 第二章基础知识 了基于离散余弦变换和其他子带编码的编码技术，逐渐发展成为了目前新的图像 压缩国际标准的首选方法。 2 4 1 嵌入式编解码算法 嵌入式编码是指编码器将待编码的比特流按重要性的不同进行排序，根据目 标码率或失真度大小要求随时结束编码；同样，对于给定码流的解码器也要能够 随时结束解码操作，并且可以得到相应码流截断处的复原图像。这种嵌入式编码 方法比较灵活，能够获得任意压缩比的性能，且能够根据实际需要，动态调整编 码的码流长度。嵌入式编码首先传输的是图像中的重要信息，即图像中幅值较大 的显著系数。 小波系数的能量大多集中在低频，而高频子带中对重建图像影响重要的显著 系数却呈现出成簇分布的特点，如何能够充分对这些系数进行编码一直是小波域 图像编码的核心。围绕这一问题产生的编解码算法中比较典型的嵌入式编解码算 法有：嵌入式零树小波编码算法( e z w ) 1 7 1 8 ，多级树集合分裂编码算法( s p i h t ) 【2 0 】【2 、集合分裂嵌入块编码算法( s p e c k ) 【2 2 】等。 e z w 算法：由于小波变换低频系数和高频系数之间在空间上存在着相关性， 正确利用这种相关性可以充分编码高频中的显著系数。由图2 4 可知，在描述相 同空间位置的小波系数时，在同方向低频子带和相邻高频子带之间存在着四叉树 的划分关系。e z w 算法正是利用了这种低频系数和高频系数的空间四分关系来 消除不同级别的高频显著系数之间的空间相关性【】7 】【18 】。 | 鬈l 氍 f 添最 | 、 鼢 翥 、删 翮离 旧 、 嘲2 南 图2 4 零树的空间结构 1 刀 对于嵌入式编码方法来说，一般都是从所有系数中门限最高的阈值开始逐层 往小去细化小波系数。大于或等于阈值的称为重要系数，小于阈值的称为不重要 系数。具有不重要系数的四叉树节点称为零节点。由于图像小波变换后高频子带 1 2 第二章基础知识 系数较小，再经过阈值标量量化后零节点的数量很大。e z w 正是把这些大量的 零节点进行了有效的组织编码，从而极大地提高了压缩算法的效率。 s p i h t 算法：该算法以l l 子带为树的根节点，按照图2 4 的方式建立了四 叉树的空间结构。s p i h t 算法的创始人s h 印i r 0m 分析后指出幅度越高的小波系 数对图像信噪比的影响越大，因此编码过程中应当优先对这些高幅度的小波系数 进行编码，这可以通过对小波系数的幅度进行排序来得到。由于幅度排序是为了 找出显著系数然后对其进行优先编码，因此幅度排序就变成了在空间树中依照一 定的规则有效查找显著系数位置的问题。s p i h t 算法通过集合树的分裂规则，有 。效地解决了高幅度小波系数的优先编码问题【2 0 】 2 。 e z w 算法和s p i h t 算法主要都是利用树形结构来表示重要系数，这两方法 都是利用了不同级别的高频子带之间不重要系数的相关性。s p e c k 算法与其不 同，它通过集合分裂的办法，采用块状结构，充分利用了子带内部的不重要系数 相关性。s p e c k 算法是图像编码算法中性能较好、编码较为容易的嵌入式图像 编解码算法。 2 4 2s p e c k 压缩算法 本文后续章节所有的实验都采用的是s p e c k 压缩算法，因此本节将详细介 绍s p e c k 压缩算法的原理 2 2 】【2 3 1 。 算法设计的集合定义： l i s ：不重要集合列表，用l l 子带进行初始化。 l s p ：重要系数集合列表。用来存放编码过程中的重要系数以便进一步量化。 集合s ：放置待处理的数据块，用最低频子带系数初始化。 集合i ：存放除了集合s 之外的剩余数据块的集合。 分裂规则： 以图2 5 为例，l l 3 为初始集合s ，剩下的9 个高频子带组成集合i ，如图 2 5 ( a ) 。如果需要对i 再次进行分裂，h l 3 ，l h 3 和h h 3 分别加入到集合s 中， 剩下的6 个集合组成i ，如图2 5 ( b ) 。图2 5 ( c ) 表示再次分裂后的s 集合和i 集合 的状况。 当集合s 中存在重要系数时，我们需要优先刻画重要系数，因此需要对集合 s 进行分裂。对s 进行的分裂按照四分集合块的原则进行。如图2 6 所示。 编码过程： 扫描全部系数，初始化阈值以及集合s 和i ，并清空l s p 。如果集合s 中有 重要系数，则要把集合s 进行四分。在分裂的过程中，如果分裂的结果依然是数 据块，且数据块内含有重要系数则继续对该数据块进行四分直到通过集合s 分裂 第二章基础知识 出的子集0 ( s ) 为一个单独的像素为止，如果此时像素为重要系数，则加入到 l s p 中。如果集合s 分裂的某个子集o s 中不存在重要系数，则将其加入l i s 中 供下一级阈值的时候再次处理，这一过程称为s p e c k 算法对重要系数的排序过 程。排序完毕后，算法需要对l s p 中的重要系数进行细化操作【2 4 】【2 5 】。 口 一耻 一| ，i 趣1 班 础 珊皿 l 勘 珊i 衄 曲口 趣趣 ( b ) 图2 5 集合s 和集合 m 皿 皿 图2 6 集合s 的四分图 整个算法的执行以阈值为中心，每一次排序及细化过程结束后都将对阈值进 行减半，然后重新扫描小波不重要系数，直到算法输出指定的码流长度或者闽值 变为零而结束。 s p e c k 算法采用易于计算和并行处理的块结构来消除小波系数内部不重要 系数的相关性，提高了算法的编码速度。由于集合块之间是独立编码，因而在传 输发生误码时，只会对产生误码的所在块有影响，而对其余数据块的数据重建没 有太大影响。 2 5 小波变换的优化平台 2 5 1 多核处理器平台 随着计算机行业日新月异的发展以及人类对计算机处理能力的要求不断提 高，c p u 的发展目前已经进入了多核时代。多核c p u 的出现打破了传统的串行 1 4 第二章基础知识 程序的运行方式，取而代之的是基于多线程技术的并行处理。多核处理器凭借其 更强大的并行处理能力以及更高的计算密度使得整个计算机行业正发生着巨大 的变化。 多核处理器已经成为现在处理器市场的主流产品。处理器的生产厂商在设计 多核处理器时在单个处理器芯片上集成两个或者更多的执行核，而这些执行核都 是相互独立的处理器单元，并且他们都有自己独立的执行集合及资源，即每个处 理器单元都有自己一个完整的硬件执行环境。这样，多核处理器的体系结构就为 多线程程序的并行执行提供了可行的条件【2 6 1 。多核处理器的结构示意如图2 7 所 示。 系统总线或自i 端总线 图2 7 多核处理器结构示意图 在多核处理器出现之前，多线程程序的运行都是通过在单核处理器上模拟而 达到，而这种方式的运行并没有从根本上使得多线程程序实现并行。多核平台通 过相应的调度算法使得多线程程序能够分配到各个执行核上，而由于执行核之间 的独立性使得执行核之间能够并行执行每个线程的任务。通过在执行核之间进行 任务调度，不仅可以降低每个执行核的工作负载，而且使得执行核之间可以并行 执行多线程任务，使得处理器资源能够得到更加充分的利用，进而达到提升整个 应用程序性能的目的。多核处理器的出现使得多线程程序设计变得越来越普及， 而多线程设计得是否合理直接关系着程序的运行性能以及运行结果的正确与否。 因此，多线程程序的设计需要合理分配每一个线程的任务、准确理解线程之间的 运行方式。 第二章基础知识 2 5 2c a c h e a w a r e 算法 高速缓存是位于c p u 和内存之间的临时存储器，它的容量比内存小，但是 访问速度却很快。高速缓存中的数据是内存中的一小部分，但这一小部分数据却 是短时期内c p u 即将访问的。当c p u 需要调用数据时，就可以避开较慢的内存 而直接从高速缓存中进行调用，从而加快读取数据的速度。由此可见，在c p u 中加入高速缓存是一种高效的速度提升方法，且整个存储结构就变成了既有高速 缓存的高速度也有内存的大容量的系统了。 高速缓存读取：c p u 要读取一个数据时，首先从高速缓存中查找，如果找到 就立即读取并送给c p u 处理，称为读取命中；如果没找到，就用相对慢的速度 从内存中读取并送给c p u 处理，这时称为读取缺失，同时c p u 把这个数据所在 的数据块调入高速缓存中，可以使得以后对整块数据的读取都从高速缓存中进 行，不再调用内存，降低了高速缓存和内存的数据交换时间。 高速缓存性能感知算法( c a c h e a w a r e ，或称为高速缓存参数相关算法) 是 指程序运行过程中对高层次存储器的存取次数达到最小化的一个优化算法，它的 设计目标在于程序运行过程中能够高效且最优地使用低层存储系统完成程序运 行【2 7 】。 由于c p u 在高速缓存和内存之间读取数据的速度差别很大，因此在高速缓 存模型上进行算法复杂度衡量时，算法的复杂度不仅跟算法的处理规模有关系， 同样还与高速缓存与内存之间数据交换的次数有着紧密的联系。 为了保证c p u 访问时有较高的命中率，c a c h e 中的内容应该按一定的算法替 换。一种常用的算法是“最近最少使用算法”( l i w 算法) ，它是将最近一段时间 内最少被访问过的行淘汰出局【2 8 】。c a c h e a w a r e 算法正是在l i w 替换算法下进 行设计的性能优化算法。 2 6 本章小结 本章首先给出了二维图像压缩的算法原理及目前主流图像压缩算法的分类， 详细介绍了每种压缩算法的技术背景以及算法优缺点；然后针对小波变换的理论 以及基于小波变换的多种图像压缩算法进行了分析，讨论了小波变换的系数特点 以及小波域图像压缩算法是如何利用小波系数特点从而达到图像压缩目的的；最 后针对本文在多核平台上对小波变换所作的性能优化工作，详细介绍了多核计算 平台的硬件知识和高速缓存的工作原理，并针对高速缓存的工作原理介绍了充分 利用高速缓存的高速缓存性能感知算法。 1 6 第三章基于w b c t 的图像编解码算法 第三章基于w b c t 的图像编解码算法 尽管小波变换是目前信号处理领域广泛使用的分析工具，但是由于小波变换 只能表征水平、垂直以及对角方向的信息，因而其在捕捉二维信号的奇异信息方 面并不是最佳选择。为了解决这一问题，研究人员相继提出了硒趣e l e t ，c u