Compression of an image is performed based on prediction of target blocks of an image from candidate source blocks of the image. Heuristics are used for identifying the candidate source blocks, for example, source blocks are selected from within a cluster of similar blocks obtained by K-means clustering. For each target block, a region adjacent to the target block is identified and a set of candidate source blocks along with candidate source regions adjacent to the candidate source blocks are identified. The candidate source regions are ranked based on the differences between the candidate source regions and the target source region. Each candidate source block is described using its rank and residual information describing differences between the candidate source block and the target block. The candidate source block that can be described using a minimum amount of information is selected for predicting the target block.