Abstract: Fractal image coding requires traditionally a very long runtime，which is mostly spent on searching for the best matched block to an input range block in a usually large domain pool.Based on the cross-trace algorithm proposed by these authors，a fast algorithm is proposed in this paper.It utilizes a newly-defined feature，i.e.，a semi-norm of normalized block，to confine the search space to the vicinity of the initial matched block（i.e.，the domain block having the closest semi-norm to that of the input range block being encoded）.The experiments show that the proposed algorithm performs better in terms of encoding time and image quality，compared with the cross-trace algorithm.

Key words: image compression, fractal, iterated function system, fractal image coding, semi-norm

摘要： 分形图像编码通常需要较长的时间，编码时间主要花费在一个海量码本中搜索每个输入子块的最佳匹配块。在提出的叉迹算法的基础上，提出一种快速编码算法。它主要利用一种新定义的特征——规范块半范数，把搜索范围限制在初始匹配块（在半范数意义下与输入子块最接近的码块）的邻域内。实验显示，与叉迹算法比较，该算法在编码时间和图像质量方面都取得了更好的效果。

关键词: 图像压缩, 分形, 迭代函数系统, 分形图像编码, 半范数