Encoding Method for Deferred Anti-Aliasing

A method for increasing the speed of color conversion during the printing of pages containing images in different color spaces by encoding to reduce the number of pixels by a factor of two prior to the color space conversion step.

In a printing system having low resolution, the boundaries between text letters or computer generated graphics and the background color may be jagged. This is called "aliasing". On the other hand, contone pictures usually have softer outlines, and aliasing is not a problem. For this reason, text and graphics are frequently supplied at higher resolutions than contone.

When combining text and contone in a single page to be printed, the two different pixel densities, when they occur, need to be equalized, and to preserve image quality, it is the contone pixel density that is typically increased up to the density of the text pixel density. Thus, for example, if the contone has a density of A by B pixels per unit area and the text has a density of 2A by 2B pixels, the contone pixels will be increased up to 2A by 2B, by duplicating pixels, before being combined. The resultant picture is not always optimal, so some kind of filtering or image enhancement is usually applied at this stage.

Now the page can be printed, but it frequently happens that the pixel density that the printer can print is less than the density that is being processed, and so the pixel density must be reduced. To continue with the above example, the page, which has been assembled into a 2A by 2B set of pixels must now be printed at a density of A by B. The fundamental challenge in accomplishing this reduction is to minimize any losses in image quality and to prevent aliasing from re-occurring. A common process for doing this is shown in FIG. 1. First, the image 10 can be divided into aligned 2-by-2 blocks of "subpixels"11, where an aligned block contains four pixels of contone which originated from one original contone pixel, or contains four pixels of text or graphics or background. These are averaged to compute a new "full pixel"12 which can be printed as the final image 13.

In the situation where the printer can print in full color,--assume CYMK,--there must be a color conversion step to convert all of the color images into one common color space. This is necessary since pixels of different color spaces can not be averaged. Thus, for example, if some of the areas within the image 10 are RGB and some CYMK, then all images scanned into the system in RGB must be converted into CYMK before the subpixels of FIG. 1 can be averaged. This color conversion step, which must be accomplished before the averaging step at the high-density subpixel level, is time consuming because of the larger number of subpixels at the higher density, and will slow down the system throughput if not compensated for. What is required is a faster color conversion process.

First, it must be taken into consideration that the image is presented to the color converter one scan line at a time. Thus, in the prior art, to average an aligned block of 2 by 2 subpixels, there must be an averaging of the first two subpixels of the aligned set of four subpixels during the first scan, and the storing of partial results for every block, prior to the presentation of the second scan and the completion of the averaging process. This is shown in FIG. 2 where an aligned pair of subpixels 11 from the high resuolution image 10 are averaged to form a first scan halfpixel 14. During the second scan, the second scan halfpixel 15 is computed, and both halfpixels are averaged to form the fullpixel 12. In this situation, the color conversion must occur before the two subpixels are averaged. Thus, more specifically, the problem becomes: how the color conversion process can be speeded up in the situation where the subpixels are still present in pairs in the system.

The solution is based on the concept that there is a fair amount of redundancy in almost all images, and that can be taken advantage of in a process which has an occasional possibility of losses, but where the losses are almost never perceptible to the viewer.

There is redundancy in most images. For example, in the common case of solid color text over a full color picture background, the redundancy of the text portion is clear: any pixel within a text character outline is the same as any other. Also within the picture portion, most pixels are the same or almost the same as neighboring pixels. Thus, if the two subpixels that must be color converted are replaced by one pixel plus a tag pointing to another pixel that can be used later in the averaging process, then the color conversion can be done on the single pixels (with tags) and the averaging process done later by finding the tag-designated pixels and using them in the averaging process. The result is that the number of pixels is reduced from two to one before the color conversion process is performed, and later expanded back to two for the averaging step.

