Data Compression

[robski]

Data Compression

I'd been promising to write a piece on the topic of data compression for a while. Hopefully I can shine some light on the subject to give you a better understanding of what is going on. It is quite simple once you have got your head around 3 basic concepts.


1) Think of a computer file as a container, cardboard box or an envelope. It can hold something of a certain size.

2) Think of a computer image as an egg tray or a piece of graph paper. It has a set number of positions depending on how many pixels are in the image. Therefore the image in the video display memory of the computer is of a fixed size.

3) The amount of Information an object contains. This concept more abstract and not so easy to grasp.

Lets take an object like a sheet of A4 paper with printed text.

In our first example it just has the words "Hello World"

The second example is say an Electricity Bill. It will contain the following sort of information. Addresses, telephone numbers, prices, units used, dates, taxes and so on.

So our second example contains much more information then the first one. Therefore the first example only needs a small sheet of paper compared to the larger sheet required for the bill.

It then follows that a smaller envelope or container can be used to hold the first example.

The Key point being there was a lot of wasted ( redundant - unused ) space on the "Hello World" example.

I will leave you with these concepts to let them soak in before looking at what methods are used.

Data Compression is about finding a more efficient code to hold the information.

If the information is already stored efficiently with no waste then it will not be easy to compress it further.

Are you all with me so far ?

[treeve]

With you all the way, I used to write random access databases,
and the need for data compression was intense in those early
days, with limited storage space. I wrote a number of algorithms
depending on the type of data to be stored. The need for set
standard storage packets was essential in order to store a full
random access database, which had to be read, unpacked,
viewed, altered (perhaps) re-coded and re-written and
re-stored in the same space. All done from machine code.
Fun days ...
Best Wishes, Raymond

[robski]

Let us first consider how much memory an uncompressed bitmap raster image uses.

Using a small 1280 x 1024 pixel desktop image as an example.

Each pixel requires 3 memory locations to store the RGB colours.

So 3 Blocks ( arrays-grids) of 1280 x 1024 memory are used = 3932160 memory locations

Therefore any 1280 x 1024 image will always use 3932160 memory locations

The Windows Paint bmp files stores data in this uncompressed format plus some header info.
With larger images the huge file sizes create a problem for data storage and transmission over networks.

To overcome these problems data compression is used to reduce the file size.

The first data compression methods devised were loss-less. That is after compression and decompression you get back the original data.

I will give you a basic idea of some of the loss-less methods used but they relied on the data being inefficiently coded in the first place to get good compression ratios. With a few exceptions as a general rule of thumb if the compression ratio is better than 10:1 then it is not a loss-less method used.

To improve compression ratios further lossy methods were developed. That is after compression and decompression you get back something that looks like the original data.

[Don Hoey]

An excellent thread Rob that I am sure will be of great value to many.

Don

[robski]

Let's look at some of the simpler lossless data compression ideas for background information. Unless your going to design a program there is no point in understanding it to the nth degree.

They basically take advantage of waste, unused values or inefficiently encoded raw data.

A simple example is some English plain text with each character stored in an 8bit byte. Data stored in a byte can hold 1 of 256 values. A typical text message is make up of 52 upper and lower case characters, 10 numbers, a dozen punctuation marks and a few control codes. Over half of the possible positions (values) are never used. In this case a 7bit code (128 values) would be more efficient. The 7bit codes would be packed together to fit into the 8bit bytes reducing the file size by ~12.5%. Not a very useful method for graphic images but illustrates a point.

Another idea is Run Length Encoding. This takes advantage of long streams of identical data.

For example AAAAAAAHHCCCCCYYYYYYRRRRRRRRRR
could be re-encoded as 7A2H5C6Y10R The number indicates the run length followed by the value of the run.

or in the case of binary data in a 1bit monochrome image ( Fax machine )
00000011100001111111101
could be re-encoded as 634811 to indicate how many zeros and ones follow each other.

If you think about it. Long streams of the same information it is telling us something we already know and therefore redundant. This information can be discarded.

