One of the main drawbacks of fractal im-age coding (FIC) is its time-consuming encoding process. So how to speed up the encoding process is a challenging issue of FIC research. As both sequential solutions and parallel ones have their advantages and disadvantages, we combine them together to further speed up the encoding phase. In this paper a derivative tree topology is first pro-posed to provide support for complex parallelism. Then a dual-classification technique is designed for speeding up the fractal image coding with Same-Sized Block Mapping, which improves the decoded image quality. Finally, some experimental results with good performance are presented.