Data Compression

[robski]

Yes Clive a number of things will click into place once you get an understanding of what is going on inside the black box. Of course in some applications such a medical images chroma down sampling is undesirable because the wanted information is in the colour so images should not be stored in the jpeg format. Just out of interest jpeg does have a lossless method but the compression ratios are nothing to write home about compared to the Baseline (Standard) method I am describing.

I am glad a number of you are interested and managing to follow what can be a complex subject. All we need to do is grasp the concepts applied to get an idea why some images compress better than others.

Part of my degree profile was to spend a year on telecoms. The data encoding and decoding aspect I found fascinating.
The boffins who worked on complex ciphers used in secret messages we have to thank for some of the concepts developed. Other concepts are very mathematical and abstract.

[Dave Smith]

Keep them coming Rob, this is a fascinating read.

Dave

[Mick]

Most interesting thread I have seen for quite a while, thanks Rob.

Mick

[robski]

Thanks Mick & Dave

I am trying to provide the info in bite size chunks as and when I get a few free moments.

A point to mention about the Chroma down sampling is that the colour information is lost forever. Plus further opening and resaving of the jpeg file will cause further lose of colour information. How important colour information is in our lives is open to debate. When you consider that 1 in 20 men are genetically disadvantaged and suffer from some form of colour blindness. The best way of explaining colour blindness is the restriction (compression) of the range of colours in a rainbow. Women ( only 1 in 200 suffer from colour blindness ) will see all the hues of reds and greens. Whereas men may just see a red and a green and in severe cases not be able to tell the difference at all.

Moving on to the next process step.

The luminance and chrominance components of the image are divided up into an array of 8x8 pixel blocks. Padding is provided if required to ensure blocks on the right and bottom of the image are full. This segmentation into blocks is in preparation for the next stage which is the most processor intensive and difficult to comprehend. But don't let that put you off

[robski]

The fans of Monty Python will probably recall the line "What did the Romans do for us" and after some thought a long list of innovations were revealed. Well we can twist this and say "What did the French do for us" and I am sure a equally long list could be produced. As far as we are concerned they produced two interesting branches of mathematics. We are going beyond the simple idea of adding up a shopping list. We are into the realms of Roger Penrose helping Stephen Hawking produce a Mathematical proof that Black Holes exist in space.

Sounds very complex but the concepts stem from a very simple idea. These ideas get extended and become very abstract and can be applied to all sorts of problems. Take the French gamblers who were trying to work out the odds or devise a system to win at the Casino. They were responsible for statistics. In fact if you touched on the subject at school the typical example was what is the chance of throwing a dice and getting a 6. Then what is the chance of throwing two 6s in a row. This leads us to workout the probabilities of events and as we saw earlier it is used in some compression schemes.

French engineers came up with a concept of using a mathematical model to solve problems. Any object or structure can be made up from smaller components.
For example a house is made up from bricks. If they need to calculate the strength of a house, bridge or dam they would test the strength of a single component. That is test a brick to destruction. Then workout the relationship of a few bricks joined together with mortar. This information can then be extended to larger buildings. In some real world situations the mathematic is too complex or long winded to process. In these cases a simpler approximation is used to replace some of the components. A bit like using a clear piece of plastic instead of glass because the required properties are similar. Another extension of this is to transform something in to something else because it is easier to work with. An example could be to turn solid ice into liquid water or a gas steam.

I am hoping the above has extended your mind into a way of lateral or abstract thinking as this is required to follow the next stages of the jpeg processing.

[robski]

Let's consider Joseph Fourier's concept of where an object can be broken down into a number of components and reconstructed from them. To be correct his concept was an infinite series of components but in practice a practical limit has to be imposed. If we take a note from a musical instrument and feed the sound into a frequency/spectrum analyser it will show the fundamental frequency of the note and number of harmonics. Each frequency being at different amplitudes. Attempts to create electronic music used these ideas. Remember the Moog Synthesizer and electronic organs of the 1970's.

If you did your own research into jpeg compression at this stage of the processing you would be told the 8 x 8 block is fed into a forward Discrete Cosine Transformation (DCT) process so that the image is transformed from a spatial domain representation to a frequency domain representation.

