Image compressing with PCA, SVD and rSVD algorithms
Daniel Kornacki, student of the Faculty of Economic Sciences, University of Warsaw
1 03 2021
Introduction
Principal Component Analysis (PCA) is a widely used technique for image compression. PCA itself is a statistical method that enables to transformation correlated set of data to a potentially uncorrelated one. In the computation process, so-called principal components are calculated, and in the form of eigenvectors (with eigenvalues), explain changes in the variation of the dataset. PCA pertains to covariances and variances’ explanation through conducting linear combinations, with no loss of original information.
When it comes to image compression, each image has a tremendous number of pixels. Every pixel has information about three different wavelengths, which corresponds to the mixture of three colors that the human eye can observe - red, blue, and green (Number of pixels = number of principal components that particular image has. In such analysis, all of the colors have their own matrix and PCA.
Besides PCA, we may examine many more complex algorithms that reduce dimensionality and present similar images with fewer principal components. One of the well-known ones is Singular Value Decomposition, which is known as a valuable matrix factor in applied algebra. It works similarly to PCA. Its main goal in image compression is to transform correlated variables into uncorrelated ones.
Sometimes, to overcome the complexity and size of the dataset, some techniques are used to speed up the calculations. An approach that gained big popularity in linear algebra to ease the computational load was randomness. The basic idea behind it is to employ randomness to derive a smaller matrix from a high-dimensional data matrix.
In this paper I will perform image compression using PCA, SVD and rSVD. I will compare them by measuring the time of performing, number of Principal Components and RMSE.
PCA
We will start by presenting the image that will be compressed.
photo<-readJPEG("flower.jpg")
plot(1, type="n")
rasterImage(photo, 0.6, 0.6, 1.4, 1.4)
dim(photo)## [1] 768 1024 3As we see, the maximum number of principal components that we may obtain is 768.
Now lets check the importance of the components. To perform it, I will use fviz_eig from package gridExtra.
r<-photo[,,1]
g<-photo[,,2]
b<-photo[,,3]
r.pca<-prcomp(r, center=FALSE, scale.=FALSE)
g.pca<-prcomp(g, center=FALSE, scale.=FALSE)
b.pca<-prcomp(b, center=FALSE, scale.=FALSE)
rgb.pca<-list(r.pca, g.pca, b.pca)
library(gridExtra)
r1<-fviz_eig(r.pca, main="Red", barfill="Orange Red", ncp=6, addlabels=TRUE)
g1<-fviz_eig(g.pca, main="Green", barfill="Forest Green", ncp=6, addlabels=TRUE)
b1<-fviz_eig(b.pca, main="Blue", barfill="Navy Blue", ncp=6, addlabels=TRUE)
grid.arrange(r1, g1, b1, ncol=3)
The biggest percentage of explained variance we can observe for green color, following by red and blue.
Now I will perform compression using PCA.
vec<-seq.int(3, round(nrow(photo)), length.out=9)
for(i in vec){
photo.pca<-sapply(rgb.pca, function(j) {
new.RGB<-j$x[,1:i] %*% t(j$rotation[,1:i])}, simplify="array")
assign(paste("photo_", round(i,0), sep=""), photo.pca)
writeJPEG(photo.pca, paste("photo_", round(i,0),"_princ_comp.jpg", sep=""))
}Each of compressed image has been saved in my work file. Bellow you can find few of them basing on number of components
Orginal
plot(1, type="n")
rasterImage(photo, 0.6, 0.6, 1.4, 1.4)
3 PC
plot(image_read(get(paste('photo_', round(vec[1],0), sep=""))))
194 PC
plot(image_read(get(paste('photo_', round(vec[3],0), sep=""))))
481 PC
plot(image_read(get(paste('photo_', round(vec[6],0), sep=""))))
768 PC
plot(image_read(get(paste('photo_', round(vec[9],0), sep=""))))
Well, as we can see from these photo even 194 components is enough to present nearly unrecognizable image from the original one. Let’s perform whole PCA algorithm together with information about number of components, size of compressed photos, Comparisson of the size to the original image, and RMSE of each one.
original <- file.info('flower.jpg')$size /1000
for (i in 1:9) {
full.path <- paste('photo_', round(vec[i],0),"_princ_comp.jpg", sep='')
print(paste("Number of PC:", round(vec[i],0), ' size: ', file.info(full.path)$size / 1000, ' Compression Ratio: ', round((file.info(full.path)$size / 1000 -original) / original, 5) * 100, '%', sep = ''))
}## [1] "Number of PC:3 size: 35.877 Compression Ratio: -66.709%"
## [1] "Number of PC:99 size: 73.766 Compression Ratio: -31.552%"
## [1] "Number of PC:194 size: 77.423 Compression Ratio: -28.158%"
## [1] "Number of PC:290 size: 83.06 Compression Ratio: -22.928%"
## [1] "Number of PC:386 size: 86.482 Compression Ratio: -19.752%"
## [1] "Number of PC:481 size: 86.736 Compression Ratio: -19.517%"
## [1] "Number of PC:577 size: 86.724 Compression Ratio: -19.528%"
## [1] "Number of PC:672 size: 86.723 Compression Ratio: -19.529%"
## [1] "Number of PC:768 size: 86.723 Compression Ratio: -19.529%"library(Metrics)
results<-matrix(0, nrow=9, ncol=4)
colnames(results)<-c("Number of PC", "Photo size", "Compraisson to orginal", "RMSE-Mean Squared Error")
results[,1]<-round(vec,0)
for(i in 1:9) {
path<-paste("photo_", round(vec[i],0), "_princ_comp.jpg", sep="")
results[i,2]<-file.info(path)$size
photo_rmse<-readJPEG(path)
results[i,4]<-rmse(photo, photo_rmse)
}
results[,3]<-round(as.numeric(results[,2])/as.numeric(results[9,2]),5)
results## Number of PC Photo size Compraisson to orginal RMSE-Mean Squared Error
## [1,] 3 35877 0.41370 0.13182534
## [2,] 99 73766 0.85059 0.04986559
## [3,] 194 77423 0.89276 0.03553485
## [4,] 290 83060 0.95776 0.02710682
## [5,] 386 86482 0.99722 0.01890685
## [6,] 481 86736 1.00015 0.01289807
## [7,] 577 86724 1.00001 0.01221535
## [8,] 672 86723 1.00000 0.01216572
## [9,] 768 86723 1.00000 0.01216572As can be seen from obtained results, file with image of 194 components with compression ratio of -28%, which is relatively solid. Lets now focus on two versions of SVD algorithm.
SVD
photo.r.svd <- svd(r)
photo.g.svd <- svd(g)
photo.b.svd <- svd(b)
rgb.svds <- list(photo.r.svd, photo.g.svd, photo.b.svd)
for (i in seq.int(3, round(nrow(photo)), length.out = 9)) {
a <- sapply(rgb.svds, function(j) {
new.svd <- j$u[,1:i] %*% diag(j$d[1:i]) %*% t(j$v[,1:i])}, simplify = "array")
assign(paste("compressed_photo_", round(i,0), sep=""), a)
writeJPEG(a, paste("compressed_photo_", round(i,0), "_svd_rank_", ".jpg", sep=""))
}
for (i in 1:9) {
full.path <- paste('compressed_photo_', round(vec[i],0),"_svd_rank_.jpg", sep="")
print(paste("Number of PC:", round(vec[i],0), ' size: ', file.info(full.path)$size / 1000, ' Compression Ratio: ', round((file.info(full.path)$size / 1000 -original) / original, 5) * 100, '%', sep = ''))
}## [1] "Number of PC:3 size: 35.877 Compression Ratio: -66.709%"
## [1] "Number of PC:99 size: 73.766 Compression Ratio: -31.552%"
## [1] "Number of PC:194 size: 77.423 Compression Ratio: -28.158%"
## [1] "Number of PC:290 size: 83.06 Compression Ratio: -22.928%"
## [1] "Number of PC:386 size: 86.482 Compression Ratio: -19.752%"
## [1] "Number of PC:481 size: 86.736 Compression Ratio: -19.517%"
## [1] "Number of PC:577 size: 86.724 Compression Ratio: -19.528%"
## [1] "Number of PC:672 size: 86.723 Compression Ratio: -19.529%"
## [1] "Number of PC:768 size: 86.723 Compression Ratio: -19.529%"results<-matrix(0, nrow=9, ncol=4)
colnames(results)<-c("Number of PC", "Photo size", "Compraisson to orginal", "RMSE-Mean Squared Error")
results[,1]<-round(vec,0)
for(i in 1:9) {
path<-paste('compressed_photo_', round(vec[i],0),"_svd_rank_.jpg", sep="")
results[i,2]<-file.info(path)$size
photo_rmse<-readJPEG(path)
results[i,4]<-rmse(photo, photo_rmse)
}
results[,3]<-round(as.numeric(results[,2])/as.numeric(results[9,2]),5)
results## Number of PC Photo size Compraisson to orginal RMSE-Mean Squared Error
## [1,] 3 35877 0.41370 0.13182534
## [2,] 99 73766 0.85059 0.04986559
## [3,] 194 77423 0.89276 0.03553485
## [4,] 290 83060 0.95776 0.02710682
## [5,] 386 86482 0.99722 0.01890685
## [6,] 481 86736 1.00015 0.01289807
## [7,] 577 86724 1.00001 0.01221535
## [8,] 672 86723 1.00000 0.01216572
## [9,] 768 86723 1.00000 0.01216572rotated SVD
library(rsvd)
photo.r.rsvd <- rsvd(r)
photo.g.rsvd <- rsvd(g)
photo.b.rsvd <- rsvd(b)
rgb.rsvds <- list(photo.r.rsvd, photo.g.rsvd, photo.b.rsvd)
for (i in seq.int(3, round(nrow(photo)), length.out = 9)) {
a <- sapply(rgb.rsvds, function(j) {
new.rsvd <- j$u[,1:i] %*% diag(j$d[1:i]) %*% t(j$v[,1:i])}, simplify = "array")
assign(paste("compressed_photo_", round(i,0), sep=""), a)
writeJPEG(a, paste("compressed_photo_", round(i,0), "_rsvd_rank_", ".jpg", sep=""))
}
for (i in 1:9) {
full.path <- paste('compressed_photo_', round(vec[i],0),"_rsvd_rank_.jpg", sep="")
print(paste("Number of PC:", round(vec[i],0), ' size: ', file.info(full.path)$size / 1000, ' Compression Ratio: ', round((file.info(full.path)$size / 1000 -original) / original, 2) * 100, '%', sep = ''))
}## [1] "Number of PC:3 size: 35.877 Compression Ratio: -67%"
## [1] "Number of PC:99 size: 73.766 Compression Ratio: -32%"
## [1] "Number of PC:194 size: 77.423 Compression Ratio: -28%"
## [1] "Number of PC:290 size: 83.06 Compression Ratio: -23%"
## [1] "Number of PC:386 size: 86.482 Compression Ratio: -20%"
## [1] "Number of PC:481 size: 86.736 Compression Ratio: -20%"
## [1] "Number of PC:577 size: 86.724 Compression Ratio: -20%"
## [1] "Number of PC:672 size: 86.723 Compression Ratio: -20%"
## [1] "Number of PC:768 size: 86.723 Compression Ratio: -20%"results<-matrix(0, nrow=9, ncol=4)
colnames(results)<-c("Number of PC", "Photo size", "Compraisson to orginal", "RMSE-Mean Squared Error")
results[,1]<-round(vec,0)
for(i in 1:9) {
path<-paste('compressed_photo_', round(vec[i],0),"_rsvd_rank_.jpg", sep="")
results[i,2]<-file.info(path)$size
photo_rmse<-readJPEG(path)
results[i,4]<-mse(photo, photo_rmse)
}
results[,3]<-round(as.numeric(results[,2])/as.numeric(results[9,2]),5)
results## Number of PC Photo size Compraisson to orginal RMSE-Mean Squared Error
## [1,] 3 35877 0.41370 0.0173779204
## [2,] 99 73766 0.85059 0.0024865773
## [3,] 194 77423 0.89276 0.0012627254
## [4,] 290 83060 0.95776 0.0007347795
## [5,] 386 86482 0.99722 0.0003574690
## [6,] 481 86736 1.00015 0.0001663603
## [7,] 577 86724 1.00001 0.0001492148
## [8,] 672 86723 1.00000 0.0001480046
## [9,] 768 86723 1.00000 0.0001480046We may observe that all of the examined algorithms use the same number of components. It means that files with compressed images have the same size. Comparing them by RMSE, SVD and PCA have the same errors, while much smaller RMSE values characterize rSVD. The last thing left is to check the time of performance of these algorithms.
pca_time <- system.time({prcomp(r, center=FALSE, scale.=FALSE)})
SVD_time <- system.time({x<-svd(r)})
rSVD_time <- system.time({x<-rsvd(r, k=194)})
(t<-list(pca_time, SVD_time, rSVD_time))## [[1]]
## user system elapsed
## 8.56 0.06 9.02
##
## [[2]]
## user system elapsed
## 7.17 0.05 7.97
##
## [[3]]
## user system elapsed
## 4.12 0.04 4.78As expected PCA is a bit slower than SVD, and rSVD computation time, in regard to therory is also faster than SVD.
Conslusions
In this paper, I examined three image compression algorithms. I compared their performance based on RMSE and computation time since the rest of the measures were the same. Regarding obtained results, rSVD has the shortest computation time and has the lowest values of RMSE. Nevertheless, both SVD and PCA are widely used methods for dimension-reduction in image compression, and there is no doubt about their relevance to this field of Data Science.
References
https://en.wikipedia.org/wiki/Principal_component_analysis
Báscones, Daniel, Carlos González, and Daniel Mozos. “Hyperspectral image compression using vector quantization, PCA and JPEG2000.” Remote sensing 10.6 (2018): 907.
https://fredhohman.com/assets/image_compression.pdf
Class Materials on Unsupervised Learning, Faculty of Economic Sciences, University of Warsaw