Hardware-efficient system for hybrid-bilinear image scaling

• US 6,252,576 B1
• Filed: 08/06/1998
• Issued: 06/26/2001
• Est. Priority Date: 08/06/1998
• Status: Expired due to Term

• Current Assignee: Semiconductor Components Industries LLC (ON Semiconductor Corporation)
• Original Assignee: In-System Design Incorporated (Infineon Technologies AG)
• Inventors: Nottingham, James R.
• Primary Examiner(s): Brier, Jeffery
• Assistant Examiner(s): HARRISON, CHANTE E
• Application Number:
  US09/130,628
• Time in Patent Office: 1,055 Days
• Field of Search: 345/523, 345/418, 345/137, 345/439, 345/466, 345/127, 382/299, 382/114, 348/458, 348/586, 358/1, 358/451, 358/428
• US Class Current: 345/660
• 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 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence

Abstract

A hybrid bilinear scaling (Qscale) scheme produces output images that have comparable quality to traditional bilinear interpolation algorithms, but requires a less complex hardware implementation. The Qscale system does not reverse-map output pixels back to arbitrary locations in the input space as defined by the mapping function. Rather all pixel values and locations are calculated after all of the original input pixels are mapped to the output. That is, all of the original image pixels are used “as-is” in the resultant scaled image. New pixels are generated from the original input pixels to meet the desired output pixel dimensions. Because only new pixels are computed, the Qscale system is less computationally complex. The computational requirements are further reduced because new pixels are computed between original pixel pairs meaning only two pixels are involved in the computation. Coefficients can be chosen to be fractional powers of two (0.5, 0.25, 0.125, etc) for the interpolation calculation between pixel pairs. By selecting coefficients this way, the linear computation reduces to a “shift-and-add” operation, which is easily implemented in hardware.

Claims

1. A method for scaling an input image of original pixels into an output image, comprising:

selecting a scale factor from multiple scale factors for scaling the input image, each one of the multiple scale factors associated with one or more additional new pixels for inserting at symmetrical locations between adjacent original pixels in the input image;

determining interpolation coefficients for each one of the new pixels associated with the selected scale factor, each one of the coefficients derived according to the symmetrical spacing between the new pixels and the adjacent original pixels;

generating values for each one of the new pixels by applying the interpolation coefficients for the selected scale factor to the adjacent original pixels in the input image;

mapping the original adjacent pixels from the input image unaltered into the output image; and

mapping the generated values for the new pixels into the output image at associated new pixel locations that are symmetrically spaced between the original adjacent pixels.

2. A method according to claim 1 including:

repeatedly inserting new pixels between the original adjacent pixels in a first horizontal or vertical direction of the input image;

identifying a number of additional new symmetrically spaced apart pixels to insert between adjacent pairs of original pixels or adjacent pairs of new pixels in a second direction perpendicular to the first direction according to the scale factor;

determining interpolation coefficients according to the number of additional new symmetrically spaced apart pixels associated with the selected scale factor;

generating values for each one of the additional new symmetrically spaced apart pixels in the second direction by applying the interpolation coefficients to the adjacent pixels;

repeatedly inserting additional new symmetrically spaced apart pixels between the adjacent original pixels or adjacent new pixels in the second direction; and

outputting all the additional new pixels in the output image.

3. A method according to claim 1 wherein generating the new pixel values comprises shifting the adjacent original pixel values and adding the shifted original pixel values together.

4. A method according to claim 1 wherein the new pixels are generated according to the following:

5. A method according to claim 1 including:

storing for each scale factor a scaling factor value having an integer portion and a fraction portion;

using the integer portion as the number of new pixels symmetrically spaced between a first pair of adjacent original pixels;

adding a fractional portion of the number of new pixels to the scaling factor value to generate a next number of new pixels; and

using an integer portion of the next number of new pixels as the number of new pixels to insert between a next pair of selected original pixels.

6. A method according to claim 1 wherein determining interpolation coefficients comprises the following:

storing every one of the interpolation coefficient values used for each one of the different scale factors;

generating a first array of scaled values by applying in parallel each one of the stored interpolation coefficient values to a first one of the adjacent pixels;

generating a second array of scaled values by applying in parallel each one of the stored interpolation coefficient values to a second adjacent one of the adjacent pixels;

