Data Compression

[Mick]

Good stuff Rob, I think I am beginning to understand it, at least it isn't the complete mystery it was before.
Thanks.

Mick

[robski]

This post is to further dot the i's and cross the t's on the Quantisation stage. It is responsible for the majority of the lossy compression.

Each DCT term is divided by the corresponding position in the Quantisation table and then rounded to the nearest integer as illustrated in the first attachment. In the Quantization table the low frequency terms are in the top left hand corner and the high frequency terms are in the bottom right hand corner.
The values in the Quantisation table are also scaled (multiplied) by the Quality Factor setting ( Compression level slider in photoshop) which has the overall effect of making the Quantization level finer or coarser. From the table we can see that the size of Quantization steps varied with frequency. High frequencies are less important to human vision and therefore receive a coarser quantization. For example the low frequencies may end up with 50 different levels and highest frequency with only 3 or 4 levels.

The effect of Quantization is a bit like the Posterisation tool in Photoshop. In fact for the next attachment I have taken a typical photographic scene and applied different levels of posterisation. The upper image has 256 levels and will store in 8 bits. The middle image illustrates the effect if we used 7bits and the lower image shows the effect if we reduced it further to 6 bits. Our vision system is very tolerant to a reduction in the number of levels for this type of image. However, in the next attachment I have used the gradient tool to simulate a very low frequency image. Stepping is clearly seen as the number of levels are reduced. So for low frequencies the number of levels must to be retained.

[robski]

The final stage of the JPEG process is to use the lossless Huffman compression coding to compress all of the run length compressed (another lossless compression technique) DCT terms. As mentioned in a previous post Huffman is a variable length code based on probabilities. Unlike most other codes which are fixed length block codes. For Huffman to work well there must be values in the data that occur more frequently than others. If the values are completely random then Huffman coding is pointless.

Now to run you through a typical training example that illustrates the benefits of Huffman compression.

Imagine that digital codes are used to transmit various regional weather conditions to shipping.
Let's consider there are 4 states for visibility as outlined in the table below

Visibility	Code word using a 2 bit block code
-----------------------------------
Very Poor         00
poor              01
moderate          10
good              11

There are 4 state which would require a 2 bit code

To workout the Huffman code you need to know the probabilities of each state. In our case the probabilities are as follows.

Visibility	Probabilities
-----------------------------------
Very Poor	 0.1
poor             0.3
moderate         0.5
good		 0.1

The most probably events gets the shortest code and the least probably events get the longest code

Visibility	Code word
------------------------------------
Very Poor	 111
poor		 10
moderate	 0
good		 110

Using a block code it will take 2 bits to transmit the information regardless of the visibility condition.

In the case of Huffman the average code length will be

(3bits x 0.1) + ( 2bits x 0.3) + (1bit x 0.5) + (3bits x 0.1) = 1.7 binary digits per code.

An average saving of 15%

Care is needed in choosing the Huffman codes so that the string of codes are uniquely decodable. We need to know when a code starts and finishes as they are no longer of a fixed length.

for example

110011110 = good,moderate,very poor, poor

In some situations the probabilities of events are know in advance but in the case of image data they have to calculated for each image before coding can commence. In most cases a coding tree or dictionary has to be constructed and included in the file so that compressed Huffman data can be decoded when the image file is opened on the computer. An example coding tree is attached. Because of the overhead of including the coding tree - dictionary, large size images benefit more than smaller ones.

By now I should imagine that you now know more about JPEG Baseline compression than you every wanted to know. Therefore in future posts I will focus on the practical aspects.

[Mick]

Thanks Rob, fascinating stuff.

Mick

[robski]

I am sure many of you have wondered how Tiff compares to Best Quality Jpeg Setting. Well lets say from the outset that Best Quality setting is not normally the Best Possible setting that could be used. The Application programmer has restricted you to a setting that optimizes compression ratio against little or no perceived loss in image quality. Accordingly applications of different versions and from different vendors will have a slight variance in compression ration and image quality. It's really down to what values they decide to use in their quantization tables.


In this post I am attempting to illustrate the difference between tiff and PhotoShop setting of 12, 9 and 5 within the limitations of using Jpeg attachments.

The first attachment compares the histograms of a tiff image and saved as Jpeg versions at settings of 12 (max quality) , 9 ( high quality ) and 5 ( medium quality ). The tiff histogram shows some very distinct and well defined areas of brightness levels in the image. The Jpeg max quality shows some deviation from the original tiff. The differences are there but not huge. Basically a number of pixels have slightly change their value. As the compression levels are increased to 9 and 5 a greater variance can be seen.

