Determining correspondence between image regions

• US 8,571,328 B2
• Filed: 08/16/2010
• Issued: 10/29/2013
• Est. Priority Date: 08/16/2010
• Status: Active Grant

• Current Assignee: Adobe Inc., The Trustees of Princeton University (Princeton University)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Shechtman, Elya, Goldman, Dan, Barnes, Connelly, Finkelstein, Adam
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US12/857,294
• Publication Number:
  US 20130163874A1
• Time in Patent Office: 1,170 Days
• Field of Search: 382/209, 382217-222
• US Class Current: 382/218
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 10/759 Region-based matching

Abstract

Determining correspondence between image regions can include: selecting first and second regions of visual content including pixels in a computer system, the first region comprising a first patch to be mapped to the second region; selecting at least two heuristics for use in mapping the first patch to the second region, the heuristics selected from the group consisting of: (i) nearby-pixel mapping evaluation; (ii) random-perturbation mapping evaluation; (iii) evaluation of multiple mapping candidates identified in an iterative search process; and (iv) enrichment to increase a collection of mapping candidates; and identifying, using the selected heuristics, at least one patch in the second region for the first patch.

Claims

1. A computer-implemented method for determining correspondence between image regions, the method comprising:

selecting, by a computer system, first and second regions of visual content that includes pixels, the first region comprising a first patch to be mapped to the second region;

performing iterations to find mappings for the first patch, the iterations including nearby-pixel mapping evaluation and random-perturbation mapping evaluation, at least one of the nearby-pixel mapping evaluation or the random-perturbation mapping evaluation performed on a different number of candidate patches than second patches found in the second region in at least one of the iterations; and

recording the second patches in the second region found using the iterations.

2. The method of claim 1, wherein a heap reflecting patch distance from the first patch is used in the iterations to find the second patches, the heap corresponding to k patches, the method further comprising:

determining whether a new patch from the iterations has a smaller patch distance from the first patch than one of the k patches that has a greatest patch distance in the heap; and

if so, removing the patch that has the greatest patch distance from the heap, and adding the new patch to the heap.

3. The method of claim 2, further comprising:

eliminating any duplicate patches from the k patches before determining patch distance.

4. The method of claim 2, wherein the random-perturbation mapping evaluation involves selecting n sample patches for each of the k patches in the heap, for a total of nk sample patches, the method further comprising:

eliminating any duplicate patches from the nk sample patches before determining patch distance.

5. The method of claim 1, further comprising:

randomly selecting k patches in the second region for use in an initial one of the iterations.

6. The method of claim 1, further comprising:

retaining all patches identified by the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation; and

recording, as the second patches, a subset of the retained patches having a smallest patch distance.

7. The method of claim 1, wherein the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation are configured to result in a single patch being identified in the second region, the method further comprising:

defining a constraint for each iteration of the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation, the constraint prohibiting selection of a patch previously selected;

retaining all patches identified by the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation; and

recording the retained patches as the second patches.

8. The method of claim 1, further comprising:

randomly selecting, before performing the evaluation, a subset from all candidate patches based on a smaller patch distance, wherein the evaluation is performed on the subset.

9. The method of claim 1, wherein the evaluation is performed on a greater number of the candidate patches than the second patches.

10. The method of claim 1, wherein the second region is identical to the first region.

11. The method of claim 10, further comprising:

determining, in the iterations and for each patch in the first region, neighbor mappings to neighbor patches in the second region;

determining, in the iterations and for each of the neighbors, neighbor'"'"'s neighbor mappings to the first region;

selecting a number of hops to make along the neighbor mappings and the neighbor'"'"'s neighbor mappings;

identifying, for each patch in the first region, third patches by sequentially following the neighbor mappings, and the neighbor'"'"'s neighbor mappings, for the number of hops; and

selecting the second patches for each patch in the first region among the corresponding third patches.

12. The method of claim 10, further comprising:

determining, in the iterations and for each patch in the first region, neighbor mappings to neighbor patches in the second region;

selecting a number of hops to make backwards along the neighbor mappings;

identifying, for each patch in the first region, third patches by sequentially following the neighbor mappings backwards for the number of hops, the neighbor patches being included in the third patches; and

selecting the second patches for each patch in the first region among the corresponding third patches.

13. The method of claim 1, further comprising:

