Systems and methods for providing improved two pass resampling

Details Systems and methods for providing improved two pass resampling Systems and methods for providing improved two pass resampling

2002-03-15

2004-07-06

Bella, Matthew C. (Department: 2676)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

C345S427000, C382S276000, C382S277000

Reexamination Certificate

active

06760037

ABSTRACT:

COPYRIGHT NOTICE AND PERMISSION
A portion of the disclosure of this patent document may contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice shall apply to this document Copyright© 2001, Microsoft Corp.
FIELD OF THE INVENTION
The present invention relates to systems and methods for providing improved two pass resampling in a computing system. More particularly, the present invention relates to systems and methods for optimizing the quality of a resultant transformation in connection with two pass resampling algorithm(s) in a computing system.
BACKGROUND OF THE INVENTION
The two pass resampling algorithm provides an efficient way to process an arbitrary transformation on a raster image. The efficiency is gained by decomposing the transformation into two passes. The first pass maps every row of the image to a row of an intermediate image, and the second pass maps every column of the intermediate image to a column of the final result. The mapping of a row or a column is performed as a one-dimensional scan. Today's processors operate extremely fast with respect to one-dimensional arrays of data, and thus the two pass resampling algorithm is very efficient.
The decomposition into two passes is an approximation of the original two-dimensional mapping, and like any approximation, some error may result depending upon the signal being mapped and/or the original mapping being applied to the signal. Unfortunately, under certain combinations of circumstances, the resulting error may seriously degrade the quality of the result. The quality can be significantly improved by either pre-rotating the image by 90°, or by changing the order to scan columns-first. Permuting these two choices provides four variations, namely: (1) pre-rotating the data and processing row-first (2) pre-rotating the data and processing column-first, (3) no pre-rotation of the data and processing row-first and (4) no pre-rotation of the data and processing column-first. For any given mapping, one of the four variations will provide the best result. One prior art algorithm that attempts to choose the best of the four variations chooses the variation that produces the largest intermediate image area. While choosing the course that results in largest intermediate image area is a reasonable approach, unfortunately, such a choice does not always lead to the best choice. In this regard, the association of a large intermediate area with a good final result is heuristic, having no theoretical basis. The area of the intermediate image reflects the behavior of the algorithm on average, but good average behavior may conceal locally poor behavior or other aberration(s), as illustrated by
FIGS. 1A and 1B
.
FIG. 1A
illustrates a first problem with the method that selects one of the four variations based upon a maximization of the intermediate image area. In this example, the transformation is projective. As a result of the prior art method, the intermediate image of greatest area contains a singularity.
FIG. 1A
thus illustrates a first source of trouble in the two pass resampling algorithm, i.e., the “bottleneck” problem, wherein the data represented by the singularity cannot be reconstructed adequately due to the lack of information available at that point of the intermediate image.
The bottleneck problem is particularly acute when the mapping is a 90° rotation. In such a case, sampling rows-first transforms a horizontal line to a vertical one, such that the first pass shrinks the entire image to a single vertical line, from which the end result cannot be recovered. Similarly, a first vertical scan shrinks the entire image to a single horizontal line. The problem disappears if the image is pre-rotated by 90°. The example wherein the mapping is a 90° rotation is an extreme case where the end result is disastrous. Where the intermediate image has just one collapsed row, as in
FIG. 1A
, the result shows up as a tear in the final image. Thus, the method that selects the intermediate image with maximum area ignores the possibility of a portion of the intermediate image with a very small area.
Thus, a solution could be constructed which minimizes the bottleneck problem; however, minimizing the bottleneck would not in all cases solve the problems associated with a second source of trouble in the two pass algorithm, i.e., the aliasing problem. The aliasing problem is illustrated in
FIG. 1B
, which shows unwarranted aliasing of vertical edges in the resulting image.
The transformation employed in
FIG. 1B
stretches the lower portion of the image vertically, while shrinking the upper portion. While the bottleneck problem has been addressed, aliasing error has not been addressed. As a result, the fine pixels of any diagonal feature-line at the bottom are magnified by the transformation to visible steps, aliasing the line. The flaw is inherent in the transformation, but vertical lines are immune to it. Unfortunately, the first pass (rows-first) in
FIG. 1B
transforms vertical lines in the source to highly slanted diagonal lines in the intermediate image, and the vertical stretching in the second pass aliases them. This defect is highly visible on the image's vertical edges. Such aliasing is not the fault of the transformation, but rather the aliasing is introduced by the transformation's two pass decomposition. Even though the choice of the four variations is such that the bottleneck problem has disappeared, the aliasing problem persists. Thus, in addition to adequately handling the bottleneck problem, it would be desirable to provide a method that also adequately addresses the aliasing problem.
Thus, in view of the deficiencies associated with prior art two pass resampling techniques, improved systems and methods for providing two pass resampling are desired. In this regard, it would be desirable to provide two pass resampling systems and methods that address both bottleneck error and aliasing error. More particularly, it would be desirable to provide two pass resampling systems and methods that minimize effects from both bottleneck and aliasing error.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides systems and methods that improve two pass resampling in a computing system. The systems and methods address both bottleneck problem(s) and aliasing problem(s) to improve upon prior art two pass resampling techniques. In view of both bottleneck problem(s) and aliasing problem(s), for each of four possibilities associated with two pass resampling, the four possibilities being (1) pre-rotating the 2-D data and performing row-first processing (2) pre-rotating the 2-D data and performing column-first processing, (3) not pre-rotating the 2-D data and performing row-first processing and (4) not pre-rotating the 2-D data and performing column-first processing, the bottleneck error and the aliasing error associated with the possibility are calculated. Also, for each possibility, a value is computed based upon the bottleneck error and the aliasing error. The choice of the four possibilities is then selected in accordance with a comparison of the values.
Other features and embodiments of the present invention are described below.


REFERENCES:
patent: 5175808 (1992-12-01), Sayre
patent: 5204944 (1993-04-01), Wolberg et al.
patent: 5638068 (1997-06-01), Nickerson
patent: 5808623 (1998-09-01), Hamburg
patent: 6670965 (2003-12-01), McKeown
Chen, J.L. et al., “2-D Discrete Signal Interpolation and its Image Resampling Application Using Fuzzy Rule-Based Interference,”Fuzzy Sets and Systems, 2000, 114(2), 225-238.
Darwish, A.M. et al., “Adaptive Resampling Algorithm for Image Zooming,”IEEE Proc.—Vision, Image and Signal Proc., 1997, 144(4), 207-212.
Dodgson, N.A., “Qaudratic Interpolation for Image Resampling”,IEEE Trans. on Image

Affiliated with

Also associated with

Rating

Systems and methods for providing improved two pass resampling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Systems and methods for providing improved two pass resampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for providing improved two pass resampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3201049