Image Compression

As the title implies, this post/activity is all about compressing an image. This activity makes use of the concept of Principal Component Analysis (PCA). Images can be compressed using bases of sinusoids of different frequencies along the x and y axis. So basically, an image can be represented and then compressed by the superposition of weight basis images (PCA eigenfunctions, or in this case, eigenimages).

First of all, open an image in scilab as a grayscale image. For this post, consider the image in figure 1.

Figure 1: Grayscale image to be compressed. The image size is 480x640

The next step is to cut this image into 10x10 block images. Therefore 3072 10x10 block images are formed from figure 1. Then, concatenate each block by using img(:), given that img is a 10x10 block. The resulting matrix is a 3072x100 matrix, where 3072 indicates the number of 10x10 blocks and 100 indicates the number of pixels in that block.

Next is to apply PCA on the 3072x100 matrix, defined as the matrix x. PCA can be implemented in scilab by using the function pca(x). Upon implementation of the PCA, three matrices will be given ([lamda, facpr, comprinc]).

The first matrix, lamda, is a px2 matrix, where p is the number of variables/pixels (in this case, p = 100). The first column of this matrix gives the eigenvalues and the second column gives the ratio of that corresponding eigenvalue.

The second matrix, facpr, shows the principal factors or the eigenvectors.

The third matrix, comprinc, gives the principal components, or basically the coefficient corresponding to a certain eigenvector.

The idea is, depending on how many nonzero eigenvectors will be used to reconstruct the image, an eigenvector (from 1 column in fracpr) will be multiplied to its corresponding coefficient for all blocks (in this case 3072 blocks). For example, if only the top three eigenvectors (meaning these eigenvectors are the top three contributors) are used, then per block, only the three corresponding coefficients are used. Let an eigenvector be noted as V and its corresponding coefficient, c, again if only three V's are used then per block, (V1*c1 + V2*c2 + V3*c3) is computed to reconstruct that block. The resulting matrix, in this case, is a 3072x100 matrix, where, again, 3072 is the number of blocks and 100 is the result of (V1*c1 + V2*c2 + V3*c3). From this matrix, all the information needed to reconstruct the image have been gathered. The final step is to return each row (there are 3072 rows) into 10x10 blocks once again, and thus the image is reconstructed.

Compression occurs because, as stated earlier, only three eigenvectors are used, where as to fully reconstruct the image (meaning without loss), all 100 eigenvectors must be used.

The corresponding images are reconstructions of figure 1 by using different numbers of top eigenvectors.

Figure 2: Reconstruction by using only the top three eigenvectors. 297984 pixels are lost from 307200 pixels originally or 97% pecent loss.


Figure 3: Reconstruction by using only the top ten eigenvectors. 276480 pixels are lost from 307200 pixels originally or 90% pecent loss.


Figure 4: Reconstruction by using only the top 25 eigenvectors. 230400 pixels are lost from 307200 pixels originally or 75% pecent loss.


Figure 5: Reconstruction by using only the top 50 eigenvectors. 153600 pixels are lost from 307200 pixels originally or 50% pecent loss.


Figure 6: Reconstruction by using only the top 90 eigenvectors. 30720 pixels are lost from 307200 pixels originally or 10% pecent loss.


Figure 7: Reconstruction by using all the eigenvectors. 0 pixels are lost from 307200 pixels originally or 0% pecent loss.

The number of pixels lost can be computed by solving for the difference between the original number of pixels (in this case, 307200) and (the number of 10x10 blocks multiplied by the number of eigenvectors used). It can be observed that increasing the number of eigenvectors used decreases the number of pixels lost, but, it can also be observed from the images that at a certain number of eigenvector, the reconstructed image is already as identical as the original image (meaning, even with a number of pixels lost, the reconstructed image can still represent the original image) and this is the basis of compressing an image. Certain information or pixels are lost without greatly affecting the quality of the image.

Below is the source code used for this activity

//open the image and convert to grayscale
image = imread('C:\Documents and Settings\andy polinar\Desktop\ap 186\activities\activity 14\shadespic.jpg');
I = (image(:,:,1)+image(:,:,2)+image(:,:,3))/3;

simage = size(image);

//vectorizing the image, producing x
k = 0;
for r = 1:(simage(1)/10)
for c = 1:(simage(2)/10)
itemp = I(((10*r-9):(10*r)),((10*c-9):(10*c)));
xtemp = itemp(:);
k = c + (r-1)*(simage(2)/10);
x(k,:) = xtemp';
end
end

//implementing pca
[lambda,facpr,comprinc] = pca(x);

vectors = 90; //indicates the number of top eigenvectors to be used
scomprinc = size(comprinc);
sfacpr = size(facpr);
redim = zeros(((simage(1)*simage(2))/100),100);
for rcomprinc = 1:scomprinc(1);
temp = zeros(100,1);
for cfacpr = 1:vectors
mrc = facpr(:,cfacpr)*(comprinc(rcomprinc,cfacpr));
temp = temp+mrc;
end
temp = temp';
redim(rcomprinc,(1:100))=temp;
end

//reconstruction of the image
y = zeros(simage(1),simage(2));
k=0;
for r = 1:(simage(1)/10)
for c = 1:(simage(2)/10)
k = c + (r-1)*(simage(2)/10);
xtemp=redim(k,:);
y(((10*r-9):(10*r)),((10*c-9):(10*c))) = matrix(xtemp,10,10);
end
end

//computing for the number of pixels lost
originalmem = simage(1)*simage(2);
newmem = ((simage(1)*simage(2))/100)*vectors;
lost = originalmem - newmem;
lostpercent = ((originalmem - newmem)/originalmem)*100;

I would like to acknowledge my discussions with Arvin Mabilangan and Dr. Maricor Soriano.

--
Technical Correctness: 5/5
Quality of Presentation: 5/5