（计算数学专业论文）低内存小波变换及其编码.pdf

国防科学技术大学研究生院学位论文 摘要 本文主要讨论基于小波变换的适合硬件实现的低内存图像压缩方法。 由于小波变换具有良好的去相关性，能置密集性，多分辨性，使得基于小波变换的图 像雎缩编码方案易于实现一些重要的极具吸引力的特征，例如。算法的低复杂度，压缩的 高性能，分辨率可调性。保真度可调性，精确的比特率控制等这些特征使得基于小波变 换的压缩方案成为当前压缩方法的丰流和研究热点但是目前基于小波变换的压缩系统还 远未成熟。当前，几乎所有基于小波的图像压缩算法都要求整幅图像在处理时被缓冲到内 存，凶此使得系统内存用量与图像尺寸成比例增长，这使得寻求高效低内存，硬件友好的 压缩算法成为迫切需要。 在许多图像压缩的应用中，尤其是对于面向大众市场的电子消费产品( 如打印机，数 码相机，p d a 等) ，为了维持低成本，内存是一个很重要的限制。而且，随着电子技术的 发展高分辨率，高质量的图片的获取与应用越来越普遍，如何用有限的内存处理大尺寸 图片已经成为一个越来越迫切的研究课题。 术文研究了低内存小波变换及其柏应的编码方法，通过研究了基于“行”的离散小波 变换( l i n e - b a s e dd i s c r e t ew a v e l e tt r a n s f o r m ，l b w t ) 的实现及其相关的编码方法( l i n e - b a s e dc o d i n g ，l b c ) ”“，基于“块”( b l o c k b y b l o c k ) 的小波变换9 14 1 等低内存变换方法 提出了基于“带”的离散小波变换( s t r i p e b a s e dd i s c r e t ew a v e l e t i 、- a n s f o r m ，s b w t ) 及其相 应的编码方法。 相对于l b w t ，s b v 、r t 具有更小的系统时延，而且其输出的变换系数结构更规范， 易于访问；另外结合本文提出的基于“带”的编码方法( m o d i f i e dl o wc o m p l e x i t ya n dl o w m e m o r ye n t r o p yc o d , ! r ，m l l e c ) 。构造了一个完整的高效、低复杂度、低内存消耗的图 像压缩系统，且该系统的内存消耗量只t _ i 待j 玉缩图像的宽度，所用小波滤波器组的长度， 及分解层数有关，而与图像高度无关。 关键词：离散小波变换，低内存实现，压缩编码，基于“带”的变换 第i 页 图防科学技术大学研究生院学住论文 a b s t r a c t i m a g ec o m p r e s s i o ns y s t e r nb a s e do nd i s c r e t ew a v e l e tt r a n s f o r m ( d w t ) h a sb e c o m ea n i n t e n s i v er e s e a r c ha r e ai nr e c e n ty e a r s d u et oi t ss u p e r i o rp e r f o r m a n c eo fe n e r g yc o m p a c t i n g a n dr e d u n d a n c yr e m o v a l d v 啊h a sb e e ni n c o r p o r a t e di n t od o z e n so fc o m p r e s s i o ns y s t e m s i n t e g r a t e dw i t hs o m ee l a b o r a t e l yd e s i g n e dc o d e c ，t h ec o m p r e s s e db i ts t r e a mc a nh a v es o m e v e r yd e s i r a b l ep r o p e r t i e s ，s u c ha sc o m p a r a t i v e l yh i g hp s n r ，r e s o l u t i o ns c a l a b i l i t y , f i d e l i t y p r o g t e s s i v i t y , e x a c tb i tr a t ec o n t r o la n dr e g i o no fi n t e r e s t e t c t h ei n c l u s i o no fd w ti n t h en e w e s ti m a g ec o m p r e s s i o ns t a n d a r do fj p e g 2 0 0 0 ”h a st r i g g e r e da no n g o i n ge f f o r tt o i m p r o v et h ei m p l e m e n t a t i o ne f f i c i e n c yo fd w t h o w e v e r ，a l m o s ta l la l g o r i t h m sa v a i l a b l en o wa s s u m et h a tt h ew h o l ei m a g ei sb u f f e r e d b e f o r ew to rc o d i n gw o r k s w h i c hw i l lb ei m p r a c t i c a li fi m p l a n t e dt ol o w - c a p a c i t yc o m p u t i n g p l a t f o r m s t h eg r e a tc o n s u m p t i o no fm e m o r yb yd w t o rd 、 7 t b a s e dc o d i n gh a sb e c o m e ak e yb o t t l e n e c kf o rt h ep o p u l a r i t yo fw a v e l e t b a s e dc o m p r e s s i o ns y s t e r n t ot a c k l et h i s p r o b l e m ，s o i i l 曼e x p e r t sh a v ep r e s e n t e dl o w - m e m o r ya n dl o w - c o m p l e x i t ya l g o r i t h m s ，a n l o n g w h i c hl b w t ”i so u t s t a n d i n gf o ri t sl o wm e m o r yd e m a n da n de f f i c i e n ti m p l e m e n t a t i o n a n d i th a sb e e ni n c l u d e di nj p e g 2 0 0 0 t h o u g hl b w ti sv e r ye f f i c i e n ti ni n e i n o r yu t i l i z a t i o n t h ec o d i n gs d i c n l cc o u p l e dw i t h i t ie 1 i n + b a s e dc o d i n g ( l b c ) ”“h a st ou s es o m e w h a tc o m p l e xc o n t e x ti n f o r m a t i o n a n d a b o v ea l l - u t i l i z eah i g h c o m p l e x i t ye n t r o p yc o d e r a r i t h m e t i cc o d e r “w h i c hi sn o ts u i t a b l ef o rh a r d w a r ei m p l e m e n t a t i o no nl o w - c a p a c i t yc o m p u t i n gp l a t f o r m si nt h i sp a p e r ，w e w i l lp r e s e n ta l o w - m e m o r y ，l o w - c o m p l e x i t y , h a r d w a r e - f r i e n d l y , y e te f f i c i e n tc o m p r e s s i o ns y s t e r nb a s e do nan o v e ls t r i p e b a s e dw a v e l e tt r a n s f o r mp r o p o s e da n da ni m p r o v e dv e r s i o no f l l e c t 9 1 t h i sp a p e rp r o p o s e san o v e ll o c a lw a v e l e tt r a p s f o i t nt e c h n i q u ec a l l e ds t r i p e - b a s e dw t ( s b w t ) w h i c hi sv e r ys u i t a b l ef o rp a r e n t c h i l d r e nt r e e ( p c t ) - b a s e dc o d i n g c o m p a r e d t ot h ef a m o p sl i n e - b a s e dw a v e l e tt r a n s f o r mf l b w t l s b 、v tp r o v i d e sl e s sl a t e n c yt op c t s t r u c t u r ep r o d u c t i o na n dl e s st o t a lm e m o r yc o n s u m p t i o nf o rt h ew h o l es y s t e m f u r t h e r m o r e ae n t r o p yc o d i n gm e t h o d ，c a l l e dm l l e ci sp r o p o s o d ，w h i c h1 1 8 sl o wc o m p u t a t i o n a la n d m e m o r yc o m p l e x i t ya n dh i g hc o m p r e s s i o ne f f i c i e n c y c o u p l e dw i t hm - l l e c ，t h ep r o p o s e dc o m p r e s s i o ns c h e m ep r o v i d e sc o m p e t i t i v eh i g h p s n r w i t hr e s p e c tt ot h eb e n d t i n a r ka l g u r i t h ms p i h t w h i l ec o m p u t a t i o n a lc o m p l e x i t y a n dm e m o r yd e m a n da r eg r e a t l yr e d u c e d k e yw o r d s ：w a v e l e t s ，l o w - l n c l n o r y ，i m a g cc o m p r e s s i o nc o d i n g ，l o c a lw a v e l e tt r a n s f o r m ，s t r i p e - b a s e dw a v e l e tt r a n s f o r m h a r d w a r e - f r i e n d l yi m p l e m e n t a t i o n 第i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特另0 加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 筮盘盔尘遽变挟盈甚翁璺 学位论文作者签名：丞丝明 日期：乃哆年月卵 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书) 学位论文题目： 篮由盔尘遮銮抉区基籀翌 学位论文作者张亟鎏幽； 吼弼年，月如 作者指导教师签名：盥薄吼劢多年，月历 里堕翌堂垫查查兰塑壅竺些主篁堡苎 图像雎缩系统示意图 矩阵的似乎面分解 阁像的位平面分解 图像保真度性渐进性示意图 图像分辨率渐进性示意阉 小波分解，示意图 分辨率可调性示意图 插图目录 基f ：滤波器的d w t 分解示意罔 基于滤波器实现的d w t 承栅示意图 令点及! | t i 对称延拓示意i 鲥 初始化时系统“j 意嘲 寄存器元索分布示意图 p q 分别为高、低通滤波j 下采样的结台， 输出系数所处的子带与时闷的关系 a n a l y s i so b j e c t 的封装示意图 a n a l y s i so b j e ( ：t n , j 结构示意翻 分析系统的摘化表示以分解3 层为例1 综合系统示意图f 以分解3 层为例) t = 4 时刻滤波系统存储示意圈 c d f 9 t d x 波分解3 层。z = 晶= 2 8 j , j 系统示意网 移位寄存器实现示意圈 ：i 层( t h m l r w l ) 小波分解厢的小波系数矩阱 襞合d ，l 示意图 p c t 结构示意图 m l l e c 编码扫描顺序示意吲 第i i 页 3 0 0 0 0 0 m u坫盟玛弘船舱孙卯凹 昌；蛎驰 a b n 1 2 3 4 h 蝴粥叫粥”粥抛m“儿 叭抛“ 因防科学投术大学研究生院学位论文 2 - 1 各种d w t 所需缓存精比较袭 4 - i 各种艟缩算法的p s n r 比较 表格目录 3 2 4 7 第i i i 页 国防科学技术大学研究生院学位论文 1 1 i 基本概念 第一章绪论 1 1压缩编码概述 本章介绍了与图像的鹾缩编码相关的基本概念在下面的论述中，待处理的原始图 像数据用矩阵，表示，中的元素i ( x ，) 表示图像中位于第y 行、第z 列( 索引从0 开始) 上像素 的灰度值，不妨设图像为h 行w 列，则有，z = 0 ，l ，w 一1 ；= 0 ，1 ，一1 。在 图像的压缩编码中，所处理的对象可认为是，经过某种变换，量化后所得到的一个整数矩 阵，记为y ( z ，) 。 编码器与解码器 编码器( e n c o d e r ) ：一种将矩阵量化后所得的矩阵y ( z ，) 映射为比特流( b i t st r e a m ) b 的 映射； 解码器( d e c o d e r ) ：一种将比特流b 映射为重构矩阵的映射。 图像压缩与解压流程 ，叵卜c 廿p 避 嘏 圈 鲢 梃 寺 群 科 螭 孛c 臻 也 0 谣 掌 枯 再f 丽 鹰譬镬! 审窜审j 啼檗罅： 。1 一 编码 矿毋e 廿j 毒i f 0 甚 谣 餐 图1 - 1图像压缩系统示意图 鹾 芒 盛 筹 窖 c 端 瞄 糕 喜| f 圃 鲢 在流程图1 - 1 中编码所处的位置已用虚线框出。 无损编码( 1 0 s s l e s sc o d i n g ) 及有损编码( 1 0 s s yc o d i n g ) 在图l 一1 所示的流程图中，如果v = 矿，则编码称为无损编码。如果v 矿，则编码称为 有损编码。 编码的比特率( b i t r a t e l r = l ( w h ) ，其中l = l e n g t h ( b ) ，即为比特流b 的长度，l 的单位为：位( m ) ；r 的意 义是原始图像每象素在b 中平均所占用的位。 编码方法的评估 无损编码：比特率，算法复杂性，所需要的资源，压缩码流b 所具有的特征等： 第1 页 噶科_ 幂 曩喾皋r髫峰hw 国防科学技术大学研究生院学位论文 有损编码：相同比特率下重建图像的质量，算法复杂性，所需要的资源避缩后所得 比特流_ 8 所具有的特征等。 对编码方法的评估不应孤立地进行，应该放到整个图像压缩系统中去考虑，不光要考虑该 编码方法的性能，还要考虑其同整个系统中其他关键环节的相互作用的复杂性等， 重建图像的质量的评价 均方误著( m s e ) d c i ，) = 斋( 炳，n ) 一j ( m ，n ) ) 2 一mn 在本文所讨论的图像压缩系统中变换采用的是具有线性相化的对称双正交小波变 换，该变换非常接近正交变换。因此有 d ( i ，j ) d ( c ，0 ) 利用上式我们可以在变换域对重构图像的失真进行估计。 p s n r p s n k = 1 0 崦，。苦 其中g 为灰度图可能出现的最大灰度值。 位平面( b i t p l a n e ) 编码 对于元素均为正整数的矩阵而言位平面分解是一种将其分解成一系列元素在集 合 0 ，1 ) 上取值的矩阵。设m 为一正整数矩阵m 的位平面分解如下所示：记m = m j m ( i ，j ) l ，即m 中的最大幅值，则m 可分解为n = 1 + ! l o mj 个比特平面；易知n 为 表示m 中最大幅值所需的最少的二进制位的数目。例如，对图i 一2 中矩阵k 而言，其最大 幅值为1 5 ，所需的位平面数n = 1 + 【1 0 1 5l = 4 。然后将m 中所有元素的第n 位有效数字 取出，其在矩阵中所处的位置不变，得到位平面n ：依次可得比特平面n 一1 ，1 。一个 具体的例子如图1 2 ，其中，左上角为个4 4 的矩阵，下面为其位平面分解所得的4 个位 平面。图1 3 为l e n a 图及其相应的位平面分解，从该图可以看出。低能面的图比高位面的 图复杂，包含了更多的细节，变化更随机。相对而言，高位面包含了大部分的视觉重要信 息。凼此在编码时，可以依次从高位面到低位面进行编码，这样解码时，首先得到的 足对视觉最重要的信息，然后是次重要信息( 譬如细节、纹理等) 。位平面编码对于渐进式 图像编码十分重要，但是在图像的压缩编码中，我们所处理韵对象是图像经过小波变换 并量化后所得的系数，有可能为负值。因此有必要考虑包含负数的整数矩阵的位平面分 解。设为一整数矩阵，的何平面分解与对正整数矩阵m 的位平面分解类似，此时，矩 阵可分解为一系列素在集合 0 ，+ 1 ，一1 ) 上取值的矩阵。此时又需将n 中元素的符号赋予 该元素对应的非零的最高位有效数字，其他做法孑正整数矩胯的分解柏瑚。 旺1 2 码流所具有的特性 在上面已经提到，评价一种编码方法，不仅要考虑计算复杂性r 所占用的资源等，还 要考虑比特流b 所具有的性质；压缩后的比特流日可能具有以下性质： 第2 页 国防科学技术大学研究生院学位论文 o o o l0 0 1 0o o l l0 1 0 0 0 1 0 10 1 1 00 1 l l1 0 0 0 l o o ll o l o 1 0 l l 1 1 0 0 l l o l1 1 l ol l l l0 0 0 0 矩阵k ( 二进制) 翮麓霹圈 位平面4位平面3位平面2位平面1 图1 - 2 矩阵的位平面分解 图1 - 3 图像的位平面分解 第3 页 国防科学技术大学研究生院学位论文 1 可调性( s c a l a b i l i t y ) 码流口具有某种可调性指的是解码器可以从单个的压缩码流b 中解艋出适合多种 不同应用场合( 譬如，不同的分辨率，不同的码率，不同的保真度等) 的重建图像。随 着i n t e r n e t 的普及，网络技术的发展，可调性的应用变得越来越广泛。例如。在多媒体视 频的分级广播中，必须根据网络带宽及用户权限等对视频进行分级，一些高权限、高带宽 的用户可以获得高分辨率、高保真度的图像；低权限、低带宽的用户恰好相反；这就要求 服务器使用的码流具有分辨率、保真度的可调性，可以根据一个单一码流对数据进行分级 控制，而不必为每一类用户单独准备一个码流，极大地提高了分级广播的效率。码流的可 调性种类很多，下面简要介绍几种重要的可调性。 保真度渐进性( f i d e l i t yp r o g r e s s i v i t y ) 保真度渐进性一个直观的定义是，对b 中越来越多的位进行解码，可以得到一个保真度越 来越高的图像。若存在m 2 个码流b 。，b 2 ，风，其均为保留b 的前若干位所得到的b 的 子比特流，且有b 1cb 2c cb ，由鼠所得的重构图像的保真度用f ( 鼠) 表示，如果 有f ( b 1 ) f ( b 2 ) f ( 风) ，则称码流b 是保真度可渐近性的。b 的可渐进性的强弱 根据编码方法的不删有很大的差别，例如对于s p i h t ”“，日。卜j b ；+ 。之问相差可以不超过2 b i t s ；而对于最近提出的j p e g 2 0 0 0 9 + ”1 标准中，可以不超过l o ，也即可达的保真度数目 变化可能相差很大。 保真度可解释性( f i d e l i t yp a r s a b i l i t y ) 所谓保真度可解释性，指的是解码器可以从同一个码流b 中解码出不同保真度的图像。 若存在2 个码流b 。，岛，既，均为从b 抽取若干位所得到的子比特流，鼠c b ，v1si ，且f ( b 1 ) f ( 岛) f ( b i ) ，则称码流b 是保真度可解释的。 从上面的定义中可以看出保真度可解释性比保真度渐进性的要求要宽松；如果b 是保真 度渐进性的，则其一定是保真度可解释性的，反之则不一定成立。 ：者定义中的不i 可之处 在于保真度渐进性的定义中，最是由引屎留前若干位所得到的：而保真度可解释性的定义 中则只要求鼠是从b 中抽取若干位所得到的。 保真度渐进性和保真度可解释性统称为保真可调性；图l 一4 以l e n a 图为例，展示了保真度 可调性的概念该图上半部为三个比特流b 1 ，三 2 ，岛的示意图，下半部则分别为其对应 的重构图像。 分辨率渐进性( r e s o l u t i o np r o g r e s s i v i t y ) 分辨率渐进性指的是解码器可以通过对码流b 的开头的部分进行解码，得出一个分辨率较 低的重构图像。其具体定义与保真度渐进性类似，不再赘述。 图1 - 5 为分辨率渐进性示意图，图中下半部为码流b 1 ，b 2 ，b 3 对应的3 幅不l 司分辨 率r ，冗2 ，几的重构图像。 分辨率可解释性( r e s o l u t i o np a r s a b i l i t y ) 分辨率可解释性指的解弼器可以通过遍历b ，提取b 中若干b i t s ，并只对该部分进行解 码可以得到若干不同分辨率的重构图像：其具体定义类似保真度可解释性，不再赘述。 图1 6 a 为一图像的3 层d w t 分解。在图中标出了其对应的予带，基于左图的分解。最多 可得4 种分辨率的重建图像，图1 6 b 中分别标出了重构这4 种分辨率r l ，危，凡，风要 第4 页 国防科学技术大学研究生院学位论文 比特流口 比特流增长方向 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - _ 马马岛 且 图1 - 4 图像保真度性渐进性示意图 第5 页 垦堕型堂垫查奎兰竺茎生些堂堡笙兰 用到的各个子带，要得到分辨率为兄1 的重构图像，解码器只需从日中提取出标记为r 1 的 予带系数；要得到分辨率为r 2 的图像，只需从b 中提取出标记为r l 及r 2 韵系数即可：对 于r 3 ，则需标记为冗”月2 、凰系数。 比特流口 罩罂 图i - 5 图像分辨率渐进性示意图 l l 2 1 h l 2 l h 2 1 h h 2 h l i h l 0 l h ih h l l h 0 h h 0 制 r r i r 黜 mr 4 图1 6 a 小波分解示意图图i - 6 b 分辨率可调性示意图 2 随机访问( r a n d o ma c c e s s l 解码器可以通过遍历日，并只对b 中的部分b i t s 进行解码，就可以得到事先指定的原 始图像部分区域的重构图像。 3 感兴趣区域( r o l l 所谓的r , o i ( r c g i o no fi n t c m s t ) 指的是在重构图像中期望保真度高于其它部分的图 像区域，也即图像质量在r o i 和背景之间的分布不同。图像压缩中的r o i 可以分为以下两 类： 第6 页 国防科学技术大学研究生院学位论文 静态r o i ( s t a t i cr o i ) ：静态r o i 指的是在编码之前就被指定的r o i ，该r o i 一旦被 确定下来，就不能再更改。 ( i ) 动态r o i ( d y n a m i cr o i ) ：在网络应用中，图像是渐进式传输地，此时动态r o i 是 在用户服务器这样一种交互类型的应用中被使用的。此种类型的r o i 适合于远程医疗等 应用场合，该r o i 在传输过程中可以由用户进行动态的修改。譬如在远程医疗中，医生所 关注的区域可能随时改变，这要求服务器( 解码器) 可以对其进行动态响应。 实现r o i 的主要思想是，在图像d w t 变换后的系数矩阵中定位出与r 。i 有关联的 系数，然后对这些系数进行编码时。给予高的保真度。一般而言，实现r o i 时需 要在压缩码流中保留原始r o i 的形状信息，但是目前已经出现了一些高效的静态r o i 算 法，如j p e g 2 0 0 0 标准中采用的m a x s h i f t 法”“1 ，p s b s h i f t ”“( p a r t i a ls i g n i f i c a n tb i t p l a n e s s h i f tm e t h o d ) ，b b b s h i r ”( b i t p l a n e - b y b i t p l m ms h i f t ) 等。使用这些r o i 方法时无需在码 流中显式地保留r o i 的形状信息，却可以实现任意形状的r o i 。 1 2 压缩编码的发展现状 考虑到小波变换具有很好的去冗余性、去相关性，对适合小波变换的图像艟缩编码算 法的探索已成为当前的研究热点并且出现了为数众多的基于小波变换的图像雎缩编码算 法。小波变换近年来在静态图像和视频压缩得到了空前的应用。由于小波具有多分辨率特 性，出现了众多的渐进式图像编码方法；这些编码方法在图像浏览、多媒体应用、数字媒 体的分级传输等应用中取得了空前的成功：例如，使用渐进式图像编码，存储在图像数据 库中的单个的图像压缩文件就足以用来满足多种不问比特率，分辨率的输出设备的需求， 在当前比特率或者分辨率条件下可获德最佳的图像质量。 目前，国内对低内存小波变换及其编码方法研究较少，大部分的研究都集中在如何 提高重构图像的p s n r 及降低其变换或编码运算量等方面；国外已经开始了这方面的研 究，但是其相关技术还很不成熟，处于起步阶段，相关的文献也相当少。目前，国外出现 了基于“行”的离散小波变换( l i n e b a s e dw a v e l e tt r a n s f o r m ) ，基于“行”的编码( l i n e - b a s e d c o d e c ) 以及基于“块? 的离散小波变换( b l o c k b y b l o c kw a v e l e t ，i r a n s f o r i n ) 等；但是由于编 码时，可供利用的伞局信息较少，如何有效地对变换后的系数进行编 i 1 5 仍然值得研究。 1 3 本文的主要工作 近年来，小波变换的内存需要已经成为阻碍基于小波的图像压缩方法得到广泛应用的 一个瓶颈，因此这方面的研究已经成为当前热点。目前，已经出现了一些低内存的实现方 法，如基于。行”的变换、编码，基于“块”的变换、编码等。在这方面的研究对于基于小 波的压缩系统的硬件实现具有重要的意义。 但是目前这些方案都有一些缺点，如基于“行”的小波变换( l b w t ) 及其编码( l b c ) ， 虽然内存消耗减小了，但是其编码复杂度太高，尤其是其采用了高度复杂的熵编码方 案一算术编码，另外该编码方案还使用了复杂的上下文信息，这些特征使得其不利于在低 计算能力平台上的实现，如手机，p d a ，数据相机等。 本文提出了一个完整的低内存消耗、低复杂度的图像雎缩方案。 第7 页 国防科学技术大学研究生院学 让论文 提出了基于“带，的d w t ( s b w t ) ，相对于l b w t 及基于“块”的d w t 而言，该方法所 消耗的总体内存更小，而且有着更小的时延此外，该方案中的分析变换系统的输出结构 很规范，特别适合予变换系数的零树量化( z e r o t r e eq u a n t i z a t i o n ) ，类s p i h t 编码等的实 现。 为了得到一个完整的硬件友好的压缩方案结合s b w t ，本文提出了基于“带”的 编码f m l l e c ) 方案，该编码方案只用到移位，分枝及比较操作。运算复杂度极低， 特别适合于低计算能力平台的硬件实现。此外，相对于其他较成熟的压缩方案 女 i s p h i t ，e b c o t 等而言，该方案的压缩效率也极具竞争力。 第8 页 曼堕型茎垫查奎主婴圣兰堕茎堡堡苎 第二章低内存小波变换技术 目前，低内存图像压缩系统主要采取以下两种方案： 第一种方案是将图像分为大小合适独立的块，每个块分别当作一个子图像进 行d w t 变换，每个块分别进行编码，在对一个图像块进行压缩时不会用到其他块的 信息，也即有，各个子图像块的处理分别是独立的。目前，有很多压缩方案采取这种做 法，女i j p e g 2 0 0 0 ”6 ”1 ，基于分块的s p i h t ”“，基于分块的s p e c k ”6 ，s b h p ”1 等。这种 方案有利于压缩算法的低内存实现，复杂度的降低。此外，另一个显著的优点是易于实 现r o i ，由于图像各块是独立缢缩的，故其所产生的码流是不柏关的这样，如果只要求 访问其中的一个分块，则可以只提取比特流中与该块相关的b i t s ，而不必对码流的其他部 分进行访问。但是该方案有一个致命的弱点，即在低比特率下，图像会出现非常明显的 边块效应( b o u n d a r ye f f e c t s ) 。整个雎缩图像看起来不是很自然，存块边界处有突变。此 外，由于对图像进行了分割，编码其中某块时可用的信息柏对整体变换而言较少，压缩效 率有所降低。而且，在控制码率时，需要考虑块问的比特率分配等问题。 另一种方案是对图像进行所谓的“局部小波变换”( l o c a lw a v e l e tt r a n s f o r m ，l w t ) ， 即对原来的d w t 变换进行优化，采用低内存实现，但变换后的系数和经典“行列 法”( 1 = g o w c o l u m nm e t h o d ) 得出的结果一致。目前现有的方案有基于“行”的d w t ( l b w t ) ”。6 1 ”1 ，基于“块”的d w t ( b l o c k b y b l o c kd w t ) 9 。，这些l w t 的一个重要特点是 虽然其变换所需的内存与“行列法”相比急剧下降，但是变换后的系数和“行列法”所得的 变换系数完全相同。 本文丰要讨论后一种低内存解决方案。往本章里，先介绍离散小波变换( d w t l ，并 对基于滤波器实现的离散小波变换进行了详细的讨论。接着为了分析变换系数对待变换序 列的依赖关系，讨论了小波滤波器组重构滤波器系数的“叠混”。 由于实际应用中的图像为有限的离散信号，为了将d w t 应用于图像雎缩，在本章中 还讨论了信号的延拓问题，并给出了与其相对应的d w t 变换算法。 最后，在分析l b w t 的基础上，提出了一种新的l w t s b w t ，相对于其他l 、v t ， 该方案有着更小的内存消耗和系统时延。结合本文提出的m l l e c 编码方法，可以构造一 个低内存，易于硬件实现的图像压缩系统。 2 1图像压缩中的离散小波变换 对于图像压缩应用，一般采用具有线性相传，对称性的双正交小波滤波器组”1 ；不 失一般性在下面的论述中，只讨论双正交的。滤波器具有奇数长度的对称性小波滤波器 组。 考虑1 dd y a d i c 离散小波变换。用。表示待处理的序列用k 及h k 分别表示第k 层分解 后的低通，高通序列。这两个序列是通过对k 一。滤波并进行下采样得到；为了记号上的统 一我们用f o 表示原始待处理的数据序列。记d w t 滤波器组中的小波分解低高通滤波器 分别为“，上匕，重构滤波器组中的低高通滤波器分别为厶，风，且这4 个滤波器的晟大 第9 页 曼堕型堂垫查查鲎型茎兰坚主竺堡苎 长度记为l = 2 s + 1 。 图2 - 1 基于滤波器的d w t 分解示意图 原始数据序列f o 可咀写作： l 。：匦耍固面压圃巫豳卫叵压囹 如图2 1 所示，序列f o 经过分解滤波器组的低通f i r 滤波器滤波并进行下采样可得f ， 经过一个该滤波器组的高通f i r 滤波器滤波并进行下采样得h ，： 2 1 ：lt l o lf 1 【1 lf l 【2 l z 1 【3 1 f l 【4 】卜 h i ：lh l 0 】i l 【1 】ih 1 1 2 】lh 1 1 3 】ih i 4 】| 下采样器保留低通滤波后数据的索引为偶数的项( 索引从0 开始) ，得到f ，：对于高通 滤波器，则保留高通滤波后索引为奇数的项，得到h l 。放在时问轴上，数据f l ，h 1 的排布 为 1 1 ：f 1 【o f l 【1 】h 2 】h 3 1f l 4 】 h 1 ： ，【o 】h i f l 】h i 【2 lh i 【3 】h 1 1 4 】 其中，空白的方格表示下采样时被抽取掉的元素，于是可以将f 1 ，h 1 “混叠”在一起， 得序列1 ： y t ：匦叮丑叮亘巫耍匝固卫匦匹亘圃卫团 由上面的关系知： 训n 】_ l l k 乩 , 当当。n = ：2 2 k k l n + l1 时 于是d w t 变换关系式可写为： l f 。坼一叫l a k 】，当n 为偶数时 y z 【n 】= 了8 l f o h 一翻h a k 】，当n 为奇数时 若将l 用卯表示，将只4 用9 1 表示，则上式可简写成： s v 1 m = 蛐一叫g ( n m o d 2 ) k = - s 于是基于滤波器实现的d w t 可用算法2 1 描述。 ( 2 - 1 ) 第1 0 页 翔= i d w t ( i n v e r s ed w t ) ，我们将在2 2 节中进行讨论。 2 2滤波器系数的“叠混， 图2 - 2 基于滤波器实现的d 、v t 重构示意图 如图2 2 所示，1 1 ， 1 分别为变换系数的低、高频分量序列：没f 1 经过偶上采样f 采样 凶子为2 ) 后得序列1 ，h 1 经过奇上采样( 采样因子为2 ) 后得序列i l ，则有 碓】= 制0 ，, 当当晃k ：= 2 2 。m + 1 仆 h 雕当k ：。2 m 。+ 1 如2 1 节所述，若l 为2 j ，h j 的“叠混一序列，则有 亘 】= g l 【l ( 1 一( m o d2 ) ) 1 = y a k 】( 女r o o d2 ) 设蠢为重构序列，则有： f 0 m = 五卧厶匝一捌+ 五，卧风f n 一叫 = y t ”( 1 一( r o o d2 ) ) 帅一叫+ 删( r o o d2 ) 也【n 一纠 = 乏二y ，【纠 l h 一叫( 1 晴r o o d2 ) ) + 玩k 一叫( 奄。d2 ) ) ( 2 - 2 ) 第1 l 页 国防科学技术大学研究生院学位论文 将式( 2 2 ) 中的求和指标由换为n k ，则有： i o n = y - h 一叫 l 。啤】+ ( 1 一( ( n 一女) m 。d2 ) ) + n k l 。( ( 仃一) m 。d2 ) ) ( 2 - 3 ) k z 故式( 2 3 ) 可按n 的奇偶性讨论： 当托为偶数时 f 0 1 - 1 = v ，h 一硝 l s i 捌( 1 一( ( 竹一) r o o d2 ) ) + h s 【硝( ( 礼一k ) m 。d 2 ) k e z = 可- b 一”慨【小( 1 一( ( 一) m o d2 ) ) + 风”( ( 一女) r o o d2 ) ) z = 掣h 一叫 l 。【叫- ( 1 一( r o o d2 ) ) + 巩【叫。( r o o d2 ) ) t z 若记 l 。【叫= l 。l 叫( 1 一( k r o o d2 ) ) 十月。陋】( k r o o d9 ) 则此时有 若记 f o m = t n 一翻己 k z ( 2 4 ) k 】 l 。 翻( 1 ( ( n 一颤) m o d 2 ) ) + h ；i q ( ( n 一) r o o d 2 ) k 1 l 。 女】( 1 ( ( 1 一k ) r o o d2 ) ) + h 。【叫( ( 1 一k ) r o o d2 ) ) = 9 1 h 一叫m 卧( r o o d2 ) + 风阶( 1 一( r o o d2 ) ) k e z 则此时有 觅 纠= l 。【q ( r o o d2 ) 十h 。【州( 1 一( 女r o o d2 ) ) i 0 n = y t h 一叫鼠 k z ( 2 - 5 ) 于是由式( 2 - 4 ) 及( 2 5 ) 知觅s t l 。均为l ，圮按一定模式“叠混”而成的序列，且它们具 有下列模式： 索引 i 一4 32一lo 123 4i 厶 fl 一4 l 风 3 】l 。f 一2 】e 卜l j厶f o |皿f l j厶 2 j峨 3 厶( 4 j h 5 i 风【_ 4 l 。 - 3 】巩【- 2 l 。卜1 l风1 0 】l 【1 】皿1 2 】l 。【3 】 见【4 】 又由l 。b x = 2 s 十1 知，l 。，风满足： 风【嘲= l 。 叫= 0 ，当l i s + l 时 第1 2 页 研 h 玑 5 ： 时鼬她 数j | | j 奇州为u 扎当 国防科学技术大学研究生院学位论文 故对于z 。，觅也有： 豆，【叫= z 。陋】= 0 ，当1 l s + 1 时 例如聂j - t c d f 9 7 t 、波，“叠混”模式如下 l 索引 一43二21ol 2 3 4 l 厶风【一3 】l 。【- 2 】风 - 1 ll 。【0 1风【1 ll 。【2 】风【3 1 l 风风【一4 】l 。 - 3 1趣卜2 】l 。 - 1 l凰f 0 1l 。 1 1凰【2 ll 。【3 l风【4 】 若分别用p o ，p l 表示三。，氲，则与式( 2 一1 ) 类似，重构方程可简写为 s f 0 m = 玑i n 一小p ( ，i r o o d2 “叫 ( 2 6 ) k = 一s 于是，可得使用“叠混”的重构滤波器系数己，盈的d w t 重构算法如算法2 2 。 2 3 边界处理 由于所有的图像处理应用中数据是有限长的，所以应用离散小波变换时必须对边界点 进行特殊处理，实际操作中应用得最多的就是所谓的边界延拓( b o u n d a r ye x t e n s i o n ) 。边 界处理的目的是，尽可能地保留小波滤波器组的重构性，数据速率，以及最大限度地减小 边块效应( b o u n d a r ye f f e c t ) 。 许多文献都对边界处理进行了研究；目前，主要有两种做法，一种是对小波滤波 器组的结构进行改造”0 1 ；另一种做法，先是对信号进行边界延拓，然后再进行滤波处 理2 ”“。 本节主要讨论后一种方案，即边界延拓。 第1 3 页 鬯堕型堂垫查查兰型塞尘堕堂垡堡兰 2 3 1 零填充( z e r op a d d i n