# Change of basis for image compression (toy example)

In linear algebra course, prof. Strang uses JPEG image compression as an example of basis change (lecture 31). I would like to make sure that I understood the concept.

For simplicity, let's assume that we deal with 1-dimensional 8-pixels image vector (greyscale). In the original (uncompressed) form we represent the image using standard basis (see below). So, in the original form, for the image of 8 pixels we will save 8 coefficients that are just greyscale values. In the compressed form, instead of standard basis we represent our image using some other basis (Fourier, DCT etc). Now, if we use all 8 coefficients in this new basis we can lossless reconstruct the original image. Critically, some of these coefficients have small values so we can drop them without compromising too much image quality in reconstruction. So, we can save only let's say 4 coefficients, achieving 50% compression rate.

Does this makes sense?

If someone can also explain how this logic is generalized to 2D I will appreciate. At the end, we probably do not want to make 1D column vector from 2D because we loose information about proximal pixels in X direction. For example, suppose I have 100x100 matrix. If I concatenate by 2D data into 1D, the values at position 1 and 2 as well as 1 and 101 will likely have similar values. Is the basis constructed in such way that it somehow takes this into account?

Thanks!

• What you described is exactly what happens. In 2D, all you just have longer vectors (you just concatenate all the rows and make a longer, 1D, vector
– 5xum
Sep 1, 2017 at 10:10
• Thanks, but the 2D question is not fully clear to me (I updated my question). Sep 1, 2017 at 10:22
• Yes something like that. But there are also quantization coefficients which are adapted to how the DCT interacts with the human visual system. Then after the quantization step there is an entropy coder which uses source coding in which the actual compression is achieved. So nothing is actually "totaly dropped", it is just selectively important as decided by the quantizer and it's coefficients. Sep 1, 2017 at 10:23
• It's not clear what your question is. Sep 1, 2017 at 10:26
• For the second part, it is natural to use a complete two dimensional basis (such as $${e^{i(n{k_x}x + m{k_y}y)}}$$ for integer numbers n and m) Sep 1, 2017 at 10:28

The idea is to think of a $(m \times n)$-grayscale image as an $(m\times n)$-matrix. In the standard basis for the vector space of $(m\times n)$-matrices (matrices with a $1$ in the $(i,j)$-position and $0$ everywhere else), the coefficient of each basis element contains the same amount of information, namely it gives us the value of a single pixel. The idea of image-compression algorithms, which is mind-boggling really, is to choose a basis with respect to which the coefficients for the first few basis vectors are much more important than the coefficients of subsequent basis elements. So the first few coefficients might give you 99% of the information you want about the image, and the remaining coefficients just 1% of what you care about.