一种基于分块的分形图像压缩方法

唐国维，韩鹏宇，王 艾，王苫社，施国俊

（1.东北石油大学计算机与信息技术学院，黑龙江大庆 163318； 2.东北石油大学石油工程学院，黑龙江大庆163318； 3.哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001； 4.大庆油田有限责任公司第八采油厂，黑龙江大庆 163514）

一种基于分块的分形图像压缩方法

唐国维1，韩鹏宇2，王 艾1，王苫社3，施国俊4

（1.东北石油大学计算机与信息技术学院，黑龙江大庆 163318； 2.东北石油大学石油工程学院，黑龙江大庆163318； 3.哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001； 4.大庆油田有限责任公司第八采油厂，黑龙江大庆 163514）

分形编码具有高压缩比的特点，但在编码过程中其匹配搜索时间开销巨大.提出一种基于分块的分形图像压缩方法：依据人眼视觉特性在PSNR变化不大的情况下，图像主观质量感受不明显的特点，将图像在空域分割为若干相对较小的块，对感兴趣区可采取一分为四的方法进一步减小块的大小，然后对每个块分别进行分形编码，并重构.结果表明，在PSNR略有降低的情况下，编码的匹配搜索时间大幅减少，同时重构图像的主观质量并没有明显降低.

图像压缩；分形；分块；图像编码；迭代函数系统

0 引言

数字图像数据量巨大，给存储和传输带来一定困难，需要对其进行压缩处理［1］.分形编码是利用图像自相似性进行压缩的一种方法，具有压缩比高、编码速度快等特点［2－3］.其主要思想是将图像在空域划分为若干个规则的矩形块，分别称为值域块和定义域块，通过它们之间的匹配产生迭代参数，进而达到图像压缩的目的.采用该方法生成的重构图像，其质量对图像划分过分依赖，通常定义域块划分得越大，重构图像的压缩比也越高，同时图像质量也随之下降.此外，若对一幅N×N的灰度图像编码，值域块和定义域块的匹配搜索的算法复杂性为O（（N）3）～O（（N）4），即若要保证较高的重构图像质量，需付出匹配搜索时间增加的代价.Bani－Eqbal B定义域块匹配搜索，构建合适的定义域块搜索树结构，以避免全局匹配搜索［4］，使算法复杂性降低，但图像重构质量也有所下降.Shen Furao等通过内积定义域块和值域块之间相似度，规定只有当相似度小于某一阈值时，才进行匹配运算，使匹配次数大为减少、算法复杂性有效降低［5］，但对相似度的定义缺乏理论依据，且算法难于实现最优匹配.在该算法基础上，Ongwattanakul S等根据概率统计分析，认为与值域块形成最优匹配的定义域块以较大概率出现在某个固定位置，使匹配搜索算法的复杂性降为多项式级［6］，但重构图像质量下降较大.人们从不同角度改进分形压缩方法，但还不能从根本上解决值域块和定义域块匹配搜索开销和重构图像质量之间的矛盾，多数算法以牺牲重构图像质量为代价，在一定程度上降低算法的复杂性［7－8］.基于人眼视觉在峰值信噪比（Peak Signal to Noise Ratio，简称PSNR）变化不大时，对图像质量的主观感受并不明显这一思想［9－10］，笔者提出基于空域分割的分形图像压缩方法，在PSNR略有下降的情况下，较大幅度地降低匹配搜索时间，同时保持一定的主观图像质量.

1 Fisher分形编码方法

分形理论研究表明，灰度图像和迭代函数系统（Iterated Function System，简称IFS）之间存在一一对应关系，既对任意一幅灰度图像，总存在一个IFS使其吸引子可以任意精度逼近之［11］.分形图像压缩的主要任务就是寻找该IFS的全部参数，并对这些参数进行适当编码.分形图像压缩方法中比较经典的是Jac－quin提出的基于划块的分形图像压缩方法［12］.1994年，Fisher对这一方法进行改进，成为传统分形编码中的主流方法［13］，该方法的编解码过程：

（2）搜索与其自相似的定义域块Dj，并做缩小、旋转和平移，且定义域块尺寸2D×2D＞2R×2R，通过平均—抽样操作Av，使定义域块与值域块具有相同尺寸，可表示为

