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.
- We calculate: Z = A xor B xor C
- Made one pass of XOR operation of each colour with Z and then:
A --> B xor C
B --> A xor C
C --> A xor B
X --> X xor Z
- Now we made a second pass of XOR operation of the previous B and C
colours with (A xor B) and making a new bitmap: 1 = XOR made, 0 = XOR
not made. So now we have:
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.