Created attachment 25365 [details]
8x8 dither versus positional(64x64) dither comparison

Well, if someone wants to hack this, then why not. Adam said that he's
not interested, but I don't see why we shouldn't accept a patch if it
is simple enough to be understood w/o studying this code for weeks.

Oh, it's very easy to do -- as simple as duplicating the existing
positional-dither code/options using a smaller matrix.  It's just
pretty darn esoteric to put in the core/UI and present to the majority
of users.  I'd be happy to do it myself if a number of people seemed
to want it, but at least in the short-mid term I couldn't personally
do it for 2.x.

> b) fix positional dithering so it's actually useful and
> non-random-looking

Absolutely bloody not!  It's *supposed* to be a random-looking
distribution to avoid fishbone/banding, except it's better than a
random dither because it avoids random clumping.  It's also 'actually'
useful for what it's intended for.  That's not to say it's perfect; it
does clamp the error pretty early.

Yeah, I'm remembering why it's like this now, it's because we need to
dither to an ARBITRARY colourmap rather than a regular colour cube. 
Check out what it does to the alpha channel when you select
transparency-dithering as a model for what you'd otherwise do if you
were dithering to a simple number of bits (i.e. one) per channel
(that's what it's doing to alpha in that situation).

dithering afaik is a tradeoff between color resolution and
spatial-resolution. ideally you'd be able to select how much of a
tradeoff you want (smaller matrices preserving more spatial resolution
while sacrificing some color resolution). the reason i chose 16x16 as
a maximum was that i see no benefit in having it larger than that
(16x16 -> 256 levels).

in my opinion it would be appropriate at least to reduce the
positional-dither matrix size to 16x16.

i'm not understanding what you mean by the second paragraph. the
alpha-dither looks pretty nice, although i'd still prefer a
deterministic interlocking pattern because it looks more uniform. what
is wrong with using the alpha-style dither for color quantization?
the only scenario i can think of that might explain this is if you are
dithering to simulate a color using three colors rather than two.

the basic idea behind this bug report is that the existing code trades
off too much spatial resolution for color resolution. this gives an
excessively blurry aspect to blends. while your intent is to avoid
fishboning and banding,adam, i want to avoid indistinctness.

thanks for the explanation on what would need to be done.

Note that the best dithering method depends very much on the source
image and the desired number of colors in the output:
- If you start with a photographic-style image that has many colors
  and color transistions, a Floyd-Steinberg dithering or positioned
  dithering with a large matrix is likely to provide the best results
  because they reduce the banding effects.
- On the other hand, if you have a cartoon-style image that has many
  smooth color gradients or uniform areas, then it is sometimes better
  to use a positioned dithering with a small matrix because the
  repeating features of this small matrix bring some order to the
  picture and the result looks better.

I don't know what would be the best way to present this new feature to
the users.  But the dither options dialog contains already the F-S
dithering with and without reduced color bleeding, so we could add a
choice for the positioned dithering with a small or a large matrix.

Bug 161113 contains a patch that makes the existing fixed-dither work how it's
supposed to, i.e. utilize the full range of the matrix better.