搜索过程通过改变Π（K，L）和Lp（K，L），使dp达到最小，即利用式（2）并结合最小二乘法求得系数CK，L和hK，L.

（4）对每一个值域块Ri，改变Π（K，L）和Lp（K，L），找到一个最优匹配映射定义域块Dj，使dp达到最小，记录为CK，L，hK，L，Π（K，L），Lp（K，L），完成对值域块Ri的编码.

（5）对所有值域块Ri，分别寻找其对应的定义域块，使图像A上的每一个值域块Ri都用其定义域块覆盖，完成对整幅图像的编码.

解码过程通过对式（1）的迭代实现，即

2 重构图像质量影响因素

分形图像压缩解码是利用分形参数不断迭代的过程，因此重构图像质量和迭代次数相关.采用C＋＋和Matlab混合编程，选用Cameraman图像（尺寸为128×128）作为样本，通过仿真实验分析文中分形压缩方法.当值域块和定义域块尺寸分别为4×4、8×8时，前6次迭代所对应的重构图像及其PSNR值见图1.由图1可见，在主观视觉上，重构图像的质量随着迭代次数的增加逐渐得到改善并趋于稳定.当达到6次迭代后，PSNR值基本不再变化，说明已经收敛并逼近于原始图像的吸引子.

图1 Cameraman图像逐次迭代的重构效果

对Cameraman图像在值域块大小不同的情况下分别进行仿真实验，分形压缩统计结果见表1，对应的重构图像见图2.由表1和图2可以看出，分形图像压缩存在明显的编解码不平衡问题.对原始图像进行划块时，如果值域块划分得较小，则重构图像质量高，但匹配搜索开销大；反之，如果值域块较大，则重构图像质量下降，但匹配搜索开销减小.在分形图像压缩编码中，重构图像质量和匹配搜索时间是一对难以调和的矛盾，这也是分形图像压缩的最大缺陷.

表1 不同尺寸值域块分形压缩结果

图2 不同尺寸值域块分形压缩后重构图像

3 基于分块的分形图像编码

基于仿真实验分析，在分形图像压缩过程中，重构图像质量主要取决于划定的值域块尺寸.如果对原始图像事先进行分割处理，那么对每块再进行分形划块时，其所包含的块的数目和大小有所降低，这对提高分形编码图像质量和降低搜索时间有利.根据人眼的视觉特性，在PSNR变化不大的情况下，人眼很难感知图像之间的细微差别［9－10］.因此，在PSNR有所牺牲情况下，以重构图像质量轻微下降换取匹配搜索时间的大幅降低是可取的.根据文献［3］，与任意给定的值域块相匹配的定义域块以较小的概率出现在距其较远的区域.设待压缩的原始图像大小为2N×2N，首先将其分割为若干较小的块，每块尺寸为2M×2M（2≤M≤N－1）；然后对每部分按照分形编码方法进行合理的值域块和定义域块划分，并分别进行分形图像编码.对感兴趣区域（Region of Interesting，简称ROI），根据感兴趣程度采取一分为四的方法适当减小值域块尺寸，以提高该区域的重构图像质量.

采用C＋＋和Matlab混合编程，选取Cameraman图像（尺寸为128×128）进行编码压缩.首先将原始图像直接分割为4个64×64的相对较小的块，再对每块分别进行分形编码.原始分形压缩算法和基于分块的压缩算法重构图像效果见图3和图4.由图3和图4可见，主观视觉上文中压缩算法和原始压缩算法相比重构的图像效果没有明显下降.文中基于分块的分形压缩算法和原始分形算法重构图像的PSNR值对比见表2.由表2可见，在值域块划分相同情况下，基于分块的分形压缩算法的PSNR值有所下降，但下降幅度不大，而编码效率有较大提高.

图3 原始分形压缩算法

图4 基于分块的分形压缩算法

表2不同压缩算法重构图像结果

4 结束语

