论文部分内容阅读
摘要：该文首先介绍了分形图像压缩的基本理论，如迭代函数系统，拼贴定理等。然后重点研究了基于四叉树的分形图像压缩编码算法。最后通过编写代码实现此算法，并与基本的分形图像压缩算法进行试验比较，进行总结。
关键词：分形图像压缩；迭代函数系统；固定分块分形图像压缩；四叉树分形图像压缩
中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)35-2220-03
Based on Quadtree Fractal Image Compression Algorithm for Research and Implementation
JIANG Yu-sheng, SHAO Wei, DING Lan-xin
(College of Communication Engineering, Chongqing University, Chongqing 400044, China)
Abstract: This paper first introduced the basic theory of the fractal image compression ，such as iteration function system(IFS), collage theorem, and so on. And then focus on the Quadtree based on the fractal image compression algorithm. Finally realizes this algorithm through the compilation code, and carries on the experiment with the basic fractal image compression algorithm to compare, carries on the summary.
Key words: fractal image compression; iteration function system; fixed piecemeal fractal image compression; quadtree fractal image compression
1 引言
1973年，曼德勃罗（B.B.Mandelbrot）首次提出了分维和分形几何的设想。由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学[1]。分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。特别随着计算机技术的发展，分形思想和方法在模式识别、自然图像的模拟、信号处理等各个领域都取得了巨大的成功。
1988年，Barnsley对几幅图像进行分形压缩编码，获得了1000：1的压缩比，虽然这只是对特定的图像而言，但足以显示分形技术在图像编码方面的巨大潜力[2]。1990年Jacquin利用图像间的相似性，提出了一种可用计算机完全自动实现的分形图像编码算法，为分形图像编码的研究带来了一次质的飞跃。自Jacquin之后，分形图像编码引起了世界各国研究人员的广泛兴趣和关注，成为目前编码研究的热点。
2 分形图像压缩编码理论
分形图像压缩是一种利用自相识性特点的图像压缩方法。为了达到压缩的目的，Barnsley使用吸引子模型的二维仿射变换描绘原始图像。在分形图像压缩的过程中，他提出迭代函数系统和拼贴定理。目前，这一理论已成为分形图像压缩的理论基础。
压缩映射：变换是指将一个空间上的点根据某种事先定义的法则，使之与另一个空间上的点相对应，变换有时也称为映射。从一个空间x1到另一个空间x2的变换通常记为f :x1→x2。设w:X→X是度量空间(x,d)上的一个映射，其中X∈R2是豪斯道夫距离。如果存在一个常数s(0 不动点定义：如果存在xw∈X，使得w(xw)=xw，则称xw为压缩映射w的不动点。压缩变换存在唯一不动点，且不动点可以通过迭代得到。
压缩映射定理：设w:X→X是完备度量空间(X,d)上的压缩映射，则存在惟一的不动点xw∈X，对任何x∈X，序列{won(x):n=1,2,…}收敛于xw。即 Ax∈X。
迭代函数系统：完备度量空间(X,d)与压缩因子分别为s1,s2,…sn的n个压缩映射wn，构成了一个迭代函数系统(IFS)。其压缩因子为s=max{s1,s2,…sn}，一个IFS可以表示为{X:w1,w2,…,wn}。
拼贴定理：设(X,d)是完备的度量空间，给定集合L∈H(X)及数ε＞0。如果能选取到一个IFS{X:wj,j=1,2,…,n}，其压缩因子为s(0，则有：。A为该IFS的不动点(又称吸引子)。
3 四叉树分形图像压缩编码
根据第二节的定理，可以得出：一幅具有自相似的图像可以由一组压缩变换表示，而这组压缩变换的吸引子就是该图像的编码结果。但是，能将整幅图像进行上述“自身复制”压缩变换w，取决于图像本身的自相似性质 ，并不总是存在。而且，许多图像并不总是单一的景物，比如一副自然风光图，画面中可能有天空的白云，山峦，树木，河流等。这种图像如果有自相似性，一般也基本是分别存在画面内的各个对象自身之中，所以，对于这种图像采用 分形编码就必须先把原图分割成几个不同的对象，然后再对每个对象提取码，而这种分割一般需要人机交互才能完成，而且费时费力，难以实时实现。
1990年，Jacqain 提出了全自动的分形图像压缩算法——固定分块分形图像压缩[2]，该方法以局部的仿射变换代替全局的仿射变换，基于图像的分块，首先把原始图像分割成一个个尺寸为k×k的不重叠方形像块，称为值域块，记为R1,R2,…, ；同时又把原图分割成若干尺寸为L×L的可以重叠的方形D2像块D1,D2,…, ，称为定义域块。规定定义域块的尺寸大于值域块的尺寸，即L>K,一般取L=2K。通过搜索匹配得到图像的 。图1所示为分块分形图像压缩编码系统框图[5]。
固定分块分形图像编码的缺点在于寻找Ri和Di两者的匹配时非常耗时，在图像还原的时候，还将出现“方块效应”，会影响图像的还原质量。
1991年，Fisher 对该方法进行改进，提出了四叉树分形图像编码方法。它具有分块灵活性高，压缩比率高的优点，是目前分形图像压缩编码中的主要方法。下面我们将重点介绍四叉树分形图像编码方法[3-4]。
四叉树方法是一种自适应分块方法。它将图像表示成一棵四叉树，树根就是原图像本身。除叶节点外，树中每个节点均有4个子节点，分别对应于原图像（或图像块）4个象限的子块。
其分割原理如图2所示[6]。
图像自适应分块的目的是将图像合理地划分成不同尺寸的R块，使任意一块都能找到合适的D块与之相应。这样图像中粗糙的部分能以较大的图像块进行变换压缩，提高压缩比；而图像中精细的部分以较小的图像块进行变换压缩，保证较高的图像还原质量。和经典的固定分块分形图像编码相比，四叉树方法能进一步提高压缩比。
为保证图像质量同时减少分块数，一般在分割图像之前，设定四叉树最大和最小深度以及最大允许误差，即设定最小和最大R块尺寸及寻找匹配块标准。用四分法按设定的最小深度级分割图像。针对图像中与该深度级对应的每一方块图像找其最佳匹配块。如找到，则标为R，对应的匹配块记为D，并且不再对该方块进行细分。如某图像方块在指定误差下没有找到最佳匹配块，则把该子块细分成等大小的四块。再对这四个分块分别找其匹配块。该过程不断进行，直到设定的最大深度级。
具体实现步骤如下[7]：
Step 1、将原始图像分成四个大小相同的方块，判断每个方块是否满足一致性标准。
Step 2、设定划分的深度范围，即值域块所允许的最大与最小尺寸。
Step 3、如果满足划分的最小深度范围就不再继续分裂(即使没有达到一致性标准)；否则如果不满足一致性标准就再细分成四个方块，并对细分得到的方块作深度范围和一致性检验。
Step 4、重复Step 3，直到所有的方块都满足一致性标准才结束。
经过以上方法进行分解后，其最终的值域块的集合可能包含多种不同尺寸的方块。虽然从理论上来说，如果块的大小取1×1或2×2或N×N，是可行的，在分形图像压缩中显然是不合适的。因此，在实际中我们常取最小块为4×4，最大块 (N/2)×(N/2)。
4 四叉树分形编码的实现及分析
在本为中，我们根据四叉树分形编码的算法，利用C++Builder6.0编写程序代码，分形编码的流程图如3所示，并将一幅256×256的cat的BMP彩色图像进行试验。试验测试平台：CPU为celeron 1.66G，RAM为1.0G，操作系统为：Windows XP professional。测试图像如图4所示，
我们利用固定分块分形图像压缩编码进行测试结果如图5所示。
原始图像 解码图像 原始图像解码图像
图4 四叉树分形编码测试图像 图5 固定分块分形图像压缩编码测试图像
表1给出了两种不同方法下测试结果的比较：
表1 固定分块与四叉树测试结果的比较
从以上的比较可看出，本文编写的基于四叉树的分形图像压缩程序代码与固定分块的分形图像编码相比，无论从压缩比还是压缩时间和信噪比上，都有了很大的改进，而且从测试图像上可以看出，解码图像的质量也有了很大的改善。
5 结论
虽然基于四叉树的分形图像压缩有了一定的改善，但仍然存在以下缺点：恢复图像中仍然有较为严重的方块效应；在压缩时，运算量较大，压缩时间较长。而造成这种的原因为：没有考虑图像的内容和含义，只进行盲目的方块分割，从而导致较高压缩比时出现严重的方块效应；人眼视觉系统（HVS）没有充分考虑。
根据以上分析，我们可以进行针对性的改进，从而得到更好的压缩效果。相信经过不断的努力，基于分形的图像压缩方法将有着更好的发展前景。
参考文献：
[1] Barnsley M F,Hurd L P.Fractal image compression[M].Wellesley:AK Peters Ltd,1993.
[2] Jacquin A E.image coding: a review[J].Proceeding of the IEEE,1993,81(10):1451-1465.
[3] Fisher Y.Fractal image compression[M].Fractals,1994.
[4] Fisher Y.Fractal image compression theory and appplication[M].Springer-Verlag,NewYork,1995.
[5] 张春田,苏育挺,张静.数字图像压缩编码[M].北京:清华大学出版社,2006
[6] 董云朝,陈贺新.基于四叉树的自适应门限分形图像IFS压缩方法[J].中国图像图形学报,2000,5(11).
[7] 郑运平,陈传波.一种基于新型四叉树的快速分形图像压缩算法[J].小型微型计算机系统,2007,28(8).
关键词：分形图像压缩；迭代函数系统；固定分块分形图像压缩；四叉树分形图像压缩
中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)35-2220-03
Based on Quadtree Fractal Image Compression Algorithm for Research and Implementation
JIANG Yu-sheng, SHAO Wei, DING Lan-xin
(College of Communication Engineering, Chongqing University, Chongqing 400044, China)
Abstract: This paper first introduced the basic theory of the fractal image compression ，such as iteration function system(IFS), collage theorem, and so on. And then focus on the Quadtree based on the fractal image compression algorithm. Finally realizes this algorithm through the compilation code, and carries on the experiment with the basic fractal image compression algorithm to compare, carries on the summary.
Key words: fractal image compression; iteration function system; fixed piecemeal fractal image compression; quadtree fractal image compression
1 引言
1973年，曼德勃罗（B.B.Mandelbrot）首次提出了分维和分形几何的设想。由于不规则现象在自然界是普遍存在的，因此分形几何又称为描述大自然的几何学[1]。分形几何建立以后，很快就引起了许多学科的关注，这是由于它不仅在理论上，而且在实用上都具有重要价值。特别随着计算机技术的发展，分形思想和方法在模式识别、自然图像的模拟、信号处理等各个领域都取得了巨大的成功。
1988年，Barnsley对几幅图像进行分形压缩编码，获得了1000：1的压缩比，虽然这只是对特定的图像而言，但足以显示分形技术在图像编码方面的巨大潜力[2]。1990年Jacquin利用图像间的相似性，提出了一种可用计算机完全自动实现的分形图像编码算法，为分形图像编码的研究带来了一次质的飞跃。自Jacquin之后，分形图像编码引起了世界各国研究人员的广泛兴趣和关注，成为目前编码研究的热点。
2 分形图像压缩编码理论
分形图像压缩是一种利用自相识性特点的图像压缩方法。为了达到压缩的目的，Barnsley使用吸引子模型的二维仿射变换描绘原始图像。在分形图像压缩的过程中，他提出迭代函数系统和拼贴定理。目前，这一理论已成为分形图像压缩的理论基础。
压缩映射：变换是指将一个空间上的点根据某种事先定义的法则，使之与另一个空间上的点相对应，变换有时也称为映射。从一个空间x1到另一个空间x2的变换通常记为f :x1→x2。设w:X→X是度量空间(x,d)上的一个映射，其中X∈R2是豪斯道夫距离。如果存在一个常数s(0
压缩映射定理：设w:X→X是完备度量空间(X,d)上的压缩映射，则存在惟一的不动点xw∈X，对任何x∈X，序列{won(x):n=1,2,…}收敛于xw。即
迭代函数系统：完备度量空间(X,d)与压缩因子分别为s1,s2,…sn的n个压缩映射wn，构成了一个迭代函数系统(IFS)。其压缩因子为s=max{s1,s2,…sn}，一个IFS可以表示为{X:w1,w2,…,wn}。
拼贴定理：设(X,d)是完备的度量空间，给定集合L∈H(X)及数ε＞0。如果能选取到一个IFS{X:wj,j=1,2,…,n}，其压缩因子为s(0
3 四叉树分形图像压缩编码
根据第二节的定理，可以得出：一幅具有自相似的图像可以由一组压缩变换表示，而这组压缩变换的吸引子就是该图像的编码结果。但是，能将整幅图像进行上述“自身复制”压缩变换w，取决于图像本身的自相似性质 ，并不总是存在。而且，许多图像并不总是单一的景物，比如一副自然风光图，画面中可能有天空的白云，山峦，树木，河流等。这种图像如果有自相似性，一般也基本是分别存在画面内的各个对象自身之中，所以，对于这种图像采用 分形编码就必须先把原图分割成几个不同的对象，然后再对每个对象提取码，而这种分割一般需要人机交互才能完成，而且费时费力，难以实时实现。
1990年，Jacqain 提出了全自动的分形图像压缩算法——固定分块分形图像压缩[2]，该方法以局部的仿射变换代替全局的仿射变换，基于图像的分块，首先把原始图像分割成一个个尺寸为k×k的不重叠方形像块，称为值域块，记为R1,R2,…, ；同时又把原图分割成若干尺寸为L×L的可以重叠的方形D2像块D1,D2,…, ，称为定义域块。规定定义域块的尺寸大于值域块的尺寸，即L>K,一般取L=2K。通过搜索匹配得到图像的 。图1所示为分块分形图像压缩编码系统框图[5]。
固定分块分形图像编码的缺点在于寻找Ri和Di两者的匹配时非常耗时，在图像还原的时候，还将出现“方块效应”，会影响图像的还原质量。
1991年，Fisher 对该方法进行改进，提出了四叉树分形图像编码方法。它具有分块灵活性高，压缩比率高的优点，是目前分形图像压缩编码中的主要方法。下面我们将重点介绍四叉树分形图像编码方法[3-4]。
四叉树方法是一种自适应分块方法。它将图像表示成一棵四叉树，树根就是原图像本身。除叶节点外，树中每个节点均有4个子节点，分别对应于原图像（或图像块）4个象限的子块。
其分割原理如图2所示[6]。
图像自适应分块的目的是将图像合理地划分成不同尺寸的R块，使任意一块都能找到合适的D块与之相应。这样图像中粗糙的部分能以较大的图像块进行变换压缩，提高压缩比；而图像中精细的部分以较小的图像块进行变换压缩，保证较高的图像还原质量。和经典的固定分块分形图像编码相比，四叉树方法能进一步提高压缩比。
为保证图像质量同时减少分块数，一般在分割图像之前，设定四叉树最大和最小深度以及最大允许误差，即设定最小和最大R块尺寸及寻找匹配块标准。用四分法按设定的最小深度级分割图像。针对图像中与该深度级对应的每一方块图像找其最佳匹配块。如找到，则标为R，对应的匹配块记为D，并且不再对该方块进行细分。如某图像方块在指定误差下没有找到最佳匹配块，则把该子块细分成等大小的四块。再对这四个分块分别找其匹配块。该过程不断进行，直到设定的最大深度级。
具体实现步骤如下[7]：
Step 1、将原始图像分成四个大小相同的方块，判断每个方块是否满足一致性标准。
Step 2、设定划分的深度范围，即值域块所允许的最大与最小尺寸。
Step 3、如果满足划分的最小深度范围就不再继续分裂(即使没有达到一致性标准)；否则如果不满足一致性标准就再细分成四个方块，并对细分得到的方块作深度范围和一致性检验。
Step 4、重复Step 3，直到所有的方块都满足一致性标准才结束。
经过以上方法进行分解后，其最终的值域块的集合可能包含多种不同尺寸的方块。虽然从理论上来说，如果块的大小取1×1或2×2或N×N，是可行的，在分形图像压缩中显然是不合适的。因此，在实际中我们常取最小块为4×4，最大块 (N/2)×(N/2)。
4 四叉树分形编码的实现及分析
在本为中，我们根据四叉树分形编码的算法，利用C++Builder6.0编写程序代码，分形编码的流程图如3所示，并将一幅256×256的cat的BMP彩色图像进行试验。试验测试平台：CPU为celeron 1.66G，RAM为1.0G，操作系统为：Windows XP professional。测试图像如图4所示，
我们利用固定分块分形图像压缩编码进行测试结果如图5所示。
原始图像 解码图像 原始图像解码图像
图4 四叉树分形编码测试图像 图5 固定分块分形图像压缩编码测试图像
表1给出了两种不同方法下测试结果的比较：
表1 固定分块与四叉树测试结果的比较
从以上的比较可看出，本文编写的基于四叉树的分形图像压缩程序代码与固定分块的分形图像编码相比，无论从压缩比还是压缩时间和信噪比上，都有了很大的改进，而且从测试图像上可以看出，解码图像的质量也有了很大的改善。
5 结论
虽然基于四叉树的分形图像压缩有了一定的改善，但仍然存在以下缺点：恢复图像中仍然有较为严重的方块效应；在压缩时，运算量较大，压缩时间较长。而造成这种的原因为：没有考虑图像的内容和含义，只进行盲目的方块分割，从而导致较高压缩比时出现严重的方块效应；人眼视觉系统（HVS）没有充分考虑。
根据以上分析，我们可以进行针对性的改进，从而得到更好的压缩效果。相信经过不断的努力，基于分形的图像压缩方法将有着更好的发展前景。
参考文献：
[1] Barnsley M F,Hurd L P.Fractal image compression[M].Wellesley:AK Peters Ltd,1993.
[2] Jacquin A E.image coding: a review[J].Proceeding of the IEEE,1993,81(10):1451-1465.
[3] Fisher Y.Fractal image compression[M].Fractals,1994.
[4] Fisher Y.Fractal image compression theory and appplication[M].Springer-Verlag,NewYork,1995.
[5] 张春田,苏育挺,张静.数字图像压缩编码[M].北京:清华大学出版社,2006
[6] 董云朝,陈贺新.基于四叉树的自适应门限分形图像IFS压缩方法[J].中国图像图形学报,2000,5(11).
[7] 郑运平,陈传波.一种基于新型四叉树的快速分形图像压缩算法[J].小型微型计算机系统,2007,28(8).