一种可控分形图像解码速度的算法

袁宗文　陈初侠

摘要：尽管更快的图像解码方法应用更为广泛，但在某些特殊的应用场合，需要渐进可控的图像解码方法.在保证最终解码图像不变的前提下，将传统压缩映射的固定参数改为可变参数，通过调节这些参数实现解码过程渐进可控.实验结果表明，传统分形解码约迭代8次即已收敛，提出的算法可实现迭代8到36次解码收敛，实现了解码过程灵活可控，而且该算法可更多地展现解码图像序列的生成过程.

关键词：分形;解码;收敛;可控

中图分类号：TP391  文献标识码：A  文章编号：1673-260X（2019）09-0059-03

分形图像编码因其较高的压缩比、分辨率无关性、迭代解码的新颖思想而受到人们广泛关注.分形图像编码是非对称的，即编码较为耗时，解码又非常快.在近二十多年中，学者们发表了大量的论文[1-11]，大都围绕怎样加快分形图像编码速度，但仍也有少量论文讨论了如何加快分形解码速度[12-13].然而在某些特殊的应用场合，如卡通的计算机辅助制作、图像解码的教学、信号的窄带渐进传输，需要一种较慢的可以控制的渐进解码方式.JPEG2000支持渐进图像传输技术，它解决了在窄带信道中以渐进的方式传输图像信息，即先以较低的码流传输图像的轮廓信息，然后同样以较低的码流逐渐传输图像的细节信息，这样既可解决窄带用户焦躁的等待问题，又可满足用户对图像质量的不同要求.分形图像编码还没有渐进传输上的应用，重要原因是传统的分形解码无法控制，它从初始图像到吸引子需要的迭代次数比较固定，一般都在7到8步左右.本文提出一种渐进可控的分形解码算法，可以将解码迭代的次数控制在8到36步之间.

1 算法分析

1.1 改进的不动点定理

不动点定理[14]：定义图像空间（，||·||）上的变换W：→.如果存在0≤s<1使得

||（W（C），W（B））||≤s||C，B||，C<B∈  （1）

则称W为压缩映射.设图像序列{Un}满足Un+1=W（Un），n≥0，U0=U，U是空间（，||·||）中的任意图像，则在压缩映射W作用下的图像序列有唯一不动点U*=U∞，也就是说存在唯一图像U*，使得W（U*）=U*.

改进的不动点定理：定义图像空间（，||·||）上的变换S：→，满足

因为0≤s<1，所以0≤w1+sw2+s2w3<1，所以S是压缩映射的.另一方面，设U*为W的不动点，则

从而U*也是s的不动点.所以，S是压缩映射的且与W具有相同的不动点.

证毕.

1.2 算法的实现方案

传统的分形解码是由分形码描述的压缩映射W对任意一幅图像U反复迭代完成的，根据拼贴定理，其不动点U*就是原图像Uorg的一个近似图像.即：

通常情况下，不论原图像是什么，满足式（3）中的N约为8，所以这是一个不能控制的迭代过程.基于改进的定理，我们使用压缩映射S代替W，通过改变加权系数，可以很好地实现对迭代过程的控制，而且其不动点也是原图像的一个近似图像，即最终的解码图像质量是相同的.实现的方案如图1（b）所描述.

当然在此基础上，还可以构造更为复杂的渐进解码方案，例如可以构造变换

