Include a pre-rendered pdf version

[dirac-spec-errata.git] / idwt.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - This chapter defines how the inverse discrete - %
% - wavelet transform is done                     - %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Picture IDWT}

The inverse discrete wavelet transform process shall consist of transforming the 
wavelet coefficients for each of the video components. It shall be defined as follows:

\begin{pseudo}{inverse\_wavelet\_transform}{}
\bsCODE{\CurrentPicture[Y]=idwt(\YTransform)}{\ref{idwt}}
\bsCODE{\CurrentPicture[C1]=idwt(\COneTransform)}{\ref{idwt}}
\bsCODE{\CurrentPicture[C2]=idwt(\CTwoTransform)}{\ref{idwt}}
\bsFOREACH{c}{Y,C1,C2}
    \bsCODE{idwt\_pad\_removal(\CurrentPicture[c],c)}{\ref{padremoval}}
\end{pseudo}

\subsection{Component IDWT}
\label{idwt}

This section defines the $idwt(coeff\_data)$ process for reconstructing picture 
component data from decoded subband data $coeff\_data$ using the inverse discrete wavelet transform (IDWT). The IDWT shall be invoked in the picture decoding process only after successful unpacking of the subband coefficient data (Section \ref{transformdec}).

The IDWT process shall return a pixel array from the subband wavelet coefficients representing a reconstructed video component (Y, C1 or C2) for a single picture.


Since wavelet filtering operates on both rows and columns of two-dimensional arrays
 independently it is useful to define operators $\row(a,k)$ and $\column(a,k)$ for 
extracting rows and columns with index $k$ from a 2-dimensional array $a$:

If $b=\row(a,k)$ then $b[r]$ is a {\em reference} to the value of $a[k][r]$. This means that modifying the
value of $b[r]$ modifies the value of $a[k][r]$.

If $b=\column(a,k)$ then $b[r]$ is a {\em reference} the value of $a[r][k]$. This means that modifying the
value of $b[r]$ modifies the value of $a[r][k]$.

The $idwt()$ process shall be an iterative procedure operating on four subbands 
(\LL, \HL,\LH and \HH) at each iteration stage to produce a new subband. The procedure
shall be as follows

\begin{pseudo}{idwt}{coeff\_data}
\bsCODE{LL\_band = coeff\_data[0][\LL]}
\bsFOR{n=1}{\TransformDepth}
   \bsCODE{ 
                   new\_LL= vh\_synth(LL\_band, coeff\_data[n][\HL], coeff\_data[n][\LH], 
                   coeff\_data[n][\HH])
                   }{\ref{vhsynth}}
   \bsCODE{LL\_band=new\_LL}
\bsEND
\bsRET{LL\_band}
\end{pseudo}

Note that at each stage, the input dimensions of the input $LL\_band$ will be the same 
as those of the other input bands, whereas the output dimensions are double those of the input bands.

\subsubsection{Vertical and horizontal synthesis}
\label{vhsynth}

This section specifies the operation of the vertical and horizontal
synthesis process:

$vh\_synth(LL\_data, HL\_data, LH\_data, HH\_data)$

$vh\_synth$ shall return an array of twice the dimensions of each of the input
argument arrays. 

$vh\_synth$ is repeatedly invoked by the IDWT synthesis process and operates on four subband data arrays of identical dimensions to produce a new array $synth$, 
which shall be returned as the result of the process.

{\bf Step 1.} $synth$ is a temporary two-dimensional array that shall be initialised so that:
\begin{eqnarray*}
\width(synth) & = & 2*\width(LL\_data) \\
\height(synth) & = & 2*\height(LL\_data)
\end{eqnarray*}

{\bf Step 2.} The data from the four arrays shall be interleaved as follows:

