Activity 13 : Image Compression

(Welcome, Interwebs traveler. A note before you go: please click any image to view in enlarged/theater mode. Now explore on!)

This week, we code an image compression scheme based on Principal Component Analysis (PCA). Essentially, PCA takes sets of highly similar data, determines the pattern/similarities in the data, and expresses the similarities in a set of linearly uncorrelated values called the principal components [1,2]. From our AP186 and AP187 lectures, we know that we will then be able to reconstruct any of the data in the original data set using a linear combination of the principal components multiplied with the appropriate coefficients [3: AP186/AP187 lectures].

It should be noted (since in the past activities, I have been using MATLAB), I will be using Scilab here. This is due to the difficulty I have had in determining the appropriate function that corresponded to Scilab's pca() function. I mean, I was able to determine what PCA function was installed with my copy of MATLAB, however I was unsure of the output of the function. I felt it was wiser to (finally) install Scilab instead of running around blind with MATLAB.

So how will this compression scheme work? We first select a sample image. The picture shown in Figure 1 is a true-color image converted to a .png format in Activity 4. It has dimensions of 256 pixels x 256 pixels, and has a file size of 192 KB. Our goal is to use PCA in our compression scheme and reduce this file size.

Figure 1. Sample true-color image stored in PNG format.
Dimension in pixels is 256x256, and file size is 192 KB.

Compression Scheme (grayscale)

For our grayscale compression scheme, the sample image is converted to grayscale by taking the average of the intensity values found in the Red, Green and Blue channels. Figure 2 shows the result after conversion to grayscale in this manner.

Figure 2. Sample image converted to grayscale, still stored in PNG format.
Dimension in pixels is 256x256, and file size is 38.7 KB.

We then write a code which chops the image into blocks of 10 pixels x 10 pixels. Each block is concatenated into a column matrix, and the whole collection of blocks is combined into a single matrix X. X has dimension MxN, where M is the number of blocks from chopped from the sample image and N = 100 are the number of pixels per 10x10 block.

Since the dimensions of my sample image are not divisible by 10, we consider only the first 250 rows and 250 columns, effectively cropping the image to be of size 250x250 pixels. We then have M = 25x25 = 625 blocks with N = 100 elements per block. Thus, X is of dimension 625x100.

Applying PCA on matrix X using the Scilab function pca(x), we obtain the normalized principal components facpr, the set of coefficients comprinc, and the eigenvalues (found in the 1st column) and ratios of the corresponding eigenvalue over the sum of eigenvalues (found in the 2nd column) in lambda [4]. Figure 3 shows the principal components we obtained after PCA.

Figure 3. Principal components of the grayscale image.

To determine the principal components which contribute significantly to our image, we check the 2nd column of lambda and find all values greater than 0.001 or 0.1%. The results tell us that the first 18 principal components have values greater than 0.1%. This means the principal components beyond the 18th will have minimal contribution.

The grayscale image will be reconstructed by taking the product of facpr and comprinc, and we can set the number of principal components to be used in the facpr and comprinc. Figures 4 to 9 show the reconstructed image after the compression scheme, with 4, 8, 12, 16, 20 and 24 principal components. (I take the 20th and the 24th instead of the 18th to maintain the increment of 4.) The images are saved in PNG format using Scilab's imwrite.

Figure 4. Sample image after compression, reconstructed using 4 components.

Figure 5. Sample image after compression, reconstructed using 8 components.

Figure 6. Sample image after compression, reconstructed using 12 components.

Figure 7. Sample image after compression, reconstructed using 16 components.

Figure 8. Sample image after compression, reconstructed using 20 components.

Figure 9. Sample image after compression, reconstructed using 24 components.

Visually, we can see that using more principal components (as shown by 4-20 principal components) greatly enhances the reconstructed image. However, the change from the image by 20 and 24 principal components is minimal.

Checking the file size of each, we have the following:

• 4 components: 31.3 KB;
• 8 components: 34.2 KB;
• 12 components: 35.5 KB;
• 16 components: 35.9 KB;
• 20 components: 37.0 KB; and,
• 24 components: 37.5 KB.

So by the file size, we can see that the use of more principal components improves the quality of the reconstructed image at the expense of an increase in the file size.


Compression Scheme (colored)

For fun, we compress the sample image per channel and recombine them during reconstruction (after compression). Figures 10 to 15 show the reconstructed color image after the compression scheme, with 4, 8, 12, 16, 20 and 24 principal components. The images are saved in PNG format using Scilab's imwrite.

Figure 10. Sample image after compression, reconstructed in color using 4 components.

Figure 11. Sample image after compression, reconstructed in color using 8 components.

Figure 12. Sample image after compression, reconstructed in color using 12 components.

Figure 13. Sample image after compression, reconstructed in color using 16 components.

Figure 14. Sample image after compression, reconstructed in color using 20 components.

Figure 15. Sample image after compression, reconstructed in color using 24 components.

As with the grayscale images, the quality improves with increasing number of principal components. Again checking the file sizes:

• 4 components: 60.1 KB
• 8 components: 62.8 KB
• 12 components: 64.0 KB
• 16 components: 64.6 KB
• 20 components: 64.7 KB
• 24 components: 64.9 KB

The conclusion remains the same: in our compression scheme, the quality of the image improves (or the saved image is less lossy) at the expense of bigger file size.

Grading

Based on the criteria for grading, I believe I can give myself a 12/10 for completing the activity and for experimenting with compression in color (despite the color being a little off for the reconstructed images).