Improved palette reduction algorithm

[GoogleCodeExporter]

1. Load a 24bit image, for example MARBLES.PCX in the pic samples.
2. Look at the picture, it is not dithered at all, looks like the error 
distribution is not done as it should. Compare with the same image when 
you load it in gimp, then convert it to indexed colors mode.

Please use labels and text to provide additional information.

Original issue reported on code.google.com by pulkoma...@gmail.com on 3 Dec 2008 at 6:47

[GoogleCodeExporter]

Ok, fixed the dithering system, there was a stupid bug in it.
Now, the palette seems a bit unsaturated, maybe we should try clustering on HSL 
(with hand-tweaked coefficients for ech of them) instead of RGB to get more 
color 
dynamic. The floyd steinberg dithering can easily create a grey color by 
dithering 
blue and yellow, the reverse is harder.

Original comment by pulkoma...@gmail.com on 3 Dec 2008 at 8:58

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Original comment by pulkoma...@gmail.com on 2 Jan 2009 at 12:15

• Changed title: Improved palette reduction algorithm
• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Original comment by pulkoma...@gmail.com on 26 May 2009 at 7:54

• Added labels: Component-Tools, Milestone-2.1
• Removed labels: Milestone-2.1b4

[GoogleCodeExporter]

This was actually started, Pulkomandy is there still something you wanted to do 
about
it ? (besides removing my unused function "without Floyd_Steinberg")

Original comment by yrizoud on 25 Aug 2009 at 8:37

• Changed state: Started

[GoogleCodeExporter]

Actually GIMP still builds a palette that is better than ours for dithering. I 
don't 
know how, but they cheat in the median cut algorithm to get more saturated 
colors. 
And Floyd Steinberg compensate for it, as when you dither in a green/purple 
pattern, 
you can build grey (this is the extreme case).

And, don't the latest revs use the non-dithered version now ? I still think 
this 
should be made available as an option...

Original comment by pulkoma...@gmail.com on 25 Aug 2009 at 9:36

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

GIMP doesn't use HSL nor RGB for its quantization, but LAB: see
http://git.gnome.org/cgit/gimp/tree/app/base/cpercep.h (and the matching .c 
file).
The LAB implementation in GIMP is extremely carefully done, and one of the few
actually correct implementations in existence.

LAB is a far more.. 'truthful' colorspace than RGB or HSL, so I believe it is 
very
very hard to get as good results while you are using these colorspaces (in 
which, for
example, color distance is misleading). 

IIRC the actual quantization code is in app/core/gimpimage-convert.c, including 
the
code to partition the colorspace according to the found colours. Check the 
history
near the top of the file, it's very informative.

cpercep is some nice code (and pretty mature), it might be wise to use it in 
GrafX2.
Also, LAB (or LCH, which is just a polar transform of AB components into 
chromaticity
(~=saturation) and hue) palette spreads would work more intuitively than RGB or 
HSL
for many cases.

Original comment by 00a...@gmail.com on 15 Sep 2009 at 7:25

[GoogleCodeExporter]

Original comment by pulkoma...@gmail.com on 15 Sep 2009 at 7:13

• Added labels: Milestone-2.3

[GoogleCodeExporter]

I played with cpercep a bit, but only managed to get a red/yellow palette (no 
blue, 
no green, no pink), so the results are quite bad. It seems to still work fine 
for 
the color that are rendered right.

I attach it here as a patch if anyone wants to find what's wrong.

Original comment by pulkoma...@gmail.com on 1 Nov 2009 at 12:55

Attachments:

• cpercept.patch

[GoogleCodeExporter]

The main problem here is,

You're storing values of range -107..+98 in unsigned bytes (ie range 0..255).
It's not surprising you can't get certain hues, you're basically clipping them 
out of
existence.
The precision of the storage of L channel could also be improved (it's on the 
range
0..100)

If you want to do things that way, you need to translate the values 
appropriately.
that is, before storing, do this:

// I've used the right variable names here instead of 'r,g,b'
// since the output of cpercep_rgb_to_space is in no way RGB, but completely LAB
// .. yes, the output argument names are misleading.

l *= 2.55;   // exact.
a += 87;     // minimum A value = -86.180778500000002
             // maximum A value = 98.236976619999993
a *= 1.3766; // approximation of 1.3766150536276922
             // which equals 255 / (maximum_A_value + 87) 
b += 108;    // minimum B value = -107.85834503
             // maximum B value = 94.480010989999997
b *= 1.2593; // approximation of 1.2593835744734023
             // which equals 255 / (maximum_B_value + 108)

and reverse the above transformation before you feed it back into 
cpercep_space_to_rgb.

The above transformation is designed to maximize precision.
A more approximate one looks like this:

l *= 2.55;
a += 128;
b += 128;

Which might be easier for testing purposes.. You'd want to use the precise one 
as
soon as you'd verified this one works, though, it'll produce better quality for 
sure.

Original comment by 00a...@gmail.com on 1 Nov 2009 at 2:19

[GoogleCodeExporter]

Works better with that.
However now all the computation are done on 8-bit precision so i'm not sure we 
are 
winning that much.

