Contents

1 Insights

• Signals can be represented at least in two different domains: the signal domain (for example, time in the case of sound of space in the case of image) and the frequency domain (in general, in a transform domain).
• Transform coding is based on the idea that, in the transform domain, most of the energy of the signal can be compacted in a small number of (transform) coefficients. This property can be interesting for increasing the coding efficiency.
• Scalar quantization of decorrelated transform coefficients is more efficient than direct scalar quantization of the samples [7].

2 Basic coding steps

2.1 Encoder

1. Split $s$ into blocks of $B$ samples, if required.
2. Transform each block.
3. (Optional) Quantize the coefficients.
4. Lossless encode the quantized coefficients, performing a minimal bit-allocation.

2.2 Decoder

1. Decode the coefficients of each block.
2. (Optional) “Dequantize” the coefficients of each block.
3. Inverse-transform each block.
4. Join the blocks, if required.

3 Splitting

1. Divide $x={\left\{x_n\right\}}_{n=0}^{N-1}$ into $\lceil N∕B\rceil$ blocks $\{x_1,\cdots ,x_{\lceil N∕B\rceil }\}$ of $B$ samples.

4 Transform of a block $x={\left\{x_n\right\}}_{n=0}^{N-1}$

• In the forward transform the samples of the block $x$ are projected (notice that this operation is a dot product) on a set of basis functions

  $$y_n=\sum _{i=0}^{N-1}{a}_{n,i}{x}_i,$$

  (forward_transform)

  where $\left\{y_n\right\}$ is the transformed sequence and $\left\{x_n\right\}$ is the original sequence.

• The backward (inverse) transform restores the original samples

  $$x_n=\sum _{i=0}^{N-1}{b}_{n,i}{y}_u.$$

  (inverse_transform)

• These equations can be written in matrix form as

  $$y=Ax=\left[\begin{array}{ccc}\hfill a_{0,0}\hfill & \hfill \cdots \hfill & \hfill a_{B-1,0}\hfill \\ \hfill ⋮<!--FUNCTION\; APPLICATION-->\hfill & \hfill \hfill & \hfill ⋮<!--FUNCTION\; APPLICATION-->\hfill \\ \hfill a_{0,B-1}\hfill & \hfill cdots\hfill & \hfill a_{B-1,B-1}\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_0\hfill \\ \hfill ⋮<!--FUNCTION\; APPLICATION-->\hfill \\ \hfill x_{N-1},\hfill \end{array}\right]$$

  (forward_transform_matrix_form)

  and

  $$x=By,$$

  (inverse_transform_matrix_form)

  where $A$ and $B$ are matrices, being

  $$\begin{array}{c}{\left[A\right]}_{i,j}=a_{i,j}\hfill \\ {\left[B\right]}_{i,j}=b_{i,j}.\hfill \end{array}$$

  (1)

  ${\left[A\right]}_i$ is called a basis vector of the transformation matrix $A$. If the transform is orthonormal, they form an orthonormal basis set.

• In transform coding, $A$ and $B$ must be inverses of each other ($B=A^{-1}$), i.e.

  $$AB=BA=I,$$

  (2)

  where $I$ is the identity matrix.

5 A color transform

5.1 Luminance and chrominance

• Chrominance (or chroma) is the signal used in video systems to convey the color information of the picture or a video. It was defined to add the color signal to the black and white one in analog TV. Thus, the same signal, composed by two different subsignals: Y and UV that can be isolated by filtering, was compatible with both, black and white (which only used Y) and color ones (that used YUV).

• Later, in digital video, the YUV color domain was called the YCrCb color domain.
• Used, for example, in JPEG.

5.2 Spectral (color) redundancy

• $\text{RGB}$ domain is more redundant than the $\text{YUV}$ domain:

Color redundancy [1, 2, 4].

6 Chrominance subsampling

The human visual system is more sensitive to the luma (Y) than to the chroma (UV). This means than the chroma can be subsampled without a significant loss of quality in the images.

Chroma subsampling.

7 Orthogonal transform

• The rows of $A$ ($a_{k,\ast }$) are refered to as the basis vectors of the transform, and should form an orthogonal basis set in order to provide maximum energy compactation. The rows can be also seen as the coefficients of $B$ filters, being the first one ($i=0$) the “low-pass” one, which will produce the DC coefficient, and the rest ($i\ge 1$) the “high-pass” filters, which will generate the AC (Alternating Current) coeffs. These $B$ filters form a filter-bank where the overlapping between the frequency response of the filters should be as small as possible if we want maximum energy compaction.

