Fractal theory has been widely applied in the field of image compression due to its advantages of resolution independence, fast decoding, and high compression ratio. However, it has a fatal shortcoming of intolerant encoding time for every range block to find its corresponding best matched domain block. In this work, an algorithm is proposed to improve this time-consuming encoding drawback by an adaptive searching window, partial distortion elimination (PDE), and characteristic exclusion algorithms. The proposed methods efficiently decrease the encoding time. In addition, the compression ratio is also raised due to the reduced searching window. While conventional full search fractal encoding to compress a 512×512 image needs to search 247,009 domain blocks for every range block, our experimental results show that our proposed method only needs to search 122 domain blocks, which is only 0.04939% compared to a conventional fractal encoder for every range block to encode a Lena 512×512 8-bit gray image at a bit rate of 0.2706 bits per pixel (bpp) while maintaining almost the same decoded quality in visual evaluation. In addition, the visual decoded quality of the proposed method is better than the most widely used JPEG compressor.