Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-01-15
2002-12-17
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S284000, C382S293000, C382S294000, C382S298000, C382S299000, C348S453000, C358S426010, C358S525000
Reexamination Certificate
active
06496608
ABSTRACT:
The present invention relates generally to “filling in” the RGB data obtained from digital camera sensors, and to generating interpolated image data values when a digitally encoded image is magnified to a larger size, and particularly to a system and method for performing image data interpolations using spatially limited two-dimension “FIR-like” filters and yet generating images that appear continuous, undistorted and sharp.
BACKGROUND OF THE INVENTION
The present invention addresses two related problems: filling in RGB data obtained from digital camera sensors, and to generating interpolated image data values when a digitally encoded image is magnified to a larger size.
Referring to
FIG. 1
, the first problem concerns the fact that digital camera sensors generate only one color value (for red, green or blue) at each pixel position of the image, creating a pattern of red, green and blue pixels called a mosaic. The specific pattern shown in
FIG. 2
is referred to as the Bayer mosaic pattern. However, all three R, G, B color values are needed for every pixel position to produce a full-color image. In this situation, when image data is first received from the camera sensor, only half the pixels in the image contain an intensity value for the color green, only one fourth of the pixels in the image contain an intensity value for the color blue, and only one fourth of the pixels in the image contain an intensity value for the color red. The goal is to produce the most “accurate” possible intensity values of the missing green, blue and red intensity values, essentially predicting what those intensity values would have been if the camera sensor had been able to record them.
Referring to
FIG. 2
, the second problem concerns the magnification of an image, such as by a factor of four (i.e., the width and height of the image are each doubled). In this situation, it is assumed that the system already has RGB or YUV values, or some other equivalent set of values, representing the initial set of image pixels. However, three fourths of the pixels in the magnified image initially have no image data values, and thus those values have to be generated from the information available in the original pixels (I), which have now been mapped to all the even index positions in the magnified image (J). For magnification factors other than four, the number of pixels that initially have no value will depend on the value of the magnification factor.
While there are literally hundreds of articles and patents addressing interpolation techniques for handling the missing RGB data problem and image data magnification, there are three primary image data interpolation techniques that are used in prior art systems: (1) pixel replication, (2) linear/bilinear interpolation, and (3) cubic/bicubic interpolation. Pixel replication is the simplest image data interpolation technique. In pixel replication, each interpolated pixel value is generated simply by replicating the value of a neighboring pixel in the initial set of pixels. The main advantage of pixel replication is that the interpolation is computationally very simple. The primary disadvantage of this technique is that the quality of the resulting image is poor.
In linear/bilinear interpolation, each interpolated pixel value is generated by essentially “averaging” the values of the two or four closest neighboring pixels in the initial set of pixels. Linear interpolation is used when performing data interpolation on a one-dimensional data set. Linear interpolation generates the interpolated pixel value based on the “average” of the values of the two closest neighboring pixels, one on the left and one on the right, and is a function having terms proportional to 1 and x, where x is the coordinate of the interpolated pixel value. Bilinear interpolation is used when performing image data interpolation on a two-dimensional image. Bilinear interpolation generates the interpolated pixel value based on the “average” of the four closest neighboring pixels, one in each of the northwest, northeast, southeast and southwest directions, and is a function having terms proportional to 1, x, y and xy, where x and y are the coordinates of the interpolated pixel value. Although the quality of the resulting image is better than that produced by pixel replication, the image quality is still relatively poor.
In cubic/bicubic interpolation, each interpolated pixel value is generated based on the values of all pixels in the initial set of pixels. Each interpolated pixel is set to a value such that the piecewise cubic polynomial (sometimes called a cubic spline) formed by the pixels in the resulting image has continuous first and second derivatives (i.e., has second order smoothness). Cubic interpolation is used when performing data interpolation on a one-dimensional data set. The interpolated pixel value generated using cubic interpolation is a function having 1, x, x
2
and x
3
terms, where x is the coordinate of the interpolated pixel value. Bicubic interpolation is used when performing image data interpolation on a two-dimensional image. The interpolated pixel value generated using bicubic interpolation is a function having 1, x, y, xy, x
2
, x
2
y, x
2
y
2
, x
2
y
3
, x
3
, x
3
y, x
3
y
2
and x
3
y
3
terms, where x and y are the coordinates of the interpolated pixel value. The quality of the image produced by cubic/bicubic interpolation is usually very good. Unfortunately, however, the computation and memory requirements of cubic/bicubic interpolation is very high because all pixel values in the image are required to generate each interpolated pixel value.
Goals of Present Invention
Goal 1: Low Distortion. Alternately stated, it is a goal to avoid the use of higher order cross terms, herein called “distortion” terms because they are responsible for introducing artifacts and distortions in interpolated image data. For bilinear interpolation, the distortion term is xy, having a “total power” of two. For biquadratic interpolation, the distortion terms are terms having a “total power” greater than two (namely x
2
y, xy
2
and x
2
y
2
). For bicubic interpolation, the distortion terms are those having total power greater than three (namely x
3
y, x
3
y
2
, x
2
y
2
, x
3
y
3
, x
2
y
3
and xy
3
) Distortion terms are undesirable because they increase the memory required to generate the interpolated image data and generate image artifacts along the diagonals of each rectangular region formed by any four adjacent pixels.
Goal 2: Smoothness. The interpolated image data should represent a smooth and continuous image surface, without discontinuities. If a group of original, neighboring image data points lie on a polynomial surface (e.g., plane or quadratic surface), the new interpolated image data points used to fill in holes between the original image data points should lie on the same polynomial surface.
Goal 3: Continuous turning tangent planes. The tangent planes of the image surface represented by the interpolated image data should be “continuously turning,” without discontinuities. In other words, the two-dimensional spatial first derivative of the surface should be continuous, providing a surface without any sharp angles.
Goal 4: The tangent plane of the image surface represented by the interpolated image data at each location for which an interpolated value is generated should be substantially parallel (i.e., visually indistinguishable from a plane that is parallel) to a secant plane formed by adjacent ones of the data points corresponding to the initial data values.
Goals 1, 2 and 3 ensure that the image after interpolation is “pleasing” by minimizing the visibility of artifacts in the interpolated image such as lines. Goal 4 ensures that sharp lines in the image remain sharp or near sharp in the interpolated image.
SUMMARY OF THE INVENTION
In summary, the present invention is a system and method for generating interpolated pixel data values that begins with an initial image data set that is a subset of data values in a data array f
k,l
representing data values at corresponding
Boudreau Leo
Kassa Yosef
Pennie & Edmonds LLP
Picsurf, Inc.
LandOfFree
Image data interpolation system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image data interpolation system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image data interpolation system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2952194