Method and system using variable line width adjustment with reduced scan buffering that is compatible with antialiasing

[0002] 1. Field of Invention

[0003] The invention relates to an apparatus and a method for controlling lines rendered by a printer or displayed on a monitor that is compatible with antialiasing image data and requires a minimal amount of scanned image data buffering.

[0004] 2. Description of Related Art

[0005] Today's marking devices typically do not match the idealized printer model used in the construction of images. For example, instead of crisp, square, non-overlapping pixels, as shown in FIG. 1, a real device may draw large, circular spots with gradual boundaries that overlap to fully cover the pixel areas, as shown in FIG. 2.

[0006] When lines and characters are drawn using these real spots, they may be thicker or thinner than their intended ideal. The actual behavior of the marker can be complex, for example, making thin lines too thick and thick lines too thin. A rendering process can be employed to adjust the width of lines and characters to compensate for the marker. One approach is to adjust the width of lines when they are rasterized, but is not always effective because the line may not always remain in isolation. For example, one might construct a color sweep by drawing a series of lines of varying color one next to another. Accordingly, adjusting the width of each line in isolation might only serve to destroy the sweep. An alternative approach is to analyze the completely rasterized image to detect lines and to alter their widths. However, to detect and alter lines up to width N pixels in a conventional manner, where the alteration is a function of line width, requires a window of 2N+3 pixels square. Thus, 2N+3 scan lines must be buffered. However, this memory is expensive if the width N is large.

[0007] The exemplary embodiments of the invention provide a method and system for compensating for the line width growth or shrinkage in an image rendering system that supports high-addressability. The amount of width adjustment can be a function of the line width. The method is applied after rendering, to the sub-pixel, bit patterns and is compatible with antialiasing and other sub-pixel rendering techniques such as half-bitting. The method and system also require less scan buffering for marker line width compensation than conventional methods. More specifically, the method and system require N+3 scans to detect and adjust widths up to N pixels instead of the 2N+3 necessary conventionally.

[0008] This, and other features and advantages of this invention are described in or are apparent from the following detailed description of the system and methods according to this invention.

[0009] The benefits of the present invention will be readily appreciated and understood from consideration of the following detailed description of the exemplary embodiment of this invention, when taken with the accompanying drawings, in which same numbered elements are identical and:

[0010] FIG. 1 illustrates a pattern of ideal of square, non-overlapping pixels;

[0011] FIG. 2 illustrates a pattern of realistic large, circular spots with gradual boundaries that overlap to fully cover the pixel areas;

[0012] FIG. 3 illustrates a pixel sub-divided into eight sub-pixels;

[0013] FIG. 4 is a flow chart illustrating a method of line width adjustment in accordance with the exemplary embodiment;

[0014] FIG. 5 illustrates a vertical sequence of pixels;

[0015] FIG. 6 illustrates a buffer used in conjunction with the exemplary embodiment of the invention;

[0016] FIG. 7 illustrates a diagonal sequence of pixels;

[0017] FIG. 8 illustrates a look up table architecture and corresponding table index used in conjunction with the exemplary embodiment; and

[0018] FIG. 9 illustrates a sequence of pixels stored in a buffer used in conjunction with the exemplary embodiment.

[0019] Modern rendering technology of ten allows high addressability in at least one direction (typically the fast-scan direction for laser printers). This can offer several advantages. It gives more freedom for the design of better halftone dots. It can be used for the antialiasing of object edges. Additionally, it can be used for finer control over width compensation. There is an issue, however, in how these various purposes interact. More specifically, the present invention is particularly directed to a method of performing width adjustment that is compatible with performing antialiasing.

[0020] As a result, it is preferred that the system for variable line width adjustment according to the exemplary embodiments is preferably located in an image path after halftoning and antialiased rendering is performed. The method of performing variable line width adjustment may, and is preferably, performed in an image rendering system in conjunction with halftoning, antialiased rendering and color image correction. The method and system act on raster image data. This raster image data is ideal image data. The operation of the system and performance of the method allow the ideal image data be rendered effectively using an image rendering device, which is inherently non-ideal.

