In this project, we are going to implement image compression using singular value decomposition method.
We are going to use matlab for this project!
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix that generalizes the eigendecomposition of a square normal matrix to any matrix via an extension of the polar decomposition.
Specifically, the singular value decomposition of an complex matrix M
is a factorization of the form , where U is an
complex unitary matrix,
is an
rectangular diagonal matrix with non-negative real numbers on the diagonal,
and V is an complex unitary matrix. If M is real, U and
are real orthogonal matrices.
The diagonal entries of
are known as the singular values of M. The number of non-zero singular values is equal to the rank of M. The columns of U and the columns of V are called the left-singular vectors and right-singular vectors of M, respectively.
The SVD is not unique. It is always possible to choose the decomposition so that the singular values are in descending order. In this case,
(but not always U and V) is uniquely determined by M.
As the Eckart-Young theorem says, we can approximate A by a low rank matrix Ak:
A = σ1v1u1 + σ2v2u2 + … + σnvnun, where σ's are the diagonals of ∑, v's are the entries of V
and u's are the entries of U
so Ak = σ1v1u1 + σ2v2u2 + … + σkvkuk , k<n
Let's read an image from our choice :
% I loaded a color image
RGB = imread('cat.jpg');
% covert image to grayscale image
A = mat2gray(RGB);
A = rgb2gray(A);
% resize the image : 512 by 512
A = imresize(A,[512 512]);
The image is a matrix 512 by 512. Every pixel is represented in the matrix by a number from 0 to 512. We are looking for compressing that image using SVD image compression method. Using this method, we will retrieve some information from the image but the image quality have to remain good.
Now let's perform svd on the matrix A:
[U, S, V] = svd(A);
Now we have the three matrices needed!
Let's take the singular values be runnig the following line of code:
[U, S, V] = svd(A);
Now let's approximate our matrix A by a low rank matrix Ak using diffrent values for k:
%k = 1, 10, 100 later on we will try all those values
k = 1;
Ak = U(:,1:k)*S(1:k,1:k)*V(:,1:k)';
%plot the original image next to compressed one
subplot(1,2,1);
imagesc(A); colormap gray; axis image; title('ORIGINAL');
subplot(1,2,2);
imagesc(Ak); colormap gray; axis image; title('1-image');
After executing the code, here is our result for k=1 :
Now let's set k=10:
As we increase k value the quality of the compressed image get well.
Now we will try k = 100:
The bigger k is, the more Ak approaches to A, this means that as k increases, the error of A - Ak gets smaller so the image gets clearer.
To understand better this, let's plots the singular values:
sv = diag(S);
plot(sv),title('Singular Values of the Image'),xlabel('Index'),ylabel('Singular Value')
We are observing that many singular values are quit small or equal to zero. The other singular values take big values from the first to the 100st singular value.
Even if we retrieved some of them, this gave us a good approximation to original matrix A which means that we will have a good compressed image.
The first 100 singular values are quit big so ‖A − A100‖ will be quite small because σ1 ≥ σ2 ≥ σ3 ≥ … ≥ σn . A100 is a good approximation for A.