Application in Image Compression

SVD image transform has different applications in image processing and analysis. We now consider how it can be used for data compression. First we write a matrix $A$ as

$${\bf A}=[a_{ij}]_{N\times N}=[{\bf a}_1,\cdots,{\bf a}_N]$$

where ${\bf a}_i=[a(1,i),\cdots,a(N,i)]^T$ is the ith column vector of ${\bf A}$. The total amount of energy contained in ${\bf A}$ can be represented by the norm of ${\bf A}$ defined as

$${\cal E}_A=\parallel {\bf A} \parallel \stackrel{\triangle}{=} tr\;[{\bf A}^T{\bf A}] = tr \left[ \begin{array}{c} {\bf a}_1^T \vdots {\bf a}_N^T... ...ts {\bf a}^T_N{\bf a}_1 & \cdots & {\bf a}_N^T{\bf a}_N \end{array} \right]$$

$$= \sum_{i=1}^N {\bf a}_i^T{\bf a}_i=\sum_{i=1}^N\sum_{j=1}^N a^2_{ij}$$

Now we consider image compression achieved by using only the first $M<N$ eigenimages of the given image ${\bf A}$:

$${\bf A}_M\stackrel{\triangle}{=}\sum_{i=1}^M\sqrt{\lambda_i}{\bf u}_i{\bf v}_i^T$$

with error

$${\bf E}_M={\bf A}-{\bf A}_M=\sum_{i=M+1}^N\sqrt{\lambda_i}{\bf u}_i{\bf v}_i^T$$

After compression, the energy (information) contained in ${\bf A}_M$ is:

$$\parallel {\bf A}_M \parallel = tr \; [{\bf A}_M^T{\bf A}_M]= tr \left[ \sum_{i=1}^M\sqrt{\lamb... ...u}_i^T \right] \left[ \sum_{j=1}^M\sqrt{\lambda_j}{\bf u}_j{\bf v}_j^T \right]$$

$$= tr \left[\sum_{i=1}^M (\sum_{j=1}^M\sqrt{\lambda_i}\sqrt{\lambda_... ...}_j^T ) \right] = tr \left[\sum_{i=1}^M \lambda_i {\bf v}_i{\bf v}_i^T \right]$$

$$= \sum_{i=1}^M \lambda_i tr\; [{\bf v}_i{\bf v}_i^T ] =\sum_{i=1}^M \lambda_i {\bf v}_i^T{\bf v}_i =\sum_{i=1}^M \lambda_i$$

Note that here we have used the property that $tr({\bf A}{\bf B})=tr({\bf B}{\bf A})$. We see that the total amount of energy (information) contained in the original image $A$ is

$$\mbox{energy in ${\bf A}$}=\sum_{i=1}^N \lambda_i$$

and the energy (information) lost (contained in ${\bf E}_M$) is

$$\mbox{energy in ${\bf E}_M$}=\sum_{i=M+1}^N \lambda_i$$

It is therefore obvious that minimum energy is lost if we range $\lambda_i$'s so that

$$\lambda_1 \geq \cdots \geq \lambda_M \geq \cdots \geq \lambda_N$$

To find out the compression ratio, consider total degrees of freedom in ${\bf A}_M$:

$${\bf A}_M=\sum_{i=1}^M \sqrt{\lambda_i} {\bf u}_i{\bf v}_i^T$$

The degrees of freedom in the $M$ orthogonal vectors $\{{\bf u}_i\;\;i=1,\cdots, M\}$ are

$$(N-1)+(N-2)+\cdots+(N-M)=NM-M(M+1)/2$$

The same is true for $\{{\bf v}_i\;\;i=1,\cdots, M\}$. Including the $M$ degrees of freedom in $\{\lambda_i,\;i=1,\cdots,M\}$, we have the total d.o.f.:

$$2NM-M(M+1)+M=2NM-M^2$$

and the compression ratio is

$$\frac{2NM-M^2}{N^2}=2\frac{M}{N}-\frac{M^2}{N^2}$$

For example, $N=1000$, $k=50$, the compression rate is less than $1/10$.

An example of using SVD for image compression is available here