0%
0%

# σα code

another addition-based transform for lossless data compression

Similar projects worth following
489 views
This is a bit-reversible transform that takes two non-negative integer numbers and outputs a sum and a modified operand. The sum is not altered and its size can expand a little bit but the transform uses auxiliary boundary informations to significantly reduce the number of bits required to encode the modified operand.

The σα transform differs from µδ transform (σα works with variable-length codes while µδ remains in the fixed-sized realm) and has other purposes and applications, such as "mother transform" for the 3R algorithm (instead of simple addition) and RGB colorplane compaction.

Logs:

σα is a very simple algorithm that uses only basic operations over positive integers. Applications include:

and certainly more to come...

Just like the µδ code, the name comes from data that are encoded:

• σ (sigma) represents the Sum
• α (alpha) represents one Addend (to be chosen)

Encoding is as simple as

Decoding is straightforward:

σα is used with VLC (variable length codes), in particular the similar-looking economy codes (also called phase-in codes or truncated binary codes) but an arithmetic encoder or a range encoder can also be used.

Why and how does this work ?

The z=x+y equation can be plotted in 3D, in the range 0..1 for each axis:

Without boundaries on x and y, the sum defines a tilted plane that is infinite. However, applying limits to the operands and the sum creates a triangle. This is actually one half of the whole plane, which is a rhombus encased inside two cubes:

