Colorspace decomposition (episode 2: the big swap)

A project log for 3RGB image lossless compression format

Tiled CODEC for still and moving pictures based on the 3R compaction algorithm

yann-guidon-ygdesYann Guidon / YGDES 06/01/2017 at 01:190 Comments

After having progressed on the other fronts, I return to the colorspace decomposition where I'm now addressing another "low hanging fruit" : that is, some way to gain a bit more space with relatively little effort, and without risk of expansion. I guess the average gain would be in the 10 to 20% range but this depends a lot on the data. This is a small gain but not negligible and the required effort is modest : it's a small permutation based on already known data.

As mentioned before, the 3RGB encoding pipeline breaks the image in 8×8 tiles and the first step is to compute the min and max values of each block, in parallel, for the individual R, G & B components.

Then, the 3 blocks (R,G,B) are transformed to the new colorspace by applying two nested σα transforms. Since we know the min and max values of each block, we can apply the generalised algorithm (see Extension to unequal boundaries) which swaps the operands: the smallest range is output after the sum.

We can go a bit further and pre-swap the block pointers: this simple step takes the swap out of the inner loop, which runs faster.

There are 6 permutations for RGB:

  1. B G R
  2. B R G
  3. G B R
  4. G R B
  5. R B G
  6. R G B

A little bubble sort would be enough but we don't need to go so far : two of the components are reproduced verbatim (at worst) so we just need to find the largest limit and map it to the intermediary sum (which is not directly transmitted)

Another parameter comes into play: the second σα transform applies to the sum of two components, so we could evaluate

  1. B + G
  2. B + R
  3. R + G

but if we already know, for example, that B is the largest value, then B+G > R and B+R > G.

This leaves us with only 3 practical combinations:

  1. σα( σα(B, G), R)
  2. σα( σα(G, R), B)
  3. σα( σα(R, B), G)

with the function σα(a,b) returning the sum a+b, and range(a)>range(b) (the modified b is sent on the bitstream).

Does the order of the two smaller ranges matter ? I think it's better to have the highest difference possible between the operands, so the general formula would be

σα( σα(max, med), min)

See the rest of the algorithm at Basic algorithm for one block