Interpolation method and apparatus for fast image magnification

• US 5,847,714 A
• Filed: 05/31/1996
• Issued: 12/08/1998
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Huonder, Russell J., Naqvi, H. Shahzad
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US08/656,500
• Time in Patent Office: 921 Days
• Field of Search: 345/428, 345/433, 345/439, 345/127, 345/132, 345/138, 345/150, 345/154, 348/426, 348/441, 348/458, 348/552, 348/561, 348/563, 348/504, 382/162, 382/166, 382/298, 382/299, 358/451
• US Class Current: 345/668
• 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: H04N 1/3935 with modification of image resolution, i.e. determining the values of picture elements at new relative positions
• CPC Class Codes: H04N 5/2628 Alteration of picture size, shape, position or orientation, e.g. zooming, rotation, rolling, perspective, translation

Abstract

Methods and apparatus for generating pixel values in a magnified destination image of an object are provided. The pixel values in the destination image are generated from a source image of the object. A value of a first pixel in each row of the destination image is determined by transforming the first pixel to a first resampled point in the source image and by vertical interpolation between vertically-aligned neighbor pixels to provide intermediate pixel values followed by horizontal interpolation between the intermediate pixel values to provide the value of the first pixel. Each subsequent pixel value that has the same neighbor pixels as a previous resampled point is determined by transforming the subsequent pixel to a subsequent resampled point and by a single horizontal interpolation between the intermediate pixel values of the previous resampled point. The value of each subsequent pixel in each row that has different neighbor pixels from the previous resampled point is determined by transforming the subsequent pixel to a subsequent resampled point and by a single vertical interpolation followed by a single horizontal interpolation to provide the value of the subsequent pixel.

Claims

1. A method for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, said method comprising the steps of:

transforming each pixel in the destination image to a corresponding resampled point in said source image space;

determining a value of a first pixel in each row of the destination image by vertical interpolation between vertically-aligned neighbor pixels of the corresponding resampled point to provide intermediate pixel values, followed by horizontal interpolation between said intermediate pixel values to provide the value of said first pixel; and

determining a value of each subsequent pixel in each row of the destination image that has the same neighbor pixels as a previous resampled point by a single horizontal interpolation between the intermediate pixel values of the previous resampled point.

2. A method for generating pixel values as defined in claim 1 further comprising the step of determining the value of each subsequent pixel in each row of the destination image that does not have the same neighbor pixels as the previous resampled point by a single vertical interpolation between a subsequent set of vertically-aligned neighbor pixels to provide a subsequent intermediate pixel value, followed by a single horizontal interpolation between the subsequent intermediate pixel value and one or more of the previous intermediate pixel values to provide the value of said subsequent pixel.

3. A method as defined in claim 1 wherein said interpolation steps comprise bilinear interpolations.

4. A method as defined in claim 1 wherein said interpolation steps comprise bicubic interpolations.

5. A method for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, said method comprising the steps of:

(a) determining a value of a first pixel in each row of said destination image by transforming the first pixel to a first resampled point in the source image space and by vertical interpolation between vertically-aligned neighbor pixels of the first resampled point to provide intermediate pixel values, followed by horizontal interpolation between said intermediate pixel values to provide the value of said first pixel in the destination image;

(b) determining a value of each subsequent pixel in each row of the destination image that has the same neighbor pixels as a previous resampled point by transforming the subsequent pixel to a subsequent resampled point in the source image space and by a single horizontal interpolation between the intermediate pixel values of the previous resampled point; and

(c) determining the value of each subsequent pixel in each row of the destination image that has different neighbor pixels from a previous resampled point by transforming the subsequent pixel to a subsequent resampled point in the source image space and by a single vertical interpolation between a set of vertically-aligned neighbor pixels of the subsequent resampled point to provide a subsequent intermediate pixel value, followed by a single horizontal interpolation between the subsequent intermediate pixel value and one or more previous intermediate pixel values to provide the value of the subsequent resampled point in the destination image.

6. A method as defined in claim 5 wherein said interpolation steps comprise bilinear interpolations.

7. A method as defined in claim 5 wherein said interpolation steps comprise bicubic interpolations.

8. A method for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, said method comprising the steps of:

(a) determining pixel locations of the destination image in said destination image space from a location and size of said source image and a magnification factor;

(b) transforming a first pixel in a row of the destination image to a first resampled point in said source image space;

(c) determining neighbor pixels of the first resampled point in said source image space;

(d) interpolating between vertically-aligned neighbor pixels in said source image space to provide horizontally-aligned intermediate pixel values;

(e) interpolating between said horizontally-aligned intermediate pixel values to provide a first value of said first pixel in the destination image;

