This paper presents work carried out on fractal (or attractor) image c
ompression. The approach relies on the assumption that image redundanc
y can be efficiently exploited through self-transformability. The algo
rithms described in this paper utilize a novel region-based partition
of the image that greatly increases the compression ratios achieved ov
er traditional block-based partitionings. Due to the large search spac
es involved, heuristic algorithms are used to construct these region-b
ased transformations. Results for three different heuristic algorithms
are given. The results show that the region-based system achieves alm
ost double the compression ratio of the simple block-based system at a
similar decompressed image quality. For the Lena Image, compression r
atios of 41:1 can be achieved at a PSNR of 26.56 dB.