[0021] Thus, line width detection and adjustment are applied to the high-addressability specification of an image. If, for example, processing begins with 400×400 spots per inch (spi) contone image data and halftoning is performed with antialisaed render to 8×addressability, then a 400×3200 spi binary image is provided. It is this 400×3200 ppi image data upon which the line width detection and adjustment is performed. The high-addressibility sub-pixels can be accessed in groups of eight, where each group corresponds to a single pixel of the original 400×400 spi image data.

[0022] An line width adjustment method performed in accordance with the exemplary embodiment processes the image in this way. Thus, the method processes groups of sub-pixels where each group represents a non-overlapping square region of the image. For example, as shown in FIG. 3, a pixel 300 is divided into eight sub-pixels 310.

[0023] The reduction of the buffer requirements from 2N+3 to only N+3 is accomplished by examining each pixel more than once. The compatibility with antialiasing implies that the adjustments can extend beyond the edge pixel either lengthening or shortening. Thus, pixels on each side of a line can be altered; such is the nature of overflow. Each pixel is examined eight times for possible changes. Throughout the explanation of the exemplary embodiments, it is assumed that the line width adjustments do not exceed one pixel at each side. Thus, line widths change at most by a width of two pixels. The methods for performing line width adjustment performed in accordance with the exemplary embodiments can be generalized to greater changes. However, handling line width changes in excess of two pixel widths requires buffering additional scan lines and performing additional examination of image pixels.

[0024] The methods performed in accordance with the exemplary embodiments examine the image data to identify runs of black or white, i.e., non-gray, pixels. In a black or white pixel, the sub-pixel values all have the same value, i.e., all black or all white. Short runs may be line cross-sections; thus, a short run's run length would be the line width.

[0025] As shown in FIG. 4, the method for line width adjustment begins in step S400 and control proceeds to step S410. In step S410, high-addressability image data is input into a pixel buffer by, for example, scanning an image, and control proceeds to step S420. In step S420, a leading edge of a horizontal or diagonal line is identified within the high-addressability image data.

[0026] Performance of step S420 differs depending on whether a horizontal line or a diagonal line is being analyzed. For a horizontal line, a vertical sequence of pixels is examined as illustrated in FIG. 5. This can be performed using a table look up, indexed by bits indicated whether the pixels in the vertical sequence are black, white, or gray. This may also be performed using logical operations.

[0027] For example, a test may be performed to determine if a pixel at position p in scan s is the leading edge of a horizontal line. In such a test, a pixel at (p, s+1) must be non-gray. The value of the pixel at (p, s) must not match the value of the pixel at (p, s+1). The values of the pixels at (p, s−i) are examined for i starting at one and incrementing while the values are the complement of the pixel at (p,s+1). In other words, if the pixel at (p, s+1) is white, then the number of black pixels trailing the pixel at (p,s) are counted. The value of i is incremented until the color changes or the buffered pixels are all analyzed. The final value of i becomes the length of the run. This run length indicates the thickness of the line and is used to determine the amount of adjustment.

[0028] To make optimal use of the pixel buffer, the scan at s+1 should be the line most recently entered into the buffer as shown in FIG. 6.

[0029] It should be recognized that it may be beneficial, in step S420, to check whether either the pixel at (p−1, s) or (p+1, s) differs in value from that at (p, s+1) to help determine whether the pixels correspond to an edge of a horizontal line. If the pixels fail the test, i.e., either the pixel at (p−1, s) or (p+1, s) is the same as the value of pixel (p, s+1), further processing on the run can be stopped because the pixels do not represent an edge of a horizontal line.

