In the general fractal image compression, each range block is approximated by a contractive transform of the matching domain block under the mean squared error criterion. In this paper, we propose a fractal image compression algorithm with perceptual distortion measure rather than the mean squared error. In the perceptual distortion measure, the background brightness sensitivity and edge sensitivity are used. To obtain the sensitivity of the background brightness for each pixel, the average value of the neighborhoods is calculated and applied to a quadratic function. In the edge sensitivity for each pixel, sum of the differences in the neighborhood is calculated and applied to a nonlinear function. The perceptual distortion measure is obtained by the multiplications of the background brightness sensitivity, the edge sensitivity, and the error between the range block and the transformed domain block. For the range blocks having large distortion, they are splitted and the same algorithm is applied for smaller blocks. Compared to the method with the mean squared error measure, 10% compression ratio improvement under the same image quality is achieved.