In conventional fractal decoding procedure, the reconstructed image is obtained by a rpredefined number of iterations starting with an arbitrary initial image. Its convergence speed depends on the selection of the initial image. It should be solved to get high speed convergence. In this paper, we theoretically reveal that conventional method is approximately decomposed into the decoding of the DC and AC components. Based on this fact, we proposed a novel fast fractal decoding algorithm made up of two steps. The averaged-image considered as an optimal initial image is estimated in the first step. In the second step, the reconstructe dimag eis genrated from the output image obtained in the first step. From the simulations, it is shown that the output image of the first step approximately converges to the averaged-image with only 15% calculations for one iteration of conventional method. And the proposed method is faster than various decoding mehtods and evenly equal to conventioanl decoding with the averaged-image. In addition, the proposed method can be applied to the compressed data resulted from the various encoding methods because it does not impose any constraints in the encoding procedure to get high decoding speed.