当前位置:众信范文网 >专题范文 > 公文范文 > 分形图像压缩技术研究与进展

分形图像压缩技术研究与进展

时间:2022-10-21 12:50:04 来源:网友投稿

摘要:利用图像的自相似性,分形图像压缩具有较高的压缩比,并且具有解码速度快、与分辨率无关的优点。该文对分形图像压缩所涉及到的基本原理、方法及存在的问题进行了讨论,并对目前的研究人对分形图像压缩方法的改进做了总结

关键词:分形;函数迭代系统;图像压缩

中图分类号:TP317.4文献标识码:A 文章编号:1009-3044(2011)23-5706-03

The Research of the Advance in Fractal Image Compression Technology

ZHANG Jing-jie, JIANG Dong, WU Yan-min, YU Kai-yun, XU Ye-fei

(Mathematics ,physics and Information Engineering College, Jiaxing University, Jiaxing 314001,China)

Abstract: Use of the images self-similarities, fractals image compression has the advantage of fast decoding and high compression ratio. This paper discuss the principle , method and main drawback of this technique and summarize the improved fractals image compression method.

Key words: fractals image; iterated function system(IFS); image compression

1 分形介绍

在1973年,Mandelbrot首次提出了分维和分形几何的设想,并提出了“分形”的概念 [1]。目前,分形还没有一个严格统一的定义,但它应该具有以下典型性质[2]: 1)分形集都具有任意小尺度下的比例细节,或者说它具有精细的结构。2)分形不能用传统的语言来描述,它既不是满足某些条件的点的轨迹,也不是某些简单方程的解集。3)分形具有某种自相似的形式,可以是近似的自相似或统计的自相似。4)一般来说,分形集的分形维数严格大于它相应的拓扑维数。5)在大多数令人感兴趣的情形下,分形集由非常简单的方法定义,可以由变换迭代产生。

利用图像的局部自相似性,分形编码技术在艺术、建筑设计、地理等方面得到了很大的应用。

2 分形编码的数学基础[6]

2.1 压缩映象原理

设(x,d)是完备度量空间,f:X→X是x上的一个压缩映射。如果存在一个常数α∈[0,1],对于任意的x,y∈X,d(f(x),f(y)) ≤a×d(x,y)都成立,则度量空间 (X,d)上的映射f称为压缩的,并且f存在唯一不动点x∈X,使得 。 f称为(X,d)上的压缩映射,α为压缩因子。

2.2 拼贴定理

设(X,d)是一个完备度量空间,f:X→X是压缩因子为α∈[0,1]是的压缩映射,则不动点x∈X满足d(x,x") ≤d(x,f(x))/(1-α)。

拼贴定理告诉我们,对于一个给定的图像,如果我们能找到一组压缩变换f,使得给定图像与其压缩变换后的映像相似,那么这组压缩变换f的不动点就可以看成给定图像。

2.3 迭代函数系统

一个迭代函数系统(IFS)是由完备度量空间x及其上的一组压缩变换(wi,i=1,2,K,N)构成的,记为{X;wi,i=1,2, …,N}。定义变换w为

迭代函数系统可以对任意图形进行初始迭代,最终得到的图像有一个特点,就是得到的最终图像会很相似,即吸引子A(整体)和wi(A)(部分)具有相似性。

3基本分形编码/解码算法

目前的分形自动压缩算法是由A.E Jacqain最先提出的[5],对分形图像压缩方法的实用化起了奠基的作用。Jacqain基本分形编码算法的主要步骤是:

1) 图像分割:首先把大小为N×N的原始图像分割成n个互不相交的值域块Ri(简称R块),且A=∪ni=1Ri。

2) 分割码本:把图像分割成若干相互重叠的、大小为D×D、步长为δ的定义域块Dj(简称 块)。一般D块的大小是R块的两倍。再把每个定义域块收缩值域块大小相同的块,构成虚拟码本Ω。

