Abstract: Fractal image coding is an efficient image compression technique which is based on the local self-similarities within real world images.The main drawback of this technique is that，for each range block，searching out the best-matched domain block is extremely time consuming.By an inequality linking the root-mean-square and mean deviation，the proposed algorithm sets up a kick-out condition based on the mean deviation to avoid the excessive search，in which the search process might be early terminated，and thus remaining domain blocks could be discarded，so its runtime is significantly shortened.Computer simulations on 3 test images with different complexities demonstrate that the proposed scheme could averagely achieve the speed-up of 60 times as the baseline fractal algorithm with full search，while it gives an insignificant degradation in the subjective quality of the decoded image.