（生物医学工程专业论文）静态医学图像和序列医学图像编码新方法研究.pdf

a b s t r a c t w i t ht h em a t u r i t yo ft h ew a v e l e ta n df r a c t a lt h e e r yi nr e c e n t y e a r s ， i m a g ec o d i n gs c h e m e s b a s e do nt h e s et w ot h e o r i e sh a v eb e c o m et h e r e s e a r c hf o c u s a tt h es a m et i m e ，m e d i c a li m a g i n gt e c h n i q u e sh a v e a c h i e v e dt r e m e n d o u sa d v a n c e s ，w h i c hp r o v i d ev a n o u sk i n d so fn e w i m a g ew p e s t h a te f f e c t i v e l yi n c r e a s et h e a c c u r a c y o ft h ed i a g n o s i n go f h u m a nd i s e a s e s u n d e rt h i st r e n d t h em a i nr e s e a r c he f f o r t sa r eo n p u t t i n gf o r w a r dn e w m e d i c a li m a g e c o d i n gs c h e m e s f o rt e l e m e d i c i n e b a s e do nw a v e l e ta n df r a c t a lt h e o n e s ，w h i c hs p e c i a l l yf i ti nw i t hc l i n i c a l r e q u i r e m e n t s t h em a i nc o n t r i b u t i o n s o fm yw o r ka r ea sf o l l o w s ： 1 ) p r o p o s i n gan o v e lw a v e l e ti m a g ec o d i n gs c h e m eb a s e do n p r e d i c t i v eq u a d t r e e s p l i t t h i sm e t h o dh y b r i d i z e st h ei n t r a - b a n da n d i n t e r - b a n dc o d i n g w a v e l e tc o e f f i c i e n t si ns a m eb a n da r ep a r t i t i o n e d i n t om a n y b l o c k s ，a n dt h eb l o c k ss p l i ta c c o r d i n gt oq u a d t r e ew i t ht h e m o v i n go fb i t p l a n e t h i sk i n do fd y n a m i cb l o c ks p l i t i n gc a no v e r c o m e s o m e s h o r t c o m i n g sb r o u g h tb y f i x e db l o c ks i z e a tt h es a m e t i m e ，t h e a l g o r i t h m i n t r o d u c e sa p r e d i c t i v ec o d i n gp r o c e d u r et o t r u n c a t et h e b l o c ka n dm a k et h eb l o c k ss h a p ef i ti nw i t ht h ea c t u a li m a g e ac o n t e x t b a s e da r i t h m e t i cc o d e ri sa d o p t e di ne n t r o p yc o d i n g ，a n df o u rd i f f e r e n t s e t so fm o d e l sa r ed e s i g n e df o rt h ea r i t h m e t i cc o d e rw h i c hc o u l db e a d j u s ta d a p t i v e l ya c c o r d i n gt od i f f e r e n tk i n d so fm e d i c a li m a g e s 2 ) p r e s e n t i n gaf a s tf r a c t i o nc o d i n gs c h e m ef o rf a s ts e q u e n c e m e d i c a li m a g ec o d i n gb a s e do nt h ep r i n c i p l eo fo f c ( o p t i m a lf u z z y c l u s t e r i n g ) t h ea l g o r i t h mm a k e su s eo fl b gm e t h o dt oi n i t i a l i z et h e s e a r c h i n gs p a c e ，t h e nf u z z yc l u s t e r i n ga l g o r i t h mi sa p p l i e dt og i v ea s o f tc l a s s i f i c a t i o no ft h e s e a r c h i n gs p a c e g l o b a ls e a r c h i n gi sr e p l a c e d b ys e a r c h i n gi nt h er e s u l t i n gc l a s s e sa n df r a c t a lc o d i n gi sf o c u s e do n t h em o s te f f e c t i v el o c a l a r e a ，t h u st h en e wa l g o r i t h m s i g n i f i c a n t l y r e d u c et h em a t c h i n gt i m e sa n d c o d i n gc o m p l e x i t y s i m u l a t i o nr e s u l t s 至= 耋! 薹奎耋兰i ：耋堡篁苎 s h o wt h ec o m p u t a t i o nt i m ei sr e d u c e db y5t i m e sc o m p a r e dw i t ht h e t r a d i t i o n a ls e q u e n c e i m a g ef r a c t a lc o d i n gs c h e m e s a tt h es a m ep s n r i e v e l k e y w o r d s = m e d i c a li m a g e ，i m a g ec o d i n g ，w a v e l e tc o d i n g ，o p t i m a l f u z z yc l u s t e r i n g ，f r a c t a lc o d i n g 1 1 概述 第一章绪论 1 1 1 医学影像学的进展【1 _ 1 2 】 1 9 7 2 年c t 的开发和应用，使医学影像学进入了一个以断层成像和 计算机图像重建为基础的新阶段，标志着医学影像学数字化进程的丌端。 随后，磁共振成像( m r ) 、放射性核素成像、超声成像、数字减影血管 造影( d s a ) 和数字x 线成像逐步成熟并应用于临床。各种新一代成像 设备，如多层螺旋c t ，m r 心脏、神经专用机等不断出现。2 0 0 4 年4 月1 2a ，美国食品和药物管理局f d a 向西门子公司研制的目前世界上 最快的s o m a t o ns e n s a t i o n 的6 4 层c t 给予了5 1 0 k 认证，它扫描一周 能够获得6 4 层图像，所用时间只有0 3 7 秒；每层厚在1 毫米以下，各 个方向上的空间分辨率是一致的0 4i l r n ，标志着医学影像设备的成像质 量、速度和图像数据量上又达到了一个新的阶段。 另外，影像技术与生物化学技术相结合，组织或疾病特异性对比剂 的开发和应用，使影像诊断不断拓展新领域，由大体形态学为主的阶段， 向生理、功能、代谢和基因成像过渡。医学图像分析由“定性”向“定量” 发展。诊断模式由胶片阅读向数字采集、存储和网络传输方向发展。另 外，随着生命科学的进展，分子生物学、生物和基因工程( 人类基因组、 疾病基因组学) 等将深入影响医学诊断技术的进程，生物医学成像 ( b i o m e d i c a li m a g i n g ) 和分子、基因成像( m o l e c u l a r 、g e n e t i c i m a g i n g ) 已经是当前研究热点。 总之，现代医学成像方式的越来越多源化，图像数据高维化、海量 化，图像信息网络化，在临床和科研中的应用范围越来越广泛。 医学成像技术不仅包括图像的产生，也包括图像的处理、显示、记 录、存储和传输。数字化的医学图像为图像存储和通讯系统( p a c s ) 的 发展奠定了基础。由于存储空问和带宽的限制，医学图像编码压缩是存 第一军医大学博十学位论文 储、检索等各种应用的前提。 1 1 2 图像编码技术 从计算机的角度看，图像是一种亮度对其位置的函数。一幅图像可 以看作是一个有限的数列或者矩阵，此过程称为空间采样；而亮度上的 数字化将得到图像亮度离散整数值，此过程称为量化。数字图像就是经 过采样和量化后的图像数据。图像矩阵中的元素就是像素( p i x e l ) ，一幅 图像可以看作是全体像素的集合。 人们已对传统的图像数据进行大量统计和视觉效果的研究，结果表 明：图像的相邻像素之间、相邻行之间或者相邻帧之间都存在着较强的 相关性，也就是图像信号存在诸如空间冗余、时间冗余、结构冗余、视 觉冗余和知识冗余等冗余，比如头颅c t 图像序列中相邻的两帧图像之 间具有相关性，头颅的形状，大脑灰质和白质的纹理都是可以利用的先 验知识，如果利用某种编码方法在一定程度上消除这些冗余，就可以实 现图像数据的压缩编码。 压缩编码过程是尽量将冗余信息去除，若恢复的图像与原始图像完 全一样，则属于无失真编码( l o s s l e s sc o d i n g ) ；若压缩编码过程是结合人 眼的视觉特性，抛弃了人眼视觉不敏感的信息，允许恢复的图像有定 的失真，则属于失真编6 马( l o s s yc o d i n g ) 。 一般来说，图像压缩包括两个过程：编码过程与解码过程。编码过 程通常可分为三个阶段： 1 ) 图像分解 图像分解也就是图像变换，其目的就是将相关性强的图像数据变换 成相关性弱的数据，即变换后数据的能量尽可能集中在少许系数上。图 像变换一般是线性变换( 如k l 变换、f o u r i e r 变换、d c t 变换、w a l s h 变 换、子带滤波、小波变换等等) ，其逆变换一定存在，以便于图像重构。 2 ) 量化 变换后数据的量化包括两种量化方法：标量量化( s c a l a rq u a n t i z a t i o n 简写s q ) 和矢量量化( v e c t o rq u a n t i z a t i o n ，简写v q ) 。标量量化是对单个 像素进行量化；而矢量量化是对一组像素进行量化。由于量化改变数据 值，将损失一些信息，使得原始图像与解码图像之间产生了一定的误差。 2 第一章绪论 3 ) 熵编码 量化后的数据经过无损熵编码( 如h u f f m a n 编码、算术编码、游程编 码等) 可以进一步压缩。 1 2 两种图像编码系统1 ”6 1 现代图像编码系统按其理论基础可以分成各有特点的两类：小波和 分形理论。9 0 年代出现了大量算法，主要包括分形压缩 1 。“j 、基于小波 变换的压缩方法【l 8 。”j 。 近几年小波图像压缩取得了很大的成功，这些算法都是成功地使用 了各自不同的具有创新性的方法，组织和表示塔式结构的小波系数，他 们利用小波变换各频带内部以及各频带之间的变换系数之间相关性是基 于小波变换图像编码的关键。 目前成功的编码方法主要分为带间编码与带内编码两类。具有多分 辨率分析特性的小波变换与人眼的视觉特性相符合，具有较好的时频局 部特性，有利于利用人类视觉系统对不同的图像的响应特性调整编码策 略，使编码策略灵活且符合人的主观视觉特性，而且这种多分辨率特性 可以非常自然地应用于图像的可分级压缩编码，基于小波变换的图像编 码方案在图像压缩领域获得巨大成功，当前流行的e w z 、s p i h t 、 j p e g 2 0 0 0 t 2 3 , 2 4 等编码技术均属此类算法。 其中最具代表性的j p e g 2 0 0 0 标准，它在编码端以最大的压缩质量 ( 包括无失真压缩) 和最大的图像分辨率压缩图像，在解码端可以从码 流中以任意的图像质量和分辨率解压图像，最大可达到编码时的图像质 量和分辨率。2 0 0 1 年被d i c o m 标准接纳后，j p e g 2 0 0 0 将在医疗影像编 码中得到了广泛应用。它的最能代表小波编码器一般特征的性质如下： 1 高压缩率：由于小波变换具有良好的空域和频域的局部性，和人眼 的视觉系统接近，很好的刻画了自然图像信号。在小波变换域里的数 据具有良好的局域性。其压缩比可以在现在的j p e g 基础上再提高l o 3 0 2 渐进的无损压缩和有损压缩：j p e g 2 0 0 0 提供无损和有损两种压缩方 式，无损压缩在许多领域是必须的，例如医学图像中有时不允许做有 第一军医大学博上学位论文 损压缩。同时j p e g 2 0 0 0 提供的是嵌入式码流，允许从有损到无损的渐 进解压。 3 感兴趣区域压缩：可以指定图片上感兴趣区域( r e g i o no f i n t e r e s t ) ， 然后在压缩时对这些区域指定压缩质量，或在恢复时指定某些区域的 解压缩要求。这是因为子波在空问和频率域上具有局域性，要完全恢 复图像中的某个局部，并不需要所有编码都被精确保留，只要对应它 的一部分编码没有误差就可以了。 分形编码也是图像编码中的一个重要研究方向。这是一种完全不同 于传统基于信源理论编码的方法，引入了利用局部和全局相关去除冗余 的新颖思想，突破了传统图像压缩方法的局限性，具较大潜力，近年来 吸引了众多的研究者。1 9 8 9 年b a r n s l e y 的学生j a c q u i n 提出了一种基于 局部迭代函数系统( p a r t i t i o n e di t e r a t e df u n c t i o ns y s t e m ，p 1 f s ) 的可以真 正自动实现图像压缩的算法分形块编码，使分形编码耿得了突破性 进展，从而使之从实验室研究走向应用成为可能。j a c q u i n 提出的经典分 形压缩是在空域完成的，它直接利用图像内部象素之间的空间相关性对 图像的灰度信息进行压缩，因而编解码过程在系统结构和实现方法上都 相对比较简单。现今绝大多数分形压缩方法都是由其发展而来的。随着 分形图像压缩技术的不断改进和完善，它在图像压缩中将越来越显示出 优势。 1 3 医学图像编码m 3 6 现代编码技术在医学图像编码中得到了广泛应用，将现代图像编码 理论应用于医学图像中，必须考虑到以下问题：首先，编码系统的效率 和图像的内容有很大关系，不同的医学图像对编码质量的要求，其冗余 信息和有效信息构成各有特点。比如在超声图像和m r 图像中的噪声类 型由于其成像的物理机制不同就完全不一样，在设计其压缩系统时必须 根据其有效信号的频率分布，选择合适的图像分解变换和量化方式，以 保留有效信息。又比如染色体成像中( c h r o m o s o m e i m a g i n g ) ，在医生诊 断之前必须将由原始图像分割出来的染色体按顺序重新排列才能用于医 生的诊断，其中的背景区域对于诊断没有意义的，这样设计其压缩系统 4 第一覃绪论 就可以利用染色体的分割结果，只编码压缩感兴趣区域( r o d 抛弃背 景，提高压缩比。其次，医学图像自身特殊性对压缩技术提出了更高的 要求。医学图像的质量直接关系到医学诊断，图像的小的细节的损失可 能导致错误的诊断( 如骨骼骨小梁的结构、乳房x 线照片上小的钙化点、 肺部气胸的边缘等很容易在常规压缩过程中损失) ，对医学图像进行压缩 必须结合对医学图像的先验知识。因此研究有针对医学图像特点的图像 编码技术显得尤其重要。 医学图像的多样性以及图像压缩系统对内容的敏感性决定了不可 能设计一个普适、完全自动的同时又是高效率的医学图像压缩系统，目 前，对医学图像压缩的研究热点主要集中于对多维医学图像数据的压缩 编码上：同时结合计算机自动分析或人工参与所得的图像分析结果的面 向对象的图像编码也获得了很多研究者关注；也有研究者结合三维显示 和图像数据库检索来设计具备相应特性的图像压缩系统，本文的主要工 作如下。 1 4 本文的研究内容 本文通过研究经典的小波编码器和分形图像编码器，结合医学图像 的特点，创新性的提出了两种适合医学特点的医学图像压缩算法。 研究内容之一是基于小波变换的医学图像编码技术研究。提出了一 种图像编码的新算法：基于小波变换的预测四叉树图像编码。该算法利 用小波系数图像频带内部与频带间相关性，属于带内编码与带间编码的 混合。同时在编码的过程中加入了预测过程。熵编码采用了基于上下文 的算术编码，提出了四种上下文编码模型，在使用时可以灵活设置，适 合对不同特点的医学图像进行编码。 本论文的第二个研究内容是针对传统序列图像分形压缩算法编码时 间过长的问题，提出了一种基于模糊聚类优化的快速算法，它是一种基 于单帧的序列图像帧间分形压缩算法。首先使用l b g 方法对序列图像搜 索空间样本集进行初始化，然后将模糊聚类优化( o p t i m a lf u z z y c l u s t e r i n g ，o f c ) 方法软分类，匹配时用类中搜索取代全局搜索，将分 形编码过程聚焦在最有效的局部范围内，从而减少了匹配次数，降低编 第一军医大学博j 学位论文 码时间。o f c 算法是一种软分类方法，它不但是基于全局最优的聚类方 法，也避免了基于局部最优l b g 算法中的某些误判，而且有效抑制了传 统硬分类方法中类别数需预先指定的人为干扰因素，使恢复图像的质量 能够得到更有效的保证。这对目前出现的各种多维医学图像数据的编解 码具有重要的意义。 1 5 本文的结构安排 论文共分为六章，分别安排如下： 第一章为绪论，主要包括医学图像编码概述、论文主要研究内容和 章节安排。 第二章主要介绍小波变换的基本理论，小波变换的实现、小波分解 的特点。同时对基于小波变换的图像编码算法进行了简单地综述。 第三章主要阐述了分形压缩的数学背景、理论基础和经典分形压缩 算法的编、解码的具体实现，并分析了目前分形图像压缩研究的现状及 优化方向； 第四章介绍了本文的第一个主要工作，基于小波变换的预测四又树 图像编码。通过对比实验表明，该方法的压缩性能较e z w 、s p i h t 、j p e g 、 q t _ l 均有不同程度的提高。 第五章介绍了本文的另外一个主要工作，基于模糊聚类优化的序列 图像快速分形压缩。 第六章为本论文工作的总结和对未来工作展望。 6 2 1 前言 第二章小波图像编码 很少有其他数学概念象小波一样在工程和数学的众多研究领域产 生了如此大的反响和成果。人们早就认识到，把函数分解成一系列简单 基函数的表示，无论是在理论上还是实际应用中都有重要意义。小波最 早的历史可以追溯到1 9 1 0 年a l f r e dh a a r 的文章。1 9 8 6 年，法国数学家 m e y e r 成功地构造出了具有一定衰减性的光滑函数沙，它的二进伸缩与 平移杪卅( f ) = 2 1 ”y ( 2 - jr - 女) ：j ，k z j 构成l 2 伍) 的规范正交基。此前， 人们普遍认为这是不可能的，至此小波分析方法才开始真正得到迅速的 发展。 l e m a r i e 和b a t t l e 继m e y e r 之后也分别独立地给出了具有指数衰减 的小波函数。1 9 8 7 年，m a l l a t 利用多分辨分析的概念，统一了这之前的 各种具体小波的构造，并提出了现今广泛应用的m a l l a t 快速小波分解和 重构算法。1 9 8 8 年d a u b e c h i e s 构造了具有紧支集的正交小波基。c o i f m a n ， m e y e r 等人在1 9 8 9 年引入了小波包的概念。基于样条函数的单正交小波 基由崔锦泰和王建忠在1 9 9 0 年构造出来。1 9 9 2 年a c o h e n i d a u b e c h h i e s 等人构造出了紧支撑双正交小波基。同一时期，有关小波变 换与滤波器组之间的关系也得到了深入研究。小波分析的理论基础基本 建立起来。 对大多数现代研究者来说，小波研究开端于8 0 年代晚期m a l l a t r “1 和d a u b e c h i e s l l o 的两篇经典文章，m a l l a t 确立了成为现代小波分析理论 里程碑的多分辨率分析的概念，而d a u b e c h i e s 构建了第一个正交而且紧 支撑的小波基。这两篇文章的巨大贡献使它们成为有史以来引用最多的 科学文章( 到目前总计超过1 5 0 0 篇s c i 引用) 。 小波变换作为能随频率的变化自动调整分析窗大小的分析工具，在 信号处理、计算机视觉、医学图像处理、语音分析与合成等众多的领域 得到广泛应用。目前小波变换在医学图像处理中的主要应用领域有 ： 第一军医大学博上学位论文 医学图像压缩编码 c t 重建、局部断层成像 小波域去噪( m r i ，u l t r a s o n i ci m a g i n g ) 基于小波的特征提取，纹理和统计描述 医学图像加强( 用于f l u o r o s c o p y 、m a m m o g r a p h y ) 脑功能图像分析( p e t 、f m r i ) 2 2 小波分析 2 2 1 小坡变换及其基本性质【5 。1 0 】 2 2 1 1 连续小波变换 v f ( t ) el 2 俾) ，o ) 的连续小波变换( 有时也称为积分小波变换) 定 义为： w s ( a 纠埘i i ，o h 学卜，n 。 ( 2 ，) 或用内积形式： w t y ( a ，6 ) = ( ，虬，。) ( 2 2 式中坩ii ”攻半) 要使逆变换存在，y 0 ) 要满足允许性条件： 铲肾 幢。， 式中矿) 是y ( f ) 的傅里叶变换。 这时，逆变换为 州“；1 胁。蚂孝 ( 2 4 ) c ，这个常数限制了能作为“基小波( 或母小波) ”的属于r 伍) 的函数y 的类，尤其是若还要求y 是+ 个窗函数，那么y 还必须属于d 伍) ，即 眦枷 o 。 故矿) 是r 中的一个连续函数。由式( 2 3 ) 可得扩在原点必定为零，即 妒( o ) = 妒( f 妞= o ( 2 5 ) 从式( 2 5 ) 可以发现小波函数必然具有振荡性。 2 2 1 2 连续小波变换的离散化 由于连续小波变换存在冗余，且连续形式不便于数值计算，在实际 应用中常对能数n ，b 离散化，常取6 = 2 ，t ，= 2 ，；，七z ，这时 q - a ，。o ) = y ：乜，。0 ) = 2 - j 2 y ( 2 一f k )( 2 6 ) 常简写为：，t p ) 。 变换形式为：w r y ( 2 , 2 。女) = ( ，。) 为了能重构信号，o ) ，要求移肚l 船。是r ) 的r i e s z 基。 定义2 1 一个函数矿l 2 恹) 称为一个r 函数，如果妙肚 。：在下述意义 2 z 是- - + r i s e z 基：y m ， z 的线性张成在l 2 伍) 中是稠密的，并且 存在正常数a 与b ，0 a b o 。，使 镌船瞻玉叫一； g ， 对所有二重双无限平方可和序列 c 似j 成立，即对于 怍肚配= 主艺k 。i 0 ，使得对所有工，y x ，有d ( w ( x ) w ( ) ，) ) q d ( x ，y ) ，则称3 a 7 满足 l i p s c h i t z 条件：特别地如果为q l 则称w 为压缩映射，q 为w 的压缩因 子，d ( ，) 为欧氏距离。若设j x ，使w ( x ) = x ，则称x 为压缩映射w 的 不动点。 定理3 1 ( 不动点原理) ：设( x ，d ) 是完备距离空间，映射w ：x _ x 是压缩映射，则w 在艽中恰好有一个不动点。 不动点原理给出了不动点存在和唯一的充分条件，同时给出了一个 逐步逼近不动点的构造过程一迭代收敛过程：对于给定初始点x ，可通 过构造合适的压缩映射w 经反复迭代后用不动点来逼近它。 定理3 2 ( 拼帖定理，c o l l a g e t h e o r e m ) ：如果x 为压缩映射w 的不 动点，那么它与初始点工之间的距离满足下式： 一 1 d ( x ，蔓d w ( 曲) ，( 其中q 为压缩映射w 的压缩因子) ( 3 1 ) l q 拼帖定理给出了衡量一个集与相应不变集的近似程度的一种方法。 对于分形图像压缩来说，则是给出了迭代过程中容许的误差范围，也就 是说我们应该选取合适的压缩映射w 来降低拼帖误差，它表明如果x 在 第一军医大学博 学位论文 压缩映射w 作用f 的映射点以x ) 与它之l 司的距离越小，那么该压缩映射 的不动点就越靠近x 。 推论3 1 ：在定理3 2 的条件f ，迭代序列对任意的初始点x 都 收敛到w 的唯一不动点x ，并且关于收敛误差有先验的估计式 d ( 吒，；) 兰 d ( x 1 , x 0 ) ( 3 2 ) j q 及一个后验的估计式 d ( ，芽) d ( 矗，1 ) ( 3 _ 3 ) 1 一q 推论3 1 给出了计算拼帖误差的方法，先验估计式可以在计算前按 给定的误差精度要求来计算收敛需要的步数，后验估计式则可用于中问 步骤或计算结果的验证。 但拼帖定理的要求是非常严格的，而在有些情况下，映射w 并不需 要压缩映射，只需满足下面的渐进收敛( e v e n t u a l l yc o n t r a c t i v e ) 条件。 定义3 2 ：设( x ，d ) 为距离空间，映射w ：x - x 满足l i p s c h i t z 条件， 如果存在n z 使得迭代序列w ”是压缩的，则称w 为渐进收敛，n 为渐 进收敛的指数。 因此我们可以得到下面的广义拼帖定理： 定理3 3 ：设仁，d ) 为距离空间，映射w ：x _ x 以指数n 渐进收敛， 那么存在唯一的不动点；x ，使得对于任意的工x ，都有： ；= ，瓜) = l i m w 。( x )( 3 4 ) 并且如果s 为w ”的压缩因子，g 为w 的压缩因子，则 讹璐击鲁m 巾” ( 3 5 ) 值得注意的是定理3 3 与定理3 2 相比，它减弱了对映射w 本身的限 制( 未要求为压缩映射) ，故q 可以大于l ，这对于灵活选取w 很重要， 使我们可以专注于w 的复合迭代序列w ”的渐进收敛问题。 b a r n s l e y 将他发现的一个分形子集定义为i f s ： 定义3 3 ：设( x ，d ) 为完备距离空问，其压缩映射 w i ：x _ x ，i = 1 , 2 ，n 的群集w = u 称为迭代函数系统( i f s ) 。 i = l 通常选取完备距离空间( x ，d ) 的x 为非空紧子集h ( x ) ，即 h a u s d o r f f 空间，距离d 为h a u s d o r f f 距离。显然，如果给定i f s 的压缩映 射群集w = u w j ，那么可由任意初始点，进行迭代w ”( ) 直至收敛 i = l 到唯一不动点z ，并且我们可以得到n 次迭代后的误差估计式： d ( x ，w ”( x o ) ) d ( x ，w ( 曲) + s n d ( x ，x 0 ) ( 3 6 ) l s 分形编码的问题就在于对于给定的集合x ，能否找到一个i f s ，使 得它的不动点；恰好是或尽量逼近x 。由不动点j 的方程： 膏。w ( x ) 5 h ( 曲uw 2 ( x ) t a w n ( x ) ( 3 7 ) 可以看出，不动点是由它映射变换后的群集构成的；由拼帖定理可知通 过寻找合适的压缩映射，努力减小x 与w ( 工) 的误差就能够使得最终的不 动点工与工很好地帖近，因此对于任意初始值，反复迭代后 w ( x o ) ，w ( w ( ) ) ，w ( w ( w ( x o ) 将最终收敛到x ，这就从理论上说明了 分形编码的可行性。 i f s 的困难在于它的每一个映射变换w ；都是作用于整个空间x 上， 但我们并不能保证所有待处理图像都具有分形意义上的那种局部与整体 第一军医大学博上学位论文 之间的相似性，实际应用中要从整个图像进行映射变换来逼近它的局部 是很难成功的，为此j a c q u i n 提出了局部迭代函数系统。 定义3 4 ：设( x ，d ) 为完备距离空涮，如果d ；c x ，i = 1 ，2 ，h ，那么 压缩映射w i ：d ij x ，i = l ，2 n 的群集( c o l l e c t i o n ) w = u 称为局部 迭代函数系统( p i f s ) 。 p i f s 的重要意义在于突破了i f s 的局限，仅用x 的子集而不是全集 来构造，它利用的是图像的某一局部与另一局部的相似性，这种相似性 在大多数图像中都会存在，从而使无需人工干预的分形雎缩成为可能。 3 3 2 仿射变换 f s 中的变换w i 采用仿射变换捌的形式，对于二维信号而言，仿射 变换是线性变换与平移变换的组合，其定义为： 定义3 5 ：二维距离空间r 2 中的仿射变换w 如下所示： 协期柏+ b s ， 其中a , b ，c ，d ，, s x ，y 均是变换系数，矩阵a 为尺度和旋转算子，矢量b 为位移算子。 如果仿射变换满足条件w ( z ) = x ，则有： 并= a x + b y 4 - 缸 y = “+ 毋4 - y 当一1 ) ( d - 1 ) 一b c 0 时，上式的解就称为仿射变换w 的不动点 工：坐：皇= 竺：! 堡二1 2 ( 口一d ( b 1 1 一b c , s x c a y - ( 一1 1 对于二维灰度图像而言，除了图像平面的x ，y 坐标外，还需要增加 表示像素灰度值的第三维。这样上述二维空间的仿射变换要扩展到三维 空间，才能对灰度也进行相应的变换。为简单起见，只考虑第三维与二 维平面坐标采取完全独立的变换形式，这样由x ，y 平面和灰度值z 组成的 定义3 6 ：三维距离空间r 3 中的仿射变换w 如下所示： 制i ； e x l 1 e ：d j 一r l 叫y j 眩。， 其中a , b ，c ，d ，缸，却，s 和d 均是变换系数，矩阵a 为尺度和旋转算子，矢 小结由此可见，如果给定压缩映射w = u 有唯一不动点南，对 于任意图像，o ，反复迭代过程w ( f o ) ，w ( w ( f o ) 将收敛到南。其反过程 则是对给定图像，寻找合适的w ，使得，= f ，这个过程即是分形编 3 4 分形图像编码研究现状睁1 7 】 3 4 1 概述 由于分形图像压缩的研究仍处于发展阶段，其原理和实现过程中还 存在许多值得探索的内容，我们可将其中有待改进和解决的问题归纳为： 1 建立更有效的匹配块搜索空间； 2 对匹配块的更有效搜索方法； 3 寻找应用于匹配块的更简便更精确的仿射变换； 第一军医大学博士学位论文 4 寻找图像值域块的更合理分割方法； 5 耐分形参数的更有效表示和量化方法； 6 充分挖掘利用人眼的视觉特性。 目前对分形编码的各种改进方案均需从上述问题入手，着眼于改善 图像压缩的三大性能：编解码速度、解码图像质量和压缩比，下面分别 简要介绍这三个发展方向的研究现状。 3 4 2 编解码速度问题 编码速度太慢一直是经典分形压缩算法实用化的最大障碍。对于n n 大小的图像，取值域子块大小为r r ，定义域块大小为2 r 2 r 时， 图像共有j n 2 个值域子块和f 掣+ 1 1 。个定义域子块( 由式3 1 0 ) 。经 r 。l j 典分形压缩算法中，一个值域块与一个定义域块进行相似性匹配的计算 量与r 2 成正比，而每一个值域块需要与所有的定义域块进行匹配计算， 因此对每一个值域块来说，其编码计算量与f 掣+ 1 r 2 成线性关 l 幽 系；对幅图像来况，其编码复杂度与 f n - 忑2 一r + 1 1 2 r 2 罢：( n - ，2 r + 1 2 2 成- i f l v , ，一般n 为常数，则 l ，r 2l j 一 分形图像编码的复杂度可记为o ( u 4 ) ，可见分形编码非常耗时，其编解 码过程极不对称，早期时采用3 8 6 机其压缩时间通常要以小时计算m 这 极大地限制了它的实际应用。因此一直以来，分形图像编码研究的核心 内容之一是提高编码速度。 分形编码过程中最耗时的是全局搜索最佳匹配的定义域块，要提高 编码速度，就必须缩小搜索范围，且保证最佳匹配落在该范围之内。故 多数学者的研究集中在问题1 即如何建立更有效的匹配块搜索空间上。 目前的改进方法主要有： 1 分类法：许多改进算法的提出是通过类内搜索或预测来改变搜索 空间的大小或形状以大幅度提高其压缩性能。如在分形编码的预处理过 筇三章分形图像编码 程中将待匹配的值域块根据其几何或统计特征预先分为c 类，匹配时仅 在与其同类的定义域块范围内进行搜索，这时全局搜索变为类内搜索， 匹配次数和编码时间均可减少为原来的1 ( 2 。因此通过结合简便有效的 块分类方法改善分形图像压缩是切实可行的。目前曾经在分形压缩中实 验过的分类方法主要有基于图像块统计或几何特征的分类，如灰度、均 值、方差、力矩等8 ；基于变换域系数( 如d c t 域“、小波域 i 1 1 ) 的 分类；基于分形维数【1 2 1 的分类：其他还有基于明暗度的定向分类、基于 相对矩的分类、基于h v s 的分类、自适应码本簇化的分类、向量量化的 分类等，它们分别从不同的角度、使用不同的工具对图像块分类，对分 形编码有不同程度的加速作用。 2 针对问题2 ，可通过对匹配块的更有效搜索来优化编码速度，其中 最简便有效的是局部搜索法。d m m o n r o 等提出一种不用搜索的编码方 法，对值域子块r ，选择在其附近的一个较大子块作为定义域子块，从 而大大减小了搜索范围，使编解码几乎可以对称；房育栋等人充分考虑 到区域的相关性，在搜索最佳匹配块时，先在r 子块最近的邻域内寻找， 若找不到再扩大搜索范围直至满足预定误差，从而有效缩短了编码时间 ”3 ；d s a u p e 采用多维最近邻搜索方法代替经典分形编码中的匹配过程， 使算法复杂度降为o ( 2l o g n ) ：c k l e e 和w k l e e 通过对匹配块之间 关系的研究发现，如果两子块的自身方差相差太远，则它们不可能相似， 从而排除了许多不必要的匹配过程，可提高编码速度l o 倍以上。 3 针对问题3 ，可寻求更优化的仿射变换。b e w o h l b e r g 等人以几何 的观点看待编码过程中的最小化问题，将复杂的匹配计算变为角度大小 的比较，大大提高了编码速度；他们还提出了一种基于d c t 变换的快速 匹配方法，将d c t 域的子块表示成规范形式使其具有尺度、偏移量及对 折等操作不变性，然后利用多维最近邻搜索方法进行匹配，提高编码速 度。b e h n a m b a n i r = q b a l 等人利用分形内积空间的概念，将经典分形编码 中求m s e 的操作变为正交投影，再构造树状结构进行搜索，可使编码速 度提高5 0 倍以上。t k t r u o n g 等人则通过d c t 频率域上几何变换的简 化与合并减小匹配过程中的计算量，提高编码速度。 茹一军医人学博士学位论文 由于分形解码过程没有耗时的搜索操作，解码速度相对于编码要快 得多，基本上能够满足实际需要，因此对解码快速算法的研究较少。然 而对于一些实际应用来说，仍然希望迭代次数越少越好，以进一步加快 解码速度，常用的加速方法有会字塔式解码器、去均值解码算法等。 3 4 3 分形编码的图像质量 目前提高分形编码质量的方法主要有： 1 针对问题l ，寻找更合理的值域块分割方法。经典分形压缩的固定 大小方块分割会受到灰度线性逼近的限制，采用较大块时虽然可以得到 较高的压缩比，但图像质量较差；而较小块时灰度的逼近效果好，但压 缩比偏低；另外，方块分割在形状上也不利于倾斜边界的编码，因此便 有了下述分割方案的改进： j a c q u i n 首先意识到了这一点，他采用了四叉树二次分割：首先对 8 8 大小的值域子块进行编码，然后判断此逼近误差，如果超过预定门 限，则对此块进行四叉树分割后再进行编码。该方法在定程度上具有 自适应性，在提高编码质量和速度的同时可避免压缩比下降太多； y f i s h e r 等人对上述方法继续推广，将分割按多层进行，使图像 质量和压缩速度有了更进一步的提高，是目前较为实用的压缩方法 t 8 ： y f i s h e r 还提出了一种三角形分割方案，在方块分割的基础上， 沿两条对角线将其分成两个三角形，从而较好实现了对倾斜边缘的逼近； e d a v o i n e 等人还提出了一种d e l a u n a y 三角形分割方案，同f i s h e r 的方 法相比，其特点在于三角形的方向和大小是任意性的，更增加了灰度逼 近时的灵活性； y f i s h e r 等人还提出了一种h v 分割方案，沿水平或垂直边缘将 一个长方形的值域子块分割成两个小块，以减小值域块的复杂度，提高 细节逼近能力； e d a v o i n e 等人提出了基于三角形和四边形的混合分割方案，三角 形分割的优点是去除方块效应，相邻三角块组合成四边形后可有效减少 编码块数，提高压缩比； 另外还有学者对基于六边形分割法、基于边界分割法、基于菱形分 割法、基于多边形分割法以及不规则区域分割和交叠块分割进行了研究， 第三章分彤图像编码 它们各有优势，但在搜索、存储、相似性提取等方面仍存在着一些问题， 需进一步研究。 2 针对问题3 ，寻找更精确的仿射变换，改进灰度逼近能力： 赵耀等人将经典分形编码中简单的线性灰度逼近一般化，提出了 一种新的仿射变换，使灰度逼近可以为二次以上多项式，有效提高了编 码图像质量； m g h a r a v i 等人通过用几个定义域子块的线性组合来逼近某一值 域子块来提高逼近能力； 3 考虑到分形压缩方法在低压缩比( 即值域块较大) 时，图像缅节 部分匹配效果不佳；而一些传统编码方法在较低压缩比时效果较好，因 此另一个优化思路就是将分形与这些传统编码方法有机结合，互相弥补， 常用的混合方案有与小波变换结合编码、与d c t 变换结合编码等。 4 提高显示效果的后处理法：对值域块的独立编码不能保证块与块 之间的连接是最光滑的，常导致块效应出现，人眼对此比较敏感，一般 采用加权平均法【l ”。 5 有研究者提出了一种基于人眼视觉模型的分形压缩理论和算法： 针对分形编码未能充分利用h v s 特性的缺陷，以“视觉最相似”准则来进 行图像子块的匹配，并推导出图像块的视觉相似匹配在d c t 域的形式， 使解码图像的视觉质量得到明显改善。此外，他们还根据i - i v s 特性，将 注意力集中机制与多分辨率分析相结合，提出了一种适于医学图像编码 的非均匀多分辨率分析的理论n m r a ( n o n u n i f o r mm u l t i r e s o l u t i o n a n a l y s i s ) ，导出了基于小波的n m r a 的理论框架：n m r a 由尺度函数 庐( z ) 和扭曲函数r ( 工) 唯一决定；在n m r a 下，信号可以由小波基 2 。沙( r - 1 ( 2 ，r ( x ) 一，1 ) ) 正交表示。经典的m a l l a t 多分辨率分析可以认为是 n m r a 的特例。在n m r a 中，固定尺度下的分辨率非均匀，随点的位 置变化而变化：不同尺度下，对应点处的分辨率按2 的指数倍数递增。 n m r a 应用于医学图像的编码，在保持感兴趣细节的同时有效地抑制了 背景信息，取得了较好的压缩效果。 第一军医大学博i ：学位论文 3 4 4 分形编码的压缩效率 压缩比的提高主要依赖于选择更有效的参数量化方法和熵编码算 法。此外，有学者提出快速覆盖式分形压缩方法和四叉树重组q r 算法， 它们可通过合并值域块来提高压缩比。 我们的研究目的侧重于对分形编码算法的改进，因