horizontally dividing offsets generated by the iterations into tiles; and

handling each tile using a separate core in a multi-core architecture of the computer system.

14. The method of claim 13, further comprising:

constraining a writing of output from the nearby-pixel mapping evaluation with regard to updating of the tiles.

15. The method of claim 1, further comprising:

selecting an image descriptor for the first and second regions;

selecting a distance metric for evaluating mappings for the first patch; and

wherein the iterations use the selected image descriptor and the selected distance metric.

16. The method of claim 1, wherein a warping action is performed on at least one of the second patches in at least one of the iterations.

17. A system comprising:

a computer readable storage memory device configured to store visual content including pixels, the visual content including a first region with a first patch to be mapped to a second region in the visual content;

a processor to implement iterations of a propagation component and a random-search component, the propagation component configured to perform nearby-pixel mapping evaluation to find mappings for the first patch and the random-search component configured to perform random-perturbation mapping evaluation to find mappings for the first patch, at least one of the nearby-pixel mapping evaluation or the random-perturbation mapping evaluation performed on a different number of candidate patches than second patches found in the second region in at least one of the iterations; and

the computer readable storage memory device further configured to store the second patches of the second region found by at least one of the propagation component and the random-search component.

18. A computer-implemented method for determining correspondence between image regions, the method comprising:

selecting, by a computer system, an image descriptor for first and second regions of visual content, the first region comprising a first patch to be mapped to the second region;

selecting a distance metric for evaluating mappings for the first patch;

performing iterations to find the mappings for the first patch, the iterations including nearby-pixel mapping evaluation and random-perturbation mapping evaluation, the iterations using the selected image descriptor and the selected distance metric, as well as a heap reflecting patch distance from the first patch to find second patches in the second region, the heap corresponding to k patches;

determining whether a new patch from the iterations has a smaller patch distance from the first patch than one of the k patches that has a greatest patch distance in the heap, and if so, removing the patch that has the greatest patch distance from the heap and adding the new patch to the heap;

eliminating any duplicate patches from the k patches before determining patch distance; and

recording at least one second patch in the second region found using the iterations.

19. The method of claim 18, wherein multiple second patches are found using the iterations and recorded.

20. The method of claim 18, wherein a warping action is performed on the second patch in at least one of the iterations.

21. A computer-implemented method for determining correspondence between image regions, the method comprising:

selecting, by a computer system, first and second regions of visual content that includes pixels, the first region comprising a first patch to be mapped to the second region;

performing iterations to find mappings for the first patch, the iterations including nearby-pixel mapping evaluation and random-perturbation mapping evaluation, the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation configured to result in a single patch being identified in the second region;

defining a constraint for each iteration of the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation, the constraint prohibiting selection of a patch previously selected;

retaining all patches identified by the nearby-pixel mapping evaluation and the random-perturbation mapping evaluation; and

recording the retained patches as the second patches found using the iterations.

22. The method of claim 21, further comprising:

performing a warping action on the second patches in the second region in at least one of the iterations, and wherein the warping action includes at least one of a rotation, a scaling, a transformation, and a homography.

23. The method of claim 21, wherein multiple second patches are found using the iterations and recorded.

24. The method of claim 21, further comprising:

selecting an image descriptor for the first and second regions;

selecting a distance metric for evaluating the mappings for the first patch; and

wherein the iterations use the selected image descriptor and the selected distance.

25. A computer-implemented method for determining correspondence between image regions, the method comprising:

selecting, by a computer system, first and second regions of visual content that includes pixels, the first region comprising a first patch to be mapped to the second region;

selecting at least two heuristics for use in mapping the first patch to the second region, the heuristics selected from the group consisting of;

(i) nearby-pixel mapping evaluation;

(ii) random-perturbation mapping evaluation;

(iii) evaluation of multiple mapping candidates identified in an iterative search process; and

(iv) enrichment to increase a collection of mapping candidates;

utilizing a heap reflecting patch distance from the first patch to find second patches in the second region, the heap corresponding to k patches;

determining whether a new patch from the iterations has a smaller patch distance from the first patch than one of the k patches that has a greatest patch distance in the heap, and if so, removing the patch that has the greatest patch distance from the heap, and adding the new patch to the heap;

eliminating any duplicate patches from the k patches before determining patch distance; and

identifying, using the selected heuristics, at least one patch in the second region for the first patch.