Abstract: In this paper,we first present a fast K-mean clustering algorithm by using Partial Distortion Search (PDS) to complete the nearest neighbor searching in traditional K-mean clustering algorithm.Then we use the improved algorithm to speed up fractal image coding:cluster the domain blocks and build a KD-Tree for each cluster;and for each range block,its best-match domain block is obtained by PDS and approximate nearest neighbor searching (ANNS) from some nearest neighbors of each of some nearest KD-Trees. Experimental results show that,in comparison with exhaustive searching,only with slight degradation of decoded image quality,the proposed method improves the coding speed and compression ratio greatly,and in contrast to similar methods,it provides better speed-up and image quality under the same compression ratio.