Abstract: Fractal image compression has received much attention for its desirable properties like resolution independence, fast decoding and high compression ratio. Despite the advances made, the long computing times in the encoding phase still remain the main drawback of this technique. So far, several methods have been proposed in order to speed up fractal image coding. In this paper, some commonly used speed up algorithms are introduced briefly, and a new algorithm is put forward, which uses notation of feature difference based on the contraction characteristics of transformations in fractal image coding. The algorithm can be simply realized in corporation with many other speedup methods and efficiently exclude pseudo matched blocks in D R matching and searching process. Experimental result shows that the algorithm not only speedups the coding process but also greatly improves the quality of decoded image.