\begin{pseudo*}
\bsFOR{y=0}{(\height(synth)//2)-1}
    \bsFOR{x=0}{(\width(synth)//2)-1}
        \bsCODE{synth[2*y][2*x] = LL\_data[y][x]}
        \bsCODE{synth[2*y][2*x+1] = HL\_data[y][x]}
        \bsCODE{synth[2*y+1][2*x] = LH\_data[y][x]}
        \bsCODE{synth[2*y+1][2*x+1] = HH\_data[y][x]}
    \bsEND
\bsEND
\bsCODE{\hdots}
\end{pseudo*}

Note: This enables in-place calculation during the inverse filter process.

{\bf Step 3.} Data shall be synthesised vertically by operating on each column
of data using a one-dimensional filter, and then horizontally by operating
on each row. The one-dimensional filters used shall be determined by
the value of $\WaveletIndex$ according to Tables \ref{filtertable0}--\ref{filtertable6}. 
The process shall be as follows:

\begin{pseudo*}
\bsFOR{x=0}{\width(synth)-1}
    \bsCODE{1d\_synthesis(\column(synth, x) )}{\ref{onedsynth}}
\bsEND
\bsFOR{y=0}{\height(synth)-1}
    \bsCODE{1d\_synthesis(\row(synth, y) )}{\ref{onedsynth}}
\bsEND
\bsCODE{\hdots}
\end{pseudo*}

{\bf Step 4.} Finally, the synthesised subband data shall implement a bitshift to
remove any accuracy bits. The bit shift value $filtershift()$ used shall be determined 
by the value of  $\WaveletIndex$ according to Tables \ref{filtertable0}--\ref{filtertable6}. 
The process shall be as follows:

\begin{pseudo*}
\bsCODE{shift = filtershift()}
\bsIF{shift>0}
    \bsFOR{y=0}{\height(synth)-1}
        \bsFOR{x=0}{\width(synth)-1}
            \bsCODE{synth[y][x] = (synth[y][x] + (1<<(shift-1)))\gg shift}
         \bsEND
    \bsEND
\bsEND
\end{pseudo*}

\begin{informative}
Accuracy bits are added in the encoder by shifting up all coefficients in the LL band 
prior to applying any filtering (this includes an initial shift of all values in the component
 data). Adding a small shift before each decomposition stage is the most efficient way of
 providing additional resolution mitigating aliasing through non-linear rounding effects.
\end{informative}

\subsubsection{One-dimensional synthesis}
\label{onedsynth}

This section specifies the one-dimensional synthesis process
$1d\_synthesis()$, which shall apply to a 1-dimensional array of coefficients 
of even length, consisting of either a row or a column of a 2-dimensional integral data array.

The one-dimensional synthesis process shall comprise the application of a
number of reversible integer lifting filter operations. 

Lifting filtering operations shall be one of four types, Type 1, Type 2, Type 3 and 
Type 4. Each type shall be characterised by four elements:
\begin{itemize}
\item a filter length value $L$
\item a filter offset value $D$
\item an array of taps of length $L$: $taps[0],\ldots,taps[L-1]$
\item a scale factor $S$
\end{itemize}

The four types of lifting operations shall be defined by the functions:
\begin{description}
\item[] $lift1(A,L,D,taps,S)$,
\item[] $lift2(A,L,D,taps,S)$,
\item[] $lift3(A,L,D,taps,S)$, and
\item[] $lift4(A,L,D,taps,S)$.
\end{description}
respectively and shall act upon the values in a one-dimensional array $A$.

The Type 1 lifting process $lift1(A,L,D,taps,S)$ shall be defined as follows:

\begin{pseudo}{lift1}{A,L,D,taps,S}
\bsFOR{n=0}{(\length(A)//2)-1}
    \bsCODE{sum=0}
    \bsFOR{i=D}{L+D-1}
        \bsCODE{pos=2*(n+i)-1}
        \bsCODE{pos=\min(pos, \length(A)-1)}
        \bsCODE{pos=\max(pos, 1)}
        \bsCODE{sum+=taps[i-D]*A[pos]}
    \bsEND
    \bsIF{S>0}
        \bsCODE{sum+=(1\ll (S-1))}
    \bsEND
    \bsCODE{A[2*n]+=(sum\gg S)}
\bsEND
\end{pseudo}

The Type 2 lifting process $lift2(A,L,D,taps,S)$ shall be defined as follows:

\begin{pseudo}{lift2}{A,L,D,taps,S}
\bsFOR{n=0}{(\length(A)//2)-1}
    \bsCODE{sum=0}
    \bsFOR{i=D}{L+D-1}
        \bsCODE{pos=2*(n+i)-1}
        \bsCODE{pos=\min(pos, \length(A)-1)}
        \bsCODE{pos=\max(pos, 1)}
        \bsCODE{sum+=taps[i-D]*A[pos]}
    \bsEND
    \bsIF{S>0}
        \bsCODE{sum+=(1\ll (S-1))}
    \bsEND
    \bsCODE{A[2*n]-=(sum\gg S)}
\bsEND
\end{pseudo}

The Type 3 lifting process $lift3(A,L,D,taps,S)$ shall be defined as follows:

\begin{pseudo}{lift3}{A,L,D,taps,S}
\bsFOR{n=0}{(\length(A)//2)-1}
    \bsCODE{sum=0}
    \bsFOR{i=D}{L+D-1}
        \bsCODE{pos=2*(n+i)}
        \bsCODE{pos=\min(pos, \length(A)-2)}
        \bsCODE{pos=\max(pos, 0)}
        \bsCODE{sum+=taps[i-D]*A[pos]}
    \bsEND
    \bsIF{S>0}
        \bsCODE{sum+=(1\ll (S-1))}
    \bsEND
    \bsCODE{A[2*n+1]+=(sum\gg S)}
\bsEND
\end{pseudo}

The Type 4 lifting process $lift4(A,L,D,taps,S)$ shall be defined as follows:

\begin{pseudo}{lift4}{A,L,D,taps,S}
\bsFOR{n=0}{(\length(A)//2)-1}
    \bsCODE{sum=0}
    \bsFOR{i=D}{L+D-1}
        \bsCODE{pos=2*(n+i)}
        \bsCODE{pos=\min(pos, \length(A)-2)}
        \bsCODE{pos=\max(pos, 0)}
        \bsCODE{sum+=taps[i-D]*A[pos]}
    \bsEND
    \bsIF{S>0}
        \bsCODE{sum+=(1\ll (S-1))}
    \bsEND
    \bsCODE{A[2*n+1]-=(sum\gg S)}
\bsEND
\end{pseudo}

$1d\_synthesis$ shall apply the sequence of lifting filters specified in Section \ref{wltfilters}
corresponding to the value of $\WaveletIndex$,and shall invoke the corresponding lifting processes with the parameters defined.

\paragraph{Mathematical formulation of lifting processes (Informative)}
$\ $\newline

The lifting processes defined in the previous section are extremely similar, and 
careful attention should be paid to the detail of their operation in any implementation. 
The four different variants arise from two factors: the ‘phase’ (odd or
even) of the lifting operation, and their implementation using integer-only 
operations, which introduces rounding errors and makes addition and subtraction 
subtly different. 

A lifting operation either modifies the odd coefficients by a linear combination of the 
even coefficients, or vice-versa. Mathematically, the four types of filter may be 
described as follows.

Type 1 and Type 2 lifting filtering operations modify the even coefficients
by the odd coefficients:
\begin{eqnarray*}
  A[2*n]& +=& \left( \sum^M_{i=-N} t_i *A[2*(n+i) + 1] +(1\ll (s-1))\right) \gg s \mbox{ (Type 1)} \\
  A[2*n]& -=& \left( \sum^M_{i=-N} t_i *A[2*(n+i) + 1] +(1\ll (s-1))\right) \gg s \mbox{ (Type 2)}
\end{eqnarray*}

Type 3 and Type 4 lifting filtering operation modify the odd coefficients
 by the even coefficients:
\begin{eqnarray*}
  A[2*n+1]& +=&  \left( \sum^M_{i=-N} t_i A[2*(n+i)]+(1\ll (s-1)) \right) \gg s \mbox{ (Type 3)} \\
  A[2*n+1]& -=&  \left( \sum^M_{i=-N} t_i A[2*(n+i)] +(1\ll (s-1))\right) \gg s \mbox{ (Type 4)} \\
\end{eqnarray*}

The distinctions between Type 1 and Type 2 and between 
Type 3 and Type 4 filters are necessary
because integer division (bit-shifting) is being used, and so the filters are non-linear:
a Type 1 or Type 3 filter with taps $t_i$ is {\em not} equivalent to 
an Type 2 or Type 4 filter with taps $-t_i$.

Edge extension is used where the filter would otherwise extend beyond the 
boundaries of the array. This is slightly different between Types 1 and 2 on the 
one hand and Types 3 and 4 on the other. This is because even values and
odd values must be extended separately to maintain the correct phase (and hence invertibility of the filter). For example, a Type 1 filter must use the values 1 and $\length(A)-1$ at the edges because (as the length is even) these are the odd values nearest the edges.

Further information on wavelet filtering and lifting is provided in Annex 
\ref{transformandlifting}.

\subsubsection{Lifting filter parameters}
\label{wltfilters}

The lifting filters and filter bit-shift operations that apply for each value
$\WaveletIndex$ shall be as specified in Tables  \ref{filtertable0} to \ref{filtertable6}
below.

\begin{table}[h]
\begin{tabular}{|l|}

\hline
Lifting steps:  \\
\begin{tabular}{l}
1. Type 2, $L=2, D=0, taps=[1,1], S=2$ i.e. \\
\quad $ A[2*n]     -=  (A[2*n-1]+A[2*n+1]+2)\gg 2$ \\
2. Type 3, $L=4, D=-1, taps=[-1,9,9,-1], S=4$ i.e. \\
\quad $ A[2*n+1]  +=  (-A[2*n-2]+9*A[2*n]+9*A[2*n+2]-A[2*n+4]+8)\gg 4$
\end{tabular}
\\
\\
$filtershift()$ returns 1\\
\hline

\end{tabular}
\caption{$\WaveletIndex==0$: Deslauriers-Dubuc (9,7) lifting stages and shift values}\label{filtertable0}
\end{table}

\begin{table}[h]

\begin{tabular}{|l|}
\hline
Lifting steps: \\

\begin{tabular}{l}
1. Type 2, $L=2, D=0, taps=[1,1], S=2$ i.e. \\
\quad $ A[2*n]  -= (A[2*n-1]+A[2*n+1]+2)\gg 2$ \\
2. Type 3, $L=2, D=0, taps=[1,1], S=1$ i.e. \\
\quad $ A[2*n+1]  += (A[2*n]+A[2*n+2]+1)\gg 1$
\end{tabular}
\\
\\
$filtershift()$ returns 1\\
\hline

\end{tabular}
\caption{$\WaveletIndex==1$: LeGall (5,3) lifting stages and shift values}
\end{table}

\begin{table}[h]
\begin{tabular}{|l|}

\hline
Lifting steps: \\
\begin{tabular}{l}
1. Type 2, $L=4, D=-1, taps=[-1,9,9,-1], S=5$ i.e. \\
\quad $ A[2*n]  -= (-A[2*n-3]+9*A[2*n-1]+9*A[2*n+1]-A[2*n+3]+16)\gg 5$ \\
2. Type 3, $L=4, D=-1, taps=[-1,9,9,-1], S=4$ i.e. \\
\quad $ A[2*n+1]  += (-A[2*n-2]+9*A[2*n]+9*A[2*n+2]-A[2*n+4]+8)\gg 4$
\end{tabular}
\\
\\
$filtershift()$ returns 1\\
\hline

\end{tabular}
\caption{$\WaveletIndex==2$: Deslauriers-Dubuc (13,7) lifting stages and shift values}
\end{table}

\begin{table}[h]
\begin{tabular}{|l|}

\hline
Lifting steps:\\
\begin{tabular}{l}
1. Type 2, $L=1, D=1, taps=[1], S=1$ i.e. \\
\quad $A[2*n] -=  (A[2*n+1]+1)\gg 1$ \\
2. Type 3, $L=1, D=0, taps=[1], S=0$ i.e. \\
\quad $ A[2*n+1] += A[2*n]$
\end{tabular}
\\
\\
$filtershift()$ returns 0\\
\hline

\end{tabular}
\caption{$\WaveletIndex==3$: Haar filter with no shift}
\end{table}

\begin{table}[h]
\begin{tabular}{|l|}

\hline
Lifting steps:\\
\begin{tabular}{l}
1. Type 2, $L=1, D=1, taps=[1], S=1$ i.e. \\
\quad $A[2*n] -=  (A[2*n+1]+1)\gg 1$ \\
2. Type 3, $L=1, D=0, taps=[1], S=0$ i.e. \\
\quad $ A[2*n+1] += A[2*n]$
\end{tabular}
\\
\\
$filtershift()$ returns 1\\
\hline

\end{tabular}
\caption{$\WaveletIndex==4$: Haar filter with single shift}
\end{table}

\begin{table}[h]
\begin{tabular}{|l|}
\hline
Lifting steps:\\
\begin{tabular}{l}
1. Type 3, $L=8, D=-3, taps=[]-2,10,-25,81,81,-25,10,-2], S=8$ i.e. \\
$ \begin{array}{rcl} A[2*n+1] & += & (-2*(A[2*n-6]+A[2*n+8])+10*(A[2*n-4]+A[2*n+6])\\
                                             & &       -25*(A[2*n-2]+A[2*n+4])+81*(A[2*n]+A[2*n+2])+128)\gg 8 \end{array}$ \\
1. Type 2, $L=8, D=-3, taps=[-8,21,-46,161,161,-46,21,-8], S=8$ i.e. \\
 $ \begin{array}{rcl}A[2*n]  & -= & (-8*(A[2*n-7]+A[2*n+7])+21*(A[2*n-5]+A[2*n+5]) \\
                                          & &      -46*(A[2*n-3]+A[2*n+3])+161*(A[2*n-1]+A[2*n+1])+128)\gg 8 \end{array}$ 
\end{tabular}
\\
\\
$filtershift()$ returns 0\\
\hline

\end{tabular}
\caption{$\WaveletIndex==5$: Fidelity filter for improved downconversion and anti-aliasing}
\end{table}

\begin{table}[h]
\begin{tabular}{|l|}

\hline
Lifting steps:\\
\begin{tabular}{l}
1. Type 2, $L=2, D=0, taps=[1817,1817], S=12$ i.e. \\
\quad $A[2*n] -=  (1817*A[2*n-1]+1817*A[2*n+1]+2048)\gg 12$ \\
2. Type 4, $L=2, D=0, taps=[3616,3616], S=12$ i.e. \\
\quad $A[2*n+1] -= (3616*A[2*n]+3616*A[2*n+2]+2048)\gg 12$ \\
3. Type 1, $L=2, D=0, taps=[217,217], S=12$ i.e. \\
\quad $A[2*n] +=  (217*A[2*n-1]+217*A[2*n+1]+2048)\gg 12$ \\
4. Type 3, $L=2, D=0, taps=[6497,6497], S=12$ i.e. \\
\quad $ A[2*n+1] += (6497*A[2*n]+6497*A[2*n+2]+2048)\gg 12$
\end{tabular}
\\
\\
$filtershift()$ returns 1\\
\hline

\end{tabular}
\caption{$\WaveletIndex==6$: Integer lifting approximation to Daubechies (9,7)}\label{filtertable6}
\end{table}
\clearpage
\subsection{Removal of IDWT pad values}
\label{padremoval}

This section defines the decoding process $idwt\_pad\_removal(pic, c)$
for removing extraneous values after performing the IDWT.

Section \ref{wltinit} requires that subband coefficient data arrays are padded to ensure that 
the reconstructed data array $pic$ has dimensions divisible by $2^\TransformDepth$.

Values $width$ and $height$ are defined to be the appropriate dimensions
of the component data:

\begin{itemize}
\item If $c=Y$, then
\begin{eqnarray*}
width & =& \LumaWidth \\
height & =& \LumaHeight
\end{eqnarray*}
\item else if $c=C1$ or $c=C2$,
\begin{eqnarray*}
width & =& \ChromaWidth \\
height & =& \ChromaHeight
\end{eqnarray*}
\end{itemize}

All component data $pic[j][i]$ with

\begin{itemize}
\item $i\geq width$, or
\item $j\geq height$
\end{itemize}

shall be discarded and $pic$ shall be resized to have width $width$ and height $height$.