3) 等距变换:对虚拟码本中的每一个Dj块进行8个等距变换tk:恒等变换、垂直中轴的对称反射、水平中轴的对称反射、主对角线的对称反射、次主对角线的对称反射、块中心逆时针旋转90°、块中心逆时针旋转180°、块中心逆时针旋转270°。

4) 编码阶段:对每个定义域块Ri,通过最小二乘法计算各变换参数在虚拟码本Ω中查找一个最佳匹配块Dm(i),计算Dm(i)"=s×tk(Dm(i))+o×1与Ri之间的误差,取最小。

其中,o=R"-s×D",s=<R-R"×I,D-D"×I>‖D-D"×I‖2,<·,·>表示欧氏内积:;误差度量采用均方误差(MSE,Mean Square Error)计算:。

5) 参数量化:每个Ri的分形码都涉及到四个参数{k,m(i),si,oi},参数k,m(i)分别指等距变换和最佳匹配块的序号,是不能量化的,只有后两个参数才需要量化。最后,输出经过量化后的分形码,得到分形编码文件。

6) 解码过程相对比较简单,是编码过程的一个逆过程。根据压缩编码提供的参数{k,m(i),si,oi},在解码初始图像中读取与每个Ri块最近似的Dm(i)块,计算Dm(i)",反向拼贴形成一次迭代的图像,做为下次解码的初始图像,直到重构图像达到要求。

4 基本分形解码算法的优缺点

从理论上看,基本分形编码/解码算法的优点是解码速度比编码速度快得多,且具有分辨率无关性。对于一些对解码速度有较高要求的场合,就可以充分发挥分形解码速度快的优点。基本分形编码/解码算法的缺点是编码时间过长,且当图像的压缩比较小的时候,图像的失真度变大,块效应比较明显。

5 分形编码改进

5.1 加快编码速度

虚拟码本对编码时间和编码质量都有很大的影响,所以选择正确的虚拟码本能够更好地实现图像的编码。如果虚拟码本越大,匹配搜索的范围就越大,搜索到最优匹配块的可能性就越大,但是编码时间会更长。

5.1.1 图像块分类

研究人员通过大量实验发现,与 块相匹配的 块之间存在某种特征的相似性。因此,为了缩短搜索时间,在匹配之前按照图像的某种特征,将定义域和值域块进行分类,匹配时只在同一类中进行搜索比较。这样在不降低图像质量的前提下,大大提高了编码速度。

文献[3]中使用了一种根据几何视觉特性分类 块的方案的图像块分类方法。在这种分类方法中, 块被区分为三种不同的类型:平滑块、边缘块和中值块。其中,平滑块是亮度变化不明显的图像块,边缘块是亮度急剧变化的图像块(常常是含有边缘的图像块),中值块的亮度变化介于平滑块和边缘块之间,它们主要是包含纹理的图像块。边缘块又进一步划分为两类:简单块和混合边缘块。对亮度变化很小的平滑块采用均一值代替,以避免搜索匹配过程。E.W.Jacobs、Y.Fisher 和R.D.Bossr 根据图像块的灰度平均值将子块分成3大类,同时又根据图像块灰度的方差大小将每一类分成24小类,即共分成72类[4]。

目前,大多数图像块分类研究都是基于视觉特性、亮度均值、方差等。目前也有很多研究者提出了很多种特征向量提取的方法,其原理和方法基本相同。另外,还有人引入遗传、粒子群、K均值等智能算法,实现模糊分类。

5.1.2 邻域搜索

文献[10]分析了值域块和它的最匹配的定义域块间的距离,发现值域块的最匹配的定义域块大多数在值域块的附近。不少研究人员在这方面也做了一些工作,如以值域块为邻域中心,搜索其所在行及其邻近两行所确定的区域[7]或是仅搜索值域块和它的周围的八个邻域块[8]。

5.2 提高编码质量

5.2.1 改进图像分割方案

