Code Poetry
and Text Adventures

by catid posted (>30 days ago) 2:37am Wed. Apr 3rd 2013 PDT
http://www.eurasip.org/Proceedings/Eusipco/Eusipco2012/Conference/papers/1569551007.pdf

This is a recent paper surveying efficient color filters.  Figure 4 is amazing.

It's definitely the best work I've been able to find on the topic and is exactly what I needed to know to decide the best color filters to apply to each 4x4 pixel zone.

Right now I'm using the same color filters used by JPEG-LS and PNG.  It's not really informed by anything.

There are about 20 color filters that are really good they describe in the paper, and having lots of good choices will definitely improve compression.

Color filtering will split the RGB data into luminance and 2 chrominance channels, where the luminance takes 8 bits and chrominance x2 take 9 bits.

Here's an example simple entropy comparison I ran earlier today:

Entropy RGB = 0.389058, 0.380056, 0.344691
Entropy YCoCg-R = 0.37669, 0.370847, 0.189332

When the RGB data is transformed a lot of bias is removed from the pixel data, the resulting data tends to have lower entropy.  This results mainly from the value distribution clustering more closely around zero for each color plane.


What I realized today is that these color filters are linear and the spatial filters that I apply to the RGB pixels are also linear (the same operation is applied to each color).  So it doesn't matter too much if I apply them before or after spatial filtering.  Since these filters expand the RGB888 data into YUV899, it makes more sense to do the spatial filtering first on RGB, and then do the YUV899 conversion afterwards.  The paper gave me a bunch of filters to try out on each block of data that should do better than the BCIF filters.

This means that in memory I can store the pixel data as RGB on the encoder, and convert to YUV899 right before encoding.  More importantly on the decoder, I can decode the huffman symbols into YUV899 in registers/stack, and unfilter back to the original RGB data before writing to the output memory on the heap.

So the fact that I use more than 8 bits per pixel should not really affect performance!


I implemented the color filters they indicated were the best in their testing, plus a few more for flavor, and the no-transform RGB version.

Here's the results on a test game spritesheet:

Entropy YUV(0) = { 0.37669, 0.312127, 0.177633 } : SCORE=0.866449 (Best: YUVr)
Entropy YUV(1) = { 0.364799, 0.36508, 0.177633 } : SCORE=0.907511
Entropy YUV(2) = { 0.364799, 0.355749, 0.177633 } : SCORE=0.89818
Entropy YUV(3) = { 0.364799, 0.240536, 0.312127 } : SCORE=0.917461
Entropy YUV(4) = { 0.389058, 0.36508, 0.177633 } : SCORE=0.931771
Entropy YUV(5) = { 0.389058, 0.355749, 0.177633 } : SCORE=0.92244
Entropy YUV(6) = { 0.389058, 0.189363, 0.404008 } : SCORE=0.982429
Entropy YUV(7) = { 0.344691, 0.228122, 0.404008 } : SCORE=0.97682
Entropy YUV(8) = { 0.344691, 0.189363, 0.404008 } : SCORE=0.938061
Entropy YUV(9) = { 0.344691, 0.158715, 0.404008 } : SCORE=0.907413
Entropy YUV(10) = { 0.344691, 0.240536, 0.312127 } : SCORE=0.897353
Entropy YUV(11) = { 0.37669, 0.404008, 0.189363 } : SCORE=0.97006
Entropy YUV(12) = { 0.380056, 0.312127, 0.177633 } : SCORE=0.869816
Entropy YUV(13) = { 0.38252, 0.312127, 0.177633 } : SCORE=0.872279
Entropy YUV(14) = { 0.38252, 0.312127, 0.177633 } : SCORE=0.872279 (LOCO-I / BCIF)
Entropy YUV(15) = { 0.380056, 0.344691, 0.389058 } : SCORE=1.11381 (RGB)
Entropy YUV(16) = { 0.344691, 0.36508, 0.177633 } : SCORE=0.887403
Entropy YUV(17) = { 0.364799, 0.254104, 0.312127 } : SCORE=0.931029
Entropy YUV(18) = { 0.390674, 0.36508, 0.177633 } : SCORE=0.933386
Entropy YUV(19) = { 0.3912, 0.189363, 0.404008 } : SCORE=0.984571
Entropy YUV(20) = { 0.38252, 0.355749, 0.177633 } : SCORE=0.915902
Entropy YUV(21) = { 0.38252, 0.240536, 0.312127 } : SCORE=0.935182


