Long coding time is the main problem in image compression based on Fractal at present

mainly due to its heavy computation of searching the best-match domain block for each range block.In this paper

a fast K-mean clustering algorithm is proposed firstly using Partial Distortion Search to replace the time-consuming Nearest Neighbor Search process in traditional K-mean clustering algorithm.Then the K-mean clustering algorithm is used to speed up the coding: scheme the domain blocks and search the best-match block for each range block in some nearest neighbors from some nearest clusters.Furthermore

by combining other techniques such as excluding planar blocks and building domain pool from an averaged image

a fast and adjustable fractal coding scheme is obtained.Experimental results indicate that comparing to exhaustive search

the proposed method improves the coding speed and compression ratio greatly with slight quality degradation of decoded image.