[0030] Another possible refinement is a test for noise in the form of single light pixels (run length zero) on a white background or single dark pixels on a black background. If the pixel run fails the test, further processing on the pixel run is terminated. An isolated noise spot (e.g., a black spot on a white background) would be expected to have a short run length (e.g. i=1) in the vertical direction, and equally limited extent horizontally (e.g., pixels at (p+1, s) and at (p−1, s) are nonblack). It should be appreciated that such noise will only appear if there is a source of noise in the system such as the scanning of a degraded hardcopy image. For ideal synthetic images generated by computer, no such noise will be present.

[0031] Run length and the color of the pixel run are used to determine the amount of adjustment. The color of the line is the complement of the color of the background found at position (p, s+1).

[0032] Step S420 is similar for diagonal lines. The search for diagonal lines is similar, but instead of examining a vertical sequence of pixels, a diagonal sequence of pixels is examined as shown in FIG. 7. Therefore, within the diagonal pixel sequence, p is incremented or decremented as s is incremented. The pixel immediately adjacent to the leading edge must have the background non-gray value, and not just the pixel along the diagonal. For example, if a run in the direction where p is incremented while s is decremented is being tested, then the pixel at location (p−1, s+1) must be a non-gray pixel. However, the pixel at either (p, s+1) or (p−1, s) must have the same non-gray background value as the pixel at (p−1, s+1).

[0033] If further tests are desired to ensure that the pixel really belongs to a line edge, an additional test can be applied in which grayscale values of surrounding pixels are analyzed. For example, if the pixels at (p, s+1), (p, s−1) and (p−1, s−1) are all the background color or if the pixels at (p−1, s), (p+1, s) and (p+1, s+1) are all the background color, then further processing of the run can be terminated and the run discarded. The idea here is that there should not be pixels having background grayscale values on both sides of an edge pixel.

[0034] Determining the lengths of runs in the other diagonal direction where p decrements as s decrements is analogous to the above explanation.

[0035] Note that run lengths for diagonals actually differ from horizontal or vertical lengths by a factor of the square root of 2. Therefore, one may wish to re-scale diagonal run length or, even better, use a different adjustment table for horizontal runs than for diagonal runs and separate the processing into two stages.

[0036] The method for performing line width adjustment continues to step S430, as shown in FIG. 4. Step S430 is the second stage of processing, in which the leading edge adjustment is calculated. Control then proceeds to step S440. Step S430 can be performed using a look up table using the run length and color as an index. Therefore, as illustrated in FIG. 8, the color and run length are listed in table index 810. The look up table 820 includes a replacement pattern section 830 and an overflow pattern section 840. The color of the line is taken to be the compliment of a background color in the image data. This table 820 provides the compensation for the marking engine's behavior. By referencing the table 820 based on the index 810, the table 820 provides information indicating how much to shrink or expand the line thickness.

[0037] Note that a current bit pattern for the edge pixel can also be included as part of the index 810 for the look up table 820. The table 820 can provide a new bit pattern including a replacement pattern and an overflow pattern corresponding to the current bit pattern. Different tables may also be employed based on a run direction so as to select a pattern of adjustment accordingly. Altering pattern selection based on run direction allows antialiased edges to grow or shrink in the proper direction as well as providing tailored half-bitting adjustment solutions.

[0038] When antialiasing is employed, the edge position can be specified to sub-pixel accuracy within the limits of high addressability. An edge may be anywhere within a pixel according to the sub-pixel specification. Because an edge can be located near a pixel boundary, a width adjustment can move the edge across the boundary and into a neighboring pixel. Therefore, the line width adjustment table should not only provide the replacement pattern for the current pixel, but also the pattern for a neighbor into which the adjustment overflows, if this should happen. Accordingly, the look up table 820 includes both the replacement pattern for the current pixel and an overflow pattern 840 for the neighboring pixel affected by overflow.

