一种几何形状比例可变的分形图像压缩编码方法

一种几何形状比例可变的分形图像压缩编码方法 Aug. 2001 2001 年 8 月 J OU RNAL O F XI′AN J IAO TOGN U N IV ERSI T Y () 文章编号 :0253 - 987 X200108Ο0844Ο04 一种几何形状比例可变的分形图像压缩编码方法 1 2 3 1 强, 任庆利, 罗莉, 杨万海罗 () 1 . 西安电子科技大学电子学院 , 710071 , 西安 ; 2 . 西安交通大学 ; 3 . 国防科技大学 摘要 : 在了图像压缩的分形几何形状比例变化可行性的基础上 ,提出一种基于分形几何形状比例可变的分形图像压缩编码方法. 以分形几何比例分别为 2?1 和 3?2 的最佳父块逼近子块程度 的实验为例 ,得出父块越大 ,父块逼近子块程度越差的结论. 因此 ,分形图象压缩必须考虑几何形状 比例. 进一步给出了 4 种分形几何比例的灰度平均采样公式 ,并模拟这 4 种分形比例 ,分别单独进 行了分形编码实验. 根据同一图像不同部位的具体情况 ,采用不同的分形几何比例进行混合几何比 例的分形编码方法实验 ,结果明 :分形几何比例可变的混合分形编码方法与其他单一几何比例分 形编码方法相比 ,图像的压缩比和峰值信噪比均有提高 ,编码时间也有所减少. 关键词 : 分形 ;图像压缩 ;迭代函数系统 ;几何形状比例. 中图分类号 : TN919 . 81 文献标识码 : A Fractal Image Compression Coding Ba sed on Varia ble Fractal Geometric Scale 1 2 3 1L uo Q i a n g, Ren Q i n gl i , L uo L i , Y a n g W a n hai ( 1 . School of Elect ro nics Engineering , Xidian U niversit y , Xi′an 710071 , China ; )2 . Xi′an J iaoto ng U niversit y ; 3 . Natio nal U niversit y of Defence Technology Abstract : A f ractal image co mp ressio n co ding met ho d based o n variable f ractal geo met ric scale is p ro2 po sed . The po ssibilit y of t he variable f ractal geo met ric scale of t he image co mp ressio n is analyzed. The experimental result s of t he app ro ximatio n abo ut t he best matching of do main blocks to range blocks based o n f ractal geo met ric scales of 2?1 o r 3?2 showed t hat t he app ro ximatio n beco me bad wit h t he do2 main blocks beco me larger . Acco rdingly , t he co nclusio n is p ropo sed t hat t he f ractal geo met ric scale must be co nsidered serio usly and t he fixed mo nogeo met ric scale is not t he goo d choice in t he f ractal im2 age co mp ressio n . Mo reover , t he gray2level averaging sampling fo r mula of t he fo ur kinds of geo met ric scale are given . The f ractal co ding experiment s simulating t he fo ur kinds of geo met ric scale were per2 fo r med respectively. The f ractal co ding experiment s based o n t he mixed geo met ric scale acco rding to t he different po sitio n cases of a real image were perfo r med. The simulatio n result s show t hat t his new met ho d imp roves t he co mp ressio n rate and peak SN R co mparing wit h t he t raditio nal image co mp res2 sio n co ding met ho d. ) ( Key words : f ract al ; i m a ge com p ression ; i te rat ion f u nct ion syste m I FS ; geom et ric scale ( ) 收稿日期 : 2000Ο12Ο19 . 作者简介 : 罗 强 1966 ,, 男 , 副教授.基金项目 : 国家自然科学基金重点资助项目 第 8 期罗 强 ,等 :一种几何形状比例可变的分形图像压缩编码方法845 ( ) ( ) 2B ?X , 使 分形 Fractal理论是由曼德勃特在 20 世纪 70任给 n ( )( )lim W B 年代提出的 ,是非线性科学的主要分支之一. 分形理 3 = A n ?? N 论已在许多学科中迅速得到发展. 当今 ,分形在图像 n ( ) ) (式中 : W 为 ?w ?的表示符 ; W B 表示对 B 迭 i 1 i = 1 压缩编码中获得了十分诱人的成果. 代 n 次运算 ; A 被称为 IFS 的吸引子. 要对图像进分形几何中的压缩映射定理和拼贴定理 ,构成 行分形编码 , 就是要寻找一个 IFS , 使其吸引子 A了分形图像压缩编码的核心部分. 图像压缩编码就 逼近原图像.2 是寻找一个迭代函数系统 IFS,有了这个系统 ,就 必然决定了惟一分形图形 ,这个图形被称为迭代函 2 几何形状比例可变的思想数系统的吸引子. 给定一幅图像 ,如何能找到一个迭 代函数系统 ,使它的吸引子与原图像完全吻合 ,这是 现实生活中的图像是有灰度的 、非严格自相似尚未解决的问. 我们可降低要求 ,使吸引子逼近原 的 , 不具有整体与局部的自相似 , 但是图像却存在局 图像. 一般在分形图像压缩编码中采用的几何形状 部之间的自相似性 , 即可将具有局部迭代函数系统 比例是固定不变的 ,如 2?1 ,结果会导致子块与父块 的完整图像分为若干个分形的子图. 寻找最佳匹配 3 的匹配性能变差 ,峰值信噪比不高 ,压缩比低. 为 的父块 , 即要求出子图的整体与局部之间存在的某 种自仿射特征. 例如图 1 所示列娜像上取出的一些 了提高图像压缩比和峰值信噪比 ,本文应用自适应 部分 , 它们具有不同比例的相似性. 问题应当选择多 的四叉树编码技术 ,首次采用了灵活多变的分形几 大比例作为分形几何形状比例. 何形状比例 ,对分形图像压缩方法进行探讨 ,经模拟 我们从下面的数据 实验表明 ,与传统的分形图像压缩编码方法相比 ,压 来分析 : 列娜像的大小 缩比和峰值信噪比均有提高. 为 256 ×256 ×8 bit , 子 块分割为 8 ×8 像素的 4 ,5 1 基本的数学原理非重叠子图 , 而父块分 成两种情况 , 一种为几 n ( ) 设 X , d是 n 维欧氏空间 R 上的完备度量空 何形状比例为 2 ?1 , 即 n 间 ,而 X 是 R 的闭子集 , d 为空间上所定义的测 16 ×16 像素可重叠的 度 , 如果 方块 , 另一种为几何形 ϖ s ?[ 0 , 1 , Π x , y ? X 状比例为 3 ?2 , 即 12 × ) ( )( ( ( ) ) ( )1 d w x , w y ?s d x , y 那么 , 变换 w : X ?X 就是压缩变换 , s 为映射 w 的 图 1 某些相似的部分 12 像素可重叠的方块 ,) ( 压缩因子. 若 w 1 , 2 , , N 是压缩变换 , 若对所有i 分别寻找子图分形结构N . 我们从中列举一段子图对( ) 一切有 f ?X , 使 ?w f , 则称其为迭代函数. 由压 i i = 1 应不同父块的情况 , 见表 1 . 缩映射定理可知 :由表 1 可见 , 父块匹配的优劣主要看测度的大 ( ) 1存在惟一的吸引子 A ?X , 使小 , 即父块逼近子块的程度 , 测度越大 , 逼近程度 ( ) ( )W A= A 2 表 1 两种分形几何形状比例下父块对应子块的最佳匹配参数情况 分形几何比例为 2?1分形几何比例为 3?2 子图 序号 父图序号 旋转形式 压缩因子偏差测度父图序号 旋转形式 压缩因子偏差测度 1 1528 4 - 0 . 030 4 . 302 . 102 1 . 030 4 . 302 . 090 95 1 1528 4 - 0 95 1 2 1321 5 - 0 . 068 2 101. 00 8 . 264 0 - 0 . 066 7 100 . 78 7 . 881 1241 5 3 1089 4 - 1 . 010 2 121. 59 387 . 90 0 . 967 8 4 . 534 0 336 . 9 652 1 4 673 5 - 0 . 066 2 139. 00 1 . 601 8 - 0 . 110 9 145 . 34 4 . 417 435 5 5 732 1 0 . 768 2 31 . 070 5 . 956 7 495 1 0 . 820 2 24 . 449 4 . 032 6 852 1 0 . 487 0 42 . 264 20 . 705 575 1 0 . 714 8 36 . 361 7 . 303 西 安 交 通大 学 学报846 第 35 卷 3 3 越差. 从整个数据来看 , 最佳匹配 12 ×12 的父块与 μ μ+ ) 32 42 4 8 子图的相似性比最佳匹配 16 ×16 的父块与子图的 4 1 1 1 1 2 相似性要好一些 , 但是同时还有一些 16 ×16 的父块 μ μμμ ( ) ( μ′+= + + +22 22 32 42 23 4 7 16 4 8 比 12 ×12 的父块吻合子块的程度好. 显然 , 几何形 1 1 1 1 μμμμ μ) + + + +33 43 24 34 状比例值不同 , 也可改变父块的位置 、压缩因子 、偏 44 2 8 2 4 差和旋转值 , 从而影响父块逼近子块的程度. 因此 , ( ) 3当 2 D = 3 B 时 , 最小子块为 2 ×2 , 对应最小分形图像压缩必须考虑几何形状比例 , 几何形状比 的父块为 3 ×3 , 父块的平均抽样值为例越大 , 其恢复图像的迭代收敛越快. 所以 , 必须根 2 1 1 1 2 ( μ)(μμμμ)′+ + += 11 21 12 22 11 据情况 , 选择合适的分形几何形状比例值. 3 2 24 ( ) 4当 4 D = 5 B 时 , 最小子块为 4 ×4 , 对应最小 3 分形几何形状比例值的变换的父块为 5 ×5 , 父块的平均抽样值为 1 1 1 4 2 μ μμ( ) (μμ ) ′= ++ +21 12 2211 11 5 4 4 16 一幅图像的一个分形仿射变换表达式如下 3 1 4 3 1 2 0 abe iiix x μμμ ′( ) ( μμ) ++ += 12 22 13 12 23 5 4 16 2 8 0 cd f ( )w y = iiy i4 + i 4 3 1 3 1 2 μμμμ) ( μ( )+′+ = + 21 21 31 z 22 32 z 0 0 so ii 4 8 5 2 16 式中 : x 、y 表示平面; z 表示灰度.w 决定父块 D i j3 3 4 9 1 2 μμ μ( ) ( μμ) ′++ += 32 23 22 22 33 5 16 8 8 4 是如何映射到子块 R 上的关系 , 它包含两者的位 i ( ) ( ) 以上 1到 4中所有变换式的选用条件是 :子块大置 、压缩因子 、偏差方向和几何形状比例. 考虑子块 小必须为它们最小子块的整数倍. 显然 , 其中的几何 和父块的形状变化 , 本文首次选用 4 种不同几何形 形状比例变换要求最小子块为 4 ×4 . 状比例值和 8 种旋转方向来拟合实际的 a、b、c和i i i d 值.i 设子块和父块大小分别为 B ×B 和 D ×D , 给 4 自适应的四叉树分形多种几何形状出父块的平均抽样值变换如下. 父块和子块都是正 比例编码方法方形的 , 因此它们可折叠成大小相等的 1/ 4 方块 , 而 折叠后同一位置的坐标有互换关系 , 其中每个像素 的位置用行 、列标表示 , 只要写出父块位于左上角的 考虑到分形图像编码的质量和压缩比 , 采用了[ 6 ] 1/ 4 方块的平均抽样公式 , 则父块的其他 3 块的平 几何形状比例与自适应的四叉树分形编码. 为了 降低分形编码时搜索的复杂度 , 搜索的范围暂时定 均抽样公式就可以按以上折叠关系推算出. 为子块临近区域的父块. 设几何形状比例为 2?1 、7? ( ) 1D = 2 B 时 , 父块的平均抽样值为当 R R max min 4 、3?2 和 5 ?4 , 按大小排列 , 分为 4 档 ; 2 、2 分 1 别为最大子块边长和最小子块边长. 具体步骤如下. μ( μ( μ( ) ) )′i , j = [2 i , 2 j + 2 i + 1 , 2 j + 4 ( ) 1W ×W , 允许匹配误差为设定搜索范围为 μ( ) μ( ) 2 i , 2 j + 1+ 2 i + 1 , 2 j + 1] R R max maxε, 把图像分割为不重叠的 2 ×2 的子块 R , 选 i i , j ?[ 1 , 2 ,, n ] 用最大几何形状比例档为 2 ?1 , 在子块周围分割可 μμ 式中 :为变换值′ ;为父块的实际灰度值.[ 7 , 8 ] 以重叠的父块. ( ) 2当 4 D = 7 B 时 , 最小子块为 4 ×4 , 对应最小 () 2搜索子块 R 的最佳匹配映射 , 以 R 的位 i i 父块为 7 ×7 , 父块的平均抽样值为 置上为起点 , 在 W ×W 范围内寻找与 R 相匹配的 i 3 3 4 9 2 μμμ ′) (μμ) ( = ++ + 11 21 12 11 22 父块.7 4 4 16 ( ) ε3如果匹配的误差小于, 则最佳匹配的 3 4 1 3 2 μμ ′) ( μμμ( = ++ ++12 23 12 22 13 ( 7 4 16 4 ) 参数 , 否则转至第 4步. ( ) 1 3 4如果分形几何形状比例不是最小档 , 把几何 μμ) +14 24 2 8 形状比例值减小一档 , 在子块周围分割可以重叠父 1 3 4 1 2 ( ) ( ) μμ块 , 然后转至第 2步 , 否则转至第 5步. μ( ) ( μμ ′= + +++41 22 21 21 31 7 4 2 16 第 8 期罗 强 ,等 :一种几何形状比例可变的分形图像压缩编码方法847 ( ) ε 5, 则把子块 R 一分为四 , 几 理论还有待进一步完善 ,如怎样在保证恢复图像质如果误差大于i 何形状比例升为最大档 , 在新的子块 R′周围分割 量的同时提高其压缩比的问题 ,都有待于在今后的 i ( ) 可以重叠的父块 , 转到第 2步. 工作中研究探索. ( ) ( ) ( ) ( ) 6重复第 2、4和 5步直到所有的大小子 ε块与相适应的父块之间匹配误差小于为止. 5 实验结果与结论 依照上述方法 , 本文做了对比实验 , 实验对象是 256 ×256 ×8 bit 的列娜灰度图像 , 计算过程在 Pen2 () ( ) () a原图b分形几何形多种几何形状比例c tium ?200 微机上完成.状比例为 2?1 5 . 1 分形单独几何形状比例四叉树编码 图 2 几何形状比例可变的分形图像压缩编码压缩效果图编码时 , 首先设列娜灰度图像的父块与子块之 R R max min 间匹配的允许误差为 7 , 2 = 16 和 2 = 4 分别 参考文献 :δ为最大子块边长和最小子块边长. 在子块的 邻域 1 赵 耀 , 王红星 , 袁保宗. 分形图像编码研究的进展寻找 , 得到原始图像的编码. 分别应用第 3 节中的 4 () J . 电子学报 ,2000 ,28 4:95,106 . 种固定分形几何形状比例进行四叉树编码 , 结果如 Hart J C. Fractal image co mp ressio n and recurrent iterat2 2 表 2 所示.ed f unctio n systems J . I EEE Co m p uter Grap hics and () Applicatio ns , 1996 , 16 4: 25,33 . 表 2 分形单独几何形状比例四叉树编码结果 J acquin A E. Image coding based o n a t heory of iterated 3 比例压缩比 峰值信噪比/ dB时间/ sco nt ractive Mar kov operators R . Theoretical founda 2 29 . 3 19 . 53 931 2?1tio n , Report Mat h. Gerogia , U SA : Gerogia Instit ute of 7?4 Technology , 1989 . 75,82 .30 . 1 20 . 78 857 3?2 Fisher Y. Fractal image co mp ressio n : t heory and applica2 31 . 9 21 . 64 783 4 tio n M . New Yor k : S p ringer , 1995 . 5?4 32 . 3 22 . 13 698 陈守吉 ,张立明. 分形与图像压缩M . 上海 :上海科技 5 教育出版社 ,1998 . Wakefield P D , Mo nro D M . Fractal enhancement of de2 由表 2 可知 ,随着几何形状比例值的下降 ,峰值6 co mp ressed image A . Proceedin gs of ICIP298 I EEE In2 信噪比提高 , 压缩比增大 , 但是图像的恢复时间增 ternatio nal Co nference o n Image Processing C . Chica 2 长 ,图像的主观质量略有下降. go : I EEE Co mp Soc , 1998 . 406,409 . 5 . 2 多种分形几何形状比例四叉树编码Saupe D. Accelerating f ractal image co mp ressio n by mul2 用第 3 节中的 4 种分形几何形状比例按 4 种所 7 ti2neighbour search A . Co hn M , Storer J A , Proceed 2 述步骤去做 ,对列娜像进行编码 ,得到的结果是压缩 ings DCC’95 Data Co mp ressio n Co nference C . New 比为 21?3 ,峰值信噪比为 3314 dB ,时间为 564 s. 虽 Yor k : I EEE Co mp Soc Press , 1995 . 235,241 . 然压缩比比几何形状比例小的略有下降 ,但是此方 Nappi M , Vit ulano D. Linear p redictio n image coding 法的匹配精度高 ,恢复图像时间短. 这其中的两种情 8 using iterated f unctio n systems J . Ima ge and Visio n 况如图 2 所示. () Co mp uting , 1999 , 17 10: 771,776 . 作为一种新的分形图像压缩方法 ,这种独特思 ()编辑 刘 杨 想丰富了图象压缩编码的研究内容 ,但是分形编码