×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×