( Dithering

Info Catalog ( Appendices ( Appendices ( Weaving
    The dithering code in `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:
   1. `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.
   2. `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.
   3. `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.
    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
   1. bottom of the range
   2. top of the range
   3. value of the lighter ink
   4. value of the darker ink
    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:
   1. 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).
   2. Find the range containing this value.
   3. 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.
   4. 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.
   5. 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.
    The matrices were generated by Thomas Tonino <<>>
 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
    I stated earlier that I've tweaked the basic error diffusion
 algorithm.  Here's what I've done to improve it:
   1. 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
      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
   2. 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.
   3. Diffusing the error into more pixels.  Instead of diffusing the
      entire error into (X+1, Y) and (X, Y+1), we diffuse it into (X+1,
      Y), (X+K, Y+1), (X, Y+1), (X-K, Y+1) where 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 *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).
   4. 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.
   5. 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.
    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, `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
 `vars_t' structure containing the parameters for the print job.
    `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, `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
    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
    * `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.
    * `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
      `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 (`dither_set_density') should be
      adjusted appropriately.
    * `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 `dither_set_X_ranges'.
      By default, there is no limit.
    * `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.
    * `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.
    * `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
      This only applies to color mode.
    * `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.
    * `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.
    * `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).
    * `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).
    * `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.
    * `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.
    * `dither_set_X_ranges_simple' (X=`c', `m', `y', or `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
      `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
      `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).
    * `dither_set_X_ranges' (X=`c', `m', `y', or `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.
    --Robert Krawitz <<>> May 8, 2000
Info Catalog ( Appendices ( Appendices ( Weaving
automatically generated byinfo2html