Generating a modified image with semantic constraint

• US 8,355,592 B1
• Filed: 05/21/2009
• Issued: 01/15/2013
• Est. Priority Date: 05/06/2009
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Shechtman, Eli, Goldman, Dan
• Primary Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US12/454,661
• Time in Patent Office: 1,335 Days
• Field of Search: None
• US Class Current: 382/254
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually

Abstract

A computer-implemented method for generating a modified image includes initiating, in a computer device, a patch-based optimization algorithm for using a first image to generate a second image. The method includes identifying, in a computer device, a first feature of a first image. The identification corresponds to a constraint on the first feature for generating a second image, The constraint restricts at least one of location and geometric orientation in the second image of patches representing the first feature. The method includes identifying, using the computer device, contents for the second image by processing patches in the image in iterations of the patch-based optimization algorithm. The patch-based optimization complies with the constraint, The method includes generating the second image from the identified contents based on the iterations of the patch-based optimization algorithm. The second image includes a second feature generated to represent the first feature and complying with the constraint.

Claims

1. A computer-implemented method for generating a modified image, the method comprising:

initiating, in a computer device, a patch-based optimization algorithm for using a first image to generate a second image;

identifying, in a computer device, a first feature of a first image, the identification corresponding to a constraint on the first feature for generating a second image, the constraint restricting at least one of location and geometric orientation in the second image of patches representing the first feature;

identifying, using the computer device, contents for the second image by processing patches in the image in iterations of the patch-based optimization algorithm, the patch-based optimization complying with the constraint; and

generating the second image from the identified contents based on the iterations of the patch-based optimization algorithm, the second image including a second feature generated to represent the first feature and complying with the constraint;

wherein the first feature is defined by a parametric-equation line, and wherein the constraint generates a parametric equation that defines the second feature.

2. The method of claim 1, further comprising:

displaying the first image to a user using the computer device; and

receiving an input from the user that marks the first feature in the first image, wherein the first feature is identified based on the input.

3. The method of claim 1, wherein the first feature is automatically identified in the first image without explicit user input.

4. The method of claim 3, further comprising:

receiving an input from the user that modifies the constraint; and

wherein the second image is generated based also on the input.

5. The method of claim 1, wherein the patch-based optimization algorithm includes fitting a parametric model to the patches and iteratively performing projections using the model to fix locations in the second image for at least some of the patches.

6. The method of claim 5, wherein the first feature includes a straight line and wherein the constraint comprises that the second feature include at least part of the straight line.

7. The method of claim 6, wherein the constraint and the parametric model do not restrict a translation and a slope of the straight line in the second image with regard to the first image.

8. The method of claim 6, wherein the constraint and the parametric model restrict the straight line in the second image to have a same slope as in the first image, and wherein the constraint and the parametric model do not restrict a translation of the straight line in the second image with regard to the first image.

9. The method of claim 6, wherein the input further specifies a location where to place the second feature in the second image, and wherein the constraint and the parametric model restrict the straight line in the second image to have a same slope as in the first image.

10. The method of claim 5, wherein the first feature includes a region of the first image, and wherein the constraint and the parametric model provide that the region is translated to a location in the second image without any deformation.

11. The method of claim 1, wherein the constraint comprises that the second feature is generated by a uniform scaling of the first feature.

12. The method of claim 1, wherein the constraint comprises that the second feature is generated by a non-uniform scaling of the first feature that changes at least one proportion of the first feature and does not change at least one other proportion of the first feature.

13. The method of claim 1, wherein the first image includes also a third feature for which a corresponding fourth feature is included in the second image, and wherein the constraint comprises that the second and fourth features are generated by a common scaling of the first and third features, respectively.

14. The method of claim 1, wherein the constraint restricts the second feature to be an affine transformation of the first feature.

15. The method of claim 1, wherein the constraint specifies an aspect of the second feature based on the first feature.

16. The method of claim 15, wherein the constraint includes at least one selected from:

the shape of the first feature is an arbitrary curve and the shape of the second feature is a straight line;

the shape of the first feature is a straight line and the shape of the second feature is an arbitrary curve;

the shape of the first feature is an arbitrary curve and the shape of the second feature is a different arbitrary curve;

the second feature corresponds to at most a predefined amount of distortion of the first feature;

the second feature corresponds to a nonlinear transformation of the first feature; and

definition of an epipole point in the second image through which point all parallel lines or their continuations should pass.

17. The method of claim 1, wherein identifying the contents for the second image comprises:

identifying each second-image point in the second image for which the patch-based optimization algorithm identifies a first-image point in the first feature;

computing the second feature in the second image based on the identified second-image points; and

projecting the identified second-image points to the second feature in the second image.

18. The method of claim 17, wherein the first feature includes a straight line and wherein identifying the contents for the second image further comprises:

determining a three-vector for the straight line; and

ensuring that a dot product of the three-vector and all points in the second feature equals zero.

19. The method of claim 18, wherein the first feature includes a region and wherein identifying the contents for the second image further comprises:

