Code Poetry
and Text Adventures

by catid posted (>30 days ago) 2:25am Sun. Apr 14th 2013 PDT
So I've been exploring using color palettes in specific areas of an image to try to effect compression.

Some images have high complexity in the colors chosen, but there are spatial correlations between the color values.  For instance, a gradient has a lot of color values but a very simple pattern.  This compresses very well with context modeling that does spatial filtering and color filtering followed by entropy encoding.  These tend to be natural images like photographs.

Other types of images have low complexity in colors chosen, but lots of detail.  This is common for video game graphics, where sprites tend to be mostly red or yellow or green etc, but the lines of the drawings are unpredictable and complex.  These types of images also tend to repeat the same image data.

Introducing 2D Local Palette (LP) compression
2D localized palettes are rectangular zones that use a local palette instead of RGB colors.  After encoding, the actual pixel data is only about 20% of the LP information written to the file: It's mainly the zone descriptors that takes up space.  So even simple spatial filters like "same as left pixel" actually hurt compression to include.

The main operation to do compression is finding the zones to encode.  Finding these zones is fast, about the same as 2D-LZ encoding time.  I think it's fast because it only needs to read up to 16 pixels for each image pixel, and often does not even have to read that many.  Once it finds a 4x4 zone that has low color count it will definitely use those pixels and maybe more nearby.

The decoding uses the same trigger mechanism as 2D-LZ so it's blazing fast and integrates easily into the rest of the decoder.  I believe that this and 2D-LZ are both novel ideas for image codecs, since I haven't seen them in the literature..

The pixels that are not covered by LP are compressed with PNG-like spatial and color filters in my codec.

As another aside it's amazing to me that none of this is patent-encumbered.  When I was playing with forward error correction, patents were severely limiting in what I could legally release.  I'm happy to see that image compression doesn't suffer from that stupidity and progress can be made by anyone.

The problems
The problems are that the overhead is somewhat unpredictable and taken as part of a whole image codec actually reduces compression ratio.  Furthermore the overhead to represent the colors in the palette takes a long time to decompress and significantly slows down the decoder.

Recent palette idea
I also had an idea to add 4-8 symbols to the Y channel encoder to cover repeated colors after filtering.  This would be pretty cool: After filtering the YUV data tends to cluster around zero, so there is a lot of repeated data.  Instead of entropy encoding the YUV+A, it would be better to just emit a symbol that means "reuse the value we just saw 4 pixels back".  I expect this type of symbol will get used a lot based on what I've seen looking at a lot of post-filter image data.  This would be a new trick for the CM encoder rather than a giant new feature.

Edit: I tried this out and it didn't seem to help either.  Not sure why.  After the decoder is working I'm going to revisit this and some other ideas.
last edit by catid edited (>30 days ago) 2:24am Sat. Apr 20th 2013 PDT