diff options
Diffstat (limited to 'doc/dither.texi')
| -rw-r--r-- | doc/dither.texi | 504 |
1 files changed, 0 insertions, 504 deletions
diff --git a/doc/dither.texi b/doc/dither.texi deleted file mode 100644 index f0b363e..0000000 --- a/doc/dither.texi +++ /dev/null @@ -1,504 +0,0 @@ -@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 |