COMPRESSION

Less than one bit per pixel
The goal of compression is to create much smaller files that use less space to store and less time to send. A DVD movie is typically compressed to about 1/60. If it wasn't you'd need up to 60 DVDs to watch 1 movie! This high compression rate is possible because most movie data has lots of similar (near equal) patterns hidden within, AND because most people are blind to visual quality. My personal compression-goal is the highest possible compression rate without visual loss of image quality.

When the size of an RGB image file is by compression reduced to 1/2, the amount of bpp (bits per pixel) is down from 24 to 12. A file reduced to 1/60, uses only 0.4 bpp on average, and it doesn't have to stop there! Spending less than 1 bpp is possible only when not describing single pixels.

I'll focus on the movie's sequence of images, but of course there's a soundtrack and such also.


Lossless, Lossy, and Near Lossless
"Lossless" compression is without any loss of image quality: the compressed than decompressed image is an exact replica of the original image.
"Lossy" compression is also done by re-writing the data more space efficient, but more than that: less important details of the image are manipulated or even removed so that much higher compression rates can be achieved.
"Near lossless" is lossy really, but no more than harmful; your should not notice a loss of image quality.


Complexity
The more details, the harder it is to compress.
Take a square of 16*16 = 256 pixels, and 256 possible shades of gray.
If all the 256 pixels are of the same shade of gray, then the complexity is of the lowest possible amount. There are 256 possible shades of gray, so there can be only 256 combinations of the lowest complexity. At the opposite side is this square with each pixel having an other shade of gray. The amount of possible combinations is now much more than 256, to be exact: (256!) =
85781777534284265411908227168123262515778152027948561985965
56503772694525531475893774402913604514084503758853423365843
06157196834693696475322289288497426025679637332563368786442
67520762679456018796886797152114330770207752664645146470918
73261008328763257028189807736717814541702505230186084953190
68138257481070252817559459476987034665712738139286205234756
80821886070120361108315209350194743710910172696826286160626
36624350228409441914084246159360000000000000000000000000000
00000000000000000000000000000000000
Not all of these combinations are of the highest complexity though. When each next pixel is 1 value higher, the complexity is very low. But when all values stand in random order, there are no repeating patterns, and so much details make too complex to compress.

Lowest possible complexity
(all pixels of equal value)
 Highest possible complexity
(on all 3 color channels)


KiloCompression
Are you also in search of extreem compression rates?
Down to 1/60 of the original file size is nice, but coolests would be 1/1000 or more!
128 pixels of 8 bits each are together 1024 bits. Compressing these 128 pixels to 1/1024 results in an 1 bit code. 1 bit can point to only one out of two library locations, ..which is almost nothing compared to the uncompressed 2^1024 possibilities. More interesting than having a small number of fixed combinations in a library, is to point to the predicted combinations that are most likely.

When wanting to compress to 1/1024:
128 pixels have 2 options
256 pixels have 4 options
512 pixels have 8 options
1024 pixels; 16 options (32*32 pixels)
2048 pixels; 32 options
4096 pixels; 64 options (64*64 pixels)
8192 pixels; 128 options
16384 pixels; 256 options (128*128 pixels)
32768 pixels; 512 options
65536 pixels; 1024 options (256*256 pixels)
So; the more pixels are grouped, the more options you'll get.
And; the better the prediction, the less options are needed.
Prediction needs to be extremely good to get 1/1024 or better results.


Prediction
Finish this:
"it ain't what you do, --- --- --- ---- --- -- --".
2, 4, 8, --, --, --, ---.
"Cna yuo raed tihs, or is ti ralely ipmsoislbe?"
One missing pixel will probably have a value very similar to the average of its surrounding pixels. What next group of pixels would be the most likely one?
Good prediction can dramatically reduce the amount of possibilities, thus the amount of bits needed to choose the right guess with.


I will say this only once; do not repeat!
A simple example of compression is "run-length encoding".
255, 255, 255, 255, 255, 255, 255, 254, 254, 254, 254.
This is a couple of pixels that "run" (repeat more than once), and can be coded like this:
7x255, 4x254.
But a typical RGB pixel is one out of 16777216 tones (2^24), thus a pure run of is very rare. And digital data is build from 0 and 1 bits, not from decimal values with spaces and other symbols in between.
The basic idea: If a code appears more than once; write it down only once, and link to it when needed somewhere else. (only when if the link is shorter than to code, of course).