Most of you would just said what the Hell !!! This is perhaps the most confusing of all steps in the process and hardest to explain.

For a spatial domain think of an object in space with 3 dimensional coordinates

For frequency/time domain think of a time line with the slowest objects at one end and the fastest the other end. In fact what you would see on the display of a frequency/spectrum analyser.

So in effect we have taken a 8 x 8 picture element and fed it into a frequency/spectrum analyser to measure the strength of certain frequency components.
The output of the forward Discrete Cosine Transformation (DCT) process is a set of 64 values. Each value is the strength of each frequency component which start from a steady level (DC - average of all pixels) and each step is an increase in frequency in the x and y direction in the 8 x 8 block.

Still not easy to visualise.

So I managed to find a diagram showing the 64 frequencies. In my mind I find it easier think of these frequencies as a set of patterns and the DCT process is finding the strength of each pattern in the 8 x 8 block.

Therefore when it comes to decode the jpeg and reconstruct the 8 x 8 block it is easier to think of it as we need strength 4 for pattern 1, strength 8 for pattern 2, strength 0 for pattern 3, strength 12 for pattern 4 and so on. Almost paint by numbers

Just out of interest the DCT process is related to the fast Fourier transform.

[robski]

The next step is Quantization which is the procedure of constraining the 64 outputs of the DCT process to a discrete set of values, such as an integer (whole number), rather than a continuous set of values, such as a real number (number that can have a fractional part). This is done by dividing all 64 strengths of frequency (pattern) by a corresponding value in a quantization table and then rounding the result to the nearest integer. The values in the quantization table are chosen to preserve low-frequency information as humans are more critical to loss of information in this area and discard high-frequency (noise-like) detail.

An example quantization table - the top left hand corner represent the low frequency and bottom right hand represent the high frequency.
A value in the table is used to divide the corresponding output of the DCT in the 8 x 8 block.
----------------------------------
16 11 10 16 24 40 51 61
12 12 14 19 26 58 60 55
14 13 16 24 40 57 69 56
14 17 22 29 51 87 80 62
18 22 37 56 68 109 103 77
24 35 55 64 81 104 113 92
49 64 78 87 103 121 120 101
72 92 95 98 112 100 103 99
----------------------------------

This is the point at which the user (you) can control the quality and amount of compression of the JPEG. Most application such as Photoshop have a slider or drop list of quality settings. The quality setting ( Quality factor ) is used to scale the values in the quantization table.

Outputs that either had a small frequency (pattern) strength or a large divisor in the quantization table will likely round to zero.

The lower the quality setting, the greater the divisor, increasing the chance of a zero result. On the converse, the highest quality setting would have quantization table values of all 1's, meaning the all of the original DCT data is preserved.

An important point to realize here is that the quantization table used for this step differs between nearly all digital cameras and software packages. Camera manufacturers independently choose an arbitrary "image quality" name (or level) to assign to the 64-value quantization matrix that they devise, and so the names cannot be compared between makes or even models by the same manufacturer.

The Quantization table used is stored as part of the Jpeg.

The Quantization process is the main source of the Lossy Compression.

We are on the home straight now the rest is simple compare to the DCT and Quantization processes.

[Mick]

Fascinating stuff Rob, going to take some reading and rereading to get to grips with it though.

Mick

[robski]

Thanks Mick - Is there any part which is proving troublesome which maybe I can expand upon or provide diagrams ?

Below is an example set of Quantization tables used in a Nikon Camera. The upper 8 x 8 matrix is used for the luminance channel and the lower two are used for the two chrominance channels. From this we can see that the tables used for the chrominance channels discard more of the high frequencies than the luminance table.

The whole point of the DCT is to separate the image data into bands of frequencies. Then through the Quality Control setting (compression level slider) the high frequencies components can be progressively discarded as the compression level (ratio) is increased.

The 64 quantized frequency bands are then sorted so that the order runs from the lowest frequency component to the highest. Which will result in an increasing stream of zeros at the end as the compression is increased. It then becomes idea to apply the lossless Run length compression method on the long stream of zeros in the next stage.

[Lee]

Rob,

many thanks for this,spent the last 20 minutes,reading through,and no doubt will return to some points,you have a knack for giving an explanation that flows along.

Much appreciated

Regards

Lee