Iteratively building displacement maps for image warping

• US 6,377,712 B1
• Filed: 04/10/2000
• Issued: 04/23/2002
• Est. Priority Date: 04/10/2000
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Georgiev, Todor G, Hamburg, Mark
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US09/545,959
• Time in Patent Office: 743 Days
• Field of Search: 382/293, 382/294, 382/279, 382/282, 382/284, 382/285, 345/433, 345/435, 345/418, 345/419, 345/427, 345/425, 345/619, 345/629
• US Class Current: 382/293
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 2210/44 Morphing

Abstract

A method and apparatus, including a computer program apparatus, implementing techniques for warping a digital image. The iterative mesh-based warping techniques select a plurality of elements from a dense mesh, each element of the mesh corresponding to one or more pixels of a digital image and representing a vector of displacement values. A kernel is applied iteratively to the mesh in order to update the selected elements with new displacement values until a termination condition is achieved, such as the convergence of the displacement values to a fixed point. The kernel is selected so that the iterations converge to a solution of an appropriate differential equation. The resultant mesh is applied to the digital image, thereby warping the image according to the new displacement values. The displacement values of the selected elements and the non-selected elements as used as inputs to the kernel. The new displacement values generated by the kernel are written to the selected elements without updating the displacement values of the non-selected elements.

Claims

1. A method for warping a digital image using a displacement map comprising:

generating a set of K kernels by convolving a kernel, representing either the Laplacean operator or the Cauchy-Riemann operator, upon itself K−

1 times;

selecting a plurality of elements of a displacement map according to input received from a user, wherein each element contains a displacement vector having a vertical displacement value and a horizontal displacement value for mapping destination pixels of an output image to source pixels of an input image;

selecting a first kernel from the set of K kernels according to user input and applying the first kernel iteratively to the displacement map in order to update the selected elements with new displacement vectors having displacement values that represent a solution to a corresponding differential equation, wherein the solution is a function of boundary conditions defined by the selected elements of displacement map;

additionally applying iteratively one or more of the kernels, selected from the set of K kernels according to user input, to the displacement map to further update the displacement vectors of the selected elements; and

generating an output image by mapping destination pixels within the output image to source pixels within the input image according to the updated displacement vectors of the displacement map.

2. The method of claim 1, wherein the kernels are applied to the displacement values of each element independently from the other displacement values of the element.

3. The method of claim 1, wherein the kernels are applied to the displacement values of each element by treating the displacement values of each element as complex numbers.

4. A method for processing a digital image, comprising:

displaying an input digital image, the input digital image being defined by a raster of source pixels;

establishing a warping mesh corresponding to the input digital image, the mesh having a plurality of elements, each mesh element corresponding to one or more source pixels, each mesh element maintaining one or more displacement values for its corresponding one or more source pixels;

receiving user input selecting an artistic effect and an area within the input digital image to which the artistic effect is to be applied;

selecting a transformation kernel based on the selected artistic effect, the kernel being defined to construct a transformation function corresponding to the selected artistic effect when the kernel is applied to the warping mesh; and

applying iteratively the selected kernel to the warping mesh until a termination condition is satisfied to generate a final warping mesh, the application of the kernel taking as inputs displacement values of all elements of the mesh but updating only the displacement values of mesh elements corresponding to the selected area of the input digital image while leaving unchanged all mesh elements not corresponding to the selected area; and

applying the final warping mesh to the input digital image to produce a warped output digital image, whereby the input image is warped to achieve the user-selected artistic effect.

5. The method of claim 4 further comprising:

receiving a user input defining initial displacement values for one or more elements in the warping mesh.

6. The method of claim 4, wherein receiving user input selecting an artistic effect and an area comprises:

receiving a user selection of a computer-generated paintbrush corresponding to an artistic effect; and

selecting one or more regions in response to a user input gesture moving the selected paintbrush over the input digital image.

7. The method of claim 4, wherein applying iteratively the selected kernel to the warping mesh comprises:

