Opened 5 years ago

Closed 2 years ago

#26 closed defect (fixed)

Color quantization issue

Reported by: yrizoud Owned by: Adrien Destugues
Priority: minor Milestone: 2.5
Component: GrafX2 Version: 2.5
Keywords: Cc:

Description

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?

Attachments (7)

avengers.jpg (72.8 KB) - added by yrizoud 5 years ago.
avengers.gif (165.4 KB) - added by yrizoud 5 years ago.
Image after loading in Grafx2
avengers_test.gif (133.3 KB) - added by Thomas Bernard 2 years ago.
avengers.jpg loaded with the new splitting
avengers_popsplit_volumesort.gif (165.4 KB) - added by Thomas Bernard 2 years ago.
Cluster Split by population, sort by volume
avengers_popsplit_diagsort.gif (183.9 KB) - added by Thomas Bernard 2 years ago.
Cluster Split by population, sort by diagonal length
avengers_volsplit_diagsort.gif (133.1 KB) - added by Thomas Bernard 2 years ago.
Cluster Split by Volume, sort by diagonal length
avengers_volsplit_volumesort.gif (133.3 KB) - added by Thomas Bernard 2 years ago.
Cluster Split by Volume, sort by volume

Download all attachments as: .zip

Change History (17)

Changed 5 years ago by yrizoud

Attachment: avengers.jpg added

Changed 5 years ago by yrizoud

Attachment: avengers.gif added

Image after loading in Grafx2

comment:1 Changed 2 years ago by Thomas Bernard

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

comment:2 Changed 2 years ago by 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.

comment:3 Changed 2 years ago by 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

Changed 2 years ago by Thomas Bernard

Attachment: avengers_test.gif added

avengers.jpg loaded with the new splitting

comment:4 Changed 2 years ago by Thomas Bernard

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

comment:5 Changed 2 years ago by 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 !!!

Changed 2 years ago by Thomas Bernard

Cluster Split by population, sort by volume

Changed 2 years ago by Thomas Bernard

Cluster Split by population, sort by diagonal length

Changed 2 years ago by Thomas Bernard

Cluster Split by Volume, sort by diagonal length

Changed 2 years ago by Thomas Bernard

Cluster Split by Volume, sort by volume

comment:6 Changed 2 years ago by Thomas Bernard

Please choose which quantized image you prefer ;)

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

comment:7 Changed 2 years ago by 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.

comment:8 Changed 2 years ago by 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 ;)

comment:10 Changed 2 years ago by Thomas Bernard

Milestone: 2.5
Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.