Re: [Gimp-print-devel] Halftoning algorithms

[Robert L K. <rl...@al...>]

This is just a quickie reply...your note contains a lot of technical
meat, far more than I know myself, and I need to digest it.

   Date: Thu, 16 Mar 2000 12:55:10 +0100
   From: Thomas Tonino <tt...@bi...>

   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.

It needs a bit more support in the infrastructure to make this
practical.  Right now the model is that the dither routine is passed a
row of input and generates a corresponding row of output.  That
doesn't allow for any lookahead or write behind, which would allow
much more flexibility.

   > 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:

Actually, what I'm doing is a pseudo-Gaussian.  It winds up with
something like

0  0  x  3  0
0  0  5  0  0

when there's a lot of ink.  Where dots are sparser, though, it becomes
(for example)

0   0   0   x  60   0  0
5  10  15  20  15  10  5

which is pseudo-Gaussian.  It works very well, but there are very fine
horizontal rows that (to my eye, at least) aren't very unpleasant.
Obviously it isn't really Gaussian, but triangular is close enough for
a first cut and fast computationally.  Interestingly, I tried
something like this:

0   0   0   x  30  20  10
5  10  15  20  15  10   5

and wound up with lots of grain again.  I *think* that the problem
here is the correlation between the two rows.

   Burkes:

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

That's similar to what I tried and didn't like.

   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 like the look of this one and of your suggestion.

   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.

I think that we should start off with experimenting with the diffusion
matrix, just because it's easier to start with.  Of course, right now
we only support a two-row matrix, but that can always change...

-- 
Robert Krawitz <rl...@al...>      http://www.tiac.net/users/rlk/

Tall Clubs International  --  http://www.tall.org/ or 1-888-IM-TALL-2
Member of the League for Programming Freedom -- mail lp...@uu...
Project lead for The Gimp Print --  http://gimp-print.sourceforge.net

"Linux doesn't dictate how I work, I dictate how Linux works."
--Eric Crampton