引入非线性变换的分形图像压缩编码

引入非线性变换的分形图像压缩编码 研究简报 引入非线性变换的分形图像压缩编码 11 1 ,2 立高瀚昭,王俊生,谢 () 1 . 南京大学 计算机系 ,江苏 南京 210093 ;2 . 国家电力公司电力自动化研究院 ,江苏 南京 210003 摘 要 :提出了一种基于非线性变换的分形图像压缩编码方法 。证明了引入的非线性变换满足压缩迭代映射理论 。模拟实验的结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明 ,与传统的分形图像压缩编码方法相比 ,压缩比和峰值信 噪比均有所改善 。 关键词 :图像压缩编码 ;分形 ;非线性变换 中图分类号 : TN91111 ; TN911176 文献标识码 :A () 文章编号 :1000 - 436X200004 - 0089 - 04 A fractal image coding a pproach based on non2linear transf orms 1 1 ,2 1GAO Han2zhao,WANG J un2sheng,XIE Li (1 . Department of Computer Science & Technology ,Nanjing University ,Nanjing 210093 ,China ; )2 . Nanjing Automation Research Institute ,Nanjing 210003 ,China Abstract : In this paper ,a fractal image coding approach based on non2linear transforms is proposed1The non2 linear transforms satisfy a theory of contractive iterated image transformations1Simulation results show that this ( ) proposed approach can improve bit2rate and peak signal2noise2ratio PSNRby comparing with a traditional frac2 tal image coding method1 Key words :image compression coding ;fractal ; non2linear transform 1 引言 1 21992 年 ,J acquin 提出了自动分形图像压缩编码算法, 后来又进一步完善了该算法 。3 ,6。 由于分形图像压缩编码在理论上可达到极高的压缩比 ,因而吸引许多研究人员进行研究 在 J acquin 提出的分形图像压缩编码算法中 ,变换映射库中的变换均为线性变换 。引入非 线性变换可进一步扩展分形压缩变换库 ,增加算法寻求“最佳映射”的机会 。本文将在这方面 做一探讨 。 2 引入的非线性变换 本文将引入三种非线性变换 :正弦 ,平方 1 和平方 2 。变换形式如下 : 正弦 :SIN αμ) Δ(π T= ×SIN / 255 ×/ 2×255 + gij 平方 1 : 收稿日期 :1997 - 04 - 02 ; 修订日期 :1999 - 04 - 20 基金项目 :中国博士后科学基金资助项目 通 信 学 报 2000 年?90 ? SQR 1 2 αμΔ T=×/ 255 + gij 平方 2 : SQR 2 2 αμ(μ ) Δ T=×/ max + gij ij ij SIN SQR 1SQR 2αμ( )式中 , T, T和 T分别表示正弦 ,平方 1 和平方 2 变换 ;为一常系数 ;为图像 i , j ij Δ( ) 位置处的像素值 ;g 为反映误差的常数项 ; SIN x为 x 的正弦值 。 分形编码算法中 , 要求变换库中的变换应满足压缩迭代理论 , 即 ( (μ) ( ) ) (μ) αα d T , T vΦd , v,Φ1 (μ) μ式中 , d , v表示图像 , v 间的距离 。 下面考察本文引入的三种非线 性变换满足压缩迭代理论的条件 。 () (π(μ) μ μ) 1正弦 :由于 ?0 ,/ 2时 ,有 SIN < 。则 SIN SIN (μ) ( ) ) αμπααπμ( (π) ()d T, Tv< d ××/ 2 ,×v ×/ 2= / 2 d , v πα满足压缩迭代理论的条件是Φ2/。 ( )1 : 2 平方 SQR1 SQR1 2 2 21/ 2( (α α ) ) μ( (μ) ( ) )= ×/ 255 - ×v/ 255d T, Tv ij ij ?ij 21/ 2 2 2 221/ 2 ) ) (μ) (μ) ) α( (μvαμα()= - v×+ v/ 255Φ 2-= 2d , v ijij ijij ijij ??ij ij α满足压缩迭代理论的条件是Φ015 。 () 3平方 2 与平方 1 的条件相同。 3 编码方法 将上述三种非线性变换加入传统分形编码变换库 ,寻找最佳组合作为码本 。 2 ( ) 采用父子 Parent2Children结构编码,本算法中用一个字节为标志字指明父子结构种类 ( ) 和变换种类 。根据这一标志字确定紧接着的码本的属性 父本和哪个子本,以及相应父子码 () 本所采用的变换种类 仅指明线性/ 非线性。采用非线性变换编码时 ,仍保留 8 种旋转变换 。 父子结构编码的方法是 :父本尺寸比子本尺寸大一倍 。首先对父本进行编码 ,如果其编码 误差小于给定的父本误差阈值 ,则不进行子本编码 ,而进行下一父本编码 ; 如果其编码误差大 于给定的父本误差阈值 ,则分别判别 4 个子本的编码误差 ;如某个子本的编码误差大于给定的 子本误差阈值 ,则对该子本进行编码 ;否则 ,该子本不进行编码 。如果有三个或三个以上子本 需要编码 ,则去掉父本编码 ,而采用 4 个子本编码 。标志字用 4 位可反映父子结构 。 码率估计如表 1 所示 。 表 1码率估计 标志字 8 位 ( () ) 分块类均匀 ,边缘 ,混合Midrange块2 位 (Δ)6 位误差项g (α) ( ) 线性参数注 :仅限于线性变换2 位 ( ) 非线性变换种类注 :仅限于非线性变换2 位 旋转变换种类3 位 () ( ) ( ) 映射域块Domain序号父本如果存在10 位 () ( ) ( )映射域块Domain序号子本如果存在11 位 () ( ) ( ) 映射域块Domain序号子本如果存在11 位 第 4 期高瀚昭等 :引入非线性变换的分形图像压缩编码?91 ? 4 解码方法 解码时 ,首先读入标志字 ,判别相应的父子结构 。再据此对紧接着的父本或子本进行依次 解码 。每个块的具体解码方法与传统分形解码方法相同 。不同的是 ,若该块的标志字中显示 该块为非线性变换编码 ,则进行相应的非线性变换解码 。对一个父子结构完成解码后 ,读入下 一标志字继续进行解码 ,直至完成全部图像解码 。 5 模拟实验 作者采用上述描述方法 ,进行了一些图像的压缩重建模拟实验 。并与传统方法进行了对 α比 。模拟实验的非线性变换中均取为 0145 。模拟实验结果如表 2 和表 3 所示。表 2 给出了 ( ) 在多个分块尺寸下 表中数值以父本尺寸为准传统方法和本文方法对比的压缩比与峰值信噪 比 。表 3 为传统方法和本文方法的对比提高率。 () 表 2压缩比 比特率和峰值信噪比的比较 尺寸 32 ×32 16 ×16 8 ×8 传统方法 本文方法 传统方法 本文方法 传统方法 本文方法 图像 bpp PSNR bpp PSNR bpp PSNR bpp PSNR bpp PSNR bpp PSNR ()Lenna 512 ×512 0126 26104 0123 27134 0161 31173 0160 32160 1175 38162 1174 39171 ()Lenna 256 ×256 0132 22151 0128 23185 0175 28112 0172 28167 2103 33185 2102 34136 ()Portrait 512 ×512 0128 21181 0125 23111 0185 27123 0184 27171 2147 30104 2141 30131 ()Tools 512 ×512 0128 21103 0127 22109 0184 27191 0181 28197 2138 37137 2130 37175 ()Beach 128 ×128 0135 22184 0129 23103 0177 25147 0174 26104 2131 30184 2123 31144 () 压缩比 表 3比特率和峰值信噪比的提高率 尺寸 32 ×32 16 ×16 8 ×8 图像 bpp PSNR bpp PSNR bpp PSNR ()Lenna 512 ×512 0103 1130 0101 0187 0101 1109 ()Lenna 256 ×256 0104 1134 0103 0155 0101 0151 ()Portrait 512 ×512 0103 1130 0101 0148 0106 0127 ()Tools 512 ×512 0101 1106 0103 1106 0108 0138 ()Beach 128 ×128 0106 0119 0103 0157 0108 0160 图 1 显示各种变换所占的比例 。表明非线性变换占了一部分比例 。图 2 和 3 为 Lenna 图 像采用本文方法的线性参数所占比例和 8 种旋转变换所占的比例 。 6 讨论 采用非线性变换后 ,与传统方法相比 ,由于更多的父本编码误差小于阈值 ,使仅需父本编 码的几率提高了 。对子本编码也如此 。同时 ,编码后图像与原始图像间的误差也减小了 。故 采用本文方法能使压缩比和峰值信噪比均有所提高 。 本文工作重点在于探讨分形变换库的扩展 ,并没有刻意追求高的压缩比和峰值信噪比 。 通过优化编码率等方法 ,还可以进一步提高压缩比和峰值信噪比 。本文工作旨在分形变换库 通 信 学 报 2000 年?92 ? 各种变换所占的比例 图 1 图 2 Lenna 图像线性图 3 Lenna 图像 8 种旋转 变换所占的比例 参数所占比例 研究方面抛砖引玉 。 不容置疑 ,由于采用了非线性变换 ,编解码时 ,增加了非线性变换运算项 ,使编解码复杂度有所增加 ,编码的耗时也较传统方法多 。由于目前 CPU 速度的提高和硬件的采用 ,使上述问 题并不十分突出 ,也可通过改进算法减少复杂度和耗时 。 作者感谢中国博士后科学基金的资助 。 参考文献 : 1 JACQUIN A E. A fractal theory of iterated Markov operators with applications to digital image codingD 1 Georgia Tech ,Atlanta ,19891 () JACQUIN A E1Fractal image coding :a reviewJ 1Proceedings of the IEEE ,1993 ,81 10:1451,14651 2 FISHER Y1Fractal image compression with guadtrees A 1Fractal Image Compression ———Theory and Applications to Digital Images 3 C 1New York : Springer2Verlag ,19941 () BANI2EQBAL B1Enhancing the speed of fractal image compressionJ 1Optical Engineering ,1995 ,34 6:1705,17101 4 () WOHLBERG B E1Fast image domain fractal compression by DCT domain block matchingJ 1Electronics Letters ,1995 ,31 11:869, 5 8701 ( ) WOHLBERG B E ,Jager G1Fractal coding performance for first2order Gauss2Markov modelsJ 1Electronics Letters ,1996 ,32 5:441 6 ,442 .