（应用数学专业论文）体数据压缩的脊波算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 就像图像是由像素组成的集合一样，体数据( 三维数据) 是由一些体素组成 的集合，在工业c t 、医学( 如心脏超声波序列图像等) 、科学计算可视化、体图 形学以及c a d 领域都能涉及到体数据的处理。体数据的最大特点就是数据量大， 可以大到从几百兆到上万兆的字节，这为数据的存储和网络的传输都带来巨大的 压力。然而，相邻或相近体素之间存在着很强的相关性，这为体数据的压缩提供 了可能。另外，体数据中含有大量的线状或面状结构，它们是构成物体轮廓所必 不可少的基础成分，压缩后的体数据必须尽量保留这些结构信息。 近十几年，图像压缩方面研究较多且结果较好的方法是小波变换的方法。小 波方法在处理点状奇异性的问题时，能达到较好的效果，但在处理超平面状奇异 性( 包括线状奇异性和面状奇异性) 的问题时，就不再那么令人满意了。为了弥 补小波方法在处理超平面状奇异性问题时的不足，斯坦福大学的c a n d e s 和d o n o h o 在1 9 9 8 年提出了一种新的多分辨率分析工具一脊波，它能有效地处理超平面状 奇异性的问题。脊波和压缩的结合是一个新兴的研究问题，最近几年在这方面已 有初步的研究成果。但是这些研究，主要集中于二维图像。 函数的脊波变换可以通过在该函数的r a d o n 域上进行小波变换来实现，因此， 脊波变换可以按先做r a d o n 变换( 投影) ，再做小波变换的顺序来实现。本文就是 按照这个思路来实现脊波变换的，并将其应用到体数据( 包括c t 切片序列图像和 心脏超声波序列图像) 的压缩中。文中研究了两种压缩策略：策略一，先将体数 据划分成切片组，针对每张切片做2 d 脊波变换，脊波变换由平行束投影( 2 d r a d o n 变换) 加l d 小波变换实现，再组织变换系数，然后做量化、熵编码等；策略二， 直接对体数据做3 d 脊波变换，脊波变换由锥束投影( 3 d r a d o n 变换) 加2 d 小波 变换实现，再组织变换系数，然后做量化、熵编码等。在组织变换系数时，考虑 到不同方向脊波变换系数间存在的相关性，使用了预测编码技术。 体数据脊波变换系数编码的使用，既保留了体数据的结构信息，又能得到较 高的数据压缩比。本文的体数据压缩算法具有渐进式编码和较强鲁棒性的特点 当数据传输时，由于受网络带宽的限制，无法在短时间内完成全部体数据的传输， 渐进式编码的设计能让接收端用户由粗到细地获得体数据信息，从而减少用户了 解体数据内容的等待时间；传输过程中的数据丢失是一个经常发生的问题，文中 根据体素间的相关性，利用相邻投影方向的脊波变换系数来补偿丢失的变换系数， 使得整个算法具有较强的鲁棒性。 比较而言，策略一解码数据质量较好；策略二消除了策略一因划分切片致使 重庆大学硕士学位论文中文摘要 切片间的相关性丢失的不足，使得压缩比有所提高。实验显示：将本文的方法同 j p e g 或者是基于小波变换的压缩方法相比，在解码数据质量大致相当的情况下， 本文的方法将拥有更高的压缩比。 关键词：体数据，脊波变换，渐进式编码，鲁棒性 n 里壅奎堂堡主兰垡丝塞 菱茎垫曼 a b s t r a c t a si m a g ei sc o m p o s e do fp i x e l ，c u b i cd a t ai sc o m p o s e do fv o x e l t h ef i r s t c h a r a c t e r i s t i co ft h ec u b i cd a t ai si t se n o r m o l l sd a t aa m o u n t ，w h i c hi sn o tc o n v e n i e n tf o r s t o r i n ga n dt r a n s m i t t i n go nt h ei n t e r n e t t h es e c o n dc h a r a c t e r i s t i co ft h ec u b i cd a t ai s t h a tt h e r ea r em a n yl i n e0 1 p l a n es i n g u l a r i t i e s ，w h i c ha r et h eb a s i ce l e m e n t so f t h ec u b i c d a 饥 c u r r e n t l y , t h em o s tp o p u l a rc h o i c ef o ri m a g ec o m p r e s s i o ni sw a v e l e tt r a n s f o r m t h es l l c o e s so fw a v e l e t si sm a i n l yd u et ot h eg o o dp e r f o r m a n c ef o rp i e c e w i s es m o o t h f u n c t i o n si no n ed i m e n s i o n u n f o r t u n a t e l y , t h i si sn o tt h ec a s ei nh i g h e rd i m e n s i o n s f o r d e s c r i b i n gt h ei m a g e sw h i c hh a v el i n e a ro rs u p e r - p l a n es i n g u l a r i t i e s ，i n1 9 9 8 ，c a n d e s a n dd o n o h op r o p o s e dan e w a n a l y t i ct o o d g e l e t a tp r e s e n t t h e r eh a v eb e e naf e w s u c c e s s f u lr e s e a r c h e so nc o m p r e s s i o nu s i n gr i d g e l e t u pt on o w , t h e s er e s e a r c h e s m a i n l yc o n c e n t r a t eo nt h ee a s eo f 2 - d s i m p l ys p e a k i n g , t h ef i d g e l e tt r a n s f o r mi sp r e c i s e l yt h ea p p l i c a t i o no fa w a v e l e t t r a n s f o r mt ot h ed o m a i no ft h er a d o nt r a u s f o 衄s o i np r a c t i c a lw o r k , d ot h er a d o n t r a n s f o r m ( p r o j e c t i o n ) a tf i r s t , t h e nd ot h ew a v e l e tt r a n s f o r mi nt h er a d o nd o m a i n i n t h i st h e s i s o i lt h eb a s i so ft h er i d g e l e tt r a n s f o r m ，t w oc o m p r e s s i o ns w a t e g i 嚣a t e r e s e a r c h e dt ot h ec u b i cd a t a , i n c l u d i n gt h ec ts e r i a li m a g e s ，e c h o c a r d i o g a p h i cs e r i a l i m a g e sa n d8 0o n i nt h e s em e t h o d s ，t h er a d o nt r a n s f o r mi s r e a l i z e db yp a r a l l e l p r o j e c t i o n ( 2 - dr a d o nt r a n s f o r m ) i nt h ef i r s ts t r a t e g ya n dc o n eb e a mp r o j e c t i o n ( 3 d r a d o nt r a n s f o r m ) i nt h es e c o n ds t r a t e g y , t h e nd o i n gw a v e l e tt r a n s f o r m , c o e f f i c i e n t s o r g a n i z i n g , q u a n t i z a f i o na n de n 心o p yc o d i n g i nt h ec o u r s eo fc o e f f i c i e n t so r g a n i z i n g , w eu s em e t h o do f o f i e n t a f i o ns a m p l i n ga n df o r e c a s t d u et ot h ef i d g e l e tt r a n s f o r mc o e f f i c i e n t sc o d i n g , t h ec o n s t r u c t i o ni n f o r m a t i o no f t h ec u b i cd a t aa t ek e p t , a n dt h ec o m p r e s s i o nr a t i oc a r tb ei m p r o v e d o t h e rh a n d ，t h e s e s t r a t e g i e sh a v ef o l l o w i n gc h a r a c t e r i s t i c s ：g r a d u a l l yc o d i n ga n dr o b u s t n e s s b e c a u s eo f g r a d u a l l yc o d i n g , b s e r sc a nc a t c ho nt h ec o n t e n to f t h ec u b i cd a t aa tt h e i rf i r s tt i m e , t h e n t od e c i d ed e c o d i n gt og oo no rn o t i nt h es t o r a g eo rt r a n s m i s s i o no ft h ec u b i cd a t a , t h e l o s sc o e f f i c i e n t s 啪b ec o m p e n s a t e du s i n ga d j a c e n tv a l i do r i e n t a t i o n s t h ec 弱eo f l o s i n g1b y t ed a t a , t h ew h o l er e c o n s t r u c td a t a i sn u l l ，w i l ln o th a p p e n c o m p a r a t i v e l ys p e a k i n g , e a c ho f a b o v et w o s t r a t e g i e sh a si t so w ns t r o n gp o i n t ，t h e f i r s to n oh a sb e t t e rd e c o d i n gq u a l i t y , t h es e c o n do n eh a sm o r ec o m p r e s s i o na b i l i t y i 重庆大学硕士学位论文 英文摘要 s e e i n gf r o mo u ee x p e r i m e n t s r e s u l t s ，w h e nt h ee x t e r n a lv a l u e sa r ea l m o s te q u i v a l e n t , t h ec o m p r e s s i o nr a t i oo fo u rm e t h o di sg r e a t e rt h a nt h o s eo fj p e gm e t h o do rm e t h o d b a s e do nd 、t k e y w o r d s ：c u b i cd a t a , r i d g e l e tt r a n s f o r m ，g r a d u a l l yc o d i n g , r o b u s t n e s s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：李啄易j 学位论文版权使用授权书 本学位论文作者完全了解 重废盔堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废盍堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：季索倒 导师签名： 签字日期：阳7 年6 月，日 l 耖星 签字目期：却年i 月日 重庆大学硕士学位论文1 绪论 1 绪论 1 1 课题的提出及研究意义 图像( 二维数据) 是由像素组成的集合，而体数据( 三维数据) 根据来源和 处理方式的不同，通常有下列两种表示方法【l 】：体素( v o x e l ) 或体元( c e l l ) 。 每一体素可视为体空间中，中心在网格点的一个立方体，且对应一定的常数 标量值。体素代表了其周围邻域方格点值的平均值。基于体素的数据集通常由实 验方法直接采集得到。 将体空间划分为若干个小的子域即体元，体元通常是由若干顶点及连接相邻 点的边组成的空间区域( 如四面体、六面体或其它不规则区域) 。体元数据集可分 为规则和不规则两类，规则数据集是指各体元均为大小相同的正六面体。由于数 据场边界及其分布的复杂性，为适应计算的要求，体元常取不规则的形状，如有 限元网格等。由数值模拟产生的多维数据集，体数据集一般以体元表示。 本文中的体数据表示方法采用体素的方法。 体数据的最大特点就是数据量大，可以大到从几百兆到上万兆的字节。如美 国的可见人体( v i s i b l e h u m a n ) 计划，其数据量大到3 9 g 字节【2 】，又如c t 中的一 次三维重建数据就能达到8 g 字节等。对于如此庞大的数据量，若不经压缩，数据 传输所需的高传输率和数据存储所需的巨大容量将给存储器容量、传输线的传输 率以及计算机的处理速度等带来巨大的压力。因此，对数据的压缩就成为了技术 进步的迫切需求，正是由于这种需求，使得压缩编码算法和技术成为近3 0 年来非 常活跃的一个研究领域。 体数据的获取是通过获取设备( 如二维c t 、三维c t 、超声波扫描等) 对真 实物体进行测量而得到的组二维断层图像或三维数据，也可以是对计算机模型 的离散采样而构成的二维断层图像序列或三维数据。一般来说，这些断层图像都 含有噪声( 点状) ，除此之外，层内和层间还含有大量的线状、面状结构，他们是 构成物体轮廓所必不可少的基础成分，压缩后的数据必须保留这些结构信息。现 有的方法对处理点状奇异性的数据能达到较好的效果，但在处理线状、面状等超 平面状的奇异性时，不是太令人满意【3 】。因此，有必要对含有超平面状奇异性的体 数据研究新的压缩方法。 1 2 图像压缩的发展史 1 2 1 图像压缩编码的可能性 图像压缩编码得以实现的两个主要依据是人类视觉系统的特性和数据的统计 重庆大学硕士学位论文1 绪论 特性【4 。 一，人类视觉系统的特性 我们可以将人类视觉系统看做一个通常意义下的输入输出系统，而其输入和 输出之间的关系就是视觉特性。人类视觉系统主要表现出以下几种特性： ( 1 ) 对比灵敏度。在数字图像中，图像的亮度表示为一系列的离散值，即灰度 值。实验表明，视觉系统很难正确判断亮度的绝对大小，然而当判断两亮度中何 者较大时，视觉系统则有较好的能力。这就是说，人眼有较好的对比灵敏度。利 用此特性，只要保证图像压缩处理后的亮度信息与原图像有比较一致的对比度即 可，而不要求有很大的亮度范围。 ( 2 ) 空间分辨率。空间分辨率指人眼区分相邻的两个发光点的能力通常用能 够分辨的两个发光点之间的最小视角表示，该视角一般为1 。这说明人眼的空间 分辨力是有限的。视角小于某个值时，人眼将无法分辨相邻的像点，也就是说， 当图像沿空间上的任一方向变化太快时，将超出人眼的接受范围。因此，从空间 频域上看，人眼视觉呈低通特性。 ( 3 ) 时间分辨力。时间分辨力指人眼对于随着时间而变化的目标的分辨力。由 于人眼的视觉惰性和频闪效应等使人眼的视觉特性从时间频率域上看，也呈低通 特性。 ( 4 ) 可见度域值。指人眼刚好能发现的干扰值，低于该域值的干扰是察觉不出 来的。 通过上面的分析，可以看出人眼的视觉能力在诸多方面都是有限的。因此， 可以对原始图像中许多人眼不敏感的信息不予处理，从而实现图像数据的压缩处 理。 二、数据的统计特性 研究数据的统计特性也是一项非常必要和有意义的工作。因为数据抽样值本 身存在的一些联系和规律，对数据压缩具有指导的意义。下面从空间域和频率域 两方面来讨论数据的统计特性。 ( 1 ) 数据的空间域统计特性。在空间域中，数据表现为在空间上分布的点阵。 通过观察发现相邻或相近的数据，其值总是相近的。这说明相邻或相近数据间存 在很强的相关性。 ( 2 ) 数据的频率域统计特性。在频率域上，数据表现为不同分量系数的分布， 按照空间域和频率域的对应关系，空间域中的强相关性，即数据存在大量的平坦 区域，反映在频率域中就是数据的能量集中于低频部分。 通过上面对数据统计特性的分析，发现大多数相邻或相近数据之间有较大的 相关性，这就会造成信息冗余。信息冗余会造成编码时比特数的浪费，消除这些 2 重庆大学硕士学位论文l 绪论 冗余可以节约码字，从而实现数据压缩的目的。 1 2 2 图像压缩的发展历程 图像编码理论的研究起源于上个世纪4 0 年代末的香农信息理论，直到7 0 年 代后，随着大规模集成电路和计算机科学的迅速发展，各种图像的压缩编码技术 和传输技术才得以发展和成熟。 早在1 9 4 8 年，o l i v e r 就提出了电视信号的p c m ( p u l s ec o d em o d u l a t i o n ，简 写为p c m ) 编码理论。 1 9 5 2 年，o l i v e r 、k r e t z m e r 、h a r r i s o n 将线性预测用于预测编码。 1 9 5 8 年，g r a h a m 首次用计算机模拟实验的方法，研究静止图像差值预测 d p c m ( d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n ) 编码法，获得了3 - 4 b p p 的图像质量的 良好效果1 6 】。 1 9 6 6 年，o n e a l 对三种典型静止图像做了系统研究，为预测编码法奠定了理 论基础【，j 。 6 0 年代末到7 0 年代初，出现了图像的变换编码。最初的概念是建立在f o u r i e r 变换、h a d a m a d 变换、k a r h u n e n - l o e v e ( k l ) 变换以及余弦变换的基础上。此后， 其它的图像变换编码方法才发展起来。1 9 6 9 年在美国召开的第一届图像编码会议 标志着图像编码作为一门独立的学科诞生了。 1 9 8 0 年，l b g 算法的提出，使矢量量化( r e o rq u a a t i z a t i o n ，简称v q ) 的 研究从理论走向实用，矢量量化在图像编码中的应用从此得到迅速发展。g e r s h o 、 b a k e r 、m u r a l k a m i 等许多学者对v q 进行了研究，出现了一系列矢量量化方案， 使v q 在当时成为新的研究热点。 8 0 年代末到9 0 年代初，自适应离散余弦变换( a d a p t i v ed i s c r e t ec o s i n e t r a n s f o r m ，简称a d c t ) 编码技术已趋成熟，先后建立了三个国际标准，即电视 电话脍议电视的h 2 6 1 国际标准、静止图像的p e g 国际标准和活动图像的m p e g 国际标准。其中a d c t 技术以其综合的优越性成为首选技术标准。 8 0 年代中后期，相关学科的迅速发展和新兴学科的不断出现为图像编码的发 展注入了新的活力。许多学者结合模式识别、计算机图形学、计算机视觉、神经 网络、小波分析和分形几何等理论开始探索信号压缩编码的新途径。同时，关于 人类的视觉生理、心理特性的研究成果也打开了人们的新视野，许多新型的图像 压缩编码技术相继出现：m k u n t 于1 9 8 5 年提出利用人眼视觉特性的第二代图像编 码技术；m b a m s l e y 于1 9 8 8 年提出基于迭代函数系统( i f s ，i t e r a t e df u n c t i o n s y s t e m ) 的分形图像编码技术( 8 】：s m a l l a t 、i d a u b c c h o s 于1 9 8 9 年将小波分析理论 应用于图像编码以及9 0 年代初发展起来的基于模型的图像编码方法等。 小波分析已成了一门学科。它涉及面之广，影响之深远，发展之迅速都是空 重庆大学硕士学位论文 1 绪论 前的，其应用成就更是令人瞩目。数据压缩是它的一个最为活跃的应用分支之一。 如今，在视频压缩国际标准m p e g - 4 以及静止图像压缩标准j p e g 2 0 0 0 中，小波算 法已被视为核心算法。小波在应用中有着自己强大的灵活性，如小波基的选取、 分解层数的确定、以及小波包分解等各种方法。经小波变换后，信号的能量集中， 变换系数有着自己独特的性质，这些使得对小波系数量化的方式层出不穷，越来 越吸引着广大科研工作者的兴趣。 实践的需要推动了小波分析的进一步发展，多尺度分析和奇异性分析不断有 新的进展，脊波( r i d g e l e t ) 、曲波( c u r v e l e t ) 等就是近年来研究的最新成果。它 们的发展推动着许多其它学科和相关领域的发展，也使得其本身具有多学科相互 结合、相互渗透的特点。相关的新理论、新方法及新应用的研究探讨非常活跃。 1 3 本文的研究内容 本文选用的体数据包括工业c t 切片序列图像和心脏超声波序列图像：工业 c t 切片序列图像选用公开的发动机切片序列图像 9 1 心脏超声波序列图像的获取 使用仪器p h i l i p ss o n o s 2 5 0 0 通过b 型扫描得到。 众所周知，小波在处理h 维空间点状奇异性( 突变) 的问题时，能达到较好的 效果【1 0 l ，但在处理超平面状( 如线状、面状等) 奇异性的问题时，小波方法就不 再那么令人满意了。 为了弥补小波方法在处理超平面状奇异性问题时的不足，斯坦福大学的e j c a n d e s 和d l d o n o h o 在1 9 9 8 年提出了一种新的多分辨率分析工具脊波 1 1 , 1 2 1 。 脊波和压缩的结合是一个新兴的研究问题，最近几年在这方面已有初步的研究成 果。2 0 0 0 年，m n d o 和m v e t t e r l i 通过比较有限脊波变换( f 黜t ) 和离散小波 变换( d w t ) 在非线性逼近方面的表现，揭示出脊波用于压缩具有线性特征图像 的潜力0 3 1 。2 0 0 3 年，l g - r a n a i 、em o s c h e t t i 和ev a n d e r g h e y n s t 提出了一种适用于 图像补偿的，脊波+ 2 - d 小波的方法【1 4 】，该方法同时利用了脊波对线性奇异性的处 理能力和小波对点状奇异性的处理能力。2 0 0 4 和2 0 0 5 年，袁修贵、宋守根、张安 等人，将脊波变换和嵌入式零树编码相结合，分别应用到地震数据和图像的压缩 中【1 5 , 1 6 。2 0 0 6 年，张选德和宋国乡设计了一种基于脊波变换的适用于具有线性特 征图像的有损压缩算法，该算法与j p e g 2 0 0 0 相比，在保持较高信噪比的情况下， 能获得更高的压缩率【l ”但到目前为止，脊波用于压缩的研究主要集中在二维情 形。 本文选用脊波作为研究体数据压缩的工具，一方面是因为脊波作为一种新的 多分辨率分析工具，它的一些优良特性尚处于研究阶段，我们的工作相当于一种 有益的探索；另一方面是因为在实际的体数据中，数据的奇异性主要是以线状、 4 重庆大学硕士学位论文i 绪论 面状等超平面状形式而存在，而脊波在处理高维空问超平面状的奇异性问题时有 它适用的一面。 1 4 本文的结构安排 论文共分六章，分别安排如下： 第一章为绪论，包括课题的研究意义、图像压缩的发展、论文的研究内容及 章节安排。 第二章主要介绍压缩的基础理论和方法。 第三章主要介绍小波、脊波的基本理论，实现小波变换、脊波变换的不同方 法，并在非线性逼近能力方面对两者作了实验比较。 第四章主要介绍由我们研究的基于脊波变换的体数据压缩方法。 第五章主要展示相应的数字实验结果。 第六章为对本论文工作的总结和未来工作的展望。 5 重庆大学硕士学位论文 2 压缩的基础理论和方法 2 压缩的基础理论和方法 2 1 编码基础 2 1 1 数据压缩的概念 信息时代带来了“信息爆炸”，使数据量大增，因此，无论传输或存储都需要对 数据进行有效的压缩。数据压缩就是减少表示信号所需的数码，从而减少容纳给 定消息集合或数据采样集合的物理存储空间，进而减少数据传输所需要的时间区 间与电磁频谱区域。 数据之所以能被压缩，是因为数据中存在着冗余。体数据冗余主要表现为相 邻或相近体素间的相关性引起的冗余。压缩的目的就是通过去除这些数据冗余来 减少表示体数据内容所需的比特数。 数据压缩一般分为无损压缩和有损压缩两类。无损压缩( 也称可逆压缩) ：原 始数据可以从压缩后的数据中完全重新构造出来，即压缩是完全可恢复的或没有 偏差的，信息没有损失。典型的无损压缩有h u f f i n a n 编码、f a n o s h a n n o n 编码、 算术编码、游程编码、l e m p e l - z e v 编码等。有损压缩( 也称不可逆压缩) ：允许重 构数据与原始数据存在一定的误差，但视觉或听觉效果一般是可被接受的，或者 能够满足用户的要求。典型的有损压缩有预测编码、子带编码、变换域编码等。 长期以来，人们都在不懈努力寻找新的数据压缩算法，以满足日益增长的压 缩需求，并提出了各种国际压缩标准，如p e g ，j p e g 2 0 0 0 ，h 2 6 3 ，h 2 6 4 ，m p e g 1 ， m p e g 2 ，m p e g - 4 ，m p e g 一7 以及m p e g 2 1 等。 2 1 2 压缩的性能评价 在数据的有损压缩中，编码恢复的数据与原始数据存在偏差。为了评价数据 压缩性能，人们引入保真度准则来度量这种偏差。在数据压缩性能评价中，常用 的准则有客观保真度与主观保真度。 令f ( 1 ，r a ，n ) 表示原始体数据，( ， m ，功表示解压后的体数据，f ( 1 ，m ，珂) 与 尹( f ，r t l ，弗) 之间的偏差为( 3 1 e c t ，m ，n ) = f ( 1 ，m ，n ) 一，u ，m ，帕 ( 2 1 ) 假定体数据尺寸大小为l x m x n ，它们之间的均方根误差p 。为 f ，lmn、1 1 2 e 柑。 z 南善萎善e “棚川) 2 偿萄 可以采用均方根误差e 。作为客观保真度，进行体数据压缩性能评价。体数据 压缩的性能评价还应与压缩比c r 结合起来考虑。压缩比定义为表示原始体数据所 需的比特数与编码后所需的比特数之比。在相同的压缩比下，均方根误差越小， 6 重庆大学硕士学位论文 2 压缩的基础理论和方法 性能越好。反过来，在相同的均方根误差下，压缩比越大，性能越好。 常用的客观保真度还有信噪比s n r 与峰值信噪比p s n r ，对于8 b i t ，2 5 6 级灰 度而言3 1 ， s ! r = l o l m np ( ，胛) 一f 4 ( 1 m，m ，九) f【厂( ，胛) 一 ，九) j ，- im = ln = l r 愿凇= l 。l g t 2 5 5 x 2 5 5 t ( 2 3 ) ( 2 4 ) 式中，s n r 与p s n r 的单位均为分贝( d b ) 。在相同的压缩比下，信噪比s n r 或峰值信噪比p s n r 越大，性能越好。反过来，在相同的信噪比s n r 或峰值信噪 比p s n r 下，压缩比越大，性能越好。 主观评价是指人对解压体数据质量的主观感觉。因为解压体数据最终是给人 观看的，从而在压缩性能评价中，主观评价往往更合适、更重要。一种常用的主 观评价方法是，把解压体数据显示给一组观察者，把他们对该解压体数据的评价 结果加以平均，以该结果来评价解压体数据的主观质量。主观评价可参照某种绝 对尺度，表2 1 所列是两种典型的评分标准p 】。 表2 1 解压体数据质量的主观评分标准 t a b2 1t h es u b j e c te v a l u a t e ds t a n d a r do f d e c o d i n gc u b i cd a t a 得分第一种评价标准第二种评价标准 5非常好 感觉不到失真 4 好感觉到失真，但没有不舒服感觉 3一般 稍有感觉到不舒服 2较差 不舒服 1 差 非常不舒服的感觉 2 2 统计编码 体数据中存在冗余，编码就是尽可能去除体数据中的冗余成分，以最小的数 码率传递最大的信息量。对于无记忆的信源，可以利用体素值出现概率的不均等 性，采用统计编码方法来压缩数码率。统计编码就是根据数据出现概率的分布特 性而进行的压缩编码。常用的统计编码有霍夫曼编码( h u f f m a n ) ，算术编码与行 程编码。对于有记忆的信源，首先要进行去相关处理，如d p c m 、k l t 、d c t 、 7 重庆大学硕士学位论文 2 压缩的基础理论和方法 d w t 等，再利用统计编码来压缩数码率。 2 2 1 编码效率与冗余度 编码效率与冗余度是用来衡量编码方法优劣的准则。设“，v ：，v ，) 为一个离 散无记忆信源，具有个消息，其中消息v t 出现的概率为p ，o = l ，) 该信源 可用如下的形式来表示【3 】 z ； m v 2 m ( 2 5 ) l p l , p 2 ，p j 信源x 的熵为 上 h ( x ) = 一p ll 0 9 2p t ( 2 6 ) i f f i l 从字母集a = o ，1 ) 中选取0 或1 对信源x 进行无失真编码，假设厶表示对v 。的编 码长度，则平均码长为 一 l = y p ，厶 ( 2 7 ) 扭l 由信息论可知，熵h ( x ) 是离散无记忆信源进行无失真编码时的基本极限，即找不 到平均码长比其更短的无失真编码，也就是 h ( 石) l( 2 8 ) 编码效率定义为 ，7 ：塑1 0 0 ( 2 9 ) l 编码效率表示平均码长三与基本极限h ( x ) 的接近程度。如果r 1 0 0 ，表明 编码还有冗余度。冗余度定义为 r d = 1 - r ( 2 1 0 ) 统计编码的关键问题就是尽量减小平均码长云，使编码效率玎趋近于l ，或者 使冗余度局趋近于0 。可阱根据这一准则来衡量编码方法的优劣。 2 2 2 霍夫曼编码 霍夫曼编码是h u f f i u a n 于1 9 5 2 年提出的一种无失真编码方法，该方法根据消 息出现的概率来构造平均码长最短的异字头码字，因此，有时称之为最佳编码。 可以证明，在变长编码中，若各码字长度严格按照所对应消息出现概率的大 小逆序排列，则其平均码长为最小。根据这个结论，编码步骤如下【3 】： ( 1 ) 将信源中的消息按出现的概率从大到小的顺序排列。 ( 2 ) 将两个最小的概率组合相加，并把相应的两个消息并成一个消息；继续 这一步骤，始终按出现的概率从大到小的顺序排列消息，直到概率达到1 为止。 ( 3 ) 对每对组合的消息中前一个赋l ，后一个赋0 ( 或反过来) 。 ( 4 ) 对于每个信源消息，跟踪其概率到l 处的路径，记下该路径的1 和0 ， 3 重庆大学硕士学位论文 2 压缩的基础理论和方法 从右到左得到一个0 ，1 序列，即为霍夫曼码。 2 2 3 算术编码 算术编码从整个符号序列出发，采用递推形式进行连续编码。假设信源符号 及其概率为 吼 口2 ，口埘 ，序列 而h 的算术编码步骤如下【3 】： 【p l ，p 2 ，p j 一 ” ( 1 ) 首先在0 和l 之间给每个符号分配一个初始子间隔，子间隔的长度等于 rfi、 它的概率，初始子间隔的范围用 p j - i p ，i 表示，其中，i = 1 ，2 ，历，p 。= 0 。 l j - , j = l 假设第一个输入符号为x i = 4 。，令 厂lf、 一= 1 ，1 1 = 阢，吒) = l p j - i p jl 而= n - l i ，l = i i ，r = ( 2 1 1 ) l j = l j = l ( 2 ) 工和r 的二进制表达式分别表示为 三= 2 - t , r = 2 。 ( 2 1 2 ) 式中，i , t 和v 。等于“1 ”或者0 。 比较和v 1 ：如果”l v 1 ，不发送任何数据，转到( 3 ) ；如果= ，就发送 二进制符号。比较“2 和v 2 ：如果“2 吃，不发送任何数据，转到( 3 ) ；如果”：= 9 2 ， 就发送二迸制符号。依次类推，这种比较一直进行到两个符号不相同为止，然 后进入( 3 ) 。 ( 3 ) 以加1 ，读入下一个符号。假设第n 个输入符号为工= 口，按照以前的 步骤把这个间隔分成如下所示的子间隔，即 l = k ，) = if 。+ d 。艺，。，一。+ 以一。艺al ( 2 1 3 ) l k il = l 令上= ，r = ，d 。= 一，然后转到( 2 ) 。 2 2 4 行程编码 在一些待编码的信源序列中，有些符号经常连续出现，例如，传真图像如果 按行扫描，则经常出现连续的0 或连续的1 ；另外，在有失真编码时，信号经过变 换和量化后的系数，经常出现连续的0 。针对这些情况，可以采用行程编码1 3 】。 一种行程编码的形式是，功，如果连续出现矿值工次，则可以用这个偶表示。 假设一个扫描行片断为0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 ，就可以用行程编码，编码为如下4 个偶： ( 4 ，o ) ，( 6 ，1 ) ，( 2 ，o ) ，( 3 ，1 ) 。一种常用的行程编码方式为零行程，一般用 于有失真编码的量化后的系数编码。零是唯一经常出现的连续值，而其它值是任 意的。在这种情况下，行程数只用于表示连续0 的个数，而偶中的数值y 用于表 示0 串后紧跟的非零值。这种零行程编码也用一个偶( 厶y ) 表示。例如0 0 0 、5 、o o 、 l 、0 0 0 0 0 0 、一3 ，用零行程编码表示为：( 3 ，5 ) ，( 2 ，1 ) ，( 6 ，3 ) 。实际应用中， 9 重庆大学硕士学位论文2 压缩的基础理论和方法 行程编码伍，n 中的和矿可以分别用h u f f r n a n 编码或算术编码做进一步的压缩。 2 3 预测编码 预测编码是一种简单、有效的编码方法，其基本原理是利用线性预测技术去 除体素间的相关性，对预测值与实际值之间的差值进行量化与编码，而不直接对 原始数据进行量化与编码，从而提高编码效率。 2 3 1 预测编码的基本原理 对于输入体数据的体素值序列六( 甩= 1 , 2 ，) ，利用体素之间存在的相关性，根 据若干过去的体素值对当前体素值进行预测，得到估计z ，预测误差为【4 】 e 。= 五一丘 ( 2 1 4 ) 实际应用中，一般采用线性预测，即 六= q 厶 ( 2 z s ) 式中，研表示预测的阶数，a l ( f = l ，m ) 为预测系数。预测误差为 岛= 正一口t ：一， ( 2 z 6 ) 线性预测估计z 与正比较接近，预测误差序列巳( 捍= 1 ，2 ，的取值都将落在 零附近的较小范围内。理论研究表明，通过预测可以去除大部分体素间的冗余， 预测误差序列( 忍= 1 ，2 ，”可近似为互不相关，且都近似服从均值为0 的拉普拉斯 ( l a p l a c e ) 分布3 1 ，即 砟卜去叫一剥 仁切 式中，口为预测误差的取值，吒为e 。( 开= 1 , 2 ，) 的均方差。 熵是概率分布的函数，分布越均匀，熵越大，其平均码长的下限越大，从而 表示每个消息所需的比特数( 码率) 就会增高；反过来，分布越集中其熵越小， 平均码长的下限越小，从而码率就会降低。预测误差的方差比原始体数据的方差 小，其概率分布比原始体数据更集中，从而，预测误差的熵比原始体数据的熵要 小。因此，预测编码不直接对原始体数据进行量化与编码，而对预测误差进行量 化与编码，从而提高了编码效率。 2 3 2 差值脉冲编码调制 差值脉冲编码调制( d p c m ，d i f f e r 即f i a lp u l s ec o d em o d u l a t i o n ) 是一种最典 型的预测编码方法。d p c m 系统框图如图2 1 所示【4 】。 l o 重庆大学硕士学位论文 2 压缩的基础理论和方法 解 图2 1d p c m 系统框图 f i g2 1d p c ms y s t e m 在图2 1 中，预测器位于一个反馈环中，其输入为过去的预测及其对应预测误 差的量化输出的函数，即 一= 六+ t ( 2 1 8 ) 这种闭环结构能够避免在解码器的输出端产生误差。 一般地，预测器采用线性预测，量化器采用标量量化，符号编码器采用统计 编码。 在d p c m 中，德尔塔调制是一种最简单的编码方法，其预测器与编码器分别 定义为 六= 彰 ( 2 1 9 ) t = 三篡 式中，a 为预测系数( 一般不超过1 ) ，c 为一正常数。此时，编码器的输出只有2 个值，从而只需1 个比特来表示，即德尔塔调制的码率为l 比特像素。 2 4 变换编码 前面介绍的预测编码技术就是直接在体数据空间对体素值进行处理，利用线 性预测去除冗余，因而称为空域方法。在体数据的压缩处理中，还有另一类主要 方法一变换编码，它是先对体数据进行变换，使得变换域中数据问的相关性减 小或互不相关，从而减小冗余度，再进行量化与编码，实现体数据的压缩。常用 的变换有正交变换( 如d f t ，d c t ，w h t ，k l t 等) 与小波交换( d w t ) 。 2 4 1 变换编码系统结构 在变换编码中，采用某种变换把原始体数据映射到变换域中，得到一组变换 系数，然后对变换系数进行量化与编码。一般地，变换系数间的相关性为零或较 小，并且原始体数据的能量主要集中在少数系数上，大多数系数的数值都很小， 重庆大学硕士学位论文 2 压缩的基础理论和方法 这些系数可较粗糙地量化，或者完全忽略，只产生较小的失真。变换编码系统框 图如图2 2 所利4 】。 解压 解 码嚣 图2 2 变换编码系统框图 f i g2 2t r a n s f o r mc o d i n gs y s t e m 采用正交变换时，首先要把体数据分割成若干个大小为，l 开行的子块，再分 别对各个子块进行变换。小波变换是全局变换，采用小波变换时，不需要把体数 据分割成若干个子块，而只需把整个体数据作为输入，再进行变换。变换的目的 就是去除体素间的相关性，并将尽可能多的信息集中到尽可能少的变换系数上。 量化模块对变换系数进行量化，可单独采用标量量化或矢量量化，也可以结 合起来使用。考虑到大多数变换系数的数值都很小，并且它们对重建数据的质量 影响较小，可以有选择地对这些系数进行粗糙量化，或者完全忽略不计。在变换 编码中，信息的失真主要是在量化阶段产生的。 符号编码把量化得到的符号流表示为比特流，以达到压缩体数据的目的。量 化得到的符号可能是量化输出系数，也可能是表示量化输出系数的代码，一般采 用熵编码。最后把压缩后的数据进行存储或传输。 解码端由与编码端相反排列的一系列逆操作模块构成，即符号解码、反量化 与反变换三个模块。其中，反量化模块把符号映射成量化电平。若采用正交变换， 还需要把各个子块合并成一个完整的体数据。 2 4 2 正交变换编码 2 4 2 1 正交变换的特点 在正交变换编码中，采用正交变换，如d f t ，d c t ，w h t ，k l t 等，对体数 据进行变换。正交变换具有如下优点【4 】： ( 1 ) 熵保持。正交变换具有熵保持性质，即正交变换不丢失信息，从而通过 传输变换系数来传送信息。 ( 2 ) 能量集中。交换域中的能量多集中于少数变换系数上，大多数系数的数 值都很小。对于能量