I'm actually running with a 4x4 dither locally, for fun, and on top of bug
161113's patch it's trivial and works well (given that it's 4x4).

If I find/derive an appropriate 16x16 matrix I might push to replace RaphL's
diffusion matrix with it, since it'd almost certainly compress better and that's
half the point of the positional dither even existing (that is to say, in
conjunction with AnimOptimized animations).

given a base matrix of 2x2:

 13
 42
(where the number represents the amount of color B in the result (from 0 to 4)

you can derive any power-of-two sized matrix from it easily. I wrote a program
which performs that derivation (2x2 -> 4x4 -> 8x8 -> 16x16 ...).

The engine of the program:

# takes a (oldw, oldh) tuple and a 2d array (ie. matrix) as input
# returns a tuple (new_width,new_height) and the resultant matrix.
def next(d,inp):
    """Constructs a dither-matrice twice the size of the input"""
    o = numarray.array(shape = (d[0] * 2, d[1] * 2), type = numarray.UInt16)
    w = d[0] * 2
    h = d[1] * 2

    for x in xrange(0,d[0]):
        for y in xrange(0,d[1]):
            data = (inp[x][y] - 1) * 4 + 1
            o[        x ][        y ] = data
            o[ x + d[0] ][ y + d[1] ] = data + 1
            o[ x        ][ y + d[1] ] = data + 2
            o[ x + d[0] ][        y ] = data + 3    

    return (d[0] * 2, d[1] * 2),o


the effect:

13
42

becomes

194B
D5F7
3C2A
G8E6

(written in base 17)

I like that a lot, though I forgot to mention that I found such a routine now
(in netpbm).

hmm, i found some predefined dithering matrices in netpbm, but not a routine
analogous to the above one. something i want to note about those predefined
matrices: their smallest value == 0, not 1. The thresholding must work based on
(b-1) rather than (b). meh, I chose to start at 1 in my satrices because then it
really does mean exactly 'the amount of b' (despite the inconvenience of max_val
== 256 rather than 255.)

Now, knowing a lot more about gimp , I've implemented a prototype of this:

a function named 'gimp_image_convert_set_dither_matrix'. It tiles the given
matrix across the 128x128 lookup table. If you pass it NULL, it restores the
original.

It scales the input to the 0..63 range used by the dithering code, so you can
easily specify matrices in a natural way. The only requirement is dimensions
which are powers of two in the input matrix.

There is also some testing code in there which sets the matrix to a 4x4 one.
It is currently active, and i really like the results.
Try getting a bilevel image and blurring(using convolve) a curve in it. It
preserves the shaping much better than Raph's matrix does (and also importantly,
it has less visual 'noise'; noisiness is a major downside of the non-clumping
matrix for me.)

This is a basically working patch; I'll make another one after i remove the
testing code and verbosity, and add PDB accessors.

One thing I haven't figured out yet is the UI. Should matrix-selection be
implemented via a pattern-selector in the indexize dialog? Or left to user
scripts and plugins to setup?

Created attachment 51752 [details] [review]
Add an API for customizing the dither matrix

* the input matrix must be an array of guchars with dimensions that are both
powers of two (but can be unequal, like 4x8)
* maximum dither levels == 62. (0 == completely color A, 63 == completely color
B)

Comment on attachment 25365 [details]
8x8 dither versus positional(64x64) dither comparison

Comparison image is obsolete - Bug 161113 fixed.

I don't strenuously object, but I think that the whole idea of 'custom' dither
patterns is gross over-engineering (some of which I've been guilty of in my
younger, more foolish gimp days and eventually hope to rectify) of a detail that
almost no-one will really care about once  saner default is in place (the small
number who do, can hack).  I've been running with a fat Bayer matrix for ages
now and since bug 161113 got fixed I like the results better for various
reasons.  I think we should just replace the Raph matrix with a fat (~64x64)
Bayer matrix and be done.

I'm happy to provide a replacement matrix that I like; I can even provide a
patch,  though my tree is old enough that it might not be clean.

A patch would be nice. I can take care of updating it so that it applies to the
current CVS, in case there are problems.

Adam: A lot of it is for aesthetic effect. For instance, some objects I would
like to dither with a diamond pattern, others with interlocking squares.. For
primarily vertical objects, vertically-oriented dithering can look best (and
horizontally-oriented for horizontal objects). I'm perfectionistic :)

Sven: That patch as it is should work on current CVS, i made it yesterday. It's
quite OK for trying out the feature but yeah, i need to make a cleaned up
version that is suitable to commit.

Given the esotericness of this, I'll leave its user-exposure to a PDB function only.

David, the comment about the patch was made to Adam. Sorry for not making that
clear.

Since you are asking for esotheric stuff here, shouldn't this go into a plug-in
then, which can be maintained outside the tree? I would prefer not to overload
the core RGB->Indexed conversion.

.. I don't know if i used the right word. What i mean is, something that is very
useful only if your knowledge and planning is advanced enough to use it.
Something that the average user will not use. Like named buffers.

.. 
The actual addition is quite self-contained. the only differences are: 

* add a copy of the original DM array to gimpimage-convert-data.h,
  and deconstify DM
* add gimp_image_convert_set_dither_matrix() function to gimpimage-convert.c
* (TODO) add gimp-image-convert-set-dither-matrix to PDB.

all the other stuff is testing-only, so, zero changes to the conversion code.

Created attachment 51784 [details] [review]
change default dither matrix to 32x32 Bayer

This blind patch against CVS HEAD addresses the 'bug' in David's 'b)' way.
I can't come close to compiling HEAD so this is going to need two basic tests
before committing:
1) Use positional dither to dither a gradient to a mono palette and
particularly verify that solid-black and solid-white remain undithered
2) Check that I didn't break alpha-dithering

The changes for 1), not 2), were tested out in my 2.0 tree, but not against 2.1
or 2.3 or whatever HEAD is up to now.  The new matrix lets us avoid some value
scaling, making alpha-dithering faster assuming that it still works.  Let me
know if it doesn't work in HEAD.

The Bayer matrix looks less 'random' than the Raph matrix but of course looks
more patterny in the low-colour cases.	This is generally desirable considering
what the positional dither was designed for (allowing dithering of animations
to create more compressable optimized results due to preserving inter-frame
similarities); the Bayer matrix results generally compress somewhat better
(whether the source is animated or not) due to more coherent patterns along the
scanline.

Whether or not David's customisation changes go in, I think this change should
go in first.

