With many observations, we find that there exists a logarithmic relationship between the average collage error (ACER) and the PSNR quality of decoded images. By making use of ACER in the encoding process, the curve fitting result can help us to predict the PSNR quality of decoded images. Then, in order to reduce the computational complexity further, an accelerated version of the prediction method is proposed. Firstly, a low limit of percentage of accumulated collage error (LLPACE) is proposed to evaluate the actual percentage of accumulated collage error (APACE). If LLPACE reaches a large value, such as 90%, the corresponding APACE can be proved to be limited in a small range (90%–100%) and the APACE can be estimated approximately. Thus, the remaining range blocks can be neglected and the corresponding computations can be saved. With the approximated APACE and the logarithmic relationship, the quality of decoded images can be predicted directly. Experiments show that, for four fractal coding methods, the quality of decoded images can be predicted accurately. Furthermore, the accelerated prediction method can provide competitive performance and reduce about one-third of total computations in the encoding process. Finally, the application of the proposed method is also discussed and analyzed.