Update of /cvsroot/dirac/compress/doc/latex_spec
In directory
sc8-pr-cvs12.sourceforge.net:/tmp/cvs-serv19996
Modified Files:
quant-matrix.tex spec-conventions.tex spec-structure.tex
Added Files:
lifting.tex
Log Message:
Added quantisation matrices for low delay syntax and
informative text on
quantisation strategies - also an informative annex on
Lifting.
Index: quant-matrix.tex
============================================================
=======
RCS file:
/cvsroot/dirac/compress/doc/latex_spec/quant-matrix.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** quant-matrix.tex 18 Jun 2007 15:22:54 -0000 1.1
--- quant-matrix.tex 21 Jun 2007 13:16:03 -0000 1.2
***************
*** 1,12 ****
label
! subsection{Default quantisation matrices}
label
This section defines default quantisation matrices to be
used
for the quantisation of slice coefficients in the
low-delay syntax.
! The following tables define matrices for
$WaveletDepthleq 4$
! and a subset of $WaveletIndex$. Combinations of values of
! $WaveletDepth$ and $WaveletIndex$ not present in the
tables
in this section shall require a custom matrix to be
encoded,
as per Section ref. Informative advice for
--- 1,16 ----
label
! This section specifies the default quantisation matrices
to be used
! in the core syntax and provides an informative description
of quantisation
! matrix design principles and of quantiser selection in
both the core
! and low-delay syntax.
!
! subsection{Quantisation matrices (low delay syntax)}
label
This section defines default quantisation matrices to be
used
for the quantisation of slice coefficients in the
low-delay syntax.
! The following tables define matrices for
$WaveletDepthleq 4$.
! Values of $WaveletDepth$ not present in the tables
in this section shall require a custom matrix to be
encoded,
as per Section ref. Informative advice for
***************
*** 77,81 ****
hline
end
! caption{Default quantisation matrices for
$WaveletIndex==0$ (Deslauriers-Debuc (9,3))
label{table:qm0}}
end
--- 81,85 ----
hline
end
! caption{Default quantisation matrices for
$WaveletIndex==0$ (Deslauriers-Debuc (9,5))
label{table:qm0}}
end
***************
*** 545,551 ****
clearpage
begin{informative*}
! subsection{Custom quantisation matrices (Informative)}
label
--- 549,698 ----
clearpage
begin{informative*}
! subsection{Quantisation matrix design and quantiser
selection (Informative)}
! label
!
! This section provides an informative guide to the
principles used to design the default
! quantisation matrix
!
! subsubsection{Noise power normalisation}
! label
!
! The quantisation matrices defined in the preceding section
are designed to counteract the
! differential power gain of the various wavelet filters, so
that quantisation noise from
! each subband is weighted equally in terms of its
contribution to noise power when transformed
! back into the picture domain. Let $alpha$ and $beta$
represent the noise gain factors of
! the low-pass and high-pass wavelet filters used in wavelet
decomposition. In a single level of
! wavelet decomposition, quantisation noise in each of the
four subbands is therefore weighted by the factors shown in
Figure ref{fig:onelevelweight}.
! end{informative*}
! setlength
! begin[!h]
! centering
! begin(20,27)
! put(0,5){line(1,0)}
! put(0,5){line(0,1)}
! put(20,5){line(0,1)}
! put(20,25){line(-1,0)}
!
! put(10,5){line(0,1)}
! put(0,15){line(1,0)}
!
! put(3,19.5){text{Large LL -- $alpha^2$}}
! put(3,9.5){text{Large LH -- $alphabeta$}}
! put(13,19.5){text{Large HL -- $alphabeta$}}
! put(13,9.5){text{Large HH -- $beta^2$}}
! end
! caption{Subband weights for a 1-level
decomposition}label{fig:onelevelweight}
! end
! begin{informative*}
!
! For higher levels of decomposition, these subband
weighting factors iterate
! in the same manner as the wavelet transform itself. For
example, with a two-level
! decomposition, the first level LL band, with weight
$alpha^2$ is further decomposed
! to give four more bands with weights as for the 1-level
decomposition, but multiplied
! by $alpha^2$. This yields the weights shown in Figure
ref{fig:twolevelweight}.
! end{informative*}
! setlength
! begin[!h]
! centering
! begin(30,40)
! put(0,5){line(1,0)}
! put(0,5){line(0,1)}
! put(30,5){line(0,1)}
! put(30,35){line(-1,0)}
!
! put(15,5){line(0,1)}
! put(0,20){line(1,0)}
!
! put(5.5,12){text{Large LH -- $alphabeta$}}
! put(20.5,27){text{Large HL -- $alphabeta$}}
! put(20.5,12){text{Large HH -- $beta^2$}}
!
! put(7.5,20){line(0,1)}
! put(0,27.5){line(1,0)}
!
! put(2,31){text{Large LL -- $alpha^4$}}
! put(2,23.5){text{Large LH -- $alpha^3beta$}}
! put(9,31){text{Large HL -- $alpha^3beta$}}
! put(9,23.5){text{Large HH -- $alpha^2beta^2$}}
!
! end
! caption{Subband weights for a 2-level
decomposition}label{fig:twolevelweight}
! end
! begin{informative*}
!
! In this specification, wavelet synthesis filters have been
defined in terms of lifting stages,
! which are filters operating on subsampled data. Wavelet
filters are more traditionally
! represented in terms of an iterated binary polyphase
filter bank: the relationship between
! these representation is described in Appendix
ref. The factors $alpha$ and $beta$
! are most easily computed from the filter bank
representation. In this case $alpha$ is either
! the RMS power gain of the low-pass synthesis filter, or
the {em reciprocal} of the RMS power
! gain of the low-pass analysis filter; and $beta$ is the
RMS power gain of the high-pass
! synthesis filter of the reciprocal of the RMS power gain
of the high-pass analysis filter.
!
! Thus, in the terminology of Appendix ref,
! $alpha=dfrac{(sum_n h(n)^2)^}$ or
! $alpha=(sum_n tilde(n)^2)^$
!
! and
! $beta=dfrac{(sum_n g(n)^2)^}$ or
! $beta=(sum_n tilde(n)^2)^$
!
! These alternative definitions arise because the wavelet
filters defined in this specification
! are not orthogonal, but technically {em biorthogonal} and
so, strictly speaking, there is
! not power addition of the quantisation noise in each
subband. The values used for quantisation
! matrices have been computed from the analysis rather than
the synthesis filters, as this yields
! better compression results in practice.
!
! Note also that these factors must also take into account
the shift factors used to add accuracy
! bits prior to each wavelet decomposition stage. For a
filter shift of $d$, $alpha$ and
! $beta$ are each multiplied by $2^{-d/2}$.
!
! Given a subband weighting factor $w$, a quantisation
offset for that subband may be defined
! as $4*log_2(w)$ rounded to the nearest integer. These
offsets are then normalised so as
! to be non-negative, to produce the tables of the preceding
section.
!
! subsubsection{Custom quantisation matrices}
label
+ Custom matrices may be defined that take into account not
only noise power normalisation
+ but also perceptual weighting based on spatial frequency.
Additional multiplicative factors
+ may be computed for each subband, which produce a matrix
of quantisation offsets which may
+ then be added to the default unweighted quantisation
matrices to produce a weighted quantisation
+ matrix.
+
+ An example perceptual weighting may be constructed from
the CCIR 959 Contrast Sensitivity
+ Function (CSF). This is a function $csf(s)$ which produces
a value representing the
+ sensitivity to detail at a given normalised spatial
frequency $s$. For luminance, it is defined
+ by
+ [csf(s)=0.255*(1+0.2561*s^2)^{-0.75}]
+
+ Assuming an isotropic response, we may form a 2-d
perceptual weighting function on
+ horizontal and vertical spatial frequencies $x_s,y_s$ by
+ begin{eqnarray*}
+ c(x_s,y_s) & = &
dfrac{csf((xs^2+ys^2)^)} \
+ & = & 0.255*(1+0.2561*(x_s^2+y_s^2))^{0.75}
+ end{eqnarray*}
+
+ Each subband in a wavelet decomposition represents a
subset of spatial frequencies according
+ to level and orientation, partitioning the spatial
frequency domain as per Figure ref{fig:orientlevel}.
+ Note that this partitioning is un-normalised, since output
pictures (and their compression artefacts) may
+ be viewed at a range of distances.
+
+ Accordingly we may pick a representative, un-normalised
horizontal and vertical spatial frequency $(f_x(b),f_y(b))$
-- perhaps the middle frequency of the band. For example, an
LH band $b$ at level 1 in a 1-level
+ decomposition will have mid frequency at $(pw/4,3*ph/4)$
where $ph$ and $pw$ are the padded
+ width and height of the picture (Section
ref). This may be turned into a true
+ spatial frequency by normalising by the number of
horizontal and vertical cycles per degree the output
+ pictures will subtend at the target viewing distance and
aspect ratio:
+ [ (f_x(b)/cpd_x,f_y(b)/cpd_y)]
+
+ and this value may be fed into the weighting function to
get a value $c(b)$. The appropriate
+ quantisation offset for that subband is then
$4*log_2(c(b))$, which may be used to define a modified
+ quantisation matrix.
+ subsection{Quantiser selection in the core syntax
(Informative)}
+ label
+
+ subsection{Quantiser selection in the low delay syntax
(Informative)}
+ label
+
Index: spec-conventions.tex
============================================================
=======
RCS file:
/cvsroot/dirac/compress/doc/latex_spec/spec-conventions.tex,
v
retrieving revision 1.13
retrieving revision 1.14
diff -C2 -d -r1.13 -r1.14
*** spec-conventions.tex 9 May 2007 14:35:54 -0000 1.13
--- spec-conventions.tex 21 Jun 2007 13:16:03 -0000 1.14
***************
*** 19,40 ****
The parsing and decoding operations are specified in terms
of modifying
! the decoder state. Decoder state variables may not
directly correspond
! to elements of the stream, but are calculated from them
taking into
account the decoder state as a whole. For example, a state
variable value
may be differentially encoded with respect to another
value, with the
difference, not the variable itself, encoded in the
stream.
! The stream structure itself is summarised in parse
diagrams, which
are presented in Appendix ref. The parsing
process
is defined by means of pseudocode and/or mathematical
formulae. The
! conventions for these elements are described in the
succeeding sections.
In the event of any conflict between the parse diagrams
and the specified
parsing processes, the latter shall be deemed to be
correct.
! subsection{Numbers and arithmetic operations}
label
! subsubsection
! label
The prefix b indicates that the following value is to be
interpreted as a binary
--- 19,39 ----
The parsing and decoding operations are specified in terms
of modifying
! the decoder state. The state variables may not directly
correspond
! to elements of the stream, but may be calculated from them
taking into
account the decoder state as a whole. For example, a state
variable value
may be differentially encoded with respect to another
value, with the
difference, not the variable itself, encoded in the
stream.
! The Dirac stream syntax is illustrated in parse diagrams,
which
are presented in Appendix ref. The parsing
process
is defined by means of pseudocode and/or mathematical
formulae. The
! conventions for these elements are described in the
following sections.
In the event of any conflict between the parse diagrams
and the specified
parsing processes, the latter shall be deemed to be
correct.
! subsection{Number formats}
label
! Numbers without a prefix shall be interpreted as decimal
numbers.
The prefix b indicates that the following value is to be
interpreted as a binary
***************
*** 48,53 ****
{bf Example} The value 0x7A is equal to the decimal value
122.
! subsubsection{Arithmetic operations}
! label
All arithmetic defined by this specification is exact: the
entire
--- 47,103 ----
{bf Example} The value 0x7A is equal to the decimal value
122.
! subsection{Data types}
! label
!
! subsubsection{Elementary data types}
!
! Only three basic types are used in the pseudo code:
! begin
! item[Boolean] - A Boolean variable that has only two
possible values: $true$ and $false$.
! item[Integer] - A positive or negative whole number or
zero.
! item[Unsigned] - A non-negative ($geq 0$) whole number,
of arbitrary size.
! end
!
! subsubsection{Compound data types}
!
! There are three types of compound data:
!
! begin
! item[Set] A collection of variables or values with no
particular indexing.
! A set containing members $A,B,C,ldots$ is denoted
${A,B,C,ldots}$. The usual
! set-theoretic operations $cup$ (union), $cap$
(intersection), $in$ (membership)
! apply.
!
! item[Map]
!
! A map is a set accessed by token names. For example
! $p[Y]$, $p[C1]$, $p[C2]$ might give the value of the
different video components
! (Y, C1 and C2) of a pixel. The set of argument tokens of a
map $m$ can be accessed by $args(m)$,
! so that $args(p)={Y,C1,C2}$.
!
! item[Array]
!
! An array is a set with an integer index or indices. All
arrays are indexed from 0.
! Elements of a 1-dimensional array $a$ are accessed by
$a[n]$ for $n$ in the
! range 0 to $length(a)-1$. Elements of a 2-dimensional
array are accessed by
! $a[n][m]$ for $0leq mleqwidth(a)-1$ and $0leq
nleqheight(a)-1$.
!
! A 1-dimensional array can be explicitly defined by the
syntax $a=[u, v, w, hdots]$.
! Then $a[0]=u$,
! $a[1]=v$ and so on.
! end
!
! The elements contained within any compound data type may
be other compound data types.
!
!
! subsection{Numerical functions and operators}
! label
!
! This section defines the functions and operators used
! in the pseudo-code in this specification. Functions and
operators
! are similar but functions use the syntax, $(arg1,
arg2,ldots)$
! whereas operators are simply placed before or between
operands,
! e.g. $a+b$. The difference is purely syntactic and is to
! correspond with conventional mathematical notation.
All arithmetic defined by this specification is exact: the
entire
***************
*** 228,231 ****
--- 278,285 ----
then at the end of $foo$, $StateName[var_name]$ has been
set to 1.
+ The only global variables are the state variables
encapsulated in $StateName$
+ and $SeqStateName$. If a variable is not declared as an
input to
+ the process and is not a state variable, then it is local
to the function.
+
If a process is particularly complex, it may be broken
into a number of steps with
intermediate discussion. This is signalled by appending
and prepending ``$hdots$" to
***************
*** 255,304 ****
into a number of steps.
- subsubsection{Variables and data types}
- label
-
- The only global variables are the state variables
encapsulated in $StateName$
- and $SeqStateName$. If a variable is not declared as an
input to
- the process and is not a state variable, then it is local
to the function.
-
- The following basic types are defined:
- begin
- item[Boolean] A boolean variable has two possible states,
$true$ and $false$.
-
- item[Unsigned integer] A non-negative ($geq 0$) whole
number, of arbitrary size.
-
- item[Integer] A whole number, of arbitrary size.
-
- item[Set] A collection of variables or values with no
particular indexing.
- A set containing members $A,B,C,ldots$ is denoted
${A,B,C,ldots}$. The usual
- set-theoretic operations $cup$ (union), $cap$
(intersection), $in$ (membership)
- apply.
-
- item[Map]
-
- A map is a set accessed by token names. For example
- $p[Y]$, $p[C1]$, $p[C2]$ might give the value of the
different video components
- (Y, C1 and C2) of a pixel. The set of argument tokens of a
map $m$ can be accessed by $args(m)$,
- so that $args(p)={Y,C1,C2}$.
-
- item[Array]
-
- A list is a set with an integer index or indices. All
arrays are indexed from 0.
- Elements of a 1-dimensional array $a$ are accessed by
$a[n]$ for $n$ in the
- range 0 to $length(a)-1$. Elements of a 2-dimensional
array are accessed by
- $a[n][m]$ for $0leq mleqwidth(a)-1$ and $0leq
nleqheight(a)-1$.
-
- A 1-dimensional array can be explicitly defined by the
syntax $a=[u, v, w, hdots]$.
- Then $a[0]=u$,
- $a[1]=v$ and so on.
-
- end
-
- These basic variable types may be combined. For example,
picture data may be considered
- to be a map of arrays $pic$, where $pic[Y]$ is a
2-dimensional array storing luma data,
- and $pic[C1]$ and $pic[C2]$ are two-dimensional arrays
storing chroma data.
-
- Variables within processes are not explicitly declared,
and their type is determined from
- context or defined in the surrounding description.
paragraph{Assignment and equality}
--- 309,312 ----
Index: spec-structure.tex
============================================================
=======
RCS file:
/cvsroot/dirac/compress/doc/latex_spec/spec-structure.tex,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -d -r1.12 -r1.13
*** spec-structure.tex 18 Jun 2007 15:22:54 -0000 1.12
--- spec-structure.tex 21 Jun 2007 13:16:03 -0000 1.13
***************
*** 52,59 ****
clearpage
! section{Quantisation matrices (low delay syntax)}
input
clearpage
section{Video systems model and source parameters}
input
--- 52,63 ----
clearpage
! section{Quantisation matrices and weighting functions}
input
clearpage
+ section{Wavelet transform and lifting (Informative)}
+ input
+
+ clearpage
section{Video systems model and source parameters}
input
--- NEW FILE: lifting.tex ---
begin{informative*}
This is an informative appendix introducing the fundamentals
of wavelet
filtering and the lifting scheme. For a fuller explanation
see ?.
subsection{Wavelet filter banks}
Figure ref{fig:decimatereconstruct} below illustrates a
single stage of a
generalized wavelet decimation followed by reconstruction.
The aim is to
get perfect reconstruction of the output so that it is
identical to the original input.
end{informative*}
setlength
begin[!ht]
begin(50,20)
put(0,10){line(1,0)}
put(5,5){line(0,1)}
put(5,5){line(1,0)}
put(5,15){line(1,0)}
put(7,3){framebox(8,4){Large $h(-z)$}}
put(7,13){framebox(8,4){Large $g(-z)$}}
put(15,5){line(1,0)}
put(15,15){line(1,0)}
put(18.5,5)put(18,5){Large $downarrow 2$}
put(18.5,15)put(18,15){Large $downarrow 2$}
put(20,5){line(1,0)}
put(20,15){line(1,0)}
put(24,5){line(1,0)}
put(24,15){line(1,0)}
put(27.5,5)put(27,5){Large $uparrow 2$}
put(27.5,15)put(27,15){Large $uparrow 2$}
put(29,5){line(1,0)}
put(29,15){line(1,0)}
put(31,3){framebox(8,4){Large $tilde(z)$}}
put(31,13){framebox(8,4){Large $tilde(z)$}}
put(39,5){line(1,0)}
put(39,15){line(1,0)}
put(39.5,10){line(1,0){6.5}}
put(41,5){line(0,1)}
put(41,10)
begin{informative*}
end
caption{Wavelet decimation and
reconstruction}label{fig:decimatereconstruct}
end
The filters $h(z)$ and $g(z)$ are the low-pass and high-pass
analysis
filters, whilst $tilde(z)$ and $tilde(z)$ are the
synthesis filters. The filters must satisfy the conditions
begin{eqnarray*}
h(z)tilde(z^)+g(z)tilde(z^) & = & 2
text{ (Perfect reconstruction)}\
h(z)tilde(-z^)+g(z)tilde(-z^) & = &
0 text{ (Alias cancellation)}
end{eqnarray*}
These conditions imply that the synthesis filters are
derived from the analysis filters and vice-versa:
begin{eqnarray*}
tilde(z) & = & z^h(-z^) \
tilde(z) & = & z^g(-z^)
end{eqnarray*}
If we have an {em orthogonal} wavelet decomposition, then
additionally $H=tilde$ and $g=tilde$
and there is a single ``mother'' wavelet.
The next figure (F.2) illustrates how the frequency
components are distributed both during decimation and
reconstruction. This figures illustrates how the alias
frequencies created during the decimation process are
cancelled out during the reconstruction process. This
feature of alias cancellation results from the wavelet
process and is a specific attribute of wavelet coding. It is
important to note that if the decoder receives imperfect
signals (caused, for example, by quantisation errors) then
the imperfections will result in distortion in the
reconstructed output.
Figure F.2 -Illustration of the alias frequency generation
and cancellation in a wavelet filter bank
A single wavelet stage is insufficient for most video coding
applications. The figure below illustrates how only the
low-pass path is passed on to the next wavelet decimation
step. Because each step of the wavelet decimation is
self-contained, the reconstructed output is still identical
to the input (barring quantisation errors).
Figure F.3 -Two-step wavelet processing filter bank
The application of wavelet filter banks in picture coding
results in a two-dimensional decimation process as
illustrated in figure F.4 below.
Figure F.4 -Decomposition of a single image into 7 wavelet
frequency bands
The final figure illustrates how a real image is decimated
to produce a low-frequency proxy in the top-left corner and
a range of increasing frequency band components extending to
the right side for increasing horizontal frequencies and
downwards for increasing vertical frequencies.
Figure F.5 -Decomposition of the EBU "Boats"
picture into 7 wavelet frequency bands
subsection
label
For any set of filters, the analysis and synthesis filter
banks shown
in Figure ref{fig:decimatereconstruct} can easily be
re-expressed as polyphase
filter banks by means of applying {em matrices} of filters
in the subsampled
domain. This is shown in Figure ref{fig:polyphase}, where
$A(z)$ is the $z-$transform
of the analysis polyphase filter matrix, and $S(z)$ is the
$z-$transform
of the synthesis polyphase filter matrix (the entries of
both matrices being Laurent
polynomials).
end{informative*}
setlength
begin[!ht]
begin(50,20)
% Analysis side
put(0,9){line(1,0)}
put(2,5){line(0,1)}
put(2,5){line(1,0)}put(3,3.5){framebox(3,3){Large
$z$}}put(6,5){line(1,0)}
put(2,13){line(1,0)}
put(8.5,5)put(8,5){Large $downarrow 2$}
put(8.5,13)put(8,13){Large $downarrow 2$}
put(10,5){line(1,0)}
put(10,13){line(1,0)}
put(12,4){framebox(8,10){Large $A(z)$}}
put(20,5){line(1,0)}
put(20,13){line(1,0)}
% Synthesis side
put(23,5){line(1,0)}
put(23,13){line(1,0)}
put(24,4){framebox(8,10){Large $S(z)$}}
put(32,5){line(1,0)}
put(32,13){line(1,0)}
put(35.5,5)put(35,5){Large $uparrow 2$}
put(35.5,13)put(35,13){Large $uparrow 2$}
put(37,5){line(1,0)}put(38,3.5){framebox(3,3){Large
$z^$}}put(41,5){line(1,0)}
put(37,13){line(1,0)}
put(41,9){line(1,0)}
put(42,5){line(0,1)}
put(42,9)
end
caption{Polyphase representation of wavelet filter
banks}label{fig:polyphase}
end
begin{informative*}
In this representation, linear combinations of filters
operate on both even and
odd samples to produce new even and odd samples:
[
left(
begin
x^_e(z) \
x^_o(z)
end
right)
= A(z)
left(
begin
x^_e(z) \
x^_o(z)
end
right)
]
Since the filter process is invertible, it can be shown that
the analysis and
synthesis matrices are related by $A(z)=(S(z^)^T)^$.
Hence, in particular
both the analysis and synthesis matrices are invertible. It
can be shown that
this means that they are (up to gain factors and delays)
factorisable into
products of upper and lower triangular matrices:
[A(z)=
left(
begin
1 & a_1(z) \
0 & 1
end
right)
left(
begin
1 & 0 \
b_1(z) & 1
end
right)
left(
begin
1 & a_2(z) \
0 & 1
end
right)
ldots
]
Each upper- or lower-triangular polyphase matrix represents
a so-called {em lifting} stage
whereby either even coefficients are modified solely by odd
coefficients or odd coefficients
solely by even coefficients. For example, if
[
left(
begin
x^_e(z) \
x^_o(z)
end
right)
=
left(
begin
1 & a(z) \
0 & 1
end
right)
left(
begin
x^_e(z) \
x^_o(z)
end
right)
]
then
begin{eqnarray*}
x^_e(z) & = & x^_e(z) + a(z)x^_o(z) \
x^_o(z) & = & x^_o(z)\
end{eqnarray*}
and the filter $a(z)$ has been applied to the odd
coefficients and then used to modify
the even coefficients. Not only is this computationally
efficient, breaking long
filters into a number of shorter filter applied successively
but the
factorisation into such filter stages allows for all
computations to be done in-place,
without additional memory.
end{informative*}
------------------------------------------------------------
-------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and
take
control of your XML. No limits. Just data. Click to get it
now.
http://sourcefor
ge.net/powerbar/db2/
_______________________________________________
Dirac-commits mailing list
Dirac-commits lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/dirac-com
mits
|