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

[GoogleCodeExporter]

@Yves: actually I was asking you about giving commit access to 00ai99 :)

Original comment by pulkoma...@gmail.com on 4 Nov 2009 at 12:09

[GoogleCodeExporter]

Access granted. Whenever you are content with your change, you can commit it. 
(in /trunk)

Original comment by yrizoud on 4 Nov 2009 at 12:55

[GoogleCodeExporter]

Original comment by pulkoma...@gmail.com on 22 Aug 2010 at 1:34

• Added labels: Milestone-2.4

[GoogleCodeExporter]

I had another look at the code, and noticed the matching of RGB to palette 
entries was not done in full precision. Going to replace the conversion table 
with an octree that should waste less memory and get us more precision. In 
theory it should be slower but I suspect smaller data fitting in the cache will 
actually help... Working with 16MB+ tables is not a good idea :)

Original comment by pulkoma...@gmail.com on 16 Nov 2011 at 9:56

[GoogleCodeExporter]

fixed in r1878.

Original comment by pulkoma...@gmail.com on 28 Nov 2011 at 10:31

[GoogleCodeExporter]

1878 crashes everytime I try to load a jpeg...is there anhything else needed 
than the stuff in /bin?

Original comment by annas...@hotmail.com on 2 Dec 2011 at 9:57

[GoogleCodeExporter]

Shouldn't need anything else.
Is it one particular picture or all of them ?
The pic from #441 loads fine for me...

Original comment by pulkoma...@gmail.com on 2 Dec 2011 at 6:26

[GoogleCodeExporter]

On an XP machine (with dev environment) about every jpg crashes.
At home on debugger I can only crash if I load several images one after the 
other, it's random. Crashes with "Program exited with code 037777777777", gdb 
doesn't catch anything even with a breakpoint on exit() and abort() :( Will try 
on another machine...

Original comment by yrizoud on 2 Dec 2011 at 8:01

[GoogleCodeExporter]

Ok, I see the crash on windows too.
It also happens with the fast preview in the load window, so I'm not sure my 
code is at fault ? Should help locating the problem.

Anyway, gdb never was too helpful for me in Windows... will see what I can 
get...

Original comment by pulkoma...@gmail.com on 30 Dec 2011 at 7:24

[GoogleCodeExporter]

Bug should be solved now.

Original comment by pulkoma...@gmail.com on 31 Dec 2011 at 1:31

• Changed state: Fixed

[GoogleCodeExporter]

Ok, I took a quick look at 1883. 24bit loading works and the palette reduction 
is an improvement from before, but it's still far from perfect or as good as 
Photoshop.

* Some images will bug-out and produce very odd results (maybe it's just PNG), 
try this spectrum image.

* Some images will be converted badly, with a huge priority for grays. See 
rgb-grey image.

* Some images will have some color mapped completely wrong, I've seen white 
mapped to black (jpeg)

* Some images may still crash the program. Test the blue-red range image.

* There's some odd jibberish on the statusbar when running scripts now. (just 
in case it's related to these changes)

Original comment by annas...@hotmail.com on 1 Jan 2012 at 12:21

Attachments:

• canvas.png
• rgb-grey.png
• range_Blue2Red.png
• jibberish.png

[GoogleCodeExporter]

The crash is because somehow an entirely black palette is generated (!!?)
The jibberish seems unrelated... no idea where it comes from...

Original comment by pulkoma...@gmail.com on 1 Jan 2012 at 10:48

• Changed state: Started

[GoogleCodeExporter]

Good catch, there was a bug left in the code. These pictures now give better 
results.

Original comment by pulkoma...@gmail.com on 1 Jan 2012 at 12:14

[GoogleCodeExporter]

I think it's fixed for good.

Original comment by pulkoma...@gmail.com on 1 Jan 2012 at 12:55

• Changed state: Fixed

[GoogleCodeExporter]

Yes, the big bugs are fixed. But the quality still isn't great (far below all 
of Photoshops 256-color reduction modes). Some images produce a large number of 
similar colors in some registers but very few in others (very apparent gaps). 
Typically you can reduce a converted image to 128 colors without any further 
noticable loss (meaning there's a mass of colors that could have been put to 
better use). Not sure what causes this, but it's apparent Grafx2 doesn't use 
perceptual colorspace (many colors in blue f.ex.). Colorregister seem to 
line-up in brightness rather than having (useful) overlapping as common in 
Photoshop conversions...I would expect Median Cut to handle this, isn't that 
what you're using? There are also instances with mapping artefacts, like a 
color between [119,49,85] & [117,67,118] (avg. Brightness = 76.3) getting 
mapped to grey 111! (Totally wrong, any of the 2 original colors are a superior 
match). You don't weigh in a histogram do you? Not sure if Photoshop does that, 
but it's possible. 

No craches so far with r1889.

Original comment by annas...@hotmail.com on 2 Jan 2012 at 1:52

Attachments:

• BackDropZoom.png
• BackDropZoom_grafx256.png
• BackDropZoom_ps256.png

[GoogleCodeExporter]

"Median cut" is not a complete description of the algorithm.

The conversion is still performed in linear colorspace.
I made some changes in the selection of the cluster to split, before it was the 
one with most pixels inside, now it is the widest one, which makes more sense.

The problem is likely the colorspace...

Original comment by pulkoma...@gmail.com on 2 Jan 2012 at 6:23

[GoogleCodeExporter]

The final colormatching/rendering isn't perceptual is it?

If I render an image in Photoshop in 256 colors and the same image in Grafx2 
and then remap the Photshop-image with the Grafx2 palette, that result can be 
better than the original Grafx2 conversion.

Original comment by annas...@hotmail.com on 13 Jan 2012 at 10:30

[GoogleCodeExporter]

Right, it isn't.
See operatio.c, CS_Generate_color_table_and palete.

Everything is quite tied, since the palette index for one of the 256 clusters 
is used for all colors in the cluster area. So, to switch to perceptual we'd 
have to also change how clusters are made.

The simplest way would be as follows:
 * Convert the initial image to some linear percetual model
 * Operate the conversion as it is now
 * Convert back the generated palette to screen RGB.

However, we're stuck with 8bits per component doing this, and I fear that some 
precision gets lost.

Original comment by pulkoma...@gmail.com on 14 Jan 2012 at 8:42