Determining correspondence between image regions

A computer program product tangibly embodied in a non-transitory tangible program carrier and comprising instructions that when executed by a processor perform a method comprising:

• identifying first and second regions of visual content including pixels in a computer system, the first region comprising a first patch of pixels having a first mapping to a second patch of pixels in the second region;
• performing iterative evaluations of the first and second regions, each iterative evaluation including at least (i) a first evaluation phase selecting a best mapping for the first patch, according to a distance metric, the best mapping selected from among the first mapping and a second mapping obtained from mappings of nearby pixels, and (ii) a second evaluation phase selecting one of the best mapping and a third mapping obtained by perturbing the second mapping;
• and
• recording a result of the iterative evaluations in the computer system that indicates a third patch of pixels in the second region identified in the iterative evaluations.

A method of determining correspondence between image regions, the method comprising:

• identifying an image S and an image T for which a nearest-neighbor correspondence is to be estimated, the image S comprising a set Q of pixel patches and the image T comprising a set P of pixel patches;
• initializing an offset object OS for the image S comprising offset values for mapping the image S to the image T, including a first mapping for a first patch in the set Q to a second patch in the set P;
• performing, using one or more processors, iterative evaluations of the first and second images, each iterative evaluation comprising:
• (i) a propagation phase wherein the first mapping in the offset object OS is replaced with a second mapping obtained from a pixel nearby the first patch in the offset object OS upon determining that the second mapping is better for the first patch than the first mapping according to a distance metric;
• and
• (ii) a perturbation phase wherein the first or second mapping resulting from the propagation phase is replaced with a third mapping obtained by perturbing the second patch upon determining that the third mapping is better for the first patch than the first or second mapping according to the distance metric;
• terminating the iterative evaluations based on a stopping criterion;
• and
• recording a result based on the offset object OS that associates at least one of the pixel patches in the set Q with at least one of the pixel patches in the set P.