Fractal image encoding is attractive due to its potential high compression ratio, fast decompression and multi-resolution properties. However, the encoding time is computationally intensive. In this paper, a new method is proposed to reduce the encoding time based on computing the gray level difference and normal variance of domain and range blocks. Proposed method only compares those domain blocks whose gray level difference and normal variance (obtained from dividing variance on gray level difference) are higher than those of the range blocks. This method reduces the number of comparisons, and thereby the encoding time considerably, while obtaining good fidelity and compression ratio for the decoded image. Experimental results on standard grayscale images (256??256, 8bit) show that the proposed method yields superior performance over conventional fractal encoding.