Pros, Cons, and Applications of SVD-based Image Compression (Singular Value Decomposition)

Question

SVD can be used for image compression:

• Tim Baumann - Image Compression with Singular Value Decomposition.
• Balabit Unsupervised - Image compression using singular value decomposition.

I think there are many image compression algorithms now. My question is:

Is the SVD based image compression popular for actual applications now?

For example, is there any image format which is using the SVD based method for compression?

If it is not popular now, what are the pros and cons of this approach compared to others?

I would like to know Pros, Cons, and applications of SVD-based image compression.

Answer 1

The idea of using PCA with images is to look at the margin ensembles generated by the image. That means, we consider two distributions: The distribution of the column over the realisations of the rows. And the distribution of the rows over the realisation of the columns.

The covariance matrices of these two distributions can be diagonalised using PCA, resulting in a set of dominant eigenvectors for both the rows and the columns. The entire image can then be described as a tensor product series using the dominant eigenvectors as tensor factors.

I've written some code in Julia to briefly demonstrate the concept:

using Images
using LinearAlgebra

# load an image and resize it to be more practical
img = load("testimage.jpg")
img_small = imresize(img, Int.(floor.(size(img).*0.25)))

# take just the red channel for the demonstration and cast to float
M = Float32.(getfield.(img_small, :r))

# construct the margin ensembles for both dimensions
M1 = M * M'
M2 = M' * M

# find the eigenvectors of each margin ensemble and sort by decreasing eigenvalue magnitude
e1 = eigen(M1, sortby = v -> -abs(v))
e2 = eigen(M2, sortby = v -> -abs(v))

# set an encoding threshold to determine the number of dimensions to use
threshold = 0.020

cv1 = cumsum(abs.(e1.values))
cv2 = cumsum(abs.(e2.values))

K = findfirst( cv -> cv > (1-threshold^2) * maximum(cv1), cv1)
L = findfirst( cv -> cv > (1-threshold^2) * maximum(cv2), cv2)

# normalise the base vectors
for k = 1:K
    e1.vectors[:,k] *= inv(sqrt(sum(e1.vectors[:,k].^2)))
end

for l = 1:L
    e1.vectors[:,l] *= inv(sqrt(sum(e2.vectors[:,l].^2)))
end

# initialize the reconstructed image
Mr = zeros(Float32, size(M))
B = zeros(Float32, size(M))

# encode and reconstruct at the same time
for k = 1:K, l = 1:L
    # Construct the tensor product basis
    B .= e1.vectors[:,k] * e2.vectors[:,l]'
    # ... to find the expansion coefficient
    c = sum(M .* B)
    # ... and finally add the tensor product 
    # contribution to the reconstruction
    Mr .+= c * B
end

# display the reconstructed image channel
Gray.(Mr)

# calculate the dimensional reduction:

required_space = K * size(M1,1) + L * size(M2,1) + K * L
original_space = prod(size(M))

encoding_ratio = required_space / original_space

# The new encoding is also more robust against quatization noise,
# so additional compression can be gained by lowering the quantization
# depth. Entropy encoding will further improve the resulting ratio.

As commented in the code, the ratio calculated is just the dimensional reduction of the coefficient space. The usual data reduction techniques to follow are requantisation and entropy encoding.

I've run the code above with an example image. The original image is

which is reconstructed to

with a dimensional reduction ratio of 0.38.

So as you can see, the other answers provided here (1 and 2) are strongly misleading.

The reasons why PCA is not widely used for image encoding despite the fact that it demonstrably works are mostly the bad scaling of the computational effort required to decompose an image. The reconstruction is also fairly slow. To add to this, most of modern encoders' compression efficiency comes from considering limitation of human perception. With PCA you can control the average reconstruction error, but have no control at all over where the error is located. A good encoder must hide the reconstruction error where it is least perceptible, which this technique cannot provide.

Edit: To demonstrate the typical encoding artifacts, here is the same example with a higher error threshold, resulting in a dimension reduction ratio of 0.1:

Answer 2

PCA is just not very useful for image compression.

You're asking the question:

Why is it not used?

without first considering the question

Why should it be used?

You owe it to yourself (and honestly, to people trying to answer the question "why not?") to think about how it could be a good tool for compressing still images.

That's not clear, and I'll explain why I think you won't find a reason why it should be used:

What you want in (lossy) data compression is:

1. identify features of the data that are more important for the purpose (here: visual perception by humans) than others
2. decompose the image into coefficients to these features, assigning a lower data rate to the unimportant features
3. arrange the resulting data in a way that is most useful for an entropy coder (e.g. LZW, LZMA)

The problem with PCA in this context is that the components you find are unknown to the receiver of an image – you need to send them as well.

So, to send an image $D$ (or a block in an image) with $N$ pixels, you first use PCA to find principal components $C_i$ (say, $m$ relevant principal components, $i=0,\ldots,m-1$), which each having $N$ pixels.

$$ D = \sum_{i=0}^{m-1} \alpha_i C_i$$

Now, you made $N\cdot m$ pixels out of your $N$ pixels file, plus $m$ coefficients $\alpha_i$. So, you greatly increased the amount of data you need to transport, instead of reducing it!

Even in the most extreme case, an image literally just containing a single principal component and nothing else, you would have not have gained anything – the component would be the original pixels, and not any better or worse to compress.

Other transform-based image codecs solve that by using a canonical base set of components that were not found by PCA. For example, basically all JPEG- and MPEG-developed image compressors use blocks of $2^k\times 2^k$ pixels, project them onto the base vectors of the 2D-DCT (or a defined set of 2D wavelets), and only encode the coefficients. You don't have to send the base functions (components) – the DCT is known to the receiver.

So, for a single image, PCA makes your data bigger, not smaller, and hence is useless.

For movies, where the same deconstruction of still images might be used multiple times in consecutive images, finding a base, transporting it, and then using it for many pictures, could make sense. But even in that case, on image-type data, PCA with a $m\ll N$ (which is what you would need to reduce data significantly) leads to very noticable artifacts; for example, consider these 32 frames (source: "Principal Component Analysis (PCA) applied to images", by Václav Hlaváč from Czech Technical University in Prague)

When we find the $m=4$ highest-energy principal components of that (still only a coefficient bits reduction by a factor of 8; even the 32 years old JPEG beats that trivially), and use them to reconstruct the 32 images, you get this:

Observe the eyes: all eyes are "blurry half open". But the boy closed them, and reopened them. Look at the eyes in the middle of the bottom row: The boy looked to the side. PCA "removed" that information that is very important to the human looking at the pictures!

PCA directly on image data is really bad at preserving these kind of things, because it's in the end a linear operation on individual pixels, so you always get a pixel-wise average. Hence, even in the context of images that are very similar and where you hence would expect principal components to be shared, PCA is a bad idea. Video codecs use methods that are useful for human perception instead – for example, motion prediction. (There might be techniques to detect motion or similar frames through SVD; but these would work on the pre-transformed image, not on pixels.)

So, PCA solves none of the problems in image compression, but introduces more pixels to transport. It's simply in itself not useful.

Answer 3

No one uses it as the basis used for the compression depends on the data. You have to send both the coordinates and the basis.