基于分形理论和演化算法的灰度图像压缩
|
摘要
随着多媒体技术和计算机通信的日益发展，具有庞大数据量的数字图像极大地制约了图像通信。采用有效的压缩编码技术删除冗余，以尽量少的比特数存储图像，并同时保证图像的质量，已成为研究的热点。分形图像可进行压缩的原因是其图像具有高度的自相似自仿射特性。本论文从理论和实践上介绍了不同于传统方法的压缩算法——基于分形理论和演化算法的灰度图像压缩算法。作者采用迭代函数系统(IFS)对图像进行压缩。主要以不动点定理和拼贴定理作为理论基础，对给定的图像，寻找一组由压缩仿射变换构成的IFS，使图像通过仿射变换后尽可能与其相以。图像的解码，不依赖于原始图形，对任意初始图像，用IFS反复迭代，就能将原始图像重现。因此，编码文件只需存储IFS码，从而能得到较高的压缩比。
分形图像压缩的最终目的是要获得一个较好的IFS，使它的吸引子与原始图像尽可能的相似，可以把这个搜索问题看成是一个优化过程。这个优化过程是在大空间搜索和具有许多复杂约束的知识背景下进行的。传统的经典算法难以解决此问题，于是作者采用具有人工智能技术的演化算法来寻找最优解。演化算法从种群开始搜索，每个种群所获得的知识都被嵌入了其成员的染色体中。在进化过程中，它引入了自然进化和适者生存的原理，在复杂和变化的环境中寻找最有利的生存方式，可以以较大的概率较快速地找到最优解。
论文首先介绍了迭代函数系统和演化算法的基本定理和原理，它们是该课题研究的理论基础。然后，作者结合分形图像的特点编写了多种基于IFS理论的压缩算法。这些算法包括：全局分块搜索算法、固定门限法、自适应门限法、线性分类法、四分之一块灰度排列法和基于块合并的压缩算法。论文通过压缩算法的描述和实验结果的比较，得出了每种算法的特点。最后作者提出了一种改进的用于求解具有全局最优的自相似分块匹配的演化算法，详细地讲述了染色体编码方法、适应度函数的设计、遗传算子的设计和采样机理。通过实验的结果表明，该方法解码质量好、编码速度快、压缩比高，是一种可行的算法。
With the developing of multimedia technology and computer communication, digital image which have enormous data quantity restricts image communication. Effective encoding technologies to obliterate redundance and retain the image quality are the focus of research. The possibility of compression is because of high self-similarity and self-transformability redundancy of images. In this dissertation, from theoretical and practice viewpoint, we present a novel approach to compress gray-scale images by using Fractals Theory and Evolutionary Algorithms. The kernel theory based on in this paper is called Iterated Function System(IFS). The main idea is to find an IFS which consists of a set of contractive affine transformations mainly based on fixed-point theorem and collage theorem, when they are applied on the original image, the union of the transformed images will cover up the original image. Decoding process starts from any images which can recur the original image by applying IFS. Therefore, coding file only stores IFS code, which can achieve high compression ratio.
The purpose of fractal image compression is to gain a good IFS whose attractor is similar to original image. So this search problem can be viewed as a combination and optimization process with complicated constraints and a large searching space. Because traditional algorithm hardly handle with this problem, we adopt evolutionary algorithm to solve this problem which has the property of artificial intelligence technology. Evolutionary algorithm starts from initial population. The individuals of each population embed some new information while the searching can be directed to the promising area. The evolutive principle and the survival mechanism are applied in the algorithm. As a result, the best result can be fast achieved with high probability.
The dissertation starts by explaining the basic notions of Iterative Function System and Evolutionary Algorithms. Then we go to details of the ideas of compression algorithms based on IFS theory, such as range block search, fixed threshold, adaptive threshold, linear classification, and so on. Lastly, an evolutionary algorithm is proposed for obtainment of matching domain blocks of fractal partition in image compression. It makes use of the partition iterated function system and fractal image compression. Chromosome representation, initialization of population, design of special genetic operators are introduced
explicitly. The algorithm is robust and optimal. Both theoretical analyses and experiments show that higher compression ratio and image quality can be achieved.
分形图像压缩的最终目的是要获得一个较好的IFS，使它的吸引子与原始图像尽可能的相似，可以把这个搜索问题看成是一个优化过程。这个优化过程是在大空间搜索和具有许多复杂约束的知识背景下进行的。传统的经典算法难以解决此问题，于是作者采用具有人工智能技术的演化算法来寻找最优解。演化算法从种群开始搜索，每个种群所获得的知识都被嵌入了其成员的染色体中。在进化过程中，它引入了自然进化和适者生存的原理，在复杂和变化的环境中寻找最有利的生存方式，可以以较大的概率较快速地找到最优解。
论文首先介绍了迭代函数系统和演化算法的基本定理和原理，它们是该课题研究的理论基础。然后，作者结合分形图像的特点编写了多种基于IFS理论的压缩算法。这些算法包括：全局分块搜索算法、固定门限法、自适应门限法、线性分类法、四分之一块灰度排列法和基于块合并的压缩算法。论文通过压缩算法的描述和实验结果的比较，得出了每种算法的特点。最后作者提出了一种改进的用于求解具有全局最优的自相似分块匹配的演化算法，详细地讲述了染色体编码方法、适应度函数的设计、遗传算子的设计和采样机理。通过实验的结果表明，该方法解码质量好、编码速度快、压缩比高，是一种可行的算法。
With the developing of multimedia technology and computer communication, digital image which have enormous data quantity restricts image communication. Effective encoding technologies to obliterate redundance and retain the image quality are the focus of research. The possibility of compression is because of high self-similarity and self-transformability redundancy of images. In this dissertation, from theoretical and practice viewpoint, we present a novel approach to compress gray-scale images by using Fractals Theory and Evolutionary Algorithms. The kernel theory based on in this paper is called Iterated Function System(IFS). The main idea is to find an IFS which consists of a set of contractive affine transformations mainly based on fixed-point theorem and collage theorem, when they are applied on the original image, the union of the transformed images will cover up the original image. Decoding process starts from any images which can recur the original image by applying IFS. Therefore, coding file only stores IFS code, which can achieve high compression ratio.
The purpose of fractal image compression is to gain a good IFS whose attractor is similar to original image. So this search problem can be viewed as a combination and optimization process with complicated constraints and a large searching space. Because traditional algorithm hardly handle with this problem, we adopt evolutionary algorithm to solve this problem which has the property of artificial intelligence technology. Evolutionary algorithm starts from initial population. The individuals of each population embed some new information while the searching can be directed to the promising area. The evolutive principle and the survival mechanism are applied in the algorithm. As a result, the best result can be fast achieved with high probability.
The dissertation starts by explaining the basic notions of Iterative Function System and Evolutionary Algorithms. Then we go to details of the ideas of compression algorithms based on IFS theory, such as range block search, fixed threshold, adaptive threshold, linear classification, and so on. Lastly, an evolutionary algorithm is proposed for obtainment of matching domain blocks of fractal partition in image compression. It makes use of the partition iterated function system and fractal image compression. Chromosome representation, initialization of population, design of special genetic operators are introduced
explicitly. The algorithm is robust and optimal. Both theoretical analyses and experiments show that higher compression ratio and image quality can be achieved.
引文
[1]齐东旭．分形及其计算机生成．北京：科学出版社，1994
[2]余松煜．现代图像信息压缩技术．北京科学出版社，1998
[3]L.F.Arson.Fractal image compesion.New York:Byle,1993
[4]D.Dasgupta,Z.Miehalwize.Evolutionart algori(?) in engineering Applications.Berlin:Spring-Verlag,1997
[5]周明，孙树栋．遗传算法原理及应用．北京：国防工业出版社，1999
[6]llolland.J.ll.Evolutionary algorithm in search.Optimization and machine learning.New York:Addison-Wesley,1989
[7]张济忠．分形．北京：清，华大学出版社，1995
[8]陈守吉，张立明．分形与图像压缩．上海：上海科技教育出版社，1998
[9]D.Dasgupta,G.llernandez.An evolutionary algorithm for fractal coding of binary images.IEEE transaction on computation,2000,4(2)
[10]M.F.Barnsley.Iterated function systems and the global construction of fractals.London:Ser.A 399,1995
[11]M.F.Barnsley.A better way to compress images.New York:Byte,1988
[12]P.M Churchland.Could a machine think?.Amer:Sci,1995
[13]P.J.Denning.Will machine ever think?.Amer:Sci,1996
[14]李国杰．计算智能：一个重要的研究方向．计算机基础研究’94会议论文集．北京：清华大学出版社，1994
[15]E.Williams.Two approaches to machine intelligence.Computer,1992,11
[16]席裕庚，柴天佑．遗传算法综述．控制理论与应用．1996，13(6)
[17]刘勇．非数值并行计算．北京：科学出版社，1996
[18]陈国良．遗传算法及其应用．北京：北京邮电出版社，1996
[19]潘正君，康立山．演化计算．北京：清华大学出版社，1998
[20]Z.Michalwicz.演化程序—遗传算法和数据编码的结合．北京：科学出版社，2000
[21]A.ll.Wright.Genetic algorithms foe real parameter optimization.Amer:Sci,1991
[22]D.B.Fogel.An evolutionary approach to the traveling salesman problem.Nan Jing:Schaffer Proc of the 4th international conference on genetic algorithms,1998
[23]D.B.Fogel.Applying evolutionary programming to selected traveling salesman
problems. Cybern, 1994
[24] J.E. Baker. Adaptive selection methods For genetic algorithms. Nan Jing: Schaffer Proe of the 1th international conference on genetic algorit hms, 1994
[25] Y. Davidor, H.P.Schwefel. An introduction to adaptive optimization algorithms based on principles of natural evolutionary, Genetic and chaotic programming. New York: John Wiley & Sons, 1992
[26] H.P. Schwefel. Numerical optimization of computer models. UK: John Wiley, 1981
[27] W.M. Spears. B.Manderick. A massively parallel genetie algorithm: implementation and first analysis. Nan Jing: Schaffer Proc of the 4th international conference on genetic algorithms, 1998
[28] G. Sysweada. Uniform crossover in genetic algorithm. Proc of 3rd international conference on genetic algorithms, 1997
[29] Z. Michalewicz. A modified genetic algorithms for optimal control problems. IEEE transaction on computers. 1992, 23(12)
[30] 玄光男．程润伟．遗传算法与工程设计．北京：科学出版社，2000
[31] 吴乐南．数据压缩的原理与应用． 北京：电子工业出版社，1995
[32] 冈萨雷斯．数字图像处理． 北京：科学出版社，1981
[33] 吴成柯，戴善荣，陆心如． 图像通信．西安：西安电子科技大学出版社，1990
[34] 姚庆栋，毕厚杰，王兆华． 图像编码基础． 北京：人民邮电出版社，1984
[35] A.E. Jacquin. Fractal image coding based on theory of iterated contractive image transformations. IEEE transaction on visual communication, 1999,13(6)
[36] D.M..Monro. Fractal approximation of image blocks. IEEE ICASSP, 1992
[37] B. Ramamurthi. Classify vector quantization of image, IEEE transaction on communication. 1981,34(11)
[38] Y. Fisher, Fractal encoding: theory and application to digital image. New York: Springer Verlag, 1994
[39] K. Kunt, M. Kocher. Second-generation image-coding techniques. IEEE transaction on image processing. 1985,73(2)
[40] D. Saupe. Accelerating fractal image compression by multi-dimensional nearest neighbor search. IEEE data compression conference. 1995
[41] Y. Fisher, E.W. Jacbos, R.D. Boss. Fractal image compression using iterated transformations, Image and text compression Boston:MA, 1992
[42] 陈衍仪．图像压缩的分形理论和方法．北京：国防工业出版社，1997
[43] V. Krcinovich. Genetic algorithms-what fitness scalirig is optimal. IEEE transaction on cybernation and systems. 1993,24(1)
[44] J.H. Holland. Adaptation in nature and artificial systems. New York: MIT Press, 1992
[45] A. Brindlc. Genetic algori thms for function opyimization. New York: university of Alberta, 1981
[46] B. Ramamurthi, A.Gersho. Classified vector quantization of images. IEEE transaction on communication. 1986, 34 (11)
[47] S. Sahni. Data structures-algorithms and application in C++. New York: McGraw-Hill, 1988
[48] A.Clifford．数据结构与算法分析． 北京：电子工业出版社，1998
[49] 马小虎，张明敏，严华明．多媒体数据压缩标准及其实现． 北京：清华大学出版社，1996
[50] 孙家广．计算机图形学．北京：清华大学出版社，1998
[51] J．Bates,T.Tompkins.Visual C++使用指南．北京：电子工业出版社，1999
[52] 周长发．精通Vsual C++图像编程．北京：电子工业出版社，2000
[53] J.David.Visual C++6.0技术内幕．北京：希望出版社，2000
[54] 郝闻．Visual C++6.0开发与实例．北京：电子工业出版社，1999
[55] 彭达，王道智等．Visual C++多媒体编程技术．北京：人民邮电出版社，1999
[56] K.Gregory,Visual C++5.0开发使用手册．北京：机械工业出版社，1998
[2]余松煜．现代图像信息压缩技术．北京科学出版社，1998
[3]L.F.Arson.Fractal image compesion.New York:Byle,1993
[4]D.Dasgupta,Z.Miehalwize.Evolutionart algori(?) in engineering Applications.Berlin:Spring-Verlag,1997
[5]周明，孙树栋．遗传算法原理及应用．北京：国防工业出版社，1999
[6]llolland.J.ll.Evolutionary algorithm in search.Optimization and machine learning.New York:Addison-Wesley,1989
[7]张济忠．分形．北京：清，华大学出版社，1995
[8]陈守吉，张立明．分形与图像压缩．上海：上海科技教育出版社，1998
[9]D.Dasgupta,G.llernandez.An evolutionary algorithm for fractal coding of binary images.IEEE transaction on computation,2000,4(2)
[10]M.F.Barnsley.Iterated function systems and the global construction of fractals.London:Ser.A 399,1995
[11]M.F.Barnsley.A better way to compress images.New York:Byte,1988
[12]P.M Churchland.Could a machine think?.Amer:Sci,1995
[13]P.J.Denning.Will machine ever think?.Amer:Sci,1996
[14]李国杰．计算智能：一个重要的研究方向．计算机基础研究’94会议论文集．北京：清华大学出版社，1994
[15]E.Williams.Two approaches to machine intelligence.Computer,1992,11
[16]席裕庚，柴天佑．遗传算法综述．控制理论与应用．1996，13(6)
[17]刘勇．非数值并行计算．北京：科学出版社，1996
[18]陈国良．遗传算法及其应用．北京：北京邮电出版社，1996
[19]潘正君，康立山．演化计算．北京：清华大学出版社，1998
[20]Z.Michalwicz.演化程序—遗传算法和数据编码的结合．北京：科学出版社，2000
[21]A.ll.Wright.Genetic algorithms foe real parameter optimization.Amer:Sci,1991
[22]D.B.Fogel.An evolutionary approach to the traveling salesman problem.Nan Jing:Schaffer Proc of the 4th international conference on genetic algorithms,1998
[23]D.B.Fogel.Applying evolutionary programming to selected traveling salesman
problems. Cybern, 1994
[24] J.E. Baker. Adaptive selection methods For genetic algorithms. Nan Jing: Schaffer Proe of the 1th international conference on genetic algorit hms, 1994
[25] Y. Davidor, H.P.Schwefel. An introduction to adaptive optimization algorithms based on principles of natural evolutionary, Genetic and chaotic programming. New York: John Wiley & Sons, 1992
[26] H.P. Schwefel. Numerical optimization of computer models. UK: John Wiley, 1981
[27] W.M. Spears. B.Manderick. A massively parallel genetie algorithm: implementation and first analysis. Nan Jing: Schaffer Proc of the 4th international conference on genetic algorithms, 1998
[28] G. Sysweada. Uniform crossover in genetic algorithm. Proc of 3rd international conference on genetic algorithms, 1997
[29] Z. Michalewicz. A modified genetic algorithms for optimal control problems. IEEE transaction on computers. 1992, 23(12)
[30] 玄光男．程润伟．遗传算法与工程设计．北京：科学出版社，2000
[31] 吴乐南．数据压缩的原理与应用． 北京：电子工业出版社，1995
[32] 冈萨雷斯．数字图像处理． 北京：科学出版社，1981
[33] 吴成柯，戴善荣，陆心如． 图像通信．西安：西安电子科技大学出版社，1990
[34] 姚庆栋，毕厚杰，王兆华． 图像编码基础． 北京：人民邮电出版社，1984
[35] A.E. Jacquin. Fractal image coding based on theory of iterated contractive image transformations. IEEE transaction on visual communication, 1999,13(6)
[36] D.M..Monro. Fractal approximation of image blocks. IEEE ICASSP, 1992
[37] B. Ramamurthi. Classify vector quantization of image, IEEE transaction on communication. 1981,34(11)
[38] Y. Fisher, Fractal encoding: theory and application to digital image. New York: Springer Verlag, 1994
[39] K. Kunt, M. Kocher. Second-generation image-coding techniques. IEEE transaction on image processing. 1985,73(2)
[40] D. Saupe. Accelerating fractal image compression by multi-dimensional nearest neighbor search. IEEE data compression conference. 1995
[41] Y. Fisher, E.W. Jacbos, R.D. Boss. Fractal image compression using iterated transformations, Image and text compression Boston:MA, 1992
[42] 陈衍仪．图像压缩的分形理论和方法．北京：国防工业出版社，1997
[43] V. Krcinovich. Genetic algorithms-what fitness scalirig is optimal. IEEE transaction on cybernation and systems. 1993,24(1)
[44] J.H. Holland. Adaptation in nature and artificial systems. New York: MIT Press, 1992
[45] A. Brindlc. Genetic algori thms for function opyimization. New York: university of Alberta, 1981
[46] B. Ramamurthi, A.Gersho. Classified vector quantization of images. IEEE transaction on communication. 1986, 34 (11)
[47] S. Sahni. Data structures-algorithms and application in C++. New York: McGraw-Hill, 1988
[48] A.Clifford．数据结构与算法分析． 北京：电子工业出版社，1998
[49] 马小虎，张明敏，严华明．多媒体数据压缩标准及其实现． 北京：清华大学出版社，1996
[50] 孙家广．计算机图形学．北京：清华大学出版社，1998
[51] J．Bates,T.Tompkins.Visual C++使用指南．北京：电子工业出版社，1999
[52] 周长发．精通Vsual C++图像编程．北京：电子工业出版社，2000
[53] J.David.Visual C++6.0技术内幕．北京：希望出版社，2000
[54] 郝闻．Visual C++6.0开发与实例．北京：电子工业出版社，1999
[55] 彭达，王道智等．Visual C++多媒体编程技术．北京：人民邮电出版社，1999
[56] K.Gregory,Visual C++5.0开发使用手册．北京：机械工业出版社，1998