The fractal image encoding method has received much attention for its many advantages over other methods,such as high decoding quality at high compression ratios. However, because every range block must be compared to all domain blocks in the codebook to find the best-matched one during the coding procedure, baseline fractal coding (BFC) is quite time consuming. To speed up fractal coding, a new fast fractal encoding algorithm is proposed. This algorithm aims at reducing the size of the search window during the domain-range matching process to minimize the computational cost. A new theorem presented in this paper shows that a special feature of the image can be used to do this work. Based on this theorem, the most inappropriate domain blocks, whose features are not similar to that of the given range block, are excluded before matching. Thus, the best-matched block can be captured much more quickly than in the BFC approachThe experimental results show that the runtime of the proposed method is reduced greatly compared to the BFC method. At the same time,the new algorithm also achieves high reconstructed image quality. In addition,the method can be incorporated with other fast algorithms to achieve better performance.Therefore, the proposed algorithm has a much better application potential than BFC.