Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-09-15
2004-05-11
Couso, Yon J. (Department: 2723)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S300000
Reexamination Certificate
active
06735349
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to graphics systems and more particularly to a method for scaling images created by such a system.
BACKGROUND OF THE INVENTION
When the resolution of a bit map image is required to be changed, one needs to take each pixel in the destination image and map it onto the source image. The coordinates of the destination pixel could point to a pixel in the source image or to a location that lies between the source pixels. Depending on the location of the destination pixel, it can be set to a mathematical combination of pixels in the source image that are physically close to the destination pixel (neighboring pixels).
FIG. 1
depicts such a mapping process. The black rectangles
10
represent the original pixel map while the circles
12
represent the pixels in the destination image. In this embodiment each destination pixel has four nearest neighbor source pixels and twelve second nearest neighbor source pixels. However, some of the destination pixels directly map onto the source pixels, as in the case of corner pixels in the illustration below.
Bilinear Interpolation
This method of computing destination pixel values is by taking the weighted average of four nearest-neighbor source pixels. The weights decrease linearly with the distance of the neighboring source pixels from the destination pixel. While this technique gives reasonable results for most source images, it causes non-uniformity when the source image consists of high-resolution periodic patterns such as single pixel pinstripe or checkerboard images. For such images, bilinear interpolation leads to non-uniform scaling and regions of high and low contrast appear on the image. In the frequency domain, this effect is called aliasing. Spatially, it can be seen to occur because of non-uniform weights to the destination pixels in the averaging process. High contrast regions correspond to pixels in the destination image, which are close to the source image and do not undergo the averaging process. Low contrast regions correspond to destination pixels that lie near the center of the square formed by the four nearest neighbor source pixels. It is highly desirable to reduce (if not completely eliminate) this contrast non-uniformity.
The value of a destination pixel in bilinear interpolation can be written as:
P
d
=
∑
i
=
1
i
=
4
C
i
P
si
Where P
d
is the destination pixel, P
si
is the i
th
pixel in the source image and C
i
is the weight associated with the i
th
pixel. Note that there are four multiply and three add operations associated with each destination pixel. Normally the two dimensional operation is decomposed into separate row and column operations horizontal interpolator
20
and vertical interpolator
22
to reduce the complexity of calculation as shown in FIG.
2
. The implementation requires at least four line buffers
24
to store the source pixels.
The weights for horizontal and vertical interpolation are determined by the value of horizontal and vertical digital data accumulators increment as inverse of the respective scaling ratios. The higher the resolution of the accumulator, the better is the accuracy of scaling ratio. Accordingly, through this system contrast uniformity is uneven.
Alternative Solutions
There are a few known ways to reducing the above described contrast non-uniformity.
Non-linear Interpolation
One class of techniques uses higher order interpolation to reduce the contrast non-uniformity. Higher order interpolation leads to better low pass filtering of the input data thereby reducing the extent of aliasing in the image. Higher order interpolation techniques could be based on biquadratic or bicubic interpolation. Both these techniques use more than the nearest neighbor pixels in the source image to generate a destination pixel. Therefore, instead of doing a weighted average of four pixels, these methods perform a weighted average of nine or sixteen pixels respectively. Normally bicubic interpolation requires sixteen multiply and fifteen add operations for each destination pixel. Again the interpolation process can be decomposed into separate row and column operations. Each row and column operation requires four multiply and three add operations only to reduce the complexity of overall computation considerably. Bicubic interpolation also requires higher memory storage in comparison to bilinear interpolation.
Digital Filters
FIR (finite impulse response) digital filters can be used for interpolation. These filters can average several more neighboring pixel in the source image to achieve a tradeoff between filter complexity and image uniformity. The drawback of using higher order digital filters is that both computational complexity and memory storage required goes up considerably as the order of filter is increased.
The present invention relates to implementation in a semiconductor integrated circuit but the concepts can be used in software based image resizing (scaling) algorithms too.
Accordingly, what is needed is a system and method for scaling images that overcomes the problems associated with prior art techniques. The system and method should be cost effective and easily implemented in existing graphics signals. The present invention addresses such a need.
SUMMARY OF THE INVENTION
A method and system for scaling an image in accordance with the present invention is disclosed. In a first aspect at least two interpolators operate in parallel. Each interpolator operates with a different spatial offset with respect to the other. The final output is the average the output of each interpolator. Normally the initial value of the horizontal and vertical DDA's is zero. Offset is introduced by introducing an initial value in the DDA. Offset has the physical effect of manipulating the weights required for the averaging process in bilinear interpolation. In a second aspect, one interpolator causes either an initial phase of the interpolator to be programmable temporally, or its spatial interpolation coefficients are program using a lookup table. The present invention relates to implementation in a semiconductor integrated circuit but the concepts can be used in software based image resizing (scaling) algorithms too.
REFERENCES:
patent: 4471349 (1984-09-01), Strolle
patent: 4667302 (1987-05-01), Mackey et al.
patent: 4757465 (1988-07-01), Hakoopian et al.
patent: 5371533 (1994-12-01), Lewins
patent: 5506583 (1996-04-01), McVicker
patent: 6121808 (2000-09-01), Gaudet
patent: 6379304 (2002-04-01), Gilbert et al.
Agarwal Sandeep
Johary Arun
Beyer Weaver & Thomas LLP
Couso Yon J.
Genesis Microchip Inc.
LandOfFree
Method and system for dual spatial or temporal 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 Method and system for dual spatial or temporal scaling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for dual spatial or temporal scaling will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3199145