Computer graphics processing and selective visual display system – Display peripheral interface input device – Light pen for fluid matrix display panel
Reexamination Certificate
1998-08-06
2001-06-26
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Display peripheral interface input device
Light pen for fluid matrix display panel
C345S440000
Reexamination Certificate
active
06252576
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to changing the size of images and more particularly to a hybrid bilinear scaling system that provides high quality output images.
The process of changing the size of an image is commonly referred to as scaling. There are several well-defined and well-understood methods used for image scaling. An overview of the subject is described in A
Simplified Approach to Image Processing
, R. Crane, Prentice Hall, Inc., 1997.
Scaling methods range from trivial, pixel-replication techniques to more complex, higher order algorithms. When selecting a particular scaling technique for a given application, a tradeoff is made between computational complexity and resultant image quality. For applications with stringent computational limits or loose image quality requirements, pixel-replication is a popular method used for scaling. Conversely, if an application can afford higher computational costs, or if there are tighter constraints on the output image quality, more complex scaling schemes are used. The most common alternative to pixel replication is bilinear interpolation, which provides improvement in image quality at a moderate computational expense.
With bilinear interpolation, new or scaled pixels are computed as a weighted sum of neighboring pixels. Weights are computed linearly and proportionally to the distance the new pixel is to existing or neighboring pixels. The new pixel locations, relative to the input (original) pixels, are determined by reverse-mapping the desired, destination pixels back to the input space. In most cases, the original input pixels are not used in the resultant output image. The only time input pixels are directly mapped to an output pixel is when the reverse-mapping of the output pixel location happens to land exactly on a grid location in the original input space. Thus, techniques, like bilinear interpolation, are computationally exhaustive and require complex scaling circuitry. Accordingly, a need remains for a simple scaling technique that produces high image quality.
SUMMARY OF THE INVENTION
A hybrid bilinear scaling scheme, dubbed Qscale, produces output images that have comparable quality to traditional bilinear interpolation algorithms, but requires a less complex hardware implementation. The Qscale algorithm system takes a different approach to determine the location and value of output pixels. Rather than reverse-mapping output pixels back to arbitrary locations in the input space (as defined by the mapping function), all output pixel values and locations are calculated after all of the original input pixels are mapped to the output image. That is, all of the original image pixels are used “as-is” in the resultant scaled output image. New pixels are generated from the original input pixels to meet the desired output pixel dimensions. The new pixel values are linearly interpolated between pixel pairs. Since all original pixels in the input image are used in the output image, the Qscale system is less computationally complex because fewer new pixels have to be generated, and there is not a “reverse-mapping” requirement in the computation.
The computational requirements are further reduced because new pixels are computed between original pixel pairs, meaning that there are only two pixels involved in the interpolation computation of a new pixel. Since new pixels are computed linearly from existing pixels, 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 extremely efficient in hardware. By constraining the computation to be between two existing pixels, a fixed set of coefficients can be selected such that new pixels are computed as a weighted average that is proportional to the relative location of the new pixel between the existing pixels. The number of new pixels generated between each pair of pixels is proportional to the desired scale factor.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 3893166 (1975-07-01), Pugsley
patent: 3938102 (1976-02-01), Morrin et al.
patent: 3995253 (1976-11-01), Morrin, II et al.
patent: 4799173 (1989-01-01), Rose et al.
patent: 4816913 (1989-03-01), Harney et al.
patent: 4837722 (1989-06-01), Sara
patent: 4903147 (1990-02-01), Kanno et al.
patent: 4937761 (1990-06-01), Hassett
patent: 5327257 (1994-07-01), Hrytzak et al.
patent: 5335296 (1994-08-01), Larkin et al.
patent: 5384904 (1995-01-01), Sprague et al.
patent: 5400154 (1995-03-01), Takayama et al.
patent: 5517612 (1996-05-01), Dwin et al.
patent: 5570436 (1996-10-01), Fukushima et al.
patent: 5586196 (1996-12-01), Sussman
patent: 5621870 (1997-04-01), Shyu et al.
patent: 5646696 (1997-07-01), Sprague
patent: 5666437 (1997-09-01), Vondran, Jr.
patent: 5682179 (1997-10-01), Cahill, III
patent: 5684981 (1997-11-01), Jones
patent: 5717507 (1998-02-01), Vondran, Jr.
patent: 5726766 (1998-03-01), Saotome
patent: 5737101 (1998-04-01), Ito
patent: 5745123 (1998-04-01), Rice
patent: 5838838 (1998-11-01), Overton
patent: 5850227 (1998-12-01), Longhenry et al.
Randy Crane, A Simplified Approach to Image Processing, Classical and Modern Techniques in C, “Chapter 4 Geometric Processes,” 1997, pp. 110-113.
Brier Jeffery
Harrison Chante
In-System Design, Inc.
Marger & Johnson & McCollom, P.C.
LandOfFree
Hardware-efficient system for hybrid-bilinear image scaling does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware-efficient system for hybrid-bilinear image scaling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-efficient system for hybrid-bilinear image scaling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483032