Determining correspondence between image regions

• US 8,285,055 B1
• Filed: 02/27/2009
• Issued: 10/09/2012
• Est. Priority Date: 09/10/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Goldman, Dan, Barnes, Connelly, Shechtman, Elya
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US12/394,280
• Time in Patent Office: 1,320 Days
• Field of Search: 382/195, 382/199, 382/164, 382/108, 382/159, 382/165, 382/170, 382/118, 382/205, 382/206, 382/209, 348/119, 348/E7.085, 340/435, 701/4, 701/100, 713/176
• 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 of determining correspondence between image regions, the 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.

2. The method of claim 1, wherein the result reflects a nearest-neighbor calculation between the first and second regions.

3. The method of claim 2, wherein the iterative evaluations are performed using an offset object that is iteratively improved by the iterative evaluations, the offset object including offsets corresponding to at least the first, second and third mappings between the first and second regions.

4. The method of claim 3, wherein a random offset value is used for the first mapping in an initial one of the iterative evaluations.

5. The method of claim 3, wherein a seed offset value is used for the first mapping in an initial one of the iterative evaluations.

6. The method of claim 3, wherein an external constraint offset value is used for the first mapping in an initial one of the iterative evaluations.

7. The method of claim 3, further comprising:

performing a search before an initial one of the iterative evaluations, wherein the initial one of the iterative evaluations uses an approximate nearest neighbor for the first patch found in the search.

8. The method of claim 3, wherein the first evaluation phase in the iterative evaluations comprises looping through each pixel in the offset object to improve on the first mapping.

9. The method of claim 8, wherein the nearby pixels in the first evaluation phase are selected in a fixed spatial neighborhood of the first patch.

10. The method of claim 3, wherein the offset object is represented as an offset image and wherein the first evaluation phase in the iterative evaluations comprises a propagation within pixels of the offset image, the method further comprising:

having the propagation occur in a predefined order in the iterative evaluations.

11. The method of claim 10, wherein the predefined order comprises 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 method of claim 1, wherein the second evaluation phase in the iterative evaluations comprises a random search in the 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. The method of claim 12, wherein the random search is performed by sampling only those points whose distance is within an exponentially decreasing threshold from the mapping of the first patch.

14. The method of claim 1, wherein the iterative evaluations are performed for, and the result used in, at least one implementation selected from:

computation of a bidirectional similarity between at least one image;

a bidirectional synthesis;

a dense patch-sampling synthesis method;

a patch-sampling optimization-based synthesis algorithm;

an image retargeting;

an interactive image editing application;

a view interpolation;

a texture synthesis;

a solid texture synthesis, an image completion or inpainting;

an image retargeting;

an image collage;

image tapestry, image stitching, video tapestry, an image reshuffling, an image recomposition, a visual copy-paste editing, a visual cut-paste editing, shape/model retargeting, shape completion, shape synthesis, shape stitching, shape reshuffling, and shape paste editing operations;

any previously mentioned technique being applied to video content, and combinations thereof.

15. The method of claim 14, wherein the implementation involves video content represented by three-dimensional data, the patches are three-dimensional patches and searching is performed in space-time.

16. The method of claim 14, wherein the implementation involves a three-dimensional shape or model, the patches are three-dimensional and searching is performed in a three-dimensional space.

17. The method of claim 1, wherein the result is recorded as part of performing a gradient domain reconstruction of an image.

18. The method of claim 17, wherein performing the gradient domain reconstruction comprises:

reconstructing gradients of the image and colors of the image separately; and

reconstructing the image from the gradients.

19. The method of claim 18, wherein reconstructing the image from the gradients comprises at least one selected from:

using the colors as a regularization term;

using the colors as an initialization condition;

using the colors as a boundary condition; and

combinations thereof.

20. The method of claim 1, wherein the second mapping is perturbed using at least one function selected from:

a random sampling pattern, a deterministic sampling pattern, an arbitrary mathematical perturbation function, and combinations thereof.

21. The method of claim 1, wherein the second mapping is perturbed using a combination of large and small perturbations.

22. 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.

23. 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 O_S 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 O_S is replaced with a second mapping obtained from a pixel nearby the first patch in the offset object O_S 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 O_S 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.

24. The method of claim 23, further comprising having the propagation occur in a predefined order in the propagation phase between the iterative evaluations.

25. The method of claim 24, wherein the predefined order comprises at least one of:

an alternation in diametrically opposed directions;

an alternation in random order; and

an alternation according to a space-covering pattern.

26. The method of claim 23, wherein the second evaluation in the iterative evaluations comprises a random search in the 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, and wherein the random search is performed by sampling only those points whose distance is within an exponentially decreasing threshold from the mapping of the first patch.