[0039] Processing is performed based on the assumption that the overflow is into a pixel with a grayscale value that is the background color. While this is typically the case, it is not necessarily true. Therefore, it should be appreciated that processing based on this assumption occasionally introduces small errors in the result.

[0040] For processing a leading edge of a horizontal line, an overflow for the pixel at (p,s) will affect the pixel at (p, s+1) if the edge expands and will affect (p, s−1) if the edge shrinks.

[0041] For processing edges of diagonal lines, the proper overflow is less clear. It is preferable to limit the effects of overflow to potentially occur in the two immediately adjacent pixels nearest the direction of growth or shrinkage. For example, if the run direction is chosen such that p increases as s decreases, then an expanding edge at (p, s) overflows into the two pixels near the edge at (p−1, s) and (p, s+1). If the edge shrinks, then the pixels at (p+1, s) and (p, s−1) are affected.

[0042] Whether a line edge grows or shrinks may be implied by the pixel run color. Alternatively, it may be a function of both pixel run color and pixel run width, in which case, line width adjustment can be provided by referencing the adjustment table 820.

[0043] Once the leading edge adjustments for each of the three directions (i.e., horizontal and two diagonals) have been calculated, their values must be reconciled with one another. This is because only a single final adjustment can be made to the positioning of the leading line edge. Therefore, the adjustment with the greatest modification to the leading edge is chosen from among the adjustments for each of the three directions. To facilitate this, replacement pixel section 830 of the adjustment table 820 can contain an amount of adjustment as well as a resulting adjusted pixel pattern. The overflow pattern 830 can also provide the amount of adjustment of the number of sub-pixels darkened for the overflow pixels.

[0044] The effects of overflows can affect the pixels near the pixel being considered, e.g., the two pixels above, below, right, or left of the current pixel. Therefore, if a black line is shrinking or a white line is expanding, the pattern with the fewest black sub-pixels should be selected. Similarly, if a white line is shrinking or a black line is expanding, the pattern with the greatest number of black sub-pixels should be selected.

[0045] In selecting the pattern, one can include the current pixel's original value as well as the values suggested by the possible overflow of the current pixel's width. For example, if a black leading edge at position (p, s) should be expanded, then the test for an edge of a horizontal line can suggest an overflow into the pixel at (p, s+1). One diagonal test can show possible overflow into the pixels at (p, s+1) and (p−1, s). The other diagonal test can show possible overflow into pixels at (p, s+1) and (p+1, s). Note that for the pixel at (p, s+1) a resulting pattern must be selected from among its original pattern and three possible overflow patterns. Since black is expanding into white, the pattern with the greatest number of black sub-pixels is selected.

[0046] The resolved pixel values for the current position (p, s) and overflow positions (p, s−1), (p−1, s) and (p, s+1) can be immediately revised in the pixel buffer. However, the revision of the pixel at (p+1, s) should be delayed to include changes from processing of the next two pixels. When the pixel at (p+1, s) is made to be the current pixel and calculation of possible adjustments is performed, any adjustments determined as necessary should take precedence over overflow adjustments. When processing returns to the next pixel so that (p+2, s) is the current position, then new overflow patterns for the left side of the new current pixel may be encountered. These new patters must be reconciled with the possible overflow patterns from the right side of the original pixel.

[0047] Another way to perceive processing is that, when (p, s) is the location of the current pixel, and the value of the pixel at (p−1, s) is to be reconciled, one must reconcile its current value with the left side overflow from the pixel at (p, s) and also with the right side overflow from pixel (p−2, s).

[0048] Along with computing leading edge adjustments, one must also calculate trailing edge adjustments. Therefore, in step S440, a trailing edge of the horizontal or diagonal line is identified within the high-addressability image data.

[0049] As in step S420, performance of step S440 differs depending on whether a horizontal line or a diagonal line is being analyzed. These processes are analogous to the leading edge cases, but there is a change of orientation. As illustrated in FIG. 8, the pixels on the next to last scan line within the buffer are considered for optimal use of the buffer.

