texput.tex

% Emacs, this is -*-latex-*-

\title{\href{https://github.com/vicente-gonzalez-ruiz/quantization}{Quantization}}

\author{Vicente González Ruiz}

\maketitle

\section{\href{https://en.wikipedia.org/wiki/Quantization\_(signal\_processing)}{Basics}}

\begin{figure}
  \svg{cuantif}{500}
  \caption{The quantization procedure.}
  \label{fig:cuantif}
\end{figure}

\begin{itemize}
\tightlist

\item
  A quantizer discretizes the amplitude of a
  \href{https://en.wikipedia.org/wiki/Pulse-amplitude_modulation}{PAM
    signal} \(s(nT_s)\) (where $s$ is an analog signal,
  $n\in{\mathbb{Z}}$ and $T_s$ is a sampling period), producing an
  analog
  \href{https://en.wikipedia.org/wiki/Pulse-code_modulation}{PCM
    signal} $s[n]$ (see Fig.~\ref{fig:cuantif}). Therefore,
  quantization maps the values of samples (that are defined in a
  continous space) into a discrete set of values
  \cite{vetterli1995wavelets}.

\item
  The quantization process can be modeled as
  \begin{equation}
    s[n] = s(nT_s) + e(nT_s),
  \end{equation}
  being \(e(nT_s)\) an unpredectible quantization error (also called,
  quantization noise). Quantization produces a loss of information in
  the signal because we cannot recover $s(nT_s)$ from $s[n]$ without
  $e(nT_s)$.

\item
  Quantizers are defined from their set of \(d_i; i\in {\mathbb{Z}}\)
  (\emph{decision levels}) and \(r_i; i\in {\mathbb{Z}}\)
  (\emph{representation levels}). $\{d_i\}$ and $\{r_i\}$ must be
  finite.

\item Another design parameter of quantizers is the
  \emph{decision boundaries} $d_{\text{min}}$ and $d_{\text{max}}$,
  ($d_{\text{min}}<d_{\text{max}}$) that define the so called \emph{low
    and high overload regions}, respectively, as
  \begin{equation}
    s[n] = \{\begin{array}{ll}
    r_{\text{min}}, & \text{if $s(nT_s)<d_{\text{min}}$} \\
    r_{\text{max}}, & \text{if $s(nT_s)>d_{\text{max}}$} \\
    s(nT_s)+e(nT_s), & \text{otherwise}.
    \end{array}
  \end{equation}
  
\item For the sake of simplicity, lets denote the inputs of the
  quantizer as $x (=\{s(nT_s)\})$ and the outputs as $y
  (=\{s[n]\})$. The performance of the quantizer can be measured as the
  distance between the input $x$ and the output $y$, and typically the
  squared error is used:
  \begin{equation*}
    d(x,y) = |x-y|^2.
  \end{equation*}
  Thus, the MSE is
  \begin{equation}
    \text{MSE} = E(|x-y|^2)=\sum_i\int_{x_{i-1}}^{x_i} (x-y_i)^2f_X(x)dx,
  \end{equation}
  where $f_X(x)$ is the
  \href{https://en.wikipedia.org/wiki/Probability_density_function}{probability
    density function (PDF)} of $x$ and $E(\cdot)$ the
  \href{https://en.wikipedia.org/wiki/Expected_value}{expectation}.

\end{itemize}

\section{Scalar quantization}
\begin{itemize}
\item In a scalar quantizer, each input sample $x_i$ is individually
  quantized as $y_i$, and the quantization error, determined by
  \begin{equation*}
    \{e_i\}=\{y_i\}-\{x_i\},
  \end{equation*}
  can be modeled as a noise process that: (1) is uncorrelated to the
  input $x$, (2) is white, and (3) follows a uniform
  distribution. However, this can only be done when the quantization
  step
  $\Delta<<\href{https://en.wikipedia.org/wiki/Standard_deviation}{\sigma_x}$~\cite{vetterli1995wavelets}.

\end{itemize}

\section{Uniform (lineal) scalar quantization}
\begin{itemize}

\item
  In an uniform quantizer (see Fig.~\ref{fig:cuantif}), the
  quantization step \(\Delta\) satisfies that the input range is
  divided into intervals of constant size
  \begin{equation}
    \Delta=d_{i+1}-d_i=r_{i+1}-r_i.
  \end{equation}
  %Therefore,
  %\begin{equation}
  %  Q=\frac{1}{\Delta}
  %\end{equation}
  %and
\item We define the number of decision levels as
  \begin{equation}
    Q=\frac{d_{\text max}-d_{\text min}}{\Delta}.
    \label{eq:delta_definition}
  \end{equation}

  \begin{figure}
    \svg{midrise}{600}
    \caption{An uniform midrise quantizer (see the
      \href{https://nbviewer.jupyter.org/github/vicente-gonzalez-ruiz/quantization/blob/master/graphics/midrise.ipynb}{notebook}). $\Delta=1$
      and $Q=13$ (the decision boundaries have been ignored). The
      decision levels ($x$) are $\{\cdots,-3,-2,-1,0,1,2,3,\cdots\}$
      and the representation levels ($y$) are
      $\{\cdots,-2.5,-1.5,-0.5,0.5,1.5,2.5,\cdots\}$.}
    \label{fig:midrise}
  \end{figure}
  
  \begin{figure}
    \svg{midtread}{600}
    \caption{An uniform midtread quantizer (see the
      \href{https://nbviewer.jupyter.org/github/vicente-gonzalez-ruiz/quantization/blob/master/graphics/midtread.ipynb}{notebook}). $\Delta=1$
      and $Q=12$ (the decision boundaries have been ignored). The
      decision levels ($x$) are $\{\cdots,-2.5,-1.5,-0.5,0.5,1.5,2.5,\cdots\}$
      and the representation levels ($y$) are
      $\{\cdots,-2,-1,-0,1,2,\cdots\}$.}
    \label{fig:midtread}
  \end{figure}

  \begin{figure}
    \svg{deadzone}{600}
    \caption{An uniform deadzone quantizer (see the
      \href{https://nbviewer.jupyter.org/github/vicente-gonzalez-ruiz/quantization/blob/master/graphics/deadzone.ipynb}{notebook}). $\Delta=1$
      and $Q=12$ (the decision boundaries have been ignored). The
      decision levels ($x$) are $\{\cdots,-3,-2,-1,1,2,3,\cdots\}$
      and the representation levels ($y$) are
      $\{\cdots,-2,-1,-0,1,2,\cdots\}$.}
    \label{fig:deadzone}
  \end{figure}

\item
  Under the premise that $e$ is uniform, and considering that
  $y_i=(x_{i-1}+x_i)/2$ (something quite reasonable when $x$ can also be
  considered as uniform) the average quantization error is
  $\frac{Z}{4}$ ($\frac{Z}{2}$ is the meximum and $0$ is the minimum),
  and for this particular case
  \begin{equation}
    \text{MSE} =
    \frac{1}{\Delta}\int_{-\Delta/2}^{\Delta/2}e^2de=\frac{\Delta^2}{12}.
    \label{eq:MSE_uniform_scalar_quantizer}
  \end{equation}
  
\item
  Uniform quantizers are used in most A/D (analogic/digital)
  converters, were it is expected the generation of uniformely
  distributed sequences of samples.

\end{itemize}

\subsection{Using codewords (encoding)}
\begin{itemize}
  \tightlist
  
\item
  Depending on the number of \(Q\) different possible values (or
  \emph{bins}) for \(s[\cdot]\), we speak of a
  \(q=\lceil\log_2(Q)\rceil\)-bits quantizer (this means that the
  output of the quantizer are \(q\) bits for each sample, or that we
  have \(2^q\) representation levels). For the simple, $r_i=i$ and the
  input intervals are of the form $(d_{i-1},d_i]=(i-1/2,i+1/2]$.

\item
  When we quantize digital signals, these are sequences of digital
  samples represented by symbols of a given alphabet, typically, a
  subset of \({\mathbb{Z}}\) or \({\mathbb{N}}\). Therefore, both the
  input and the output of the quantizer are indexes, not real values
  of a sampled signal. The set $\{r_i\}$ is called the codebook and
  the $r_i$ the codewords.

\item If $R$ is the number of bits of the quantizer (for example, in
  the quantizer of the Fig.~\ref{fig:cuantif},
  $R=\lceil\log_2(5)\rceil=3$-bits and$(Q=8)$), $\Delta$ decreases as
  $\frac{1}{2^R}$. Considering
  Eq.~\ref{eq:MSE_uniform_scalar_quantizer} and
  Eq.~\ref{eq:delta_definition}, we get that
  \begin{equation}
    \text{MSE} = \frac{\Delta^2}{12} = \frac{(d_{\text max}-d_{\text min})^2}{12Q^2}.
  \end{equation}
  Considering now that $\sigma^2_x=\frac{(d_{\text max}-d_{\text
      min})^2}{12}$ for uniform input PDF, we obtain that
  \begin{equation}
    \text{MSE} =
    \sigma_x^22^{-2R}.
  \end{equation}

\item
  Now, if we add a bit to $R$, $R^{+1}=R+1$, then
  \begin{equation*}
    \text{MSE}^{+1}=2^{-2(R+1)}\sigma_x^2 = 2^{-2}2^{-2R}\sigma_x^2,
  \end{equation*}
  and
  \begin{equation*}
    \text{SNR}^{+1} = 10\log_{10}\frac{\sigma_x^2}{\text{MSE}^{+1}} = 10\log_{10}4\frac{\sigma_x^2}{\text{MSE}} =
    10\log_{10} 4 + \text{SNR} \approx  6~\text{dB} + \text{SNR}.
  \end{equation*}
  This result is interesting because in a PCM system, the quality of
  the signal is incremented $6$ dB with each bit. Notice that in
  \href{https://en.wikipedia.org/wiki/High_fidelity}{HiFi}, the SNR
  must be at least of $96$ dB, and
  \begin{equation*}
    \frac{96}{6} = 16,
  \end{equation*}
  the number of bits per sample used in the
  \href{https://en.wikipedia.org/wiki/Compact_disc}{Audio CDs}.
  
%\item
%  Therefore, in this context, \(\Delta\) represents the length of the
%  intervals of indexes what will be ignored.
\end{itemize}

\subsection{Exersize}
Quantize
\href{https://upload.wikimedia.org/wikipedia/commons/3/3a/Jfk_berlin_address_high.ogg}{Jfk\_berlin\_address\_high.ogg}
using \(\Delta=2\). Compute the variance of both audio sequences.

\section{Non-uniform quantization}
\begin{itemize}
  \tightlist
\item
  In order to minimize the maximun, average or the total quantization
  error, \(\Delta\) can be adapted to the characteristics of \(s\).
\end{itemize}

\section{Companded quantization~\cite{sayood2017introduction}}
\begin{itemize}
\item
  Non-uniform quantizer.
\item
  \href{https://en.wikipedia.org/wiki/Companding}{Companding}:
  COMpressing + exPANDING. The original signal is mapped through a
  compressor, quantized using an uniform quantized, and re-mapped using
  the corresponding expander. The result is a logarithmic quantization.
\item
  \href{https://en.wikipedia.org/wiki/\%CE\%9C-law_algorithm}{\(\mu\)-law}
  example:
\end{itemize}

\href{https://nbviewer.jupyter.org/github/vicente-gonzalez-ruiz/quantization/blob/master/graphics/companded_quantization.ipynb}{notebook}

\begin{figure}
  \svg{ulaw-compressor}{600}
  \svg{ulaw-expander}{600}
  \svg{companded}{600}
  \caption{Insights of a companded quantizer.}
  \label{fig:companded_quantizer}
\end{figure}

\section{PDF-optimized quantization}
\begin{itemize}
\item
  Non-uniform quantizer.
\item
  if we known the probability distribution of the samples, we can select
  a small \(\Delta\) for the most probable samples and viceversa.
\end{itemize}

\svg{cuantif_max-lloyd}{600}

\section{Adaptive quantization}
\begin{itemize}
\item
  Useful when the characteristics of \(s\) (the variance, for example)
  vary over time.
\item
  Typically, the quantizer varies \(\Delta\) depending on such
  characteristics.
\end{itemize}

\section{Forward adaptive quantization}
\begin{itemize}
\item
  Used for determining a suitable \(\Delta\) for blocks of samples.
\item ~
  \hypertarget{encoder}{%
  \subsubsection*{Encoder:}\label{encoder}}

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    While samples in \(s\):

    \begin{enumerate}
    \def\labelenumii{\arabic{enumii}.}
    \tightlist
    \item
      Read into \(b\) the next \(B\) samples of \(s\).
    \item
      Determine \(\Delta\), minimizing the quantization error, and
      output \(\Delta\) (or the data necessary for its determination).
    \item
      Quantize \(b\) and output it.
    \end{enumerate}
  \end{enumerate}
\item ~
  \hypertarget{decoder}{%
  \subsubsection*{Decoder:}\label{decoder}}

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    While data in input:

    \begin{enumerate}
    \def\labelenumii{\arabic{enumii}.}
    \tightlist
    \item
      Read \(\Delta\) (or the data necessary for determining it, and in
      this case, use the same algorithm that the used by the encoder).
    \item
      ``Dequantize'' \(b\) and output it (note that the dequantization
      is only a way of calling the process of reverting the original
      range of the quantized signal).
    \end{enumerate}
  \end{enumerate}
\item
  The selection of \(B\) is a trade-off between the increase in side
  information needed by small block sizes and the loss of fidelity due
  to large block sizes.
\item
  Forward adaptive quantization generates a
  \(B\text{-samples}\times f_s\) delay (buffering), where \(f_s\) is the
  sampling rate of \(s\).
\end{itemize}

\section{Backward adaptive quantization}
\begin{itemize}
\item
  Only the previously quantized samples are available to use in adapting
  the quantizer.
\item
  Idea: If happens that \(\Delta\) is smaller than it should be, the
  input will fall in the outer levels of the quantizer a high number of
  times. On the other hand, if \(\Delta\) is larger than it should be,
  the samples will fall in the inner levels a high number of times.
\item ~
  \hypertarget{encoder}{%
  \subsubsection*{Encoder:}\label{encoder}}

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    \(\Delta\leftarrow 2\).
  \item
    While \(s\) is not exhausted:

    \begin{enumerate}
    \def\labelenumii{\arabic{enumii}.}
    \tightlist
    \item
      Quantize the next sample.
    \item
      Observe the output and refine \(\Delta\).
    \end{enumerate}
  \end{enumerate}
\item ~
  \hypertarget{decoder}{%
  \subsubsection*{Decoder:}\label{decoder}}

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \tightlist
  \item
    \(\Delta\leftarrow 2\).
  \item
    While \(\hat{s}\) is not exhausted:

    \begin{enumerate}
    \def\labelenumii{\arabic{enumii}.}
    \tightlist
    \item
      ``Dequantize'' the next sample.
    \item
      Step 2.B of the encoder.
    \end{enumerate}
  \end{enumerate}
\end{itemize}

\section{The Jayant quantizer~\cite{jayant1974digital}}
\begin{itemize}
\item
  Adaptive quantization with a one word memory (\(\Delta_{(t-1)}\)).
\item
  A Jayant quantider defines the Step 2.B. as: Define a multiplier
  \(M_l\) for each quantization level \(l\), where for the inner levels
  \(M_l<1\) and for the outer levels \(M_l>1\), and compute:

  \[
    \Delta^{[n]} = \Delta^{[n-1]}{M_l}^{[n-1]},
  \]

  where \(\Delta^{[n-1]}\) was the previous quantization step and
  \({M_l}^{[n-1]}\) the level multiplier for the \(n-1\)-th (previous)
  sample. Thus, if the previous (\(n-1\)) quantization used a
  \(\Delta^{[n-1]}\) too small (using outer quantization levels) then
  \(\Delta^{[n]}\) will be larger and viceversa.
\item
  Depending on the multipliers \(M\), the quantizer will converge or
  oscillate. In the first case, the quantizer will be good for small
  variations of \(s\) but bad when a fast adaption to large changes in
  \(s\) is required. In the second one, the quantizer will adapt quickly
  to fast variations of \(s\) but will oscillate when \(s\) changles
  slowly.
\item
  Most Jayant quantizers clip the computation of \(\Delta\) to avoid
  generating a zero output quantizer in those contexts where \(s\) is
  zero or very close to zero, and to improve the adaptation to smaller
  samples after a sequence of bigger ones (avoiding to grow without
  limit):

  \[
  \begin{array}{ll}
    \text{if}~\Delta^{[n]}<\Delta_{\text{min}}~\text{then}~\Delta^{[n]} = \Delta_{\text{min}},\\
    \text{if}~\Delta^{[n]}>\Delta_{\text{max}}~\text{then}~\Delta^{[n]} = \Delta_{\text{max}}.
  \end{array}
  \]
\end{itemize}

\section{Adapting with a scale factor}
\begin{itemize}
\item
  A Jayant quantized adapts the quantization step to the dynamic range
  of the signa using a set of multipiers. A similar effect can be
  provided by dividing the input signal by a scale factor defined
  iteratively as:

  \begin{equation}
    \alpha^{[n]} = \alpha^{[n-1]}M_l^{[n-1]}.
  \end{equation}
\end{itemize}

\subsection{Exercise}
Quantize
\href{https://upload.wikimedia.org/wikipedia/commons/3/3a/Jfk_berlin_address_high.ogg}{Jfk\_berlin\_address\_high.ogg}
using \(4\)-bits backward adaptive Jayant quantizer. Reproduce the
quantized sequence and provide a subjective comparison with the original
sequence.

\section{Vector quantization}
\begin{itemize}
\item Samples are quantized in groups (vectors).
\end{itemize}
  
\section{Perceptual quantization}
An important consideration is the relative perfectual importante of
the input samples. This leads to a weighting of the MSE at the
output. The weighting function can be derived through experiments to
determine the ``level of just noticeable noise''. For example, in
subband coding, as expected, high freq. subbands tolerate more noise
because the HVS becomes less sensitive at them.

\bibliography{quantization,DWT,data-compression}