分形图像编码是利用图像自相似性进行压缩的一种方法，突破传统图像压缩方法的局限，可以获得较高的压缩比.在对分形压缩算法进行仿真实验分析基础上，提出基于图像分块的分形图像压缩方法.结果表明，在PSNR略有降低的情况下，匹配搜索复杂性明显降低，编码时间大为减少；同时重构图像的主观质量未受到明显损害，在一定程度上解决分形图像压缩中的编解码不平衡问题.

［1］ 唐国维，顾国昌.基于单窗口扫描的并行EBCOT编码［J］.哈尔滨工业大学学报，2008，40（12）：2078－2081.

［2］ 王向阳，于雁春.基于改进K－均值聚类的快速分形图像编码算法［J］.计算机科学，2008，35（2）：219－222.

［3］ 杨红颖，王向阳，于雁春.基于FCM聚类的快速分形图像编码算法［J］.小型微型计算机系统，2009，30（3）：493－497.

［4］ Bani－Eqbal B.Speeding up fractal image compression［C］.Proc SPIE：Still－Image Compression 2418，1995：67－74.

［5］ Shen Furao，Osamu Hasegawa.A fastno search fractal image coding method［C］.Signal Processing：Image Communication，2004，19（5）：393－404.

［6］ Ongwattanakul S，Xianwei Wu，Jackson D J.A new searchless fractal image encoding method for a realtime image compression device［C］.Proceedings of the 2004International Symposium on Circuits and System，2004，5（3）：23－26.

［7］ Tong C S，Pi M.Fastfractal image encoding based on adaptive search［J］.IEEE Trans Image Process，2001，10（9）：1269－1277.

［8］ Wang C C，Hsieh C H.An efficientfractal image－coding method using inter－block correlation search［J］.IEEE Trans Circuits，Syst，Video Technol，2001，11（2）：257－261.

［9］ 唐国维，王学春，齐峰.一种改进的基于人眼视觉特性的图像编码算法［J］.大庆石油学院学报，2006，30（6）：80－82.

［10］ 潘春华，朱同林，刘浩.图像质量的HVS评价方法［J］.计算机工程与应用，2010，46（4）：146－151.

［11］ 曾文曲，文有为，孙炜.分形小波与图像压缩［M］.沈阳：东北大学出版社，2002.

［12］ 张旭东，卢国栋，冯健.图像编码基础和小波压缩技术：原理、算法和标准［M］.北京：清华大学出版社，2004.

［13］ 王苫社.基于小波及分形的嵌入式图像编码算法研究［D］.大庆：东北石油大学，2010.

A fractal image compression method based on block－dividing／2012，36（3）：100－103

TANG Guo－wei1，HAN Peng－yu2，WANG Ai1，WANG Shan－she3，SHI Guo－jun4
（1.School of Computer and Information Technology，NortheastPetroleum University，Daqing，Heilongjiang163318，China；2.School of Petroleum Engineering，NortheastPetroleum University，Daqing，Heilongjiang163318，China；3.School of Computer Science and Technology，Harbin Institute of Technology，Harbin，Heilongjiang150001，China；4.Oil Recovery PlantNo.8，Daqing Oilfield Corp.Ltd.，Daqing，Heilongjiang163514，China）

For the convenience of store and transmission，itis necessary to conductcompression encoding for digital image.Fractal image coding has the characteristics of high compression，butthe match searching time in the process of encoding is huge.In this paper a fractal image coding method based on block－dividing is proposed.The human vision system is notsensitive to the subjective quality of the reconstructed image in case of a small PSNR change.The original image is divided into small blocks in space domain directly，and to the interesting parts the blocks can be divided further by one－to－four.Then the fractal image coding to each blocks is carried out，and the reconstruction is also conducted ateach block respectively.The experimental results demonstrate thatthe match searching time can be reduced substantially and the subjectimage quality remain unchanged basically，meanwhile the PSNR being decreased slightly.

image segmentation；fractal；block－dividing；image coding；iterated function system

book=3,ebook=84

TP391.41

A

1000－1891（2012）03－0100－04

2012－02－21；编辑：张兆虹

黑龙江省教育厅科学技术研究项目（12521050）

唐国维（1966－），男，博士，教授，主要从事图像处理与模式识别方面的研究.