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.