7.1 Orthonormal transform

• If the basis vectors of a orthogonal transform are unit vectors, the transform is said orthonormal.
• For orthonormal transforms, it holds that

  $$A^{-1}=A^T.$$

  (5)

  Therefore, the pair of transforms refered by Eqs. (forward_transform_matrix_form) and (inverse_transform_matrix_form) can be written as

  $$\begin{array}{c}y=Ax\hfill \\ x=A^{T}y.\hfill \end{array}$$

  (6)

8 Signal energy

8.1 Energy conservation

Orthonormal transforms are energy preserving.

• If $A$ is orthonormal (also called unitary), the energy of the transformed signal is the equal to the original one:

  $$\left|\right|C|{|}^2=|\left|c\right|{|}^2.$$

  (8)

8.2 Proof

Therefore, the sum of the squares of the transformed sequence is the same as the sum of the squares of the original sequence.

9 Expected value

The expected value $E<!--FUNCTION\; APPLICATION-->\left[X\right]$ of a random variable $X$, intuitively, is the long-run average value of repetitions of the experiment it represents. Let $X$ be a random variable with a finite number of finite outcomes $X_1$, $X_2$, $\cdots$, $X_n$ occurring with probabilities $p_1$, $p_2$, $\cdots$, $p_k$, respectively. The expected value (or expectation) of $X$ is defined as

10 Variance

The variance of a random variable $X$ is the expected value of the squared deviation from the mean of $X$:

10.1 Covariance

The covariance $\mathrm{cov}<!--FUNCTION\; APPLICATION-->(X,Y)$ is a measure of the joint variability of two random variables $X$, $Y$, defined as:

11 Covariance matrix

A covariance matrix ${\Sigma }_Z$ is a matrix whose element in the $i$, $j$ position is the covariance between the $i$-th and $j$-th elements of a random vector $Z$ (a collection of random variables $Z_i$):

where

is the expected value of the $i$-th entry in the vector $Z$.

12 Covariance matrix of a block-based transform

13 Correlation

The most familiar measure of dependence between two random variables $X$ and $Y$ is the Pearson product-moment correlation coefficient, or “Pearson’s correlation coefficient”, commonly called simply “the correlation coefficient”. It is obtained by dividing the covariance of the two variables by the product of their standard deviations.

14 Autocorrelation

Autocorrelation, also known as serial correlation, is the correlation of a signal $s\left[t\right]$ with a delayed copy of itself as a function of delay $s[t+\tau ]$.

where $\mu =E<!--FUNCTION\; APPLICATION-->\left(s\right[t\left]\right)=E<!--FUNCTION\; APPLICATION-->\left(s\right[t+\tau \left]\right)$ and $\sigma ={\sigma }_{s\left[t\right]}={\sigma }_{s[t+\tau ]}$.

15 Autocorrelation matrix

The autocorrelation matrix of a random process $X$ is the matrix $\left[R\right]$ defined by

16 Eigenvalue and eigenvector

In linear algebra, an eigenvector or characteristic vector $\vec{v}$ of a linear transformation $T\left(\right)$ is a non-zero vector that changes by only a scalar factor $\lambda$ (known as the eigenvalue, characteristic value, or characteristic root of $\vec{v}$) when that linear transformation is applied to it:

When $T\left(\right)$ can be expressed by a matrix $X$, we get

17 Coding gain

• The coding gain measures the compaction level of the transform, which is defined as

  $$G=\frac{\frac{1}{N}\sum _{i=0}^{N-1}{\sigma }_{y_i}^2}{\sqrt[N]{\prod _{i=0}^{N-1}{\sigma }_{y_i}^2}},$$

  (21)

  where ${\sigma }_{y_i}^2$ is the variance of coefficient $y_i$.

18 Karhunen-Loéve transform (KLT)

• For the KLT, the rows of $A$ (the basis of the forward transform) are the eigenvectors of the (unnormalized) autocorrelation matrix $\left[R\right]$ of the signal $s$, where

  $${\left[R\right]}_{i,j}=E<!--FUNCTION\; APPLICATION-->(s_n{s}_{n+|i-j|}).$$

  (22)

