分形图像压缩算法的研究
|
摘要
分形图像压缩方法是一种很有前途的图像编码方法,以其新颖的思想、高压缩比、分辨率无关性和快速解码等优点而广受关注。本文研究了分形的基本理论以及分形图像压缩的基本方法。首先,对图像压缩的原理和方法做了简要回顾;接着,就分形几何学的基本理论、分形用于图像压缩编码所必需的一些基本数学知识以及分形编码的基本原理、基本分形算法的描述与实现作了介绍;最后,针对分形编码算法中存在的问题提出了两种分形图像压缩的新方法,通过仿真实验,说明了两种新方法的有效性。
本论文的创新点如下:
(1)提出了分级匹配的分形图像压缩方法。与经典的Fisher方法相比,该方法通过去掉定义域块的8种等距变换和采用分级分类的匹配方式,压缩了域池,大大提高了匹配的速度和精度,同时图像的压缩比也有所提高。通过计算机编程对该算法进行仿真,实验结果表明,对于6幅复杂性不同的标准测试图像,本方案确实能够从解码图像质量、压缩比和编码速度等方面改进传统的分形图像压缩方法,达到了既加快编码速度又提高编码图像质量的目的。
(2)提出了多维分形图像压缩的方法。该方法打破了传统的定义域块边长为值域块边长两倍的概念,采用多个定义域池,定义域块的边长分别为值域块边长的两倍、三倍、四倍、五倍大小,匹配时依次搜索各个域池寻找最佳匹配块。大量实验数据表明,该方法与Y.Fisher的分形图像压缩方法相比具有一定优势,在保证重建图像质量的同时缩短了编码时间且提高了压缩比。
Fractal image coding is a very promising compression technique. It has been paid great attention because of its novelty, high compression rate, resolution independence and rapid decoding. This paper mainly studies the basic theory of fractal and fractal image compression methods. Firstly, the article reviewed the basic principles and methodologies for image compression. Then we introduce the principles of fractal geometry and the mathematical foundation necessary for fractal image compression. After that the LIFS fractal image compression scheme proposed by Jacquin is discussed in detail. Finally two new methods of fractal image compression are proposed after some discussion. Experiment results show that these algorithms and methods are useful and valid.
The main contributions of this dissertation are as follows:
(1) Introduce the classical fractal image compression method proposed by Fisher, then propose a new algorithm based on Fisher's method, so named the Hierarchical Matching Encoding Scheme (HMES). Firstly there are no rotations and flips on domain blocks in this method, which compress the domain pool consequently. Secondly a hierarchical classification matching scheme is proposed to classify the domain blocks more reasonably. Experimental results on standard gray scale image show that the hierarchical classification matching scheme yields much better performance over other classification matching scheme.
(2) A multi-dimensional fractal image compression is presented. In this method we adopt several domain pools of different sizes other than the traditional domain pool. The size of the domain blocks are twice, three times, four times, five times of the ranges separately. In the matching process, the search is conducted in each domain pool. Experimental results show that this method has advantage over Fisher's algorithm; it reduces the encoding time while the compression ratio and PSNR are both increased.
本论文的创新点如下:
(1)提出了分级匹配的分形图像压缩方法。与经典的Fisher方法相比,该方法通过去掉定义域块的8种等距变换和采用分级分类的匹配方式,压缩了域池,大大提高了匹配的速度和精度,同时图像的压缩比也有所提高。通过计算机编程对该算法进行仿真,实验结果表明,对于6幅复杂性不同的标准测试图像,本方案确实能够从解码图像质量、压缩比和编码速度等方面改进传统的分形图像压缩方法,达到了既加快编码速度又提高编码图像质量的目的。
(2)提出了多维分形图像压缩的方法。该方法打破了传统的定义域块边长为值域块边长两倍的概念,采用多个定义域池,定义域块的边长分别为值域块边长的两倍、三倍、四倍、五倍大小,匹配时依次搜索各个域池寻找最佳匹配块。大量实验数据表明,该方法与Y.Fisher的分形图像压缩方法相比具有一定优势,在保证重建图像质量的同时缩短了编码时间且提高了压缩比。
Fractal image coding is a very promising compression technique. It has been paid great attention because of its novelty, high compression rate, resolution independence and rapid decoding. This paper mainly studies the basic theory of fractal and fractal image compression methods. Firstly, the article reviewed the basic principles and methodologies for image compression. Then we introduce the principles of fractal geometry and the mathematical foundation necessary for fractal image compression. After that the LIFS fractal image compression scheme proposed by Jacquin is discussed in detail. Finally two new methods of fractal image compression are proposed after some discussion. Experiment results show that these algorithms and methods are useful and valid.
The main contributions of this dissertation are as follows:
(1) Introduce the classical fractal image compression method proposed by Fisher, then propose a new algorithm based on Fisher's method, so named the Hierarchical Matching Encoding Scheme (HMES). Firstly there are no rotations and flips on domain blocks in this method, which compress the domain pool consequently. Secondly a hierarchical classification matching scheme is proposed to classify the domain blocks more reasonably. Experimental results on standard gray scale image show that the hierarchical classification matching scheme yields much better performance over other classification matching scheme.
(2) A multi-dimensional fractal image compression is presented. In this method we adopt several domain pools of different sizes other than the traditional domain pool. The size of the domain blocks are twice, three times, four times, five times of the ranges separately. In the matching process, the search is conducted in each domain pool. Experimental results show that this method has advantage over Fisher's algorithm; it reduces the encoding time while the compression ratio and PSNR are both increased.
引文
[1]B B Mandelbrot.The fractal geometry of nature[M].New York:Freeman,1983:12-19
[2]M F Bamsley,A D Sloan.A better way to compress image byte.New York:GORDEN,1998:215-223
[3]C S Tong,M Pi.Fast fractal image encoding based on adaptive search.IEEE Transactions on Image Processing,2001,9(10):1269-1277
[4]Ramirez,A M Sanchez,A D Aranda,M.L,Pineda,J V.An architecture for fractal image compression using quad-tree multi-resolution.ISCS04,2004,5(2):897-900
[5]Ponomarenko,N N Egiazarian,K Lukin,V V Astola,J T.Cascade fractal image compression and its modification.ICASSP'05,2005,4(2):361-364
[6]洪喜勇,陈贺新.广义收敛的分形图像压缩编码.电子学报,2001,6(6):842-845
[7]何传江,蒋海军,黄席樾.快速分形图像编码的一种特征方法[J].电工电子学报,2004,32(11):1864-1867
[8]Frank Davoine,Marc Antonin,Jean Marc Chassery.Fractal image compression based on delaunay triangulation and vector quantization[J].IEEE Trans.Image Processing,1996,5(2):338-346
[9]Thomas L.Region-based fractal image compression using heuristic search[J].IEEE Transaction on Image Processing,1995,4(6):832-838
[10]颜飞翔,蔡宣平,孙茂印.快速覆盖式分形压缩算法[J].中国图像图形学报,1997,2(9):589-592
[11]David J Jackson,Wagdy Mahmoud,William A Stapleton.Faster fractal image compression using quantree recomposition[J].Image and Vision Computing,1997,15(10):759-767
[12]Jacobs E W,Fisher Y,Boss Y D.Image compression:A study of the iterated transform method[J].Signal Processing,1992,29(3):251-263
[13]Jacquin A E.Image coding based on fractal theory of iterated contractive image transformations[J].IEEE Tran.Image Processing,1992,1(1):18-30
[14]秦峰,吴征.分区IFS图像压缩编码[J].通讯学报,1997,18(5):1-7
[15]Y Fisher.Fractal image compression theory and application[M].New York:Springer-Verlag,1995:1-77
[16]E W Jacobs,Y Fisher,R D Boss.Image compression:a study of the iterated transform method.Signal Processing 29,1992:251-263
[17]Hurtgen B,Stiller C.Fast hierarchical codebook search for fractal coding of still image[M].Berlin:PACSMA,1993:90-97
[18]Saupe D.Fractal image compression by multi-dimensional nearest neighbor search[M].UT:IEEE Computer Society Press,1995:17-24
[19]Chen Y,Zhang F.Feature difference classification method in fractal image coding[J].Proc IEEE DCC,2001,32(2):56-59
[20]G Vines,M H Hayes.Adaptive IFS image coding with proximity maps.In Proceedings of IEEE ICASSP-93,1993,54(1):349-352
[21]Polvere M,Nappi M.A feature vector technique for fast fractal image coding.University of Salerno,1998,12(2):34-49
[22]王学军.基于边缘提取的分形图像编码方法.中国图像图形学报.2001,6(4):325-328
[23]何佳,刘政凯.基于DCT变换的快速分形编码方法.电子学报.2001,29(6):748-750
[24]狄红卫,钟金刚.基于色度矢量与亮度分离的彩色图像分形编码.计算机工程与应用,2001,7(1):20-22
[25]Venkata Rama Prasad,Vaddella Ramesh Babu,Inampudi.Adaptive gray level difference to speed up fractal image compression.ICSCN-07 IEEE International Conference,2007:253-258
[26]D Saupe,M Ruthl.Evolutionary fractal image compression.Proc ICIP-96 IEEE International Conference on IP,1996:187-195
[27]A E Jacquin.Fractal image coding:A Review.Proceedings of the IEEE,1993,81(10):1451-1465
[28]M Gharavr,Alkhansari,T S Huang.Fractal based techniques for a generalized image coding method.Proc Of IEEE ICIP,1994,3:223-226
[29]沈建军,涂丹.基于矢量量化的图像分形压缩编码.中国图像图形学报,1999,4(5):414-417
[30]Y.Zhao,B Yuan.Image compression using fractals and discrete cosine transform.Electronics Letters,1994,30(6):107-112
[31]张元亮,郑南宁.基于感知度量的分形编码.中国图像图形学报,1998,3(9):721-726
[32]谢鑫,马争鸣.小波分形混合图像编码.中国图像图形学报,2000(9):716-724
[33]Roberto Rinaldo,Giancarlo Calvagno.Image coding by block prediction of multiresolution subimages.IEEE Trans on IP,1995,4(7):141 - 145
[34]陈衍仪.图像压缩的分形理论和方法.北京:国防工业出版社,1997:24-47
[35]吴敏金.分形信息导论.上海:上海科学技术文献出版社,1994:32-44
[36]K J Falconer.Fractal Geometry:Mathematical Foundations and Applications.New York:Chichester John Wiley and Sons,1990:33-45
[37]张石生.不动点理论及应用.重庆:重庆出版社,1984:76-87
[38]Y Tang,何传江,X Y Zhang.A fractal approximation algorithm for inverse initial-value problems of nonlinear differential equation,Journal Chongqing University,2003,Vol.2:32-37
[2]M F Bamsley,A D Sloan.A better way to compress image byte.New York:GORDEN,1998:215-223
[3]C S Tong,M Pi.Fast fractal image encoding based on adaptive search.IEEE Transactions on Image Processing,2001,9(10):1269-1277
[4]Ramirez,A M Sanchez,A D Aranda,M.L,Pineda,J V.An architecture for fractal image compression using quad-tree multi-resolution.ISCS04,2004,5(2):897-900
[5]Ponomarenko,N N Egiazarian,K Lukin,V V Astola,J T.Cascade fractal image compression and its modification.ICASSP'05,2005,4(2):361-364
[6]洪喜勇,陈贺新.广义收敛的分形图像压缩编码.电子学报,2001,6(6):842-845
[7]何传江,蒋海军,黄席樾.快速分形图像编码的一种特征方法[J].电工电子学报,2004,32(11):1864-1867
[8]Frank Davoine,Marc Antonin,Jean Marc Chassery.Fractal image compression based on delaunay triangulation and vector quantization[J].IEEE Trans.Image Processing,1996,5(2):338-346
[9]Thomas L.Region-based fractal image compression using heuristic search[J].IEEE Transaction on Image Processing,1995,4(6):832-838
[10]颜飞翔,蔡宣平,孙茂印.快速覆盖式分形压缩算法[J].中国图像图形学报,1997,2(9):589-592
[11]David J Jackson,Wagdy Mahmoud,William A Stapleton.Faster fractal image compression using quantree recomposition[J].Image and Vision Computing,1997,15(10):759-767
[12]Jacobs E W,Fisher Y,Boss Y D.Image compression:A study of the iterated transform method[J].Signal Processing,1992,29(3):251-263
[13]Jacquin A E.Image coding based on fractal theory of iterated contractive image transformations[J].IEEE Tran.Image Processing,1992,1(1):18-30
[14]秦峰,吴征.分区IFS图像压缩编码[J].通讯学报,1997,18(5):1-7
[15]Y Fisher.Fractal image compression theory and application[M].New York:Springer-Verlag,1995:1-77
[16]E W Jacobs,Y Fisher,R D Boss.Image compression:a study of the iterated transform method.Signal Processing 29,1992:251-263
[17]Hurtgen B,Stiller C.Fast hierarchical codebook search for fractal coding of still image[M].Berlin:PACSMA,1993:90-97
[18]Saupe D.Fractal image compression by multi-dimensional nearest neighbor search[M].UT:IEEE Computer Society Press,1995:17-24
[19]Chen Y,Zhang F.Feature difference classification method in fractal image coding[J].Proc IEEE DCC,2001,32(2):56-59
[20]G Vines,M H Hayes.Adaptive IFS image coding with proximity maps.In Proceedings of IEEE ICASSP-93,1993,54(1):349-352
[21]Polvere M,Nappi M.A feature vector technique for fast fractal image coding.University of Salerno,1998,12(2):34-49
[22]王学军.基于边缘提取的分形图像编码方法.中国图像图形学报.2001,6(4):325-328
[23]何佳,刘政凯.基于DCT变换的快速分形编码方法.电子学报.2001,29(6):748-750
[24]狄红卫,钟金刚.基于色度矢量与亮度分离的彩色图像分形编码.计算机工程与应用,2001,7(1):20-22
[25]Venkata Rama Prasad,Vaddella Ramesh Babu,Inampudi.Adaptive gray level difference to speed up fractal image compression.ICSCN-07 IEEE International Conference,2007:253-258
[26]D Saupe,M Ruthl.Evolutionary fractal image compression.Proc ICIP-96 IEEE International Conference on IP,1996:187-195
[27]A E Jacquin.Fractal image coding:A Review.Proceedings of the IEEE,1993,81(10):1451-1465
[28]M Gharavr,Alkhansari,T S Huang.Fractal based techniques for a generalized image coding method.Proc Of IEEE ICIP,1994,3:223-226
[29]沈建军,涂丹.基于矢量量化的图像分形压缩编码.中国图像图形学报,1999,4(5):414-417
[30]Y.Zhao,B Yuan.Image compression using fractals and discrete cosine transform.Electronics Letters,1994,30(6):107-112
[31]张元亮,郑南宁.基于感知度量的分形编码.中国图像图形学报,1998,3(9):721-726
[32]谢鑫,马争鸣.小波分形混合图像编码.中国图像图形学报,2000(9):716-724
[33]Roberto Rinaldo,Giancarlo Calvagno.Image coding by block prediction of multiresolution subimages.IEEE Trans on IP,1995,4(7):141 - 145
[34]陈衍仪.图像压缩的分形理论和方法.北京:国防工业出版社,1997:24-47
[35]吴敏金.分形信息导论.上海:上海科学技术文献出版社,1994:32-44
[36]K J Falconer.Fractal Geometry:Mathematical Foundations and Applications.New York:Chichester John Wiley and Sons,1990:33-45
[37]张石生.不动点理论及应用.重庆:重庆出版社,1984:76-87
[38]Y Tang,何传江,X Y Zhang.A fractal approximation algorithm for inverse initial-value problems of nonlinear differential equation,Journal Chongqing University,2003,Vol.2:32-37