起初,Jacquin使用的是固定大小的方块分割。在这种分割方案中,当分块尺寸较大时,虽然压缩比较高,但图像质量较差,块效应比较明显;当分块尺寸较小时,编码质量较高,但编码时间长,压缩比较低。随后,Jacquin改进了分割方案,使用自适应二次分割方案[9]:先将图像块分成8×8大小进行编码,再将图像块分成四个4×4子块,分别计算误差,如果误差超过预定阈值,则对子块进行编码。此种方法在提高编码质量的同时又避免压缩比下降太多。

之后,Y.Fisher等人又推广了Jacquin的改进方案,提出了四叉树分割方案[6]:先把整幅图像看成一个单一的父块(即四叉树的树根),当拼贴误差超过预定阀值时,图像被等分成四个子块(四叉树树根的四个子结点)。再以相同的方式依次考虑四个子块的每一块,当拼贴误差超过预定阀值时,新父块又被等分成四个子块,继续这个过程直至中止条件满足。四叉树分割方案是目前比较实用的压缩方法,被很多研究者采用。

上述方法都是将图像分成方块,这种分割并不能很好的体现图像的自相似性,为此研究者们又提出了 分割和多边形(三角形、六边形、菱形等)分割等分割方案,并结合四叉树分割方案的思想,通过设置阈值实现自适应的图像的非固定大小的划分,以加快图像编码速度提高图像编码质量。

5.2.2 提高灰度的逼近能力

在分形编码中,常用的仿射变换如前,其灰度值的逼近式为:w(z)=pz+g,这是一个简单的线性逼近,逼近能力有限。有研究者将灰度的逼近变为w(z)=t(z),t(z)可以为任意形式,可以为二次以上的多项式,有效提高了编码效果,改进图像质量[11]。M. Gharavi-Alkhansari 和T.S.Huang 用几个定义域子块的线性组合来逼近某一值域子块,提高逼近能力[12]。

5.2.3 后期处理

分形图像压缩的一个常见问题是块效应。消除块效应的一个常用方法是后处理,一般采用2:1加权平均或3:2:1加权平均均法。若要提高处理精度,亦可采用幂指数加权平均算法和选择性加权平均算法,但在处理速度方面还有待加强。另外,还有研究者还通过对解码图像与原图像之间误差图像进行二次编码以提高图像质量。

5.3 结合其他技术实现混合编码

分形的本质特征是自相似性, 但自然图像的自相似性不强, 因此典型的分形图像编码方法难以达到最初的高压缩比的理想状态。目前,很多研究者利用其他一些编码方法(如小波、变换编码、矢量量化、预测编码等)来增强图像的自相似性,再与分形编码结合,进行混合编码,已经取得巨大成功[10]。目前研究得最多种混合编码方案是分形与小波变换、分形与DCT相结合的压缩方法。

5.3.1 小波与分形编码

小波变换是将图像信号分解为具有不同尺度和空间选择性的系列子带图像,这些不同分辨率的子带图像之间存在一定的相似性,则可通过分形变换来描述,从而最大限度地发挥小波变换和分形编码的优势。 编码过程是一个由小波树的顶部开始一层层向下预测其它系数的过程,这个自上至下、由粗到细的预测过程可通过分形编码来完成。

基于相邻子带图像相似性的分形预测图像编码的核心算法就是用低分辨率的子带图像来预测同方向高一级分辨率的子带图像 ,其编码步骤大致如下:对图像进行多级小波分解, 以得到不同方向和不同分辨率的各个子带图像;最低分辨率的子带图像( 如图1中的LL1、LH1、HL1和HH1 ) 是分形预测的基础,采用无失真或失真较少的图像编码方法来编码;利用低分辨率的子带图像( 如图1 中的LHi、HLi和HHi,i≥1) , 对同方向高一级分辨率的子带图像( 如图1 中的LHi+1、HLi+1和HHi+1) 进行分形预测编码;图像解码时, 先恢复最低分辨率的子带图像, 然后, 按照从低到高的次序, 逐级分形预测高分辨率的各个子带图像。

