Image analysis – Image enhancement or restoration – Intensity – brightness – contrast – or shading correction
Reexamination Certificate
1999-07-22
2003-05-20
Grant, II, Jerome (Department: 2724)
Image analysis
Image enhancement or restoration
Intensity, brightness, contrast, or shading correction
C382S298000
Reexamination Certificate
active
06567565
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 scaling antialiased original color images to prepare them for display on hard-copy or soft-copy and will be described with particular reference thereto. It will be appreciated, however, that the invention is also amenable to other like applications.
The use of graphics in computer and communication applications is very widespread and is becoming increasingly 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 converted into a raster image file. Printing devices then include electronics and software for making marks on paper corresponding to positions in the raster image file where the image values so indicate.
Page description language interpreters may include means for printing antialiased images. In the context of gray-scale raster 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 raster data, antialiasing refers to introducing intermediate colors along the edges of objects to achieve the same effect in lower resolution color images.
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 often cheaper to manipulate data for lower resolution images. When it becomes desirable to print the image stored using low-resolution data, the data must then be scaled up to a higher resolution. In this manner, a high-resolution image is produced using less computing power than would otherwise be required. Similarly, the image is transmitted using substantially less transmission bandwidth. For example, an image to be printed at 1000 square inches per minute, 600×4800 spots per inch, and 1 bit per pixel, if transmitted at full resolution, requires 48M bits per second raw bandwidth. On the other hand under the same circumstances, if the image is computed at 400 spots per inch, antialiased to 8 bits per pixel, and transmitted before scaling, the total required bandwidth is only 21M bits per second.
Scaling up a pixel of an image included within an area having a single, constant color is relatively simple. More specifically, each pixel within the area of constant color is replaced by a group of pixels having the same color.
Scaling up pixels along edges or other geometries, on the other hand, is relatively more complicated.
FIG. 1
illustrates a portion of an antialiased image
10
having dark lines
12
that are approximately 2.5 pixels thick. The lines
12
in
FIG. 1
are scaled up for improved visibility and are best viewed at approximately five (5) feet for receiving a correct subjective impression.
FIG. 2
illustrates a magnified view
14
of the top, left portion of FIG.
1
. The edge position
16
of
FIG. 2
is represented by pixels having intermediate gray-levels. When the intermediate gray-levels are halftoned, as shown in
FIG. 3
, the resulting appearance
20
depends strongly on where the dot center is relative to the pixel. If the image is halftoned using a typical high-addressability scheme, in which each contone input pixel is replaced with a set of binary output pixels, some of the generated halftone dots
22
are disconnected from the line
24
(see FIG.
3
). Several conventional algorithms (e.g., hyperacuity and tagged antialiased imaging) exist for scaling up pixels to be halftoned.
Hyperacuity seeks to improve image quality without increasing overall resolution. Information concerning the location of where edges are to be printed is maintained with a high degree of accuracy, but without increasing the resolution of the input data. A byte-map, instead of a bit-map, is used for the desired image of text (or lineart) to be printed. Each bit position is replaced with a multi-bit byte of coded information, such as a gray value or pixel. The information contained in these multi-bit gray pixels is processed with neighboring gray pixels within the hyperacuity printer to generate an identification of where the edges should be placed. This information, in turn, is used to adjust the exposure in the printer in an optimal manner in order to produce edges that do not have a stair stepping effect. Hyperacuity printing requires a preprocessing stage for deciding when to simply halftone the image and when to treat it as line art and interpolate an edge position.
Tagged antialiased imaging involves thresholding input data into various categories of brightness. Template matching is used to determine whether the thresholded data “looks” like an antialiased edge. The template matching approach tags pixels along the edge to indicate whether the edge is dark on the left, the right, or top/bottom. The halftone screen is changed in accordance with which of the four (4) cases occurs (i.e., left, right, top/bottom, or none). In the left and right cases, a high-frequency screen having darkness and lightness growing from one side of the screen is used. In the top/bottom case, the screen grows from the center.
Tagged antialiased imaging is based on an assumption that edges worth rendering as antialiased are only identified by intermediate color-levels. Furthermore, neither of the methods discussed above is capable of determining whether an edge exists or an orientation of an edge when the edge divides two regions of color that are not full (or nearly) on and off. Therefore, this information must be supplied to the hyperacuity and tagged antialiased rendering algorithms.
One approach used for generating tags for hyperacuity and tagged antialiased rendering is to threshold the data so that pixels with one neighbor with more than one threshold and one with less than another threshold must be present. Having a threshold at which the rendering technique changes invariably leads to the possibility of artifacts. First, consider a 95% black line on a sweep from white to 50% gray. At some point in the sweep, the contrast drops to a point that the rendering technique changes, leading to an artifact at this point. Second, consider a pictorial image. Only very high contrast edges in such an image will retain an acceptable appearance if rendered as lineart, or tagged to use the high frequency halftone. If the threshold is too low, far too many pixels within an image fit the criterion and, therefore, use the high-frequency halftone. Even synthetic data may not switch smoothly between the methods. A line at certain angles may have pixels that appear to meet the criterion, whereas elsewhere on the same line there are pixels that do not.
FIG. 3
illustrates that a variety of gray-levels result in such situations.
As illustrated in
FIG. 4
, a partial dotting
26
preserves an edge
28
when a “clean” edge is between first and second gray-levels
30
,
32
, respectively. Despite the fact that the edge
28
is not between black and white, it is preserved as well as can be achieved without changing the intensity along the edge
28
. This results as a natural result of halftoning an edge between two gray levels if the edge is at the same resolution as the halftone dot.
Another conventional method for transforming a pixel from low-resolution to high-resolution looks at a window around the pixel. Patterns are identified within the pixels in the window. The patterns are compared to known samples at both 300 spots per inch (“spi”) and 600 spi. There are several drawbacks with this method. For example, the original image may contain patterns that are not recognized. Furthermore, the patterns viewed at 300 spi may equally translate to two (2) different objects at 600 spi. Also, in order to be able to accur
Fay Sharpe Fagan Minnich & McKee LLP
Grant II Jerome
Xerox Corporation
LandOfFree
Antialiased image rendering algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Antialiased image rendering algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Antialiased image rendering algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3041285