That works fine, both for normal and alpha dithering :)
I noticed in passing a bug where dithering to B/W is extremely optimistic (the
resultant picture is MUCH brighter than the source.). I remember coming across
that before. There doesn't seem to be a bug for it, should I enter one?
(covering both 'indexizing to a very low number of colors produces wrong
results' and 'dithering te B/W is overly optimistic' -- i suspect they're related.)

My patch intersects fine with this also (I just have to duplicate and unconstify
DM in gimpimage-convert for my function to work as expected again).

Is the bug there before and after the patch?  Can you supply examples and/or
screenshots?  It's a different bug but I may as well take a look while I'm here,
I don't get to look at gimp stuff very often.

Created attachment 51797 [details]
examples of BW dithering error

It occurred both before and after.
This image shows in order l->r:

source | FS-dither | FS (reduced bleed) | positional

Thanks for the example, though the results illustrated are as-intended for each
option.

2006-01-02  Sven Neumann  <sven@gimp.org>

	* app/core/gimpimage-convert-data.h
	* app/core/gimpimage-convert.c: applied patch by Adam D. Moss that
	replaces the default dither matrix by a 32x32 Bayer pattern (see
	bug #136604).

Created attachment 70019 [details] [review]
updated, tested patch, applicable to CVS HEAD

Coming back to this, I finally got the PDB interface to work. It should be good to commit now.

There are minor coding style issues with the patch: in function declarations, there should be one space before the opening parenthesis, never after it.  Also, you could add a comment in gimpimage-convert-data.h saying that "DM" is not const because it may be overwritten.  Otherwise, the patch looks good although I did not test the PDB interface.  If nobody complains, I would commit this code in a couple of days with the minor style cleanup and some additional comments.

It would be nice to provide at least one script (scheme, perl or python) that uses this new PDB interface to set a different dither matrix.

Created attachment 70024 [details] [review]
cleaned up patch

I have some interesting matrices I've already tried, so I have just to write the plugin (in Python). Should be done very quickly.

Not perfect yet :-)  You still have wrong spacing for the calls to g_return_if_fail and for the declaration in gimpimage-convert.h.  But you do not have to re-submit a patch just for these details.

Created attachment 70028 [details] [review]
finished patch

.. I had to anyway , to fix a bug that prevented resetting the dither matrix.

Plugin offering choices between standard, crosshatch, and square dithering styles follows.

Created attachment 70030 [details]
plugin providing example usage

The plugin's procs register themselves with the following menu paths:

<Image>/Image/Mode/Use _Crosshatch dithering
<Image>/Image/Mode/Use _Square dithering
<Image>/Image/Mode/Use Standar_d dithering

The location of these entries is the only thing that I think could use more work.
The actual plugin itself is very simple.

Tanks for the script.  It would be better to put these functions in a submenu, such as "Image/Mode/Dithering/..." or "Image/Mode/Conversion/...".

As for the PDB call, it would be better to change the order of the parameters and have width and height before the matrix.  This would be more in line with other PDB entries dealing with arrays, even if the order does not really matter much.

Created attachment 70084 [details]
updated plugin

* fixed off-by-one error in crosshatch dither matrix
* updated menu paths (Mode/Conversion)

The parameter order is easily fixed by transposing a few lines in the patch, so I won't resubmit that.

Thanks for your patch.  It is now in CVS.  I swapped the arguments as mentioned above and did some minor whitespace adjustments.  Note that you used the default copyright message, assigning it to Spencer & Peter.  Maybe you should attribute this new PDB function to yourself?

Also, I tried the script and it works fine (after swapping the arguments).  However, I don't know if we should include it as part of the GIMP distribution or if it would be better to add the functionality to select or load custom dither patterns directly into the "convert to indexed" dialog?

2006-08-04  Raphaël Quinet  <raphael@gimp.org>

	* app/core/gimpimage-convert-data.h
	* app/core/gimpimage-convert.c
	* app/core/gimpimage-convert.h
	* tools/pdbgen/pdb/convert.pdb: Applied slightly modified patch
	from David Gowers allowing a custom dither matrix to be used when
	converting images to indexed mode.  Fixes bug #136604.
	
	* app/pdb/convert_cmds.c
	* app/pdb/internal_procs.c
	* libgimp/gimpconvert_pdb.h
	* libgimp/gimpconvert_pdb.c: Regenerated.

Yeah, I was lazy about the attribution; I don't care in this case.
Direct selection(via greyscale pattern) would be nice and I can provide a range of patterns including the ones that are in the plugin.
I've noted the idea and  will investigate it later (involves defining an appropriate constraint function for a palette selector, right?)

Just for the record, I have now added the correct attribution in the PDB.

I'm not sure about what would be the best user interface and best underlying code for selecting the dithering patterns.  This deserves a separate bug report anyway.