The Fractal image compression has the advantage of presenting fast decoding and independent resolution but it suffers of slow encoding phase. In the present study, we propose to reduce the computational complexity by using two domain pools instead of one domain pool and encoding an image in two steps (AP2D approach). AP2D could be applied to classification methods or domain pool reduction methods leading to more reduction in encoding phase. Indeed, experimental results showed that AP2D speed up the encoding time. The time reduction obtained reached a percentage of more than 65% when AP2D was applied to Fisher classification and more than 72% when AP2D was applied to exhaustive search. The image quality was not altered by this approach while the compression ratio was slightly enhanced.