Code Poetry
and Text Adventures

by catid posted (>30 days ago) 5:21am Sat. Mar 16th 2013 PDT
I am stunned sometimes that brilliant papers go unnoticed.

"In the author's opinion there is a missing piece that would be of use
in many real world situation: there is no practical algorithm, i.e. fast and
with compression ratios comparable to JPEG2000 or JPEG-LS, that aims
to optimize the decompression time."

In other words perhaps the #1 most performed activity in the world on cellphones: Viewing lossless images.  Is not a solved problem.  And is in fact far from solved.

http://www.dsi.unifi.it/DRIIA/RaccoltaTesi/Brocchi.pdf

Really excited about BCIF and where it can be taken with a small amount of work to add alpha channel encoded with RLE and Golomb codes.

Image compression gets the space geeks interested too.  Read through here for some feedback from a guy who worked on the cameras for the two Mars Exploration Rovers from 2004:

http://compgroups.net/comp.compression/new-lossless-image-compression-algorithm/1320823

Read through all the code for BCIF and realized there's a lot of room for improvement.

It uses a very simplistic Huffman decoder.  Huffman decoders were PERFECTED in the paper referenced here in 1997:
http://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffman-paper.html

And CBloom demonstrates that the best implementation is unrolled comparison against tabular values (from the paper).  This is ridiculously fast.

But, you can do better.  Falling through a lot of if statements is slow, so encoding ahead of time makes this happen rarely.  And you can get better compression by using arithmetic encoding sparingly where it barely affects performance.

Of course someone really bright (who works at Valve) has slogged through all this already and written something amazing:

http://code.google.com/p/lzham/

This guy is a fucking genius.  He's smashed LZMA-like code performance into a decoder that runs faster than most naive static Huffman decoders out there.

BCIF has a brilliant context model for calculating entropy for RGB data, and LZHAM has a brilliantly fast entropy decoder.

For alpha channel I think we'd use some special encoding since it's basically 1 bit of data per pixel for most cases.  And it's heavily correlated with RGB=0.  In fact a modified sprite image encoder would probably use 1-bit alpha as a starting point, and then modify the RGB context model to prefer zeroes heavily in transparent parts.  That would lead to better overall compression I think.

LZHAM is pretty overkill for what I want to do.  Really I just want to implement a fast prefix decoder.  I could probably grab the encoder from LZHAM to make that part easier, but making the decoder fast is the main thing.


Edited edit:

I came up with a simple improvement on PCIF that won't change runtime.

It currently splits images into bitplanes.  So 24-bit images = 24 bitplanes.  And it has a preprocessing step where each intermediate pixel value is the result of subtracting its neighbors in certain ways.

Since neighboring pixels are assumed to only be a little different, probably following a geometric distribution (which is what JPEG-LS assumes), it's better to encode these intermediate pixel values as GRAY CODES.  So neighboring intermediate pixels {3, 4} just flip ONE bit across all the bitplanes rather than flipping THREE.  This could potentially greatly improve the compression.

However PCIF isn't that interesting; more interested in BCIF since it performs much better.
last edit by catid edited (>30 days ago) 6:37pm Sun. Mar 17th 2013 PDT