@node Dithering, Weaving, Appendices, Appendices
@appendix Dithering
@cindex dithering
The dithering code in @file{print-dither.c} attempts to reproduce
various shades of gray (or all colors) from only a few different inks
(black, cyan, magenta, yellow, and sometimes light cyan and light
magenta). The dots can't vary in darkness or size (except for certain
special printers), and so we need to lay down a certain fraction of dots
to represent each distinct level.
This sounds straightforward; in practice, it isn't. Completely random
distribution of dots (simple probabilistic dithering) would create
grainy clumps and light spots. The smoothest pattern results from an
equidistant spacing of dots. Approximating this requires sophisticated
algorithms. We have two dithering algorithms, an ordered dither
algorithm that uses a grid (matrix) to decide whether to print, and a
modified Floyd-Steinberg error diffusion algorithm that uses a grid in a
slightly different way.
We currently have three dithering functions:
@enumerate
@item
@code{dither_fastblack} produces pure black or white from a pre-dithered
input. This is used for two purposes: for printing pure black and white
very quickly (e. g. text), and for printing pre-screened monochrome
output that was rasterized externally.
@item
@code{dither_black} produces black from grayscale input. The new
dither_black can produce either a single or multiple levels of black,
for printers supporting variable dot size.
@item
@code{dither_cmyk} produces 3, 4, 5, 6, or 7 color output (CMY, CMYK,
CcMmYK, CcMmYy, CcMmYyK, or any variants). The new routine can handle
single or multiple levels of each color.
@end enumerate
There is a choice of dithering algorithms. Four of them are based on a
basic error diffusion, with a few tweaks of my own. The other one is
`ordered'. However, they all share the basic operation in common.
First, the algorithm picks what kind of dot (if there are multiple dot
sizes and/or tones that may be picked) is the candidate to be printed.
This decision is made based on the darkness at the point being dithered.
Then, it decides whether the dot will be printed at all. What this is
based on depends upon which algorithm family we use. This is all
described in more detail below.
Ordered dithering works by comparing the value at a given point with the
value of a tiled matrix. If the value at the point is greater than the
value in the matrix, the dot is printed. The matrix should consist of a
set of evenly spaced points between 0 and the upper limit. The choice
of matrix is very important for print quality. A good dither matrix
will emphasize high frequency components, which distributes dots evenly
with a minimum of clumping. The matrices used here are all simple
matrices that are expanded recursively to create larger matrices with
the same kind of even point distribution. This is described below.
Note that it is important to use different matrices for the two
sub-operations, because otherwise the choice about whether to print and
the choice of dot size will be correlated. The usual result is that the
print is either too dark or too light, but there can be other problems.
Ordered dithering works quite well on single dot size, four color
printers. It has not been well tested on four color, variable dot size
printers. It should be avoided on six color printers.
Error diffusion works by taking the output error at a given pixel and
``diffusing'' it into surrounding pixels. Output error is the
difference between the amount of ink output and the input level at each
pixel. For simple printers, with one or four ink colors and only one
dot size, the amount of ink output is either 65536 (i. e. full output)
or 0 (no output). The difference between this and the input level is
the error. Normal error diffusion adds part of this error to the
adjoining pixels in the next column and the next row (the algorithm
simply scans each row in turn, never backing up). The error adds up
until it reaches a threshold (half of the full output level, or 32768),
at which point a dot is output, the output is subtracted from the
current value, and the (now negative) error is diffused similarly.
Error diffusion works quite well in general, but it tends to generate
artifacts which usually appear as worm-like lines or areas of anomalous
density. I have devised some ways, as described below, of ameliorating
these artifacts.
There are two sub-classes of error diffusion that we use here, `random'
and `hybrid'. One of the techniques that we use to ameliorate the
artifacts is to use a fuzzy threshold rather than the hard threshold of
half of the output level. Random error diffusion uses a pseudo-random
number to perturb the threshold, while hybrid error diffusion uses a
matrix. Hybrid error diffusion worked very poorly in 3.1.3, and I
couldn't figure out why until I found a bug. It now works very well.
There is one additional variant (on both sub-classes), called `adaptive
hybrid' and `adaptive random'. The adaptive variant takes advantage of
the fact that the patterns that ordered dithering create are less
visible at very low densities, while the artifacts created by error
diffusion are more objectionable at low densities. At low densities,
therefore, it uses ordered dithering; at higher densities it uses error
diffusion.
Handling multiple output levels makes life a bit more complicated. In
principle, it shouldn't be much harder: simply figure out what the ratio
between the available output levels is and have multiple thresholds. In
practice, getting these right involves a lot of trial and error. The
other thing that's important is to maximize the number of dots that have
some ink. This will reduce the amount of speckling. More on this
later.
The next question: how do we handle black when printing in color? Black
ink is much darker than colored inks. It's possible to produce black by
adding some mixture of cyan, magenta, and yellow---in principle. In
practice, the black really isn't very black, and different inks and
different papers will produce different color casts. However, by using
CMY to produce gray, we can output a lot more dots! This makes for a much
smoother image. What's more, one cyan, one magenta, and one yellow dot
produce less darkness than one black dot, so we're outputting that many
more dots. Better yet, with 6 or 7 color printers, we have to output even
more light ink dots. So Epson Stylus Photo printers can produce really
smooth grays---if we do everything right. The right idea is to use
CMY at lower black levels, and gradually mix in black as the overall
amount of ink increases, so the black dots don't really become visible
within the ink mass.
Variable dot sizes are handled by dividing the range between 0 and
65536 into segments. Each segment can either represent a range in
which all of one kind of ink (color and/or dot size) is used, with
varying amounts of ink, or a transition region between inks, in which
equal numbers of dots are printed but the amount of each ink will be
adjusted throughout the range. Each range is represented by four
numbers:
@enumerate
@item
bottom of the range
@item
top of the range
@item
value of the lighter ink
@item
value of the darker ink
@end enumerate
In addition, the bit patterns and which type of ink are also
represented, but they don't affect the actual algorithm.
As mentioned above, the basic algorithm is the same whether we use
ordered dither or error diffusion. We perform the following steps on
each color of each pixel:
@enumerate
@item
Compute the value of the particular color we're printing. This isn't
usually the pure CMY value; it's adjusted to improve saturation and to
limit the use of black in light toned regions (to avoid speckling).
@item
Find the range containing this value.
@item
Compute where this value lies within the range. We scale the endpoints
between 0 and 65536 for this purpose. So for example, if the bottom of
the range is 10,000 and the top of the range is 20,000, and the value is
12,500, we're 1/4 of the way between the bottom and the top of the
range, so our scale point is 16384.
@item
Compute the ``virtual value''. The virtual value is the distance between
the value of the lighter and the value of the darker ink. So if the
value of the light ink is 32768 and the dark ink is 65536, we compute a
virtual value scaled appropriately between these two values, which is
40960 in this case.
@item
Using either error diffusion or ordered dither, the standard threshold
is 1/2 of the value (20480 in this case). Using ordered dither, we want
to compute a value between 0 and 40960 that we will compare the input
value against to decide whether to print. Using pure error diffusion,
we would compare the accumulated error against 20480 to decide whether
to print. In practice, we use the same matrix method to decide whether
to print. The correct amount of ink will be printed this way, but we
minimize the squiggly lines characteristic of error diffusion by
dithering the threshold in this fashion. A future enhancement will
allow us to control the amount of dithering applied to the threshold.
@end enumerate
The matrices were generated by Thomas Tonino
@email{<ttonino@@bio.vu.nl>} with an algorithm of his devising. The
algorithm is designed to maximize the spacing between dots at any given
density by searching the matrix for holes and placing a dot in the
largest available hole. It requires careful selection of initial points
to achieve good results, and is very time consuming. For best results,
a different matrix must be used for modes with 2:1 aspect ratio
(e.g. 1440x720) than for 1:1 (e. g. 720x720). It is essential with any
of these matrices that every point be used. Skipping points generates
low-frequency noise.
It's essential to use different matrices for deciding whether to print
and for deciding what color (dark or light) to print. This should be
obvious; the decision about whether to print at all should be as
independent as possible from the decision about what color to print,
because any bias will result in excess light or dark ink being
printed, shifting the tonal balance. We actually use the same
matrices, but we shift them vertically and horizontally. Assuming
that the matrices are not self-correlated, this will yield good
results.
The ranges are computed from a list of ink values (between 0 and 1 for
each possible combination of dot size and ink tone, where the value
represents the darkness of the ink) and the desired maximum density of
the ink. This is done in dither_set_ranges, and needs more
documentation.
I stated earlier that I've tweaked the basic error diffusion algorithm.
Here's what I've done to improve it:
@enumerate
@item
We use a variable threshold to decide when to print, as discussed above.
This does two things for us: it reduces the slightly squiggly diagonal
lines that are the mark of error diffusion; and it allows us to lay down
some ink even in very light areas near the edge of the image. The
squiggly lines that error diffusion algorithms tend to generate are
caused by the gradual accumulation of error. This error is partially
added horizontally and partially vertically. The horizontal
accumulation results in a dot eventually being printed. The vertical
accumulation results in a dot getting laid down in roughly the same
horizontal position in the next row. The diagonal squigglies result
from the error being added to pixels one forward and one below the
current pixel; these lines slope from the top right to the bottom left
of the image.
Error diffusion also results in pale areas being completely white near
the top left of the image (the origin of the printing coordinates).
This is because enough error has to accumulate for anything at all to
get printed. In very pale areas it takes quite a long time to build up
anything printable at all; this results in the bare spots.
Randomizing the threshold somewhat breaks up the diagonals to some
degree by randomizing the exact location that the accumulated output
crosses the threshold. It reduces the false white areas by allowing
some dots to be printed even when the accumulated output level is very
low. It doesn't result in excess ink because the full output level is
still subtracted and diffused.
Excessive randomization leads to blobs at high densities. Therefore, as
the density increases, the degree of randomization decreases.
@item
Alternating scan direction between rows (first row is scanned left to
right, second is scanned right to left, and so on). This also helps
break up white areas, and it also seems to break up squigglies a bit.
Furthermore, it eliminates directional biases in the horizontal
direction. This isn't necessary for ordered dither, but it doesn't hurt
either.
@item
Diffusing the error into more pixels. Instead of diffusing the entire
error into @math{(X+1, Y)} and @math{(X, Y+1)}, we diffuse it into
@math{(X+1, Y)}, @math{(X+K, Y+1)}, @math{(X, Y+1)}, @math{(X-K, Y+1)}
where @math{K} depends upon the output level (it never exceeds about 10
dots, and is greater at higher output levels). This really reduces
squigglies and graininess. The amount of this spread can be controlled;
for line art, it should be less than for photographs (of course, line
art doesn't usually contain much light color, but the @strong{error}
value can be small in places!) In addition to requiring more
computation, a wide ink spread results in patterning at high dot
densities (note that the dot density can be high even in fairly pale
regions if multiple dot sizes are in use).
@item
Don't lay down any colored ink if we're laying down black ink. There's
no point; the colored ink won't show. We still pretend that we did for
purposes of error diffusion (otherwise excessive error will build up,
and will take a long time to clear, resulting in heavy bleeding of ink
into surrounding areas, which is very ugly indeed), but we don't bother
wasting the ink. How well this will do with variable dot size remains
to be seen.
@item
Oversampling. This is how to print 1440x720 with Epson Stylus printers.
Printing full density at 1440x720 will result in excess ink being laid
down. The trick is to print only every other dot. We still compute the
error as though we printed every dot. It turns out that randomizing
which dots are printed results in very speckled output. This can be
taken too far; oversampling at 1440x1440 or 1440x2880 virtual resolution
results in other problems. However, at present 1440x1440 (which is more
accurately called "1440x720 enhanced", as the Epson printers cannot
print 1440 rows per inch) does quite well, although it's slow.
@end enumerate
What about multiple output levels? For 6 and 7 color printers, simply
using different threshold levels has a problem: the pale inks have trouble
being seen when a lot of darker ink is being printed. So rather than
just using the output level of the particular color to decide which ink
to print, we look at the total density (sum of all output levels).
If the density's high enough, we prefer to use the dark ink. Speckling
is less visible when there's a lot of ink, anyway. I haven't yet figured
out what to do for multiple levels of one color.
You'll note that I haven't quoted a single source on color or printing
theory. I simply did all of this empirically.
There are various other tricks to reduce speckling. One that I've seen
is to reduce the amount of ink printed in regions where one color
(particularly cyan, which is perceived as the darkest) is very pale.
This does reduce speckling all right, but it also results in strange
tonal curves and weird (to my eye) colors.
Before any dither routine is used, @code{init_dither()} must be called.
This takes three arguments: the input width (number of pixels in the
input), the output width (number of pixels in the output), and a
@code{vars_t} structure containing the parameters for the print job.
@code{init_dither()} returns a pointer to an opaque object representing
the dither. This object is passed as the first argument to all of the
dither-related routines.
After a page is fully dithered, @code{free_dither()} must be called to
free the dither object and perform any cleanup. In the future, this may
do more (such as flush output). This arrangement permits using these
routines with programs that create multiple output pages, such as
GhostScript.
The dithering routines themselves have a number of control knobs that
control internal aspects of the dithering process. These knobs are
accessible via a number of functions that can be called after
@code{init_dither()}.
@itemize @bullet
@item
@code{dither_set_density()} takes a double between 0 and 1 representing
the desired ink density for printing solid colors. This is used in a
number of places in the dithering routine to make decisions.
@item
@code{dither_set_black_density()} takes a double between 0 and 1
representing the desired ink density for printing black ink in color
printing. This is used to balance black against color ink. By default,
this is equal to the density set by @code{dither_set_density()}. By
setting it higher, more black ink will be printed. For example, if the
base density is .4 and the black density is .8, twice as much black ink
will be printed as would otherwise be called for.
This is not used when printing in monochrome. When printing monochrome,
the base density (@code{dither_set_density}) should be adjusted
appropriately.
@item
@code{dither_set_ink_budget()} takes an unsigned number representing the
most ink that may be deposited at a given point. This number is
arbitrary; the limit is computed by summing the size of each ink dot,
which is supplied as a parameter in @code{dither_set_@var{X}_ranges}.
By default, there is no limit.
@item
@code{dither_set_black_lower()} takes a double that should be between 0
and 1 that represents the lowest density level at which black ink will
start to mix in with colored ink to generate grays. The lower this is,
the less density is required to use black ink. Setting this too low
will result in speckling from black dots, particularly on 6 and 7 color
printers. Setting this too high will make it hard to get satisfactory
black or may result in sharp transition between blended colors and
black. Default: 0.0468.
It is important to note that since the density scale is never linear
(and since this value is adjusted via other things happening during the
dithering process) that this does not mean that 95% gray will use any
black ink. At this setting, there will be no black ink used until about
50% gray.
This only applies to color mode.
This value should be set lower for printers capable of variable dot
size, since more dots can be laid down close to each other.
@item
@code{dither_set_black_upper()} takes a double that should be between 0
and 1 that represents the highest density level at which colored inks
will be mixed to create gray. Setting this too low will result in
speckly dark grays because there is not enough ink to fill all the
holes, or sharp transition between blended colors and black if it is too
close to the value of dither_set_black_upper(). Setting this too high
will result in poor black and dark tone quality. Default: 0.5. This
results in 10% and darker grays being printed with essentially all
black.
This only applies to color mode.
@item
@code{dither_set_black_levels()} takes three doubles that represent the
amount of cyan, magenta, and yellow respectively that are blended to
create gray. The defaults are 1.0 for each, which is probably too low
for most printers. These values are adjusted to create a good gray
balance. Setting these too low will result in pale light and midtone
grays, with a sharp transition to darker tones as black mixes in.
Setting them too high will result in overly dark grays and use of too
much ink, possibly creating bleed-through.
This only applies to color mode.
@item
@code{dither_set_randomizers()} takes four integer values representing
the degree of randomness used for cyan, magenta, yellow, and black.
This is used to allow some printing to take place in pale areas. Zero
is the most random; greater than 8 or so gives very little randomness at
all. Defaults are 0 for cyan, magenta, and yellow, and 4 for black.
Setting the value for black too low will result in black speckling in
pale areas. Setting values too high will result in pale areas getting
no ink at all.
This currently only applies to single dot size in color and black. It
should be extended to operate in variable dot size mode, although
actually applying it correctly will be tricky.
@item
@code{dither_set_ink_darkness()} takes three doubles representing the
contribution to perceived darkness of cyan, magenta, and yellow. This
is used to help decide when to switch between light and dark inks in 6
and 7 color printers (with light cyan, light magenta, and possibly light
yellow). Setting these too low will result in too much light ink being
laid down, creating flat spots in the darkness curves and bleed-through.
Setting them too high will result in dark ink being used in pale areas,
creating speckle. The defaults are .4 for cyan, .3 for magenta, and .2
for yellow. Dark cyan will show against yellow much more than dark
magenta will show against cyan, since the cyan appears much darker than
the yellow.
@item
@code{dither_set_light_inks()} takes three doubles between 0 and 1
representing the ratio in darkness between the light and dark versions
of the inks. Setting these too low will result in too much dark ink
being used in pale areas, creating speckling, while setting them too
high will result in very smooth texture but too much use of light ink,
resulting in flat spots in the density curves and ink bleed-through.
There are no defaults. Any light ink specified as zero indicates that
there is no light ink for that color.
This only applies to 6 and 7 color printers in single dot size color
mode, and only to those inks which have light versions (usually cyan and
magenta).
@item
@code{dither_set_ink_spread()} takes a small integer representing the
amount of ink spread in the dither. Larger numbers mean less spread.
Larger values are appropriate for line art and solid tones; they will
yield sharper transitions but more dither artifacts. Smaller values are
more appropriate for photos. They will reduce resolution and sharpness
but reduce dither artifacts up to a point. A value of 16 or higher
implies minimum ink spread at any resolution no matter what the
overdensity. A value of 14 is typical for photos on single dot size, 6
color printers. For 4 color printers, subtract 1 (more spread; the dots
are farther apart). For variable dot size printers, add 1 (more small
dots are printed; less spread is desirable).
@item
@code{dither_set_adaptive_divisor()} takes a float representing the
transition point between error diffusion and ordered dither if adaptive
dithering is used. The float is a fraction of the printing density.
For example, if you wish the transition to be at 1/4 of the maximum
density (which works well on simple 4-color printers), you would pass
.25 here. With six colors and/or with multiple dot sizes, the values
should be set lower.
@item
@code{dither_set_transition()} takes a float representing the exponent
of the transition curve between light and dark inks/dot sizes. A value
less than 1 (typical when using error diffusion) mixes in less dark
ink/small dots at lower ends of the range, to reduce speckling. When
using ordered dithering, this must be set to 1.
@item
@code{dither_set_@var{X}_ranges_simple} (@var{X}=@samp{c}, @samp{m},
@samp{y}, or @samp{k}) describes the ink choices available for each
color. This is useful in typical cases where a four color printer with
variable dot sizes is in use. It is passed an array of doubles between
(0, 1] representing the relative darkness of each dot size. The dot
sizes are assigned bit patterns (and ink quantities, see
@code{dither_set_ink_budget()} above) from 1 to the number of levels.
This also requires a density, which is the desired density for this
color. This density need not equal the density specified in
@code{dither_set_density()}. Setting it lower will tend to print more
dark ink (because the curves are calculated for this color assuming a
lower density than is actually supplied).
@item
@code{dither_set_@var{X}_ranges} (@var{X}=@samp{c}, @samp{m}, @samp{y},
or @samp{k}) describes in a more general way the ink choices available
for each color. For each possible ink choice, a bit pattern, dot size,
value (i. e. relative darkness), and whether the ink is the dark or
light variant ink is specified.
@end itemize
---Robert Krawitz @email{<rlk@@alum.mit.edu>} May 8, 2000