• It can be proven that KLT minimizes $\sqrt[B]{{\prod <!--FUNCTION\; APPLICATION-->}_{u=0}^{B-1}{\sigma }_{C_u}^2}$, and therefore, it provides the maximum coding gain. Unfortunately, the basis fuctions of the KLT depends on $s$. If $S$ is non-stationary, the autocorrelation matrix (or the basis) must be sent to the decoder (to run the inverse transform) as side information. However, if $N=2$, the KLT is

  $$A_{\text{2-KLT}}=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -1\hfill \end{array}\right]$$

  (23)

  for all signals.

19 Discrete cosine transform (DCT))

19.0.1 Definition

• The forward (direct) transform is

  $$S_u=\frac{\sqrt{2}}{\sqrt{N}}K\left(u\right)\sum _{n=0}^{N-1}{s}_n\cos <!--FUNCTION\; APPLICATION-->\frac{(2n+1)\pi u}{2n},$$

  (24)

  and the backward (inverse) transform is

  $$s_n=\frac{\sqrt{2}}{\sqrt{N}}\sum _{u=0}^{N-1}K\left(u\right)S_u\cos <!--FUNCTION\; APPLICATION-->\frac{(2n+1)\pi u}{2n},$$

  (25)

  where $N$ is the number of pixels, and $s_n$ denotes the $n$-th pixel of the image $s$, and

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

  (26)

19.1 Properties fo DCT

1. Separable: the $D$-dimensional DCT can be computed using the $1$D DCT in each possible dimension.
2. In general, high energy compaction: a small number of DCT coefficients can reconstruct with a reasonable accuracy the original signal.
3. Unitary: the energy of the DCT coefficients is proportional to the energy of the samples.
4. Orthonormality: DCT basis are orthonormal (orthogonal + unitary) and therefore, DCT coefficients are uncorrelated.

DCT.

20 Dyadic discrete wavelet transform (DWT)

Key features:

1. High spectral compaction, specially when transient signals are present.
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.

21 Filters bank implementation

Where:

and

Comments:

1. ${\text{a}}_L$ and ${\text{a}}_H$ are the transfer function (the transfer function of a filter is the response of that filter to the unitary impulse function (Dirac’s delta)) of a low-pass filter and 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.
2. In the wavelet theory, ${\text{s}}_L$ is named the scale function and ${\text{s}}_H$ the mother function or wavelet basis function. The coefficients of $L$ are also known as the scale coeffients and the coeffcientes of $H$ the wavelet coefficients [5].
3. ${\downarrow }^2(\cdot )$ and ${\uparrow }^2(\cdot )$ donote the subsampling and oversampling operations:

and

where $s_i$ if the $i$-th sample of $s$.

1. $\ast$ is the convolution operator.
2. Notice that half of the filtered samples are wasted.

22 Lifting implementation [6]

Comments:

1. $$H_i=s_{2i+1}-\mathcal{𝒫}{\left(\right\{s_{2i}\left\}\right)}_i$$

   (PredictionStep)

1. Subsampled signals $\left\{s_{2i}\right\}$ and $\left\{s_{2i+1}\right\}$ can been computed by using

and

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

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

23 $T$-levels 1D-DWT

24 Subband indepency [7]

While the subbands are only independent if the input is a Gaussian random variable and the filters decorrelate the subbands (the filters are ideal), the independence assumption is ofte made because it makes he system simpler.

25 Statistics of the subbands [7]

The PDF of the coefficients of the high-frequency subbands peaks in zero and falls off very rapidly. While is it often modeled as a Laplacian distribution, it is actually falling off faster. It is more adequately fitted with a generalized Gaussian PDF with faster decay than the Laplacian PDF.

26 Subband quantization [7]

Besides the low band compression, which uses known image coding methods, the bulk of the compression is obtained by appropiate quantization of the high bands. The following quantizers are typically used:

1. Lloyd quantizers fitted to the PDF of the particular subband.
2. Deadzone uniform quantizers, since they tend to eliminate what is essentially noise.

Because entropy coding is used after quantization, uniform quantizers are nearly optimal. Note that VQ could be used in the subbands, but its complexity is usually not worthwhile since there is little dependence between coefficients anyway.

27 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.

