大学课件图像压缩编码方法第5章分形图像编码.doc
《大学课件图像压缩编码方法第5章分形图像编码.doc》由会员分享,可在线阅读,更多相关《大学课件图像压缩编码方法第5章分形图像编码.doc(85页珍藏版)》请在三一文库上搜索。
1、大学课件图像压缩编码方法第5章分形图像编码第5章分形图像编码51基本理论52分形图像压缩编码的研究发展一种几何形状比例可变的分形图像压缩编码方法54 一种基于局部极大模和分形的混合编码方法5.1基本理论1 迭代函数系统(IFS, Iterated Function System)定义1设(X, 0是完备度量空间,(,)是X中的度量,w: XX是基本空间(X, )上的一个映射,如果存在一个正的常 数cl,使d(w(x), w(y)Scd(x, y)(5-1)则称w为(X, )上的压缩映射,c称为压缩因子。这里w: XX是基本空间(X, )的一个压缩映射,包括 在X的子集一个压缩映射。这个式为:w
2、B) =Vrc 6 B VB O X定义2完备的度量空间(X, d)以及斤个压缩映射w: X X(其压缩因子分别为5,c2,c”)一起,组成一个迭代函数,简称IFS,记作X: 叫,叫,c=niax(C, C2,c”)称沏FS的压缩因子,考虑(心),/i)上有个压缩 映射叱:T(x)S E, 2,n,定义一个新的映射W: T(X)T( 即nWCB) =u wt(B) VB e T(X) (5-2) 1 = 1则W是压缩映射,且压缩因子c=max(C, c?,,c”),即A(W(A),W(B) c A(A, B) VA, B e T(X)(5-3)定理1(压缩映射的不动点定理)设X: vvr v
3、v2, 叫是以,町上的IFS,则(1)由下式定义的变换W: T(X)fT(X),即W(B) -U wz(B) VB e T(X) i=i是完备度量空间(T(x),力)上的压缩映射,其压缩因子也是C,即h(W(A), W(B)OO其中,W(B)=W(B),入在IFS中也称为吸引子。在迭代函数(IFS)中,要求映 射Wj(=l, 2, w)是压缩的,通常采用仿射变换。在二 维情况下,这种映射成为(5-7)其中,%、叽、5、%、勺和/;是实数,定义域为二维的。对于 三维情况(图像为灰度图),这种仿射变换叫成为(乞9 y)_i, 1, *2, 1, i、Q 3, 1, Q 1, 3, *X时、2, 3
4、 y+2, i3, 3, i,JXi y).03,.Q1, 2, i2, 2, i3, 2, i其中,。1, 1,八。1, 2, i、。1,1,(5-8)3,八 2, 1,八 2, 2, i、2, 3,八 3,1,八。3, 2, i、。3, 3,八 “1,八:2, 0,如能选到一个IFSX: W, w2,,w”; c(0cl)使n(5-9)U (L) ) W ei=l(5-10)_ A(L, U wz(L) hj A) 戶1 其中,力为豪斯多夫距离,而入是该IFS的吸引子。由拼贴定理可知,为了使入逼近厶 必须使u W,(L) 2=1 足够精确地逼近Q。因此,尽可能地接近厶入才能更好地 逼近Q
5、根据叱,我们有nU w2 (L) Li = 1(5-11)W(L) =LnW(L) =U (L)n因此,厶划分厶,使L = U以至厶满足仿射变换叫得i=l到厶=叫(厶)如果力(厶,w(D)为呢,即称之为编码误差或拼贴误差h(L,入:示,称之为解码误差,则根据拼贴定理,得到此式根据编码误差乡(5-12)1* EC E?值。3.(带映射)局部迭代函数系统(LIFS)现在怎样对现实生活中的图像(例如图5.2(a)所示的少女 Lena像的原始图像)用分形原理进行压缩呢?虽然没有整体 与局部的自相似性,但经验显示,现实生活中的图像却存在 局部之间的自相似性,如图5.2(b)所示,从Lena像上取出的
6、一些部分具有不同比例的自相似性:她肩上一部分与其重叠 的一个小部分几乎是相同的,镜子里帽子的像的一部分与她 的帽子的一部分是相似的。可见局部自相似与图5.2表示的 自相似的不同之处在于现在的图像是由本身的许多“部分” 在适当变换下复制构成的,这些“部分”并不是它们自身在 仿射变换下的怛等复制品,而是有误差的,这样就构成了局 部迭代函数系统,它完全是IFS方法的推广,即每个变换叱 的定义域仅为X的一部分0变换。Lena图像(b)某些自相似的“部分”图5.2 Lena图像及某些相似的“部分”定义3设(X, )是完备度量空间,0uX(其中=1,2,n),局部迭代函数系统(LIFS, Local it
7、eratedFunction System)就是下列压缩映射集:仙 DlX, (Z=l, 2,n)(5-13)若图像为灰度图像,贝|”仗,y)称为每个点(x, y)上的灰 度值。一般情况下,把(x, y)区域划分为许多块,把(x, y) 区域划分为不可重叠的Range块尺和可以重叠的Domain块0, Domain块的边长都大于Range块。仿射变换叱作用于0.上, 逼近于尺上的灰度值而得到近似的叱,它们之间有如下的 关系:XyWiz、Xy、/(力,(x, y) 6 R:、2, y),如图5.3所示。f、X厂、JCyy工,y)eoiG y)、/G y)(5-14)H7Ki始图像仿射变换切作用于
8、D上逼近R,的示意图图5.3局部仿射变换示意图5-2分形图像压缩编码的研究发展1.基本方法在1989年和1990年之间,Jacquin提岀了全自动的分形 图像压缩方法。该方法以局部的仿射变换代替全局的仿射变 换。仿射变换以下式表示:XS, 1, ia 1,2, 0 -X-h.-Wjya2, 1,:a2, 2, i0y+c*(工9 y)_.00Pi, 0-y)_-Pi, 1-(5-15)Qi, 1, iLQ2, 1, io -+ a-(5-16) 每一尺均为一正方形式,而尤,y的原点是Domain块的中心点, a=0.5且p, 02)- (Sa)2(5-17)j=lj=lInf IH r luf
9、 m (QMzg3w+7N:QZ+0MzvNo3o+MT H s s g s s:1, 则放弃且继续搜索,否则记录卩的方位、旋转、和久1。(5) 对所有Range块都寻找其对应的最佳的Domain块, 使图像4上的每一Range块尺,都用其Domain块来覆盖,就 完成了一整幅图像的编码。图5.6表示对一个512X512的Lena图像进行解码迭代的 过程,经过8次迭代,完全可达到不动点,即可认为分形编 码的恢复图像。图5.6 512X512的Lena图像分形解码过程分别为0、1、2、3、4、8次迭代2.改进的分形图像压缩方法1991年,简库恩和弗歇尔等提岀了改进的仿射变换为XQl, 1, iQ
10、 1, 2, i0、XWiy如1, i2, 2, i0y+Ci、Zspi,o yP,1 (5-19)在一般情况下,该法与Jacquiii提出的方法相同,只是 增加了两个映射参数和勺。用D为Domain块在子块范围内 搜索来确定,即、勺确定;山,1,八山,2,八如1, i和也,2, i 与基本方法的参数相同,表示几何收缩映射和八种反射-旋 转操作。该法将Domain块缩小成与Range块相同的尺寸,用 最小二乘法逼近Range块求得、pit P %和即根据最佳 匹配原理,寻找最佳匹配的Domain块的方位、旋转、门,、 Pi, 1、%和采用此方法对标准的512X512 Lena图像进行 编码,当
11、压缩比为0.5 bpp时,峰值信噪比为30.8 dBo1992年,Momo和Dudbridge提出把图像分割成许多小方 块子图且每块子图单独采用IFS,但是整幅图像的IFS不能建 立,这相当于局部的IFS,对于子图的Domain块是预先决定 的且又包含Range块。Fishei Monro和Dudbridge等人研究了Range块的划分 方法,如自适应四叉树法、自适应HV分块法和自适应三角 形分块法等,并且比较了它们的压缩效果。实验结果表明: 自适应HV分块法比自适应四叉树法的压缩效果要好,但该 方法比较复杂;自适应三角形分块法的压缩效果最好,但也 是最复杂的方法,是目前改进分形编码的研究方向
12、之一。1993年,Gharavi Alkliansaric和Huang将Jacquin方法拓 宽,用一组固定基块(FBB, Fixed Basis Block)和一组与固定 基块无关、与图像有关的基块 (IDBB, Image-Dependednt Basis Block)的线性组合来逼近Range块。其中,FBB由设计 者选定,是与图像无关的基块集,彼此相互正交;IDBB之 间彼此近似正交,这类基块要通过多种运算从图像中求出。 这种方法中的FBB和IDBB的线性组合的系数较多,而且必 须记录这些系数。采用这种方法对标准的512X512 Lena图 像进行编码,其压缩比为053 bpp时峰值信
13、噪比为32.0 dBoThomas和Deravi在Jacquin方法中使用相关自由的形状, 对标准的512X512 Lena图像进行编码,获得压缩比为0.30 bpp时峰值信噪比为27.7 dBo虽然压缩效果得到了提高,但 恢复的图像效果不佳。简库恩和弗歇尔在分形图像编码中,引入不迭代解码算 法,即自适应码本聚类(Adaptive Codebook Clustering)方法, 可将编码速度提高许多,但算法复杂,对标准的512X512 Lena图像编码在0.5 bpp上可获得峰值信噪比为32.1 dBoVines和Hayes将搜索区域限定为离被编码的Range块最 近的256个Domain块,
14、采用多级分块法,对512X512 Lena图 像编码,可获得压缩比为0.47 bpp峰值信噪比为31.5 dBo1993年之前,大部分发表的分形编码论文主要集中在分 形变换上。为了产生非常有效的算法,大部分专家将注意力 集中于分形编码用搐编码和如何对分形变换参数用% 商编码来 建立最佳模型。1994年,Barthel等人提出以分形为主的DCT补偿编码混 合方法,该法优于单纯的分形编码方法。由于DCT本身具有 较快的编码速度,加上分形本身具有高的压缩比,可以通过 调节四叉树法分割阈值和DCT量化得到比较好的综合效果。 此方法虽然没有单纯DCT法快,但是比单纯的分形编码方法 要快得多。此方法对51
15、2X512 Lena图像编码在压缩比为0.35 bpp时可获得峰值信噪比为35 dBoGharavi-Alkliansarico和Huang提出了 一般图像分块编码 方法,即将分块变换、矢量量化和基于分形编码方法联合起 来。利用这种方法,图像中的每一个Range块都采用一个或 多个块的线性组合来逼近,而这些块是从尽可能大的块库中 选取的,块库中的块不一定正交。在视频编码情况下, DPCM的块预测方法和与块运动补偿法类似的自适应块预测 方法,也是此算法的特例。他们提出,分形图像解码器的迭 代性能是与编码器非因果有关的,采用一个因果的编码器导 致一个非迭代的解码器,这个解码器只需要一次迭代就收敛。
16、1994年和1995年,Rinaldo和Calvagon最早提出了基于小 波变换分形图像压缩方法,Davia、Walle、Krapnik和Simon 等人后续借助小波变换开展了一些分形图像编码方法的研究。 一种方法是知道Range块的均值和树变换参数,在解码时用 低频系数预测高频系数。另一种方法是结合零树编码、尺度 编码和借助各种最佳方法的技巧与分形编码的混合编码方法。 利用小波域的分形编码,可得到高质量、高压缩比的结果, 对512X512 Lena图像编码,在压缩比为0.26 bpp和0.08 bpp 时分别得到了32.78 dB和27.5 dB的峰值信噪比。1996年,Saupe提出了最佳
17、Domain块在Range块最邻近 区域的特征向量里的寻找范围。实验结果表明:此方法在相 同的压缩比情况下,不仅没有使峰值信噪比下降,还略有提 高,而且节省了大量时间。对512X512 Lena图像编码在压 缩比为0.931 bpp时,峰值信噪比为36.27 dB,且时间花费了 1分10秒,与传统分形编码方法对比,速度提高了6.6倍。1997年,Thao对Domain块搜索区域限定方法进行了改 进,根据统计Range块最匹配Domain块的规律,在距Range 块最近的81个Domain块中寻找最佳匹配块。虽然解码图像 略有下降,但编码速度大大地提高了,用稍微牺牲一点峰值 信噪比值的代价,换取
18、了编码速度的提高。1997年,Au和Liou等提出了基于DCT变换的分形编码 方法。为了减小分形编码的复杂度,采用DCT变换系数求解 出最优压缩因子和亮度差值。根据DCT变换的特点,减小分 形编码的计算量,采用少量DCT变换的系数参与仿射变换。 实验结果表明:在相同条件下,此方法只用视觉效果的稍微 下降就可以换来分形编码的大量计算减少。1998年,Hailenstein和Saup提出了在分形编码过程中区 域合并增长方法。根据拼贴误差大小、划分边界Euclidean长 度大小,来决定区域合并大小。初步测试表明,编码代价估 计器对一系列分形编码非常重要。1999年,Saup和Raouf等提出在分形
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学 课件 图像 压缩 编码 方法 章分形
