In Fractal image coding (FIC), a partitioning of the original image into ranges and domains is required, which greatly affects the coding performance. Usually, the more adaptive to the image content the partition is, the higher performance it can achieve. Nowadays, some alleged Region-based fractal coders (RBFC) using split-and-merge strategy can achieve better adaptivity andperformance compared with traditional rectangular block partitions. However, the regions are still with linear contour. In this paper, we present a Freely-shaped Regionbased fractal coder (FS-RBFC) using a two-step partitioning, i.e. coarse partitioning based on fractal dimension and fine partitioning based on region growth, which brings freely-shaped regions. Our highly image-adaptive scheme can achieve better rate-distortion curve than conventional scheme, even more visually pleasing results at the same performance.