UoL CS Notes
Menu

Spectral Methods - SVD & Image Compression

COMP116 Lectures

An image can be represented as a matrix where each cell used 24 bits to encode the colour as RGB.

To compress it we can use the following method:

Given an $H\times W$ image $P$, let $M$ be the corresponding matrix.

$M$ will not typically be a square matrix.

Exploiting Spectra

Any $H\times W$ matrix $M$ can be described as the product of three matrices $U,S,V$:

  • $U$ is the same dimensions as the original matrix.
  • $S$ and $V$ are square matrices the same dimensions as $W$.

The original matrix can be recovered like so:

\[M=U\cdot S\cdot V\]

The Three Matrices

This method appears to use more space as shown below:

\[HW+W^2+W^2=W\cdot(H+2W)\]

The compression comes from removing rows and columns in $S$. As a result we have to remove the same:

  • Columns in $U$.
  • Rows in $V$.

This is to keep that matrix proportions.

Suppose we keep only $k$ rows and columns giving $S_k$. We end up with space:

\[k\cdot(H+k+W)< HW\]

This can be much smaller than $HW$.

Example

For an image with dimensions $2500\times2500$ requiring 18.75 Mb of space (using the RGB scheme). If it is the be encoded with SVD using a maximum of 3 Mb, what are the maximum dimensions for $S$.

  1. Currently the SVD approach uses this much space:

    \[3(2500^2+2500^2+2500^2)\approx56.25\text{Mb}\]

  2. We can use the following equation from earlier to scale the image to fit a new size (the centre value is the matrix $S$):

    \[3(2500k+k^2+2500k)\]

  3. Solve this equation with respect to the required size:

    \[3(2500k+k^2+2500k)=3\times10^6\]

This gives a $k$ value as $k=192$ as you round down to satisfy the size requirement.

Calculating $U,S$ and $V$

Given $M$, form the matrices:

\[\begin{aligned} M&\cdot M^T\\ M^T&\cdot M \end{aligned}\]

$M^T$ is the transpose of $M$.

These two matrices are square and symmetric. This means that:

  • All of their eigenvalues are real numbers.

  • Their spectra are identical:

    \[(\lambda_1,\lambda_2,\ldots,\lambda_i,\ldots,\lambda_n)(\lambda_i\leq\lambda_{i+1})\]

To calculate $S,U$ and $V$:

  • $S:s_{ij}=0$ if $i\neq j$ and $s_{ii}=\sqrt{\lambda_i}$
  • $U:$ $k^{th}$ column an eigenvector of $M\cdot M^T$ with $\lambda_k$
  • $V:$ $k^{th}$ row an eigenvector of $M^T\cdot M$ with $\lambda_k$

Choosing What to Throw Away

Small eigenvalues aren’t going to make much difference ot he matrix product outcome.

So to reduce space:

  • Throw away all by the $k$ largest values in $S$.
  • Throw away the matching eigenvectors in $U$ and $V$.

Summary

  • The technique of using three matrices to represent one is called singular value decomposition (SVD).
  • Both Python (numpy) and Java (jama) provide packages to compute SVD decompositions.