We should not be focusing on values too much, because we are trying to compress an image, not values, it may be a little bit lossy.


Index
There are 2^24 = 16777216 possible colors (for ordinary 8 bits/channel RGB pixels).
There are 2^48 = 281474976710656 possible combinations of two pixels.
There are 2^96 = 79228162514264337593543950336 possible combinations of four RGB pixels.
And so on.
But in a movie, it's not likely that all colors and combinations of colors will appear, and it's also likely that the amount of combinations of just a few pixels is already larger than can possibly fit in this one movie.
In this one-hour movie for example, fit only 2332800000 groups of four pixels.
In an index, only the ones who appear get a code. The ones that appear most often get a short code and the rare ones a longer one.
The index can become quiet large, which is a problem because it has to be saved also. That's why the index must be compressed too.


Groups get discount
When the goal is 0.0078 bpp, you may -on average- not spend even 1 bit per pixel, not even 1/100 bit!
16x16 RGB pixels are 6144 bits, thus have 2^6144 combinations, but at 1/128 file size you'll have only 48 bits left, thus 2^48 = 281474976710656 possible options to address, which is a lot, but next to nothing compared to 2^6144.
The larger the group that can get a "global treat" (one treatment for all), the less bits you have to spend.


Less combinations & relative values
There are so many possible combinations of groups of pixels, that about zero combinations will appear more than once, within one movie.
But the amount of pixel-groups that aren't exactly equal but very similar to other groups, is pretty large. If you compare groups and may use: scaling, turning, and other global twists, than extremely more similarities arise. Within one frame some similarities can be found, but extremely good matches can be found when allowed to compare within any frame of a film, or even somewhere else!
When the most ideal match if found, one only has to note where to compare to and what the difference is. The code of difference (relative values) can also be compared to other codes of difference, and on and on, possible until the difference is equal to zero (or almost). The final code could exist mainly out of directions; where to compare with.

A crude method of creating less combinations is by reducing the amount of colors, but even when using diffusion dither and picking especially the less visible tones, the result isn't great. 8 bits = 256 tones, minus two bits is 64 tones. Little loss of bits and a lot of loss in image quality.

The less combinations and lower relative values, the higher compression rate can be achieved.


Remove noise
Noise is not what we want in an image and also is noise really hard to compress. There are only a few good noise reduction software tools that not only improve image quality, but also make the file much easier to compress. Not just a few % smaller files, more likely is 40%!


Fixed & Variable code length
Fixed:
0=000000000000000000000000
1=000000000000000000000001
2=000000000000000000000010
3=000000000000000000000011
4=000000000000000000000100
5=000000000000000000000101
6=000000000000000000000110
Variable:
0=0
1=1
2=00
3=01
4=10
5=11
6=000
Clearly; variable is the best option, BUT not the easiest one; you'll need to know how many bits each code is, where does it start, where does it end?
Does: 00011010010001001
mean: 0, 00, 1101, 0, 0, 1, 00, 0, 10, 0, 1.
or maybe?: 00, 01, 101, 0, 01, 0, 001 0, 01.
Some solutions (there are many more):
- Intern. Place a code of for example 4 bits in front of each code, which can tell 16 different code lengths.
- Extern. Same as intern, but out of the main code, and can be compressed separately.
- Separation code. For example could "1111" be the in-between code, and may no other code start or end with "11" or "111", or contain "1111". The good thing of separate, is that if the track is lost; it can be found easily. Also is there no limit on the length of the code. Finally, run-length encoding could remove long separationcode-runs pretty well.

MAXIMUM COMPRESSION

What is the best compression method? No, there is no "one solution for all". If the data is divers; so are the solutions. Multiple compression types can be combined to reach optimal compression of one file, thus one should analyze the data before choosing how to compress it.

Some wild stories (like about Jan Sloot) claim compression rates of 1/1000.000 and more! Is that possible? Not within the box.

Redundancy
If you analyze a compressed file, you'll find that all possible symbols are present in almost equal amounts and in almost random order. All profitable repetitions have been removed. This type of data has the most combinations per volume, and seems impossible to compress any further. Its redundancy is about zero.