It also makes the nearest neighbour reduction work really bad.

I had a look at what gimp does and I'm not sure it's worth adding all that 
stuff 
just for loading 24bit pictures since you'll probably want to clean them up 
afterwards anyway...

Attached conversion samples from MARBLES.PCX if you want to have a look.

I don't think I'll go further with this, lot of lines of code that may not be 
worth 
it.

Original comment by pulkoma...@gmail.com on 1 Nov 2009 at 3:59

Attachments:

• gimp.png
• grafx2_new.png
• old_grafx2.png

[GoogleCodeExporter]

It looks to me like you are comparing a FloydSteinberg dithered 'new' image 
with a
non-dithered 'old' image.. that doesn't seem like an accurate comparison. If
dithering was enabled for both, it looks like the 'old' dithering is broken.
The 'new' image is also offset both horizontally and vertically.

If you use some distance metric to determine what colors to discard, that may 
also be
currently incorrect -- applying cpercep_distance_space (from cpercep.h, 
currently #if
0'd out.) to the LAB values should give more accurate result.

Original comment by 00a...@gmail.com on 1 Nov 2009 at 9:56

[GoogleCodeExporter]

Yes. Actually I wasn't sure if dithering was enabled or not in the old version. 
And 
I quickly cropped the big sample picture in gimp (it's a 1410x1001px file) so 
they 
don't have the same size.

I tried with dithering disabled too, but this gives even worse results. It 
looks 
like something is oversaturated, maybe it's linked to the loss of precision due 
to 
the 8-bit calculations. GIMP is using a mix of 64-bit int and floats, so it 
works 
better for them.

And yes, they have a different way to split clusters in the median cut. We 
split at 
the middle of the longest axis (real median cut) while they compute the mean 
(pondered by number of pixels for each color), which may or may not be a lot 
better.

Actually, we don't really want dithering as the picture is meant to be touched 
up in 
grafx2, so we want to keep clean outlines instead. Our current implementation 
outputs a quite grayish palette but keeps the outlines quite nicely.

Original comment by pulkoma...@gmail.com on 1 Nov 2009 at 10:12

[GoogleCodeExporter]

I don't really understand the code in op_c.c, it's a bit hard to read.
I would guess that the excessive grayness in the current quantizer is caused by
treating the RGB colorspace as if it were linear. I can tell that HSL_to_RGB and
RGB_to_HSL at least suffer from this.
I'll try adding some code to de/linearize the RGB components when converting 
from/to
HSL and check if it improves results. 

For reference, converting nonlinear sRGB values in the range 0..1 to linear RGB
values in the range 0..1 is done like this:

#define EPS1 0.04045
// for each of r,g,b:
if (value <= EPS1)
  value = value / 12.92;
else
  value = pow (value + 0.055) / 1.055, 2.4);

The opposite transformation (linear RGB to nonlinear sRGB) is:

#define EPS2 0.0031308
// for each of r,g,b:
if (value < EPS2)
  value = value * 12.92
else
  value = 1.055 * pow (value ** (1.0 / 2.4)) - 0.055 // I need to check if the pow()
is around the right subset of the equation, so this may not be 100% correct.

Original comment by 00a...@gmail.com on 2 Nov 2009 at 8:20

[GoogleCodeExporter]

actually hsl is not used for color reduction. median cut is done on RGB values 
with
an axis ponderation (using arbitrary values i found somewhere on the internet)

Look at the part about clusters.

Original comment by pulkoma...@gmail.com on 2 Nov 2009 at 9:33

[GoogleCodeExporter]

I have looked at the part about clusters repeatedly (I'm sure the comments are
quite helpful, if you know French.. I don't :)

While I still don't understand the clustering code very well, I understand that 
the
weightings on lines 464..466 are necessarily inaccurate.. all such weightings 
should
be done on linear data. Especially in this instance, you are calculating 
distances
which are inaccurate (essentially measuring along a curve as if it were a 
straight
line). 
To illustrate this .. what's the difference between
sRGB 255, 255, 255 (white) and 128,128,128 (gray)?
The naive metric says '127,127,127'. The correct metric says '200,200,200'

The weightings suggested by the W3C sRGB specification are:

213 (rounded from 212.6)
715
 72

I haven't figured out yet, whether c->rmin,vmin,bmin are on the normal sRGB 
0..255
range. I'll make a patch to linearize the RGB values before measuring the
differences, as soon as I figure out whether they are on the 0..255 range.

Original comment by 00a...@gmail.com on 2 Nov 2009 at 12:26

[GoogleCodeExporter]

There aren't any colorspace conversions, we just take the values from the 24bit 
picture.
But with the current algorithm, we split the cluster on its biggest axis (using 
this 
weird multiplication that may or may not improve things), and we select the 
cluster 
to split looking only at its number of covered pixels.

Anyway, i've translated the comments to english in the file and added some more 
(there is even some more space left for optimizations)

And here attached is my "working" implementation of the L*A*B* colorspace 
conversion.

Original comment by pulkoma...@gmail.com on 2 Nov 2009 at 7:32

Attachments:

• cpercep.diff

[GoogleCodeExporter]

Thanks for taking the time to translate that!

Here's my patch (not optimized) which uses linear RGB when 
a) calculating HSL->RGB or RGB->HSL conversions
and
b) choosing a quantized palette.

