Apparatus for 2-D affine transformation of images

• US 5,715,385 A
• Filed: 06/06/1994
• Issued: 02/03/1998
• 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:
  US08/254,150
• Time in Patent Office: 1,338 Days
• Field of Search: 395/136, 395/137, 395/138, 395/139, 395/132, 345/121, 345/126, 345/127, 345/131, 382/293, 382/295, 382/296, 382/298
• 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. Apparatus for 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 the output coordinate system;

each input pixel has a height and a width in the input coordinate system;

each output pixel has a height and a width in the output coordinate system;

an order of sequential input pixel processing is predefined such that access to said input pixels is made in rows, such that each subsequently accessed pixel in any given row is adjacent along one axis of the input image coordinate system to the input pixel accessed immediately previously, and such that each subsequently accessed row of input pixels is adjacent along the other axis of the input image coordinate system to the row of input pixels accessed immediately previously;

said image transformation specification is expressed in three by three matrix format, thus forming an image transformation matrix having nine transformation matrix coefficients, and selected ones of said transformation matrix coefficients are made available in digital form; and

said horizontal and vertical coordinates in input image space of a first input pixel are made available in digital form;

said apparatus comprising;

means for selecting a first number of input pixels according to said selected order of input pixel processing and calculating horizontal coordinates in output image space of a like number of intermediate output metapixels, which metapixels correspond 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;

means for adding the intensity values of all but a last of said first number of input pixels, and an intensity value of an incomplete horizontal partial pixel (IHPP), producing an intensity sum;

means for adding to the intensity sum the intensity value of the last of said first number of input pixels, scaled by an amount proportional to an amount of the width of the intermediate output metapixel which corresponds to said last of said first number of input pixels required which, in combination with the widths of the intermediate output metapixels which correspond to all but the last of said first number of input pixels, exactly fills one output pixel in width, producing an intensity value which is stored into a horizontal partial pixel (HPP);

means for storing a remaining portion of the intensity value of the last of said first number of input pixels in a storage location corresponding to the intensity value of an incomplete horizontal partial pixel (IHPP);

means for calculating the vertical coordinate of the intermediate output metapixel corresponding to the last of said first number of input pixels, and determining its floor and ceiling values;

means for comparing the height and vertical coordinate of said intermediate output metapixel corresponding to the last of said first number of input pixels with the height and vertical coordinate of a nearest output pixel, and determining if said intermediate output metapixel crosses vertically into a next nearest output pixel;

means for 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 the nearest output pixel, scaled by an amount equal to an amount of said horizontal partial pixel which covers said nearest output pixel (OS), if and only if said intermediate output metapixel crosses vertically into the next nearest output pixel; and

means for storing any remaining intensity value of said horizontal partial pixel into an incomplete output pixel (IOS).

2. Apparatus for transforming an input image in an input image space into an output image in output image space according to 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.

3. Apparatus for transforming an input image in an input image space into an output image in output image space according to claim 1, wherein:

said pre-defined order of input pixel processing is a raster-scan order.

4. Apparatus for transforming an input image in an input image space into an output image in output image space according to claim 1, wherein:

said pre-defined order of input pixel processing is a serpentine scanning order.