The Singular Value Decomposition of an Image

Kristian Sandberg
Dept. of Applied Mathematics
University of Colorado at Boulder

Instructions

This lab is due February 14 in lecture. You are encouraged to discuss the lab with each other, but your solutions must be independently written using you own words and formulations.

Goal

The goals with this lab are:

1.
Illustrate how the singular value decomposition (SVD) can be used to analyze an image.
2.
Introduce the concept of image compression and see how the SVD can be used for image compression.
3.
Give practice in using Matlab for image processing.

Background

For an excellent introduction to how the SVD can be used in image processing, please read pp.16-21 in the article A Singularly Valuable Decomposition: The SVD of a Matrix by Dan Kalman [1].

The energy of an image

In many cases it is useful to associate an energy to an image. If we want to compress an image, we usually want to remove as much data as possible without losing too much energy of the image. The difference in energy between the original image and the compressed image is one possible way to design an error measure when compressing images. However, it is important to notice that this measure is not always appropriate as an error measure. In some cases the energy error measure might be small, while the visual error is terrible. One difficult problem in image processing is to find a good way of measuring error so that the error measure ``agrees with our eyes''. In other words, ``what you see is what you get''.

Let a digital image be represented as the $m\times n$ matrix I and denote its elements as Iij, $i=1,2,\ldots,m$ and $j=1,2,\ldots,n$. We define the Frobenius norm of the matrix I as

\begin{displaymath}\vert\vert I\vert\vert _{Fro}=\sqrt{\sum_{i=1}^m\sum_{j=1}^n\ \vert I_{ij}\vert^2}\ . \end{displaymath}

This is not the most common matrix norm, and not always very convenient, but it is related to the so-called L2-norm for functions (cf. l2-norm for sequences) which you will study later on in this course. The L2-norm (and the l2-norm) is related to the concept of energy and for this reason the Frobenius matrix norm is sometimes useful in image processing. Note that in our case when we work with matrices representing images our matrix elements are real.

Let Ic represent a compressed version of the image I. We define the relative (Frobenius) error Erel as

\begin{displaymath}E_{rel}=\frac{\vert\vert I-I_c\vert\vert _{Fro}}{\vert\vert I\vert\vert _{Fro}}\ . \end{displaymath}

Data compression

When we compress data, we already saw that we want some kind of measure of the error that the compression introduces. We also want a way to measure how efficient our compression is in terms of information we need to store.

Let nI be a number representing the the number of ``memory units'' we need to represent an image I and let nIc be a number representing the number of memory units we need to represent a compressed version of the image. (Here Ic denotes the compressed version of the image I.) We can now measure the compression efficiency as

\begin{displaymath}C=\frac{n_{I}}{n_{I_c}}\ . \end{displaymath}

Hence, C=1 means no compression at all and C=10 means that we only need 10% as much memory to store Ic compared to I. If C=10 we say that we have a ``compression ratio of 10:1''.

If you are interested in how to store a sparse matrix, i.e., a matrix with relatively many zeros, please see Digital Image processing[2] by Gonzales and Woods for a good introduction on how this can be done. However, this reading is not required for this lab.

Exercises

Here follows a few exercises that involve studying an image using the SVD. The exercises are explained with reference to Matlab, but as long as you can solve the problem in the exercise, you are free to use any software you like. When implementing your code you do not have to worry about making it ``super fast''. If you are a beginner in Matlab programming, it is important that you concentrate on learning how to use Matlab in order to solve a problem. Grading will be based on whether your code solves the problem or not.

Preparations

Before you start the exercises, please do the following:
1.
Down-load the image of ``campus and the rockies'' from the CU home page.
2.
Convert the image into an intensity (gray scale) image using the class double.
3.
``Cut out'' the upper left $256\times 256$ pixels of the image and name the matrix representing this part of the image I1 . Save this matrix by typing save I1 I1 in Matlab's command window. (Make sure to type I1 twice after save in order to specify that you want to save only the matrix you named I1 regardless of what other variables that are currently stored in Matlab's memory.)
4.
Down-load the image below:
5.
Convert the image into an intensity (gray scale) image using the class double.
6.
Name the matrix representing the gray scale image of the basket I2Save this matrix by typing save I2 I2 in the command window.
7.
Create a $256\times 256$ random matrix. To do this, type I3=rand(256);. You can learn more about this command by typing help rand in Matlab's command window.
8.
Convert the random matrix into an intensity (gray scale) image using the command mat2gray .
9.
Save the matrix representing the random image as I3.

Since we will compare the SVD performance on all these images it is important to use the same size ( $256\times 256$) and the same format (intensity) for all three images in order to obtain a fair comparison.

