An efficient algorithm for detecting duplicate regions is proposed in this paper. The basic idea is to segment the input image into blocks and search for blocks with similar intensity patterns using matching techniques. To improve the efficiency, the blocks are sorted based on the concept of k-dimensional tree. The sorting process groups blocks with similar patterns and hence the number of matching operations required for finding the duplicated blocks can be significantly reduced. The matching block detection results are encoded as a color image. This makes it possible to use a set of colour-based morphological operations to remove isolated mismatches, as well as to fill in missing matches. The experiments conducted show the effectiveness of the proposed algorithm.