[Gimp-print-devel] Halftoning algorithms

[Thomas T. <tt...@bi...>]

I have recently been thinking about how Ghostscript dither quality could
be improved. I came up with two major ideas.

My most recent idea was to use Floyd-Steinberg on the brightness of the
image. Instead of deciding per color when to print, decide on the basis
of total accumulated error. When that exceeds threshold, print the color
with the darkest error and distribute errors accordingly. In light tints
colors will not overlap any more, hopefully leading to smoother and
brighter results.

Example pseudocode:

For x,y in image:
  While (Cyan[x,y]+Magenta[x,y]+Yellow[x,y]+Black[x,y]) > Threshold
    Find the largest of Cyan[x,y] Magenta[x,y] Yellow[x,y] Black[x,y]
    Print a dot in this color 
    ThisColor[x,y] -= dotsize  # so we can exit the while loop
                               # the value is the error; it is
distributed over the neighboring pizels
    ThisColor[x+1,y] += ThisColor[x,y] * 7/16
    ThisColor[x-1,y-1] += ThisColor[x,y] * 3/16
    ThisColor[x,y-1] += Thiscolor[x,y] * 5/16
    ThisColor[x+1,y-1] += Thiscolor[x,y] * 1/16

I think this will give 3 times as many effective pixels for greyscale
images. Color is printed a bit less accurately, but the human eye
notices color variations less than variations in brightness. Manual
execution with a spreadsheet showed color dots not being printed on top
of each other, unless the total ink amount was so high that overlap was
needed. With per-color Floyd-Steinberg, the occasional 2 or 3 color
pixel shows up, and the interference patterns between the different ink
colors can show up as coarseness.

An older idea was to take dot overlap into account. If two dots are
printed adjacent to each other, they overlap. As a result the two dots
are not as dark as when they would have been printed a bit apart from
each other. I do not know if this is something that must be taken into
account: overlapping will only happen near full density and I doubt if
this modification does anything except change the tone curve somewhat.

Thomas Tonino