Determining correspondence between image regions

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.