For instructions on how to do the above operations, please see the examples at the end of the work sheet Introduction to image processing in Matlab 1. For the exercises below I suggest you begin your code(s) with:

clear
load I1
load I2
load I3
 

You may also find the code for a function named redrank useful. You can down load it from here.

To display several images in the same window, use the command subplot. Type help subplot in the Matlab command window to learn more about this command.

Exercise 1: The SVD approximation of an image

Using the SVD (and, for example, the above mentioned function redrank), display a rank 1 approximation of the image I1 (the one of the rockies and campus). What can you say about the ``columns'' in the rank 1 approximation of the image in terms of linear dependence/independence? Does your image appear to agree that you indeed produced a rank 1 approximation?

Next, reconstruct your image using the SVD of rank 2, 4, 8, 16, 32, 64 and 128 respectively. Using the command subplot, plot all these approximations along with the original image in the same window for an easy comparison.

Exercise 2: The decay of the singular values

Make a plot which shows how the singular values decay along the diagonal of the matrix $\Sigma$ in the singular value decomposition $X=U\Sigma V^*$. In other words, plot the singular values against the position in the diagonal of S (i.e., your x-axis should include $i=1,2,\ldots,256$). Produce one such graph for each of the images I1 (campus), I2 (basket) and I3 (random) and put them together in the same plot. Label (you may do this by hand) each curve.

How do the singular values decay for the different images? You should find that the singular values for I3 (the random image) decay slower than for the other images. Any thoughts on why this happens?

Hint. You may find the following piece of code useful.

Exercise 3: Compression error

Approximate all the images with a rank 64 approximation (using the SVD). Compute the relative error using the Frobenius norm (use norm(image,'fro') in Matlab). Compare the relative errors between the images and discuss the results.

Exercise 4: Compression based on visual perception

How much can you compress I1 using the SVD such that your compressed image is ``almost'' perfect based on your eyes? How large did the rank need to be before it looked ``natural'' to your eyes?

Since each rank requires two vectors (of length 256 in our case) to be stored, each rank requires $2\times 256$ pieces of information to be stored. (Once we have stored these two vectors we can create the rank 1 matrix by forming their outer product.) The full image requires 2562 pieces of information to be stored. See Numerical Methods and Software[3] by Kahaner, Moler and Nash for more details.

Exercise 5: the Frobenius norm

For the image I1 verify (using Matlab) that

\begin{displaymath}\sqrt{\sum_{i=1}^{256}\sum_{j=1}^{256}\ I_{ij}^2}=\sqrt{\sum_{i=1}^{256}\sigma_i^2}\ . \end{displaymath}

Here I denotes the matrix representing I1 and $\sigma_i,\ i=1,2,\ldots,256$ denote the singular values of I.

Exercise 6: Illustration of the Frobenius norm

Reconstruct I1 using

a) a rank 100 approximation

and

b) using all but the first two singular values.

Compute the relative error in the Frobenius norm for both of the approximation. Does the result of the norm roughly agree with the error based on visual perception (in other words, ``based on your eyes'')?

Exercise 7: Compression based on the Frobenius norm

For each of the images I1, I2 and I3, how large does the rank need to be so that the relative error (in the Frobenius norm) is less than 10%? Discuss the poor performance of the SVD compression applied to the random matrix I3.

Format of your lab report

Write down your comments to all of the exercises above (word processed). Include the code(s) that you used as an appendix. You do not need to include every single code to every single run you did, but choose 2 or 3 codes that represent your programming work for this lab. Make sure to include comments in your code explaining what it does. Include any plots or images you need to justify your conclusions.

Questions?

In case you have questions regarding the material in this lab, do not hesitate to contact me at kristian.sandberg@colorado.edu or visit me during my lab hours Mondays 4:30-6 pm and Thursdays 4-5:30 pm in ECCR 143.

Lycka till!

References

[1] Dan Kalman A Singularly Valuable Decomposition: The SVD of a Matrix, The College Mathematics Journal, Vol. 27, NO. 1, January 1996.

[2] Gonzales R.C., Woods, R.E. Digital Image Processing, Addison-Wesley Publishing Company, 1992. (Note: I (Kristian) have a copy of this book in my office.)

[3] Kahaner D., Moler C., Nash S. Numerical Methods and Software Prentice Hall series in computational Mathematics, 1989 (Note: I (Kristian) have a copy of this book in my office.)

About this document ...

The Singular Value Decomposition of an Image

This document was generated using the LaTeX2HTML translator Version 98.1 release (February 19th, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -no_navigation svd.tex.

The translation was initiated by Kristian Sandberg on 2000-02-01

Kristian Sandberg
2000-02-01