31. Change of Basis; Image Compression
Watch on YouTube →
Overview
The lecture connects change of basis to lossy image compression: representing 8×8 pixel blocks in a Fourier-style or wavelet basis concentrates much of the signal into a few coefficients that can be retained while small ones are discarded. It then develops the linear algebra behind coordinate changes, showing how a transformation’s matrix changes by similarity and why an eigenvector basis makes that matrix diagonal.
Key takeaways
- A 512×512 grayscale image contains 262,144 pixel coordinates, but spatial correlation lets a transform basis represent much of its information with far fewer significant coefficients.
- JPEG-style compression separates an exact coordinate transform from lossy thresholding: transforming 64 pixels into 64 coefficients loses nothing, while setting small coefficients to zero creates compression.
- A useful compression basis must balance two properties: fast forward and inverse transforms, and concentration of the signal into a small number of coefficients.
- For an orthonormal wavelet matrix W, the inverse transform is Wᵀ, so fast multiplication by W also enables fast reconstruction.
- A linear transformation’s matrix depends on the chosen basis; matrices for the same transformation in different bases are similar.
- When a basis consists of eigenvectors, the transformation matrix is diagonal, but computing that basis may cost more than using practical fast transforms such as Fourier or wavelet methods.
Chapters
- A 512×512 grayscale image is a vector with 262,144 pixel values, each typically represented with 8 bits.
- A color image needs three values per pixel, or 3×512² coordinates.
- The lecture distinguishes lossless representation changes from lossy compression that deliberately discards information.
- Neighboring pixels often have similar gray levels, so pixel values contain strong spatial correlation.
- A blank or nearly uniform blackboard image is poorly represented as hundreds of thousands of separate pixel values.
- A basis containing a constant vector of all ones can represent a uniform image with a single coefficient.
- JPEG divides a large image into 8×8 blocks, transforming each block’s 64 pixels independently.
- Each block is rewritten using 64 basis vectors, including a constant, zero-frequency component and higher-frequency patterns.
- The lecture presents the Fourier basis as a useful model for this transform; practical JPEG uses a closely related discrete cosine transform.
- Changing from pixels to 64 transform coefficients is lossless because it only changes coordinates.
- Lossy compression follows by thresholding small coefficients to zero, preserving the large coefficients that carry most visible structure.
- If only three of a block’s 64 coefficients are needed for reconstruction, the example gives a compression ratio of about 21:1.
- Digitized fingerprint images need compression and indexing so a large archive can be searched in minutes rather than through physical files over a week.
- The lecture describes fingerprints being sent to a facility in West Virginia for digital compression and indexing.
- Video frames are highly correlated over time, so prediction can encode a previous frame plus a compressed correction instead of treating every frame as unrelated.
- The 8-dimensional wavelet example starts with an all-ones vector, then uses patterns with four-versus-four and two-versus-two blocks of positive and negative entries.
- The remaining vectors localize one-positive, one-negative pairs at different positions, producing eight basis vectors for R⁸.
- A rapidly alternating pattern can be expressed as a sum of the four localized wavelets, illustrating how the basis captures different scales.
- The pixel vector P is expressed as a linear combination of wavelet basis vectors, with coefficients collected in C.
- Placing the eight basis vectors in the columns of W gives P = WC, so the transform coefficients are C = W⁻¹P.
- This coordinate conversion preserves the signal exactly until a later compression step removes selected coefficients.
- A practical basis must support fast multiplication by both W and W⁻¹; the Fourier transform has the Fast Fourier Transform, and wavelets have a fast wavelet transform.
- The illustrated wavelet vectors are orthogonal, and normalizing them makes W orthonormal, giving W⁻¹ = Wᵀ.
- A useful compression basis must also concentrate the signal in a few coefficients; simply retaining a few standard-basis pixel values would badly damage the image.
- A linear transformation T is independent of coordinates, but its matrix depends on the basis used to represent input and output vectors.
- Matrices A and B for the same transformation in two bases are similar, related by a change-of-basis matrix M and its inverse.
- Changing basis affects both vector coordinates and the matrix that describes T in those coordinates.
- To construct T’s matrix in a basis v₁ through v₈, apply T to each basis vector and place the output’s basis coordinates in the corresponding column.
- Linearity makes those eight outputs sufficient to determine T on every vector in the space.
- If the basis vectors are eigenvectors with T(vᵢ) = λᵢvᵢ, the matrix is diagonal with eigenvalues λ₁ through λ₈ on the diagonal.
- Eigenvector coordinates are ideal for simplifying a transformation, but finding them can be too computationally expensive for image compression, motivating fast alternatives such as wavelets.
Transcript excerpt
0:07 OK. So, coming nearer the end of the course, this lecture will be a mixture of the linear algebra that comes with a change of basis. And a change of basis from one basis to another basis is something you really do in applications. And, I would like to talk about those applications. I got a little bit involved with compression. Compressing a signal, compressing an image. And that's exactly change-of-basis. And then, the main theme in this chapter is th- the connection between a linear transformation, which doesn't have to have coordinates,
0:56 and the matrix that tells us that transformation with respect to coordinates. So the matrix is the coordinate-based description of the linear transformation. Let me start out with the nice part, which is just to tell you something about image compression. Those of you -- well, everybody's going to meet compression, because you know that the amount of data that we're getting -- well, these lectures are compressed. So that, actually, probably you see my motion as jerky? Shall I use that word? Have you looked on the web? I should like to find a better word.
1:46 Compressed, let's say. So the complete signal is, of course, in those video cameras, and in the videotape, but that goes to the bottom of building nine, and out of that comes a jumpy motion because it uses a standard system for compressing images. And, you'll notice that the stuff that sits on the board comes very clearly, but it's my motion that needs a whole lot of bits, right? So, and if I were to run up and back up there and back, that would need too many bits, and I'd be compressed even more. So, what does compression mean?
2:36 Let me just think of a still image. And of course, satellites, and computations
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, MIT OpenCourseWare.