分形图像编码是一种很有前途的压缩技术，但由于其编码时间长、计算复杂性高，因而阻碍了它的广泛应用，针对此问题，提出了一种快速的分形编码算法。这种算法是首先将码本按照平均偏差大小进行排序，然后使用二分搜索法寻找给定Range块在平均偏差意义下的最好匹配码块，进而利用一个联系均方根和平均偏差的不等式来在这个最好匹配码块的邻域中搜索Range块在均方根意义下的最佳匹配码块。实验结果显示，在主观质量略有下降的条件下，该算法编码过程显著快于基本分形算法。

Fractal image coding is a very promising compression technique, in which an image is encoded by a contractive transformation whose fixed point is close to the original image, and then is decoded by using the iteration procedure stemmed from Banach fixed-point theorem. However, it has not been widely used because of its long encoding time and high computational complexity. A fast fractal encoding algorithm is thus proposed in this paper. The proposed algorithm uses an inequality linking the root-mean-square (RMS) and mean intensity deviation to convert the range-domain block matching problem to the nearest neighbors search problem in the sense of mean deviations. In detail, after the codebook blocks are sorted according to their mean deviations of intensities, the encoder uses the bisection search method to find out the best matched codebook block regarding to mean deviations of a given range block. Because the closeness of mean intensity deviations of two blocks cannot ensure their good approximations in the RMS sense, the encoder utilizes the inequality to again search for the best-matched block (in the RMS sense) in the nearest k-neighbor of the best-matched block (in the sense of mean deviations) to a given range block in order to further improve the image quality. The experimental results demonstrate that the encoding procedure is much faster than that of the baseline fractal algorithm, while it gives an insignificant degradation in the subjective quality.