The second attachment is the image in question.

Next I took the original tiff file and subtracted the Jpeg version from it to produce a difference image. As the differences were lost in the darkness I then increased the brightness by 50%. I also show the histogram for each case.

With the setting of 12 the differences are barely noticeable and you have to amplify the image to make out which pixels differ.

With the setting of 9 and 5 the differences become more noticeable.

[Don Hoey]

Blimey Rob.

This has turned into a major article. I will have to read this through several times to absorb all the info. All very interesting.

Don

[robski]

Further to Post 35 on the question how does Jpeg max quality setting compare with the original Tiff. I have written a little utility program to compare each pixel in the tiff image against the jpeg version. The test image in Post 35 is 150 x 150 pixels = 22500 pixels.

The attached compares of the 3 versions of the saved as jpeg with settings of Max Quality, 9 and 5 against the original tiff. In the case of the Max Quality version some 90% of the pixels are the same as the tiff and the other 10% are within 1%.

[robski]

In my last posting the utility program compared the original tiff against various saved Jpeg versions. After a small modification to the program I was able to flag the offending pixels. A blue flag for pixels that errored by less than 2%. A green flag for those that errored between 2% and 10%. A red flag for those with an error of more than 10%. Error pixels are often referred to as Jpeg artifacts. See attached.

When the Jpeg Committee were considering various lossy compression schemes they took into account which scheme gave the best results for the type of images they wanted to handle. You may have been wondering why I had designed such an odd looking test image. I wanted to contrast gentle undulations with steep steps in levels running vertically, horizontally and diagonally. If you examine the Jpeg versions you will notice that the errors congregate around the steep steps especially those that run diagonally. This falls inline with the decisions made by the committee.

The point I am trying to make is that gentle undulating data is more suitable for Jpeg compression than black and white line art images or black text on a white background. This then leads into the subject matter of whether we should shoot in raw (Tiff) or Jpeg along with what Post Processing image storage formats we should used. It is not my intention to go down this avenue as it is a topic more than adequately covered elsewhere.

[robski]

Whilst I was in the mood for pixel peeping I thought I would investigate the other favourite question about Jpeg.
If I re-save a Jpeg will it degrade the image ? The question stems from those who only work in the Jpeg format when Post Processing.
If you scan forums where this question has been asked the reply will be yes it will discard information each time because of the lossy compression. But nobody has a feel as to what extent the image will degrade.

So I've taken a 760 x 760 pixel (577600 pixels) Tiff and saved it as Jpeg. I ran my program to compare the two images in the same manor as in previous Postings. I then opened and re-save the file. I repeated this operation 10 times on each occasion making no adjustment to the image. I ran the program again to compare the Tiff with the Jpeg file that was processed 10 times. I carried out this exercise at Max Quality and a Quality setting of 10. The results are below.

Compare Tiff with Jpeg 12 Max quality setting saved once
  450319 Pixels are identical to the original Tiff
  127267 Pixels error by less than 1 percent
      14 Pixels with  1 to 2  percent error
       0 Pixels with  2 to 5  percent error
       0 Pixels with  5 to 10 percent error
       0 Pixels with 10 to 15 percent error
       0 Pixels error by more than 15 percent

Compare original Tiff with Jpeg 12 Max quality setting saved 10 times
  362346 Pixels are identical to the original Tiff
  209950 Pixels error by less than 1 percent
    5303 Pixels with  1 to 2  percent error
       1 Pixels with  2 to 5  percent error
       0 Pixels with  5 to 10 percent error
       0 Pixels with 10 to 15 percent error
       0 Pixels error by more than 15 percent

Compare original Tiff with Jpeg 10 quality setting saved  once
  211658 Pixels are identical to the original Tiff
  294235 Pixels error by less than 1 percent
   69615 Pixels with  1 to 2  percent error
    2092 Pixels with  2 to 5  percent error
       0 Pixels with  5 to 10 percent error
       0 Pixels with 10 to 15 percent error
       0 Pixels error by more than 15 percent

Compare original Tiff with Jpeg 10 quality setting saved 10 times
  209957 Pixels are identical to the original Tiff
  295319 Pixels error by less than 1 percent
   70189 Pixels with  1 to 2  percent error
    2135 Pixels with  2 to 5  percent error
       0 Pixels with  5 to 10 percent error
       0 Pixels with 10 to 15 percent error
       0 Pixels error by more than 15 percent

[Mick]

Thanks Rob I was going to ask you that very thing about multiple compressions, nice to see some numbers attached to the process I did a little experiment the other day and re compressed an image 10 times and could see no difference, your numbers tell me why.

Mick