Fast Fractal Image Encoding Based on Mean Deviation-ordered
基于平均偏差排序的快速分形图像编码

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.