Color quantization issue

[yrizoud]

The attaached image doesn't convert well to 256 color when loaded in Grafx2 : Some very red parts get mapped to color 0 (near-black)

Reported by DawnBringer

[yrizoud]

Image after loading in Grafx2

[Thomas Bernard]

Maybe that had to do with the color model used during quantization.

[Thomas Bernard]

OK color quantization is done in RGB space by clustering on the volume...
distances in RGB space are far from what human eye perceive, so the palette is far from optimal.

I think we cannot get better result without switching to a better algorithm.

[Thomas Bernard]

Hum I get far better result on your avengers.jpg image with a change in the Cluster splitting algorithm.
see ​https://gitlab.com/miniupnp/grafX2/commits/quantize
​https://gitlab.com/miniupnp/grafX2/commit/9ec4adae808a0dc09823ee5934fc7f4ad3fcb72b

Please test and tell me

[Thomas Bernard]

avengers.jpg loaded with the new splitting

[Thomas Bernard]

for further improvement we could use ​https://github.com/ImageOptim/libimagequant which is GPLv3

[Thomas Bernard]

I was wrong. I think I can improve the current code.
Cluster are now sorted by volume (Rrange * Grange * Brange) of the "color cube".
It would be better to sort by maximum distance between 2 colors inside the pointer, that is the length of the diagonal of the "color cube".

For example let take 2 cluster :
A) with 2 colors black (0, 0, 0) and red (255, 0, 0) => volume is 256
B) with 2 colors (255,255,255) (248,248,248) => volume is 8*8*8 = 512

The current algorithm will split B first whereas the 2 light grey colors are far closer than red and black !!!

[Thomas Bernard]

Cluster Split by population, sort by volume

[Thomas Bernard]

Cluster Split by population, sort by diagonal length

[Thomas Bernard]

Cluster Split by Volume, sort by diagonal length

[Thomas Bernard]

Cluster Split by Volume, sort by volume

[Thomas Bernard]

Please choose which quantized image you prefer ;)

see ​https://gitlab.com/GrafX2/grafX2/merge_requests/8

[PulkoMandy]

I think keeping the population split makes sense. The idea (and this is where the algorithm gets its "median cut" name) is to have more colors allocated when there are a lot of pixels using similar colors. However, it may not make sense to always go with that. Old versions of GrafX2 first reduced the colors to 18 bits (3*6) instead of 24 (3*8) and as a result there were much less different colors to start with.

By just splitting in the middle, we ignore that information from the image.

Picking the cluster with the longest diagonal makes sense, however. So popsplit_diagsort would be my favorite way. It seems to give better results (the red shades in the background are preserved, and the shadow above the title does not become red).

Maybe we should test with more pictures (I think we had another test file in an older issue?), and maybe we should implement several variants and allow the user to test them when loading an image, because different images may need different algorithms.

[Thomas Bernard]

there is MARBLES.PCX in the pic-sample repository

indeed we could add a switch for the user to choose the algorithm during loading.
But I think you're right, popsplit_diagsort is probably the better

By the way, I've also fixed Optimize_palette() for precisions different than 8 8 8
I'm pushing this soon (in another branch)
so we can test with lower bit per color component and make it work without eating 64MB+ of RAM ;)

[Thomas Bernard]

see ​https://gitlab.com/miniupnp/grafX2/tree/quantize_fix