Fast fractal image encoding using one-norm of normalised block

The baseline fractal image encoding with full search typically requires a very long encoding time, which is essentially spent on searching for the best-matched block to an input range block in a large domain pool. In this paper, one-norm of normalised block is first utilized to avoid the excessive search, in which the search process might be early terminated, and thus remaining domain blocks could be safely discarded. Then the encoding schemes proposed recently by the authors are used to further reduce the search space and improve the decoded image quality. Experiments show that, for three popular 512×512 test images, the proposed algorithm can averagely reduce the runtime by about 40 times while there is averagely the PSNR gain of 0.91dB, in comparison with the baseline fractal algorithm. Besides, when combined with the kick-out condition and the zero contrast prediction proposed recently by Lai et al. [Lai CM, Lam KM, Siu WC. A fast fractal image coding based on kick-out and zero contrast conditions. IEEE Trans Image Process 2003:11;1398–403], the combined algorithm further reduced the runtime by about 10% while maintaining the same PSNR exactly as that of the proposed algorithm.