Techniques adopted for model reduction are used for image compression as well. In this case, they are useful to explain how model reduction works. In particular, we’re going to use Singular Value Decomposition (SVD) to compress an image!
First of all, the ingredients we are going to use for this recipe are: a grayscale image, some linear algebra math and a little bit of time. Regarding the software, we can use any kind of scientific package and in this case we’re going to use Mathematica from Wolfram since it allows for a quick and effective image manipulation as well as advanced math manipulation.
Step 1. The first step involves choosing the image. For the sake of simplicity, we’re going to use a grayscale image. Such images can be seen as matrices whose elements are number ranging from 0 to 1 and representing the level of grey corresponding to each pixel. The image we’ll use is this:
It is a nice picture of New York from the Staten Island ferry. It was converted to grayscale by discarding the colour information and it has a resolution of 642×398 pixels.
Step 2. We have to load this image into a Mathematica notebook and transform the data into a matrix. This is achieved with this command:
S = Image[ImportData[''SampleNY.jpg'']]
The matrix S has dimension m x n where m and n are the number of pixels in the horizontal and vertical direction, 642 and 398 respectively.
Step 3. The compression is performed calculating the singular value decomposition of the matrix S. Given S, its SVD decomposition is written as:
S = U w V*
and U w and V are obtained with the code
[U, w, V] = SingularValueDecomposition[S]
This results in a factorisation of the rectangular matrix S that resembles the eigenvalue decomposition of a square matrix. The columns of U and V are called left and right singular vectors, respectively, while the entries of the diagonal matrix w are the singular values. The entries of w are associated with the amount of information contained by each pair of singular vectors. We can sort the singular values since they are a measure of the energy contained in the corresponding singular pair. The compression is performed by assuming the image can be represented by the few most energetic singular vectors.
We can ask Mathematica to calculate the SVD decomposition and return a subset of singular vectors corresponding to the largest singular values. In particular, we can ask for the 10 singular pairs with the largest singular values:
[U, w, V] = SingularValueDecomposition[S,10]
Now, the matrices U and V contain only 10 singular pairs.
Step 4. The image is reconstructed using only these 10 singular pairs. The new data is calculated and stored in a new variable. In Mathematica, that becomes:
recS = U . w . Conjugate[Transpose[V]]
where the dot stands for the matrix product. The matrix recS has the same size of the initial S matrix which represents the full-quality image. However, in terms of memory the combined size of U, V and w is much smaller than the corresponding memory needed by S or recS.
Step 5. Reconstructing the image with few singular pairs means also discarding a large part of the information. In fact, we used the 10 most “energetic” pairs out of hundreds. We can visualise the effect of retraining only few singular pairs by showing the image reconstructed with just 10 of them:
As you can see, the main features of the picture are there but all the details are missing!
Step 6. Last but not least, we can play with the number of singular pairs we use to reconstruct the image. As already said, the largest singular value corresponds to the most important feature of the image. If we reduce the picture to just 1 singular value, we have:
Increasing the number of singular values from 1 to 5, things improve…
But we need at least 50 singular pairs to have a good result like this:
and if we increase the number to 100, we have the good result shown below which uses only 40% of the original memory!
Step 7. To summarise, the compression is obtained here by calculating the SVD decomposition of the image, discarding the majority of the singular pairs and retraining only a subset of them (the most important). In terms of storage memory, this subset needs just a fraction of the memory which would be required by the whole image!
Leave a Reply