Contents

1 Motivation

Homer.ppm (1,467,663 bytes)	Homer.j2c (12,101 bytes (122 times smaller))

2 Spatial redundancy

• Image compressors take profit of the spatial redundancy to speed up the encoding process and to increase the compression ratios.

  

• If the decoder can recover the original data, we speak about lossless codecs, otherwise, lossy codecs.
• Lossless image and video codecs are used only in some specific cases because the compression ratios are quite modest compared to the equivalent lossy encoder.

3 The RGB $\to$ Y’CbCr color transform [5]

• Removes intercomponent (color) redundancy.
• Usually, the RGB domain is more redundant than the YCbCr domain (spectral redundancy or intercomponent redundancy).
• The RGB $\to$ YCbCr color (multicomponent) transform is defined as:

  $$\left(\begin{array}{c}\hfill \text{Y’}\hfill \\ \hfill \text{Cb}\hfill \\ \hfill \text{Cr}\hfill \end{array}\right)=\left(\begin{array}{ccc}\hfill 0,299& \hfill 0,587& \hfill 0,144\\ \hfill -0,1687& \hfill -0,3313& \hfill 0,5\\ \hfill 0,5& \hfill -0,4187& \hfill -0,0813\end{array}\right)\left(\begin{array}{c}\hfill \text{R}\hfill \\ \hfill \text{G}\hfill \\ \hfill \text{B}\hfill \end{array}\right)$$

  (1)

  which when the dinamic range of the RGB components is $\left[0,255\right]$ can be approximated by

  $$\left(\begin{array}{c}\hfill 256\times \text{Y’}\hfill \\ \hfill 256\times \left(\text{Cb}-128\right)\hfill \\ \hfill 256\times \left(\text{Cr}-128\right)\hfill \end{array}\right)=\left(\begin{array}{ccc}\hfill 77& \hfill 150& \hfill 29\\ \hfill -44& \hfill -67& \hfill 131\\ \hfill 131& \hfill -110& \hfill -21\end{array}\right)\left(\begin{array}{c}\hfill \text{R}\hfill \\ \hfill \text{G}\hfill \\ \hfill \text{B}\hfill \end{array}\right)$$

  (2)

  in order to avoid the floating point computations.

• Used for example in JPEG [4].

The RGB $\to$ Y’CbCr color transform: example

R, $H\left(\text{R}\right)=7.51$ bpp	G, $H\left(\text{G}\right)=6.82$ bpp	B, $H\left(\text{B}\right)=7.04$ bpp
Total $=$ 21,37 bpp

Y’, $H\left(\text{Y’}\right)=7.42$ bpp	Cb, $H\left(\text{Cb}\right)=6.86$ bpp	Cr, $H\left(\text{Cr}\right)=4.51$ bpp
Total $=$ 18,79 bpp

4 Chrominance subsampling

• Removes visual information.
• The human visual system is more sensitive to the luma (Y’) than to the chroma (CbCr)¹ . This means than the chroma can be subsampled without a significant loss of quality in the images:

  

5 The PSNR (Peak Signal-to-Noise Ratio)

• Useful to measure the quality of the lossy reconstructions.
• Definition:

  $$\text{PSNR[dB]}=10{log}_{10}\frac{{\left(2^b-1\right)}^2}{\text{MSE}},$$

  (3)

  where $b$ is the number of bits/pixel and MSE (Mean Squared Error) is

  $$\text{MSE}=\frac{1}{N}\sum _{i=1}^N{\left(s\left[i\right]-ŝ\left[i\right]\right)}^2,$$

  (4)

  where $N$ is the number of pixels, s[$i$] is the $i$-th ($i=\left(x,y\right)$) point of the $s\left[\cdot \right]$ image and $ŝ\left[i\right]$ is the $i$-h point of the reconstructed image.

Chrominance subsampling: example

Original (4:4:4)	Subsampled (4:2:0), PSNR $=22.07$ dB

Original (8:8:8)	Subsampled (8:2:0), PSNR $=22.01$ dB

Original (16:16:16)	Subsampled (16:2:0) PSNR $=21.96$ dB

6 The DCT (Discrete Cosine (spatial) Transform)