selecting the scaled values from the first and second array associated with the selected scale factor;

combining selected scaled values from the first array with selected scaled values from the second array to form the new pixel values; and

outputting the new pixel values into the output image between the first and second adjacent original pixels.

7. A system for scaling an input image having an array of original pixels, comprising:

a coefficient generator that generates a set of coefficients for generating a selectable number of new pixels for inserting between adjacent original pixels, the coefficient generator generating the entire set of interpolation coefficients in parallel at the same time by applying the entire set of coefficients to a first one and to a second one of the original adjacent pixels;

an accumulation circuit selecting different selectable ones of the interpolation coefficients generated from the first one of the adjacent original pixels according to a scale factor and selecting different selectable ones of the interpolation coefficients generated from the second one of the adjacent original pixels according to the scale factor;

an interpolation engine that combines the selected interpolation coefficients generated from the first one of the adjacent original pixels together with the selected interpolation coefficients generated from the second one of the adjacent original pixels in parallel to generate all of the new pixels at the same time;

the interpolation engine outputting, both the original adjacent pixels as-is from the input image and the new pixels interpolated from the original pixels as an output image.

8. A system according to claim 7 wherein the accumulation circuit comprises:

a first register for storing the scale factor;

an adder having a first input receiving the scale factor from the first register, a second input and an output; and

a second register having an input receiving the adder output, a first output outputting the number of new pixels inserted between the selected original pixels and a second output outputting a fractional portion of the new pixel number to the second input of the adder.

9. A system according to claim 7 wherein the coefficient generator comprises only bit shifters and adders.

10. A system according to claim 9 wherein the coefficient generator includes multiple sets of predetermined coefficient values each set associated with one of the possible number of new pixels that can be inserted between the selected original pixels, each set comprising pairs of coefficient values each corresponding with each one of the new pixels and the pairs of coefficient values each applied to one of the two selected original pixels.

11. A system according to claim 10 wherein the coefficient generator includes multiple coefficient generation circuits that are selected according to the pair of coefficient values associated with the new pixels.

12. A system according to claim 7 wherein the interpolation engine comprises:

a first multiplexer selecting one of the interpolation coefficients associated with a first one of the selected original pixels;

a second multiplexer selecting one of the interpolation coefficients associated with a second one of the selected original pixels; and

an adder adding together the selected interpolation coefficients.

13. A system according to claim 7 wherein the coefficient generator, accumulation circuit and interpolation engine together generate new pixels according to the following:

14. A system according to claim 7 wherein:

the new pixels are derived and inserted between horizontally adjacent pixels for each row of original pixels in the original image and then the new pixels are derived and inserted between pixels in vertically adjacent rows for each column of the combined original pixels and new pixels;

or

the new pixels are derived and inserted between pixels on vertically adjacent rows for each column of the original pixels and then the new pixels derived and inserted between pixels in horizontally adjacent columns for each row of the combined original pixels and new pixels.

15. A method for scaling an input image having input pixels into an output image, comprising:

mapping all of the input pixels from the input image into the output image;

determining numbers of new pixels to insert between adjacent pairs of pixels in a first direction of the input image according to a first scaling factor;

selecting a set of coefficients for deriving values for the new pixels according to the numbers of new pixels to be inserted between the adjacent pairs of input pixels in the first direction and to provide symmetrical spacing between the new pixels and the adjacent pairs of input pixels;

deriving values for the new pixels according to the pixel values of the adjacent pair of pixels and the selected set of coefficients;

determining numbers of new pixels to insert between each adjacent pair of input pixels and each pair of adjacent new pixels in a second direction;

selecting a set of coefficients for deriving the values of the new pixels in the second direction according to the numbers of new pixels between the adjacent pair of pixels;

generating values for the new pixels in the second direction using the adjacent pair of pixels and the selected set of coefficients; and

outputting the new pixels as part of the output image between the input pixels in the output image.

16. A method according to claim 15 wherein generating the new pixel values comprises the following:

applying a first coefficient to a first one of the adjacent pixels;

applying a second coefficient to a second one of the adjacent pixels; and

adding the first applied coefficient and second applied coefficient together.

17. A method according to claim 16 wherein applying the first and second coefficient comprises bit shifting the first and second adjacent pixels.

18. A method according to claim 15 wherein the number of new pixels are determined using a Bresenham accumulation.