{"id":178,"date":"2017-09-11T20:17:47","date_gmt":"2017-09-11T19:17:47","guid":{"rendered":"http:\/\/www.science-now.org\/giampaolo\/?p=178"},"modified":"2018-08-21T14:16:38","modified_gmt":"2018-08-21T13:16:38","slug":"image-compression-with-svd","status":"publish","type":"post","link":"https:\/\/www.science-now.org\/giampaolo\/2017\/09\/11\/image-compression-with-svd\/","title":{"rendered":"Image compression with SVD"},"content":{"rendered":"

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!<\/p>\n

<\/p>\n

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\u00a0a quick and effective image manipulation as well as advanced math manipulation.<\/p>\n

Step 1.<\/strong> 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:<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

Step 2<\/strong>. We have to load this image into a Mathematica notebook and transform the data into a matrix. This is achieved with this command:<\/p>\n

S = Image[ImportData[''SampleNY.jpg'']]<\/pre>\n
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.<\/p>\n
Step 3.<\/strong>\u00a0The compression is performed calculating the\u00a0singular value decomposition of the matrix S. Given\u00a0S, its SVD decomposition is written as:<\/p>\n
S = U w\u00a0V*<\/pre>\n
and U w and V are obtained with the code<\/p>\n
[U, w, V] = SingularValueDecomposition[S]<\/pre>\n
This results in a factorisation of the rectangular matrix S that resembles the eigenvalue decomposition of a square matrix. \u00a0The columns of\u00a0U 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\u00a0information 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.\u00a0The compression is performed by assuming the image can be represented by the few most energetic\u00a0singular vectors.<\/p>\n
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\u00a010 singular pairs with the largest\u00a0singular values:<\/p>\n
[U, w, V] = SingularValueDecomposition[S,10]<\/pre>\n
Now, the matrices U and V contain\u00a0only 10 singular pairs.<\/p>\n
Step 4.<\/strong> The image is reconstructed using only these 10 singular pairs. The new data is calculated and\u00a0stored in a new variable. In Mathematica, that becomes:<\/p>\n
recS\u00a0= U . w . Conjugate[Transpose[V]]<\/pre>\n
where the dot stands for the matrix product. The matrix recS\u00a0has 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 \u00a0is much smaller\u00a0than the corresponding memory needed by S or recS.<\/p>\n
Step 5.<\/strong> 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.\u00a0We can visualise the effect of retraining only few singular pairs by showing the image reconstructed with just 10 of them:<\/p>\n
\"\"<\/p>\n
As you can see, the main features of the picture are there but all the details are missing!<\/p>\n
Step 6.<\/strong> Last but not least, we can play with the number of singular pairs\u00a0we use to reconstruct the image. As already\u00a0said, 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:<\/p>\n
\"\"<\/p>\n
Increasing the number of singular values from 1 to 5, things improve…<\/p>\n
\"\"<\/p>\n
But we need at least 50 singular pairs to have a good result like this:<\/p>\n
\"\"<\/p>\n
and if we increase the number to 100, we have the good result shown below which uses only 40% of the original memory!<\/p>\n
\"\"<\/p>\n
Step 7.<\/strong> To summarise, the compression is obtained here by calculating the SVD decomposition of the image,\u00a0discarding the majority of the singular pairs and retraining only a subset of them (the most important). In terms of storage\u00a0memory, this subset needs just a fraction of the memory which would be required by the whole image!<\/p>\n","protected":false},"excerpt":{"rendered":"
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!<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[29,28,27],"class_list":["post-178","post","type-post","status-publish","format-standard","hentry","category-programming","tag-image-compression","tag-model-reduction","tag-singular-value-decomposition"],"_links":{"self":[{"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/posts\/178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/comments?post=178"}],"version-history":[{"count":3,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/posts\/178\/revisions"}],"predecessor-version":[{"id":197,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/posts\/178\/revisions\/197"}],"wp:attachment":[{"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/media?parent=178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/categories?post=178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.science-now.org\/giampaolo\/wp-json\/wp\/v2\/tags?post=178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}