• The forward transform is

  $$\text{DCT}\left[u\right]=\frac{\sqrt{2}}{\sqrt{N}}K\left(u\right)\sum _{n=0}^{N-1}s\left[n\right]cos\frac{\left(2n+1\right)\pi u}{2n}$$

  (5)

  and the inverse transform is

  $$s\left[n\right]=\frac{\sqrt{2}}{\sqrt{N}}\sum _{u=0}^{N-1}K\left(u\right)\text{DCT}\left[u\right]cos\frac{\left(2n+1\right)\pi u}{2n},$$

  (6)

  where $N$ is the number of pixels, and $s\left[n\right]$ denotes the $n$-th pixel of the image $s$, and

  $$K\left(u\right)=\left\{\begin{array}{cc}\frac{1}{\sqrt{2}}\hfill & \text{si}u=0\hfill \\ 1\hfill & \text{if}u>0.\hfill \end{array}\right.$$

• The DCT is separable (the $D$-dimensional DCT can be computed using the $1$D DCT in each possible dimension).
• It’s fast: There is a fast algorith for the DCT with complexity $N{log}_{2}N$.
• Spectral energy compactation: Very close to the Karhunen-Lòeve Transform in terms of spectral compactation² . As a consecuence, the DCT accumulated the most part of the energy of the image in a small set of coefficients.
• It’s idempotent: In other words ... the Euclidean distancy is preserved. Therefore,the largest (taking the absolute value of the) coefficients minimizes the reconstruction error when a subset of coefficients are used.

7 Basis functions of the DCT

• The waveform of the basis functions of the DCT talk about the spatial correlation exploited by JPEG and the artifacts than can be expected in the reconstructions.
• The 9 lowest-frequency DCT basis functions are:

8 A progressive transmission using the DCT

1. Transform the image.
2. Remove a set of the smallest coefficients (in absolute value).
3. Do the inverse transform.

Lena reconstructed with $1.000$ DCT coefs

Lena reconstructed with $2.000$ DCT coefs

Lena reconstructed with $3.000$ DCT coefs

Lena reconstructed with $4.000$ DCT coefs.png

Lena reconstructed with $5.000$ DCT coefs

9 The dyadic DWT (Discrete Wavelet Transform)

• The DWT has two benefits:
  1. Spectral energy compactation: a small set of coefficient concentrates the main part of the image energy.
  2. Multiresolution representation: it is easy to recover a reduced version of the original image if only a sub-set of the coefficients is proccesed.

10 Computation of the DWT using a filter bank

Where

and

• $a_L$ and $a_H$ are the transfer function³ of a low-pass filter and a high-pass filter, respectively, that have been designed to be complementary (ideally, in $L$ we only found the frequencies of $S$ that are not in $H$, and viceversa). When this is true, it is said the we are using a Perfect Reconstruction Quadrature Mirror Filter bank and the DWT is biorthogonal.
• In the wavelet theory, $s_L$ is named the scale function and $s_H$ the mother function or wavelet basis function. The coefficients of $L$ are also knwon as the scale coeffients and the coeffcientes of $H$ the wavelet coefficients [7].
• ${\downarrow }^2\left(\cdot \right)$ and ${\uparrow }^2\left(\cdot \right)$ donote the subsampling and oversampling operations:

  $${\left({\downarrow }^2\left(S\right)\right)}_i=S_{2i}$$

  (9)

  and

  $${\left({\uparrow }^2\left(S\right)\right)}_i=\left\{\begin{array}{cc}{S}_{i∕2}\hfill & \text{if }i\text{ if even}\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}\right.$$

  (10)

  where $S_i$ if the $i$-th sample of $S$.

• Finaly, $\ast$ is the convolution operator.

11 Drawback of the filter bank implementation

• In general, the convolution is an expensive operation if the filters are long and the half of the filtered samples are wasted.

12 The Lifting approach [8])

• Notice that the subsampled signals $\left\{S_{2i}\right\}$ and $\left\{S_{2i+1}\right\}$ can been computed by using

  $$\left\{S_{2i+1}\right\}={\downarrow }^2\left(Z^{-1}\left(S\right)\right)$$

  and

  $$\left\{S_{2i}\right\}={\downarrow }^2\left(S\right),$$

  where $Z^{-1}$ represents the one sample delay function.

• $H$ has tipically less energy and entropy than $\left\{S_{2i+1}\right\}$.
• $L$ has less aliasing than $\left\{S_{2i}\right\}$ (notice that $L$ has not been low-pass filtered before subsampling it).

13 The $T$-levels 1D DWT

14 The $N$-levels 2D DWT

• The one-dimensional (1D) DWT is a separable transform. Therefore, the 2D DWT can be computed applying the DWT to all the rows of an image and next, to all the columns, or viceversa.

  

15 Subband importances (energy gain factors or L${}_2$-norms) [6]

• All the (DWT) coefficients has not the same importance in order to reduce the reconstruction error (when all the coefficients can not be recovered).
• The contribution of a coefficient to the minimization of the distortion depends on the energy in the space domain that this coefficient generates.
• All the coefficients of a subband have the same energy contribution, except those coefficients that are in the boundaries of the subbands. For this reason, only a gain value is usually given for a subband and for this reason, only one DWT basis function (also known as the wavelet function) is needed to be evaluated in order to know the contribution.
• The energy of a discrete signal $x$ is defined as

  $$E\left(x\right)=\sum _i{\left|x_i\right|}^2,$$

  (11)

  where $\left|x_i\right|$ represents the Euclidian Norm (also known as the L${}_2$ Norm) of the sample $x_i$, that in a general case could be a complex number.

