Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
2000-03-31
2004-02-24
Do, Anh Hong (Department: 2624)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S236000, C382S294000, C382S295000
Reexamination Certificate
active
06697539
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to digital image scaling.
Digital image processing of images by a computer is a relatively recent development. In its short history, it has been applied to a variety of technical fields with varying degrees of success. The coordinate conversion of a two-dimensional digital data is known as “re-sampling”. In order to re-sample the digital input data, data processing techniques such as nearest neighbor interpolation, bilinear interpolation, and interpolation using the cubic convolution method are known.
Image scaling techniques may be differentiated according to the interpolation method used to compute a new value at each scaled location. Of particular interest are those techniques which operate in the spatial domain and employ local, polynomial interpolants. Of these, there are two primary approaches, namely, regional (two-dimensional) interpolants and profile-curve (one-dimensional) interpolants. In either case, the derived polynomial provides image values only for points in the interior to a given 2×2 pixel neighborhood (the domain) of the interpolation. Accordingly, to scale an entire image requires computing individual interpolants for each such neighborhood.
The nearest neighbor interpolation technique is the simplest interpolation scheme, wherein the data of the output pixel (picture element) is taken to be that of the input pixel nearest to the position to which it maps. This interpolation technique, however, introduces a sawtooth effect at the edges of the obtained image. On the other hand, bilinear interpolation obtains the output pixel by interpolating adjacent four-pixel neighborhoods, but still does not provide sufficient contour smoothing. This problem is particularly notable if the geometric operation involves magnification.
Region interpolant techniques typically involve either directly computing an interpolating surface or computing a set of weights based on an underlying set of 2D polynomial equations. In the case of interpolating a surface, the value at an interpolated position is obtained by directly evaluating the surface polynomial at that point. In the case of computing a set of weights, they determine the proportionate contributions of neighboring pixel values to the interpolated value. Techniques involving surface computations can be computationally intensive to compute and evaluate, and increasing in computational complexity as the degree of the polynomial increases. Furthermore, for degree d≧2, such surfaces may involve over-determined systems. For example, this occurs when a polynomial of degree d is fit to a (d+1)×(d+1) pixel neighborhood. Referring to
FIG. 1
, a bicubic surface is fit a representative 4×4 neighborhood. A detail of the surface section corresponding to the central 2×2 neighborhood is shown in
FIG. 2
together with exemplary pixel values. The pixel values for the 4×4 neighborhood of
FIG. 1
are shown at the bottom, with the central 2×2 neighborhood outlined. The central 2×2 neighborhood outlined in FIG.
1
and shown in
FIG. 2
is the only region used to interpolate image values that are to be used for the 2×2 region.
The principal benefit of a surface interpolant is that, once computed, it can provide values for any point interior to its 2×2 region by simply evaluating the surface at that point. In other words, there is no need to compute a new interpolant for other points within the region. However, as previously noted, it is computationally expensive to compute a surface interpolant. In addition, the system may be over-determined resulting in polynomials that do not exactly interpolate the boundary points of their central 2×2 pixel neighborhood. More significantly, the exact boundary interpolation results in interpolants computed for adjacent neighborhoods that do not agree in their common boundary points. Not only do the boundary values for the computed points not agree with one another, they do not even agree with the underlying image points. In other words, the use of the surface interpolant may result in discontinuities at the region boundaries.
To illustrate this effect,
FIG. 3
shows the comparison of the surface of
FIG. 2
with another surface computed for an adjacent 2×2 neighborhood. For convenience, each surface is displayed in its local coordinate system. However, it may be observed that their common points disagree in value. In particular, the values of 133.91, 120.24 vary significantly from the values of 136.715, 125.385, which should be identical.
One proposed improvement is to use an exactly determined (d+1)
2
×(d+1)
2
system comprised of the four 2×2 boundary pixels, their 1st derivatives, and their cross derivatives. Unfortunately, such a proposal is computationally expensive and inappropriate for a real time system with limited computational capability, such as a digital photocopier.
Referring to
FIG. 4
, the other principal approach of profile-curve interpolants uses profile curves fitting curves of degree d to corresponding d+1 contiguous pixels along d+1 adjacent rows (or columns). A transverse curve is then fit to corresponding points on the original curves, i.e., points with the identical row (or column) offset. An interpolated value is obtained by evaluating the transverse curve at the proper row (or column) offset. Profile-curve interpolants has the benefit of determining the value of any point along the ab line (aligned with C
5
) by evaluating transverse curve C
5
at the proper offsets. On the other hand, to compute the values of other points in the neighborhood (e.g., c or d) entails fitting a new transverse curve with the appropriate offset along base curves (C
1
, C
2
, C
3
, C
4
) and evaluating that new curve at the corresponding point position. Moreover, to evaluate any point in region R
2
involves a number of additional steps: fitting a new base curve to the four pixels to the right of curve C
4
; fitting a new transverse curve to the base curves at the appropriate offset; and evaluating the new transverse curve at the corresponding point position. Finally, to evaluate any point in region R
3
involves fitting four new base curves now centered on R
3
; fitting a new transverse curve; and evaluating the transverse curve at the appropriate position. Unfortunately, the profile-curve interpolants are not well suited to transformations that are not axis-aligned (e.g., rotation, shearing, or warping), since the interpolation along the base curves will rarely produce actual output values.
SUMMARY OF THE INVENTION
The present invention overcomes the aforementioned drawbacks of the prior art by providing a system for modifying an image consisting of a plurality of pixels from a first scale to a second scale. The system determines an integer matrix that is independent of the values of the plurality of pixels of the image. The system also determines a first vector for a region of the first scale representative of a surface based on the coordinates of the first scale. Also, the system interpolates pixel locations in the second scale by scaling the coordinates of points of the first scale and computing a scaled second vector. A third vector is determined based, at least in part, upon the product of the first vector and the second vector, where the third vector has uneven scaling of its terms. A plurality of the terms of the third vector based upon a fractional scaling factor related to said uneven scaling and summing the components of the third vector.
The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention, taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4193092 (1980-03-01), Stoffel
patent: 4578812 (1986-03-01), Yui
patent: 5007752 (1991-04-01), Yasumi et al.
patent: 5008752 (1991-04-01), Van Nostrand
patent: 5551137 (1996-09-01), Davis
patent: 5671298 (1997-09-01), Markandey et al
Charnoff Vilhauer McClung & Stenzel, LLP
Do Anh Hong
Sharp Laboratories of America Inc.
LandOfFree
Image scaling by exact 2D implicit polynomials 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 scaling by exact 2D implicit polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image scaling by exact 2D implicit polynomials will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3293345