opendir has moved servers and i cant be assed to reconfigure the clusterfuck that is Histoire, enjoy the new look!

if you're missing any directory headers or footers then try with these: header / footer

Direccional Compression

Direccional Compression

by Abraham Macías Paredes





The Direccional compression method

The word "Direccion" means address in spanish. This method tries to compress the  colour information of an image using the address of the colours. This address is a pair of coordinates (X, Y).

One colour is represented with 24 bits in RGB (one byte for Red, one byte for Green and one byte for Red components). But if you take a 16x16 section you could codify much colours like: [Colour][number of repetitions][X1][Y1][X2][Y2] ... [Xn][Yn]. Where each pair of [X1][Y1] and the [number of repetition] are only 1 byte of long. And is obvious that you could save a colour representation, so we save the 0x000000 representation leaving it like the codification of the end of one section codification.

Let see an example with a 4x4 section:

000000
 217624
 000000
 223787
000000
 217624
 000000
 223787
000000
 217624
 000000
 223787
000000
 217624
 000000
 223787


This section have 4x4x3 = 48 bytes. If we codify it:

COLOR
 N
 XY
 XY
 XY
 XY
217624
 04
 10
 11
 12
 13
223787
 04
 30
 31
 32
 33
000000
 00




Now the section is only 20 bytes.

To recover the original codification just fill a 4x4 section with 0x000000 and place in each position given by XY the colour pertinent untill find the zero colour.


Advantages/Disadvantages of this compression method

The main advantage of this compression method is that could compress with the same ration despite the order of the colours. I will explain it.
Let see this two sections:

Section 1:

000000
 217624
 000000
 223787
000000
 217624
 000000
 223787
000000
 217624
 000000
 223787
000000
 217624
 000000
 223787

Section 2:

217624
 217624
 217624
 217624
223787
 223787
 223787
 223787
000000
 000000
 000000
 000000
000000
 000000
 000000
 000000

With many others compression methods this two sections will be compressed with diferents ratios but not with direccional compression.

And the main disadvantage of this compression method is that not compress very much.



Improvement 1: CSR

The first thing you could try in order to compress more is to use another method of my own, the CSR compression. CSR means Combination Without Repetition in spanish.

Now you can see that the XY coordinates are a combination without repetitions of bytes (we can't have more than one colour in each cell). As you may know a there is much less combinations without repetitions possibles than combinations with repetitions.

Let see:
 Number of combinations with repetitions of n numbers taking m =power(n,m)
 Number of combinations without repetitions of n numbers taking m = n * (n-1) * (n-2) * ... * (n-m+1) = n!/m!
 (n!/m!) <= power(n,m)

Example:

  Combination without repetitions of 3 numbers taking 3 is 3! = 6

combination
 number
0
 1
 2
 0
0
 2
 1
 1
1
 0
 2
 2
1
 2
 0
 3
2
 0
 1
 4
2
 1
 0
 5

So if we codify each combination with each number we can save many bits.
I have an algorithm to do this easy, but you can see that in the coordinates the order is not important and if the order is not important you can compress more. So this improvement have been discarded.



Improvement 2: bitmap


So we have said that the order is not important. This means that the combination without repetitions can be represented as a bitmap. This bitmap will have 256 bits and it will have a 0 is the number isn't in the combination , and a 1 is the number is in the combination. And if we have only 2 diferent colours we can codify it with only one bitmap: 0 = colour A/ 1 = colour B.



Improvement 3: Colour elimination

With the bitmap if you have more than 32 equal colours it will be always 32 bytes. So if you have 3 colours, 2 of them with more than 32 repetitions you can eliminate the 3º colour converting it into zero thanks to the XOR operation.

Let see, if we have 3 colours A, B, C.
A --> B xor C
B --> A xor C
C --> A xor B
X --> X xor Z

B xor C --> B xor C
A xor C --> B xor C
A xor B --> 0
X xor Z --> X xor Z

Now the A and B colours are equals to (B xor C) and will be codified with 32 bytes of bitmap, and the C colour is zero and is not codified.



Improvement 4: Reverse codification


If you have more than  224 elements you can save more bits by codifying the positions in where the colour isn't. So if you have 256 equal colours you can codify it only like [Colour][00].




Improvement 5: Section elimination

We codify sections but one section may be equal to a previous one, specially  if this section corresponds to a background colour. Think by a  moment in a chess board of 16x16 squares. We haven't to codify all this sections, we can say that one section is equal to the previous.



Improvement 6: Ordering

This improvement will not give a smaller file size but it will give you a file that can be compressed (with another compressor) much more.
The only thing you have to do is to put the same codifications together. Put first the codes (each code is a compression method) and then the sections compressed by the first method, sections compressed by the second method and so on.

Posible codes:
 00 --> 256 zeroes
 01 --> 256 numbers equals to X
 02 --> 255 numbers equals to X and one more
 03 --> Section equal to a previous one
 04 --> Codification with colour elimination
 05 --> Codification without colour elimination and with zero (needs 0x000000000 in order to find the end of the section)
 06 --> Codification without colour elimination and without zero (ends when 256 elements have been decompressed)
 07 --> RAW section (sections that have more than 127 diferent colours can not be compressed)
 08 --> 2 colours section (the 2 colours are codified like a bitmap)

Improvement 7: Sub filtering

You have notice that we can compress much more the codifications with many zeroes. So we can make a SUB filtering in order to generate much zeroes.
The sub filtering is something like the sub filtering of the PNG format. We substract the next colour from the actual.

 Colour[n] = Colour[n] - Colour[n+1]

The sub filtering not always ensures a smaller file size because of the other improvements. (The sub filtering ensures much zeroes but much diferents colours too).



Software Implementation

I have a software implementation of the direccional compression. Is a program for Linux that converts a 24 bits (and only 24 bits) windows bitmap into a dir image. You cand find it in http://motioncodecs.sourceforge.net/

This compression method usually compress more than RLE but can not compete with PNG.