In fractal image compression (FIC) an image is divided into sub-images (domains and ranges), and a range is compared with all possible domains for similarity matching. However this process is extremely time-consuming. In this paper, a novel sub-image classification scheme is proposed to speed up the compression process. The proposed scheme partitions the domain pool hierarchically, and a range is compared to only those domains which belong to the same hierarchical group as the range. Experiments on standard images show that the proposed scheme exponentially reduces the compression time when compared to baseline fractal image compression (BFIC), and is comparable to other sub-image classification schemes proposed till date. The proposed scheme can compress Lenna (512x512x8) in 1.371 seconds, with 30.6 dB PSNR decoding quality (140x faster than BFIC), without compromising compression ratio and decoded image quality.