4

I found some help material and guided by it tried to implement PCA using SVD in MAtlab for image compression.

I did it in this way:

I = imread('1.jpg');
I2 = rgb2gray(I);
inImageD=double(I3);

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

C = S;

C(5+1:end,:)=0;
C(:,5+1:end)=0;

D=U*C*V';

And now D contain a matrix that looks like my image but kindly smoothed, but this matrix has the same dimesion as my start image. I expected that PCA will reduce not only number of features but also dimension..

Obviosly I do not understand something.

Well - reduction here means that I can restore initial data with some precision from matrices that much less than my data?

But multiplication of these matrices gives me matrix with same dimension as my initial matrix.

I want to use reduced data for training a classifier. In this case what I shloud use dor training?

In a ML course on Coursera we learned to use PCA with SVD for dimensionality redcution:

Steps:

1) Suppose we have four images 50x50. We did form a matrix X 4x2500; First step is normalazing this matrix: X(:,j) = X(:,j) - Mean(X(:,j));

2) Calculate covariance matrix: Sigma = (1 / m) * X' * X;

3) [U, S, V] = svd(sigma);

4) Obtain reduced examples of images: Zi = U'reduce * X(1,:); where Ureduce is subset of matrix U. If we had an image with 2500 pixels then with this action we can obtain an image of, for example, 1600 pixels(any number, depends of how many columns we will leave in Ureduce from U).

Il'ya Zhenin
  • 205
  • 1
    You did use the first five singular values only, and then you computed the five-dim reconstruction of the image. The compression consists of the five singular values, and the first five columns of $U$ and $V$. Those can be stored in fewer bytes than the originaol image, so it is a compression! – kjetil b halvorsen Mar 31 '14 at 08:55
  • You seem to be confusing scaling with compression. If you just want to reduce the dimensions, then just downscale your images. http://en.wikipedia.org/wiki/Image_scaling – TenaliRaman Mar 31 '14 at 09:37
  • Another example of low rank approximation, to augment the superb answer by @Mike Miller: https://math.stackexchange.com/questions/2205651/low-rank-approximation-with-svd-on-a-kernel-matrix/2207592#2207592 – dantopa May 18 '17 at 02:40

2 Answers2

1

You can indeed store the information with less data. The SVD gives the best $k$-rank approximation of the image. If we take the SVD of the image $I$, then $I = USV$, where $U$ and $V$ are the left and right singular vectors and $S$ is the matrix of singular values. We can then make the $k$-rank approximation by

$I = \sum\limits_{n=1}^k u_n \sigma_n v_n^T.$

WE can then make a good approximation with a fraction of the data. For example here's a $512$ $\times$ $512$ image of Lena. enter image description here

And here are a few low rank approximations to the image. You can see by $k=50$, we are getting something very similar visually which contains only $51250$ bit of information compared to $512^2$, just less than a quarter of the data.

enter image description here

Mike Miller
  • 2,453
0

The first part you have described is essentially right but not completely right. Compute the svd as you have done: $$ [U,S,V] = svd(inImageD); $$ Let $k$ be the number of singular values you would like to use. You have used $k=5$. I assume that you are using a rectangular $m \times n$ image where $m \ge n$.

Choose a rank $k$ for the compressed image. Let $$ U_k = U(:,1:k); $$ $$ V_k = V(:,1:k); $$ $$ S_k = S(1:k,1:k); $$ $$ D_k = U_k*S_k*V_k^t $$ The matrix (image) $D_k$ contains a new image formed from $k$ singular values. If $D_k$ does not contain enough features from the original image then increase $k$.

Note that $U_k$ and $V_k$ matrices have $m \times k$ and $n \times k$ elements, respectively and the diagonal matrix needs only $k$ elements. Thus, the reduced rank image can be stored using $k(m+n+1)$ elements. The original image needs $mn$ values. Thus, for small values of $k$ there is a high compression factor of $\frac{k(m+n+1)}{mn}$.

The second part: Compressing a series of images

Now we are trying to extract the features which common to all the images.

There is a major error in your course notes. I believe that the following algorithm will do what you intended to do. We again assume that the image size is $m \times n$ and there are $q$ number of images.

(1a) We form a "tall" matrix by stacking the $q$ matrices (images); we call it $A$. Thus, $A$ is an $mn \times q$ matrix. You may use the reshape command in Matlab to transform an image to a column. There are certain computational advantages in forming a "tall" matrix instead of a "fat" matrix. However, the algorithm is essentially the same for "tall" matrices and "fat" matrices.

(1b) Compute the mean pixel value as $a$ and remove it from $A$. $$ a = mean(A); $$ $$ A = A -ones(m*n,1)*a; $$ The removal of the mean is optional. A statistician will insist on doing this step. However, I am aware of engineers who do not remove the mean.

(2) This step is wrong and not required.

(3) [U,S,V] = svd(A); % as previously

(4a) Choose $k$ such that $k \le q$. Compute $D_k$ as previously which is an $mn \times q$ matrix (the same size as $A$).

(4b) If the mean was removed restore it. $$ D_k = D_k + ones(mn,1)*a $$ (4c) Take each column of $D_k$ and reshape that to an $m \times n$ image.

Vini
  • 526
  • 3
  • 9