Code Poetry
and Text Adventures

by catid posted (>30 days ago) 3:52pm Tue. May 7th 2013 PDT
Choosing the palette index for each of the <= 256 colors is essential for producing good compression results using a PNG-like filter-based approach.

Palette index assignment does not affect LZ or mask results, nor does it offer any direct improvement in entropy encoding.

However, when neighboring pixels have similar values, the filters are more effective at predicting them, which increases the number of post-filter zero pixels and reduces overall entropy.

A simple approximation to good choices is to just sort by luminance, so the brighest pixels get the highest palette index.  However you can do better.

Since this is designed to improve filter effectiveness, the criterion for a good palette selection is based on how close each pixel index is to its up, up-left, left, and up-right neighbor pixel indices.  Those positions are called the pixel's "filter zone."

The algorithm is:
(1) Assign each palette index by popularity, most popular gets index 0.
(2) From palette index 1:
*** (1) Score each color by how often palette index 0 appears in filter zone.
*** (2) Add in how often the color appears in index 0's filter zone.
*** (3) Choose the one that scores highest to be index 1.
(3) For palette index 2+, score by filter zone closeness for index 0 and 1.
(4) After index 8, it cares about closeness to the last 8 indices only.

The closeness to the last index is more important than earlier indices, so those are scored higher.

I also realized today that this is applicable to more than just index-mode images that are using color palettes.  In fact, thanks to the recent introduction of recursive monochrome compression, every time it is applied, palette sorting is an interesting preprocessing step.