基于区域划分的分形图象压缩方法
|
摘要
分形图象压缩方法是根据图象的自相似性，将一幅数字图象转化为一组收缩的迭代函数系统模型，通过对迭代函数系统参数编码达到图象压缩的目的。分形图象压缩方法具有压缩比高，解码速度快的优点。对于现实生活中的大量非严格自相似图象，常用的是基于子块划分的分形图象压缩方法。这种方法将图象划分为规则形状的不重叠的子块集，根据子块的局部自相似性，找出集中每一个子块的迭代函数系统，由全体子块的迭代函数系统参数形成分形图象压缩编码。
本文设计了一种基于区域划分的分形图象压缩方法。首先在第一章中介绍了分形图象压缩研究的意义和数字图象质量的评价标准。接着在第二章中阐述了分形图象压缩的理论基础，通过对完备空间中迭代函数系统性质的研究，提出了分形图象压缩的两个基本定理：压缩映射的不动点定理和拼贴定理。在第三章中讨论并实现了基于子块划分的分形图象压缩方法，这种方法将原始图象划分为不重叠的正方形值域块集和四倍大小的正方形定义块集，对于每一个值域块，在定义块集中通过最佳匹配找出最相似的定义块，通过匹配得到值域块的最佳自相似变换，对所在值域块的最佳自相似变换参数编码实现图象压缩。在第四章中讨论并实现了基于区域划分的分形图象压缩方法，这种方法首先采用第三章中的方法进行初始化，形成最初的由正方形子块组成的最小区域集和相邻区域对队列，并得到每一个区域的多个最佳自相似变换，根据拼贴误差最小的原则，在保证一定性噪比前提下，不断合并最佳相邻值域对，实现区域合并，最终图象划分区域集由一些不规则形状区域组成，对这些区域自相似变换参数和区域形状编码实现分形图象压缩。通过对两种分形压缩方法性能的比较，基于区域划分的分形图象压缩方法可以在相同的性噪比下达到更高的压缩比，压缩性能显著提高。
The method of fractal image compression transfers a digital into a group of contract iterate function system (IPS) model. Encoding IFS's parameters achieves image compression. This method may gain higher compression ratio,as well as decoding rapidly. To many not strictiy self-similar image,the usual fractal image compression method based on block partition divides the image into non-overlap regular shape block collection. Every block's iterate function system is found out by local self-similarity. The parameters of all iterate function system form fractal image compression code.
In this paper,a fractal image compression method based on region partition is devised. The first chapter introduces the significance of fractal image compression research and the valuation standard of image quality. The second chapter sets forth the theorem basis of fractal image compression. By researching the property of iterate function system in metric space,two basic theorems are brought outthe fixed-point theorem of contract mapping and collage theorem. In the third chapter,fractal image compression method based on block partition is discussed and implemented. The original image is divided into non-overlap square domain block collection and range collection,which is fourfold the domain block. To every domain block,the best self-similarity transformation is gained by matching the found best similar range block,The parameters of the gained best domain block's transformations are the image compression code. The fourth chapter discusses and implements fractal image compression method based on region partit
ion. Firstly,the least square region collection and neighboring regions pair queue are gained,by initiating using the method referred in the third chapter. Following,under a given fixed sign to noise rate,the best neighboring domain region pair is combined continually in according with the least collage error principle. Finally,the image region collection comprises many irregular shape regions. The image compression code is gained by
encoding the parameter of the self-similar transformation and shapes of regions. In comparison with the abilities of two fractal image compressions,the fractal image compression method based on region partition can gain higher compression ratio as the same of sign to noise rate,which compression ability is improved obviously.
本文设计了一种基于区域划分的分形图象压缩方法。首先在第一章中介绍了分形图象压缩研究的意义和数字图象质量的评价标准。接着在第二章中阐述了分形图象压缩的理论基础，通过对完备空间中迭代函数系统性质的研究，提出了分形图象压缩的两个基本定理：压缩映射的不动点定理和拼贴定理。在第三章中讨论并实现了基于子块划分的分形图象压缩方法，这种方法将原始图象划分为不重叠的正方形值域块集和四倍大小的正方形定义块集，对于每一个值域块，在定义块集中通过最佳匹配找出最相似的定义块，通过匹配得到值域块的最佳自相似变换，对所在值域块的最佳自相似变换参数编码实现图象压缩。在第四章中讨论并实现了基于区域划分的分形图象压缩方法，这种方法首先采用第三章中的方法进行初始化，形成最初的由正方形子块组成的最小区域集和相邻区域对队列，并得到每一个区域的多个最佳自相似变换，根据拼贴误差最小的原则，在保证一定性噪比前提下，不断合并最佳相邻值域对，实现区域合并，最终图象划分区域集由一些不规则形状区域组成，对这些区域自相似变换参数和区域形状编码实现分形图象压缩。通过对两种分形压缩方法性能的比较，基于区域划分的分形图象压缩方法可以在相同的性噪比下达到更高的压缩比，压缩性能显著提高。
The method of fractal image compression transfers a digital into a group of contract iterate function system (IPS) model. Encoding IFS's parameters achieves image compression. This method may gain higher compression ratio,as well as decoding rapidly. To many not strictiy self-similar image,the usual fractal image compression method based on block partition divides the image into non-overlap regular shape block collection. Every block's iterate function system is found out by local self-similarity. The parameters of all iterate function system form fractal image compression code.
In this paper,a fractal image compression method based on region partition is devised. The first chapter introduces the significance of fractal image compression research and the valuation standard of image quality. The second chapter sets forth the theorem basis of fractal image compression. By researching the property of iterate function system in metric space,two basic theorems are brought outthe fixed-point theorem of contract mapping and collage theorem. In the third chapter,fractal image compression method based on block partition is discussed and implemented. The original image is divided into non-overlap square domain block collection and range collection,which is fourfold the domain block. To every domain block,the best self-similarity transformation is gained by matching the found best similar range block,The parameters of the gained best domain block's transformations are the image compression code. The fourth chapter discusses and implements fractal image compression method based on region partit
ion. Firstly,the least square region collection and neighboring regions pair queue are gained,by initiating using the method referred in the third chapter. Following,under a given fixed sign to noise rate,the best neighboring domain region pair is combined continually in according with the least collage error principle. Finally,the image region collection comprises many irregular shape regions. The image compression code is gained by
encoding the parameter of the self-similar transformation and shapes of regions. In comparison with the abilities of two fractal image compressions,the fractal image compression method based on region partition can gain higher compression ratio as the same of sign to noise rate,which compression ability is improved obviously.
引文
[1] 曼德勃罗特，《大自然的分形几何学》(中译本)的序(1997．1．9)，陈守吉、凌复华译，上海远东出版社，1998．
[2] B.B.Mandelbrot, Les ob jets fractals: forme, hazard et dimension, Flammarion, 1975.
[3] B.B.Mandelbrot, Fractals: form, chance, and dimension, Freeman, 1977.
[4] Y. Fisher, (ed.)Fractal Image Compression: Theory and Application, Springer, 1995.
[5] K.Falconer, Fractal Geometry, Wiley & sons, 1990.
[6] B.B.Mandelbrot, The Fractal Geometry of Nature, freeman, 1983.
[7] J.Huchinson, Fractals and Self Similarity, Indiana Univ. Math. J.30.1981.
[8] M.F. Barnsley,et.al, Iterated function systems and the global construction of fractals, Proc. Roy. Soc. London, Ser. A 399, 1985.
[9] M.F. Bamsley, Fractals Everywhere (2 ed.), Academic Press, 1993.
[10] J.E.Blton, An ergotic theorem for iterated maps, Egotic Theory Dynamical System, 7,1987.
[11] M.F.Barnsley, et. al, The Desktop fractal Design System Handbook, Academic Press, 1992.
[12] M.F. Bamsley, et.al, Fractal image compression, AK Peter, 1993.
[13] Oden, Applied Functional Analysis, 1975.
[14] 顾其均，图象分形编码与压缩技术，《分形几何讲义》，非线性科学研讨班讲义，1994．
[15] A.P. Pentland, Fractal-based description of nature scenes, IEEE Trans. MAMI-6(6), 1984.
[16] 齐东旭，《分形及其计算机生成》，科学出版社，1994．
[17] M.F.Bamsley, A.D.Sloan, A Better W ay to Compress Image Byte, Jan. 1988.
[18] 吴平南，《数据压缩的原理与应用》，电子工业出版社，1995．
[19] M.F. Barnsley ,A.D.Sloan, A Better W ay to Compress Image Byte, Jan. 1988.
[20] A.E.Jacquin, A Novel fractal Block-Coding Technique for Digital Image, Proceedings of ICASSP IEEE International conference on ASSP, Vol. 4 1990.
[21] A.E.Jacquin, Fractal Image Coding: A/Review, Proceedivg of the IEEE Vol.81 No.10 1993.
[22] Y. Fisher, Fractal Image Compression, Fractals Vol.2 No.3 1994.
[23] Y. Fisher, fractal Encoding: Theoy and Application to Digifal Image, Springer Verlag, New York 1994.
[24] E.W. Jacobs ,Y. Fisher, R.D.Boss, Image Compression: A Study of the Itrated Transform Method, Signal Processing Vol.29,1992.
[25] T. Bedford, F.M.Dekking, M.S.Keane, Fractal Image Coding Techniques and Contraction operators, Nieuw Arch. Wisk(4) 10,3,1992.
[26] A.E.Jacquin, Image Coding Based on a Fractal Theoy of Iterated Contractive
Markov Operators, Part I、 II:Theoretical Foundation, Report Math. 91389-016 Georgia Institute of Technology, 1989．
[27] A.e.Jacquin, Fractal Image Coding Based on A Theoy of Iterated Contractive Image Transformafions, IEEE Trans, Image Proessing Vol.1 1992．
[28] H.Lin, A.N.Venetsanopoulos, A Pyramid algorithm for Fast Fractal Image Compression, Proceedings of ICIP. 95 IEEE International Conference on Image Processing 1995．
[29] D.Saupe, R.A.Hamzaoui, A Guided Tour of The Fractal Image Compression Literature, New Directions for Fractal Modeling in Computer Graphics, J.Hart, ACM Siggraph Course Notes 13,1994．
[30] F.M.Dekking, An Inequality for Pairs of Martingales and Its Applications to Fractal Image Coding, Technical Report 95-10 Faculfy of Technical Mathematics and Informatics Delft university of Technology, 1995．
[31] F.M.Dekking, Fractal Image Coding: Some Mathematical Remarks on Its Limits and Its Prospects, Thechnical Report, Faculty of Technical Mathematics and Informatics Delft University of Technology, 1995．
[32] H.Lin, A.N.Venetsanopoulos, Incorporating Nonlinear Contractive functions into fractal Coding, Proceedings of International W orkshop on Intelligent Signal Proessing and Communication System, 1994．
[33] Y.Fisher, S.Menlove, Fractal Encoding With HV Partitions, Fractal Image Compression-Theoy and Application, Springer Verlag, New York, 1994．
[34] F.Davoine, E.Bertin, J.M.Chassery ,From Rigidity to Adaptive Tessellation for Fractal Image Compression: Compression: Comparative Studies, proc. Of IEEE 8th Workshop on Image and Mutidimensional Signd processing 1993．
[35] F.Daroine, E.Bertin, J.M.Chassery ,An Adaptive Partition for Fractal Image Coding, NATO ASI Couf. Fractal Imag Encoding and Analysis, 1995．
[36] L.Thomas ,F.Deravi, Region Based Fractal Image Compression Using Heuristic Search, IEEE Trans, on Image processing Nol.4． No.6 1995．
[37] D.Saupe, M.Ruhl, Evolutionary Fractal Image Compression, Proc. ICIP-96 IEEEE Internation al Conference on Image Processing, 1996．
[38] M.F.Barnsley ,Lecture Notes on Iterated Function System, Proceedings of Symposia in Applired Mathematics Vol.39,1989．
[39] Emmanuel Rousens, Sequence Coding Based on The Fractal Theoy of Iterated Transformations Systems SPIE Vol.2094．
[40] I.Daubechies, Ten lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992．
[41] S.E.Mallat, A Theoy for Multiresolution Signal Decomposition The Wavelet Represantation, IEEE Trans on Pattern Analysis and Machine Intelligencl Vol.11,No.7 1989．
[42] E.H.Adelson and E.Simoncelli, Orthogonal Pyramid Tramsform for Image Coding, Visual Communications and Image Processing II Proc. SPIE Vol.645,197．
[2] B.B.Mandelbrot, Les ob jets fractals: forme, hazard et dimension, Flammarion, 1975.
[3] B.B.Mandelbrot, Fractals: form, chance, and dimension, Freeman, 1977.
[4] Y. Fisher, (ed.)Fractal Image Compression: Theory and Application, Springer, 1995.
[5] K.Falconer, Fractal Geometry, Wiley & sons, 1990.
[6] B.B.Mandelbrot, The Fractal Geometry of Nature, freeman, 1983.
[7] J.Huchinson, Fractals and Self Similarity, Indiana Univ. Math. J.30.1981.
[8] M.F. Barnsley,et.al, Iterated function systems and the global construction of fractals, Proc. Roy. Soc. London, Ser. A 399, 1985.
[9] M.F. Bamsley, Fractals Everywhere (2 ed.), Academic Press, 1993.
[10] J.E.Blton, An ergotic theorem for iterated maps, Egotic Theory Dynamical System, 7,1987.
[11] M.F.Barnsley, et. al, The Desktop fractal Design System Handbook, Academic Press, 1992.
[12] M.F. Bamsley, et.al, Fractal image compression, AK Peter, 1993.
[13] Oden, Applied Functional Analysis, 1975.
[14] 顾其均，图象分形编码与压缩技术，《分形几何讲义》，非线性科学研讨班讲义，1994．
[15] A.P. Pentland, Fractal-based description of nature scenes, IEEE Trans. MAMI-6(6), 1984.
[16] 齐东旭，《分形及其计算机生成》，科学出版社，1994．
[17] M.F.Bamsley, A.D.Sloan, A Better W ay to Compress Image Byte, Jan. 1988.
[18] 吴平南，《数据压缩的原理与应用》，电子工业出版社，1995．
[19] M.F. Barnsley ,A.D.Sloan, A Better W ay to Compress Image Byte, Jan. 1988.
[20] A.E.Jacquin, A Novel fractal Block-Coding Technique for Digital Image, Proceedings of ICASSP IEEE International conference on ASSP, Vol. 4 1990.
[21] A.E.Jacquin, Fractal Image Coding: A/Review, Proceedivg of the IEEE Vol.81 No.10 1993.
[22] Y. Fisher, Fractal Image Compression, Fractals Vol.2 No.3 1994.
[23] Y. Fisher, fractal Encoding: Theoy and Application to Digifal Image, Springer Verlag, New York 1994.
[24] E.W. Jacobs ,Y. Fisher, R.D.Boss, Image Compression: A Study of the Itrated Transform Method, Signal Processing Vol.29,1992.
[25] T. Bedford, F.M.Dekking, M.S.Keane, Fractal Image Coding Techniques and Contraction operators, Nieuw Arch. Wisk(4) 10,3,1992.
[26] A.E.Jacquin, Image Coding Based on a Fractal Theoy of Iterated Contractive
Markov Operators, Part I、 II:Theoretical Foundation, Report Math. 91389-016 Georgia Institute of Technology, 1989．
[27] A.e.Jacquin, Fractal Image Coding Based on A Theoy of Iterated Contractive Image Transformafions, IEEE Trans, Image Proessing Vol.1 1992．
[28] H.Lin, A.N.Venetsanopoulos, A Pyramid algorithm for Fast Fractal Image Compression, Proceedings of ICIP. 95 IEEE International Conference on Image Processing 1995．
[29] D.Saupe, R.A.Hamzaoui, A Guided Tour of The Fractal Image Compression Literature, New Directions for Fractal Modeling in Computer Graphics, J.Hart, ACM Siggraph Course Notes 13,1994．
[30] F.M.Dekking, An Inequality for Pairs of Martingales and Its Applications to Fractal Image Coding, Technical Report 95-10 Faculfy of Technical Mathematics and Informatics Delft university of Technology, 1995．
[31] F.M.Dekking, Fractal Image Coding: Some Mathematical Remarks on Its Limits and Its Prospects, Thechnical Report, Faculty of Technical Mathematics and Informatics Delft University of Technology, 1995．
[32] H.Lin, A.N.Venetsanopoulos, Incorporating Nonlinear Contractive functions into fractal Coding, Proceedings of International W orkshop on Intelligent Signal Proessing and Communication System, 1994．
[33] Y.Fisher, S.Menlove, Fractal Encoding With HV Partitions, Fractal Image Compression-Theoy and Application, Springer Verlag, New York, 1994．
[34] F.Davoine, E.Bertin, J.M.Chassery ,From Rigidity to Adaptive Tessellation for Fractal Image Compression: Compression: Comparative Studies, proc. Of IEEE 8th Workshop on Image and Mutidimensional Signd processing 1993．
[35] F.Daroine, E.Bertin, J.M.Chassery ,An Adaptive Partition for Fractal Image Coding, NATO ASI Couf. Fractal Imag Encoding and Analysis, 1995．
[36] L.Thomas ,F.Deravi, Region Based Fractal Image Compression Using Heuristic Search, IEEE Trans, on Image processing Nol.4． No.6 1995．
[37] D.Saupe, M.Ruhl, Evolutionary Fractal Image Compression, Proc. ICIP-96 IEEEE Internation al Conference on Image Processing, 1996．
[38] M.F.Barnsley ,Lecture Notes on Iterated Function System, Proceedings of Symposia in Applired Mathematics Vol.39,1989．
[39] Emmanuel Rousens, Sequence Coding Based on The Fractal Theoy of Iterated Transformations Systems SPIE Vol.2094．
[40] I.Daubechies, Ten lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992．
[41] S.E.Mallat, A Theoy for Multiresolution Signal Decomposition The Wavelet Represantation, IEEE Trans on Pattern Analysis and Machine Intelligencl Vol.11,No.7 1989．
[42] E.H.Adelson and E.Simoncelli, Orthogonal Pyramid Tramsform for Image Coding, Visual Communications and Image Processing II Proc. SPIE Vol.645,197．