Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-10-01
2002-12-17
Couso, Yon J. (Department: 2723)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C358S525000
Reexamination Certificate
active
06496609
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and component for interpolating data.
BACKGROUND OF THE INVENTION
In the area of image and video processing, there is frequently a need to create new images by re-sampling an original image.
Typical instances are:
a) zooming-in, where there is a need to create more pixels than in the original image;
b) Image-rotation, where new pixels overlap 2 or more of the original pixels; and
c) Image-distortion (morphing), where the aim may be to correct lens aberration (barrel, pin-cushion distortion) or even to deliberately introduce distortion.
Several two-dimensional techniques for computing new pixel-values are well known, and used frequently. The most commonly met ones are:
a) Nearest-neighbour
b) Bilinear
c) Bicubic
Nearest-neighbour is extremely simple. It consists of sampling the pixel nearest to the centre of the desired new pixel, and using that value. Unfortunately, it has the undesirable effect of introducing ‘jaggies’ or ‘staircasing’. Consider the case of a horizontal line, 1 pixel wide. This appears to the eye as a perfect, straight line (which it is). If re-sampled using nearest-neighbour, a very-slight image-rotation of a degree or so will convert this line into a highly visible staircase. Further operations will enhance this effect, and can even cause break-up of the original line. This form of interpolation is not considered further, as the quality is very poor.
Bilinear is more complex. It consists of taking the 4 pixels which surround, the position of the new pixel, and computing a new pixel-value based on these 4 neighbours. Whichever pixel is nearest to the new one has most weight. If the new pixel is right in the middle of the 4 neighbours, then it will end up being the average of the 4 pixels. This technique is a considerable improvement on nearest neighbour, but still has some draw-backs. It has the effect of blurring the original image, and losing contrast, as the new pixel's computed value will never lie outside the min-max range of the 4 neighbours.
Bicubic is recognised as being the ‘best’ quality, as it applies a curve-fit to the pixel-values, and so is attempting to re-construct the original waveform which gave rise to the sampled pixel-values in the original image. Unfortunately, bicubic interpolation is recognised as being expensive computationally.
DISCLOSURE OF THE INVENTION
The present invention provides a new type of interpolation, a hybrid linear-bicubic interpolation, which achieves the quality of a bicubic interpolation, but using some 80% of the computation of traditional bicubic interpolation.
According to the invention there is provided a method of determining an interpolated value for a point lying between second and third rows of an array comprising at least four rows of spatially related points each having respective values, said method comprising the steps of: linearly interpolating between a first two points on said first row to determine a first value at a first location; cubically interpolating between a second two points on said second row in accordance with the rate of change of values at said second two points on said second row to determine a second value at a second location; cubically interpolating between a third two points on said third row in accordance with the rate of change of values at said third two points on said third row to determine a third value at a third location; linearly interpolating between a fourth two points on said fourth row to determine a fourth value at a fourth location; said first, second, third and fourth locations forming a transverse row intersecting said point; and cubically interpolating between said second and third locations in accordance with the rate of change of values at said second and third locations determined according to said first and fourth values to determine said interpolated value.
REFERENCES:
patent: 4611348 (1986-09-01), Williams et al.
patent: 6088062 (2000-07-01), Kanou et al.
patent: 6236766 (2001-05-01), Zavaljevski et al.
patent: 0 700 015 (1996-03-01), None
patent: WO 90/16035 (1990-12-01), None
Couso Yon J.
Morris Daniel P.
Ohlandt Greeley Ruggiero & Perle L.L.P.
LandOfFree
Hybrid-linear-bicubic interpolation method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid-linear-bicubic interpolation method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid-linear-bicubic interpolation method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2974835