Code Poetry
and Text Adventures

by catid posted (>30 days ago) 2:28am Sat. Apr 20th 2013 PDT
The image compression project is coming along.  It's been about a month since I started working on it, and I've decided it's time to get the decoder finished.

This week I refactored and otherwise improved the Huffman table compression significantly, so re-zipping the output files no longer reduces the file size.  That's a good quick test to see if an image compression scheme is decent.

Here's what the decoder can do as of 2:00 AM this morning:

What's left is:

1) Getting the decoder working on all of my test images.

2) Benchmarking and seeing where it's at right now.

3) Profiling and optimizing the decoder for better performance.  Tuning table sizes for speed.

4) Investigating files it fails to compress as well as PNG.  Why?  These seem to be smaller graphics where our overhead is proportionally higher, or ones where post-filter data can be submitted to LZ and we don't do that..

5) Coming up with alternative compression schemes that do better than PNG on these files and incorporating them as alternate modes I can switch on where they are applicable.

Future improvements

In the order I want to try them:

+ Experiment more with recent color palettes.  These seemed to have promise and may work better than global post-filter palettes.  It may make sense to use a hash table instead of pixel-offset, since the pixel offset is somewhat uniformly distributed and does not compress well.  The hash table approach is unfortunately a burden on the decompressor.  In that case the table index is sort of like an adaptive global color palette, so... [EDIT : This didn't help.]

+ Experiment with a global post-filter color palette.  I suspect this would be a win sometimes, where multiple YUVA channels contain the same expensive values repeatedly.  The advantage would be that just one or two channels would carry extra escape symbols, and the rest could mainly be doing zRLE.  Since these post-filter YUVA colors are popular they'd necessarily have short codes and should be good for compression ratio. [EDIT : This didn't help.]

+ Experiment with MRP-style fitted spatial filters that are designed for the image (pick and ship the top X custom predictors).  Mix in the good static filters for speed.  MRP also goes way beyond distance-1 pixels to find filters to apply, and so does CALIC.  It would be a good idea to experiment more with these sorts of filters, see which ones perform well, and find ways to incorporate them as a set of static functions that can decode as fast as the static filters.  For example, polymorphic code is possible on Android, and it would be a two-day project to generate a few lines of machine code at runtime for these filters since I only care about ARM. [EDIT : This helped a little, about ~3KB for ~911KB files.]

EDIT : The rest I haven't tried yet:

+ For images where a global palette can be applied (<=256 colors), do that, and then rock it with a grayscale compressor.  The grayscale compressor would be just like the RGBA one except it would sort the palette colors to maximize the image smoothness, and then apply spatial filters and do entropy encoding on a single channel.  This would be a huge win for decompression speed and compression ratio where it can be applied.

+ Scanline LZ.  During encoding, check for original data repeated matches, post-spatial-filter repeated matches, and post-filtering repeated matches.  Investigate if this would gain us better performance.  Right now we only do 2D-LZ, which only works on ~4x4 blocks of pixels.  Scanline LZ would be more like what WebP and PNG do, where they look at the pixel data as 1D and push matches from that data.  The zRLE of the entropy encoder tends to compress well-predicted pixels ridiculously well, so it would have to be a pretty big repetition to be worthwhile.  The encoder would have to run both and see which is smaller or use a good heuristic.  It's worth looking into since it would be fast to decode.

+ Scanline filters.  This builds on scanline LZ.  During encoding, try running a whole set of 4 scanlines through the same two filters and optimize filter selection jointly with LZ compression.  This is basically an improved PNG mode that targets exactly those cases where PNG-style compression can take advantage of computer-generated graphics with less overhead than our methods.

+ Expose a lot of the heuristic knobs of the compressor at the API and command-line level so that the spriter can try to optimize the compressor a bit more in unexpected ways.

+ A new spriter that writes GCIF files.  Our current spriter has a lot of flaws, and doesn't take advantage of rotation for better fits, which is free with OpenGL native graphics.  Furthermore the spriter performance can be greatly improved using a better algorithm for landing new pieces and assuming a certain number of sheets for more placement options.  This would be a big win on top of the GCIF compression to give even smaller file sizes, and is a logical next step.
last edit by catid edited (>30 days ago) 6:58pm Mon. Apr 22nd 2013 PDT