Code Poetry
and Text Adventures

by catid posted (>30 days ago) 4:55pm Thu. May 2nd 2013 PDT
Through working on compressing 2D RGBA data I've noticed a few parts of the data are effectively monochrome data:
(1) Which color filter to use for each SF/CF filter zone.
(2) Which spatial filter to use for each SF/CF filter zone.
(3) Palette mode encoding.
(4) The alpha channel encoding.
(5) Which alpha filter to use for each alpha filter zone. (new)

What I realized while working more on adding better alpha channel filtering is that it would make a lot of sense to do it recursively.  And that made me step back.  This could be an encoding that recursively produces subresolution monochrome images that are then recompressed!  Any of the modeling that can be done for one of these monochrome data streams may be applicable to any of the others!

Exciting!

I've already got a pretty flexible entropy encoder that can do zero-run-length-encoding (zRLE) and order-1 modeling for after-zero symbols, but will also turn these features off if a basic Huffman coder makes more sense.  And the Huffman tables are compressed effectively regardless of the input.  So I can use this same entropy encoder for just about everything now, and it enables me to decide between filter choices just purely using entropy comparison.

class MonochromeFilter

The new MonochromeFilter class is going to combine all of the tricks I've picked up:

(0) Select a power-of-two ZxZ zone size, starting with twice the size of the parent zone.


(1) Mask Filters

Provide a delegate that we can call per x,y pixel to check if the data is masked or not, and note that a filter tile is part of masked data so it can be skipped over tile-wise for the rest of the decision process.


(2) Spatial Filters

There will be a whole bunch of spatial filters that are complex, as well as a large set of tapped linear filters to swap in where it makes sense.  The filters will be listed in order of complexity, with most complex filters are the bottom.

+ "No modification". (degenerate linear tapped) [ALWAYS AVAILABLE]
+ "Same as A, B, C, D". (degenerate linear tapped) [ALWAYS AVAILABLE]
+ About 80 linear tapped filters that seem to do well.
+ All of the ones involving if-statements from the current codebase, plus more.  (At the bottom of preference list).
+ Whole zone is value "X". [Special encoding that requires a byte to be emitted]

All of the filters will be tried against the input in ZxZ zones, and the top 4 matches will be awarded + REWARD[0..3].  Scored by L1 norm for speed.

After this process, the filters that are scored above REWARD[0] * ZONE_COUNT * THRESHOLD_PERCENT are taken, up to MAX_FILTERS.  Some of the filters are always chosen regardless of how well they do and are just included in the measurement to avoid rewarding other filters unnecessarily.

Pixels are passed to the mask delegate to see if they are considered or not.


(3) Filter selection

Use entropy analysis to decide which filter to select for each tile, starting in the upper left, to lower right.  After working over the whole 2D data, loop back to the front for 4096 iterations to allow the entropy histogram to stabilize and tune tighter.


(4) Filter the filters

For each filter row, select a 2-bit code meaning:

00 "FF[n] = f[n]"
01 "FF[n] = f[n] - f[n - 1], or 0"
10 "FF[n] = f[n] - f[n - width], or 0"
11 "FF[n] = f[n] - f[n - width - 1], or 0"

Loop over the whole image twice, minimizing entropy of the FF[n] data.


(5) Recursively compress the FF[n] data.

Create a new instance of the MonochromeFilter to compress the resulting FF[n] data.


(6) Determine the best number of chaos levels to use for the data

Try out 16 order-1 chaos levels and work down to 1 (disabled) to encode the data; pick the level that works best.


(7) Calculate the number of bits required to encode the data in this way

And loop back to step 0 to see if increasing Z helps.  Stop on the first one that makes it worse.


Decoding

Read and initialize the filters.

Decoding the original data proceeds per scan-line.

On lines that have (y & (Z-1) == 0), we check to see if FILTERS[x >> Z_BITS] is NULL.  If so, we expect the writer to have written out the filter selection.  We recursively call MonochromeFilter filter reading code, which will have its own FILTERS[] sub-array.  Until eventually it's just directly read in.
last edit by catid edited (>30 days ago) 6:28pm Thu. May 2nd 2013 PDT