Activity 14 – Image Compression

Back in 2002, my siblings and I had a relatively high-end computer. It had specs (500Ghz, 80gig hard drive and 512mb RAM, a good video card) that were optimal for playing the newest game at that time, which was the graphics and memory intensive Warcraft 3. Making my setup wicked still is that it had two monitors, enabling me to chat and surf the web while at the same time playing Counter-Strike.

This set-up lasted for quite a few years. In fact, I’ve been using this computer until first year college. Through the years I pushed my use of its hard drive to the limit: I’ve reinstalled/changed its OS many times (Windows, Ubuntu, both), I partitioned the hard drive for different set-ups (for dual-booting, for media organization) and then I filled it with lots of stuff.

As I installed different games, captured more pictures, pirated more music (hehehe), downloaded more movies, the 80gig hard drive, I realized, was not enough with the demand for more storage. Even now that I own a 3 year old Macbook Pro with a hard drive of 160gig, I sometimes find this storage is not enough (as of now I only have 11.42 gigs left).

Of course, this demand was obvious to the computing community, and that is why different programmers developed different ways of compressing files. Zip, tar, rar, and all were basic solutions to compression of multiple files.

Another compression technique of interest is image compression.

Cameras are evolving rapidly: from pinholes to higher grade lenses, from film to memory card storage. In the next few years we expect that cameras can capture images of higher and higher resolution. But problem is, higher resolution also means more space occupied. To be able to optimize your storage, images must be compressed, though not at the expense of losing quality.

That is why the Joint Photographic Experts Group conceived the JPEG image format.

The JPEG compression algorithm is quite complicated and too technical, but one part of the algorithm catches our physicists’ eye for pattens. An image can be reconstructed with the help of the combination of patterns obtained from a Discrete Cosine Transform (DCT).

“The DCT transforms an 8×8 block of input values to a linear combination of these 64 patterns. The patterns are
referred to as the two-dimensional DCT basis functions, and the output values are referred to as transform
coefficients. The horizontal index is u and the vertical index is v.” [2]

As physicists, besides learning the DCT, we also learned Principal Components Analysis (PCA) to represent different sets of data. PCA basically decomposes our data into eigenvalues, eigenvectors, and principal components. Similar to DCT, these broken down information can be used to reconstruct the original dataset. What we do is simply combine some of these components to able to reconstruct the original image. I say “some” because yes, it is possible that we can use only a few components to represent the original data without significant loss.

And that is where the beauty of DCT and PCA lies. From these methods we can choose to use different combinations basis functions to reconstruct our original image. Along these combinations you can choose to use less basis functions to reconstruct. Less basis functions for reconstruction means less memory used.

Now we are ready to compress an image using PCA.

We first get an image that we want to compress and then convert it to grayscale. Upon conversion, we chop up the image into 10×10 regions. The chopped up images were then sampled using PCA, and then resulted to 100 basis functions, aka eigenimages representing the original image.

Notice that the components that the PCA method produced are similar to the components in the DCT method.

After obtaining our eigenimages, we use different combinations of the eigenimages multiplied to the principal components to get our reconstruction.

Above is the reconstruction using different numbers of eigenimages (the numbers are embedded on the photo as white text). Notice that even if we just used only 7 eigenimages, an accurate reconstruction is still produced. Quality then starts to decrease when we only used 4 eigenimages. Using 2 eigenimages for reconstruction, the quality then dramatically drops. But as seen in the last block, even 1 eigenimage can be used to reconstruct the image, though at low very quality (try squinting your eye, the image may still look like of high quality, hehe).

In theory, the image is already compressed because less eigenimages, meaning less information was needed to reconstruct the image.

I cannot make an analysis with regards to file size. Apparently, as you save your PCA compressed image using Scilab, it goes through another compression to make it JPG, effectively disregarding the previous compression we made.

Conclusion
Principal Components Analysis instead of Discrete Cosine Transform was used to compress an image. An image can be reconstructed using small basis functions called eigenimages. It is possible that 7 eigenimages may already be enough to compress the image without a significant loss in quality.

I give myself a grade of 10/10 for demonstrating knowledge of the subject and producing the needed results.

Acknowledgments

• Brian for helping me code.
• Joseph for also helping me code and the discussions about eigenimages.
• Dennis for insightful discussions and for sharing the frustration.
• Troy for the Adobe Photoshop tips.

References
1. M Soriano, “A14 – Image Compression”
2. http://en.wikipedia.org/wiki/JPEG
3. http://en.wikipedia.org/wiki/Principal_component_analysis

‘TIS DONE!