（计算机系统结构专业论文）多核机群下基于小波原理的并行图像压缩与解压缩.pdf

内蒙古大学硕士学位论文 多核机群下基于小波原理的并行图像压缩与解压缩 摘要 图像压缩技术是多媒体技术研究的重点问题，其中嵌入式零树小波压缩 ：? 算法又被认为是迄今为止最有效的压缩算法，但因为压缩过程是一个耗时的 过程，所以为了更好地扩展嵌入式零树小波压缩算法的应用，应该寻求更为 有效的方法来缩短压缩时间。随着计算机技术的不断发展，多核技术应运而 生，这也使并行技术得到了长足的发展。本论文就是将多核技术与嵌入式零 树小波压缩方法相结合，在得到好的压缩效果的同时也缩短了压缩时间。本 文首先介绍了串行嵌入式零树算法的实现过程。然后介绍了嵌入式零树算法 是如何在多核机群上实现并行化的，并给出两种并行算法：第一种是仅使用 m p i 编程模式的并行算法，该算法实现的是机群各节点间的并行化，第二种 是使用了m p i + o p e n m p 混合并行算法。混合并行算法由m p i 实现节点间的并 行化，o p e n m p 实现节点内部的并行化，即实现了两级并行。最后通过实验 分析了串行程序的效果、对比了串行程序与并行程序的性能。结果表明，嵌 入式零树算法的图像恢复效果很理想。同时，发现随着数据量的增多，不论 m p i 并行算法还是m p i + o p e n m p 并行算法相对于串行算法的运行效率都有明 显的提高，其中又以m p i + o p e n m p 并行算法的效果最好。 关键词：多核机群，图像压缩，小波，嵌入式零树小波编码，m p i ，i + o p e n m v 多核机群下基于小波原理的并行图像压缩与解压缩 p a r a l l e li m a g ec o p r e s s i o na n dd e c o m p r e s s i o n b a s e do n ，a v e l e tp r i n c i p l eo nm u l 月i c o r ec l u s t e r a b s t r a c t t h et e c h n i q u eo fi m a g ec o m p r e s s i o ni st h ei m p o r t a n ta r e ao fm u l t i m e d i a r e s e a r c h t h ee z w ( e m b e d e dz e r o t r e ew a v e l e t ) i sd e e m e dt ob et h em o s te f f i c i e n c t a l g o r i t h mf o ri m a g ec o m p r e s s i o n i m a g ec o m p r e s s i o ni sat i m e - c o n s u m i n gp r o c e s s ， t h e r e f o r eam o r ee f f e c t i v em e t h o ds h o u l db ef o u n df o re x t e n d i n gt h ea p p l i c a t i o no f e z w i nt h i st h e s i s ，m u l t i c o r ei sc o m b i n e dw i t ht h ee z w w h i l eg o o dc o m p r e s s i o n e f f e c ti so b t a i n e d ，t h eq u i c k e rc o m p r e s s i o nt i m ei s g e a e d f i r s to fa l l ，h o wt o a c t u a l i z es e r i a le z w a l g o r i t h mi si n t r o d u c e d s e c o n d l y ，h o wt oa c t u a l i z ep a r a l l e l a l g o r i t h mo nm u l t i c o r ec l u s t e ri si n t r u d u c e d t w om e t h o d sf o rp a r a l l e la l g o r i t h m a r eg i v e ni nt h i sp e r i o d t h ef i r s tm e t h o di n v o l v e sa p p l i c a t i o no fm p ip r o g r a m m i n g m o d e ，w h i c hr e a l i z e sp a r a l l e l i z a t i o na m o n gc l u s t e rn o d e s t h es e c o n de m p l o y sm p i + o p e n m ph y b r i dp a r a l l e lp r o g r a m m i n gm o d e ，i nw h i c hm p is t i l l a c t u a l i z et h e p a r a l l e l i z a t i o na m o n gc l u s t e rn o d e s ，b u to p e n m pa c t u a l i z et h ep a r a l l e l i z a t i o ni n n o d e a tl a s t ，t h ee f f e c to fs e r i a lp r o g r a mi sa n a l y z e da n dt h ep e r f o r m a n c eo fs e r i a l a l g o r i t h mi sc o m p a r e dt op a r a l l e la l g o r i t h m t h er e s u l ts h o w st h a tt h ee f f i c i e n c yo f i m a g ec o m e b a c ki sv e r yw e l l a n da st h en u m b e ro fd e a l i n gw i t hd a t ai n c r e a s e i n g ， t h ee f f i c i e n c yo ft w op a r a l l e la l g o r i t h m si si m p r o v e do b v i o u s l y f u r t h e r m o r et h e e f f e c to fm p i + o p e n m p p r o g r a mi sb e t t e rt h a nt h a to ft h em p ip r o g r a m i i 内蒙古大学硕上学位论文 k e y w o r d s ：m u l t i - c o r ec l u s t e r ，i m a g ec o m p r e s s i o n ，w a v e l e t ，e z w ( e m b e d d e d z e r o t r e ew a v e l e t ) ，m p i ，m p i + o p e n m p i i i 内蒙古大学硕七学位论文 图表目录 图2 1 小波的特性3 图2 2 小波变换8 图2 3l e n a 三级小波变换：矗8 图3 1 图像压缩分类。1 3 图3 2 零树构造一一1 4 图3 3 扫描次序一1 5 图3 4 量化过程1 5 图4 1m p i + o p e n m p 混合编程模型18 图4 2m p i + o p e n m p 混合编程模型实现1 9 图5 1 列变换2 3 图5 2l e n a 一级小波分解2 3 图5 3 图像原数据2 3 图5 4 图像三级小波变换后数据2 3 图5 5 四叉树在图像矩阵中的位置2 4 图5 6 图5 5 中的一棵四叉树2 4 图5 7 比较树。2 6 图5 83 个队列的图示2 7 图5 9t 兰1 2 8 ，量化后第一棵树的结果2 7 图5 1 0 解压缩主表、辅表流程图2 9 图5 1 1i = 0 时，s e tn e wl i s t 数值。2 9 图5 1 2i = 0 时，d a t a 数值2 9 图5 1 3 大于阀值像素点的细化3 0 图5 1 4i = l 时，大于阀值像素点细化后d a t a 的数值3 0 图5 1 5 图1 的原始图及7 次量化效果图3 1 图5 1 6 图l e n a 的原始图及7 次量化效果图3 2 图5 1 7 图b a b o o n 的原始图及7 次量化效果图3 2 图5 18p s r n 图表3 3 v i i 多核机群下基于小波原理的并行图像压缩与解压缩 图5 1 9 最低频子带数据划分3 4 图5 2 0 数据划分3 4 图5 2 l2 号节点恢复数据3 5 ， 图5 2 2m p i 并行程序加速比3 6 图5 2 3m p i + o p e n m p 并行程序加速比3 8 叶：? 表5 1b i t m a p 图像组成2 1 表5 2 主表代码信息2 5 表5 3 辅表代码信息2 5 表5 4i = 0 时，主表、辅表和大于阀值链表数值2 8 表5 5i = l 时，大于阀值细化信息表数值2 8 表5 6 大于各阀值占图像像素点比值3 1 表5 7 图片l 、l e n a 和b a b o o n 的p s n r 3 2 表5 8m p i 并行程序使用时间3 6 表5 9m p i 并行程序加速比3 6 表5 1 0m p i + o p e n m p 并行程序时间3 7 表5 11m p i + o p e n m p 并行程序加速比3 7 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已经 注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得凼鏊直太堂及其 他教育机构的学位或证书而使用过的材料，与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：驻面冱 e l期：塑星! 虚! ! 里 指导教师签名： 日期：翌艘堡笸! 汐 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全 部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索， 也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期 间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古 大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 矗一一o 学位论文作者签名：垃鳗i 互 指导教师签名： 日 期： 麴星! ：! ! 日期： 歪 内蒙古大学硕士学位论文 1 1 论文研究背景 第一章绪论 近年来，随着计算机技术、现代通信技术、网络技术和信息处理技术的迅速发展，人们 对各种信息的需求不断增长，尤其是图像和多媒体信息。未经处理的图像信号的数据量是巨 大的，使得图像信息的传输、处理和存储都受到限制。因此，研究高效的图像数据压缩编码 方法，即怎样处理、组织图像数据，在应用领域中的作用将是至关重要的。图像数据压缩编 码技术已经成为多媒体及通讯领域中的关键技术之一。 j m s h a p i r o 根据小波分解后同方向子带中的小波系数存在的相似性，利用一种称为小波 树的树形结构来组织这些小波系数，设计了嵌入式小波零树编码方法( e z w ) 。e z w 算法 能有效地去除频域和空间域中的相关性。被认为是迄今为止最有效的编码方法，它有效地利 用了小波系数的特性，实现了图像的可分级压缩编码。e z w 算法的特点是可以产生嵌入式 码流，可以按照要求的目标比率或目标失真的精度随时结束编码，因而它有很好的发展前景 和应用前景。 众所周知并行图像处理技术是提高图像处理速度的最有效技术。其发展水平一直受到图 像领域的关注。因为，一方面，图像并行处理技术【l9 】难度很大，这种难度不仅在于图像并行 处理系统的硬件及系统结构本身，以及它对计算机技术及集成电路技术的依赖，而且在于实 际应用中的复杂性和应用部门对系统价格的承受力；另一方面，图像并行处理技术的发展所 产生的效益也是十分显著的，它在处理速度上获得的加速比令人振奋，其实际应用系统也将 产生巨大的经济效益和社会效益。随着多核和机群技术的普及，很自然的想到将并行技术应 用到图像压缩领域。这样可以在图片压缩质量不变的前提下，尽可能的缩短压缩的时间。 1 2 论文研究的内容 本课题研究的主要内容：在多核机群环境下采用m p i 、m p i + o p e n m p 两种并行编程模型 来实现小波分解，零树的编码、零树的解码和小波合成这些费时的处理过程。小波变换因其 运算的复杂性，一直以来是研究的重点。嵌入式零树编码方法被认为是迄今为止最为有效的 编码方式，但因其是内嵌编码，即编码器将待编码的比特流按重要性的不同进行排序，根据 目标码率或失真度大小的要求随时结束，所以一直未将这种特殊的编码方式并行化。但通过 多核机群下基于小波原理的并行图像乐缩t j 解压缩 分析零树的特点，发现还是有并行的可能性。分析如下：零树是在小波变换的基础上产生的， 将小波变换的最高层作为零树的一系列树根，将下一层作为树根的孩子，依此类推，形成一 个四叉树的森林。可以将这个森林中的树按一定的分配算法分配给机群上的多个节点，让他 们同时进行量化过程，然后再将量化的结果由一个节点收回，这样我们就得到了量化后的结 果。同样以对称的方式可以实现嵌入式零树的解压缩的并行化。 本课题主要工作包括串行应用程序的实现和并行算法的设计与实现。其中，并行算法部 分是本课题的重点。并行算法所做的主要工作包括程序任务的划分、通信和同步的协调、任 务调度等。如果这些问题不能得到正确处理，那么应用程序的并行化就不会获得较好的收益。 实验结果表明：本程序利用多核机群的特点在保证图像恢复质量的同时，也缩短了图像 压缩的运行时间。 2 内蒙古大学硕士学位论文 第二章小波分析原理介绍 小波变换【2 】【3 】是傅立叶变换思想方法的发展和拓延。小波分析可以根据信号频率的变化， 对高频部分，选取一个窄的时间窗提高时间分辨率，以分析信号的高频部分；而取一个宽的 时间窗来更充分地分析信号的低频部分，所以被誉为数学显微镜。它是空间( 时间) 和频率 的局部变换，能够有效地从信号中提取信息，通过伸缩和平移等运算功能，可对函数或信号 进行多尺度的细化分析，解决傅立叶变换不能解决的很多问题。近十年来，小波分析的理论 和方法在信号处理、语音分析、模式识别、数据压缩、图像处理、数字水印、量子物理等专 业和领域得到了广泛的应用。小波变换是8 0 年代后期发展起来的新的数学分支，在函数论、 微分方程、信号分析与传输、图像处理方面有着重要作用。 2 1 小波的基本概念 小波( w a v e l e t ) 就是小的波形，所谓小，就是存在于较小区域的波，且具有衰减性。根 据小波的定义，小波函数妒( ，) 应具有振荡性和迅速衰减的特性( 见图2 1 ) 【7 】【8 1 。 2 2 连续小波变换的定义 图2 1 小波的特性 f i g u r e 2 1w a v e l e tc h a r c t e r 设函数厂( ，) 具有有限能量，即( f ) l 2 ( r ) ，则小波变换的定义如下： 町( 口，6 ) = e 厂( f 溉“f 渺= e 厂( f ) 击妒洋渺( a 。，f ( t ) ) l 2 ( r ) ) ( 2 - 1 ) 积分核为吼。( f ) ：下i 妒【t - b ) 的函数族。其中a 为尺度函数，b 为定位函数，函数，6 ( r ) 称 吖a 多核机群下基于小波原理的并行图像胝编与解压绢 为小波。如果仇。( f ) 是复变函数时，上式采用复共轭函数p 盯 6 ( f ) 。若a l ，函数伊( f ) 具有伸 展作用，若a l ，函数具有收缩作用。 随着参数a 的减小，仍。( f ) 的支撑区也随之变窄，这就有可能实现窗口大小自适应变换， 当信号频率增高时，时窗宽度变窄，而频窗宽度增大，有利于调高时域分辨率，反之亦然9 1 。 小波) 的选择不是唯一的，也不是任意的，这里妒( ，) 是归一化的具有单位能量的解析 函数，驴( r ) 应满足如下几个条件9 1 ： ( 1 ) 定义域应是紧支撑( c o m p a c ts u p p o r t ) ，换句话说就是在一个很小的区间之外，函 数为零，也就是函数应有速降特性。 ( 2 ) 平均值为零。即 跏) d r = 0 ( 2 2 ) 其高阶距也为零，要求妒( f ) 的前1 1 阶原点距为零，且1 1 越大越好，以便充分刻画信号的 高阶变化，即： d 妒o ) 刃= o ( k = 1 ，2 ，3 ，n 1 ) ( 2 - 3 ) 该条件也叫小波的容许条件。 巳：。r - * 拯o ( 也- 0 国 ( 2 - 4 ) 式中，( 缈) = e 缈( ，) 刃= 0 ，c 妒是有限值，它意味着y ( 缈) 连续可积： y ( o ) 2 上。伊( ) 衍= o ( 2 5 ) 卜 i ，- 、l 由上式可以看出，小波矽( ，) 在t 轴上取值有正有负才能保证式( 2 5 ) 积分为零。所以， 缈( ，) 应有震荡性。 上面2 个条件可概括为：小波应是一个具有震荡性和迅速衰减的波。 对于所有的f ( t ) ，9 ( ，) r ( r ) ，连续小波逆变换如下： 巾) 2 虿1 ep 矽削( f 脚 ( 2 - 6 ) 4 内蒙古大学硕上学位论文 2 3 离散小波变换 2 3 1 离散二进小波变换 对连续小波离散化可以通过尺度参数a 和位移参数b 的离散化取样来实现。可以证明， 如果对a 按指数取样，对b 均匀取样，依下式对a ，b 离散化： u = a o j 9l ba o ：，裂誊如 p 7 ， ：，后= 0 ，1 ，2 ， 、。 则由此得到的离散化的小波函数 仍，i ( f ) = 口；伊( 口i f 一七) ， 歹，k z( 2 - 8 ) 一般使用中，常取式( 2 8 ) 中的= 2 ，这就是离散二进小波函数 z 伊，。t ( r ) = 2 2 r p ( 2 。f 一七) ， ，后z ( 2 - 9 ) m e y e r 和s t r o m b e r g 证明，存在一些小波f o ( t ) r ( r ) ，使得式( 2 9 ) 中的二进小波函数 构成l 2 ( r ) 空间的标准正交基。这些特殊的小波c o ( t ) 称为正交小波基。由于对尺度函数的离散 化是依2 0 形式进行的，这样生成的小波正交基又称二进正交小波基，相应的变换又称二进正 交小波变换。对这种二进正交小波基，任一能量有限信号f ( t ) 的二进正交小波变换为 孵( ，七) 5 上( f ) 妒j j ( f ) 衍 ( 2 - l o ) 其相应的重建公式为 加) = ( ，k ) f g j , 。( f ) ( 2 - 1 1 ) 由于实际应用中信号f ( t ) 往往是离散的，由数值形式给出的，因此直接由式( 2 1 0 ) 求信号 的小波变换很不方便，而且正交小波缈( ，) 的构造也不是一件容易的事。s m a l l a t 在1 9 8 8 年提 出的多分辨率分析( m u l t i r e s o l u t i o na n a l y s i s ，m r a ) 克服了这种不便，由此也产生了小波分 解与合成的快速m a l l a t 算法。 2 3 2m a l l a t 算法 m a l l a t 提出的多分辨率分析又称多尺度分析，是建立在函数空间概念上的理论。基于多 分辨率分析理论，m a l l a t 就信号的离散二进小波分解与合成导出可用递推方式进行的快速算 法，并且建立小波变换与数字滤波器之间的联系，在小波变换理论及其应用方面均做出重要 贡献。 多核机群下基于小波原理的并行图像压缩与自星! 匡绩 由多分辨率分析可知，任意( ，) 巧一。在巧一。空间中的展开式为 ( 一+ 1 ) ( f ) 二c 川乒2 下矽( 2 小1 f 一七) 七 将厂( f ) 分解一次( 即分别投影到一，髟空间) ，则有 ( 2 1 2 ) 一j 饨) = c j 2 t 0 ( 2 7 卜七) + 屯妒( 2 7 ，一七) ( 2 - 1 3 ) t k 其中c 似是厂( f ) 在巧空间的离散逼近，称为尺度系数。d j ，t f ( t ) 在w j 空间的离散值， 称为小波系数。 c ”= i x m a x i ，这里x m 舣是小波变换系数矩阵中的最 大绝对值。 ( 2 ) 主扫描 扫描每一个系数产生系数符号。如果系数幅度大于门限值t 且为正数，输出符号p o s ：如 果系数幅度小于阀值t ，且为负数，输出符号n e g ：如果系数是零树根，输出z t r 如果系数 幅度小于阀值但树中有大于阀值的子孙系数，输出孤立零符号i z 。在扫描过程中，用一个主 扫描表记录这些输出符号。当一个系数的输出符号为z t r 时，它的所有子孙就不再扫描，用 表示。第一次主扫描结束后，将输出符号为p o s 或n e g 的系数的相应位置加标记或将这些 系数置为零。以免在下次主扫描时再对它们编码。为了确定一个系数是否为零树根t 或者是孤 立零，需要对整个四叉树进行扫描，这样就需要花费时间。此外，为了保护已经被标识为零 树的所有系数，需要跟踪它们，这就意味需要存储空间来保存。最后要把绝对值大于门限值 的系数取出来，并在图像系数相应的位置上填入一个标记或者零，这样做可防止对它们再编 码。 ( 3 ) 辅扫描 辅扫描是对主扫描取出的带有符号p o s 或者n e g 的系数进行量化，产生代表对应量化值 的符号“0 ”和“1 ，这种符号称为量化符号。在量化系数之前要构造量化器。量化器的输入 间隔为【t i - l ，2 t i - 1 】，该间隔被1 5 t i 一1 ，分成两个部分：( t i 一1 ，1 5 t i - l 】和( 1 5 t i - l ，2 t i - 1 】，量化间隔 为0 5 t i 1 ，其中i 为第i 次编码。量化器的输出为量化符号“0 和“1 ：“o 对应量化值为 ( 1 5 0 2 5 ) t i - l ；“1 对应量化值为( 1 5 + 0 2 5 ) t i - 1 1 1 4 1 。 1 6 内蒙古大学硕士学位论文 第四章m p i 和o p e n m p 混合编程 4 1m p i 与0 p e n m p 概述 4 1 1m p i 概述 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 编程是基于消息传递的并行编程技术，是如今应用最为 广泛的并行程序开发方法。m p i 是一种编程接口标准，而不是一种具体的编程语言。该标准 是由消息传递接口论坛( m e s s a g ep a s s i n gi n t e r f a c ef o r u m ，m p i f ) 发起讨论并进行规范化的。 m p i 标准从1 9 9 2 年开始起草，于1 9 9 4 年发布第一个版本m p i 1 ，到1 9 9 7 年发布第二个版本 m p i