US5847714A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interpolation method and apparatus for fast image magnification
Assignee: Hewlett Packard Development Co LP
•
Filing: 1996-05-31
•
Granted: 1998-12-08
•
Expires: 2016-05-31
Abstract
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.
Inventors
- 👤 H. Shahzad Naqvi
- 👤 Russell J. Huonder
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 15:08
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/40; G06T3/4007; H; H04; H04N; H04N1/00; H04N1/387; H04N1/393; H04N1/3935; H04N5/00; H04N5/222; H04N5/262; H04N5/2628
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
172 words
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.
Claim 2
Independent Claim
172 words
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.
Claim 3
Dependent Claim
93 words
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.
Claim 4
Dependent Claim
14 words
A method as defined in claim 1 wherein said interpolation steps comprise bilinear interpolations.
Claim 5
Dependent Claim
14 words
A method as defined in claim 1 wherein said interpolation steps comprise bicubic interpolations.
Claim 6
Independent Claim
291 words
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.
Claim 7
Independent Claim
291 words
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.
Claim 8
Dependent Claim
14 words
A method as defined in claim 5 wherein said interpolation steps comprise bilinear interpolations.
Claim 9
Dependent Claim
14 words
A method as defined in claim 5 wherein said interpolation steps comprise bicubic interpolations.
Claim 10
Independent Claim
347 words
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.
Claim 11
Independent Claim
347 words
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.
Claim 12
Dependent Claim
24 words
A method as defined in claim 8 wherein step c) comprises determining four neighbor pixels and wherein steps d) and e) comprise bilinear interpolations.
Claim 13
Dependent Claim
24 words
A method as defined in claim 8 wherein step c) comprises determining sixteen neighbor pixels and wherein steps d) and e) comprise bicubic interpolations.
Claim 14
Dependent Claim
24 words
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.
Claim 15
Dependent Claim
21 words
A method as defined in claim 11 further comprising: (l) repeating steps (b)-(k) for each remaining row of the destination image.
Claim 16
Dependent Claim
234 words
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.
Claim 17
Dependent Claim
234 words
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.
Claim 18
Dependent Claim
87 words
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.
Claim 19
Dependent Claim
200 words
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.
Claim 20
Dependent Claim
200 words
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.
Claim 21
Dependent Claim
114 words
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.
Claim 22
Dependent Claim
12 words
A computer-readable medium as defined in claim 15 comprising a magnetic disk.
Claim 23
Independent Claim
208 words
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.
Claim 24
Independent Claim
208 words
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.
References Cited (Backward Citations)
GB2172167A
Cited
US4988984A
Cited
US5125042A
Cited
US5113455A
Cited
US5335296A
Cited
US5475803A
Cited
US5384904A
Cited
US5579418A
Cited
GB2287154A
Cited
US5574572A
Cited
GB2303758A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-07 | 2002-06-08 | 2002-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-07 | 2006-06-08 | 2006-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-07 | 2010-06-08 | 2010-12-08 | $7700.00 | Window Closed / Lapsed |