Image Compression with Singular Value Decomposition

November 10, 2016
By

(This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers)

As mentioned in a previous post, image compression with singular value decomposition is a frequently occurring application of the method. The image is treated as a matrix of pixels with corresponding color values and is decomposed into smaller ranks that retain only the essential information that comprises the image. In this example, we are interested in compressing the below 600×337 image of a lion into a real-valued representation of the picture which will result in a smaller image file size.

image of a lion

The method of image compression with singular value decomposition is based on the idea that if the SVD is known, some of the singular values \sigma are significant while the others are small and not significant. Thus, if the significant values are kept and the small values are discarded then only the columns of U and V corresponding to the singular values are used. We will see in the following example, as more and more singular values are kept, the quality and representation compared to the original image improves.

Image Compression with Singular Value Decomposition

The jpeg package provides handy functions for reading and writing .jpeg files which we will need to turn the image of the lion into a matrix.

library(jpeg)

The readJPEG function is used to convert the image into a matrix representation.

lion <- readJPEG('lion.jpg')
ncol(lion)
## [1] 600
nrow(lion)
## [1] 337

The output of the function gives an array of three matrices with 337 rows and 600 columns, the same size as the image. Each matrice represents a color value that comprises the RGB color scale. To perform SVD on these matrices, first separate the array into separate objects.

r <- lion[,,1]
g <- lion[,,2]
b <- lion[,,3]

SVD is then performed on the extracted matrices that represent the individual RGB color values.

lion.r.svd <- svd(r)
lion.g.svd <- svd(g)
lion.b.svd <- svd(b)

Collect the results into a list that we will use to reconstruct the original image.

rgb.svds <- list(lion.r.svd, lion.g.svd, lion.b.svd)

With the singular value decompositions computed for the RGB color value matrices, we can take the resulting matrix factorizations and reconstruct the original matrix (image) as we saw in the previous post on SVD as we know that A = U\Sigma V^T.

As mentioned at the beginning of the post, the more significant singular values we keep results in a more accurate approximation of the original matrix. We can see this in action below. The following code takes each decomposed color value matrix and reconstructs the color value array that comprises the original lion image with increasing ranks. The loop will approximate the original image with eight different rank values starting from rank 3 to rank 300. The writeJPEG() function from the jpeg package takes the approximated color value array and writes it to a .jpeg.

for (j in seq.int(3, round(nrow(lion), -2), length.out = 8)) {
  a <- sapply(rgb.svds, function(i) {
    lion.compress <- i$u[,1:j] %*% diag(i$d[1:j]) %*% t(i$v[,1:j])
  }, simplify = 'array')
  
  writeJPEG(a, paste('compressed/lion_compressed', '_svd_rank_', round(j,0), '.jpg', sep=''))
}

Rank 3

Rank 3 lion image

With just three singular values remaining the resulting image retains very few of the original image’s characteristics.

Rank 45

Rank 45 lion image

At just rank 45, the resulting image is much more representative of the original.

Rank 88

lion_compressed_svd_rank_88

Rank 130

Rank 130 lion image

Rank 173

Rank 173 lion image

Rank 215

Rank 215 lion image

Rank 258

Rank 258 lion image

At rank 300, the resulting compressed image is rather unrecognizable from the original (at least to me).

Rank 300

Rank 300 lion image

We can then see how much the SVD compressed the image by finding the percent difference of the compressed images and the original.

original <- file.info('lion.jpg')$size / 1000
imgs <- dir('compressed/')

for (i in imgs) {
  full.path <- paste('compressed/', i, sep='')
  print(paste(i, ' size: ', file.info(full.path)$size / 1000, ' original: ', original, ' % diff: ', round((file.info(full.path)$size / 1000 - original) / original, 2) * 100, '%', sep = ''))
}
## [1] "lion_compressed_svd_rank_130.jpg size: 36.608 original: 52.05 % diff: -30%"
## [1] "lion_compressed_svd_rank_173.jpg size: 37.144 original: 52.05 % diff: -29%"
## [1] "lion_compressed_svd_rank_215.jpg size: 37.559 original: 52.05 % diff: -28%"
## [1] "lion_compressed_svd_rank_258.jpg size: 37.613 original: 52.05 % diff: -28%"
## [1] "lion_compressed_svd_rank_3.jpg size: 15.732 original: 52.05 % diff: -70%"
## [1] "lion_compressed_svd_rank_300.jpg size: 37.621 original: 52.05 % diff: -28%"
## [1] "lion_compressed_svd_rank_45.jpg size: 31.422 original: 52.05 % diff: -40%"
## [1] "lion_compressed_svd_rank_88.jpg size: 35.266 original: 52.05 % diff: -32%"

The rank 300 image has a file size of 37.62KB compared to the original image size of 52.05KB, which results in a 28% smaller file size. We can see the difference in the file sizes quickly converge to around -28%, likely indicating further ranks would not result in a more efficient compression ratio.

Summary

The following post was an example of image compression with singular value decomposition, a typical application of the method in real-world settings. Commercial image compression solutions use a more robust method than what was described here; however, I hope it serves as a good example of the power matrix decomposition methods such as singular value decomposition can have in the real-world.

The post Image Compression with Singular Value Decomposition appeared first on Aaron Schlegel.

To leave a comment for the author, please follow the link and comment on their blog: R – Aaron Schlegel.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)