Abstract: To reduce the computation time of fractal image coding, an approach based on classification and clustering is proposed. The image blocks are classified into different categories according to the fractal dimensions of image blocks, and the same category is then further divided into several clusters. Matching is done within the cluster, and the blocks in different categories are coded in different ways. Experiment shows that compared with the conventional fractal coding method (PIFS), the coding speed and compression ratio is increased significantly while the signal to noise ratio of it and the decoding image quality is acceptable.