GIF: _get_optimize() missed opportunities

[raygard]

What did you do?

Copied a GIF using a recent 9.2.0dev0 build:

from PIL import Image
with Image.open('stripes.gif') as im:
    im.save('out.gif', save_all=True, optimize=True, disposal=1)

What did you expect to happen?

The output file would have optimized local color tables.

What actually happened?

All the local color tables had 256 colors where 8 colors would suffice.

What are your OS, Python and Pillow versions?

• OS: Windows 10 Pro
• Python: 3.10.4
• Pillow: 9.2.0dev0

Discussion

stripes.gif is similar in every way that matters to the aniship.gif image I used in issue #6260. I created it so it could be freely distributed as desired. I realize it's unusual. It has no GCT and the LCT is the same on every frame. But aniship.gif was found "in the wild" so stripes.gif not an entirely artificial example.

In GifImagePlugin.py, _get_optimize() uses certain criteria to decide if the palette is worth trying to optimize (remapping to only the used colors). The optimization is done only if the image is smaller than 262144 pixels, there are no more than 128 used colors, and there are "holes" in the palette, the latter being the case if max(used_palette_colors) > len(used_palette_colors).

I think the "holes" test should be max(used_palette_colors) >= len(used_palette_colors), as e.g. [1, 2, 3, 4, 5] has a hole at the bottom and [0, 1, 2, 4, 5] has a hole in the middle, but would be seen now as having no hole.

But I'm not clear on the point regarding holes. I would think the condition for optimizing would be if the palette actually got smaller. The number of colors in the current palette would (I think) be a power of two, so you would want to check if the new (used colors) palette is not more than half the size of the current palette. I'm sure I must be missing something here, but how about getting the current number of colors and testing if the number of colors used is not more than half of that. For example:

            num_palette_colors = len(im.palette.palette) // 4 if len(im.palette.palette) % 3 else len(im.palette.palette) // 3
            if optimise or (
                len(used_palette_colors) <= 128
                and (max(used_palette_colors) >= len(used_palette_colors)
                or len(used_palette_colors) <= num_palette_colors // 2)
            ):

This assumes that im.palette.palette exists, is not None and is actually a byte string or array of RGB or RGBA colors. If its length is not a multiple of 3 I assume it's RGBA because they would always be a multiple of 4 in size. Are these valid assumptions? If not, is there something we can do along these lines?

Would this also obviate the need for len(used_palette_colors) <= 128?

With this change to _get_optimize(), The out.gif is reduced from 36653 bytes to 22517 bytes.

If this change is worth pursuing and my logic is close to correct, I can create a PR for this. What have I missed?

[radarhere]

im.palette.mode will tell you whether the palette is RGB or RGBA (% 3 will not, because there may be 3 RGBA entries).

It would remove the need for len(used_palette_colors) <= 128, yes.

Your thinking sounds essentially correct to me, so feel free to create a PR.

[raygard]

there may be 3 RGBA entries

So the number of colors in a RGBA palette may be not a power of 2? Can the number of colors in a RGB palette be other than a power of 2? At least at the point where _get_optimize() is used?
If so, I think I may have to rework this. Maybe round up the number of colors to a power of 2 then divide by 2 before comparing with used_palette_colors?

[radarhere]

If nothing else, a palette might be modified by Python code. So yes, it can contain any number of colors.