Image filtering via SVD

Here is an application of the singular value decomposition (SVD), and particularly of the expansion of a matrix into the sum of rank one matrices. I started with the picture of a famous bird, which I have as the file bigbird.jpg in the JPG format:

Using IrfanView I converted this file to a 147x104 matrix of integers between 0 and 255 (1 greyscale byte per pixel). Here's some of the details. Save bigbird.jpg as bigbird.pgm (Portable Graymap) with the ASCII encoding option. The resulting file bigbird.pgm is essentially (after a few lines of topmatter) a list of (147)(104)=15,288 numbers between 0 and 255. If you check the file bigbird.pgm, you will see that the header specifies that there are 104 columns and 147 rows. Starting with the first row of 17 numbers, count off 104 numbers (6 rows plus the first 2 entries in the 7th row) represents the first row of pixels in the bigbird image. Using an ASCII editor (Notepad will do if the file isn't too large) delete the header material in bigbird.pgm and call the resulting file bigbird.txt (or anyother name you wish to distinguish it from bigbird.pgm).

I used the following sequence of MATLAB commands to read in bigbird.txt:

fid=fopen('bigbird.txt','r');
a=fscanf(fid,'%4d',[104,147])';
fclose(fid);

(The command "fscanf" is a C statement. In C matrices are stored column by column. Also, recall that ' indicates transpose.)
Now compute the singular value decomposition of the matrix a:

[u,s,v]=svd(a);

Click here to see all 104 singular values in decreasing order. Next use just the first 5 singular values to compute the weighted sum of outer products:

c=0;
for i=1:4
   c=c+s(i,i)*u(:,i)*v(:,i)';
end
c=round(c);

The "round" command insures that the entries of the matrix c are integers.
Finally, write c to an ASCII file to which I can add back the header material. I used the following code to write bigbird_04.txt:

fid=fopen('bigbird_04.txt','w');
out=fprintf(fid,'%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d%4d\n',c');
fclose(fid);

This saves the result using only the 4 largest singular values. Then I converted the numbers back into PGM format by replaced the exact header from bigbird.pgm, and viewed the resulting picture file with xv again. I tried this with varying numbers of retained singular values -- not only 40, but also 20, 10, 8, 5, 2 and 1. These are my results (converted to jpg's):

all 104 values	1 value	2 values	5 values
8 values	10 values	20 values	40 values

As you can see, not all 104 singular values are needed to recover the original picture, at least to the human eye. Using only 40 seems to do a sufficient job.Let's calculate the image compression rate represented by this replacement. Using 40 singular values means representing the matrix by the sum of 40 rank one matrices. For each of the latter we need to remember a length 147 column vector of bytes (numbers between 0 and 255) and a length 104 row vector, plus one more number (the singular value). The total number of bytes is 40(147+104+1) = 10080. This is about a 34% reduction from 15,288, the original number of bytes needed. If we use only the largest 20 singular values, only 5040 bytes are needed, which represents a 67% reduction, although the reconstructed picture is somewhat degraded. This is a demonstration of the use of the SVD for filtering purposes. It is far from the best way to compress images. The jpg format is the current standard for compressing and transmitting images across the internet and to and from satellites where bandwidth is limited. It uses Fourier analysis along with several other tricks that are well-tuned to the physiology of the eye. In addition, jpeg packs the pixel bytes into a file in a much more efficient format than the list of 147x104 integers separated by spaces that PGM uses.

Back to Math 203 Home Page