Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-09-24
2004-12-14
Patel, Kanji (Department: 2625)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
Reexamination Certificate
active
06832009
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of logic systems. More particularly, the present invention is directed to methods and logic apparatus for image interpolation.
BACKGROUND OF THE INVENTION
Good quality interpolation of digitally encoded images to higher resolution is important in many applications of digital imaging. Such applications include image zooming for digital camera pre-print processing or image zooming in digital video. Image up-scaling interpolation is commonly performed by simple methods such as pixel replication, bilinear interpolation, or spline interpolation [1,2]. The visual results of these interpolation methods suffer from blurring and aliasing affects.
Adaptive interpolation is one method used to achieve better results in image up-scaling. While digital imaging applications require the ability to scale an image to any fractional scaling ratio, most existing adaptive interpolation methods are designed for an integer scaling ratio only. Another typical problem with many advanced interpolation methods is their high computational complexity and high storage complexity.
Adaptive interpolation algorithms have been developed to improve the magnified image quality. Allebach et al. [4] and Biancardi et al. [5] use an interpolation technique that is directed by a high resolution edge-map that was generated from the original low resolution image. Thurnhofer et al. [6] and Michaud et al. [7] used interpolation method that first find the local edge orientation and then interpolate along the edge direction that was found. This method was also being used by Ting et al. [3] for interpolating along sharply curved edges.
A review of interpolation methods was conducted during development of the present invention. A number of papers were reviewed. Reviewed methods include the following approaches:
1. Conventional interpolation methods that use a constant convolution kernel;
2. Adaptive methods that use edge information for the interpolation;
3. Interpolation methods that use Median filters;
4. Interpolation methods that use image transformation like DCT;
5. Interpolation methods that exploit video motion compensation.
Ting. et al. [3] discusses using local gradient properties for interpolating the image. The discussed method consists of two phases. In the first phase, the method interpolates the image using a fuzzy logic system with member functions that are Gaussian-like, depending on calculated gradients of the source image. In its second phase, the method changes values on sharply curved edges due to unsatisfying performance of the first phase along such edges. These values are replaced by linear interpolation along the sharply curved edges detected. The complexity of the edge detection discussed by Ting is high and is not suitable for fractional scaling ratios. The method used by the first phase fails when a fractional scale ratio is needed. Its behavior with a fractional scale ratio is very close to pixel replication, due to the properties of the Gaussian function.
While the first phase of the interpolation algorithm in Ting uses an interpolation formula that is gradient dependent, the formula does not produce consistent satisfactory results and Ting therefore uses a second correction phase that requires much higher complexity.
Paint Shop Pro 5, a very well-known graphics program, uses three methods of resizing: smart size, Bilinear resample, and Bicubic resample. The first method is a special resizing algorithm of Paint Shop Pro and the other two are classical methods. None of these methods yield consistently satisfactory results.
What is needed is a method or apparatus for performing image interpolation that is suitable for lower complexity applications and produces results with a minimum of visual artifacts. What is further needed is a method that can be made adaptive and that can use a non-integer scaling ratio.
Sobel Operator Background
A variety of different operators and functions are known and used in the art to perform various image processing tasks. Specific operators are given herein for the sake of clarity of the description of the invention, however other known or yet to be developed operators and functions may also be used to generate gradients and other values used by the invention.
One important operator is known as the Sobel Operator. In its ideal form, the operator consists of a pair of 3×3 convolution kernel masks, one as shown in (5) and the other rotated by 90°.
These kernels are designed to respond maximally to edges running vertically and horizontally relative to the pixel grid, one kernel for each of the two perpendicular orientations. The kernels can be applied separately to the input image, to produce separate measurements of the gradient component in each orientation (call these Gx and Gy). The components can then be combined to determine an absolute magnitude of the gradient at each point and the orientation of that gradient. The gradient magnitude is given by: |G|=sqrt(Gx
2
+Gy
2
). In many applications, an approximate magnitude for the gradient is computed using: |G|=(|Gx|+|Gy|)/2, which is much faster to compute.
Often, the absolute magnitude is the only output a user from a Sobel operation—the two components of the gradient are conveniently computed and added in a single pass over the input image using a pseudo-convolution operator as shown below:
P1
P2
P3
P4
a
i
P6
P7
P8
P9
Using this kernel, the approximate magnitude can be obtained from: |Ga
i
|=(|(P1+2P2+P3)−(P7+2P8+P9)|+|(P3+2P6+P9)−(P1+2P4+P7)|)/2.
The angle of orientation of the edge (relative to the pixel grid) giving rise to the spatial gradient is given by: &thgr;=arctan Gy/Gx. In this case, orientation angle value 0 is taken to mean that the direction of maximum contrast from black to white runs from left to right on the image, and other angles are measured anti-clockwise from this.
A related operator is the Prewitt gradient edge detector. This works in a very similar way to the Sobel operator but uses slightly different kernels. These kernels produce similar results to the Sobel, but the operator is not as isotropic in its response. Another known operator is the Roberts operator.
Image Interpolation
As is known in the art, common applications for pixel interpolation include changing the size of a digital image or changing the resolution of a digital image. In either case, generally the number of pixels in the image will change and the final size of the digital image will be related to the final pixel size. When the number of pixels in an image increases, either due to increasing the size or the resolution of the original image, that is often referred to in the art as upscaling.
It is also known in the art that pixels can be roughly square, as is common for computer displays, or roughly rectangular, as common for television images, and pixels are generally uniform in size and arrangement in an image. Other pixel geometries have been discussed in the art, but these are not commonly used. The interpolation methods discussed herein can be adapted to these alternate geometries.
It is also known in the art that digital images can be encoded in a two-dimensional x, y array with a single value at each location. Single-value encoding is often used for gray-scale images, but may also be used for various compressed color images.
Color images are commonly encoded in a three-dimensional array, with three values at every x, y location. These three values can denote primary color values, such as red, green, and blue (RGB) or cyan, magenta, and yellow (CMY). Three values can also denote luminance and color difference values such as YIQ; or can denote hue, saturation, and luminance value (HSV). It is also known in the art to use a color mosaic pattern (such as the Bayer pattern) to encode a color image in a
Abramov-Segal Hagit
Bar-Sella Ran
Shezaf Nira
Sutskover Ilan
Parsons Hsue & de Runtz LLP
Patel Kanji
Zoran Corporation
LandOfFree
Method and apparatus for improved image 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 improved image interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for improved image interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326620