(sorry, I couldn't get the scales right)

So the sum, when supplemented with the boundaries of the addends, puts an upper bound on the addends, which results in the triangle of the first plot (where x and y are restricted in the 0:1 range). To get the upper triangle, a simple symmetry is applied, and at the upper part, the triangle is getting narrower as x and y increase.

Now if you plot all the possible values that an addend, say, x, can have, depending on the sum y, we get another rhombus. What the algorithm's conditional subtraction does is to swap one half of the rhombus to create a triangle.

The above plot shows where the values m-a and l-S come from. The red shape can be encoded with a value that is x-sum but there is another, more interesting, possibility: by encoding 1-x, all the high values of x are transformed into low values. In the context of the 3R encoder, this solves a very nagging issue where consecutive high values eat up a lot of bits.

The following table shows the encoding for two numbers a and b bound to [0:7]. S is sent with the default range [0:14] The following number c = a || m-a is sent when it's not zero.

 b \ a 0 1 2 3 4 5 6 7 0 S=0 S=1,c=1 [0:1] S=2, c=2 [0:2] S=3,c=3 [0:3] S=4,c=4 [0:4] S=5,c=5 [0:5] S=6,c=6 [0:6] S=7,c=7 [0:7] 1 S=1,c=0 [0:1] S=2,c=1 [0:2] S=3,c=2 [0:3] S=4,c=3 [0:4] S=5,c=4 [0:5] S=6,c=5 [0:6] S=7,c=6 [0:7] S=8,c=0 [0:6] 2 S=2,c=0 [0:2] S=3,c=1 [0:3] S=4,c=2 [0:4] S=5,c=3 [0:5] S=6,c=4 [0:6] S=7,c=5 [0:7] S=8,c=1 [0:6] S=9,c=0 [0:5] 3 S=3,c=0 [0:3] S=4,c=1 [0:4] S=5,c=2 [0:5] S=6,c=3 [0:6] S=7,c=4 [0:7] S=8,c=2 [0:6] S=9,c=1 [0:]5 S=10,c=0 [0:4] 4 S=4,c=0 [0:4] S=5,c=1 [0:5] S=6,c=2 [0:6] S=7,c=3 [0:7] S=8,c=3 [0:6] S=9,c=2 [0:5] S=10,c=1 [0:4] S=11,c=0 [0:3] 5 S=5,c=0 [0:5] S=6,c=1 [0:6] S=7,c=2 [0:7] S=8,c=4 [0:6] S=9,c=3 [0:5] S=10,c=2 [0:4] S=11,c=1 [0:3] S=12,c=0 [0:2] 6 S=6,c=0 [0:6] S=7,c=1 [0:7] S=8,c=5 [0:6] S=9,c=4 [0:5] S=10,c=3 [0:4] S=11,c=2 [0:3] S=12,c=1 [0:2] S=13,c=0 [0..1] 7 S=7,c=0 [0:7] S=8,c=6 [0:6] S=9,c=5 [0:5] S=10,c=4 [0:4] S=11,c=3 [0:3] S=12,c=2 [0:2] S=13,c=1 [0..1] S=14

The table contains no identical pair of {S, c}, which proves that the encoding is fully reversible.

The size of S is fixed, in the range [0:2m], which adds one bit to the normal binary representation. This is a constant overhead that can't be avoided.

However the sum carries information about the addend a, which is then encoded as c. Depending on the value of S, c can use fewer bits, even no bit at all in the two extreme...

• ### Some lossy video compression

Yann Guidon / YGDES10/22/2018 at 16:27 0 comments

LordNothing

block formats are pretty easy to do but i dont think there is any support for that in the display hardware. like being able to use dxt1 at four bits per pixel, a 4x improvement over raw 16 bit color data. for every 4×4 block of cells, select the lightest and darkest 2 pixels in the block, sticking those into a color table, generate 2 interpolated pixels. those four colors become a color table and the pixels are stored as 2-bit indices. decompression is much faster as it just needs to do the interpolation step and from that it can assign color values to the pixels on the screen so the demands on the display controller would be minimal. it just has to exist first.

So given the min and max values of pixels in a square, some relatively decent compression is possible, which directly benefits from the σα code. The system is a bit more complex because there are 2 layers of compression, with very different characteristics, but the compression ratio will be better in some pathological cases such as noise or other very fine details.

• ### To reverse or to not reverse

Yann Guidon / YGDES05/30/2017 at 04:21 0 comments

20170530:

The reversing of the encoded number comes from the following assumptions:

• Colors are often "saturated", often very close to zero or close to max, few "pastels" between 25% and 75%
• This is reinforced when a block is adjusted for minimum and maximum values : at least one sample will be 0 and another will be max (which ?)
• The "very high and very low" scenario also happens with relative/delta/differential coding where hopefully there are mostly low-amplitude values, and the positive values wrap around to very high values. Low amplitudes with negative values will use fewer bits

However,

• The reversal at the middle is totally arbitrary. Nobody can be sure that these heuristics will happen "most of the time".
• This reversal could be under-efficient with different kinds of data sets.
• The amplitude reversal requires a subtraction in the critical datapath, which slows things down (a bit).

The "safe answer" is to say : measure and compare various scenarii. But there is a catch: with no reversal, there is still something to compute, in this case a-S.

Considering that S=a+b we get a-S=a-a-b=-b

Oh wait, we have a negative number now ?

If there is no reversal, there still is some computation ( -x = ~x +1 and incrementation is faster than full addition but not by significantly much)

• ### Extension to unequal boundaries

Yann Guidon / YGDES05/27/2017 at 04:14 0 comments

The algorithm presented on the project description is, in fact, a special case where both addends have the same range.

In the colorspace decomposition algorithm however, there are 3 addends, with the same boundaries but the intermediary sum Cgb has twice the range of the R component. Combining R and Cgb creates a new set of problems...

First : one addend's boundary is larger than the other. The algorithm requires a clear ordering to work, so we must swap the operands in a preliminary step, if the order is not respected.

```0 ≤ a ≤ m,
0 ≤ b ≤ n,

1) initial setup:
S = a + b,
l = m + n

2) operand swap:
if (m < n) then
swap (a, b),
swap (m, n)
fi
```

(edit 20170607: removed o and p because they were useless)

Now that it's out of our way, we can focus on what to do with these data and what happens to them.

Let's focus on the data table of the Project Details Page.

What this amount to, is: a square of side n, cut in half at the diagonal (that corresponds to S==n). One half of the square has a normal numbering of the columns, the other half has a reverse numbering.

What happens when m > n ?

In a geometric sense, this amounts to cutting the square at the S=m diagonal and moving the lower/reversed part away from the higher part, creating a new zone between them.

The diagonal of the square is the place where two things happen:

• the operand is reversed: a becomes m-a
• the range of a is also reversed

However when the limits are different, these two things do not happen at the same place anymore.

• The reversal of a must occur at the middle of the rectangle, so there are as many direct codes as there are reversed codes. This does not occur at n or m, but in the middle:
```if ( S > l/2) then
a = l/2 - a;
fi
```
• The range decreases at S>m, increases at S≤n, but between these bounds, it does not change: there is a saturation region.
```if (S < n) then
range = S     (increase)
else
if (S > m) then
range = l - S  (decrease)
else
range = n     (saturate)
fi
fi```

These tests can be run in parallel, but also in series, because the conditions are co-dependent: n < l/2 < m. The code segments can be merged:

```3) Reversal:
if (S ≤ l/2) then
range = S
else
range = l - S
a = l/2 - a
fi

4) saturation
if (range > n)
range = n
fi```

Of course, the decoding is symmetrical, it reuses the same formulas to compute the requested range and adjust a.

Conclusion

This general algorithm works for m=n, and the special case presented in the main page is just an optimisation and simplification. The special case is faster and more compact but the general case is more powerful and potentially more efficient.

In the context of 3R, when m != n, the trivial approach for encoding one of the data is to send the one with the smallest range. The above algorithm goes further:

• it reverses the encoded number, which makes it easier eventual further entropy coding steps
• it reduces the range of the encoded number, when it is known to not exceed an implicit limit.

Taken together, these elements significantly increase the packing density with no pathological case or increase of the original data (to be demonstrated). These improvements would be impossible without the knowledge of the respective limits of the operands.

Share

## Similar Projects

Project Owner Contributor

### 3RGB image lossless compression format Yann Guidon / YGDES

Project Owner Contributor

### PEAC Pisano with End-Around Carry algorithm Yann Guidon / YGDES

Project Owner Contributor

### QuickSilver Neo: Open Source GPU Ruud Schellekens

# Does this project spark your interest?

Become a member to follow this project and never miss any updates 