Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-04-16
2003-03-25
Mehta, Bhavesh (Department: 2625)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C358S426010, C358S525000
Reexamination Certificate
active
06539128
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to interpolation, and more specifically, to a method and apparatus for interpolating between successive input signals.
2. Description of Related Art
Mathematic interpolation is used in numerous technological fields including, for example, digital processing and analog sampling applications. In the past, interpolation has been accomplished using approaches such as “nearest neighbor” methods and polynomial approximations using linear, quadratic and cubic polynomials.
Linear interpolation approximates values between two points using a straight line function, provided by
y=mx+b
(1)
for a domain range such as 0≦x≦1. With reference to the above equation, known points at x=0 and x=1 are used to determine the slope m and the intercept b. Since only two points are needed to interpolate using a linear function, computational costs associated with linear interpolation are minimal. However, the output resulting from linear interpolation is too inaccurate for many applications. For example, in image processing applications, linear interpolation produces output signals having less clarity and contrast in comparison to the input signals.
A general quadratic interpolation curve approximates values between two points using a second order function, provided by
y=ax
2
+bx+c
(2)
or a domain of 0≦x≦1. Quadratic interpolation in general requires three known points, e.g. f(−1), f(0), and f(1). One interpolation equation that may be obtained using a second order function is
f
=((
f
(−1)−2
f
(0)+
f
(1))/2)
x
2
+(
f
(1)−
f
(−1))
x+f
(0) (3)
for a domain of 0≦x≦1. Another quadratic interpolation equation is disclosed in U.S. Pat. No. 5,379,241 to Greggain, which provides
f
=((
f
(−0.5)−2
f
(0)+
f
(0.5))/0.5)
x
2
+(
f
(0.5)−
f
(−0.5))
x+f
(0) (4)
for a domain of −0.5≦x≦0.5. Equation (4) may also be combined with equation (1) to yield
f
=(
f
(−1)−2
f
(0)+
f
(1))
x
2
+((
f
(1)−
f
(−1))/2)
x+f
(0) (5)
for a domain of −0.5≦x≦0.5.
Similarly, cubic or higher order interpolations are also known in the art, as shown by U.S. Pat. No. 4,578,612, which implements higher order polynomials as weight factors for cubic convolution interpolation.
For applications that require better clarity and contrast, second or higher-order interpolations are generally preferred. However, higher order interpolations come at a cost of increased complexity and resources for performing interpolation. Therefore, there is a need for an interpolation method and application that provides accuracy without computational demands associated with second and higher order interpolation methods.
These and other shortcomings of the known art will be addressed by this invention.
SUMMARY OF THE INVENTION
An embodiment of the present provides a method for interpolating between a first and second pixel in a video display system, where the first pixel has a first pixel value and a first coordinate on a first axis, and the second pixel has a second pixel value and a second coordinate on the first axis. The method includes the steps of providing a first intermediate coordinate in between the first and second coordinates on the first axis. The method further includes determining a weight factor for the first intermediate coordinate. The weight factor is determined by either inputting the first intermediate coordinate into a first blending function if the first intermediate coordinate is within a first domain, or by inputting the first intermediate coordinate into a second blending function if the first intermediate coordinate is within a second domain. The method further includes calculating a first interpolated value from a first product of the weight factor and a difference between the first pixel value and the second pixel value.
In another embodiment of the present invention, a method is provided for interpolating between a first and second pixel, where the first pixel has a first pixel value and a first coordinate on a first axis, and the second pixel has a second pixel value and a second coordinate on the first axis. The method includes the steps of providing a first intermediate coordinate in between the first and second coordinates on the first axis, and determining a weight factor for the first intermediate coordinate. The weight factor may be determined by either inputting the first intermediate coordinate into a first quadratic blending function if the first intermediate coordinate is within a first domain, or by inputting the first intermediate coordinate into a second quadratic blending function if the first intermediate coordinate is within a second domain. The method also includes the step of calculating a first interpolated value from a linear equation comprising a constant equal to either the first or second pixel value, and a product of the weighting factor and a difference between the first pixel value and the second pixel value.
This invention may also include a video display device for interpolating between a first and second pixel. The device includes a fraction generator for providing a signal corresponding to a first intermediate coordinate between the first coordinate and the second coordinate on the first axis. The device may also include a controller coupled to the fraction generator to receive the signal corresponding to the intermediate coordinate, the controller including logic for determining a weight factor for the first intermediate coordinate by alternatively using at least two blending functions. The device further includes an operator that is adapted to receive a first and second pixel and coupled to the controller to receive the signal corresponding to the weight factor, where the first pixel has a first pixel value and a first coordinate on a first axis, and the second pixel has a second pixel value and a second coordinate on the first axis. The operator further includes resources for calculating a first interpolated value using an equation comprising a product of the weight factor and a difference between the first pixel value and the second pixel value.
In a variation to the embodiment, the controller includes logic for implementing a first blending function for when the first intermediate coordinate is within a first domain, and a second blending function for when the first intermediate coordinate is within a second domain.
In another variation to the embodiment, a pixel order generator is coupled to the operator, and the pixel order generator provides the first and second pixel to the operator. The pixel order generator may include memory resources for receiving and storing an input matrix of pixels.
REFERENCES:
patent: 3789203 (1974-01-01), Catherall et al.
patent: 4763293 (1988-08-01), Takei et al.
patent: 5020014 (1991-05-01), Miller et al.
patent: 5229698 (1993-07-01), Minnich et al.
patent: 5235534 (1993-08-01), Potter
patent: 5379241 (1995-01-01), Greggain
patent: 5949695 (1999-09-01), Snell
patent: 5991464 (1999-11-01), Hsu et al.
patent: 5995682 (1999-11-01), Pawlicki et al.
patent: 6023302 (2000-02-01), MacInnis et al.
patent: 6278466 (2001-08-01), Chen
Cheng Kun-Nan
Lee Michael M.
Wang Fu-Chi
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Macronix International Co. Ltd.
Patel Kanji
LandOfFree
Method and apparatus for interpolation 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 apparatus for interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3036231