As a structure-based image compression technology, fractal image compression (FIC) has been applied not only in image coding but also in many important image processing algorithms. However, two main bottlenecks restrained the develop and application of FIC for a long time. First, the encoding phase of FIC is time-consuming. Second, the quality of the reconstructed images for some images which have low structure-similarity is usually unacceptable. Based on the absolute value of Pearson's correlation coefficient (APCC), we had proposed an accelerating method to significantly speed up the encoding of FIC. In this paper, we make use of the sparse searching strategy to greatly improve the quality of the reconstructed images in FIC. We call it the sparse fractal image compression (SFIC). Furthermore, we combine both the APCC-based accelerating method and the sparse searching strategy to propose the fast sparse fractal image compression (FSFIC), which can effectively improve the two main bottlenecks of FIC. The experimental results show that the proposed algorithm greatly improves both the efficiency and effectiveness of FIC.