Abstract: To reduce the long encoding time in fractal compression process which limits its various practical applications, the paper proposes a newly-defined subregion diagonal sum of normalized image block.After sorting the blocks in the codebook according to their subregion diagonal sum, the encoder finds out the nearest domain block in sorted codebook to each range block being encoded in the sense of subregion diagonal sum, then the encoder visits the codebook blocks in the vicinity of this nearest domain block to search out the best-matched block.Experimental results show that the proposed algorithm can significantly improve coding speed with the gurantee of decoded image′s quality.