Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1998-06-11
2002-12-24
Mehta, Bhavesh (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S299000, C382S205000, C382S165000, C382S164000, C358S538000, C358S448000, C348S453000
Reexamination Certificate
active
06498868
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to scaling (i.e., enlarging or reducing) color images. It finds particular application in conjunction with choosing an appropriate algorithm for scaling an antialiased original color image before it is combined with a new image, and will be described with particular reference thereto. It will be appreciated, however, that the invention will also find application for choosing a scaling algorithm for video images or other types of images.
The use of graphics in computer and communication applications is very widespread and is becoming increasingly more prevalent. A computing device often transmits a document including graphical data to a printing device using a page description language. Page description languages (e.g., the PostScript® language) include interpretive programming commands useful for implementing powerful graphics capabilities. When transmitted via a page description language, graphical data is typically first converted to a bit-map data file. Printing devices then include an interpreter for deciphering the bit-map data into raster graphics.
Recently, page description interpreters have begun to include means for antialiased images to be printed. In the context of gray-scale or black and white bit-map data, antialiasing refers to introducing intermediate intensity levels along edges of the object for smoothing jagged lines in lower resolution images. Similarly, in the context of color bit-map data, antialiasing refers to introducing a single color which is representative of various colors along the edges of an object to achieve the same effect in lower resolution color images.
Devices such as scanners and/or CCD cameras produce data which are similar to antialiased data. Data produced by those devices often includes optical blurring in intermediate values appearing along edges. The optical blurring provides the appearance of smoothness.
Because an antialiased image by definition is a gray-scale image, it is not possible to print an antialiased image directly on a black and white printer (i.e., a printer not capable of producing gray-scale images). Therefore, antialiased gray-scale images must first be converted to black and white (binary) images before they are printed to such printers. Typically, converting an antialiased image to a black and white image includes “scaling-up” the image.
One benefit of using antialiasing is that it reduces the total amount of data that must be computed and transmitted. As an example, assume a computer creates a 300 dot per inch (“dpi”) by 300 dpi antialiased gray-scale image. The computer transmits the 300 dpi×300 dpi gray-scale image to a black and white printer (e.g., via a cable). The printer includes a scaling algorithm which scales-up the 300 dpi×300 dpi gray-scale image to a 1200 dpi×1200 dpi image and subsequently converts it to black and white. Because the resulting 1200 dpi×1200 dpi image is black and white, it only has a single bit of data per pixel. The 300 dpi×300 dpi gray-scale image, on the other hand, has multiple (e.g., eight (8)) bits of data per pixel (i.e., one level of pixel data for each shade of gray). For each level of the 300 dpi×300 dpi gray-scale image, the 1200 dpi×1200 dpi black and white image has four (4) times as many pixels in each of the four (4) directions. In this sense, the 1200 dpi×1200 dpi black and white image appears to contain sixteen (16) times as much data. However., because the 1200 dpi×1200 dpi black and white image only contains one (1) bit per pixel and the 300 dpi×300 dpi gray-scale image contains eight (8) bits per pixel, the 1200 dpi×1200 dpi scaled-up image actually only contains two (2) times as much data.
In general, the cost of computing power necessary for manipulating data is at least proportional to the amount of data to be manipulated. Therefore, it is cheaper to manipulate data for lower resolution images. In the example described above, the lower resolution gray-scale image is stored and manipulated until the image is printed. Only at that time is the gray-scale image scaled-up to the black and white image. Consequently, a high resolution black and white image is produced using only about one-half of the computing power which would typically be required to achieve such an image. Similarly, that image may be transmitted using only one-half of the transmission bandwidth.
In addition to printing, there are other reasons for wanting to scale up an image, or some portion thereof. For example, it is often desirable to combine new image data with an existing image. Combining the images results in different pixel values for the final image. In this case, both images can be either gray-scale or color. Sharper images are produced when higher-resolution, as opposed to lower-resolution, images are combined. Therefore, it is desirable to scale-up an original antialiased image before it is combined with a second image.
One method of combining images is known as alpha-blending. For color images, alpha-blending uses the fractional coverage of the object contained in the new image to determine the fraction of the new color to be combined with the existing background (i.e., the original color). Alpha-blending assumes the background is a constant color. Specifically,:
I
NEW
=I
BACKGROUND
+&agr;(
I
OBJECT
−I
BACKGROUND
)
where &agr; is the fraction of the pixel covered by the new object. While alpha-blending works for zero or full coverage, it is not reliable when a background object only partially covers a pixel.
FIGS. 1A
,
1
B and
1
C illustrate three different high-resolution pixels representing edge geometries of a pixel in an original color image. Note that in
FIGS. 1A
,
1
B and
1
C only one-half of the original image covers the pixel. More specifically, one-half of the original pixel is solid cyan
2
while the other half of the pixel is solid white
3
.
FIG. 2
shows an image of the pixel after any one of the high-resolution pixels of
FIGS. 1A
,
1
B, and
1
C is antialiased. The antialiased pixel shown in
FIG. 2
is represented by a shade
4
of cyan which is lighter than the original pixels shown in
FIGS. 1A
,
1
B and
1
C. As discussed above, one drawback of the weighted average technique of alpha-blending is that the geometry of the original image is lost when an image is antialiased. In other words, color distinctions along edges of the original image are lost. Therefore, if the antialiased original image is combined with a second image, correct colors may not be produced along edges of the resulting image.
FIGS. 3A
,
3
B and
3
C illustrate the three high-resolution pixel geometries of
FIGS. 1A
,
1
B and
1
C, respectively, in which a new object having a solid magenta color
5
covering the right-half of the pixel is to be combined with the original cyan object.
FIGS. 4A
,
4
B and
4
C illustrate the correct rasterization which would result from alpha-blending the images of
FIGS. 3A
,
3
B and
3
C, respectively. More specifically,
FIG. 3A
illustrates a geometry having a left-half which is cyan
2
and a right-half which is magenta
5
(i.e., the new magenta
5
object does not cover any of the original cyan
2
object).
FIG. 4A
shows a dark purple pixel
6
results when the colors of
FIG. 3A
are blended correctly.
FIG. 3B
illustrates a geometry having a left-half which is white
3
and a right-half which is magenta
5
(i.e., the new magenta
5
object completely covers the original cyan object).
FIG. 4B
shows a pink pixel
7
results when the colors of
FIG. 3B
are blended correctly.
FIG. 3C
illustrates a geometry having a top left-half which is white
3
, a bottom left-half which is cyan
2
, and a right-half which is magenta
5
(i.e., the new magenta
5
object covers one-half {fraction (
1
/
2
)} of the original cyan
2
object).
FIG. 4C
shows a light purple pixel
8
results when the colors of
FIG. 3C
are blended correctly.
As discussed above, because there is only a limited amount of memory on a com
Fay Sharpe Fagan Minnich & McKee LLP
Kassa Yosef
Mehta Bhavesh
Xerox Corporation
LandOfFree
Image scaling using pattern matching to select among scaling... 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 using pattern matching to select among scaling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image scaling using pattern matching to select among scaling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960030