《分形图像压缩.doc》由会员分享，可在线阅读，更多相关《分形图像压缩.doc（7页珍藏版）》请在三一文库上搜索。
1、宁波工程学年论文分形图像压缩裘勤超,应宏微宁波工程学院 电子与信息工程学院 浙江 宁波 (315016)摘要：21世纪，互联网技术正在迅猛的发展，以图像为主的多媒体技术大大丰富了我们的生活。但是如果没有一个高效的压缩方法，图像通信将不可能实现。图像压缩编码的目的就是要以尽量少的比特数表征图像，同时保持复原图像的质量，使它符合特定应用场合的要求。图像压缩也是多媒体技术的关键和瓶颈之一。分形图像处理技术是分形理论与图像处理技术结合的产物，已经在压缩编码、区域分割、模式识别等方面得到较多的应用。分形图像压缩方法是根据图像的自相似性，将一幅数字图像转化为一组收缩的迭代函数系统模型，通过对迭代函数系统参
2、数编码达到图像压缩的目的。分形图像压缩方法具有压缩比高，解码速度快的优点。关键词：图像压缩、分形、迭代函数系统一、引 言近年来，分形学已广泛应用于自然科学与社会科学的众多领域。分形图像压缩的基础是分形变换，实际上是局部迭代函数系统。1988年，Barnsley对几幅图像进行压缩编码，获得了高达10000:1的压缩比，当然这是对特定的图像而言的。1992年12月，微软公司推出一张磁盘，他是一部奇特的集文字、动画、音响、图像与照片于一体的百科全书，其中还包含了一部地图册与一部辞典。它有7个小时的音响、100个动画及800张可缩放的彩色地图。在700多张高质量的图片中有鲜花、植物、人物、动物、云彩与
3、名胜等，而所有这些压缩后的数据没有超过600M，做到这一点的恰是分形技术。Barnsley评价说：“They are all fractals”。IFS可以产生分形，进而发现利用IFS码可以进行图像压缩。比如一张512*512的黑白色蕨叶，我们用4个仿射变换去产生它，每个变换6个系数，每个系数占用32bit，故其IFS码占用了768个bit，而这幅图像在计算机里占用了512*512*1=262144*1个bit，用IFS码作为对蕨叶的压缩编码，则其压缩比高达341倍。另外，对一张枫叶(512*512)图像的压缩更高达1365倍，而采用DCT为核心的方法，其压缩比在820倍左右，通过精心调整的小
4、波变换方法，也只达到100倍左右，可见分形压缩编码在图像压缩中的巨大潜力1。二、分形图像压缩1.概述分形图像压缩现况分形是非线性科学中的一个重要领域。分形图像是一种具有复杂几何形状，不规则的图像，但其内部存在着无穷多个自相似性，因而可以用一组简单的迭代函数方程通过随机迭代而得到。这个思想在80年代末被引入到图像的压缩编码中，从严格具有自相似性的分形图像推广到一般的任意图像，从黑白图像推广到有灰阶甚至于彩色图像上。如果任意图像都可以近似为分形图像，那么只要找到其图像内部存在的自相似迭代函数的参数，则图像就可用迭代函数的参数来表达，这就大大压缩了图像的信息量，解决图像压缩编码中的问题。近年来，由于
5、信息科学和工程应用的发展，图像分形编码的研究也发展很快，分形几何在图像压缩编码中的应用成为十分诱人的研究领域。分形编码利用分形几何中自相似性原理来实现数据压缩的。首先对图像进行分块，然后在去寻找各个块之间的相似性，这里的相似性的描述主要是依靠仿射变换来确定的，一旦找到了每块的放射变换，就保存下这个放射系数，由于每块的数据量远远大于放射变换的系数，因而，图像得到大幅度的压缩。十多年来，虽然分形图像编码和解码不断改进，但仍然不够成熟，产生的压缩比不够高，压缩效果还不十分理想，在当前图像压缩编码中还不能占据主导地位。国际标准MPEG4中已经把小波分析列了进去，但分形编码不在其中。静态压缩标准JPEG
6、 2000有着完全的优势和巨大潜力。 总之，分形不管是作为一门艺术还是作为一门科学，或者说是科学与艺术的交叉：即用简单构造复杂，用科学再现艺术，都会让人着迷。正如分形之父所言：似乎没有人会对分形无动于衷。虽然分形在计算机图形学，数据压缩有巨大的潜力，但是其应用还处于摸索阶段，这有待于广大分形爱好者的努力2。2.分形压缩原理和方法(1)缩仿射变换（Contractive Affine Transformation）如果一个平面图形上的各点经过线性变换后，图形上各点的距离比原有的距离要小，那么就称这种变换是收缩仿射变换。这个变换的a，b，f是变换矩阵的系数。比如，一个变换为：用它对一个图的各点进行
7、变换,变换后得到一新图。其形状与原图形相似，但各点的距离缩短。显然，如果对一个图形反复施加收缩仿射变换，即对W(F)再行变换得到W2（F），对W2（F）又施行变换得到W3（F），其迭代的结果将使原来图形收缩为一个点。(2)迭代函数系统（Iterated Function System）人们把若干个收缩仿射变换的组合称为迭代函数系统（IFS）。分形几何学中有一个定理：每一个迭代函数系统都定义了一个唯一的分形图形，这个分形图形称为该迭代函数系统的吸收子（attractor）。这个定理称为收缩影射不动点原理。最典型的例子是一片蕨子叶却所对应的迭代函数系统： 图1它所定义的蕨子叶如图1所示。从这个例子
8、可看出，要产生一个复杂的图形需要得数据并不多。蕨叶对应的迭代函数系统只有24个系数。如果以8比特代表一个系数，那么192比特就可以代表一片蕨叶。可见压缩比是很大的。分形图像压缩的提出者之一邦利斯曾经扬言，他实现过10000:1的压缩。是否夸大不得而知，但分形压缩很有潜力却是毋庸置疑的。(3)采用迭代函数系统的图像压缩方法从蕨叶的例子可看出，迭代函数系统用不多的系数就可以代表一幅图像，从而得到很大的压缩比。但在实用时，如何寻找一个图像的迭代函数系统呢？目前有两个办法；一是基于图像的自相似性，直接计算迭代函数系统各收缩仿射变换的系数、二是把图像分割成教小的部分，然后从迭代函数系统库中查找这些小部分
9、所对应的迭代函数系统。前一种方法适合于那些自相似性很强的图形。此处以谢尔品斯基垫为例加以说明。图2(a)是一个谢尔品斯基垫，可以看出，整个垫子是由上、左下、右下3个较小的垫子组成。每个较小的垫子是由原来的垫子经收缩仿射变换得来的。如果能分别找出把原图形变成3个小图形的收缩放射变换，那么，整个迭代函数系统就定下来了。图2设来垫子3各顶点的坐标分别为（x1,y1），（x2,y2），（x3,y3）。变换所得小垫子的3个顶点坐标为（x1,y1），（x2,y2），（x3,y3）。图2(b)表示的是把原垫子变为上面小垫子的坐标。把W1的变换式展开:x1=a1x1+b1y1+e1y1=c1x1+d1y1+f
10、1x2=a1x2+b1y2+e1y2=c1x2+d1y2+f1x3=a1x3+b1y3+e1y3=c1x3+d1y3+f1解这组方程得到变换W1的各系数。以图2(b)所示各坐标点的数值代入以上方程组，得到。同理，利用左下方垫子和右下方垫子可求出变换W2和W3的系数分别为:a2=d2=0.5,b2=c2=e2=f2=0,a3=d3=0.5,b3=c3=f3=0,e3=1.直接计算迭代函数系统各变换矩阵系数的方法只能用于那些局部与整体有自相似特性的图像，而许多图像是难以用上述办法寻找迭代函数系统的。但若能把整个图像分割成小片，而这些小片图像的迭代函数系统是已知的，同样也可以实现图像的压缩。办法就是
11、事先建立一个分形库（这个库里只需存储分形相应的迭代函数系统代码），原图像分割的小片可按库的目录去寻找相应的迭代函数系统。当然，如何自动把图像合理地分割成小片，分形图形如何适当地放大、缩小或旋转以使之与目标尽可能的重合等，都还有大量的工作要做。3.分形图像压缩的实例利用分形几何方法进行图像压缩的历史比传统方法要短的多，因此相对也没有传统方法那么成熟。目前，尽管还不如传统方法那样已经有了对活动图像进行图像压缩的软件、硬件，但对单幅图像的分形压缩方法已经出现了商品化得计算机软件。提供这种软件的公司是美国迭代系统公司（Iterated System Inc.）。他们提供的软件名叫SuperBase F
12、ractal Picture Linkers，这是一个配合SuperBase数据库系统的软件。它可以把画面进行压缩，得到的图形文件称为分形图像格式（Fractal Image Format，FIF），也可以把FIF文件解压成原有图像。对程序开发人员，迭代系统公司还有POEM Colorbox 和POEM Videobox等软件，前者使开发人员能够在微软视窗下把FIF文件集成到普通应用软件内，后者则可对MS-DOS上运行的应用软件中的图像进行压缩或解压。4.分形图像压缩有待研究的问题分形图像压缩是有失真的，失真量大小与压缩比密切相关。尽管分形图像压缩有巨大的潜力，但要把这种潜力释放出来，还有许多
13、问题有待进一步的研究，主要表现在：* 普遍性问题。对于一定的整体与局部存在明显相似性或仿射性的分形图像类，分形图像压缩方法的压缩比较高，但难以期望在很低的失真条件下，对一切分形图像压缩都具有极高的压缩比，只能在压缩比与失真度之间加以平衡。* 就目前分形压缩技术而言，其编码时间比较长。因此，需要开发编码时间短、效率高的分形压缩算法。* 理论上，有关自动压缩原理与算法，失真测度或相似性准则等有待继续深入研究。* 实用化编码方法与硬件实现。总之，分形理论用于图像压缩之所以有效，是因为自然界中普遍存在着分形物体，它们表面上具有非常复杂的统计特性和视觉特性，但信息量却很少，可用几条简单的确定规则迭代出来
14、。传统的建立于信息论之上的图像压缩技术几乎不能压缩这类图像。而使用分形编码，只需对少数几条变换规则进行编码，即可以获得非常高的压缩比。但另一方面，由于自然界的景物千差万别，因此分形压缩尚有许多问题有待人们深入研究。5.分形图像压缩的发展趋势分形图像压缩编码的研究发展趋势主要表现为以下几个方面：(1)分形编码在人工干预条件下能够达到相当高的压缩比，但对于如何去掉人工干预则需研究给定的图像，实现计算机自动确定分形生长模型、IFS码和RIFS码等，寻找新的压缩模型和新的突破点。(2)综合分析当前自动编码的各种改进算法，继续寻找加快编码速度、提高压缩比、改善压缩效果的突破性方法。(3)研究按分形维数分
15、割图像，将分形维数相同的区域块用分形方法进行编码的理论、方法及实现的算法。(4)继续研究分形编码与其他编码方法相结合的新的编码方法。(5)进一步研究分形图像压缩的计算机仿真和实际应用。分形图像压缩编码的应用已经深入到人类活动的各个方面，并已取得了令人瞩目的成果。分形图像压缩既考虑局部与局部，又考虑局部与整体之间的相关性，适合于自相似或自仿射的图像压缩；分形图像压缩解码时能放大到任意大的尺寸，且保持精细的结构；在高压缩比的情况下，分形图像压缩自动编码能有很高的信噪比和很好的视觉效果。因此，分形图像压缩是一个有潜力、有发展前途的压缩方法。分形编码和小波变换进行结合，充分利用了小波变换后图像自相似强
16、的特点对图像进行了分形编码。本算法具有压缩比高（约16：1），信噪比大（28分贝）且运算速度快的特点。三、结论分形真正作为一门科学开始于上个世纪60年代，虽然短短几十年的发展，在生物，物理，地理，计算机，哲学等各个学科都取得了喜人的成绩。它开辟了科学与艺术的融合，分形的不规则散发自然魅力，利用巧妙的算法构造精美图案，完整的代码再现非凡的艺术，另外，改变了传统的图像压缩思想，使图像的压缩比10000：1成为可能。但应该看到，这些成绩大部分都停留在理论阶段，虽然，分形人们经常接触但是分形还鲜为人知，特别是在国内。其应用只仅仅局限于，服装设计，装潢设计，而潜力巨大的图像压缩还仅仅处于摸索阶段，大部分
17、算法失真的结果令人无法忍受，有待于改进。这需要所有分形爱好者的努力！参考文献1李水根，吴纪桃. 分形与小波M. 北京：科学出版社，2002. 2陈守吉，张立明. 分形与图像压缩M. 上海：上海科技教育出版社，1998. Fractal Image CompressionQiu Qinchao Ying HongweiNingbo University of Technology，Electronic and Information Engineering，Ningbo Zhejiang China (315607)AbstractIn the 21st century, the rapid d
18、evelopment of Internet technology is mainly in the image, multimedia technology greatly enrich our life. But if no effective compression method, image communication will not be possible. Image compression is less as far as possible to characterize the number of bits, while maintaining the image of t
19、he restored image quality, make it conform to specific applications. Image compression is the key of multimedia technology and the bottleneck. Fractal image processing technology is fractal theory and image processing technology, the combination of compression and regional segmentation, pattern reco
20、gnition, etc have many. Fractal image compression method is based on the image similarity, since a digital image into a group of contraction iterated function system model, based on iterative function system parameters of the code to image compression. Fractal image compression method has higher compression ratio, decoding speed. Key words: image compression, fractal, iterative function system