摘要：研究了分形编码过程中值域块与定义域块相似程度的分布特点，提出利用代间差分遗传算法优化其编码速度。实验结果证明了该方法的有效性。

关键词：图像压缩 分形编码 遗传算法

分形图像压缩技术是利用数字图像本身固有的自相似性，在分形理论的指导下，把图像数据转变为相关的分形参数，从而达到对数据进行压缩的目的。在一些情况下分形压缩可以达到非常高的压缩比，因此这是一种极具发展潜力的图像压缩技术。

分形图像压缩的概念首先由barnsley提出，但是barnsely基于ifs的分形压缩方法在实话时需要人机交互，无法实现自动化的压缩过程。1990年，janquin利用局部仿射变换代替全局仿射变换而提出了一种全自动的分形图像压缩方法，使这种图像压缩技术向实用化迈进一了步。janquin方式虽然解决了barnsley的子图分割问题，但是搜索最佳匹配块的计算量是十分可观的。为了减小计算量，从90年代起又有许多改进方法被提出，例如分类搜索法、四叉树搜索法等。这些方法虽然在一定程度上节约了搜索时间，但仍需进一步减小编码所需要的时间。

遗传算法是人类在自然进化的启发下发展的一种随机搜索算法，在大计算量面前具有快速自寻优的能力。目前人们已经开始利用遗传算法对分形编码的编码速度进行优化。本文为了进一步提高分形压缩的编码速度，深入研究了每个值域块、所有定义域块与其相似程度的分布特点，推导了适用于分形编码的代间差分遗传算法；然后利用代间差分遗传算法优化分形编码。实验表明代间差分遗传算法较变通遗传算法具有更快的收敛速度。

1 分形图像压缩的基本原理

分形理论是现代非线性科学中一门非常活跃且应用十分广泛的学科，特别随着计算机技术的发展，分形思想和方法在模式识别、自然图像的模拟、信号处理等各个领域都取得了巨大的成功。

分形编码的主要过程如下：首先将图像i分割成互不相交的值域块{ri}，对每个值域块，在整个图像范围寻找其在压缩、仿射变换下的最佳匹配定义域块di,记录下该定义域块和所采用的变换，完成了一个子块的编码；对于所有值域块{ri}重复上述过程分别寻找各自的最优匹配定义域块，即完成整幅图像的编码。

在仿射变换下，定义域和值域的误差可由下式确定：

所谓某个值域块ri的最优匹配定义域就是：在f映射下，定义域块和值域块使（1）式最小。利用janquin方法进行编码，为了找到具有最小误差err的定义域块，即最优匹配定义域块，每一个值域块ri需要匹配的定义域块数为（假设图像、定义域块以及值域块都是正方形）：

num=(图像大小-定义域块大小+1)2×仿射变换种数

例如，对于一个大小为256×256的图像，如果选取值域块为16×16，定义块为32×32，则每个值域块要搜索的定义域块为50625。可见该匹配过程的计算量非常大。

2 代间差分遗传算法的基本思想

遗传算法是一种具有内在并行性的优化算法，本文试图利用遗传算法的优化能力改善编码过程。同时针对分形编码过程的特点，为了提高算法的收敛速度，对遗传算法进行了改进，提出了带有代间差分杂交算子的遗传算法。

遗传算法中的杂交算子是一类非常重要的算子，杂交算子的性以也直接影响整个算法的收敛速度。本文提出的代间差分霜交算子其思想为：遗传算法是根据自然界中生物进化、适者生存的思想而发展的一种优化算法；随着种群进化代数的增加，在选择算子等的作用下，种群的平均适应值将以大概率增加。这样有理由假定种群的适应值将随着进化代数的增加而单调增加，从相邻两代种群中随机选择一个个体，则两个个体的差以一定概率代表了种群适应值增加的方向，也就是所希望的进化方向。因此可以利用相邻两代种群中个体的差来构成新的杂交算子，以产生新的个体，该新个体将以更高的概率向量优解靠近。

本文在不产生混淆的情况下，把采用代间差分杂交算子的遗传算法称为代间差分遗传算法。

3 基于代间差分遗传算法的快速分形压缩算法