Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-08-24
2001-04-17
Boudreau, Leo H. (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S293000, C382S300000, C348S561000, C348S581000, C348S582000, C345S440000, C358S451000, C708S208000, C708S290000
Reexamination Certificate
active
06219464
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data interpolation and in particular to a method of generating an upsampled target pixel from input source data and an apparatus for performing the method.
BACKGROUND OF THE INVENTION
Video images can be represented as a two-dimensional array of digital data with each data point in the array representing a pixel of the digitized video image. The value assigned to each pixel determines its intensity and/or colour when the video image is recreated. In the video imaging art, it is often desired to magnify a video image to arbitrary magnification factors to create enlarged video images. When creating an enlarged image from an original image represented by a digital data array, it is necessary to interpolate between pixels of the original digital data array to generate upsampled pixels between consecutive lines and pixels of the original digital data array to “fill” in pixels of the enlarged image. Prior art techniques to create these enlarged video images have been considered.
It is common practice in the prior art to use an orthogonal, Cartesian approach to interpolate separately the vertical and horizontal dimensions of the digitized video image to be enlarged. However, this technique typically results in enlarged video images which suffer from jagged edges commonly referred to as “stairstepping”. Improvements in the interpolation method used may reduce the stairstepping, but it cannot be completely avoided because it is inherent when using this technique.
A directional interpolation scheme addresses the stairstepping problem. Directional interpolation recognizes the geometric structure in images. With directional interpolation, it has been found that interpolation along the edges produces improved results over interpolation across the edges. Directional interpolation involves analysing local image structure and performing the interpolation based on the image structure.
U.S. Pat. No. 5,019,903 to Dougall et al. discloses an apparatus for directionally interpolating between lines of a supersampled digital signal. The apparatus calculates gradient vectors for use in directionally interpolating a vertically upsampled line. This operation makes the apparatus best suited for line-doubling deinterlacing applications.
U.S. Pat. No. 5,347,599 to Yamashita et al. discloses an adaptive interpolation method and an apparatus using correlation detection. The apparatus performs calculations on lines of pixels of the source data to select the desired upsampling direction. However, similar to Dougall et al, this apparatus is also best suited for line-doubling deinterlacing applications.
Although Dougall et al. and Yamashita et al. disclose alternative directional interpolation methods to generate upsampled pixels, their design is such as to support only fixed, integral vertical resize factors. Accordingly, there exists a need for an improved interpolation method and apparatus that supports arbitrary, fractional resize factors in both vertical and horizontal dimensions.
It is therefore an object of the present invention to provide a novel method and apparatus for generating an upsampled target pixel from input source data.
SUMMARY OF THE INVENTION
The present invention performs directional interpolation to arbitrary, fractional resize factors. First, an interpolation direction is selected corresponding to any low-frequency edges in the source data. Next, directional interpolation is performed to generate intermediate pixels. The intermediate pixels are then interpolated, possibly non-orthogonally, to generated the desired upsampled pixel.
More specifically, according to one aspect of the present invention there is provided a method of generating an upsampled target pixel from input source data comprising the steps of:
(i) comparing pixels of different lines of said source data in a region surrounding an upsampled target pixel to be generated in at least two different directions;
(ii) selecting an interpolation direction based on the comparisons of step (i);
(iii) interpolating between selected pixels of different lines of said source data in the interpolation direction determined at step (ii) and computing intermediate pixels on a line segment passing through said upsampled target pixel; and
(iv) interpolating between the intermediate pixels to generate said upsampled target pixel.
In the preferred embodiment, the line segment is parallel to the lines of the source data. Restricting the line segment to be horizontal as such, greatly simplifies the calculation of the intermediate pixels and the upsampled target pixel.
In one possible embodiment, pixels of different lines of source data are compared in three different directions, including a vertical direction, and opposite oblique directions forming an angle with the vertical direction that is in the range 0<angle<90°. During the comparisons of step (i), difference values between the compared pixels are generated, the difference values being used to select the interpolation direction at step (ii).
In this embodiment, prior to step (ii), the difference values resulting from the comparisons in the three directions are compared to determine whether the differences therebetween are within a threshold. The direction associated with the smallest difference value is selected as the interpolation direction when none of the differences are within the threshold. When the differences between the difference values resulting from the comparisons in all three directions are within the threshold, the vertical direction is selected as the interpolation direction. When the difference between the difference values resulting from the comparisons in the vertical direction and only one of the oblique directions is within the threshold, that oblique direction is selected as the interpolation direction. When the difference between the difference values resulting from the comparison in the two oblique directions is within the threshold, additional pixels of the different lines of source data are compared in the opposite oblique directions. The difference values generated as a result of these comparisons are compared. When the difference between the difference values resulting from the comparisons of the additional pixels is within the threshold, the vertical interpolation direction is selected as the interpolation direction.
In another embodiment the line segment is once again parallel to the lines of the source data but this time pixels of the different lines of source data are compared in seven directions are at step (i). These directions include the vertical direction and three pairs of opposite oblique directions forming varying angles with the vertical direction that are within the range 0<angle<90°. Difference values between the compared pixels of step (i) are calculated.
In this embodiment, the set of difference values to the left of the set under consideration and the set to the right are also examined. The three difference values for each possible oblique interpolation direction are summed and compared to determine if the differences therebetween are within a threshold. When none of the differences are sufficiently small to indicate a low-frequency edge in the source image, then the vertical direction is selected as the interpolation direction. When none of the differences are within the threshold, then the oblique direction associated with the smallest difference value is selected as the interpolation direction. When difference values associated with a “right-ward” oblique direction and a “left-ward” oblique direction are within the threshold, then the vertical direction is once again selected as the interpolation direction. Otherwise one of the oblique directions is selected.
According to another aspect of the present invention there is provided an apparatus for generating an upsampled target pixel from input source data comprising:
comparison means for comparing pixels of different lines of said source data in a region surrounding an upsampled target pixel to be generated, in at least two d
Greggain Lance
Ngo Calvin
Boudreau Leo H.
Genesis Microchip Inc.
Mariam Daniel G.
LandOfFree
Source data 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 Source data interpolation method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Source data interpolation method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2481160