Abstract: Fractal image coding can provide a high decoded image quality at a high compression ratio, but it requires traditionally a very long runtime in the encoding process. Therefore, it is essential to develop fast encoding algorithms before it could be widely used for various applications. The encoding time is mostly spenton searching for the best-matched block to an input range block in a usually-large domain pool; a new scheme is thus proposed to limit the search space in this paper. It first defines a new feature, quincunx sum, which is the intensities sum of a normalised image block over each corner of the block and one at the centre. Then, the quincunx sum is utilized to confine efficiently the search space to the vicinity of the initial-matched block (i.e., the domain block having the closest absolute quincunx sum to that of the input range block being encoded). Experimental results show that this method can reduce drastically the amount of range-domain comparisons needed to encode each range block. The proposed algorithm has also been compared with the fast fractal encoding algorithm based on cross-trace, showing that under the same search neighborhood it performs better in terms of encoding time, image quality and compression rate.