Method and apparatus for non-affine image warping

• US 5,175,808 A
• Filed: 09/12/1989
• Issued: 12/29/1992
• Est. Priority Date: 09/12/1989
• Status: Expired due to Term

• Current Assignee: Pixar (The Walt Disney Company)
• Original Assignee: Pixar (The Walt Disney Company)
• Inventors: Sayre, Rick
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Bayerl, Raymond J.
• Application Number:
  US07/406,227
• Time in Patent Office: 1,204 Days
• Field of Search: 382/44, 382/45, 382/46, 382/47, 358/22, 358/445, 358/451, 340/731, 340/728, 364/518, 364/522, 395/133, 395/136-139, 395/125
• US Class Current: 345/647
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 3/18 Image warping, e.g. rearranging pixels individually

Abstract

A method and apparatus for two-pass image transformation, providing a general solution to execute arbitrary warping of an image. A bicubic mesh is created, by splines or other suitable means, and is used to create displacement tables for X and Y displacement. Alternatively, the displacement tables can be generated directly. The displacement tables represent the movement of each pixel from an original location in the source image to a new location in the destination image. One of the displacement maps is applied to the source image to create an intermediate image and to the other displacement map to create a resampled displacement map. The resampled map is then applied to the intermediate image to create the destination image. By resampling, compensation for altered location points is done automatically. In this manner, no inversion of the underlying equations and functions is required.

Claims

1. A method for performing a non-affine image transformation on a source image comprised of a plurality of points having at least X and Y values comprising the steps of:

defining a warp mesh representing said non-affine transformation of said source image;

defining an X displacement table, the entries of said X displacement table representing the displacement of each point of said source image in an X direction resulting from said non-affine transformation;

defining a Y displacement table, the entries of said Y displacement table representing the displacement of each point of said source image in a Y direction resulting from said non-affine transformation;

resampling said source image with said X displacement table to generate an intermediate image;

resampling said Y displacement table with said X displacement table to generate an intermediate Y displacement table;

resampling said intermediate image with said intermediate Y displacement table to generate a destination image representing said non-affine transformation of said source image.

2. The method of claim 1 wherein said entries of said X and Y displacement tables are described to sub-pixel accuracy.

3. A circuit for performing a non-affine image transformation on a source image comprised of a plurality of points having at least X and Y values comprising:

first storage means for storing said source image;

second storage means for storing an X displacement table, the entries of said X displacement table representing the displacement of each point of said source image in an X direction resulting from said non-affine transformation;

third storage means for storing a Y displacement table, the entries of said Y displacement table representing the displacement of each point of said source image in a Y direction resulting from said non-affine transformation;

first resampling means coupled to said first and second storage means for resampling said source image with said X displacement table to generate an intermediate image, said intermediate image stored in a fourth storage means;

second resampling means coupled to said second and third storage means for resampling said Y displacement table with said X displacement table to generate an intermediate Y displacement table, said intermediate Y displacement table stored in a fifth storage means;

third resampling means coupled to said fourth and fifth storage means for resampling said intermediate image with said intermediate Y displacement table to generate a destination image representing said non-affine transformation of said source image, said destination image stored in a sixth storage means.

4. A method for performing a non-affine image transformation on a source image comprised of a plurality of points having at least X and Y values comprising the steps of:

defining a warp mesh representing said non-affine transformation of said source image;

defining an X displacement table, the entries of said X displacement table representing the displacement of each point of said source image in an X direction resulting from said non-affine transformation;

defining a Y displacement table, the entries of said Y displacement table representing the displacement of each point of said source image in a Y direction resulting from said non-affine transformation;

resampling said source image with said X displacement table to generate a first intermediate image of surface area S1;

resampling said source image with said Y displacement table to generate a second intermediate image of surface area S2;

transposing said source image and said X and Y displacement tables, and resampling said transposed source image with said transposed X displacement table to generate a third intermediate image of surface area S3;

resampling said transposed source image with said transposed Y displacement table to generate a fourth intermediate image of surface area S4;

when S1 is greater than S2, S3 and S4, resampling said Y displacement table with said X displacement table to generate an intermediate Y displacement table, then resampling said first intermediate image with said intermediate Y displacement table to generate a destination image representing said non-affine transformation of said source image;

when S2 is greater than S1, S3 and S4, resampling said X displacement table with said Y displacement table to generate an intermediate X displacement table, then resampling said second intermediate image with said intermediate X displacement table to generate a destination image representing said non-affine transformation of said source image;

when S3 is greater than S1, S2 and S4, resampling said transposed Y displacement table with said transposed X displacement table to generate a transposed intermediate Y displacement table, then resampling said third intermediate image with said transposed intermediate Y displacement table to generate a destination image representing said non-affine transformation of said source image;

when S4 is greater than S1, S2 and S3, resampling said transposed X displacement table with said transposed Y displacement table to generate a transposed intermediate X displacement table, then resampling said fourth intermediate image with said transposed intermediate X displacement table to generate a destination image representing said non-affine transformation of said source image.

5. The method of claim 4 wherein said entries of said X and Y displacement tables are described to sub-pixel accuracy.