• 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 (notice that ${s_H}^b$ does not depend on the coefficient because we are supposing that all the coefficients of a subband have the same contribution, the same basis fuction) [?]. Therefore, the L$2_{}$-norm for the subband $b$ is computed as the energy of a basis function of that subband as

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

28 Haar filters [3]

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

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

If Lifting is used,

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.

Haar basis.

29 Linear (5/3) filters [6]

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

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

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

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

Linear (5/3) basis.

30 Orthogonal, orthonormal, and biorthogonal transforms

In signal processing¹ , a transform (such as the Discrete Cosine Transform, the Walsh-Hadamard Transform or the Karhunen-Loève Transform) is orthogonal when the coefficients generated by the transform are uncorrelated (there is no way to infer one coefficient from another).

If the norm of all the basis of an orthogonal transform is one, then the transform is said orthonormal. Orthonormal transforms are interesting because of their:

1. Energy preservation: The energy of the output is the same than the energy of the input. This means that, for example, a quantization error produced in a coefficient of the transform will generate the same quantization error at the output (the complete signal) of the inverse transform. The same holds by the forward transform.
2. Implementation: The transform matrix of the inverse transform is the transpose of the forward transform. In orthogonal transforms, the transform matrix of the inverse transform is the inverse of the transform matrix of the forward transform.

Biorthogonal transforms (and in particular, biorthogonal wavelets) do no satisfy any of these features: they are not energy preserving (this can be also observed because the frequency-domain responses of the analysis and synthesis filters are not symmetric), and there is not an algebraic way (matrix transposition/inversion) to compute the backward transform from the forward one, and viceversa. This, that can be considered as a drawback, gives an extra degree of freedom to design the analysis and the synthesis filters (whose only requirement is that transform pair to be reversible), providing in general the possibility of using more sofisticated filters such as those based on non-linear filtering, as for example, those that use motion estimation algorithms.

In general, each subband $b$ of a decomposition generated by a biorthogonal 2D-DWT transform have a different subband gain ${\alpha }_b$. Usually, the lower the frequency of the subband, the higher the gain. Notice also, that these gains also are different for each transform.

Subband gains are important in lossy signal compression because they quantify the relative importance of the wavelet coefficients of the different subbands when we introduce distortion in the wavelet domain. Thus, for example, if we decide to quantize a wavelet coefficient, the amount of distortion that we are generating in the signal domain will depend on the subband where that coefficient is localized. In general, low-frequency coefficients are more “important” that high-frequency ones.

To compute the subband gains we have two options:

1. The algebraic way. We will need the expressions of the four filters (two anaylsis filters and two synthesis filters) and deduce the gains.
2. The algorithmic way. We will need to compute the energy of the impulse response of the inverse transform, when we apply such impulse to each one of the subbands of the decomposition. Supposing that, after appliying the DWT to an image, the coefficients of the subband HH are the least energetic with an energy $x$, the subband gain for subband $b$ is computed as

   $${\alpha }_b=E_b∕x,$$

   (32)

   where $E_b$ is the energy of the reconstruction when the impulse signal is localized at $b$. Notice that all the gains should be larger than one.

This computation can be also applied to MCDWT, by computing the subband gains as a function of the number $T$ of temporal decompositions.

31 Quantization in the transform domain

• If the transform is orthogonal, by definition coeffs $S\left[k\right]$ are uncorrelated. Therefore, a scalar quantizer can performs an optimal quantization.

32 Bit-planes progression

32.1 Bit allocation (bit-rate control)

• In lossless coding, coeffs $S_u$ are directly encoded using some text compression algorithm or a combination of them.
• However, in most situations, a lossy compression is needed and in this case, a transform coder must determine, given a maximum number of bits $\overline{R}$ (which is defined by the compression ratio selected by the user), the number of bits $R\left(u\right)$ used by the quantizer for each coeff $S_k$.

33 Bit allocation based on minimizing the quantization error

• In unitary transforms, as a consequence of the energy preserving property, an uniform quantization (i.e. the dividing each coeff $S_u$ by the same quantization step) should provide optimal bit allocation if we want to minimize the quantization error (the distortion) in the recostructed signal $s$.

34 Bit allocation based on minimizing the variance of the quantization error

