（信号与信息处理专业论文）基于分形的混合图象压缩编码方法的研究.pdf

摘要 分形编码是在分形几何的迭代函数系统理论基础上发展起来 的一种崭新的编码技术。它以其思路新颖、压缩比高等特点迅速 吸引了大批编码工作者的注意。随着9 0 年代j a c q u i n 的自动分形 编码方案的提出，分形编码进入了一个高潮时期，使之与小波变 换编码一道成为新的编码方向的热点。 本论文以分形图象编码理论为研究对象，从整体上对分形编 码予以论述说明，在实现经典的分形编码算法的同时，分析了分形 编码算法的优点和缺陷。 本文以加快分形编码速度、提高编码效果为主要目的。通过 将分形编码方法与d c t 、小波变换相结合，提出了两种混合编码 方案，取得了较好的效果。 、 本论文主要做了以下的工作： 一) 实现了经典的分形编码算法，详细分析了分形编码算 法，指出了它的优点和缺陷。 ( 2 ) 阅读了大量对经典分形编码算法进行改进的文献，认真 研究了其中有代表性的编码方法，提出了自己的见解。 ( 3 ) 分析了国内外各种分形与d c t 结合的混合编码方法， 提出了一种基于局部搜索技术的分形- - d c t 混合编码方 案。得到的结果为：在峰值信噪比为2 9 5 2 d b 时，压缩比 为2 0 1 0 ：1 ，编码时间为1 5 秒。 ( 4 ) 分析了小波变换的分形特性，介绍了国内外比较有影响 的小波变换与分形编码相结合的混合编码方法，提出了 一种基于小波分析的分形一小波混合编码方法。得到的l 结果为：在峰值信噪比为3 i 1 2 d b 时，压缩比为3 6 2 9 ：l 。卜、 。 a b s t r a c t f r a c t a li m a g ee n c o d i n gb a s e do ni t e r a t e df u n c t i o ns y s t e mo f f r a c t a lg e o m e t r y ，i san e o t e r i ct e c h n i q u eo f e n c o d i n g d u i n gt oi t s c r e a t i v ei d e aa n df a b u l o u sc o m p r e s s i o nr a t e ，i ti sa t t r a c t i n gg r o u p so f c o d i n g r e s e a r c hs t a f t f r a c t a le n c o d i n gh i t si t st i d e m a r k , a l o n gw i m t h es c h e m eo ff r a c t a lb y j a c q u i na u t o e n c o d i n gi n9 0 s t h es i t u a t i o n m a k e sf r a c t a lc o m p r e s s i o na n dw a v e l e tt r a n s f o r l t l a t i o na sh o t - p o i n t o f n e o t e r i ce n c o d i n g t e c h n i q u e o b v i o u s l yf r a c t a li m a g ec o d i n gi s ap r o m i s i n gn e w t e c h n o l o g yf o r i m a g ec o d i n g u n f o r t u n a t e l y , t h el a r g ea m o u n t o f c o m p u t a t i o n n e e d e d f o rc o m p r e s s i o ns t a g ei sam a j o ro b s t a c l et h a tn e e d st ob eo v e r c o m e i nt h i s d i s s e r t a t i o n ，w e i n t r o d u c e dt w o h y b r i di m a g ec o d i n g a p p r o a c h e s b a s e do nf r a c t a lt o b r e a k i n gt h e “s p e e dp r o b l e m ”a n d a c h i e v e dg o o dc o d i n ge f f e c t t h em a i ni o b si n v o v l e di nt h ed i s s e r t a t i o na r e ： f1 1r e a l i z e d t h ec l a s s i c a lf r a c t a l i m a g ec o d i n ga l g o r i t h m p r o p o s e db yj a c q u i n ei n19 8 9a n dg i v e nam m l y s i so f t h es c h e m e f 2 1i n t r o d u c e dt h ec u r r e n tt e c h n i q u e su s e di n 行a c t a ii m a g e c o m p r e s s i o nf i e l di n c l u d i n gs t i l li m a g ea n dv i d e o i n v e s t i g a t e dt h e a d v a n t a g e s a n d d i s a d v a n t a g e s o f e a c h t e c h n i q u e a n dg i v e a n e x t e n s i v e s1 i s to fr e l e v a n tr e f e f e n c e s f 3 1 p r o p o s e dah y b r i di m a g ec o d i n ga p p r o a c hb a s e do nf r a c t a lt o b r e a k i n gt h e “s p e e dp r o b l e m ”a tf i r s t w eu t i l i z eal o c a ls e a r c hf r a c t a l c o d i n gm e t h o dt oe n c o d et h eg i v e ni m a g e t h e n ，w eg i v et h er o l eo f c a p t u r i n gt h em i s s i n gd e t a i l e df e a t u r e st oad c tc o d e r e x p e r i m e n t a i r e s u l t ss h o wt h a tc o m p a r e dt ob a s i ca u t o m a t i cf r a c t a li m a g ec o d i n g m e t h o d ，t h i sn e wa p p r o a c hi sf a s t e rw i t hh i g l lc o m p r e s s i o nr a t i o sa n d g o o d r e c o n s t r u c t e di m a g e q u a l i t y ( 4 ) p r e s e n t e dah y b r i di m a g ec o d i n gs c h e m ec o m b i n i n gf r a c t a l a n dw a v e l e tt r a n s f o r m a t i o n t h ei m a g ew a sd e c o m p o s e db yd i s c r e t e w a v e l e tt r a n s f o r m ，t h et r a n s f o r ms u b i m a g ew a se n c o d e db yf r a c t a l b l o c k p r e d i c t i o n w h i c he x p l o i t e dt h e s i m i l a r i t yb e t w e e nl o w e ra n d h i g h e rr e s o l u t i o ns u b i m a g e e x p e r i m e n t a lr e s u l t ss h o wt h a tc o m p a r e d t ob a s i ca u t o m a t i cf f a c t a li m a g e c o d i n gm e t h o d ，t h i sn e wa p p r o a c hh a s h i g hc o m p r e s s i o nr a t i o sa n dg o o dr e c o n s t r u c t e di m a g eq u a l i t y 致谢 3 1 3 5 0 9 在本论文的工作过程中，我要深深感谢我的导师裘正定教 授，从开始选题到最后完成论文阶段，裘老师给予了我大量的指 导。裘老师儒雅谦和的学者风度、博大精深的学术功底、严谨求 实的治学态度以及深刻敏锐的洞察力使我获益非浅，足我学习的 榜样。在此，请允许我再次对裘老师致以深深的谢意。 还要特别感谢丁晓明老师，在我硕士生期间，丁老师给了我 大量指导和帮助。在此向他表示诚挚的谢意。 另外，还要感酣马波博士，当我在论文完成过程巾，他给了 我热忱的帮助，使我少走了不少弯路。在此向他表示感谢。 我还要感谢赵耀博士，王钦老师，唐丕强老师，马金明硕士， 汪礼勇硕士，姜海东硕士，齐飞硕士，张强硕士，王黎炜硕士， 万挺硕士，金京华硕士。在我完成课题期间，他们给了我大量的 帮助。 最后，我要特别感谢我的家人。是他们含辛茹苦的培养我长 人，一直令力以赴的支持我、鼓励我。我的每一点进步，都是与 他1 f 1 分个丌的。我已无法用语苦来表达列他们最真挚的感激之 一情。 1 引言： 第一章前言 第一节图象压缩编码的意义 视觉通信通常被认为是继传统语音通信之后的新一代通信工 具。因而图像是人类最主要的一种信息载体。在目前的数据量中图 象数据占有很大比例，而数字化图像产生的数据量极其巨大，这导 致了在实际应用中传输、存储的困难，于是人们开始寻找将图像数 据进行压缩的方法，以减少图像数据量，但又要使有用的信息得以 保存。 图象编码器在技术上和经济上曾一度被认为是不可行的。然 而，随着微电子和编码技术的发展，对于大量的应用场合，图象压 缩编码已成为现实。为了实现这一目标，全世界数以万计的科学工 作者经过四、五十年的努力，提出了数十种编码方案：并于近几年， 公布了儿种图象编码标准，如：用于静止图象的j p e g 标准，用于 电视会议和可视电话的h 2 6 1 、h 2 6 3 标准，以及用于介质存储的 m p e g t 、m p e g i i 、m p e g - 1 v 标准等。 本章首先对图象编码的必要性和基本原理作些介绍；然后对目 前常用的一些编码方法作些分类、比较和回顾；最后介绍了论文安 排。 2 数字图象的应用和图象压缩的必要性： 数字图象目前主要应用于以下场合 ( 1 ) 高清晰度电视( h d t v ) ( 2 ) 可视电话 ( 3 ) 多媒体会议通信系统 ( 4 ) 交互式电视( v c t v ) ( 5 ) c d 电影 ( 6 ) 大量存储的应用： 采用数字技术( 或系统) 具有许多优越性，但也使数据量大增。 尽管随着光纤网和光盘等宽带信道和大容量存储介质的采用，信道 带宽和存储量变得越来越大，但数据量的增加远远快于带宽和存储 量的增长，显然需要对数据进行高效的压缩。 数据压缩的好处在于： ( 1 ) 较快的传输各种信息( 降低信道占用费用) 一时间域的 压缩； ( 2 ) 在现有的通信线路上开通更多的并行业务( 如电视、传 真、电话、电报、可视图文等) 一频率域的压缩； ( 3 ) 降低发射机的功率一能量域的压缩： ( 4 ) 紧缩数据存储容量( 降低存储费用) 一空间域的压缩。 3 压缩编码的基本原理和分类 数据在某种程度上是有很大的冗余。比如一幅图像中表面颜色 或灰度均匀的块，它具有空间的冗余，再如序列图像前后相邻图像 相关性，它具有时间冗余。除了时间冗余和空间冗余外，还存在其 他冗余，如：信息熵冗余( 即编码冗余) 、结构冗余( 如纹理结构 上的冗余) 、知识冗余( 先验知识) 、视觉冗余( 如人眼的分辨力 只能分辨2 6 个灰度等级) 等等，如果能够将这些冗余予以去除，那 么数据就可进行压缩。 一般来说，数据压缩分成可逆压缩和不可逆压缩两种，前者的 解码后数据与原始数据严格相同，即压缩是完全可恢复的。如哈夫 曼编码、算数编码、游程编码等。但是这种方法压缩比不高，一般 其压缩比介于1 _ 7 2 1 之间，故而在图像压缩中只能起辅助作 用。不可逆压缩其解码数据与原始数据存在一定的误差，但却有很 高的压缩比，目前图像压缩中常用这种方式。 如果按照信息提取的模型分类，图象编码有可分成以下两类： ( 1 ) 波形基编码( w a v e f o r m - - - b a s e d c o d i n g ) ：这种编码方法 将图象看作2 d 信号波形，从中提取固定的、统计的特性，大部分 图象编码技术，象变换编码、子带编码、失量量化编码、小波变换 编码以及分形编码等，都可归于此类。 ( 2 ) 模型基编码( m o d e l - - b a s e dc o d i n g ) ：这种编码方法将 图象看作3 d 真实场景在2 d 的投影。在编码端，首先将3 d 场景建 模，提取参数；在解码端，通过使用抽取和量化的参数来拟合原始 图象。语义基图象编码和物体基图象编码是这一类的两个典型例 子。 第二节图象压缩编码方法简介 1经典图象编码方法： 1 1 预测编码( p r e d i c t i v ec o d i n g ) ： 预测编码的目的是使预测值尽可能接近要发送的样值，也就是 寻找一种尽可能接近原信号统计特性的预测方法。而相减去除了图 象信号的相关性，从而达到数据压缩的目的。预测编码分为线性预 测编码和非预测编码两类，可以在一幅图象内进行帧内预测编码， 也可以在多幅图象间进行帧间预测编码。线性预测编码常称为差分 脉冲编码调制，即d p c m 。 1 2 变换编码： 一般来说，在变换域里描述要比在空间域里简单，而且图象的 相关性明显下降。尽管变换本身并不能导致数据压缩，但由于变换 图象的能量大部分集中在少数几个变换系数上，采用量化和熵编码 就可以有效的压缩图象的编码比特率。图象交换编码还可以利用人 的视觉特性，如人眼的分辨率、空间概率特性和视觉心理等，去除 影响较小的数据。变换编码的另一个特点是抗信道误码能力强。 变换编码主要由映射变换、量化及编码几部分组成，其中映射 变换是把原始信号中的各个样值从一个域变换到另一个域，然后针 对变换后的数据再进行量化和编码操作。在接收端，首先对收到的 信号进行译码，然后再进行反变换以恢复原来的信号( 在定的保 真度下) 。映射变换关键在于能够产生一系列更加有效的系数，对 这些进行编码所需的总比特数，要比对原始数据进行编码所需的总 比特数少得多，从而使得数据得以压缩。 映射变换的方法很多，般是指函数变换法，而常用的是正交 变换法。比如我们熟知的傅立叶变换，就是利用复数域正交变换将 一个函数从时域描写变到频域描写，使函数某些特性变得明显，从 而简化处理。 k l t 是最理想的变换方法，它具有均方误差意义下的最佳性 能。但就其实现的成本和实时性来讲，k l t 被认为是最困难的一种 变换。显然，它的理论价值大于它的实际价值。目前，最常用的变 换方法是离散余弦变换( d c t ) 。d c t 是次最佳变换，其变换性能 接近k l t 。d c t 具有快速算法，在实现编码和滤波时，有很好的信 息压缩效果。由于v l s i 的发展，结构有规律或易于并行的一些d c t 算法已能用专用的i c 实现，这就更牢固地确立了d c t 在目前图象 编码中的重要地位，成为h 2 6 l 、j p e g 、m p e g 等国际标准的主要算 法。其它变换方法还有：正弦变换( d s t ) 、沃尔氏一哈达马变换 ( w h t ) 、哈尔变换( h a a r ) 、斜变换( s l a n t ) 等。 1 3 子带编码( s u b b a n dc o d i n g ，简写为s b c ) ： 子带编码就是利用带通滤波器( b p f ) 组把信号频带分割成若 干个子频带( 简称子带) ，通过等效于单边带调幅的调制过程，将 各子带搬移到零频率附近以得到低通表示，再以奈奎斯特速率对各 子带抽取样值，并对取样值进行通常的数字编码。在解码端，将各 子带信号解码并重新调制回其初始频带位置，再将所有子带输出相 加就可以得到近似于原始信号的恢复波形。显然，子带编码属于波 形编码。 1 4 矢量量化编码( v e c t o rq u a n t i z a t i o nc o d i n g ，简称 v q ) ： 矢量量化是将k 个( k z ) 样值形成一个k 维空间r k 中的 一个矢量，然后对此矢量一次进行量化，只传输或存储矢量的地 址，因此能大大地降低数码率，矢量量化总是优于标量量化，这是 因为矢量量化有效地利用了矢量中各分量间的四种相关性( 线性依 赖性、非线性依赖性、概率密度函数的形状和矢量维数) 来去除冗 余度。矢量量化是标量量化的多维扩展。 矢量量化的另一个特点是译码器非常简单，只需作简单查表 运算。其简单的工作过程是：在编码端输入矢量x 与码书( y ) 中 的每一个或部分码字进行比较，分别计算出它们的失真，搜索到失 真最小的码字y i 的序呈j ( 或此码字所在码书中的地址) 将j 的编 码信号通过信道传送到译码端；在译码端先将信道传过来的编码信 号译成序号i ，再根据序呈i ( 或y i 所在的地址) 以码书( y ) 中 查出相应的码字y i 由于码书i 和码书i i 是完全一样的，故此时失真d ( x ，v ) 最小， 所以y i 就是输入矢量x 的恢复矢量。很明显，由于在信道中传输 的并不是矢量y i 本身，而是其序号i 的编码信号，设码书的大小 为n ，则传输序号所需的比特数为l o g a n ，传输一个像素所需的平 均比特数为( 1 k ) l 0 9 2 n 。 1 5 小波变换编码( w a v e l e t t r a n s f o r mc o d i n g ) ： 由法国科学家m o r l e t 于1 9 8 0 年提出，其他一些学者共同发展 的小波编码，具有十分优异的性能。其核心就是利用小波滤波器组 来分解图象信号。这种小波滤波器组具有高频时空域较短而低频时 空域较长的特性。小波滤波器组的这种特性与视觉信息的一些特性 相匹配：高频分量通常发生在较短的空间域中，而低频分量通常发 生在较长的空间域中 2 现代图象编码方法： j 9 8 8 年以来有较多发展的各种现代图象编码方法的显著特点 是：它们突破了经典图象编码方法所依据的信源编码理论的框架 ( 例如，假设图象是平稳的随机场) 。在同样压缩比条件下，现代 方法比经典方法处理后的重建图象在主观质量方面有显著的改 进：或者是，在重建图象的主观质量大致相当的条件下，现代方法 的压缩比是经典方法的几倍至几十倍。 2 1 模型法： 实际上，模型法的编码解码过程就是对图象的分析综合的过 程。模型法编码时，在发送端，用线框模型对图象进行分析，获得 各结点的参数值。接收断由线框模型和各结点的参数值，综合而得 出重建图象。 模型法可分为两类：有先验知识的和无先验知识的。 2 2 神经网络用于图象编码： 人们的视觉系统具有极为复杂的高级神经活动的功能。神经网 络的研究就是试图模仿人们视觉系统某些局部的初级功能，经过几 十年的努力，神经网络研究先后提出了神经元模型，h o p f i e l d 模 型，具有反向传播的多层网络模型( b e 模型) ，这些研究成果应用 于图象编码领域，已经取得了一些进展，但还不如其它应用方面收 效，还有待于广大研究人员的进一步努力。 2 3 分形用于图象编码 以上介绍的编码方法各有其优缺点，但是在压缩问题上并没有 一利，突破( 除小波变换编码外) 。它们仅借助于象素间灰度渐变等 假设进行压缩，而忽视了图像中的相关不仅仅是象素之间的，而区 域与整体，或区域与相距较远的区域之间也存在着很大的相关性。 为了描述图象的这种特性，人们将分形引入了图象编码领域，取得 了很好的效果。 分形图象编码这一概念是由乔治亚州工学院的数学家 m f b a r n s l e y 于1 9 8 7 年提出的。之后，在1 9 8 8 年，m f b a r n s l e y 和a d s i o a n 发表了一篇题为“a b e t t e r w a y t o c o m p r e s s i m a g e s ”的文章。在此文中，他们首次将i f s 理论应用于图象压缩 编码中，并获得了较好的压缩效果，压缩比高达1 0 ，0 0 0 ：1 。以此 编码方法为基础，二人申请了美国的专利。这种压缩方法突破了以 往熵编码的理论界限，新颖、高效，引起了编码研究者的高度关注。 但是这种方法的最大缺点是需要人机交互实现，对操作者有较高的 要求，无法广泛应用。 l 9 9 0 年，m f b a r n s l e y 的学生a e j a c q u i n 首次提出了一种 基于子块的全自动分形压缩方案，为分形图象压缩编码的研究带来 了一次质的飞跃。在这是以后，各国的研究者们纷纷效仿 a e j a c q u i n 的压缩方案，提出了各种各样的改进方案，从而掀起 了分形图象编码研究的高潮。 第三节主要研究工作和论文安排 本论文以分形图象编码理论为研究对象，从整体上对分形编码 予以论述说明，在实现经典的分形编码算法的同时，分析了分形编 码算法的优点和缺陷。通过将分形编码方法与d c t 、小波变换相 结合，提出了两种混合编码方案，取得了较好的效果。 本论文安排如下： 在第二章中首先介绍了分形的基本原理，然后实现了经典的分 形编码算法。 在第三章中首先分析了分形编码算法，指出了它的优点和缺 陷。然后研究了大量对经典分形编码算法进行改进的文献，认真分 析了其中有代表性的编码方法，提出了自己的见解。最后在分析了 国内外各种分形与d c t 结合的混合编码方法的基础上，提 出了一种基于局部搜索技术的分形- - d c t 混合编码方案。 在第四章中首先分析了小波变换的分形特性，然后介绍了国 内外比较有影响的小波变换与分形编码相结合的混合编码方法最 后提出了一种基于小波分析的分形一小波混合编码方法。 第二章经典的分形图象编码方法 第一节分形的基本概念 1 分形的定义： 分形( f r a c t a l ) 这个词，是曼德布罗特f b b m a n d e l b r o t ) 仓i 造出来 的，其原意具有不规则、支离破碎等意义。m a n d e lb r o t 提出这一 概念是为了描述大自然中许多极其复杂的形状，如山、云、闪电、 雪花、羽毛等。这些形状不再具有我们所熟知的数学巾连续，光滑 的性质，而有其特殊的些特性。 分形儿何建立以后，很快就引起了许多学科的关注，这是山于 它不仅在理论上，而目在应用上都具有鼋要价值。与传统的儿何学 相比，分形几何有这样的特点： ( 1 ) 从整体上行，分形几何图形是处处不规则的。 ( 2 ) 在不同尺度上，图形的规则性又是相同的。 f j 河列分形还没有严格的数学定义，只能给出描述性的定义。 粗略地说，分形是对没有特征| 殳度但具有定意义下的自, f p i f 以图形 和结构的总称。在某种意义上，它就象我们所说的“生命”一样， 无法明确定义，而只能列举出一系列具有生命的特性，同样，分形 也无法明确定义，而只能用一系列特i i e 去描述。 ( 1 ) 具有无限细致的结构，即具有任意小尺度下的比例细节。 ( 2 ) 分形集不能用传统的数学语言描述。它即不是满足某些条 件的点的轨迹，也不是某些简单方程的解集。 ( ：”具有比例自相似性( 包括精确，近似，统计自相似) ( 1 ) 分形维数大于它的拓扑维数 ( 5 ) 可用简单的算法予以描述，即可用简单的变换迭代产生。 这样，我们要想知道一个形状是甭是分形，那么只需看它是否 具柯上丽的几条性质。对于各种不同的分形，有的可能同时具有f ： 述的全部性质，也可能只具有t 述的大部分性质。 2 分形维数： 人4 f j 用分维数束刻画分形集的复杂性，正如用整数维数来刻画欧 氏几何中的对象一样。分形维数可以通过实验的手段得到定量的估 计，同时出于其取值大小与人眼感觉到的“光滑”与“粗糙”，“简 单”与“复杂”的程度有很强的关系，非常适合作为图象的种特 征) f j | l 以利用。 在分形理论及其应用中，给定一个分形后，其h a u s d o r f f 维数 的计算是比较复杂的：在一般情况下，分形的h a u s d o r f f 维数的下 界也难以得到，这一弱点限制了它在实际问题中的应用。在实际 巾，通常采用计盒的方法( 盒维数1 来确定几何对象的维数。分形维 数之问有的还可以相_ ：转换，例如，h a u s d o r f f 维数d i i 是等概率情 沙f f ，j 信息维数d 【。 3 迭代函数系统： 几何对象的全貌与局部，在仿射变换的意义下，具有自相似结 构。b a m s l e y 将其系统化和公式化，正式命名为迭代函数系统 i f s 。从而可以解析地构造分形，在欧氏几何学和分形几何学之间 找到了联系纽带。i f s 目前已成为研究分形最成功、最普及的数学 模型，在计算机图形学、生命科学、图象压缩编码等许多领域取得 了巨大成功。 i f sj f 理论包括以f 几方而的内容：( 1 1 i f s 码获取过程巾的拼 贴枷_ ! u 。( 2 ) 由i f s 码显示y l g x , j 象的计算机算法，其中包括随机 迭代算法 i j 确定性算法。 对于分形图形来说，其局部是整体的个小复制品，局部可以 看作是原图的一个仿射变换图形。但并不是任意仿射变换都可以用 j ：迭代函数系统，它必须是收缩的。它的收缩性决定了迭代函数的 保形。r e ，使迭代函数系统最终是收敛的。 4 分形几何的应用： 自b b ，m a n d e l b r o t 创立分形几何学以来，这一新的数学分支 就日益受到各国学者的重视。在过去的几十年里，分形几何有了很 大的发展，成为一个研究和处理自然与工程中不规则图形的强有力 的理论工具，它的应用几乎涉及到自然科学的各个领域，如：数学、 物理学、分子科学、材料科学、地质科学、计算机图形学及信息科 学等，甚至应用于社会科学，并且它实际上正起着把现代科学各个 领域联结起来的作用。人们把分形几何和耗散结构及混沌理论共称 为七十年代中期科学上的三大重要发现。 近几年来，人们又将分形几何引入到图象编码之中，出现了分 形图象压缩编码这一新的编码分支。分形图象压缩编码是将图象看 作分形图形，然后利用分形的重要特性自相似形去除图象的冗 余度，从而达到压缩的目的。经过各国科研工作者的大量工作，分 形图象编码已取得了很大的发展 第二节经典的分形图象编码算法 1 引言： 出曼德布罗特( b b m a n d e l b r o t ) 提出的分形几何学，圆满地对 自然界的分形现象进行了研究。这种现象一般具有标度不变性的 自相似结构。图象是自然界的反映因此图象中也存在着许多分 形特征。分形图象压缩的目的就是用分形变换来寻找这些特征， 并h j 简洁的形式来表示这些特征，进而达到压缩图象的日的。 j a c q u i n 等提出的变换方法，为“自动”实现图象压缩开辟了先河。 2 b a r n s l e y 的编码方法： b a r n s l e y 的基于迭代函数系统的分形图象编码与重构包括下 列步骤： ( 1 ) 将原图( 集合x 获图象1 ) 予以分割( 或予分解) 为若干分形子网 x ，m = 1 ，m ； ( 2 ) 对每一个子图x ( 1 提取i f s 代码 ( 3 ) x qi f s 代码进行编码 ( 4 ) 传输或存储； ( 5 ) 译码形成i f s 代码； ( 6 ) k hi f s 代码构造x 的重构图y 旧 ( 7 ) i l iy w l ) 构造x 的熏构图y 。 将原图x 分解为若干子图x 【m ) ，m = l ，2 ，m ，x “可以是x 的空间 域分割，也可以是频率域或其他干日空阔的分解。目前尚未找到种 统的有效机制来实现这种分形子图分割份解。 就一l ：述的编码算法而氘人机交互方式占有重要地位，分形压缩编 f f q 的高爪绵比以其编码过程的费时费力为l e 价，难以实现实时自动 压缩，特别是在编码端。b a r n s l e y 的方法很大程度上依赖于人为的 _ | 泶作，1 9 8 9 年，1 a c q u i n 对其进行改进，提出了种基于p i i ? s 理 论f ：的全自动分形图像压缩编码方法，使得利用计算机实现自动压 缩成为可能。j a c q u i n 算法后来成为火多数分形编码方法的基础。 2 j a c q u i n 的编码方法 一幅扶度陶像常可表示成f ( x ，y ) ，它的仿射变换写作 其。i - z = f c x 、y ) ： s 。表示狄度变换的列比度，0 表示变换的亮度，可将上面仍 射变换分成两部： 僻 獭+ 阴 其巾v i ( x ，y ) 表不空间变换，v i ( z ) 表不灰度变换 为了满足p i f s 理论，上述的仿射变换应当是收缩映射，由于 j 。：。j 可分解成旋转、伸缩、扭曲、反转等几个部分 l c 一“一j 刚 “c ： = i 。o i n s 臼0 - - 。g 。i r 曰t 口 ，：口“ ： 这样v i ( x ，y ) 可以有八种变换方式和几何变换。 山于变换是收缩的，所以变换的收缩因子进行几何变换，而八 利，旋转翻转变换分别是： ( 1 ) 不变； ( 2 ) 从过中心的垂直轴反射投影( 翻转) ： ( 3 ) 从过中心的水平轴翻转； ( 4 ) 从第一对角线为轴翻： 1，l e ，0 _。，l + ，r_i_，_ x y z ri。ii。ii。忆 o o i 以4 o q q o p：。，l = 工 y z ，l ( 5 ) 从第二对角线为轴翻转； ( 6 ) 以中心点为轴心旋转9 0 。 ( 7 ) 以中心点为轴心旋转1 8 0 。 ( 8 ) 以中心点为轴旋转9 0 。 v i 。( z ) 则对应- t - x qk p , 度尺度变换，亮度变换。 设u i 和v 分别为变换后的定义域块和原始值域块的像素值( 为 简币起见，以一维f 标表示) 。 则x , i 比度尺度因予s 定义为： s = ”( 喜“v ， 一( 喜z 。 ( 墨；v ， l ”( 喜“? ) 一 萋；“， 2 若 。f 芝。? ) _ f 窆q ) ：o 则令s = 0 而亮度因子0 则定义为： r 舀o 、 。2 l 乞1 j 一，乞“， ” 、忙忙f 7 仿射变换的这些变换主要h 1 其系数决定在实际应用t i t ，直接 获取，量化和存储这些系数较为困难，因此常用一个等价的组合变 换束代替w i ： 形= 谚y ，纯 其r 】，( p 、是x y 平面上的收缩变换，将大小l l 的d 映射成 k x k 大小的块：y i 为8 个列折和旋转变换；机为灰度处理算子， 包含对比度比例因子s 和灰度补尝因子( 亮度因子) o 则有 ，、 r ，a 谚仍t ，l d ，j 设r i 的第i 个象素值为z i ，设( f ) i y i ( d j ) 的第i 个象素值为 z i ，则r i 的分形编码过程就是寻找合适的d j 、帆、y 使下式最小： r k k e r r o r = ( 互s z 存, i a c q u i n 的编码方案中，s 取值介于 o 2 ，0 3 ，o 9 ) 之间 。可通过下式计算而知， 0 = z 。一s z ? 其中乏= 丽1k 蔷x k 辐= 去善z 也就是说，对于r i ， 种取值中，找出最佳d j ， 使 丽qe r r o r = d 。 其编码方程就是在所有d j 中以及s 的各 s ，o 设要编码的图像为u ，编码过程为 第步：将u 划分成p 个n x n 的值块r l i 一，r p ，并使u = r i ur 2 u u r p 和r i ( r j = 0 ( i c j ) h 壮，同时也将其分为q 个域块d l ，d 2 ，d q ， 其交集可以不为零，并集一般等于u 。域块d i 的尺寸一般比值块r i 大一倍，为2 n x 2 n 。 第二步：将域块d i 的尺寸缩小一倍，使之与值块尺寸相同。记设 值块 d 】，d 2 ，d q ) 经尺寸压缩后为 6 l ，西，反) 则 矾) ：些焦吐鲤型趔兰攀丝尘型坐旦业 d 其中i j 2 0 ，1 ， n 。1 。 石l ，西，反) 有时也称作虚拟码书。 第三步：对值块r i ，找到最佳码矢亩j 西i ，茂，晚) ，最佳几何 变换t t o , h ，7 ) ，最优比例因子a ( 下标+ 表示最优解，以下同) 和灰度平移量b 。的组合( j ，t 。，a ，b ) ，使下式成立： ( j ，t ，a ，b ) 2 ( j ，t ，a b ) ：f fr i - a t ( 历) 一b f f2 r a i n | jr i a t ( 历) 一 n 川 盯k r h 幻 m h r义 h志 m 小 d 最 b ) 其中， t = f t 0 , t ，t 7 ) 为8 种几何变换，j = l ，2 ，q ) ，在上式 中，最优分形参数( j ，t ，a b ) 是针对值块r i 的，但为了表达简练， 我们都省略了索引i 。 对给定的t ：t k 和域块反，最优参数a + 和b 为 i r ，一面l f k ( 石，) 一t i ) ) a ：j 二，二一 ( f ( 茸) 一， ( 3 ，女( 历) 一，女( 历) ) b 一瓦，一小t k ( 历) 在上式中，瓦，和f ( d j ) 分别代表r i 和t k ( 3 j ) 得平均值， 表示图像内积，如果计算得到的孙大于1 ，则需作限幅处理，使其 小于1 。 汜y = t ( x ) ，前面提到的8 种几何变换指 ( 滓0 ) 相同 ( i = 1 ) 沿垂矗中轴对折 ( i = 2 ) 沿水平中轴对折 ( 滓3 ) 沿主对角线对折 ( 滓4 ) 沿轴对角线别折 ( i = 5 ) j l 删钟旋转9 0 0 ( 滓6 ) 顺日、j 钭一旋转18 0 0 ( i = 7 ) 逆时钟旋转9 0 0 y ( i j ) 一x ( i j ) y ( i j ) = x ( i ，n 一1 - j ) y ( i j ) = x ( n 一1 - i j ) y ( i j ) = x ( i ，i ) y ( i j ) = x 州- l - j , n 一1 一i ) v ( i d ) = x q ，n 一1 - j ) y ( i j ) = x ( n 一1 一i , n - 1 - j ) y ( i j ) = x ( n - 1 一i j ) 这种方法有很好的可信度，但对每一个值域子块都要在整个定 义域中搜索，花费时间过多。 第四步：保存最佳分形编码参数( j ，t 。，a + ，b + ) 作为对r i 的编码结果。 第五步：对所有r r l ，r ) 重复第三步和第四步。 这种编码算法的流图如图2 2 2 所示。由于它对每个值域子 块都要在整个定义域中搜索，所以运算量比较大花费时间过多， 这是它最大的弱点。 这种力法有很好的可信度，但对每一个值域子块都要在整个定 义域巾搜索，花费时间过多。为了缩短压缩时间，提高压缩比， j a c q u i n 又根据值域子块r l 和定义域子块d ，的复杂性，将它们分 为四类：平滑子块，中等复杂子块，简单边缘子块，混合边缘子块。 对于每类值域了块，其搜索过程只需在同类定义域子块中进行，这 就火大减少了搜寻的数月，简少了压缩编码的时间，同时对各类子 块，其处理方法也略有不同。 【1 ) 对于平滑值域予块，这类了二块的灰度变化极为乎缓，接近于一 个灰度，因此对这类予块的编码，只需存储其平均灰度岳，仅需8 个比特( 对8 比特表示的图像而言) ： ( 2 ) x jr 中等复杂的值域子块，这类子块的灰度有一定的变化，但 小含有边缘，剥这类予块，旋转与对折变换的意义不大，冈此，为 提音i 压缩比，省略旋转与对折变换q ： ( 3 ) 对于简单边缘子块和混合边缘予块，块内灰度变化较大，且含 有边缘，因此需全部采用上述变换。 识。 在存储分形变换参数时，要首先存储2 比特的码字用于类别标 解码时，分形压缩有其特殊的表现形式，由分形编码方法的数 学原理可知，在编码过程中所得到的i f s 是紧缩的，它的吸引子可 以通过任意初始图像的不断迭代变换而得到的。可以任意给定一幅 起始图像，只要尺寸与原图一致即可。每个值域块通过编码信息确 定的相应定义域块区域经过一个仿射变换得到。所有的值域块都计 算次后，称为一次迭代。根据吸引子定理，用一组w i 对初始图 像进行反复迭代最终收缩于一个不变图像。实际只需迭代数次就可 重构 h 解码图像，还用归一化均方误差，信噪比等确定迭代次数， 如果进一步迭代不能提高精度，就可以结束迭代。而解码的快慢与 新迭取的初始化图像有关，但一般情况下，需8 次迭代。 解码是相当迅速的。其解码流图如图22 3 所示。 开始 选定初始图象s o ，设定 迭代次数m ，设n = 0 根据觚缩剧象文件的数 据对s o 进行定义域分块 n = nq - 1 读取乐缩文件数据：顺序读 取个定义域子块位置和 对s o 对应的定义域子 块进行仿射变换 图2 2 3 解码流图 是 实验结果： 本实验的目的是为了显示分形压缩编码的性能，并为后续的改 进方案作标准：本实验采用的原始待编码图象尺寸为5 1 2 x5 1 2 灰 度缀为2 5 6 的l e n a 图象。对浚图作8 8 大小的块分割构成分形交 换的值域单元集合，且相邻块之问不重叠。分形变换的定义域单元 为原图象中1 6 1 6 的图象块，相邻块之间的位置平移为4 象素。 我们用瓜缩比c r = _ = ；生，( 其中a 。表示原始陶象的比特 a ”m 数，a 。表示坼缩图象的比特数) ，和峰一峰信噪比p s n r ，以 及压缩时间t 来衡量压缩效果。 图象l e n a ，其原始图象和解码图象如下图所示，压缩比 c r = 2 0 5 ，p s n r = 3 0 3 6 d b ，t r 约2 小时。 3 小结： ( 1 ) 原始图致f 2 ) 解码图象 阱上简要介绍了分形编码的基本思想和经典编码方法。 b a r n s l e y 的编码方案虽然没有具体的方法，但首次将分形理论与图 象编码相结合，获得很高的压缩比，具有一般性指导意义，为图象 压缩编码开创了一条新路。j a c q u i n 的压缩编码方案利用计算机进 行分形图象压缩编码，首次实现了自动分形压缩编码，为分形编码 的发展奠定了基础。 但是，j a c q u i n 的方法还存在着不足，尤其是在压缩时间上。 下而一章我将提出一些改进方案。 第三章一种基于局部搜索技术的分形d c t 混合编码方法 1 概述： 第一节分形编码方法研究 分形编码方法是计算机图形学与图象压缩编码相结合的产 物。在计算机图形学巾，分形方法早有应用。我们能够通过迭代函 数系统i f s 产生视觉上相当复杂的分形图形，然而在这些复杂图形 的背后，却是仅用几个字节就能表示的分形变换而已。从这个意义 上蜕，分形图形中存在这很大的冗余成分，由此人们就试图在图形 压缩编码中进行相反的过程，通过构造相应的分形变换，更有效的 表示待编码图象，从而达到图象压缩的目的，这是分形编码的思想 u 发点。 分形编码思想新颖独特，该方法基于如下假设：图象中的冗余 成分能够通过图象景物内容的分形特性( 自相似特性) 而有效去 除，分形特性在自然界中无处不有。有了这样的前提，给定一幅待 编码陶象，则对于这幅图象的编码实际上就是针对图象景物各部分 内容寻找分形变换的过程，编码结果就是得到了一系列的分形变 换。 3 分形编码方法的分析： 3 1 分形编码方法的优势： 自从1 9 8 8 年b a r n s l e y 首次提出分形图象压缩的概念以来，分形 图象l r 缩由于潜存的高乐缩比，图象恢复速度快等优点受到广泛的 关注。1 9 8 9 年，j a c q u i n 提出了一种基于分块的全自动编码方案， 可以在无人干预的情况下实现图象压缩，将分形图象压缩编码向前 椎土垃了一大步。从此以后，分形图象压缩编码就成为编码科研工作 者研究的焦点。 分形图象e 缩编码之所以有这样的魅力，主要是有以下的几个 特点： ( 1 ) 压缩原理新颖：在分形编码中，利用原始图象在不同分辨 率下的自相似性构造i 一个收缩的迭代函数系