DCT in image compression

Why?

I've been looking into WebP image compression again as part of thinking about doing stuff on the Rust image-webp library. This might involve some quite difficult stuff so I want to try to write down my thoughts clearly. This will be useful in having the explanations for myself but also anyone else who might come upon it. It also forces me to make sure I understand the concept properly if I can explain it to others. I can also test some web development ideas to try to create more interactive explanations.

What?

DCT stands for Discrete Cosine Transform and is used as one step in image compression for lossy images. Notably this includes JPEG, lossy WebP and AVIF. Note that both WebP and AVIF are based on video formats since lossy image compression is basically the same as video compression of a specific frame of a video. Video compression has extra complexity to make subsequent frames that have similarities to the previous frame more efficient but this isn't needed for single images so image compression is only based on keyframes or intraframes.

X_{k} = Σ_{n = 0}^{N - 1} x_{n} \cos [\frac{π}{N} (n + \frac{1}{2}) k] for k = 0, ... N - 1 .

This formula is one of the DCT formulae, doing the transform on each of the values on the input to give an output. Note that when k=0, the whole cos section will be cos(0) which is equal to 1. For other values of k, it gives different cosine amounts to multiply the input by to get the output. The idea is that each iteration of k gives different levels of precision so that lower values of k give a blurrier impression of the overall amount while the higher values of k encode more details.

For DCT on an image it will use a 2d version of the formula since it needs to be encoded across both dimensions. I will mostly focus on the 4x4 version of the transform here since it's simpler and easier to demonstrate. The larger the transform the more efficiently it can encode but it becomes much less accurate and slower to run, so it's a tradeoff. VP8 tends to only use 4x4 transforms.

The following shows the amount each element is contributed to from the input. So for example for the top left value of the output it is just the sum of all the input multiplied by 1(i.e. unchanged). This means it captures the overall value of the whole image while the rest of the matrix will have different combinations of the input to contribute to the value of the resulting matrix post-transformation. You can select different values on the right to see how it changes.

The following shows an example of how an example section would be mapped via dct. Note that these numbers are randomly distributed between 0 and 1 and they're brighter the higher they are so in some sense the top left value of the output is a measure of the brightness of the input.

The reason I focus so much on the top left one is that by concentrating the overall value of the matrix in one value, even after reducing the quality of this then increasing the quality it will still retain the overall quality of the image. Let's show how that works in the following. The default image is an image I took a while ago and had lying around. Also you can use your own image by clicking on the image in the top left. Note that it's not very efficient so if you use a large image it may lag your tab somewhat while it processes it.

Note that if you click the without DCT button the final image after dequantisation doesn't look anywhere near as clear. Part of this is an artifact of the way I'm doing quantisation since I'm using floating point numbers for this example so I round the values to a certain level of precision. It's the same process in each case though.

In the real world we wouldn't use floating point numbers for this, most images are displayed as 24 bit colour, which is 8 bit for each of red, green and blue although they tend to be encoded with the luma (greyscale) plane separated from the chroma (colour) planes. This is so the luma can be encoded with a higher level of precision since the human eye perceives differences in lightness more distinctly than changes in colours. The sums are also quite inefficient on floating point numbers as well as it not being exactly the same between different hardware so it makes sense to use fixed point versions of the algorithms that reduce the number of additions/multiplications required as well as avoiding doing the cosine function each time.