So it's clear that while BCIF's prize filter from LOCO-I does a pretty good job, there are better filters for this image.  And the exciting note is that since all of these filters are YUV899, the color filter can switch from block to block.  This means that image color features that do not reflect the overall image color scheme can be normalized out by applying a color filter that reduces its impact on overall entropy.

This is something new that hasn't been done before in an image codec to my knowledge, and I'm excited to try it out soon!

One thing the paper author may not have noticed is that, in at least all of the color transforms I've played with, you don't really need 9 bits for chroma channels.  Aliasing them into 8 bits is reversible too.  The advantage is lower entropy as a result.  Since the color filtering occurs right before entropy coding this would be ideal.  I'm going to do some testing to see if all of the filters are reversible when they're aliased.  And if so, I'm going to decide what type of aliasing is best.  Aliasing over zero would be ideal to improve code performance.

Even if aliasing works in just a few cases, the results are exceptional for entropy improvement.  Compare these results with above:

Entropy YUV(0) = { 0.37669, 0.311642, 0.162714 } : SCORE=0.851046 (Even better!  But see below...)
Entropy YUV(1) = { 0.364799, 0.34218, 0.162714 } : SCORE=0.869692
Entropy YUV(2) = { 0.364799, 0.353814, 0.162714 } : SCORE=0.881326
Entropy YUV(3) = { 0.364799, 0.215519, 0.311642 } : SCORE=0.89196
Entropy YUV(4) = { 0.389058, 0.34218, 0.162714 } : SCORE=0.893952
Entropy YUV(5) = { 0.389058, 0.353814, 0.162714 } : SCORE=0.905586
Entropy YUV(6) = { 0.389058, 0.189332, 0.370847 } : SCORE=0.949237
Entropy YUV(7) = { 0.344691, 0.228077, 0.370847 } : SCORE=0.943614
Entropy YUV(8) = { 0.344691, 0.189332, 0.370847 } : SCORE=0.904869
Entropy YUV(9) = { 0.344691, 0.157806, 0.370847 } : SCORE=0.873343
Entropy YUV(10) = { 0.344691, 0.215519, 0.311642 } : SCORE=0.871852
Entropy YUV(11) = { 0.37669, 0.370847, 0.189332 } : SCORE=0.936868
Entropy YUV(12) = { 0.38252, 0.311642, 0.162714 } : SCORE=0.856876
Entropy YUV(13) = { 0.380056, 0.311642, 0.162714 } : SCORE=0.854413
Entropy YUV(14) = { 0.380056, 0.344691, 0.389058 } : SCORE=1.11381
Entropy YUV(15) = { 0.344691, 0.34218, 0.162714 } : SCORE=0.849584 (New champion!  This is C7 from the Strutz paper)
Entropy YUV(16) = { 0.364799, 0.228256, 0.311642 } : SCORE=0.904696
Entropy YUV(17) = { 0.390674, 0.34218, 0.162714 } : SCORE=0.895567
Entropy YUV(18) = { 0.3912, 0.189332, 0.370847 } : SCORE=0.951379
Entropy YUV(19) = { 0.38252, 0.353814, 0.162714 } : SCORE=0.899048
Entropy YUV(20) = { 0.38252, 0.215519, 0.311642 } : SCORE=0.909681

It may be that C7 isn't reversible under aliasing and that's why it does better.  We'll see tomorrow I guess.
last edit by catid edited (>30 days ago) 3:21am Wed. Apr 3rd 2013 PDT