• Lets assume that the variance of the coeffs, defined as

  $${\sigma }_{S_u}^2=\text{E}({(S_u-\overline{S})}^2)$$

  (33)

  (where

  $$\overline{S}=\text{E}\left(S\right)=\frac{1}{B}\sum _{u=0}^{B-1}{S}_u$$

  (34)

  corresponds to the amount of information provided by each coeff. Therefore, coeffs with high variance should be assigned more bits and viceversa.

• Lets define

  $$\overline{R}=\frac{1}{B}\sum _{u=0}^{B-1}R\left(u\right)$$

  ($\overline{R}$)

  as the (target) average number of bits/coeff, where $R\left(u\right)$ is the number of bits assigned to coeff $S_u$.

• If the mean square error is as a measure of distortion, the variance of the distortion generated by the quantization of a coeff $S_u$ can be modeled by

  $${\sigma }_{S_u-{\tilde{S}}_u}^2={\alpha }_u{2}^{-2R\left(u\right)}{\sigma }_{S_u}^2,$$

  (35)

  where ${\alpha }_u$ depends on the frequency $u$ and the quantizer.

DR_model notebook.

• Assuming an additive distorion metric, the total distortion variance for $R_k$ bits/coeff is given by

  $$D={\sigma }_{S-\tilde{S}}^2=\sum _{u=0}^{B-1}{\sigma }_{S_u-{\tilde{S}}_u}^2=\sum _{u=0}^{B-1}{\alpha }_u{2}^{-2R\left(u\right)}{\sigma }_{S_u}^2=\alpha \sum _{u=0}^{B-1}{2}^{-2R\left(u\right)}{\sigma }_{S_u}^2$$

  ($D$)

  ,

  supposing that ${\alpha }_u=\alpha$ is constant for all coeffs (a valid supposition for unitary transforms because the quantization error generated in each coeff should be the same if an uniform quantizer is used).

• The objective of the bit-allocation process is to find the ${\left\{R\right(u\left)\right\}}_{u=0}^{B-1}$ so that minimize $D$ subject to constraint $\overline{R}$:

  $$\underset{{\left\{R\right(u\left)\right\}}_{u=0}^{B-1}}{\mathrm{argmin}<!--FUNCTION\; APPLICATION-->}D,\text{s.t.} \overline{R}.$$

  (36)

• This is an optimization problem that can be solved using Lagrange multipliers (note: the following development is not the “standard” way of using Lagrenge multipliear, but it is equivalent).
• Lets define the Lagrangian functional

  $$J=D-\lambda (\overline{R}-\frac{1}{B}\sum _{u=0}^{B-1}R\left(u\right))=\alpha \sum _{u=0}^{B-1}{2}^{-2R\left(u\right)}{\sigma }_{S_u}^2-\lambda (\overline{R}-\frac{1}{B}\sum _{u=0}^{B-1}R\left(u\right)),$$

  (37)

which taking

produces that

• Substituting $R\left(u\right)$ in Eq. ($\overline{R}$), we get that

  $$\overline{R}=\frac{1}{B}\sum _{u=0}^{B-1}\frac{1}{2}{\log <!--FUNCTION\; APPLICATION-->}_2(2\alpha \ln <!--FUNCTION\; APPLICATION-->2{\sigma }_{S_u}^2)-\frac{1}{2}{\log <!--FUNCTION\; APPLICATION-->}_2\lambda .$$

  (39)

• Operating

  $$\lambda =\prod _{u=0}^{B-1}\sqrt[B]{2\alpha \ln <!--FUNCTION\; APPLICATION-->2{\sigma }_{S_u}^2}-2^{-2\overline{R}}.$$

  (40)

• Substituting $\lambda$ in Eq. ($R\left(u\right)$), we obtain the optimal number of bits for each coeff

  $$R\left(u\right)=\overline{R}+\frac{1}{2}{\log <!--FUNCTION\; APPLICATION-->}_2\frac{{\sigma }_{S_u}^2}{\prod _{u=0}^{B-1}\sqrt[B]{{\sigma }_{S_u}^2}}.$$

  (41)

  which minimizes the variance of the quantization error. Notice that this value depends proportionally on $\overline{R}$ (the target average bits/coeff), logaritmically on ${\sigma }_{S_u^2}$ (the variance of the coeff) and log-inversely on the geometric mean of the variances of all coeffs.

35 Encoding

• For DCT, usually ZigZag-RLE followed by 0-order entropy coding.
• For DWT, tree coding or block-based coding.

36 Code-stream orderings and scalabilities

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