Abstract: The full search fractal image encoding algorithm is based on the partitioned iteration function system, its encoding process requires a very long run-time, which limits its practical application. By defining the sub-block features of each range block and domain block, this paper thus proposes an effective method of liming the search space to improve the drawback, which is mainly based on inequality linking the root-mean-square and image sub-block feature. During the search process, the image sub-block feature is utilized to confine efficiently the search space to the vicinity of the domain block having the closest image sub-block feature to the input range block being encoded, aiming at reducing the searching scope of similarity matching to accelerate the encoding process. Simulation results of fourteen test images show that the proposed scheme can averagely reduce the run-time by about 99 times while there is averagely the [PSNR] decrease of 0.73 dB（the structural similarity decrease of 0.002）, in comparison with the full search fractal algorithm.Moreover, it is better than the other feature algorithm.

Key words: image compression, fractal, fractal image coding, image sub-block feature

摘要： 基于分块迭代函数的全搜索分形图像编码算法，因其编码过程特别耗时而限制了它的诸多应用。为了减少编码时间，通过定义每个range块和domain块的子块特征，根据匹配均方根误差与它的关系，设计出一个限制搜索空间的新算法。一个待编码range块和它的最佳匹配domain块的子块特征应该接近，因此，每个range块的最佳匹配块搜索范围仅限定在与其子块特征接近的domain块邻域内，以达到加快编码过程的目标。14幅图像的仿真结果表明，该算法能够在[PSNR]降低0.73 dB（其结构相似性[SSIM]值仅下降0.002）的情况下，平均加快全搜索分形编码算法的编码速度99倍左右，而且也优于其他特征算法。

关键词: 图像压缩, 分形, 分形图像编码, 图像子块特征