式中加权系数w1，w2，w3，…，wN∈[0，1）且w1+w2+w3+…+wN=1，可以证明该S也是压缩映射的且与W具有相同的不动点，不过可以预见，这样的解码方案会因其复杂性反而降低其實用性.此外，改进方案中因为包含了两次压缩映射W，所以当预设的迭代次数N为奇数时，前（N-1）/2次采用本方案，对于最后一次即第（N-1）/2+1次，可令w3=0，w2=1-w1，而w1保持不变，再进行迭代解码，这样就可以使得迭代次数能任意设置，同时保证了不动点图像不变.

2 实验结果分析

改进方案的加权系数w1，w2，w3中只有两个变量是独立的，我们可以任意改变其中两个系数实现对解码速度的控制.为显示该系数对解码的影响，实验中，我们取了512×512的Lena灰度图像，编码采用传统方案，图像采用固定分割，值域块大小为8×8，解码时令w2、w3取不同值，得到渐进解码结果如图2所示.

图2中，图例baseline曲线表示传统分形解码，其他曲线为改进方案解码.可见改进方案解码比传统解码速度更为缓慢，改进方案解码具有更多的选择和解码可控的特点.为了主观感受改进方案渐进解码的特点，我们可以从图2中任取一条非baseline曲线，以图像序列的方式展示它的解码过程，譬如取w2=0.2，w3=0.2对应的曲线，得到的解码图像序列如图3所示.初始图像为全黑图像，其中图3（k）为第36次迭代，其PSNR=30.26dB，与不动点图像的PSNR=30.31dB相差0.05dB，表明已基本收敛（见图2（a））.

作为对比，同样从图2中取出baseline曲线以展示解码过程，即传统分形解码过程，得到的图像序列如图4所示，图4（e）为第8次迭代，其PSNR=30.28dB，表明已基本收敛.可见改进方案解码较传统方案解码的收敛速度要慢得多，而且如果调整加权系数，可以实现不同的收敛速度，特别地如果令w2=1，则改进方案就变成传统的方案.

我们还计算了改进方案相邻解码图像的差值图像，以显示其细节的增加情况.设Un表示第n次迭代解码图像，图5从左到右，从上到下，依次为：U2-U0、U4-U2、U6-U4、…、U18-U16.结果表明，解码图像序列细节以较均匀的比例逐渐增加.如果我们改变系数，可以得到更多的细节增加特点.

3 结论

基于传统分形解码的过程不能控制的特点，提出了一种可以控制的渐进分形解码算法，而且这种解码算法不需要改变原有的编码算法，实现过程简单.对于一些特殊的应用场合具有潜在的应用价值.

——————————

参考文献：

〔1〕Barnsley M F. Fractal everywhere[M].Academic Press，1988：375-377.

〔2〕Jacquin A E. Image coding based on a fractal theory of iterated contractive image  transformations[J]. IEEE Trans. Image Process，1992，1 （1）： 18-30.

〔3〕Davis G M. A wavelet-based analysis of fractal image compression[J].IEEE Transaction on Image Processing，February，1988，7（2）：141-154.

〔4〕Fisher Y， Jacobs E W， Boss R D. Image compression：a study of the iterated transform method[J].Signal Processing，1992，29（3）：251-263.

〔5〕Hurtgen B， Stiller C. Fast hierarchical codebook search for fractal coding of still image[C].Berlin，Germany，1993.397-408.

〔6〕Martio P， Michele N. Speed up in fractal image coding：comparison of methods[J].IEEE Trans. on Image Processing，2000，9（6）：1002-1009.

〔7〕He C J， Yang S X， Huang X Y. Variance-based accelerating scheme for fractal image encoding[J].IEE Electronics Letters， 2004，40（2）： 115-116.

〔8〕Lai C， Lam K， Siu W. Improved searching scheme for fractal image coding[J].IEE Electronics Letters， 2002， 38（25）： 1653-2654.

〔9〕Lai C， Lam K， Siu W. A fast fractal image coding based on kick-out and zero contrast conditions[J]. IEEE Transactions on Image Processing， 2003，12（11）：1398-1403.

〔10〕Wohlberg B， Jager G D. A review of the fractal image coding literature[J].IEEE Transactions on Image Processing，1999，8（12）： 1716-1729.

〔11〕Lototskiy R V.Images fractal compression optimization by means of artificial Kohonen neural networks[J].Journal of Automation and Informfation  Sciences，2003，35（1）：50-60.

〔12〕Moon Y H， Kim H S， Kim J H. A fast fractal decoding algorithm based on the selection of an initial image[J].IEEE Trans. Image Process， 2000，9（5）： 941-945.

〔13〕丁政建，袁宗文，繆东升.基于对比度因子调节的快速分形解码算法[J].兰州理工大学学报，2007，33（4）：110-112.

〔14〕夏道行，严绍宗，舒五昌.泛函分析第二教程[M].北京：高等教育出版社，2009.338-345.