determining a homography transformation of each point in the first feature; and

ensuring that a distance between;

(i) the homography transformations of all points in the first feature equal to points in the second image, and

(ii) all points in the second feature equals zero.

20. The method of claim 1, wherein the second image comprises a retargeting of the first image.

21. The method of claim 1, wherein the constraint limits available locations in the second image for placing the patches of the first feature.

22. The method of claim 1, wherein the patch-based optimization algorithm comprises:

(1) initializing the second image to be equal to the first image;

(2) subsampling the first and second images to a coarsest resolution;

(3) resizing, at the coarsest resolution, the second image by a scale factor using linear interpolation;

(4) computing a nearest-neighbor field in at least one of (i) a direction from the first image to the second image and (ii) a direction from the second image to the first image;

(5) fitting a parametric model to the patches and their nearest-neighbor locations, and performing projections using the parametric model to fix locations in the second image for at least some of the patches;

(6) computing a new second image by copying and averaging colors from nearest-neighbor patches;

(7) repeating steps (4)-(6) until a convergence criterion is met;

(8) repeating, at the coarsest resolution, steps (3)-(7) until a desired output ratio of the second image is reached; and

(9) upscaling to a finer resolution and repeating steps (3)-(8) until reaching an original resolution of the first image.

23. The method of claim 1, wherein the second image represents a reshuffling of the first image.

24. The method of claim 23, wherein the patch-based optimization algorithm comprises:

(1) initializing the second image to be equal to the first image;

(2) subsampling the first and second images to a coarsest resolution;

(3) reshuffling, at the coarsest resolution, the second image;

(4) computing a nearest-neighbor field in at least one of (i) a direction from the first image to the second image and (ii) a direction from the second image to the first image;

(5) fitting a parametric model to the patches and their nearest-neighbor locations, and performing projections using the parametric model to fix locations in the second image for at least some of the patches;

(6) computing a new second image by copying and averaging colors from nearest-neighbor patches;

(7) repeating steps (4)-(6) until a convergence criterion is met; and

(8) upscaling to a finer resolution and repeating steps (3)-(7) until reaching an original resolution of the first image.

25. The method of claim 1, wherein the second image represents an image warping of the first image that preserves texture of the first image.

26. The method of claim 1, wherein the patch-based optimization algorithm uses patches of the first image that have more than one size.

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

initiating, in a computer device, a patch-based optimization algorithm for using a first image to generate a second image;

identifying, in a computer device, a first feature of a first image, the identification corresponding to a constraint on the first feature for generating a second image, the constraint restricting at least one of location and geometric orientation in the second image of patches representing the first feature;

identifying, using the computer device, contents for the second image by processing patches in the image in iterations of the patch-based optimization algorithm, the patch-based optimization complying with the constraint; and

generating the second image from the identified contents based on the iterations of the patch-based optimization algorithm, the second image including a second feature generated to represent the first feature and complying with the constraint;

wherein the first feature is defined by a parametric-equation line, and wherein the constraint generates a parametric equation that defines the second feature.

28. A computer program product tangibly embodied in a computer-readable storage medium, the computer program product including instructions that, when executed, generate on a display device a graphical user interface comprising:

an image display area displaying to a user a first image that is to be used in generating a second image that represents the first image;

an input control for the user to generate an input that marks a first feature of the first image, the input representing a constraint on the first feature for generating the second image, the constraint restricting at least one of location and geometric orientation in the second image of patches representing the first feature;

wherein contents for the second image are identified using a patch-based optimization algorithm applied to patches in the image, the patch-based optimization algorithm complying with the constraint, and the second image is generated using the identified contents, the second image including a second feature generated to represent the first feature and complying with the constraint, wherein the first feature is defined by a parametric-equation line, and wherein the constraint generates a parametric equation that defines the second feature.

29. The computer program product of claim 28, wherein the first feature includes a straight line, and wherein the input control comprises a drawing tool with which the user marks the straight line representing the constraint.

30. The computer program product of claim 28, wherein the first feature includes a region of the first image, and wherein the input control comprises a drawing tool with which the user marks the region representing the constraint.

31. A system comprising:

one or more processors; and

a computer program product tangibly embodied in a tangible program carrier and comprising instructions that when executed by a processor perform a method comprising;

initiating, in a computer device, a patch-based optimization algorithm for using a first image to generate a second image;

identifying, in a computer device, a first feature of a first image, the identification corresponding to a constraint on the first feature for generating a second image, the constraint restricting at least one of location and geometric orientation in the second image of patches representing the first feature;

identifying, using the computer device, contents for the second image by processing patches in the image in iterations of the patch-based optimization algorithm, the patch-based optimization complying with the constraint; and

generating the second image from the identified contents based on the iterations of the patch-based optimization algorithm, the second image including a second feature generated to represent the first feature and complying with the constraint;

wherein the first feature is defined by a parametric-equation line, and wherein the constraint generates a parametric equation that defines the second feature.