Computer graphics processing and selective visual display system – Computer graphics processing – Adjusting level of detail
Reexamination Certificate
1999-02-17
2002-10-01
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Adjusting level of detail
C345S667000, C345S698000
Reexamination Certificate
active
06459430
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a system and method for scaling image resolution conversion, and specifically to a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation.
2. Description of Related Art
A wide variety of applications today utilize digital images, where many of these applications have different resolution requirements. In order to perform several applications using the same digital image, the resolution of the digital image must be converted between the resolution requirements of the various applications. Some multi-function peripheral devices have been developed for performing several of these digital image applications, such as scanning, storing, copying, faxing, and printing images. In performing these functions, the resolution required for each of these applications is typically different from the other applications. For instance, the resolution of scanner, printer, and fax standards are typically quite different. International standards define the resolution of faxed documents, while scanners and printers often possess resolutions which are a function of the individual capabilities of the respective devices. In order to support applications having varying resolution requirements, it is necessary to perform resolution conversion between the multiple applications. It is common for a scanner to have a resolution of 300 dpi, while some printers have resolutions of 600 dpi. In order to make the printed image the same size as the image scanned by the scanner, a resolution conversion of 300 dpi to 600 dpi is required.
Scaling methods are utilized to perform this resolution conversion in order to scale the size of an image between respective applications. Previous scaling methods have included the use of a fixed ratio of resolution conversion between an input resolution and an output resolution. For instance, a 1280×1280 pixel input box could be scaled down to a 640×640 pixel output box. Other scaling methods have further used a set of fixed resolution conversions, wherein a user may select a desired scaling of an image from a set of predetermined resolutions incremented in steps, such as image size reductions of 90%, 80%, 70%, etc. These prior scaling methods were limited to predefined incremental steps and did not allow a user to variably select the resolution conversion to more precise values depending upon the needs of the user.
Several scaling methods have been developed to provide a variably selectable resolution conversion, where the particular resolution conversion selected is a function of the number of input pixels and the number of output pixels. One such scaling method is the nearest neighbor algorithm, where each output pixel is mapped from its closest neighboring input pixel. The closest neighbor is determined as a function of the spacing between the input pixels and the spacing between the output pixels. After the input pixels have been mapped to output pixels using the closest neighbor algorithm, all remaining unmapped input pixels which do not closely neighbor an output pixel are removed. These deleted input pixels create image distortion and aliasing in the output image. Another scaling method known as linear interpolation improves on the nearest neighbor algorithm by forming every output pixel as a weighted average of the two closest respective input pixels. An example of linear interpolation scaling is shown in FIG.
1
. Linear interpolation scaling prevents pixel dropping for certain scaling factors above 50%. However, for resolution conversions less than 50%, linear interpolation degenerates into the closest neighbor algorithm where certain input pixels are deleted. As can be seen from
FIG. 1
, input pixels
2
,
5
, and
8
do not contribute to the output pixels when converting from nine input pixels to four output pixels. Thus, aliasing and distortion problems also arise with certain applications of the linear interpolation scaling method.
In order to perform resolution conversion for all resize factors without information loss through pixel dropping, each input pixel from an image must contribute to the output pixels. One such lossless technique is known as 'textbook correct' scaling or DSP scaling, where multi-rate digital signal processing is used to perform the scaling.
FIG. 2
illustrates an example of DSP scaling, where nine input pixels are scaled down to four output pixels. Initially, a set of upsampled pixels are generated from the input pixels using an interpolator, where each input pixel is multiplied by a coefficient value and added together with other values. The resulting upsampled pixel values are then stored in memory elements. Filtering and decimation is then performed on the upsampled pixel values to generate the output pixels. A decimator multiplies the upsampled pixels by a set number of coefficients called filter taps and sums the products to produce a single output pixel. The decimator coefficients are calculated based upon DSP theory to produce output pixels with minimal aliasing.
While the DSP scaling method minimizes aliasing for any resize factor, there are also several drawbacks of the DSP scaling method. The first drawback is caused by the directly proportional relationship of the resize factor to the number of upsampled pixels. For example, if a user wanted to resize 1000 pixels down to 999 pixels, then almost one million upsampled pixels are required to be generated in real time with each one of these upsampled pixels being stored in a memory element. Thus, a great deal of memory is required to store the upsampled pixels as well as requiring fast clock cycles to pipeline the upsampling process in a real-time manner. Another problem results from the large number of decimator coefficients that are required to be calculated for each resize factor, because calculating decimator coefficients for every resize factor is difficult and expensive to implement in hardware. Thus, the resolution conversion achieved by the DSP scaling method depends upon the number of memory elements available and the number of calculations performed, resulting in a large amount of computational complexity, processing time, and memory required to produce unaliased output pixels through DSP scaling.
There is clearly a need for a system and method for implementing multi-level image resolution conversion to efficiently produce unaliased output image pixels in a cost-effective, real-time manner. Moreover, there is a need for a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which performs image scaling for all resize factors while reducing the number of complex calculations, processing time, and amount of memory required for performing the desired resolution conversion.
SUMMARY OF THE INVENTION
It is a primary object of the present invention to overcome the aforementioned shortcomings associated with the prior art.
The present invention provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation scaling.
The present invention further provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which performs image scaling for all resize factors without the need to store a large number of upsampled intermediate pixel values.
The present invention further provides a system and method for implementing multi-level image resolution conversion efficiently using linear interpolation which minimizes the number of complex calculations, the amount of processing time, and the am
Allen Larry M.
Kusumo-Rahardjo Winarto
Brier Jeffery
Conexant Systems Inc.
LandOfFree
System and method for implementing multi-level resolution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for implementing multi-level resolution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for implementing multi-level resolution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2949134