In this paper, a new fractal image coding algorithm is presented to process imag e coding by difference and approximation with various grey levels because the co ding time of classical fractal image coding algorithm is very long. In addition, some researches with respect to its feasibility in compression theory are also discussed and the theoretical foundation of the new algorithm is given. Based on the idea, a new concrete algorithm for realizing fractal image coding is design ed in the paper. The experimental results show that the new algorithm can improv e compression ratio and reconstruct high quality images while computational time of image coding is reduced greatly.