5.3.2 DCT与分形编码

目前有两种结合DCT变换的编码方法:基于DCT补偿的分形编码方法和基于DCT变换系数的分形编码方法。

基于DCT补偿的分形编码先是对同一幅图像中值域块到定义域块进行匹配,如果图像的质量没有达到要求,则对经过分形编码后还没达到要求的误差部分再用DCT 进行编码和补偿。对误差和量化因子两个量的控制使图像的质量和压缩比得到了较好的调节。在解码时,将误差作为迭代函数系统中的偏移量进行处理。

基于DCT变换系数的分形编码方法是将所有的 块和 块通过DCT变化到频域上,然后按分形匹配方法,通过几何变换和亮度变换,找到最佳匹配,得到分形码。解码时,跟空间域类似,只是还需进行DCT逆变换。优点是:在DCT 变换系数中比较容易找到具有自相似性的定义域块和值域块,而在空间域中却难以找到;对DCT系数做了误差补偿,从而改进了图像压缩的质量;频率域分形图像编码带来的另一个好处,就是可以减少几何变换的类型,从而大大减少相似块的数目,使得编码时间大大缩短。表面上看,频率域上的分形图像编码比空间域上的图像编码多了DCT和IDCT两道工序。但是,因为在频率域上几何变换可以简化合并为4个比较简单的几何变换,从而大大减少了相似块数目(呈几何级数) ,所以也大大缩短了编码时间。

6结束语

分形图像编码冲破了传统编码方法的理论框架,并利用了图像本身所具有的自相似性以潜在的高压比和良好的重建图像质量吸引着广大研究员。但是,为得到高质量高压缩比的重构图像往往要花费较长的压缩时间,从而影响了其在实际工程中的应用。虽然目前研究人员已经对分形图像编码做了一定的改进,往往都不能在压缩时间和图像质量等方面同时获得满意的结果。但我们仍然可以看到分形图像压缩方法的优势和巨大潜力。

参考文献:

[1] Mandelbrot B B,Voss R F.Fractals:Form,Chance and Dimension[M].Freeman,San Francisco,1977.

[2] Falconer K J.Fractal Geometry :Mathematical Foundations and Applications[M].John Wiley and Sons,1990(中译本).曾文曲,译.沈阳:东北工学院出版社,1991.

[3] Ramamurthi B,Gersho A.Classified vector quantization of images[C].IEEE Trans. Commun. vol. COM-34,1986:1105-1115.

[4] Jacobs E W,Fisher Y,Boss R D.Image compression :A study of the transform method[C].Signal Processing,1992,29:251-263.

[5] Jacquin A E.A Novel fractal Block-Coding Technique for Digital Image[J].Proceeding of IEEE International conference on ICASSP,1990,4:2225-2228.

[6] 何传江,黄席樾.现代智能算法理论及应用[M].北京:科学出版社,2005.

[7] 赵明,杨小远,李波.一种优选匹配的快速分形图象编码算法[J].数值计算与计算机应用,2006,27(1):24-30.

[8] 娄莉.一种基于邻域搜索的分形图象编码改进算法[J].微电子学与计算机,2003(5):66-68.

[9] Jacquin A E.Image coding based on a fractal theory of iterated contractive image transformations.IEEE Trans.on Image Processing,January.1992,1(1):18-30.

[10] Wohlberg B,de Jager G.A Review of the Fractal Image Coding Literature[J].IEEE,Transactions on Image Processing,1999,8:1716-1729.

[11] Zhao Yao,Yuan Baozong.A New Affine Transformation : Its Theory and Application to Image Coding[J].IEEE Trans on Circuits and Systems for Video Technology,1998,8(3).

[12] Gharavi-Alkhansari M,Huang T S.Fractal-based techniques for a generalized image coding method[C].Proc of IEEEE ICIP,1994,3.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问: 技术研究 进展 图像 压缩 分形