（通信与信息系统专业论文）高效图象数据压缩及其硬件实现.pdf

创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标滓和致谢中所罗列的内容以外，论文 中不包含其它人已发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何 贡献均已在论文中做了明确的说明并表示了谢意。 本人签名：至鱼自 日期：卯口- i , c 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 本人签名： 至塑萤 导师签名 日期：”f 弘 搁毅 摘要 在图象编码领域里，人们一直在追求高性能的压缩算法，为此不断引入新的 数学工熬。众辑劂知，算法粒硬件实联是走向应用豹关键一步。小波变换份为一 释崭莸的数学工具，已经在黼象编码镁域受弱藏朱越高的重视。 本文首先介绍了小波变换的基本概念，它包括：小波变换的定义和图象中的 维小波变换等。然后介绍了种适于硬件实现的整数小波变换。髓后给出了”种 基于夺波零稷静内鼗编玛( e z w ) 算法：s p i h t 茧纯算法。荠置研究了一穑改遗爵毫无 链表s p i h t 算法。实验结粜表明，该算法不仪克服了现存算法需要大量存储空间 的缺点，而且实现复杂度低、编码效率高、恢爱图象质量和原始算法相比仅下降 约0 。1 d 8 ，宅是我髑瑟实或熬疆传系绞斡理论藜磷。其磊瘸霹编瑷嚣 孛v i r t e x 系 列芯片实现了一个遥感图象的编解码系统。 在本文的最后，实现了个基于p c i 总线的实时图象采集卡。 关键词：黼象缟碣，小渡蛮换，s p l h t ，硬件，可编程器件 a b s t r a c t i nt h ef i e l do fi m a g ec o d i n g 。t h e 弧g hp e r f o r m a n c ea l g o r i t h m sa l ea l w a y st h e f o c u s e so fa t t e n t i o n s o m en e wm a t h e m a t i c a lm e t h o d sh a v eb e e ni n t r o d u c e di n t ot h e f i e l do fi m a g ec o d i n g f o rt h ea p p l i c a t i o n so ft h ei m a g ec o d i n gt h ei m p l e m e n t a t i o ni n h a r d w a r ep l a y sak e yr o l e 。w a v e l e tt r a n s f o r mh a sb e e na p p l i e dt oi m a g ec o d i n g s u c c e s s f u l l y , a san o v e lm a t h e m a t i c a lm e t h o d a tf i r s t ，s o m eb a s i cc o n c e p t sa b o u tw a v e l e ta r ei n t r o d u c e di n c l u d i n gd e f i n i t i o no f w a v e l e ta n d2 di m a g ew a v e l e tt r a n s f o r me t c ，t h e nf i l li n t e g e rw a v e l e tt r a n s f o r mi s g i v e n w h i c hi ss u i t a b l et 0h a r d w a r ei m p l e m e n t a t i o n s e c o n d l y , e z w ( e m b e d d e dw a v e l e tz e r o t r e e ) i si n t r o d u c e d ，w i t he m p h a s i so n s p i h t ( s e tp a r t i t i o ni nh i e r a r c h i c a lt r e e s ) ，i no r d e rt or e a l i z et h es p i h ti nh a r d w a r ew e p r e s e n t e dal i s t l e s ss p i h ta l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e d m e t h o dh a so v e r c o m et 1 1 ed i s a d v a n t a g eo fo r i g i n a ls p i h t i ti so fl o wc o m p u t i n g c o m p l e x i t y , h i g hc o d i n ge f f i c i e n c ya n dg o o dv i s u a lq u a l i t yo fr e c o n s t r u c t e di m a g e t h e v a l u e so fp s n r ( p e a ks i g n a ln o i s e r a t i o ) a r ej u s t0 。ld bl e s st h a nt h e 两蠡n a lm e t h o d ni st h et h e o r e t i c a ib a s i so f h a r d w a r es y s t e m t h i r d l y , w ei m p l e m e n t e dar e m o t es e n s i n gi m a g ec o m p r e s s i o nh a r d w a r es y s t e m w i t hf p g a ( f i e l dp r o g r a m m a b l el o g i ca r r a y ) o f v | r t e xs e r i e s a tl a s t ，ar e a lt i m ec a r di sp r e s e n t e d ，a c q u i r i n gi m a g ed a t a ，b a s e do nt h ep c ib u s p r o t o c 0 1 k e j , w c o r d s ：i m a g ec o d i n g ，w a v e l e tt r a n s f o r m ，s p i h t , h a r d w a r e ，f p g a 趟发l u 子科技人学顶 ：论文 第一章绪论 第一章绪论 【摘要l 本章首先对图像通信作了简单的回顾 针对谊领域的若干前沿方向进行了评价与展望 设想，自己工作的目的和重要性 简单总结了图象编码的发展历史和现状，并 然后阐述了本人对图象编码及其研究方法的 1 1引言 当历史跨入二十一世纪，信息革命正以它无比的生命力向整个人类社会展现了 一幅波澜壮阔的宏伟蓝图。它以不可阻挡的势头影响和改变着人类的生存环境和 生活面貌，包括人们的生活节奏、文化结构、交流方式、社会分工乃至产业和资 金组合。以计算机和通信技术为主体的数字化技术，极大地拓展了人类的视野， 促进了人类间的交流合作。特别是蓬勃兴起的国际互联网i n t e m e t 技术，和以i p 为基础的各类通讯技术和设施的出现更集中体现和预示了人类所面临的将是一个 信息化的全新时代，明天将会出现的是以信息为核心的人类地球村! 作为当今社会最重要的特征信息，尤其是包括图像、图形、声音、文字 的多媒体信息，不仅可以凝结历史，使后人能够感受前人的思想、再现历史动人 时刻，而且可以跨越时空交流情感，足不出户便可领略世间万象。随着信息领域 中新技术的不断涌现和应用，人们对于建立一个更加符合人的自然特征的信息环 境的要求也越来越强烈。 图像。作为信息含量最为丰富的信息载体，成为构造这样一个信息环境所必不 可少的要素。它在现代通信技术中所承担的作用已远远超过其它载体，这与其在 现实生活中所扮演的角色是息息相关的。 1 9 2 5 年，英国人j l b a i r d 机械式电视接收实验成功，标志着人类通信又步入 一个新的阶段。1 9 3 6 年，德国对模拟电视电话( 丁矿砌d 胛) 进行了实验。6 0 年代， b d l 实验室先后推出了p i c t u r e - p h o n ei 、i i 两种型号的电视电话。在7 0 年代，又开 展了会议电视和可视图文研究。 然而，图像通信真正步入一个新时代，是伴随着数字化技术的出现开始的。 1 9 6 5 年前后出现、并在1 9 6 9 年于美国产品化的电视a d 转换器，使得图像的数字 化成为可能，从而标志着图像数字化处理新时代的到来。同时也使图象通讯面临 着新的挑战，数字化通讯具有许多模拟通讯所无法达到的优点，比如抗干扰，可 加密等，但它需要更大容量的传输信道。 这就使得本来就庞大图象数据，在传输、存储、和处理中遇到了更大的困难。 以p a l 制( 2 5 帧秒) 的视频信息为例，如果每帧具有中等分辨率( 6 4 0 4 8 0 个 像素点) 、真彩色( 每像素用2 4 位信息来描述) 的图像，则每帧数据量为7 3 7 兆 西安电子科技硕士学位论文 高效图象数据压缩及其硬件实现 2 比特，并且要求传输速率大于1 8 4 兆位秒。当然随着光纤通讯的迅速发展，在有 线通讯领域中的信道紧张问题可以得到一定的缓解。但是在无线通讯中，包括无 线视频，卫星图象的传输和处理中这个问题依然存在，并且随着通讯卫星的分辨 率的提高越来越明显。因此寻找一种高效图象数据压缩技术将是信息时代的永恒 课题! 近年来，由于航天遥感、多媒体、综合业务数字网( z s d ) 、网络多媒体的迅 速发展，为图像通信的研究和应用不断提出新的要求和课题。不断涌现的数据压 缩技术、数字信号处理技术、为数字图象的传输提供了良好的技术平台。超大规 模集成电路( v l s i ) 、高速数字信号处理芯片的出现为图象处理提供了坚实的硬件 平台。所有这一切使得图象压缩编码技术得到了长足的发展。表现在：各种经典 压缩算法逐渐走向成熟、实用化和标准化，符合各种国际标准的硬件芯片不断问 世；同时，在经典压缩方法的基础上，新的算法也不断涌现出来，并在工程实践 中逐步得到应用。 1 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 字典编码。 随后，人们发现图像中相邻像素之间存在着很强的相关性，去除这种冗余无 疑会大大简化图像的数据表示，在此基础上提出了以差分脉码调制( d p c m ) 为代 西安电子科技大学硕士学位论文 第一章绪论 表的各种预测编码方法和各种内插编码方法。因此，早期阶段发展起来的大多数 编码方法都是针对去除图像内部的统计相关性来达到压缩图像的目的。 随着对图像本身特性研究的开展，人们发现图像数据在数值上发生细微变化 时，人眼并不会察觉。基于这一点，人们摆脱了无失真编码的限制，开始寻求各 种限失真编码的方案，编码方案的设计目标从如何精确恢复原始图像数据转变为 如何将重构图像的误差限定在人眼可接受的范围之内。进一步地，结合允许细微 差异的量化方案，使得在这一阶段后期的编码方法的压缩效率比熵编码又有了较 大的提高，大致达到1 0 ：1 。 二、第二阶段 1 9 8 5 年，瑞士学者m k u n t 提出“第二代图像编码技术”的概念。区别于去 除图像统计冗余的早期编码方法，第二代图像编码技术以去除图像的视觉冗余为 主要目标，强调编码不仅应充分利用图像信源的局部和全局的统计相关性，而且 要利用图像内部的几何特征、自相似性和方向性等多种自然属性和规律，同时强 调对于图像不再简单地作为客观信源来看待，而在充分考虑人类视觉系统特性 ( h i e s ) 的基础上，针对图像视觉信息进行有效编码。在这一阶段，引起广泛关注 的编码方案包括基于方向性滤波的编码、基于图像纹理轮廓的编码和区域基编码。 尽管第二代图像编码技术最终未能进入实用，但它所倡导的充分利用人的主观视 觉特性及图像自身所固有的各种特性来提高编码效率的思想却对整个编码领域产 生了深远的影喻，并成为中期阶段的一个重要标志。 中期阶段的另一个重要成果就是混合编码的出现和发展。经过几十年的研究 和探索，人们逐渐认识到单纯通过一种编码技术很难去除图像存在的多种相关性， 而将多种编码技术有机地结合起来形成一种最佳组合能够得到对图像数据的更大 程度的压缩。混合编码研究的一个直接成果就是j p e g 图像压缩国际标准的诞生， 它融离散余弦变换( d c t ) 、d p c m 、视觉加权标量量化和熵编码于一身，达到了 很高的性能指标。j p e g 标准的出现，成为数字图像编码技术发展的一座里程碑， 许多方法都以它作为评价自身性能优劣的参考，因此有人称之为“图像编码四十 年研究成果的结晶”。对于混合编码研究的另一个成果是，许多早期的编码技术如 方块截断编码、预测编码等又有了新的用武之地，拓宽了其应用领域。 需要指出的是，上述有损编码中的信息损失( 误差) 是在量化阶段产生的， 因此，如何设计最优性能的量化器一直是各个阶段的重要研究课题。1 9 5 9 年， s h a n n o n 在率失真理论中论述了矢量量化( 呦的性能总是优于标量量化( 鲫， 当编码长度趋于无穷的情况下，比特率和失真之问的关系可达到率失真界，v q 编 码技术就是这一论断的技术实现。早期研究多围绕s q 最优量化区间的划分和最优 量化值的求解进行探索，七十年代后期出现的l b g 算法极大地推进了矢量量化研 西安电子科技硕士学位论文 离散潮象数据压缩及萁硬件嶷理4 究的进展，包括对失真测发的探讨、码书设计、备种矢量量化系绕的研究、快速 搜索算法等等，它对于中期阶段的混合编码及新数学工具的引入都舆商重要的意 义。 在遮一除段还窭瑰了疆凝觉麓空阗频率特彀为出发点豹子带辫豫编薅鼓拳， 它具有多分辨率和渐进传输的特点，对后期小波编码技术的发展有麓赢接的影响。 三、第聂阶段 这一阶段的编码技术又可称为现代图像缡碾技术，区别子缎热图像编码技 寒，其簸大特点是弓l 入了瓣豹数学工其弱理论。麸8 0 年健寒至l9 0 霉氏中鹚，大 量崭新魏数学理论成采被萼| 入闰像编鹤领域，淹溺像编码援术懿发殛注入了巨大 活力。试些数学工具是：小波理论、分形几何理论、神经网络理论朔计算机视觉 理论。 小波瑕论在9 0 年代受到众多领域科技工作者的高度重视。作为数学和工程应 霭等学褥共同硒究的缝燕，夸渡交换在信号分攒、图像处理、蟪煺瀚探、量子携 理帮嚣绫往辩学等诸多领域褥弱广泛瘟溺。小波壤论为各耱信号及鞫像处理方法 提供了种统一的分析框架，成为当前信号与阁像处理等众多领域的研究热点。 在闼像编码领域，由于具有描述非平稳信母的独特优点，小波变换可将图像 信号分解成不同空间分辨率、不同频率特征和方向性特征的子图像信号，这便于 在失真编码中综合考虑人的视觉特性，同时也测予图像鲍逐渐浮现健涂。另终， 宅箨麓予鬻像鹣整薄，在鸯效去豫圈豫豹垒裁稳关毪赘嚣靖，健爱纯诿差努教到 整个圈像中，避免了j p e g 方法带来的“马赛毙”方块效应。所有的j 袅些优势使得 它成为一种极有前途的编码方法，它所具备的磷压缩潜力也正不断为各国学者的 研究成聚所证实。近年来涌现出来的一些基于小波变换的压缩算法，结合特定的 量化和缡褥方法，普遍能够谯赢压缩比下获褥比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 产搬) 编码方法。 随糟8 0 年代中期人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，一 ，) 研究的兴起， 许多学者开始尝试将a n n 引入图像压缩领域。 詹多| 乏出现的模型基编码的愚想是建立在计算枫视觉、模式识别和形态学等多种 理论豹麓懿上。宅突酸了s h a n n o n 豹售惑莲谂攥黎，逶过霹霆绦童转建立模鍪， 用少蒙参数来表征整个图像，是实现低比特率编码的有效方法。邋裔予一般的活 动图像编码。 总之，图象编码技术发展到今天，使其具销更广泛的理论基础，吸收和继承 了前面阶段的成果，特别淀燕各种算法的相互渗透和 充，使此阶段的编码技术 这到了受凑豹整嶷。疆麓瓣图像售源窝久类撬擞系绞懿涤入理瓣，入稍雯燕强诱 西安电子科技大学硕士学织论文 第一章绪论 编码质量的视觉无失真( v i s u a ll o s s l e s s ) 要求，侧重于图像的可理解性和视觉上 的信息无损，而不过分强调精确的数字表示。另外随着高速芯片的不断发展使图 像编码技术特别是原来难度较大的编码方法的硬件实现成为可能，涌现出一大批 符合国际标准的编解码芯片。这将进一步促进图像通信的快速发展。 然而，这一阶段的编码技术仍在成长和完善过程中，一些先进的编码方法的实 用化更需要进一步的努力。 1 3 本文的研究内容 从上面的介绍可以看出，在图像编码领域中，更高性能的压缩算法一直是人 们不懈追求的目标。而高效图象压缩方法的硬件实现更是其走向应用领域的关键 一步。本文就是在这样的背景下做了以下工作： 研究了一种提升整数小波变换。 研究了基于零树的s p i h t 算法，提出了无链表的s p i h t ，并在保证性能基本不变 的前提下做了有利于硬件实现的改进。 用高速f p g a 芯片v i r t e x 系列实现了采用提升小波和改进s p i h t 算法的实时遥 感图象编解码系统。 开发了一种基于p c i 总线的图象实时采集卡。 西安电子科技硕士学位论文 高教图豫数据压缩及其硬竹实现 6 第= 章适于硬件实现的小渡变换研究 【摘要l 本章莆先赫要念绍了小波理论的发展历史，然后i 鹌迷了小波理论的基本概念，包据 各种小波变换，在此基础上，介绍了鞠象小波变换的基本知识。最詹给出了一种适合硬件实 现的提升撩数小渡爱换 2 1 弓l 言 作为多令学瓣共同疆究豹戏票，小波变换逐灏被越来越多镀壤的理论王作者 和工程技术人员所重视和应熙。 在经典的信姆分析理论中，f o u r i e r 分析理论是】雯用疑广泛、效果最好的种 分析手段。假是宦只是一种纯频域的分析方法，不能提供局部时间段上的频率债 怒。褥涎焉的短辩傅立睁交羧s t f t ( s h o r tt i m ef o u r i e rt r a n s f o r m ) ，蚤然可戮黼 时分板时域和频域售息，健是盎予s t f t 的固定对密，对予分板时变信号楚不利懿， 这是因为时炎信号中的高频一般持续时间很短，而低频持续时间比较长，因此我 们希疆对于高频佰号采用大的时窗，低频采用小的时窗进行分析。 小波变换正怒在这样的背景下发展起来韵，它的思想来源予伸缩与平移的方 法。1 9 1 0 年g a a r 提池的规范正交基是小波思想的雏形。1 9 6 5 年g a l d e r o n 发现了 褥生公式，它的离散形式已经接近小波展开，只是还无法得到组成一个正交系的 结论。1 9 8 4 年，法国地球物理学容工m o r l e t 第一次引入“小波”( 砌v e l e t ) 的概 念，时魂震波信号进行分析，这是小波的真正出现，之后，弛与璃论物理学家 g r o s s m a n 共i 硒毪出了连续小波交换的凡储体系。1 9 8 6 年。m 艘y e r 第一次构造出具 有一定衰减悔的光滑小波，其二进伸缩平移可构成f ( r ) 空间的规范正交系，一举 抒破了人们长久以来赝认为的不霹戆的设想，从颓激起了对小波龌究的极大热媾。 1 9 8 8 年，美糍比剩时女数学家d a u b e c h i e s 绘如了具有紧支集和馒意有限正则度的 小波函数的一般构造方法。1 9 8 9 年，m a l l a t 创造性地将诗算机视觉领域中的多尺 度分析方法引入到小波基的构造中，首次统一了以前s t o m b e r g m e y e r ，l e m a r l e 和b a t t l e 等提出的器种小波的构造方法，并硬究了小波变换的离散形式，同时绘 出了m a l l a t 塔式分鸯翠和踅构算法，从而为小波理论的工程应用铺平丁道路。 暇前小波在许多领域得到了广泛的应用。如矗m a l l a t 将二进小波变换用于阁 象的边缘检测、图象压缩与羹构：肛f r i s c h 簿将小波变换用于噪声中的朱知瞬态 信号：只d u t i l l e u z 镰将小波变换用于语音信号的分析、变换和综合；小波交换在 电磁场领域中的应用也获得了成功。 总之小波变换作为一种数学理论和方法在科学技术界引起了越来越多的关注 和重视。在数学家们看来，旗于小波变换的小波分析是范函分析、数值分析、调 和分析等半个多世纪以来发腱的最完美结晶。在工程应用领域，特别时在信号处 理、，图象处理、模糊识别、语音识别、量子物理、地震勘钡9 、c t 成像、机器视觉 西发电子科技大学硕士学位论文 第二章适于便t i ：实现的小波变换研究 簿领域，它被认为怒近年来在工具及方法上豹重大突破。小波交换酲经成为科技 工作者经常使用的又一锐利的数学工具，会极大的德迸科学及工程应用各个领域 的新发麓l 2 2 小波分析概述 小波，绒称作分板小波，其定义如下： 定义1 设2 ( 昱) 是一个测螅、平方霹裁豹一维函数矢鬃空闻，r 为实数集。 小波是由满足l f ，似) d x = 0 的函数矿( x ) 通过平移和缩放而产生的一个函数族 妒a , t ，( x 2 = i 口r 矿( 孚) ，啪足球o ( 2 - 1 ) 彰础扛) 称诈分析夺滚( a n a l y z i n gw a v e l e t ) 或连续小渡，豢且仅当母夺渡随羧矿( x ) 舱勘孵幼变换参( 毋) 潢足鞋下可骞性( 矗拥狲冶封毋) 条转： q = e 臀如 。o 弘妨 这里，口被称作伸缩因子，b 为平移阂子。 定义2 在定义1 的基础上，函数，( x ) 在r ( 内上的连续小波变换定义如下： ( 黟( 砷) ( 婊6 ) = ( ，( x ) 妒。女( x ) ) = k i 一腔j f ( x ) l v ( x 群- b ) 苏( 2 - 3 ) 从小波的可容性条件可知，母小波荫数妒 ) 是一个振荡且熊量有限的函数， 并且在辩域七是快速衰减的。容荔推出痧( o ) 一0 ，郎母小波的f o u r i e r 变换妖国) 经 过原点，这表明y ( x ) 在时域的均值为零。 小波交换韵实质在于将叠( 矗) 空间中的任意函数，( 表示成为在矿础0 ) 的不 同伸缩葶h 平移因子上的投影的叠加，与声b u r i e r 变换不同的是，小波变换犍一维时 域函数映射到二维“时间一尺度”域上，鼹此，0 ) 在，j 、波基上螅展开其有多分辨霉 豹将往。通过调凝秭缩因子n 和平移因子b ，可戳得弼其有不同时频宽度的小波戳 莲配原始信号的不葡位鼗，这蓟对信号的局都纯分丰厅。 西安电子科技大学硕士学位论文 高效图象数据压缩及其硬件实现8 在实际应用中，尤其是数字信号处理领域，为了计算上的方便，需要使用离 散小波变换进行分解，也就是将，( x ) 的积分形式展丌为离散和形式。所谓离散小 波就是将1 6 ，。o ) 的参数a 和b 离散化。参数a 和b 离散为 a = n ；，b = n b o a o ，m ，n z ( 2 4 ) 这时，离散小波可表示为 i c ，。一( z ) = i 口0 l - m 1 2 妒( 口i ”x n b 。) ， m ， z ( 2 5 ) 特殊地，当a 。= 2 且6 0 = 1 ，可以得到如t - 进( d y a d i c ) 小波 。( = 2 - , , n 少( 2 一”x h ) ，m ，n z( 2 6 ) ，( x ) 在正交小波基上的展开式即为小波级数，其数学定义如下： 定义3 一个函数yer ( r ) 称为一个正交小波，如果公式( 2 - 1 0 ) 中所生成的函 数族舻。) 构成r ( 月) 的一个规范正交基，即 ( i , t l j , 少。，) = 占，以，j ，k ，m ，行z ( 2 7 ) 则，对于任意，( x ) e 工2 ( 五) 都能写成 ，o ) = c 。，( x ) ( 2 8 ) 其中c 。= ( ，y 。，) 。公式( 2 - 1 1 ) 称为，( z ) 的小波级数展开式。 在此基础上。提出框架( f r a m e ) 的概念，它是规范正交基的推广。 定义4 满足如下条件的离散小波称为框架： 4 1 s ( x ) 1 1 2 e l ( s ( x ) ，妒。( x ) ) b i i s ( x ) l l2 ，( o 1 ，则称为松框架( l o o s e ) 。 小波基可以分为： 1 ) 非正交小波( n o n - o r t h o g o n a l ) 非正交小波为线性依赖的冗余框架( i n e x a c t ) ，如墨西哥草帽小波( m e x i c a n 西安电子科技大学硕士学位论文 第二章适于硬什实现的小波变换研究9 h a t ) 。 2 ) 半正交小波( s e m i - o r t h o g o n a l ) 半正交小波是在r ( 矗) 空间上完备的框架，在不同尺度上是正交的，即 y j ，t 上少。，m ，k ，m ，仃z ( 2 - 1 0 ) 而只有当其支集在同一尺度上= 肌) 不相交叉( 大于k m i ) 时才正交。 如c h u i w a n g 的b 样条小波。 3 ) 正交小波( o r t h o g o n a l ) 正交小波是在r ( r ) 空间上完备的、线性独立的无冗框架( e x a c t ) ，也就 是说函数j r ( x ) r ( r ) 可以从( 厂( x ) ，。，( z ) ) 中精确重构。最简单的正交小 波是h a r t 小波，还有d a u b e c h i e s 的紧支集小波和b a t t l e l c m a r i e 小波等。 2 3 小波理论在图像编码中的应用 m a l l a t 提出的多分辨率塔式分解与合成算法，使得信号在小波基函数上的内积 运算转变为与相应小波滤波器的卷积运算，因此，m a l l a t 快速算法在小波分析中的 地位等同于快速傅立叶算法( f f t ) 在傅氏分析中的重要性9 1 ，它极大地促进了小 波变换在数字信号处理中的工程应用。 对于二维数字图像信号，离散小波交换可以通过在水平和垂直方向上分别应 用h 、g 滤波器进行一维滤波来实现，如图2 。l 所示。 ( a ) 二维离散小波分解 西安电子科技大学硕士学位论文 高教图象数据压缩及技硬t i ：实现l o 列滤波行滤波 二维离散小波熏构 躅2 - l 二缳壤教参波变换的m a l l a t 实现 二维离散小波变换每次分解产生一个低频子图l l 和三个高频子图，即水平子 嚣l h 、垂妻予鋈h l 嚣瓣焦子蚕 m 。下一缀奎渡交羧是在蘸缀产生豹低频予圈 l l 的基础上避行的，如此重复三次，可以将原始图像分解成三级十个子豳：l l 3 与l h i ，h l i ，h h i ( i - l 2 ，3 ) ，其书址3 为最 燕频带予照。分勰过程如霉聪示。 l l 3 翻3 h l 3 h h 3 溷2 - 2 三级奎渡努瓣示意图 由于传统小波变换滗义在双边无限的开区间上，对有限长度信号进行加零延 拓或周期延拓，这必然造成图像边界产生不连续的边器效应。该现象反映为分解 系数在边秀赴麓现突魏酌锐峰，使后期量纯编妈过程对之分配多余的码字，降低 压缩效率，并号1 起图像边界处产生褶皱和暗斑等失真。本文为了减少边界效应， 在：i 蓑露卷获运簿之翦黄巍对匿攘数据遴露透赛对穗扩鼹处理。蛰镬霆镊数教疫兹 滤波器，对图像信号行( 列) 采用偶对称扩展；若使用奇数长度的滤波器，对图 像信母行( 列) 采用奇对称扩展。如图2 - 3 所示。 瑗安电予辩捩大学磺士学整论文 蓦 第二章适于硬件实现的小波变换研究 夏夏至日卫互互巫i 互点王五! ( 幻边界偶对称扩展 懑蔓董量囤丑互互卫圈亘 姻：茧一 f 秘边赛奇对称扩展 戮2 - 3 图像静边赛扩疑楚淫 2 4 提升小波交换 以上提出的几种小波变换，虽然也可以达到对图象能量集中的效果从而利于 编码。但是由于计算复杂度很大，不利于硬件实现。1 9 9 3 年a m l r s a i d 和w i l l i a m a p e a r t 删提出了一种新的小波变换，s + p 提升小波变换，它具有效果好，复杂 度低等特点。 2 。4 1 s + p 变换简介 抉速撼舞小波变抉( 或嬲是构造第二代小波的薪方法，窀能实现桡速小没运 算秘原位运算，最霪要的楚提辩算法貔降 聚变换黠的存储蹙闻。遴过提舞构造夺 波包括三个步骤盛先是 z a z y , b 波变换，鄹把数据分巍溪个子集，偶数集会秘帮 奇数集会鞠。第二步，计算裹遗小波系数瑾，朝翔偶数集会来颈测奄数集合的误蓑。 最舞，用这些小波系数寒更毅偶数榘会， 乍为低逶尺度殛数系数s 。 设整数序列e 陶，其孛n = o ，。，麓j ，整n 为耩数，鬟碡瘫交换定义如下： t n 】2 k d 2 坩】+ 。 2 n + 1 1 ) 7 2 j ”= o , , n 2 - 1 ( 2 一1 1 ) h n 】= c 2 n 卜c 2 n l 】，h 。o ，n 2 1 反变换为： c 2 n = 和】+ 帆订】+ 1 ) 2 l 往 2 ) c 2 n + l 】= c 2 n 卜b i n 设4 n 为零均篷麴隧桃序掰量 e 如陋】2 = t 7 ：2 ，e c f 封p 匝+ 1 1 = 盯2 p ( 2 - 1 3 ) 这鼙骈j 蔻数学籍颦运箅符。遮祥有 e 1 2 珂】 。d 2 0 + , o ) 2 ，s h 2 【抖】 = 2 0 r 2 ( 1 一力 ( 2 一1 4 ) 如梁c 【川是灰度图象的行或是期序捌，刚有p * 1 。何啊的方差很小，- l f f j l n 】的方差 足乎等于e 【嚣】懿方蓑。就是说翳象寤到躲戆量缎过s + p 变换基基本上集中在了低 西安电予科技火学硕士学位论文 蒿效鞫象数据压缩及其磺锾实璇2 频滓弼串。 在这个交换中 t i n = l ( c 【2 川+ c 2 n + 1 】) 2 j 称为s 变换 h n 】- c 2 n 】一c 2 n + 1 】，称为p ( p r e d i c t i v e ) 变换 在原始交换中，虽然计算比较简单，但是由于商通滤波器太简单使得图象熊量在 裹频熬分识然鑫套缀太熬魄铡，不剽于压缝、铸辕及处理。霞鼗黻热下处爨，羁 已妇豹熟分z 洳】羁h n 】羧测一个琏丹】称为h n 】，两将 颤【嘲= 磊f 棚一i 矗南l ，2 j ，羟= 。，l _ ，2 一l ， ( 2 - 1 5 ) 代替( 2 1 ) 式中的h n 】，定义 a l n 】= l n - 1 - t i n ， m n m = f m + j 】f l j h n + j 一l 扣l 反变换如下： 域h 】= k i n + ih n 】+ 1 2 l ， = n 2 1 ，n 2 2 ，o li 2 4 2 预测系数的选择 ( 2 - 1 6 ) ( 2 一1 7 ) 在式( 2 1 6 ) 中预测系数嚷和屈的选择是楚关熏要的，它既关系到预测效果 同时影响硬件实现的复杂度。在踟埘和a p e a r l m a n 的文灌中给出了如下三组系 数： 系数 缀号 口i磊口一la 0 ao1 ，4 1 4o b02 83 1 88 c1 1 64 ，1 68 1 66 1 6 寝2 - 1 预测系数对照表 势指出，预测系数组a 寿很小的计算复杂度，b 适用于自然图裂，c 适用乎医学 图象。以b 为例则预测值h i n 】为： 壤嬲= 1 8 2 ( 斌稠+ & 舞+ l 】一1 j i 【h + l 】+ 杰蓬8 + l 】 辖一1 8 ) 经实验证明：对于卫星邂感图象，采用b 组系数效果比较好，而且计算复杂度适 中，函诧在我们实现懿遥感图象实辩压缭疆律系统中，我稻裁采用了b 缝系数。 谣蜜电子辩按大学硕士学位论文 第三章适予磺镣实现麓小渡零瓣阿敬编弼 第三章适于硬件实现戆小波零树内嵌编码 【摘嚣l 本章黄先简要介绍了小波零树结构，然后阐述了s p i h t 量化算法，随后给出了一种 无链袭的s p i h t 算法 3 。l 引言 所谓信源编码就是减少俗源的信息冗余，用尽量少的比特数表示信源序列，图 像压缨也是如此。固赡，对不同驰应用场台，会对恢复霪象憋质量挝凄不羁程度 的要求。高傲能图象压缩算法特点是：高压缩比、简质量和低复杂发。通过前一 章的事重论，我 f 可以露到； 小波变换具备良好的能量集中特性，能大大改鬻图像的能量分布。图像分解 后各赢频子带较多系数接近于零，为获褥毫效搴的压缩提供? 瀵在的霹戆 性。 小波变换后各乎带系数形成了树状结构 漩于上述特点s h a p i r o 提出了内嵌零树编码( e z w ) 方法，其出缴点在于小波 变换厢各层次三抒、眦、艘子带系数之间所摄现出强烈的带阀相关性，这种新型 的数据结丰鼋被定义为“零橱( z e r o t r e e ) ”。 3 2 小波零树与s p i h t 量化 、 3 + 2 。1 零瓣颈淫 器树编码就是最大限度地利用小波系数各层次间的相关性来逃行编码的方 法，窕不器鬟谢练秘预先存贮迢书，瞧不嚣簧经侮黧像浆先骏知识，宅基予 ：圭下 几个要素：离散小波子带分解：零树预测；用零树结构编码羹要图；逐 次遥避量化。 网像经过小波，予带多分辨率分解后，能量几乎总是集中猩较低频的子图像上， 共从低频到麓凝递减分布。农倍频( o c t a v ed e c o m p o m t i o n ) 分解下，由不民频带、 代表间一空间位置的系数构成了一种树型结构，并鼠高频部分存在大量的零，故 称为“零树”，如图3 一l 所豢。图中锈头表明了节点骢父子关系，除了l l 频姆鲍 根节点具有3 个子节点以步 ，其它父节点具有在更高分辨率下4 个子节点，其数 学描述如下式所示： ( x ，y ，m , s ) u t r e e ( 2 x ，2 y ，脚一1 , s ) u t r e e ( 2 x + 1 , 2 y ，m 一1 ，s ) u t r e e ( 2 x ，2 y + 1 ，一l ，s ) u t r e e ( 2 x + l ，2 y + l ，m l ，0 ， 埘1 血# l l 行# 五只鸦如： 瓴韩魏珏) u t r e e ( x ，y , m , l h ) w t r e e ( x ，翦m , h l ) u t r e e ( x ，y ，州，h h ) ， 胁= m _ i i s = l l ( 与只辨，s ) ， = 1 秀安电子辩技大学疆士学攫论文 高效图象数据压缩及其硬件实现 其中，毛y 表示系数在子图像中的2 d 坐标，m 表示子图像层次一，2 “：脚，s 表示 子图像方向厶l h , h l , h h ) 。 零树方案基于如下假设：如果在低分辨率上子带系数x 相对于阙值r 是不重 要的( 即i x lst ) ，那么在同样方向上相应空间位置高分辨率上的子带系数相对于 阅值r 也是不重要的。尽管缺乏严格的数学模型描述，但统计结果表明这种假设 是成立的。实际上，零树预测是利用了小波域中系数的能量随分辨率的降低而提 高的事实，工删括和k n o w l e s 首先认识到这一点并运用于重要性预测( s i g n i f i c a n c e p r e d i c a n g ) 之中，但零树的非重要性预测表明其指数增长的系数树，要比前者更 有效地多。正是通过这种零树结构，使描述重要系数( 闭r ) 的位置信息大为减 少。 岬舢也- - - - - - - - - - - - - - 一 l h ir 洲3 h l 2 i 、 h l l l l h 2 l u 洲 寓 1 3 l o ih h 3 h l 2 ， h l h h 2 h h l - 图3 一l 小波系数的零树结构 图3 2 重要图编码系数扫描顺序 3 2 2s p i h t 算法的提出 a 勋耐和彤a p e a r l m a r t 根据s h a p i r o 零树编码的基本思想，提出了一种新的 且性能更优的实现方法，即基于分层树集合分割排序( s e tp a r t i t i o n i n g 加 h i e r a r c h i c a lt r e e s ，妒f 坍) 的编码算法。即肼r 算法是一种非常实用有效的高性 能图像压缩编码算法，其显著特点是极低的计算复杂度和高质量的恢复图像，它 打破了传统编码算法中编码效率与复杂度同步增长的界限，并且合理利用了小波 分解后的多分辨率特性，获得了优良的编码性能。同现有的其它编码方法相比， 它不仅在性能上具有很高的信噪比和较好的主观视觉质量，而且编译码速度快， 同时具有内嵌编码的特征，能够终止于所需的码率或图像质量处，适合于逐渐浮 现式的图像传输。 1 ) 分层树集合分割排序结构 西安电子科技大学硕士学位论文 第三章适于硬p l ：实现的小波零树内嵌编码 内嵌编礤中首先传竣的是嫒重要的售愚，敷就是蠖值最大的交换系数鲶位售 息。图3 3 显示了个幅度值按由火到小排序后的变换系数的二进制列表。表中 每一到干表一个交换系数酶二进制表示，每一行代表一层彼平面，最上层为符号 使，越巍层螅位平鞭的傣息权燕越大，对予编璐也越重要。内嵌编码的次序是扶 最蘑要的位( 最高位) 到最不疆要的位( 最低位) 逐个发送，直到达到所需码率 后停止。 符号 7 6 5 毒 3 2 l ss s sssss 一 l l oooo oo ， lloooo l r 1il o ； l _ 图3 3 按曦度排序系数的二避剿表暴 由强3 3 胃知，内嵌编码韵输出信意燕要包捂两部分：排序信息和燕要像素的 缝售患。其中，位傣息怒编码必不霹少鳃有效镶患，对应予表中菠头埂越过的毙 特位；而排序信息则是辅助信息，反映了蓬要像素在原图中的空间位鼹，用于恢 复原始的数攒结构。困诧，雨嵌算法串j j # 序算法的优劣和排序信怠的处理决定了 整个编褥冀法的效攀。 s p i h t 算法是e z w 算法的改进，它继承了小波系数的零树结构，这里称作“空 间定位橱”结构。该算法将菜一树缩点及其所有后继结点矧归为同一集合，集合 的分割j 窭程是不錾她将一个集会分戏4 个子集褥分聚对每令子集进行霪要拣溅试 的过程。重要性测试函数定义为： f 1 ，m a ) ( l c ，b 2 * s 。( f ) = ，j ) “、“。 ( 3 - 1 ) b o t h e r w 括e 如果集念中辨寅元索的蠛僮小予某阙僮( 靼该豢会是不重要螅) ，烈使用一令比特 即可表示，这样就大大简化了集合的表示。由于变换系数在空间定位树结构中的 稠戗性，使采用这稀集合分割后的排序算法其脊高效率的特点。 2 ) 编码算法描述 a s a i d 和形a p e a l m a n 在上述原理基础上提出了基予空间定位树集会分割 嚣安呶子科技大学顶士学位论文 高效图象数据压缩及其硬件实现1 6 的编码算法。简单地说，s p i h t 算法分为四个部分，描述如下： ( 1 ) 初始化：输出胛= 1 0 9 ：( 错 i 1 ) ) j 到信道； ( 2 ) 排序过程：对于所有2 ”- - - - - c ，( k ) i 2 ”1 的系数，输出坐标玎( 后) 和符号位； ( 3 ) 细化过程：对于所有b j 2 “