Techniques for determining correspondence between image regions are described. A computing system stores images that are comparable to determine corresponding image patches of the images. An approximation algorithm is implemented, and for multiple image patches in a region in a first image, corresponding image patches are determined in a second image. The approximation algorithm performs iterations utilizing a nearby-pixel mapping evaluation and a random-perturbation mapping evaluation to determine and select the corresponding image patches in the second image.