To reduce the long encoding time of fractal compression algorithm, this paper proposes an improved algorithm. It uses the similar characteristics of sub-block, and converts the basic fractal image coding’s entire search into the nearest neighbor search of a relative di fference defined in this paper, and to the only search of the domain blocks which have the same difference. This method can reduce the search space.Experimental results demonstrate that, compared with the basic fractal image coding, the proposed algorithm can speed up the encoding process with the gurantee of the image’s quality.