There is a big disadvantage with the run length method when the data changes very rapidly

For example AHCYR
would be re-encoded as 1A1H1C1Y1R which is in fact larger than the original.

Rapidly changing data contains more information which needs to be retained by using more code.

Two Common 1bit fax compressions are group 3 and group 4. The group 3 works in one direction only along the row of pixels. Group 4 works in both directions and takes into account multiple rows. Although group 4 gives higher compression ratios it has more work to do which results in it being slower than group 3 when compressing or decompressing.

Another idea is to look for common Patterns in the raw data and replace them with shorter special codes.
An example in text data is to replace common words or parts of words ( the, and, or, in, to, un, ed, for) with a shorter unique code.

The last idea involves more processing by counting the number of times a value occurs in the data. The most frequent values are assigned short codes which get longer and longer as the frequency of the value reduces.

A perfect example of this is Morse Code - remember that thing with dots and dashes on the radio. The letter E (the most common character in English) is a single dot and less common characters like J & Q may have 4 or more dots and dashes. The overall effect is to shorten the coding on a typical message.

In cases such as English text the typical frequency of characters is well know and a standard coding table or dictionary can be used instead of calculating a new table from scratch each time. In essence we are calculating or predicting the probability of values in the raw data. Huffman coding is based on this idea.

What is important is to match compression method to the type of information in the data. Choosing the wrong method will either make the file bigger or give poor compression. Advanced compression programs first analysis the data to decide which is the best method to use.

The LZW Compression is very effective and uses the more complex ideas but unfortunately it's use required a license. So not to be found in your cheap and cheerful photo editing software.

[robski]

Image pixel data is stored in one of two formats. Contone (CONtinuous TONE) where data is stored in bytes to represent the different levels of brightness and colour. This is the type of data produced by a scanner or camera. For the purposes of printing newspapers and magazines on a printing press these are converted and stored in 1bit image format. Basically a stream of zeros and ones ( on - off signals if you like). Often referred to as 1bit tiff or bitmaps, Line Art and halftones images. The Lossless Group 3 and 4 compress 1bit data very well. It is the Contone data that presents the headache for compression.

Graphic image data with lots of fine detail when compressed using a lossless method entail lots of processing for little compression effect. New ideas were needed to overcome the problem which led to a detailed examination of the information stored in an image. An image is shades of light and dark of different hues. The viewer is the human eye and brain. The new ideas were centered around exploiting the strengths and weakness of the human system. What information does the eye and brain need to see the image correctly? What detail can we afford to lose without it being noticed and what detail lost will be noticed ?

The brain is a powerful tool and can workout a lot of things for itself.

"Digital imagi_g is rapidly replacing film phot_graphy in consumer _nd professional markets"

If you can read and understand English the message in the sentence above is not lost despite the fact 3 characters are missing.

One approach of removing information from graphic image data is to apply a process that will remove noise (seen as a fine grain effect) caused by the input sensor of a camera or scanner. By definition Noise is unwanted and random. The denoising process is designed to smooth out random pixel hot spots and leave behind the wanted picture information. A simple approach is to zero the least significant bit of a byte. Or in Plain English to round down all odd values held in a byte to the next even number. Sophisticated programs such as ninja, picture cooler and neat image analysis a patch of bland picture area to build a profile of the noise characteristics and apply it to the whole picture area. The overall effect is much the same in each case that it has smoothed out many of the little pits and bumps in the range of data values. Effectively reducing the number of changes (transitions) in value of the data. Changing the pixels colour value by 1/256th is not going to be noticed.

Example original raw data
ABABAABAEDEDDEKKLKKLLK

Compressed original ( in this case the code is longer )
1A1B1A1B2A1B1A1E1D1E2D1E2K1L2K2L1K

Smoothed data ( noise removed )
AAAAAAAAEEEEEEKKKKKKKK

Compressed Smoothed data
8A6E8K

The smoothing has increased the length of runs of data which will improve the compression ratio.

Of course this approach of throwing information away can only be applied to audio/visual data. Dangerous and senseless to throw away information in a spreadsheet of an accounts system.

