基于混合分类和矩形划分的快速分形编码方法摘要：针对分形图像压缩中矩形划分计算量太大的问题,提出了一种混合分类方法并将其应用于图像的矩不变量，得到了一种基于矩形划分的快速分形编码方法。实验表明，该方法相对于全局搜索，在压缩比和解码质量略有下降的基础上，能极大地提高分形编码速度；与均匀分类方法相比,混合分类法可进一步提高分形编码速度并改善解码图像质量，可以在一定的条件下取得压缩比优势。关键词：分形图像压缩;迭代函数系统;矩形划分;自适应分类;混合分类：TP391．41文献标志码：A：1001－3695(2007)07－0064－030引言??分形图像压缩是近十几年发展起来的一种新的图像压缩方法。它以迭代函数系统(IteratedFunctionSystem，IFS)为基础,基于自然景物的自相似性进行数据压缩。此项研究由M.Barnsley[1]首先提出；Jacquin[2]的基本自动分形图像编码(BasicAutomationFractalImageCoding)使分形图像编码进入了新时代；此后Y．Fisher[3]又对此方法进行了不断的改进和完善。前期对值域块的划分都是采用正方形，忽略了图像的灰阶均匀性。采用矩形划分[4]可以避免这种情况，但是采用矩形划分的计算量相当大，导致编码时间过长。本文提出了一种混合分类方法并将其应用于图像的矩不变量，大大提高了编码速度。??1分形图像压缩的基本模型??Jaquin在IFS的基础上，提出了局部迭代函数系统(PartitionedIteratedFunctionSystem,PIFS)[5,6]，并据此第一个提出了全自动的基于分块的分形编码方法,它现已成为了分形图像压缩的基本模型。其基本过程如下：??对一幅待编码图像，先将其划分为互不重叠的等大小图像子块，称为值域块(RangeBlock)，记为R；又将原图像划分为可以重叠的等大小的子块,其尺寸比值域块稍大(一般为两倍)，称为定义域块(DomainBlock)，记为D；所有这些定义域块组成定义域块库(DomainPool)??S??D，它构成了搜索空间。分形编码可描述为对每一个值域块R，求解如下的最优化问题：??对每一个值域块，它所对应的最优化问题（式(1)）的解就构成了这个值域块的编码参数。其中包括D(此时称为该值域块的最优匹配块)的位置、τ??i的代号和f??的信息。这样所有值域块的编码参数就一起定义了一个PIFS,再对该PIFS的参数进行量化、熵编码并存储成文件就完成了整幅图像的编码。??分形解码很简单，只要对上述得到的文件进行熵解码、逆量化先恢复出PIFS，再用该PIFS对任意初始图像反复迭代即可。??2基于矩形划分的分形编码方法??与传统的分形图像压缩基本模型相比，基于矩形划分的分形编码方法有以下不同：??(1)按照值域块最小维的大小由大到小进行编码??编码时,首先从值域块库中选取最小维最大的值域块，为其寻找最优匹配块。例如：10×7的块要先于20×6的块进行匹配，虽然后者包含的像素数目多于前者。如果当前正在匹配的值域块尺寸和下一个待匹配块相同，则为当前值域块建立的定义域块库就可以直接被下一个待匹配块使用，无须为其重新建立定义域块库。??(2)定义域块只有四种旋转―反射变换??其包含顺时针作0、180°旋转及沿水平中线、垂直中线反射。??(3)矩形分割标准??于是得到了一系列矩不变量以构成一个特征向量(θ??1,θ??2,…)。笔者只采用矩不变量的第一维分量。将矩不变量特征值等分成（预先给定的）K个小区间，然后将特征值落在第i个小区间的图像块归为第i??类，在搜索时只需要搜索值域块的特征值所在区间的定义域块。这样就减少了搜索次数，提高了编码速度。笔者称这种等分特征区间的方法为均匀分类法。??本文中所有实验都使用标准的256×256的灰度测试图像Lena；实验环境为P42．6GHz/256MBRAM/VC++；定义域块的大小都取为值域块的两倍，相邻定义域块的水平和垂直间隔都取为值域块的大小。在均匀分类的情况下，经过统计，几乎所有的定义域块的分布都呈现一种极少数区间包含大多数块的情况。图1是9×6和5×4的值域块对应的定义域块分布图，它们对应的定义域块数目分别为1107和3150。??从图中看出，各个区间定义域块数目的分布很不均匀，这导致以下后果：当值域块的矩不变量落在分布数目较多的区间时，搜索此区间相当耗时；而落在分布数目较少的区间时，则很难找到匹配块...