Computer graphics processing and selective visual display system – Display peripheral interface input device – Light pen for fluid matrix display panel
Reexamination Certificate
1998-04-29
2001-08-28
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Display peripheral interface input device
Light pen for fluid matrix display panel
C345S182000, C345S440000, C345S440000, C345S440000
Reexamination Certificate
active
06281875
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to image processing by interpolation so as to obtain interpolated values between pixels in an existing image. In particular, the invention pertains to interpolation based on the existence of diagonal gradients in image data.
2. Description of the Related Art
Scaling is one common form of image processing, whereby image data of a first size is scaled to image data of a second size. Consider, for example, a situation in which a computer user is viewing image data on a computer screen, which physically appears to the user as having measurements of 3½×5 inches. Given screen resolution of 72 dpi (dots per inch), the image data measures 252×360 pixels. If such an image were thereafter to be printed, given a printer resolution of 600 dpi, the image would be printed to a size of 0.42×0.60 inches, which would be entirely unacceptable to the user. Accordingly, before printing, the image data originally comprised by 252×360 pixels must be scaled to a size of 2100×3000 pixels, so that when printed on the 600 dpi printer the resulting image again measures 3½×5 inches.
To scale images from a first pixel dimension to a second pixel dimension, interpolation is generally unavoidable. Interpolation is a procedure by which image data for pixels between existing pixels of the source image is derived. Many interpolation techniques have been proposed, such as bi-linear, bi-cubic and two-step linear interpolation. These techniques usually use the four (or more) surrounding pixels of existing data in order to derive pixel data for a target pixel.
Two-step linear interpolation will now be explained with reference to FIG.
4
. As shown in
FIG. 4
, destination image data of size Q pixels high by R pixels wide is desired to be derived from source image data of size M pixels high by N pixels wide. With two-step linear interpolation, to derive a data value for a pixel in the destination image, data values for the four corresponding nearest neighbor pixels in the source image are found, and these four data values are interpolated horizontally to form two intermediate horizontal data values. These two intermediate data values are then further interpolated vertically to form the data value for the desired pixel in the destination image.
Specifically, and again referring to
FIG. 4
, to derive a data value for the pixel at position (r, q) in the destination image, the corresponding position (n, m) in the source image is derived using simple scaling equations as follows:
n
=
N
R
r
m
=
M
Q
q
Data values V
1
, V
2
, V
3
and V
4
for the four corresponding nearest neighbor pixels in the source image are then found. Values for these four pixels are interpolated horizontally and then vertically, using the following interpolation equation so as to obtain a value V for the target pixel at (r, q) in the destination image:
V=
(
V
1
(1−
x
)+
V
2
x
)(1−
y
)+(
V
3
(1−
x
)+
V
4
x
)
y
where x is the horizontal distance in the source image between the location of the target pixel and the location of the nearest neighbor pixel to the left of the target pixel, and where y is the vertical distance in the source image between the location of the target pixel and the location of the nearest neighbor pixel above the target pixel.
Mathematically, it can be shown that the foregoing equation is the same as the following equation, which can be interpreted based on relative areas:
V=V
1
(1−
x
)(1−
y
)+
V
2
(
x
)(1−
y
)+
V
3
(1−
x
)(
y
)+
V
4
(
x
)(
y
)
Although such interpolation methods produce acceptable results in many situations, one situation in which these interpolation methods fail is where diagonal gradients or lines are present in the source image. When scaled, diagonal gradients and lines produce distortions that manifest themselves as periodic zigzag structures (also known as staircasing), corresponding to an aliasing that is introduced by the interpolation.
An example of these distortions is illustrated in
FIGS. 1
a
through
1
d
.
FIG. 1
a
is a view of an image with diagonal gradients scanned at 300 dpi.
FIG. 1
b
is an enlarged view of the same image scanned at 600 dpi. It is desired in this example to scale the image shown in
FIG. 1
a
up to the resolution of the image shown in
FIG. 1
b
. In order to accomplish this scaling, pixel interpolation must be performed.
FIG. 1
c
shows the result of scaling performed by a conventional pixel interpolation method, which has produced aliasing. This aliasing is evident in the staircasing pattern shown in
FIG. 1
c
, which was not in the source image shown in
FIG. 1
a
and which is an unwanted distortion of the image.
While other interpolation techniques such as bi-linear and bi-cubic interpolation tend to minimize such aliasing artifacts, these interpolation methods often decrease performance and sometimes do not reduce aliasing to any significant extent.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide for improved interpolation which, because it is based on a detection of diagonal gradients, produces reduced aliasing while not significantly affecting performance.
According to one aspect of the invention, a diagonal gradient is detected based for example on data values of four corresponding nearest neighbor pixels in the source image. In the absence of a diagonal gradient, interpolation based at least on all four neighbor pixels, such as the aforementioned two-step linear interpolation, is performed so as to derive a data value for the target pixel in the destination image. On the other hand, if a diagonal gradient is detected, then interpolation is based only on two diagonally-adjacent pixels. Good performance has been found by interpolating across the gradient (i.e., along a diagonal edge), but better performance has been found by interpolating along the gradient (i.e., across the edge).
Preferably, detection of a diagonal gradient is performed by the simple expedient of comparing data values for the four corresponding neighbor pixels in the source image. If the first pair of diagonal pixels have data values that are close, while the second pair of diagonal pixels have data values that differ significantly, then it can be determined that a diagonal gradient is present.
Thus, in one aspect, the invention is a method of interpolation so as to obtain data values for a destination image based on data values for pixels in a source image, with the destination image being scaled relative to the source image. Based on pixel position in the destination image, a corresponding position in the source image is calculated. Based on the position, surrounding pixels in the source image are inspected so as to test for the presence of a diagonal gradient. In the absence of a diagonal gradient, a data value for the target pixel in the destination image is calculated by interpolation based on at least all four of the surrounding pixels. On the other hand, if a diagonal gradient is detected, a data value for the target pixel in the destination image is calculated based upon interpolation using only diagonally-adjacent pixels in the source image, and preferably diagonally-adjacent pixels along the gradient.
Preferably, a diagonal gradient is detected based on a comparison between pairs of diagonally-adjacent pixels in the source image, with the presence of a gradient being confirmed by a first pair of the diagonally-adjacent pixels having data values that are similar with a second pair of diagonally-adjacent pixels having data values that differ significantly. In the absence of a gradient, it is preferred that two-step linear interpolation be performed based on four surrounding pixels so as to determine a data value for the target pixel. On the other hand, in the presence of a gradient, it is preferred that interpolation be performed based on only a single pair of diagonally-adjacent pixels, and preferably the pa
Hui Jonathan
Zhao Jun
Zheng Tong
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Stevenson Philip H.
Zimmerman Mark
LandOfFree
Gradient-based pixel 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 Gradient-based pixel interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gradient-based pixel interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520497