[0050] It is this shift in orientation between leading and trailing edges that causes the reduction the amount of buffering required. During processing, the pixel of interest at the lower edge of the window is considered and analyzed for leading edges. Subsequently, the upper edge of the window is considered and analyzed for trailing edges.

[0051] In conventional processing, each pixel is considered only once for adjustment. That means that in that single test, one must simultaneously decide on adjustments due to its presence on a line above, or below, right or left. One must be able to examine the neighborhood in all directions about the pixel in question. To do this, one must hold in memory the pixels both above an below the pixel in question. If one is to recognize pixels on the edge of a line of width N then one needs a scan line for the pixel, N scan lines for the line and one more scan line to confirm that the line has ended. Thus, N+1 scans are needed above the scan line of the pixel and also N+1 scans are needed below it. Conventional processing thus requires the buffering of 2N+3 scan lines.

[0052] To the contrary, in the present invention one does not consider the pixel only once. Each pixel is considered twice, once shortly after it has entered the buffer, and again shortly before it is about to leave the buffer. When the scan enters the buffer there will be a buffer's worth of scan lines above it, but none below. Thus, when the scan enters the buffer, one has the information to determine if the pixel is on the edge of a line located above it, but not if it is on the edge of a line below it. However, just before a scan leaves the buffer, there will be a buffer's worth of scan below it, while none above. At that point, one can determine if a line is located below it. In both cases, the actual number of scans needed for the test is N+3. Therefore, by processing the pixel in two stages, the amount of buffering may be reduced from 2N+3 to N+3.

[0053] Because entire scan lines are present, the information about the behavior to the right or left of a pixel in question is always present. Accordingly, the check for vertical lines can be included in either of the two test stages. However, it is preferable to include the test for vertical lines as part of the second test stage so as to minimize the modification of the image prior to the second test stage. The tests for edges of horizontal and diagonal lines are the same as for leading edges except scan indices are incremented instead of decremented when determining runs.

[0054] The method for performing line width adjustment continues to step S450, as shown in FIG. 4. Step S450 is the second stage of processing, in which the trailing edge adjustment is calculated. Control then proceeds to step S460, in which a determination is made whether there is additional image data to be processed. If so, control returns to step S410. If not control proceeds to step S470, in which the method ends.

[0055] While this invention has been described in conjunction with the specific embodiments outlined above, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the preferred embodiments of the invention, as set forth above, are intended to be illustrative, not limiting. Various changes may be made without departing from the spirit and scope of the invention.

[0056] For example, although the benefits of the exemplary embodiment have been explained in conjunction with the use of a window of pixel values of width N+3, it should be appreciated that using a window of pixel values of width 2N+3 to detect lines up to width N allows the simultaneous testing for both leading and trailing edges. However, such an increase in window size requires additional scan-line buffering thereby increasing the memory costs associated with practicing the invention.

[0057] Additionally, the trailing edge processing can also include an adjustment for vertical lines (both leading and trailing edges). The tests for edges of vertical lines are analogous to those for horizontal lines with an exchange of the roles of scan and pixel indices. However, in addition to potentially adjusting a current pixel, implementation of a test for edges of vertical lines can also result in possible overflow adjustments to the pixels left and right of the current pixel. These adjustments must be reconciled with those arising from diagonal lines, for example, by selecting the adjustment that is greatest from among the possible overflow adjustments.

[0058] Moreover, specific implementations of the line width adjustment method can provide further refinement. For example, note that when a trailing edge of a horizontal line shrinks and overflows, the original pixel can change from gray to non-gray. This can trigger detection of the edge again when the next scan line is processed. One way of avoiding this double processing is to not replace the current pixel with a full non-gray value for this case. Instead, using a pattern that has one complimentary sub-pixel value is preferable. Thus, the pattern should be nearly black or white and should produce the desired imaging without triggering double edge processing of the edge.