• The contribution of a coefficient of a subband $b$ is determined by the DWT basis fuction ${S_H}^b$ asociated to that coefficient, which can be empirically determined by applying the inverse DWT to the Dirac Impulse function localized in that coefficient.⁴
• Therefore, the L${}_2$-norm for the subband $b$ is computed as the energy of a basis function of that subband as

  $$E\left({S_H}^b\right)=\sqrt{\sum _i{\left|{S_H}_i^b\right|}^2}.$$

  (12)

• In the case of the 5/3-DWT, the L${}_2$-norms of the DWT subbands are:

  

16 The Haar filters (spline 2/2) [3]

• The $i$-th sample of the low-frequency subband is computed (using a filter plus subsampling) as

  $$L_i=\frac{S_{2i}+S_{2i+1}}{2},$$

  (HaarL)

  and the $i$-th sample of the high-frequency subband as

  $$H_i=S_{2i+1}-S_{2i}.$$

  (HaarH)

  If Lifting is used,

  $$L_i=S_{2i}+\frac{H_i}{2}.$$

  (HaarLLifted)

• Notice that $H_i=0$ if $S_{2i+1}=S_{2i}$, therefore, the Haar transform is good to encode constant signals.
• The notation X/Y indicates the length (taps or number of coefficients) of the low-pass and the high-pass (convolution) filters of the filter bank implementation (not Lifting), respectively.

17 1D basis functions of the Haar Transform

18 2D basis functions of the Haar Transform

19 A progressive transmission using the Haar DWT

1. Transform the image.
2. Remove a set of the smallest coefficients (in absolute value).
3. Do the inverse transform.

Lena reconstructed with $1.000$ Haar coefs

Lena reconstructed with $2.000$ Haar coefs

Lena reconstructed with $3.000$ Haar coefs

Lena reconstructed with $4.000$ Haar coefs

Lena reconstructed with $5.000$ Haar coefs

20 The Lineal filters (Spline 5/3, LeGall and Tabatabai, 1988) [1, 8]

• The $i$-th sample of the low-frequency subband (using a filter-bank implementation) is

  $$L_i=-\frac{1}{8}{S}_{2i-2}+\frac{1}{4}{S}_{2i-1}+\frac{3}{4}{S}_{2i}+\frac{1}{4}{S}_{2i+1}-\frac{1}{8}{S}_{2i+2}$$

  (5/3L)

  and the $i$-th sample of the high-frequency signal is computed by

  $$H_i=S_{2i+1}-\frac{S_{2i}+S_{2i+2}}{2},$$

  (5/3H)

  that, if we use Lifting, it can be also computed using less operations by

  $$L_i=S_{2i}+\frac{H_{i-1}+H_i}{4}.$$

  (5/3LLifted)

• Notice that $H_i=0$ if $S_{2i+1}=\left(S_{2i}+S_{2i+2}\right)∕2$. Therefore, the 5/3 transform is suitable to encode lineally piece-wised signals.

21 1D basis functions of the 5/3 Transform

22 2D basis functions of the 5/3 Transform

23 A progressive transmission using the 5/3 DWT

Lena reconstructed with $1.000$ 5/3 coefs

Lena reconstructed with $2.000$ 5/3 coefs

Lena reconstructed with $3.000$ 5/3 coefs

Lena reconstructed with $4.000$ 5/3 coefs

Lena reconstructed with $5.000$ 5/3 coefs

24 The Cubic filters (Spline 13/7) [2, 8]

• The $i$-th sample of the high-frequency subband is

  $$H_i=S_{2i+1}-\left(\right.\frac{9}{16}\left(\right.S_{2i}+S_{2i+2}\left)\right.-\frac{1}{16}\left(\right.S_{2i-2}+S_{2i+4}\left)\right.\left)\right.$$

  (13/7H)

  and (the lifted) calulus of the $i$-th sample of the low-frequency signal is

  $$L_i=S_{2i}+\frac{9}{32}\left(\right.H_{i-1}+H_i\left)\right.-\frac{1}{32}\left(\right.H_{i-2}+H_{i+1}\left)\right..$$

  (13)

• The 13/7 reconstructions are smoother than the 5/3 ones.

25 Basis functions of the 13/7 Transform

26 2D basis functions of the 13/7 Transform

27 A progressive transmission using the 13/7 DWT

Lena reconstructed with $1.000$ 13/7 coefs

Lena reconstructed with $2.000$ 13/7 coefs

Lena reconstructed with $3.000$ 13/7 coefs

Lena reconstructed with $4.000$ 13/7 coefs

Lena reconstructed with $5.000$ 13/7 coefs

28 Bit-plane transmission

29 Code-stream ordering and scalabilities

• The order in which the DWT coeffients are decoded determines the type of scalability (example with 2 qualities and 3 resolutions):

References