Approach

Approach

To compress an image using SVD, we followed the approach below:

Step One: Read in image

First thing we needed to do was read in our original image.

Step Two: Apply SVD appropriately

If our image was grayscale, we could just apply SVD normally. However, if our image was in color we need to consider the separate RGB channels. So, SVD would be applied for each color.

Step Three: Isolate first k singular values in Σ

Depending on what was selected, we would need to retain the first k (must be a positive integer less than or equal to the rank of our original image matrix) singular terms in Σ. All other terms (k+1  through the rest of the matrix) would be replaced with zero. The reason why this is done is to ensure that the most important pieces that help us reconstruct our image are used, while the lesser terms are removed to ensure compression. It should be noted however, that there is a tradeoff with the selection of k. The higher we select our k, the more terms we’ll use to reconstruct our image. This results in a better less compressed version of the original image. The lower we select our k, the less terms we’ll be using. So, although our image will be more compressed, the quality will suffer. Because of this we must wisely choose our k to acquire an image that both looks close to the original and is greatly compressed. 

Step Four: Multiply UΣV^T

After modifying our Σ matrix, we can multiply it with the U and V^T matrices obtained through SVD. 

Step Five: Store and Display

If our original image was grayscale, we can store our newly compressed image and display it. If our image was in color, we first have to recombine the different channels into one matrix. With that completed, we can store our newly compressed image and display it as well.

Step Six: Compression Ratio

Since we have both the original image and the compressed image, we can find the compression ratio. In general the compression ratio is calculated as:

Our uncompressed (original m x n) image matrix consists of mn terms. Our compressed image is composed of three different matrices:  U, Σ, and V^T. U has mk non-zero terms.  V^T has nk non-zero terms. And because Σ is a diagonal matrix, it only contributes k non-zero terms. So our compressed image matrix has a total of mk + nk + k terms, or k(m+n+1) terms. Therefore, our compression ratio now looks like:

Once the ratio is calculated, we can interpret our results. The larger the ratio is, the greater the image is compressed. The smaller the ratio is the less the image is compressed.

Something that was observed through the results, however,  was that if the k selected was too large, the compressed image would actually be larger than the original. To ensure this doesn’t happen, we needed to be conscious with our pick of k. Using the compression ratio above, we established the following inequality to guarantee that our compressed image would be smaller: