Image transformation method and device

• US 4,975,976 A
• Filed: 09/15/1989
• Issued: 12/04/1990
• Est. Priority Date: 09/20/1988
• Status: Expired due to Term

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Kimata, Naohiro, Yoshida, Takayoshi, Oyake, Ikuo
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/407,936
• Time in Patent Office: 445 Days
• Field of Search: 382/44, 382/22, 382/45, 382/46, 382/47, 382/28, 364/521
• US Class Current: 382/293
• CPC Class Codes: G06T 3/02 Affine transformations for image registration G06T3/147; for image mosaicing G06T3/4038
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based

Abstract

A rectangular source image formed by pixels in a two-axis coordinate system is transformed to a destination image by mapping vertices of the source image onto vertices of the destination image, then mapping edges of the destination image onto edges of the source image, mapping scan lines in the destination image onto the source image, and assigning to pixels on these scan lines the values of corresponding pixels in the source image. DDA algorithms are employed for the edge mapping and scan line mapping steps. This method enables arbitrary affine transformations, including combinations of a rotation with an enlargement or reduction, to be executed without introducing image defects.

Claims

1. An image transformation method for transforming a rectangular source image formed by pixels in a two-axis coordinate system to a destination image formed by pixels disposed on scan lines, comprising the steps of:

(a) mapping vertices of said source image onto vertices of said destination image by a coordinate transformation;

(b) finding intersections of scan lines with edges of said destination image and mapping these intersections onto edges of said source image;

(c) mapping scan lines in said destination image onto said source image, and assigning to pixels on said scan lines the values of corresponding pixels in said source image; and

(d) displaying said destination image by scanning according to said scan lines.

2. The method of claim 1, wherein step (b) comprises steps of:

(b1) computing coordinates of the ends of respective scan lines on said destination image;

(b2) determining an increment value;

(b3) initializing a source coordinate;

(b4) iteratively updating said source coordinate by adding said increment value;

(b5) taking the integer parts of respective updated source coordinates; and

(b6) obtaining the coordinates of corresponding pixels on the edges of said source image according to said integer parts.

3. The method of claim 2, wherein said increment value is determined by dividing the height of an edge of said destination image into the length of a corresponding edge of said source image.

4. The method of claim 3, wherein said source coordinate is initialized to a coordinate of a vertex of said source image plus one-half said increment value.

5. The method of claim 1, wherein step (c) comprises steps of:

(c1) selecting an initial destination pixel on a scan line in said destination image;

(c2) calculating a pair of increment values;

(c3) initializing a pair of source coordinates;

(c4) taking the integer parts of said pair of source coordinates;

(c5) assigning to said destination pixel the value of a pixel disposed in said source image at a location specified by said integer parts of said pair of source coordinates;

(c6) deciding whether said destination pixel is the last pixel on said scan line in said destination image; and

(c7) if said destination pixel is not the last pixel on said scan line in said destination image, updating said pair of source coordinates by adding thereto said pair of increment values, selecting the next destination pixel on said scan line, and returning to step (c4).

6. The method of claim 5, wherein said pair of increment values are calculated by dividing the length of said scan line in said destination image into the directed lengths along respective axes of a corresponding line in said source image.

7. the method of claim 6, wherein said pair of source coordinates are initialized by adding half the values of said pair of increment values to coordinates of a pixel at one end of said corresponding line in said source image.

8. The method of claim 7, wherein a further value of one is added to the initial value of one of said source coordinates.

9. An image transformation method for transforming a rectangular source image formed by pixels in a two-axis coordinate system to a destination image formed by pixels disposed on scan lines, comprising the steps of:

(a) mapping vertices of said source image onto vertices of said destination image, said mapping vertices of said source image step including the substeps of;

(a1) receiving parameters describing one or more affine transformations;

(a2) combining said parameters to generate a product transformation; and

(a3) applying said product transformation to said vertices of said source image;

(b) finding intersections of scan lines with edges of said destination image and mapping these intersections onto edges of said source image;

(c) mapping scan lines in said destination image onto said source image, and assigning to pixels on said scan lines the values of corresponding pixels in said source image; and

(d) displaying said destination image by scanning according to said scan lines.

11. The device of claim 9, wherein for each edge of said destination image, said edge mapping means maps one pixel for each scan line meeting said edge of said destination image.

12. The device of claim 11, wherein said edge mapping means receives a source coordinate and increment value from said controller, iteratively updates said source coordinate by adding said increment value, and calculates the coordinates of pixels on the edges of said source image by taking the integer parts of respective updated source coordinates.

13. The device of claim 12, wherein said controller calculates said increment value by dividing the height of an edge of said destination image into the length a corresponding edge of said source image.

14. The device of claim 13, wherein said controller calculates said source coordinate by adding one-half said increment value to a coordinate of a vertex of said source image.

10. An image transformation device for transforming a rectangular source image formed by pixels in a two-axis coordinate system to a destination image formed by pixels disposed on scan lines, comprising:

a source image memory for storing said source image;

a destination image memory for storing said destination image;

affine transformation means for performing an affine transformation on vertices of said source image to generate vertices of said destination image;

edge mapping means for mapping pixels on edges of said destination image to pixels on edges of said source image;

scan line mapping means for mapping pixels on scan lines in said destination image to pixels in said source image;

controller means for controlling said affine transformation means, said edge mapping means, and said scan line mapping means, and for transferring values of pixels from said source image memory to said destination image memory as indicated by said scan line mapping means;

a data bus for interconnecting said source image memory, said destination image memory, and said controller means; and

display means for displaying images stored in said destination image memory.

15. The device of claim 10, wherein said scan line mapping means receives a pair of increment values and a pair of source coordinates from said controller, iteratively updates said pair of source coordinates by adding said pair of increment values, and calculates the coordinates of pixels in said source image by taking the integer parts of respective updated pair of source coordinates.

16. The device of claim 15, wherein said controller calculates said pair of increment values by dividing the length of a scan line in said destination image into the lengths along respective axes of a corresponding line in said source image.

17. The device of claim 16, wherein said controller calculates said pair of source coordinates by adding half the values of said pair of increment values to the coordinates of a pixel at one end of said corresponding line in said source image.

18. The device of claim 17, wherein said controller adds a further value of one to the value of one of said source coordinates.

19. The device of claim 10, wherein said affine transformation means performs matrix multiplication to calculate a product transformation, and to apply said product transformation to said vertices of said source image.