Determining correspondence between image regions

• US 8,811,749 B1
• Filed: 09/10/2012
• Issued: 08/19/2014
• Est. Priority Date: 09/10/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Barnes, Connelly, Goldman, Dan, Shechtman, Elya
• Primary Examiner(s): Do, Anh
• Application Number:
  US13/607,965
• Time in Patent Office: 708 Days
• Field of Search: 382/108, 382/195, 382/199, 382/218, 382/278, 380/270, 380/277, 370/258, 370/403, 370/410, 345/629, 435/325, 435/366, 435/374, 600/508, 600/509, 600/523, 715/201, 715/204, 726/11, 726/14, 455/11.1, 455/12.1, 455/13.1
• US Class Current: 382/195
• CPC Class Codes: G06T 7/337 involving reference images or patches

Abstract

Determining correspondence between image regions includes identifying first and second regions of visual content including pixels in a computer system. The first region includes a first patch of pixels having a first mapping to a second patch of pixels in the second region. Iterative evaluations of the first and second regions are performed, each 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. A result of the iterative evaluations is recorded in the computer system that indicates a third patch of pixels in the second region identified in the iterative evaluations.

Claims

1. A method comprising:

identifying a mapping assigned to a first patch by one or more processor-based devices;

propagating the identified mapping to a second patch to generate a propagated mapping by the one or more processor-based devices;

perturbing the propagated mapping to generate a perturbed mapping by the one or more processor-based devices; and

assigning one of the propagated mapping and the perturbed mapping to the second patch by the one or more processor-based devices.

2. The method of claim 1, further comprising performing iterations of propagations and perturbations using an offset object that is iteratively improved by the iterations, the offset object including offsets corresponding to at least the propagated and perturbed mappings.

3. The method of claim 2, further comprising:

performing a k-d tree search;

generating one or more patch offsets based on the performed k-d tree search; and

initializing the offset object using the generated one or more patch offsets.

4. The method of claim 2, further comprising using an external constraint offset value for an initial one of the iterations.

5. The method of claim 2, wherein the iterations of propagations are performed according to at least one of:

an alternation in diametrically opposed directions;

an alternation in random order; and

an alternation according to a space-covering pattern.

6. The method of claim 1, wherein the iterations of perturbations comprise a random search in an offset space with a random distribution that includes large and small distances, the small distances selected more preferentially in the random distribution than would be obtained from uniform sampling.

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

identifying a mapping assigned to a first patch;

propagating the identified mapping to a second patch to generate a propagated mapping;

perturbing the propagated mapping to generate a perturbed mapping; and

assigning one of the propagated mapping and the perturbed mapping to the second patch.

8. The computer program product of claim 7, the method further comprising performing iterations of propagations and perturbations using an offset object that is iteratively improved by the iterations, the offset object including offsets corresponding to at least the propagated and perturbed mappings.

9. The computer program product of claim 8, the method further comprising:

performing a k-d tree search;

generating one or more patch offsets based on the performed k-d tree search; and

initializing the offset object using the generated one or more patch offsets.

10. The computer program product of claim 8, the method further comprising using an external constraint offset value for an initial one of the iterations.

11. The computer program product of claim 7, wherein the iterations of propagations are performed according to at least one of:

an alternation in diametrically opposed directions;

an alternation in random order; and

an alternation according to a space-covering pattern.

12. The computer program product of claim 7, wherein the iterations of perturbations comprise a random search in an offset space with a random distribution that includes large and small distances, the small distances selected more preferentially in the random distribution than would be obtained from uniform sampling.

13. A system comprising:

one or more processors; and

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

identifying a mapping assigned to a first patch;

propagating the identified mapping to a second patch to generate a propagated mapping;

perturbing the propagated mapping to generate a perturbed mapping; and

assigning one of the propagated mapping and the perturbed mapping to the second patch.

14. The system of claim 13, the method further comprising performing iterations of propagations and perturbations using an offset object that is iteratively improved by the iterations, the offset object including offsets corresponding to at least the propagated and perturbed mappings.

15. The system of claim 14, the method further comprising:

performing a k-d tree search;

generating one or more patch offsets based on the performed k-d tree search; and

initializing the offset object using the generated one or more patch offsets.

16. The system of claim 14, the method further comprising using an external constraint offset value for an initial one of the iterations.

17. The system of claim 13, wherein the iterations of propagations are performed according to at least one of:

an alternation in diametrically opposed directions;

an alternation in random order; and

an alternation according to a space-covering pattern.

18. The system of claim 13, wherein the iterations of perturbations comprise a random search in an offset space with a random distribution that includes large and small distances, the small distances selected more preferentially in the random distribution than would be obtained from uniform sampling.