His Story

Introduced by one of best friend, Sui Huang, I recently learned how to use svd function in Matlab to compress an image, which in my opinion is easier to be understood and implemented. Instead of the algorithm inside svd, only its usage is discussed below.

svd is a function which allows any matrix M with arbitrary size m by n, to be decomposited into 3 matrices, U (m by m), S (m by n) and V (n by n), such that

M = U * S * V'.

S is a diagonal matrix with its non-negative elements sorted in decreasing order diagonally, whereas U and V are unitary matrices. Note that those elements with larger value in S are more important to the content of an image. The idea of compressing the image is that only first number of diagonal elements in S, with corresponding columns and rows in U and V are saved. Other elements in these matrices are not saved since they are less important to the image content. Depending on different saving selections, the quality of the image varies. The actual steps of compressing and restoring an image are shown in the following Matlab statements.

First we use imread function to read a image into matrix M. Since usually the given image contains 3 layers, red, green and blue, to simplify the steps, we assume that only one layer, M, is to be compressed:

[M1, M2, M3] = imread (’filename‘,’format‘);
M = double (M1);


Here filename is the file name of the image and format is the image type of the filename, such as jpg, gif and etc.

Next, we use svd to decompose M into three matrices:

[U, S, V] = svd (M);

and we trim each of them with only first 10 valuable columns and rows saved:

U = U(:, 1:10);
V = V(:, 1:10);
S = S(1:10, 1:10);


Now we restore the image using new U, V and S matrices, and save it to a file:

M = U * S * V';
M1 = uint8 (M);
imwrite ([M1, M2, M3], ‘filename‘, ‘format‘);


Thanks Sui for providing the full source code. With variable r in the code set to 20 and 10 respectively, given an input image, two output images were generated:

As can be seen, the qualities of output images are very low, thus cannot be used in any image processing tasks that have high demands on picture quality, since this method just manipulate matrices, with no image analyzing at all. But still, it is possible to combine with other image processing techniques together, to compensate its weakness, and become useful for programs such as object recognition and video streaming.

Update:

According to the comments, we can use Lanczos method to compute “only large singular values and singular vectors (columns of U and V are actually singular vectors)“, to simply the calculation and save more memory during the process. Thanks to Sui Huang and Dr. Qiao.

This entry was posted on Monday, November 14th, 2005 at 9:32 am and is filed under English, Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.