Next we will turn our attention to JPEG. As yet nobody has managed to slap a license on its use so camera manufactures and photo editing programs can freely enjoy the benefits of this picture image format. In 1982 the ISO formed the Photographic Expert Group to research methods of transmitting Video and still images over data links. It's Goal was to produce a set of industry standards. In 1986 the CCITT set up a group to work on Compression methods required for colour facsimile machine transmission. In 1987 the two groups were combined to form a joint committee (Joint Photographic Experts Group ( JPEG )) that would research and produce a single standard.

JPEG unlike other compression methods is not a single algorithm but maybe thought of as a toolkit of image compression methods to suit the users needs.

[treeve]

Fascinating stuff Rob ... Thanks

[robski]

JPEG uses a lossy compression method that throws useless data away during encoding. This is why lossy schemes manage to obtain superior compression ratios over most lossless schemes. JPEG is designed to discard information the human eye cannot easily see. The eye barely notices slight changes in colour but will pick out slight changes in brightness or contrast. Therefore JPEG's lossy encoding tends to be frugal with the gray-scale part of an picture and frivolous with the colour component. A typical photographic quality image maybe compressed by 20:1 without experiencing any noticeable degradation in quality.

If we look at the original RGB image we will find 3 high definition images one for each colour.

The first task of the JPEG encoder is to convert the RGB image components into a monochrome component ( luminance), a blue chroma component and a red chroma component. For the more technically minded it have converted from a RGB colour space to a YCbCr colour space used in video systems. Those who use Photoshop may of bumped into changing the mode of a RGB image to Lab.

Lab is a similar idea to YCbCr

Where L is the brightness component, a is the red/green component, b is the yellow/blue component

The purpose of the separating RGB into mono and colour it to allow different processing to the luminance and chroma channels.

Below we can see the 3 high definition RGB channels.

I have also added an illustration that shows the luminance (gray scale (L channel)) and combined chroma (a + b channels ) components separated from a RGB image using Photoshop. From this we can see that the gray scale is high definition and the chroma is very low definition. In fact if you blurred the a and b channels and converted back to RGB you would barely notice any difference. A completely different story if you sharpened or blurred the L channel.

[robski]

The next stage is to apply Chroma sub sampling (down sampling - reduce the resolution).

The simplest way of exploiting the eye's lesser sensitivity to colour information is to use less pixels for the two chrominance channels

The luminance channel is retained at full resolution.

Both chrominance channels are typically down sampled by 2:1 horizontally and either 1:1 or 2:1 vertically

For example a colour image of 1000 x 1000 pixels, the luminance (grey/mono) channel will remain at 1000 x 1000 pixels but the chroma channels would be either 500 x 1000 pixels or 500 x 500 pixels. So a single Chrominance pixel would cover either cover 2 x 1 or 2 x 2 luminance pixels dependent on a jpeg encoder setting. This maybe under user control as part of the quality setting or just hard coded by the programmer.

So in terms of compression the higher down sampling will give us 50% compression with very little perceived lost of quality with photographic images .

i.e. we store 6 pixels values for each 2x2 block ( 4 luminance values and one for each of the 2 chrominance channels) instead of the 12 needed to store at full resolution in each channel.

The existence of chroma sub sampling in JPEG compression explains why better compression ratios are achieved (ratio between original file size & compressed file size) with colour photos than with greyscale (mono) photos.

Most DSLR cameras use 2x1 chroma down sampling while some graphic editing programs and point and shoot digicams use 2x2.

[Gidders]

Originally Posted by robski

The existence of chroma sub sampling in JPEG compression explains why better compression ratios are achieved (ratio between original file size & compressed file size) with colour photos than with greyscale (mono) photos.

Ah ha - so that's the answer. I've always wondered why a when preparing my images for the forum, to achieve ~200k file size from a 1000 x 667 image, with colour a jpeg compression quality setting of 10 gives the required file size, where as with mono I have to reduce the quality setting to 6 or 7