Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-12-17
2004-03-30
Brier, Jeffery (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S698000
Reexamination Certificate
active
06714210
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of resolution conversions of digital data and in particular digital image data. The current invention is particularly advantageous for a resolution conversion implementation that uses samples from a continuous kernel as coefficients in the convolution operation. The current invention also provides an efficient software algorithm to implement resolution conversion.
BACKGROUND OF INVENTION
A filter function used in digital data resolution conversion is often called a convolution kernel, a filter kernel or just a kernel. When a kernel produces data that passes through original data points of a sampled signal, it is often called an interpolating kernel and when the interpolated data produced is not constrained to pass through the original data points it is often called an approximating kernel.
Prior art kernels for digital data resolution conversion include the nearest neighbour (NN), linear, quadratic and cubic kernels. The NN kernel is the simplest method of interpolation, simply interpolating the image with the pixel value that is spatially nearest to the required pixel value. This method works quite well when the scaling ratio is an integer multiple of the original data as it introduces no new values, ie. no new colours, and preserves sharp edges. However, at other ratios the NN kernel has the disadvantage of shifting edge locations which often produces visible distortions in the output image, especially in images containing text or fine line details. Linear interpolation on the other hand allows for the introduction of new grey levels (or colours) that are effectively used to position edges at sub-pixel locations. This has the advantage of reducing the effect of shifted edge locations, however sharp edges can now appear to be blurred. Quadratic and cubic interpolation provide steeper step responses and therefore less edge blurring, however, the steeper response results in an overshoot on either side of the edge. These overshoots can make the edges in natural images appear sharper, but on text, fine lines, or on other computer generated graphics these overshoots are clearly visible and detract from the perceived image quality and text legibility.
Hardware to perform two dimensional image interpolation using a method of cubic convolution is known whereby pre-calculated values of the two-dimensional cubic convolution kernel are stored in a look-up table (LUT) and then simultaneously 16 (4×4) coefficient values are read and multiplied with 16 pixels in the original image surrounding the pixel location to be interpolated. Storing the coefficient values in a look-up table removes the need to calculate the coefficients at each interpolated pixel and therefore increases the speed of execution of the algorithm.
Another technique performs two-dimensional interpolation by first interpolating the rows of an image and then interpolating the columns of the image. Up to 4 coefficients for each of the one-dimensional convolution kernels are again read from a LUT, multiplied with data, and summed to produce an interpolated pixel. However, this implementation, which is commonly referred to as a “separable implementation”, is not as fast as the two-dimensional implementation discussed above, although significant reductions in the memory requirements of the LUT may be obtained.
There is a problem however, with both of these known methods in that pre-calculating values and storing them in a LUT introduces an error between the actual coefficient value required for the interpolation and the closest value stored in the LUT. Storing more values in the LUT can reduce this error, however, this can drastically increase the amount of storage required for the LUT.
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
SUMMARY OF THE INVENTION
One or more exemplary aspects of the invention are listed below, but are not limited thereto.
According to one aspect of the invention there is provided a method of converting a first set of discrete data values to a second set of discrete data values, the method comprising the following steps:
(i) calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values;
(ii) calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter functions;
(iii) storing said filter function coefficients;
(iv) accessing said stored filter function coefficients; and
(v) performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to another aspect of the invention there is provided an apparatus for converting a first set of discrete data values to a second set of discrete data values, the apparatus comprising:
calculator means for calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values, and calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter functions;
storage means for storing said filter function coefficients;
storage access means for accessing said stored filter function coefficients; and
interpolation means for performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to still another aspect of the invention there is provided a computer readable medium for storing a program for an apparatus which processes data, said processing comprising a method of converting a first set of discrete data values to a second set of discrete data values, said program comprising:
code for calculating a scaling factor of said first set of discrete data values compared to said second set of discrete data values;
code for calculating a plurality of filter function coefficients, based on said scaling factor, utilising at least one of a plurality of filter function;
code for storing said filter function coefficients;
code for accessing said stored filter function coefficients; and
code for performing interpolation on said first set of discrete data values, using said accessed filter function coefficients, to generate said second set of discrete data values.
According to still another aspect of the invention there is provided a method of performing interpolation on a pixel-based image, the method comprising the steps of:
(i) calculating a scaling factor of a first image compared to a second image;
(ii) calculating a plurality of filter function coefficients, based on said scaling factor, utilising one of a plurality of filter functions;
(iii) storing said filter function coefficients;
(iv) detecting incoming pixels of said first image;
(v) accessing said stored filter function coefficients; and
(vi) performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
According to still another aspect of the invention there is provided an apparatus for performing interpolation on a pixel-based image, the apparatus comprising:
calculator means for calculating a scaling factor of a first image compared to a second image, and calculating a plurality of filter function coefficients, based on said scaling factor, utilising one of a plurality of filter functions;
storage means for storing said filter function coefficients;
detection means for detecting incoming pixels of said first image;
coefficient access means for accessing said stored filter function coefficients; and
interpolator for performing interpolation on said pixels of said first image, using said accessed filter function coefficients, to generate said second image.
In embodiments of the invention, the first image may be a colour image.
According to still another aspect of the invention there is provided a computer readable medium for storing a program fo
Bradley Andrew Peter
Huang Kai
Yip Dominic
LandOfFree
Continuous kernel 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 Continuous kernel image interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Continuous kernel image interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291453