Re: [Gimp-print-devel] Halftoning algorithms

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

Karl Heinz Kremer wrote:

> I'm not sure if Thomas Tonino is on the list...I'm reading his message
> on geocrawler and I have comments on it.  If he's not, could someone
> forward him the message?  His email address doesn't appear in the
> archived message.

Yes, I'm on the digest.

> I once experimented with only allowing one dot to be printed if the
> density at that point was less than one.  It didn't help too much.

I think the other color will then be printed adjacent to the current
dot. This doesn't help much I would expect. The key is to print the
first dot much earlier, the second a lot later. It may be better to
leave yellow out of the darkness calculation - yellow is not very dark.

[ instability ]

> The problem was that not
> enough ink was getting printed to discharge all of the error, and the
> built-up error got printed out in white areas very strangely.  I wound
> up having to cap the accumulated error to avoid this.

The pseudocode has a while loop that keeps finding colors to print for
the current pixel, until the total error is gone. But it may well be
possible to have two colors at a maximum negative and two others at a
maximum positive error threshold. For pixels in values of 0 to 100 % in
a 4 color system I would expect the worst case to be the following case:

- All pixels are at 12.5 % error, giving a sum of 50% which is
threshold.
- The system fires one of the colors, bringing it to - 87.5% error.
- The other colors rise to 46 % ( 3 * 46 - 87.5 is just above the
threshold of 50) and one of them fires.
- This leaves one color in -87.5 % and another in 46 - 100 = -54 %. Now
the two remaining colors could rise to a sum of 191.5, so 96 % each. If
one colors prints now, we are left with the following state:

- 87.5%
- 54 %
- 4 %
+ 96 %

The gray value of this error is within bounds as is to be expected. The
color errors are double the errors of the non brightness aware dither.

This may be a problem or it may not be, but it points to an inherent
problem in Floyd-Steinberg: it is not built on a model of human vision.
Say we print two objects quite a distance apart. If one object gets too
little ink, the other one gets too much. This is not neccessary for
correct percetion: making one line thicker does not make th eother line
seem any thinner. It is the root of the color bleed problem described
above: what basically happens is that the system can and will compensate
for a lack of ink in one place by putting that ink on a totally
different place on the page.

It may be worthwhile to use a different method of dithering. Dithering
works because the eye sees things a little blurred. By modeling how that
blur works, we can get a better result.

By calculating a gaussian blur of the surrounding pixels (as far as they
have been printed) one gets a better match to perception: nearby pixels
have larger influence than pixels father away.

The gaussian blur needs to be larger than the largest distance between
pixels to be printed. Calculating big gaussian blurs may be slow, but it
can be optimized fairly well. Now compare the current pixel to the color
formed by the blurred surrounding pixels and determine the optimal dot
to print. Update the gaussian buffer with the current printed dot and
move on to the next pixel to be printed.

> BTW, something else that I've done, which seems to have done a lot to
> eliminate the diagonals so common with error diffusion, is to
> distribute the error over a variable number of pixels.  Specifically,
> the lighter the tone, the broader the region over which the error is
> distributed.

Seems to be a good idea. Larger and different error distribution
matrices have also been proposed in the past. Some I have found are:

Burkes:

0  0  x  8  4
2  4  8  4  2   /32

Stucki:

0  0  x  8  4
2  4  8  4  2
1  2  4  2  1   /42

Sierra:

0  0  x  5  3
2  4  5  4  2
0  2  3  2  0   /32

Steven:

 0  0  0  x  0 32  0
12  0 26  0 30  0 16
 0 12  0 26  0 12  0
 5  0 12  0 12  0  5   /200

I have no idea of what the design goal for these matrices is. Other ways
to decrease squigglies could be to forbid or discourage printing in
certain patterns and to distribute the error mainly to the place where
you do not want more dots to be printed:

      x  2  1
0  1  2  1  0
1  0  1  0  1   /10

Basically the 0's in the above are places where we prefer pixels if the
current dot is printed, the 1's are neutral and the 2's are discouraged.
I do not know if the effect is sufficient - I feel the gaussian method
may be better eventually because it has a perception model built in. It
would even be possible to calculate wider gaussians for color and a
tighter gaussian for perceived brightness, and determine what needs to
be printed from the various results: the largest error gets corrected,
basically.

Sounds like quite a project though.


Thomas Tonino
tt...@bi...