The tag for each pixel in this case need only be a few bits, two in this described embodiment. The set of candidates for tag-designated pixels is therefore small, being confined to the previous and next halfpixels in this described embodiment, but there is usually a neighboring pixel that can be used. Moreover, the system is lossy only where there is no neighbor that has the same color, and this would happen only if there were many different colors within a small local area. This is relatively rare, but also, the production of a wrong color for one pixel where there were many different colors within a small local area would hardly be noticeable to the viewer, especially after the image quality improvement achieved by the anti-aliasing.

To summarize all of the above by the use of a simplified numerical example, assume that two subpixels must be color converted and averaged. The first subpixel to be color converted and averaged has a value of 6 (and is preceeded by several 6'), and the second has a value of 8 (and is followed by a 9). The average value of the two subpixels to be averaged (6 and 8) is therefore 7. To speed up the color conversion process, this invention deletes the first subpixel and substitutes for it a tag that states that in the averaging process, the previous pseudo-halfpixel (with a value of 6) should be used. Hence, the two subpixels have been converted into one pixel (the second pixel) and a tag, and the color conversion is applied to that one pixel.

After color conversion, the pixel designated by the tag (the previous pseudo-halfpixel with a value of 6) is substituted for the tag, and the averaging produces an average of 7 (from the inputs of 6 and 8). This is the same answer as the one that would have been produced with the original two subpixels, and the color conversion process takes half the time it would have otherwise.

FIG. 1 is a diagram of a simplified prior art anti-aliasing process.

FIG. 2 is a diagram of the prior art process of FIG. 1 showing how it is divided into the processing of two scans in series.

FIG. 3 shows how the process of this invention uses pseudo-halfpixels during the color conversion step.

FIG. 4 describes the encoding algorithm of this invention in pseudo-code.

FIG. 5 is a table of the results of the encoding process of this invention.

FIG. 6 shows how halfpixels are generated from pseudo-halfpixels in the decoding process of this invention.

FIG. 7 shows a resultant system that implements the process of this invention.

This invention, as shown in FIG. 3, is an improvement over the line by line implementation of the 2.times.2 anti-aliasing system of FIG. 2. Just as in the original line-by-line approach, it starts by taking an aligned pair of adjacent subpixels, T, U, from the same raster scanline of the starting image. As described above, the next step is color conversion, and here it would be preferable if the stream of subpixel pairs can be reduced to a stream of single subpixels, which would reduce the computation overhead by 50%. This is done by reducing each pair, in turn, to a single pseudo-halfpixel which contains one subpixel and a tag pointing to another pseudo-halfpixel. Some obvious ways to accomplish this are immediately obvious. For example, if the current pair of subpixels are the same color, then only one is needed, and the tag can specify that the same pixel be doubled to two subpixels for the later averaging step. Another simple case is that one of the subpixels is identical to the previously precessed pseudo-halfpixel. In this case, the result would be one subpixel and the tag indicating that the other subpixel in the averaging step should be copied from the previous pseudo-halfpixel. The complete algorithm for deciding on which subpixel should be used for the pseudo-halfpixel, and which other pseudo-halfpixel should be used for the object of the tag is shown in FIG. 4.

The assumption is that a string of pseudo-halfpixels, . . . S.sub.i-3, S.sub.i-2 and S.sub.i.times.1 have already been generated from the subpixels . . . T.sub.i.times.3, T.sub.i.times.2, T.sub.i.times.1, and . . . U.sub.i.times.3, U.sub.i.times.2 and U.sub.i.times.1, before the computation of the current pseudo-halfpixel S.sub.i is started.

The first step is to determine whether the two subpixels are the same. That is, check if T.sub.i =U.sub.i. If so, the tag indicates that one subpixel can be used and that the other subpixel is the same, so that Tag.sub.i =CurrColor.

If the two subpixels are not the same, then test to see if T.sub.i =S.sub.i-1. That is, check if the current subpixel T.sub.i is the same as the previously produced pseudo-halfpixel S.sub.i-1. If it is, then subpixel U.sub.i is used as the pseudo-halfpixel S.sub.i, and the tag points to the previous pseudo-halfpixel, so that S.sub.i =U.sub.i and Tag.sub.i =PrevColor.

If T.sub.i is not equal to U.sub.i-1, then U.sub.i is tested to see if it is the same as the previous pseudo-halfpixel, that is, whether U.sub.i =S.sub.i-1. If so, then Ti is used as the pseudo-halfpixel S.sub.i, and the tag points to the previous pseudo-halfpixel. The result of all of the above is that if the subpixels are the same, then one of them can be used for the pseudo-halfpixel, and that if one of them is the same as the previous pseudo-halfpixel, then the previous pseudo-halfpixel can be pointed to by the tag, and the other subpixel used as the pseudo-halfpixel.

If none of the above options are available, then the algorithm starts to compare the current subpixels to the next pair. If T.sub.i =T.sub.i+1 and T.sub.i =U.sub.i+1, then the next two subpixels are the same and the current tag can refer to the next pseudo-halfpixel, so that Tagi=NextColor, since the next pseudo-halfpixel will be equal to subpixel T.sub.i.

The remainder of the algorithm proceeds as is shown in FIG. 4. In all cases, the pseudo-halfpixel S.sub.i will be set to the color of one of the current subpixels T.sub.i or U.sub.i, and the Tag will be set to indicate either the current color (if both subpixels are the same), the color of the previous pseudo-halfpixel, or the color of the next pseudo-halfpixel.

FIG. 5 shows the same information in a different form. The letters a, b c, d, e and f represent any six different colors, and * =don't care. Thus, on the first line of the table, regardless of the colors of the previous and next pair of subpixels, if the current two subpixels are the same color, then the current pseudo-halfpixel will have the same color and the Tag will be Current Color, which means that the subpixel will simply be duplicated to form the other subpixel before averaging.

The second line shows that regardless of the colors of the next subpixel pair, if the two previous subpixels and subpixel T.sub.i are the same color, then U.sub.i will be used as the color of the current pseudo-halfpixel, and the Tag will point to the color of the previous pseudo-halfpixel. All of the other possible options are listed thereafter.

Notice that on lines 6 through 9 of the table, if the test fails, the previous subpixels are assumed to be c and d, and the last 9 lines of the table are used.

Refering back to FIG. 3, each pseudo-halfpixel, S plus tag, in the first line is formed, and the color of each pseudo-halfpixel is converted to the common color space. Then, the tag is used to generate the other subpixel, and the two can be averaged to form halfpixel X. Note that since the previous, current and next pseudo-halfpixels are all now color converted, after the tag is used and before averaging, both subpixels will be in the converted color space even though only one of the subpixels was actually converted. That is the point of this invention.

The process proceeds with the next scanline to produce halfpixel Y, and X and Y are averaged to produce the new fullpixel Z.

As stated above, after color conversion, the current pseudo-halfpixel is used as one of the two subpixels for the purpose of averaging while the tag is used to get the other subpixel. FIG. 6 shows this algorithm. If the two subpixels were the same color (CurrColor), the average is equal to either subpixel, so nothing else is required. If the tag=PrevColor, the color of the previous pseudo-halfpixel is used. Otherwise, the color of the next pseudo-halfpixel is used. This operation converts one color converted pseudo-halfpixel into two color converted subpixels.

The resultant system is shown in FIG. 7. A computer 23 receives full color image data from a character generator 20, a terminal 21 which generates computer generated graphics and a scanner 22 which scans in pictures. The computer will compose a page in the form of a bit map 24 having any combination of data, including text or graphics over pictures. Assume the bit map is 2A by 2B pixels per unit area, and is output one scan line at a time. Within each scanline, each aligned set of two subpixels is encoded in encoder 25 according to the process described herein into one pseudo-halfpixel to yield a density of A by B pixels per unit area, which is color converted 26 if necessary. The decoder 27 then expands each pseudo-halfpixel back into two subpixels, and these are averaged 28 to form the final image which is printed on a Raster Output Scanner 29.

While the invention has been described with reference to a specific embodiment, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the true spirit and scope of the invention. In addition, many modifications may be made without departing from the essential teachings of the invention.