quantize() to a palette often chooses unideal color matches

[ericpauley]

What did you do?

I am quantizing many images to the same palette and colors are often not picked to be ideal values, instead being mapped to close values when an exact match exists in the palette.

What did you expect to happen?

Colors would be matched to the closest value in the palette or an exact match if one exists.

What actually happened?

Colors are mapped to close values. (Specifically white is mapped to #fcfcfc)

What versions of Pillow and Python are you using?

PILLOW_VERSION = '2.9.0'
VERSION = '1.1.7'
PYTHON = '2.7.10'

Please include code that reproduces the issue and whenever possible, an image that demonstrates the issue. The best reproductions are self-contained scripts with minimal dependencies.

import PIL.Image
ptext = '\xff\xff\xff\xfd\xfd\xfd\xfc\xfc\xfc\xfb\xfb\xfb\xfa\xfa\xfa\xf8\xf8\xf8\xf7\xf7\xf7\xf6\xf6\xf6\xf5\xf5\xf5\xf4\xf4\xf4\xf1\xf1\xf1\xf0\xf0\xf0\xef\xef\xef\xed\xed\xed\xec\xec\xec\xea\xea\xea\xe9\xe9\xe9\xe8\xe8\xe8\xe7\xe7\xe7\xe6\xe6\xe6\xe5\xe5\xe5\xe4\xe4\xe4\xdd\xdd\xdd\xdc\xdc\xdc\xdb\xdb\xdb\xda\xda\xda\xd8\xd8\xd8\xd7\xd7\xd7\xd5\xd5\xd5\xd3\xd3\xd3\xd1\xd1\xd1\xcf\xcf\xcf\xcd\xcd\xcd\xcc\xcc\xcc\xcb\xcb\xcb\xca\xca\xca\xc9\xc9\xc9\xc7\xc7\xc7\xc5\xc5\xc5\xc4\xc4\xc4\xc2\xc2\xc2\xbd\xbd\xbd\xbb\xbb\xbb\xba\xba\xba\xb8\xb8\xb8\xb7\xb7\xb7\xb6\xb6\xb6\xb5\xb5\xb5\xb3\xb3\xb3\xb1\xb1\xb1\xb0\xb0\xb0\xaf\xaf\xaf\xad\xad\xad\xac\xac\xac\xaa\xaa\xaa\xa9\xa9\xa9\xa8\xa8\xa8\xa6\xa6\xa6\xa5\xa5\xa5\xa3\xa3\xa3\xa2\xa2\xa2\xa1\xa1\xa1\xa0\xa0\xa0\x9d\x9d\x9d\x9c\x9c\x9c\x9a\x9a\x9a\x99\x99\x99\x94\x94\x94\x91\x91\x91\x8f\x8f\x8f\x8d\x8d\x8d\x8b\x8b\x8b\x87\x87\x87\x86\x86\x86\x85\x85\x85\x83\x83\x83\x80\x80\x80~~~}}}|||{{{zzzwwwvvvtttsssrrrpppooolllkkkjjjfffeeedddcccbbbaaa```___^^^\\\\\\YYYXXXWWWUUUTTTSSSMMMLLLKKKIIIHHHGGGDDDCCCBBBAAA@@@???>>>===<<<;;;:::666444333222///...---+++***)))\xd8\x08\x00\xd6\x08\x00\xd5\x08\x00\xd4\x08\x00\xd2\x08\x00\xd0\x08\x00\xcc\x08\x00\xcb\x08\x00\xca\x07\x00\xc9\x07\x00\xc8\x07\x00\xc6\x07\x00\xc5\x07\x00\xc4\x07\x00\xc2\x07\x00\xba\x07\x00\xb7\x07\x00\xb6\x07\x00\xaf\x06\x00\xae\x06\x00\xad\x06\x00\xac\x06\x00\xa9\x06\x00\xa0\x06\x00\x9e\x06\x00\x9c\x06\x00\x94\x05\x00\x93\x05\x00\x92\x05\x00\x8c\x05\x00\x8a\x05\x00\x89\x05\x00\x88\x05\x00}\x05\x00y\x04\x00r\x04\x00q\x04\x00o\x04\x00d\x04\x00b\x04\x00a\x04\x00^\x03\x00V\x03\x00U\x03\x00R\x03\x00Q\x03\x00K\x03\x00J\x03\x00H\x03\x00G\x03\x00F\x03\x00A\x02\x00@\x02\x00=\x02\x00<\x02\x00:\x02\x00(((&&&%%%!!!\x1f\x1f\x1f\x1e\x1e\x1e\x1d\x1d\x1d9\x02\x008\x02\x002\x02\x001\x02\x00,\x02\x00+\x02\x00*\x02\x00(\x01\x00$\x01\x00#\x01\x00"\x01\x00\x1f\x01\x00\x1c\x1c\x1c\x1b\x1b\x1b\x1a\x1a\x1a\x19\x19\x19\x18\x18\x18\x17\x17\x17\x15\x15\x15\x14\x14\x14\x11\x11\x11\x10\x10\x10\x0f\x0f\x0f\x0e\x0e\x0e\r\r\r\x0b\x0b\x0b\t\t\t\x08\x08\x08\x19\x01\x00\x16\x01\x00\x07\x07\x07\x06\x06\x06\x05\x05\x05\x04\x04\x04\x03\x03\x03\x02\x02\x02\x01\x01\x01\x0b\x00\x00\x08\x00\x00\x07\x00\x00\x06\x00\x00\x05\x00\x00\x04\x00\x00\x03\x00\x00\x02\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' #Palette is not malicious, similar behavior occurs with white on many palettes.
i = PIL.Image.new('RGB', (1,1),(255,255,255))
p = PIL.Image.new('P',(1,1))
p.putpalette(palette)
p.putpalette(ptext)
i2 = i.quantize(palette=p)
i2.show()

[eevee]

This also happens regardless of the method argument.

[wiredfool]

Pretty sure that this is connected with #1987 (comment)

[radarhere]

I found an undefined variable in the sample code, so I'm providing a version here that is fixed, simpler, and also provides easier inspection of the result.

from PIL import Image
i = Image.new('RGB', (1,1), (255, 255, 255))
p = Image.new('P', (1,1))
i2 = i.quantize(palette=p)
print(i2.convert('RGB').load()[0, 0])  # (252, 252, 252)

[FredHappyface]

I've been having this issue. Are there any workarounds in the meantime?

[sprntgd]

This seems to be caused by lossy caching.

#define ImagingPaletteCache(p, r, g, b) \
    p->cache[(r >> 2) + (g >> 2) * 64 + (b >> 2) * 64 * 64]

Any image passed through this palette cache gets reduced from 8bpc to 6bpc with values being rounded down, hence the change from 255 to 252 in the sample.

Relevant functions for anyone who wants to take a look:

Pillow/src/libImaging/Palette.c

Line 167 in 61b9065

ImagingPaletteCacheUpdate(ImagingPalette palette, int r, int g, int b) {

Pillow/src/libImaging/Convert.c

Line 1255 in 61b9065

topalette(

The way the cache works probably needs completely rethinking to fix this.

[Artoria2e5]

A simple but far-from-optimal way to "fix" the cache would be extending the ImagingPaletteInstance.cache member to a tagged union allowing multiple values. Sparse cells can keep their one-value encoding, while the multi-value ones can just use a linear search -- 64 entries to look through at most. [Ideally the whole cache becomes some proper search tree, but that hurts my head. Ayy, double space use can't be that bad, right?]

(Sorry for the previous message -- I didn't even do a getpalette to check it out.)

---

Alright, I tried this idea out in https://github.com/Artoria2e5/Pillow/tree/cache and I hate it. The biggest problem is the small malloc scattered around -- I initially wanted to put a big, shared "extra palette indices" buffer under ImagingPaletteInstance, using the negative values of INT16 *cache to indicate indices to it. The thing is despite knowing the ideal maximum size (something along the lines of 256 * 8 * 2 entries), repeated calls to ImagingPaletteCacheUpdate will produce a lot of "dead" space, blowing it up quickly. And I would really love to not have to write a terrible arena allocator on top of my terrible nearest-neighbor code. (Yes, l could just skip already-assigned entries because there really shouldn't be anything to update in that case -- but no thanks i'm tired.)

[Ah great, now I am reminding myself that repeated calls will never happen What did I do in the last hour?]

[Solstice245]

Reported in 2016, yet biting my ass all the way in 2024, nice.

[Artoria2e5]

Heck, I don't even remember if my code compiles. It's C.