applying the selected kernel independently to a horizontal and a vertical displacement value of each element if the selected kernel is an integer kernel; and

applying the selected kernel to a displacement vector of each element if the selected kernel is a half-integer kernel.

8. The method of claim 4, wherein the termination condition includes applying the kernel a predefined number of times.

9. The method of claim 4, wherein the termination condition includes the convergence of the displacement values of the updated elements to a fixed point.

10. The method of claim 4, wherein applying the warping mesh to the input digital image comprises:

mapping pixels in the input digital image to the output digital image in accordance with the displacement values in the warping mesh.

11. The method of claim 4, wherein the displacement values of the elements in the warping mesh corresponding to selected and non-selected areas of the input digital image converge to an approximate solution to an equation related to Laplace'"'"'s equation after the iterative application of the selected kernel.

12. The method of claim 11, wherein the equation related to Laplace'"'"'s equation is Laplace'"'"'s equation to a power of (N−

1)/2, N being an integer greater than one.

13. The method of claim 4, wherein applying iteratively the selected kernel to the warping mesh comprises:

applying the selected kernel independently to each element in the warping mesh corresponding to a selected area of the input digital image.

14. A computer program product, tangibly stored on a computer-readable medium, for processing a digital image, the product comprising instructions operable to cause a programmable processor to:

display an input digital image, the input digital image being defined by a raster of source pixels;

establish a warping mesh corresponding to the input digital image, the mesh having a plurality of elements, each mesh element corresponding to one or more source pixels, each mesh element maintaining one or more displacement values for its corresponding one or more source pixels;

receive user input selecting an artistic effect and an area within the input digital image to which the artistic effect is to be applied;

select a transformation kernel based on the selected artistic effect, the kernel being defined to construct a transformation function corresponding to the selected artistic effect when the kernel is applied to the warping mesh; and

apply iteratively the selected kernel to the warping mesh until a termination condition is satisfied to generate a final warping mesh, the application of the kernel taking as inputs displacement values of all elements of the mesh but updating only the displacement values of mesh elements corresponding to the selected area of the input digital image while leaving unchanged all mesh elements not corresponding to the selected area; and

apply the final warping mesh to the input digital image to produce a warped output digital image, whereby the input image is warped to achieve the user-selected artistic effect.

15. The computer program product of claim 14, further comprising instructions to:

receive a user input defining initial displacement values for one or more elements in the warping mesh.

16. The computer program product of claim 14, wherein the instructions to receive a user input selecting an artistic effect and an area comprise instructions to:

receive a user selection of a computer-generated paintbrush corresponding to an artistic effect; and

select one or more regions in response to a user input gesture moving the selected paintbrush over the input digital image.

17. The computer program product of claim 14, wherein the instructions to

apply the selected kernel independently to a horizontal and a vertical displacement value of each element if the selected kernel is an integer kernel;

and

apply the selected kernel to a displacement vector of each element if the selected kernel is a half-integer kernel.

18. The computer program product of claim 14, wherein the termination condition includes applying the kernel a predefined number of times.

19. The computer program product of claim 14, wherein the termination condition includes the convergence of the displacement values of the updated elements to a fixed point.

20. The computer program product of claim 14, wherein the instructions to apply the warping mesh to the input digital image comprises instructions to:

map pixels in the input digital image to the output digital image in accordance with the displacement values in the warping mesh.

21. The computer program product of claim 14, wherein the displacement values of the elements in the warping mesh corresponding to selected and non-selected areas of the input digital image converge to an approximate solution to an equation related to Laplace'"'"'s equation after the iterative application of the selected kernel.

22. The computer program product of claim 21, wherein the equation related to Laplace'"'"'s equation is Laplace'"'"'s equation to a power of (N−

1)/2, N being an integer greater than one.

23. The computer program product of claim 14, wherein the instructions to apply iteratively the selected kernel to the warping mesh comprises instructions to:

applying the selected kernel independently to each element in the warping mesh corresponding to a selected area of the input digital image.