(f) designating the first pixel as a previous pixel and the first resampled point as a previous point, and incrementing to a current pixel in said row adjacent to said previous pixel;

(g) transforming the current pixel in the destination image to a current resampled point in said source image space;

(h) determining if the current resampled point in said source image space has the same neighbor pixels as said previous point;

(i) when the current resampled point has the same neighbor pixels as said previous point, interpolating between the horizontally-aligned intermediate pixel values of said previous point to provide a current value of said current resampled point in the destination image; and

(j) when the current resampled point does not have the same neighbor pixels as said previous point, interpolating between one set of vertically-aligned neighbor pixels of said current resampled point to provide a current intermediate pixel value and interpolating between the current intermediate pixel value and at least one of said intermediate pixel values to provide the current value of said current resampled point in the destination image.

9. A method as defined in claim 8 wherein step c) comprises determining four neighbor pixels and wherein steps d) and e) comprise bilinear interpolations.

10. A method as defined in claim 8 wherein step c) comprises determining sixteen neighbor pixels and wherein steps d) and e) comprise bicubic interpolations.

11. A method as defined in claim 8 further comprising:

(k) repeating steps (g)-(j) for each remaining pixel in the row of the destination image.

12. A method as defined in claim 11 further comprising:

(l) repeating steps (b)-(k) for each remaining row of the destination image.

13. Apparatus for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, comprising:

a disk storage unit for storing the values of the pixels in the source image;

a digital computer for processing the values of the source image in said disk storage unit, said digital computer comprising;

means for determining pixel locations of the destination image in said destination image space from a location and size of said source image and a magnification factor;

means for transforming each pixel in the destination image to a corresponding resampled point in said source image space;

means for determining a value of a first pixel in each row of the destination image by vertical interpolation between vertically-aligned neighbor pixels of the corresponding resampled point to provide intermediate pixel values, followed by horizontal interpolation between said intermediate pixel values to provide the value of said first pixel; and

means for determining a value of each subsequent pixel in each row of the destination image that has the same neighbor pixels as the previous resampled point by a single horizontal interpolation between the intermediate pixel values of the previous resampled point.

14. Apparatus as defined in claim 13 further comprising means for determining the value of each subsequent pixel in each row of the destination image that does not have the same neighbor pixels as the previous resampled point by a single vertical interpolation between a subsequent set of vertically-aligned neighbor pixels to provide a subsequent intermediate pixel value, followed by a single horizontal interpolation between the subsequent intermediate pixel value and one or more of the previous intermediate pixel values to provide the value of said subsequent pixel.

15. A computer-readable medium encoded with a computer program for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, said computer program comprising computer instructions for:

(a) determining a value of a first pixel in each row of said destination image by transforming the first pixel to a first resampled point in the source image space and by vertical interpolation between vertically aligned neighbor pixels of the first resampled point to provide intermediate pixel values, followed by horizontal interpolation between said intermediate pixel values to provide the value of said first pixel in the destination image; and

(b) determining a value of each subsequent pixel in each row of the destination image that has the same neighbor pixels as the previous resampled point by transforming the subsequent pixel to a subsequent resampled point in the source image and by a single horizontal interpolation between the intermediate pixel values of the previous resampled point.

16. A computer-readable medium as defined in claim 15 wherein said computer program further comprises computer instructions for determining the value of each subsequent pixel in each row of the destination image that has different neighbor pixels from a previous resampled point by transforming the subsequent pixel to a subsequent resampled point in the source image space and by a single vertical interpolation between a set of vertically-aligned neighbor pixels of the subsequent resampled point to provide a subsequent intermediate pixel value, followed by a single horizontal interpolation between the subsequent intermediate pixel value and one or more previous intermediate pixel values to provide the value of the subsequent resampled point in the destination image.

17. A computer-readable medium as defined in claim 15 comprising a magnetic disk.

18. A method for generating pixel values in a magnified destination image of an object in a destination image space from a source image of the object in a source image space, said destination image and said source image each comprising a two-dimensional array of pixels, each of said pixels in said source image having a value representative of the object, said method comprising the steps of:

transforming each pixel in the destination image to a corresponding resampled point in said source image space by processing the pixels in said destination image in a first direction relative to said array;

determining a value of a first pixel in each row of the destination image by interpolation between neighbor pixels of the corresponding resampled point, which are aligned perpendicular to said first direction, to provide intermediate pixel values, followed by interpolation between said intermediate pixel values, which are aligned parallel to said first direction, to provide the value of said first pixel; and

determining a value of each subsequent pixel in each row of the destination image that has the same neighbor pixels as a previous resampled point by a single interpolation between the intermediate pixel values of the previous resampled point, which are aligned parallel to said first direction.