I'll optimize it soon.
It seems to represent the original picture's colors better.
Here is an example.

Original picture:
http://www.placervilleflowermarket.org/images/flowers/wed_r_3.jpg

I performed 'Selective Gaussian blur' in GIMP with radius 3, delta 20 to remove
as much jpg artefacts as possible.
I saved this as wed_r_3.png (which is too big for my picture host.. 2.2 mb. So I
can't provide a link.)

Loaded it into a compilation of grafx2 before the patch was applied, and got 
this result:

http://img.photobucket.com/albums/v449/neota/tech/oldq.png

I wasn't happy with this because it destroyed some particularly vivid areas,the 
wall
in the backdrop became too saturated, and some flowers in the foreground became 
too dark.

Recompiling and loading it into a version of grafx2 *with* the patch:

http://img.photobucket.com/albums/v449/neota/tech/newq.png

I was happy with this because it fixed all of the problems I mentioned above, 
and the
result is generally smoother.

Then I adjusted the weightings to match the W3C's recommended weightings listed
above, and this seemed to produce the best of all results.

http://img.photobucket.com/albums/v449/neota/tech/newq2.png

Finally, I used GIMP to perform a similar conversion. It seemed to produce more
accurate overall colorfulness with less smoothness than Grafx2. In particular, 
the
green buds at the back left were much closer to original coloring in the GIMP 
version.

http://img.photobucket.com/albums/v449/neota/tech/gimpq.png

If you load the modified source image into GIMP and drop newq2, newq, and oldq 
onto
the layers dialog, you can toggle layer visibility to see the difference 
between them.

Original comment by 00a...@gmail.com on 3 Nov 2009 at 1:13

Attachments:

• use_linear_rgb.diff

[GoogleCodeExporter]

BTW, I'm still not sure whether L should work the way it currently does in my 
patch.
It might be overall most useful to have H and S calculated linearly, and L 
according
to the previous (non-linear) values. Can that even be done sensibly?
I'd appreciate any feedback about the way L works with this patch.

Original comment by 00a...@gmail.com on 3 Nov 2009 at 12:51

[GoogleCodeExporter]

actuallt i'm not sure we want the hsl convert functions to be changed, they are 
used
in the paletrte screen and we want the conversion to be lossless. And it's only 
used
for display on this screen and selecting colors with visual feedback.

Original comment by pulkoma...@gmail.com on 3 Nov 2009 at 12:57

[GoogleCodeExporter]

that's a shame, S channel behaved much more sensibly (and H channel a bit more
sensibly) using linear RGB.

Here's a patch without the HSL changes.

Original comment by 00a...@gmail.com on 3 Nov 2009 at 10:09

Attachments:

• use_linear_rgb2.diff

[GoogleCodeExporter]

Mh... actually this patch does not seem to work on our usual testfile, 
marbles.pcx.
I don't know why but I only get 33 used colors when loading this one.

Get it here for trying : http://grafx2.googlecode.com/svn/branches/pic-samples/
MARBLES.PCX

btw, as you made a good number of useful patches, i'm considering giving you 
commit 
access if Yves agrees (and you're ok with that). Tell me if you want so :)

Original comment by pulkoma...@gmail.com on 3 Nov 2009 at 10:35

[GoogleCodeExporter]

I have no problem with it, and you two know much more than me about color 
theory, so
I'll safely stay outside of discussion :) I can't even provide reliable 
feedback on
results, I'm colorblind.

Original comment by yrizoud on 3 Nov 2009 at 11:58

[GoogleCodeExporter]

Yes.. I can reproduce this (and with other images, too -- it's not just '32 
colors').
It looks like in certain circumstances, some hues are left out entirely (erased 
from
the color table). Sometimes it can also pick appropriate colors to approximate 
the
image, but less colors than would make it nice and smooth.
I suspect I need to adjust the cluster-splitting code.

BTW -- Cluster_compute_hue() seems to depend on the meaning of RGB_to_HSL() 
being
consistent with the way 'c->plus_large' is decided. Otherwise it crashes on many
images (thus the patch with HSL included currently works better)
This could be resolved by adding a parameter to RGB_to_HSL and HSL_to_RGB to 
control
whether the HSL values are based on linear or nonlinear RGB.

Note that there are still images I can crash grafx2 by loading with the patch
including HSL (again, in Cluster_compute_hue, c->occurences is sometimes 0 and 
causes
a SIGFPE), so clearly this patch needs some work.

If I get this patch working fully, I'd feel worthy to have commit access (so
obviously I want to and I'd really appreciate it, just I'm not sure I should 
until
I've done this)

Original comment by 00a...@gmail.com on 4 Nov 2009 at 12:42

[GoogleCodeExporter]

c->occurences should never be 0, as you split on the longest axis and this one 
is
always at least 2 values. But well :)

Original comment by pulkoma...@gmail.com on 4 Nov 2009 at 7:15