Abstract: Starting from reducing the unnecessary computation, the basic fractal image compression algorithm introduced by A.E. Jacquin is improved with a fractal image compression algorithm proposed on error threshold basis. A fixed error threshold is given to compute the total accumulative pixel error of corresponding finite pixels between the child blocks and father blocks, which is then used to find the father block most similar to child block. Experiments indicate that the proposed algorithm can obviously shorten the time of fractal image compression with little changes in compression and signal-to-noise ratios.