Abstract: Traditional fractal coding has been widely applied to the image compression due to the high compression ratio. But the encoding in fractal image compressions are very time-consuming, because a large numbers of sequential search through a list of domains are needed to find the best match for a given range block. The Complex Exponent Moments (CEMs) are shift, rotation, scale and intensity distorted-invariant. This invariance can be used to match fractal image, and 2-D Fast Fourier Transform (FFT) algorithm is easily used to calculate CEMs. An effective fractal image compression based on CEMs and fuzzy clustering is proposed in this paper. Firstly, domain blocks are categorized using fuzzy c-mean-clustering approach. Then range blocks are compared to find the best domain blocks based on the CEMs. It shows in experimental results that the encoding is speed up with better performance in contrast with other fractal algorithms.