Method for 2-D affine transformation of images

• US 5,475,803 A
• Filed: 07/10/1992
• Issued: 12/12/1995
• Est. Priority Date: 07/10/1992
• Status: Expired due to Term

• Current Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Stearns, Charles C., Kannappan, Karthikeyan
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US07/911,832
• Time in Patent Office: 1,250 Days
• Field of Search: 395/136, 395/137, 395/138, 395/139, 395/132, 345/121, 345/126, 345/127, 345/131, 382/44, 382/45, 382/46, 382/47
• US Class Current: 345/648
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image

Abstract

Affine image transformations are performed in an interleaved manner, whereby coordinate transformations and intensity calculations are alternately performed incrementally on small portions of an image. The pixels are processed in rows such that after coordinates of a first pixel are determined for reference, each pixel in a row, and then pixels in vertically adjacent rows, are processed relative to the coordinates of the previously processed adjacent pixels. After coordinate transformation to produce affine translation, rotation, skew, and/or scaling, intermediate metapixels are vertically split and shifted to eliminate holes and overlaps. Intensity values of output metapixels are calculated as being proportional to the sum of scaled portions of the intermediate metapixels which cover the output pixels respectively.

Claims

1. Method of transforming an input image in an input image space into an output image in an output image space according to an image transformation specification,

wherein,

said input image comprises a plurality of input pixels, each having an intensity value, arranged in a rectangular array in said input image space according to a two-dimensional rectilinear input coordinate system;

each input pixel has a horizontal and a vertical coordinate in the input coordinate system;

said output image comprises a plurality of output pixels, each having an intensity value, arranged in a rectangular array in said output image space according to a two-dimensional rectilinear output coordinate system;

each output pixel has a horizontal and a vertical coordinate in an output coordinate system;

said method comprising the steps of;

a) selecting an order of sequential input pixel processing such that input pixels are processed in rows, such that each subsequent input pixel in any given row is adjacent along one axis of the input image coordinate system to the input pixel coordinate system processed immediately previously, and such that each subsequent row of input pixels processed is adjacent along the other axis of the input image coordinate system to the row of input pixels processed immediately previously;

b) expressing said image transformation specification in three by three matrix format, thus forming an image transformation matrix having nine transformation coefficients, said coefficients corresponding to transformation values including scaling, rotation, and, shearing;

c) expressing the horizontal and vertical coordinates in input image space of a first input pixel as a vector quantity to compute horizontal and vertical coordinates in the output image space based on said image transformation matrix;

d) selecting a first number of input pixels according to said selected order of input pixel processing and calculating horizontal coordinates in output image space, relative to said horizontal coordinate of said first input pixel in output image space, of a like number of intermediate output metapixels, said metapixels corresponding to said first number of input pixels on a one-to-one basis and each of which have a common width and height, where said first number is equal to that number of intermediate output metapixels required to fill one output pixel in width;

e) adding the intensity values of all but a last of said first number of input pixels producing an intensity sum;

f) producing an intensity value which is stored into a horizontal partial pixel (HPP) by adding to the intensity sum the intensity value of the last of said first number of input pixels, scaled by an amount proportional to a first portion of a width of a last intermediate output metapixel corresponding the last of said first number of input pixels, said first portion being that which is required to complete filling of said one output pixel;

g) applying the intensity value of the last of said first number of input pixels scaled by an amount proportional to a second portion of said width which is equal to said width minus said first portion as an intensity value of an incomplete horizontal partial pixel (IHPP);

h) calculating the vertical coordinate, relative to said vertical coordinate of the first input pixel in output image space, of said last intermediate output metapixel, and determining its floor and ceiling values;

i) comparing the height and vertical coordinate of said last intermediate output metapixel with the height and vertical coordinate of a vertically nearest output pixel (OS), and determining if said last intermediate output metapixel crosses vertically into said vertically nearest output pixel;

j) if said last intermediate output metapixel crosses vertically into said vertically nearest output pixel (OS), adding the intensity value of the incomplete horizontal partial pixel (IHPP) to the intensity value of the horizontal partial pixel (HPP) and saving it as the intensity value of said vertically nearest output pixel (OS), scaled by an amount of said horizontal partial pixel (IHPP) which covers said vertically nearest output pixel (OS);

k) storing any remaining intensity value of said horizontal incomplete partial pixel (IHPP) into an incomplete output pixel (IOS);

l) repeating steps d) through k) until all input pixels have been processed; and

m) converting any remaining incomplete output pixels into output pixels.

2. A method of transforming an input image in an input image space into an output image in output image space as in claim 1, wherein:

horizontal and vertical coordinates of an intermediate output metapixel corresponding to a first processed input pixel are determined by a complete matrix transformation of the coordinates of the first processed input pixel, and wherein the horizontal and vertical coordinates of all subsequent intermediate output metapixels are determined by adding selected transformation matrix coefficients to the coordinates of previously calculated intermediate output metapixel coordinates.