The Singular Value Decomposition has many very useful applications, including one image compression technique that I’ll discuss in this post. I chose the following image of a baboon to serve as a demo: (click any thumbnail to get the full 298×298 image)

What we’re going to do is experiment with various SVD compressions of this 298×298 matrix. This baboon is currently represented as a matrix of values between 0 and 1, 0 being black and 1 being white. If we do the Singular Value Decomposition of this matrix, we get back three matrices, U, Σ and V. The Σ matrix consists of zeros, except with decreasing Singular Values on the diagonal. We can approximate this Σ matrix by keeping the first K Singular Values and throwing out the remaining (298-K) Singular Values. Throwing out the smallest Singular Values will have the least effect on the original matrix. By doing this, we are reducing the amount of data we need to store in Σ. As a consequence, we can discard some data in U and V, because Σ now contains rows with all zeros. Let’s do this in MATLAB!

img = double(imread(’baboon.bmp’))/255;
[a,b,c] = svd(img);
rank = [1 2 4 8 16 32 64 128];
for i = 1:length(rank)
    d = zeros(298);
    d(1:rank(i),1:rank(i)) = eye(rank(i));
    d = d.*b;
    imview(a*d*c’);
end

Let’s see the generated images:

Rank N means keep only the first N Singular Values out of 298 in the original Σ

Rank 1,2,4,8:

Rank 16,32,64,128:

The Rank 64 image looks very close to the original image. How much space does this compressed image use? Well, the original image is described in 298*298 = 88804 numbers. The Σ matrix can now be described with the first 64 numbers on the diagonal, because we’ve thrown out the rest. We also only need to store the first 64 rows of U and V, because the rest of these matrices are no longer relevant, as they would be multiplied by zero in the Σ matrix anyway. The first 64 rows of U and V each contain 64*298 = 19072 numbers. So, we can represent the compressed image in 19072 + 64 + 19072 = 38208 numbers, for U, Σ, V, respectively. This represents a compression ratio of 38208/88804 = 43%. Pretty good for a near-identical compression. If we are willing to sacrifice image quality, going with a smaller Rank such as 8 provides us with a still-recognizable image, with an extremely high amount of data compression.

Inspiration: http://www.uwlax.edu/faculty/will/svd/compression/index.html