Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-09-14
2002-08-20
Rogers, Scott (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003260, C358S525000, C358S502000
Reexamination Certificate
active
06437879
ABSTRACT:
This invention relates to the interpolation of greyscale levels and—in the most important example—to the interpolation of greyscale levels in dot-based printing techniques such as ink jet printing.
It is well known that in a printing technology which is capable of producing only a single dot size, greyscale images can be created by the appropriate spatial distribution of fixed size dots. In one well known technique, pixels are organised into square arrays with each pixel in the array being assigned a different threshold value. Typically, an eight by eight square array of pixels will provide sixty-four threshold values. This square array of sixty-four threshold values is tessellated across the whole picture. At each pixel, the local grey level is compared to the threshold value assigned to that element in the pixel array and a dot is created only if the local grey level is darker than the threshold value. In the case of colour printing, this operation is of course conducted separately for each of three colours and, usually, black.
This dither technique is simple to implement and fast to run. However, great difficulties are encountered in defining the threshold array in such a way as to produce acceptable results. It is found that boundaries between areas of constant grey level are accentuated by the eye's sensitivity to the change in pattern between the two areas. As will be recognised, the threshold approach defines for each grey level a characteristic pattern and shifts between certain grey levels—which may be adjacent—can result in pattern changes which are distracting to the eye.
Other forms of spatial distribution, such as error diffusion, have been developed in an attempt to overcome these difficulties. The basic approach of error diffusion techniques is that the “error” between the “actual” and “printed” grey levels at one pixel is taken into consideration in the thresholding decisions of neighbouring pixels. Even with the simplification that errors are only carried forward in time, error diffusion techniques are complex to implement. They tend—moreover—to produce characteristically noisy grey levels.
It is an object of one form of the present invention to provide an improved method of interpolating a greyscale which enables the reduction of visually disturbing artifacts without complex processing.
The present invention has the further object of providing a solution to the problems with existing threshold arrays which is fundamental in character and which does not rely simply on empirical investigation.
Accordingly, the present invention consists in one aspect in a method of interpolating a greyscale between pixel levels in a regular array of pixels, where threshold values are associated with pixels and at each pixel a selection is made between said pixel levels in accordance with a comparison between the desired grey level and the threshold value associated with that pixel, charactersed in that rows of threshold values are defined, each row having the same repeating sequence of values with the i'th value in the sequence of the form (i*p)%S where p and S are integers and the notation a%b denotes the remainder after integer division of a by b, there being a constant offset of d pixels in the phase of the repeating sequence from one row to the next.
It is recognised in the present invention that the problem of patterning can be identified with variations in horizontal and vertical spatial frequencies between greyscale levels in the two-dimensional prior art threshold arrays. The eye is extremely sensitive to the contrast between certain spatial frequencies; changes from vertical stripes to horizontal stripes are, for example, particular noticeable, as are changes from stripes to a check. The novel approach of the present invention, by first assigning the threshold values to a linear array or row, and then creating subsequent rows by repeating the sequence with a constant offset, forces the spatial frequency content of all greyscale levels towards diagonals. The phase of the repeating sequence, determined for example by reference to the location of a specified threshold value (which might conveniently be zero), thus increases by a constant number of pixels from one row to the next succeeding row. With the spatial frequency content of all greyscales patterns being similar, the boundaries between levels become much less noticeable. It is also observed that, because of the eye's reduced sensitivity to diagonal lines, as opposed to horizontal or vertical lines, the intrinsic visibility of the patterns is reduced.
The repeating sequence of threshold values in each row will contain all values of the greyscale, say S values. In comparison with the prior art approach of square threshold arrays of side S and “area” S ,the approach of the invention results in “unit squares” of side S and area S2. Rather surprisingly, this increase in size of the “unit square” has no material disadvantages in the quality of the image. Moreover, this observation remains true for larger values of S.
In this form of the invention, the i'th value of the repeating sequence of threshold values is defined as (i*p) % S, where p is a non-zero integer. The notation a%b denotes the remainder after integer division of a by b. By way of example, the function: (i*3) % 7 will produce the series:
36251403625
Preferably, p and S are mutually prime.
This approach elegantly assigns the threshold values to the row in an even manner. It further enables control over the difference in threshold values between adjacent pixels of the row. By increasing this difference, the spatial resolution of the image is increased, in the sense that the greater is the difference in threshold between adjacent levels, the more likely is a change in input grey level to result in a change in pixel level. Thus p is preferably chosen to be close to S/2.
The constant offset of pixels in the phase of the repeating sequence from one row to the next succeeding row may be defined as d and, preferably d is not a factor of S.
The approach of defining repeating sequences in rows and then repeating rows with a constant offset can be considered also from a more symmetric viewpoint. Take a general array i,j—which includes the special case where i denotes the location in the row and j the number of the row—and define the threshold value at each point of the array as T
ij
. This threshold value can then be defined as:
T
ij
=(
i*p−j*q
)%
S
where the notation %S denotes as before the remainder after integer division by S. It can be seen that this approach produces a constant offset d between the j'th and (j+1)'th rows of d where:
q
=(
S−dp
)%
S
which can be stated more simply as
q
=(−
dp
)%
S
Looking at the problem of spatial resolution in both directions, there is a preference for:
p≈S/2 or q =S/2
In the prior art, the various techniques of dither and the like have been viewed as ways to produce a greyscale from printing technologies which are fundamentally binary, for example ink jet print heads which in any channel either produce an ink drop or do not. Many other printing technologies are intrinsically capable of handling greyscate and accommodate pixel values of zero to N. this being the desired greyscale range. Efforts are being made, with some success, to provide this intrinsic greyscale capability in ink jet and other, once, binary technologies by providing for N different sizes of ink drop and thus N pixel values. In a typical arrangement, a minimum value for N will be 64, which is generally regarded as being the minimum number of levels which the eye can perceive without there being obvious contrast between levels. Providing this number of distinct drop sizes in a reproducible manner, is not straightforward and in many cases, especially drop-on-demand ink jet printing, may force undesirable design compromises in other areas. For example, the smallest drop may be so small as to cause errors in placement due to aerodynamic effects.
Accordingly, the present invention, ha
Marshall Gerstein & Borun
Rogers Scott
Xaar Technology Limited
LandOfFree
Interpolation of greyscale levels does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interpolation of greyscale levels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interpolation of greyscale levels will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960639