\documentclass[mathserif,professionalfonts,compress,slidestop,10pt]{beamer}
 
\mode<presentation>
 
\usepackage[utf8x]{inputenc}
\usepackage[italian]{babel}
\usepackage{default}
\usepackage{iwona}
\usepackage[T1]{fontenc}
% \usepackage{rotate}
 
 
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{subfigure}
 
% Comandi miei, ovvero piccole cose matematiche che
% ci saranno utili in seguito.
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\hat}{\widehat}
\renewcommand{\tilde}{\widetilde}
\newcommand{\upsample}[1]{\makebox[0.85\width]{$\uparrow$}_{#1}}
\newcommand{\downsample}[1]{\makebox[0.85\width]{$\downarrow$}^{#1}}
\newcommand{\pausaindice}{
\begin{frame} \frametitle{Outline}
  \tableofcontents[current]
\end{frame}}
% \newcommand{\downsample}[1]{\downarrow{#1}}
 
% Il nostro tema
% \usetheme{CambridgeUS}
\usetheme{Antibes}
\usecolortheme{dolphin}
\beamertemplateshadingbackground{blue!10}{blue!2}
\setbeamercovered{transparent=15}
 
% Chi siamo e cosa facciamo
\author{Leonardo Robol \\ \scriptsize \href{mailto:robol@poisson.phc.unipi.it}{\texttt{robol@poisson.phc.unipi.it}} \normalsize }
\title{Wavelet e signal processing}
\subtitle{Trasformata wavelet discreta tramite filter banks}
 
\begin{document}
 
% Pagina principale
\begin{frame}[plain]
 \titlepage
\end{frame}
 
% \begin{frame} \frametitle{Outline}
%  \tableofcontents[pausesections]
% \end{frame}
 
%
% Teoremi
%
\theoremstyle{plain} \newtheorem{teo}{Teorema}
\theoremstyle{remark} \newtheorem{de}{Definizione}
\theoremstyle{remark} \newtheorem{os}{Osservazione}
\theoremstyle{remark} \newtheorem{problema}{Problema}
 
%
% Cominciamo a capire cosa ci interessa di un segnale e come lo vogliamo
% guardare.
%
\section{Manipolazione di segnali}
\subsection{Segnali analogici e segnali digitali}
\pausaindice
% FRAME: Cosa sono i segnali
\begin{frame}\frametitle{Segnali}
	Un \emph{segnale analogico x} è una funzione $x_{analog}: \R \to \R$.
 
	Quasi tutti i sengali ``nascono''
	in forma analogica ma vengono \emph{campionati} per essere rappresentati come
	\[
		\left\{ \begin{array}{ll}
		  x_{digital}(n): & \Z  \to  \R \\
		  x_{digital}(n)= &  x_{analog}(nT) \\
	  \end{array} \right.
	\]
	dove $T \in \R$ è l'\emph{intervallo di campionamento}.
 
	Questo permette di memorizzare un segnale analogico su un supporto digitale (i.e. un computer).
\end{frame}
 
% FRAME: Shannon sampling theorem
\begin{frame} \frametitle{Shannon sampling theorem}
 
	Quando un segnale viene campionato molta ``informazione'' viene scartata. Se però il segnale
	è \emph{band-limited} allora questo non crea nessun problema, come ci dice il seguente teorema:
	\begin{teo}
		Ogni segnale analogico le cui frequenze non superano un dato $\omega_{max} \in \R_+$
		può essere ricostruito dal suo campionamento $x(nT)$ se $\frac{1}{T} > \frac{\omega_{max}}{\pi}$.
	\end{teo}
 
	%% Commento allo shannon sampling theorem
	\begin{de}
	  Il valore $\frac{\omega_{max}}{\pi}$ viene chiamato \emph{Nyquist period}.
	\end{de}
\end{frame}
 
% FRAME: Aliasing
\begin{frame} \frametitle{Aliasing}
 
	% Un po' di spettacolo
	\transdissolve[duration=0.2]<2>
	\transdissolve[duration=0.2]<3>
 
	Cosa succede quando non è soddisfatta l'identità $T^{-1} > \omega_{max} \pi^{-1}$?
 
	Osserviamo il seguente esempio:
 
  \begin{itemize}
		\only<1-> {\item	Sia $x(t) = sin(\omega x)$.	}
		\uncover<2-> {		\item Consideriamo il sampling $x(nT)$ con $T = \frac{3\pi}{2\omega}$. }
	  \uncover<3-> { \item Si ottiene lo stesso sampling che per $\hat x_{alias}(t) = \sin(\frac{\omega}{3}t)$, e quindi il segnale non può
					venire ricostruito. }
	\end{itemize}
 
  \begin{figure}
	\begin{tikzpicture}[domain=0:7,samples=150]
		\draw[->] (0,0) -- (8,0) node[anchor=west]{$t$};
		\draw[->] (0,0) -- (0,1.5) node[anchor=south]{$sin(\omega t)$};
 
		% Disegno la funzione
		\only<1->{
			\draw[color=blue] plot[id=signal] function {sin(5*x)};
		}
 
		% Disegno i puntini del sampling
		\visible<2->{
			\foreach \x in {0,1.8849,...,7}
				{\fill (\x, 0) circle (0.05cm);}
			\foreach \x in {0.94,4.71,...,7}
				{\fill (\x, -1) circle (0.05cm);}
			\foreach \x in {2.81,6.59,...,7}
				{\fill (\x, 1) circle (0.05cm);}
		}
 
		% Disegno la funzione alias
		\visible<3-> {
			\draw[color=red] plot[id=aliasedsignal] function {-1 * sin( 1.666667 * x)};
		}
	\end{tikzpicture}
	\caption{Esempio di aliasing}
	\end{figure}
\end{frame}
 
% FRAME: Cosa sono i filtri
\subsection{Filtri e FIR}
\begin{frame} \frametitle{Filtri}
	Supponiamo di avere il segnale campionato $x(nT)$; d'ora in poi
	supporremo $T = 1$ per semplicità.
 
  \begin{de}
	Un \emph{filtro} è un'applicazione che manda $x(n)$ in un altro segnale $y(n)$.
	Diremo che un filtro è
	\begin{description}
		\item[causale] se $y(n)$ è funzione unicamente di $x(n), x(n-1), \ldots$;
		\item[FIR\footnote{che sta per finite impulse response.}] se $y(n)$ si può ottenere con un numero finito di
		campioni di $x(n)$ per ogni $n$;
	\end{description}
	\end{de}
 
	I filtri FIR e causali sono interessanti perché possono essere calcolati
	in \emph{real--time}.
 
\end{frame}
 
% FRAME: Esempio di filtro
\begin{frame} \frametitle{Esempio di filtro}
	Sia $h \in \R^n$ e consideriamo il filtro:
	\[
		x(n) \longrightarrow y(n) = \sum_{i=1}^{n} h_{i} x(n - i)
	\]
	Questo è sia FIR che causale. Consideriamo i seguenti segnali:
	\[
		\left\{ \begin{array}{l}
			x_1(n) = ( \ldots , 1 , 1 , 1 , 1 , 1 , \ldots ) \\
			x_2(n) = ( \ldots , 1 , -1 , 1 , -1 , 1 , \ldots ) \\
		\end{array} \right.
	\]
	ed i seguenti filtri:
	\[
		\left\{ \begin{array}{l}
			h_0 = ( \frac{1}{2}, \frac{1}{2} ) \\
			h_1 = ( \frac{1}{2}, - \frac{1}{2} ) \\
		\end{array} \right.
	\]
 
	Si ottengono i seguenti output:
	\[
		h_0x_0 = x_0 \qquad h_1x_0 \equiv 0 \qquad h_0x_1 \equiv 0 \qquad h_1x_2 = x_2
	\]
 
\end{frame}
 
\begin{frame} \frametitle{Frequency response}
	%$h_0$ è un \emph{lowpass filter}, perché elimina le alte frequenze lasciando invariate quelle
	%basse, mentre $h_1$ è un \emph{highpass filter} perché mantiene le alte frequenze eliminando
	%quelle basse.
%
%	Osserviamo che per ogni $\omega$ e per ogni $h$, $h * {e^{in\omega}} = H(\omega)e^{in\omega}$ e quindi
%	$e^{inw}$ è un autovettore per il filtro. Il suo autovalore $H(\omega)$ viene detto
%	\emph{frequency response} del filtro alla frequenza $\omega$.
 
  Sia $x(n) = e^{in\omega}$. Questo è un autovettore per il filtro:
  \[
    h * \{e^{in\omega}\} = \sum_{i=0}^{N} h_i e^{i(n-i)\omega} =
    e^{in\omega} \underbrace{\sum_{i=0}^{N} e^{-i\omega}}_{\textrm{autovalore } H(\omega)}
  \]
 
	\vskip 10pt
 
 	\uncover<2-> {
	Consideriamo un segnale generico $x(n)$, e la sua trasformata di Fourier $X(\omega)$.
 
	La trasformata di Fourier $Y(\omega)$ del segnale $y(n)$ ottenuto dopo l'applicazione del filtro
	sarà
	\[
		Y(\omega) = X(\omega) H(\omega)
	\]
  }
\end{frame}
 
 
\begin{frame} \frametitle{Lowpass e Highpass}
 
%	Nell'esempio precedente abbiamo
	\begin{figure}
	\subfigure{
		\begin{tikzpicture}[domain=0:1.57, samples=150,scale=1.5]
			\draw[->] (0,0) -- (1.9,0) node[anchor=west] {$\omega$};
			\draw[->] (0,-0.1) -- (0,1.1) node[anchor=south] {$H_0(\omega)$};
 
			\draw[color=blue] plot[id=h0resp] function {cos(x)};
		\end{tikzpicture}
	}
	\subfigure {
		\begin{tikzpicture}[domain=0:1.57, samples=150,scale=1.5]
			\draw[->] (0,0) -- (1.9,0) node[anchor=west] {$\omega$};
			\draw[->] (0,-0.1) -- (0,1.1) node[anchor=south] {$H_1(\omega)$};
 
			\draw[color=blue] plot[id=h1resp] function {sin(x)};
		\end{tikzpicture}
	}
 
	\caption{Frequency response di $h_0$ ed $h_1$}
	\end{figure}
 
  \begin{description}
  \item[$H_0(\omega)$]	Il filtro $h_0$ si dice \emph{lowpass} perché lascia invariati i segnali
	a bassa frequenza, mentre elimina quelli ad alta frequenza.
 
  \item[$H_1(\omega)$]	Analogamente $h_1$ si dice \emph{highpass}.
	\end{description}
 
\end{frame}
 
\subsection{Upsampling e downsampling}
\begin{frame} \frametitle{Downsampling}
 
	\begin{de}
	Diremo che $y(n)$ è il \emph{downsampling} di $x(n)$ e lo indicheremo con
	$y(n) = \downsample{k}x(n)$ se
	\[
	  y(n) = x(kn) \quad \textrm{dove } k \in \N
	\]
	\end{de}
 
	\begin{example}
	  Applichiamo il downsampling ad un numero finito di samples:
	  Se $x = (1, 5, 3, 2, 6, 4, 8) = x(0) \ldots x(6)$ si ha
	  \[
	    \downsample{3}x = (1, 2, 8) \qquad \downsample{2}x = (1,3,6,8)
	  \]
	\end{example}
 
\end{frame}
\begin{frame} \frametitle{Upsampling}
 
	Per ``invertire'' il downsampling applicheremo l'\emph{upsampling}:
	\begin{de}
	Diremo che $x(n)$ è l'upsampling di $y(n)$ di un fattore $k$ e lo
	indicheremo con $x(n) = \upsample k y(n)$ se
	\[
	  x(n) = \left\{ \begin{array}{ll}
	    y(\frac{n}{k}) & \textrm{se } n \textrm{ è multiplo di } k \\
	    0 & \textrm{altrimenti}
	  \end{array} \right.
	\]
	\end{de}
	\begin{os}
	  Il downsampling è l'inverso dell'upsampling ma non viceversa, ovvero
	  \[
	    \downsample{k}\upsample{k} x(n) = x(n) \quad \textrm{ma} \quad \upsample{k}\downsample{k} x(n) \neq x(n)
	  \]
	\end{os}
\end{frame}
 
 
 
 
 
%
%
%                          %%%%%%%%%%%%%%%%%%
%                          SEZIONE filter bank
%                          %%%%%%%%%%%%%%%%%%
%
%
%
%
\section{Filter Bank}
\pausaindice
\subsection{Cos'è una filter bank}
\begin{frame} \frametitle{Struttura di una filter bank}
  Possiamo immaginare una \emph{filter bank} come una successione di filtri
  che, partendo, da uno o più segnali di input $x(n)$ produca uno o più segnali
  di output $y_{0}(n) \ldots y_{1}(n)$. \\[15pt]
  Questo esempio prende un input (in giallo) e restituisce tre output (in blu).
  \begin{figure}
    \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
    \tikzstyle{place}=[rectangle,draw=blue!80,fill=white!20]
    \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
    \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
 
    	%% Disegnamo i pezzetti
      \node [input] (inputsignal) {$x(n)$};
      \node [place] (y0) [right of=inputsignal, yshift=25pt] {$y_0(n)$};
      \node [output] (y1) [right of=inputsignal, yshift=-25pt] {$y_1(n)$};
			\node [output] (y00)[right of=y0, yshift=20pt] {$y_{00}(n)$};
			\node [output] (y01)[right of=y0, yshift=-20pt] {$y_{01}(n)$};
 
			%% .. e li colleghiamo
			\draw[->] (inputsignal.east) -- (y0.west);
			\draw[->] (inputsignal.east) -- (y1.west);
			\draw[->] (y0.east) -- (y01.west);
			\draw[->] (y0.east) -- (y00.west);
 
    \end{tikzpicture}
    \caption{Esempio di filter bank}
  \end{figure}
\end{frame}
 
\begin{frame} \frametitle{Perché una filter bank?}
 
  Le filter bank ci permettono di scomporre (e ricomporre un segnale). Questo ci è utile per:
 
  \vskip 20pt
 
	\begin{description}
	  \item[Analisi] Vorremmo avere il segnale in una forma che metta in evidenza
	  la decomposizione in frequenze del segnale e contemporaneamente la localizzazione
	  temporale degli ``eventi'';
 
	  \vskip 25pt
 
	  \item[Compressione] Vorremmo scomporre il segnale in piccole componenti più idonee ad
	  essere compresse (ovvero che contengano dati 	omogenei);
	\end{description}
 
\end{frame}
 
\subsection{Analysis e Synthesis filter bank}
 
\begin{frame}
	\frametitle{}
%	Consideriamo i seguenti filtri e filter bank:
%	\[
%	  h_0 = (\frac{1}{2}, \frac{1}{2}) \qquad h_1 = (\frac 1 2 , - \frac{1}{2}) \qquad
%	  f_0 = (\frac{1}{2}, \frac{1}{2}) \qquad f_1 = (-\frac 1 2 , \frac{1}{2})
%	\]
 
	\begin{figure}
    \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
    \tikzstyle{title}=[rectangle,draw=blue!80,fill=white!20]
    \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
    \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
 
    	%% Disegnamo i pezzetti
      \node [input] (inputsignal) [xshift=10mm] {$x(n)$};
      \node [input] (y0) [right of=inputsignal, yshift=10pt, xshift=10mm]  {$y_0(n) = h_0 * x(n)$};
      \node [input] (y1) [right of=inputsignal, yshift=-10pt, xshift=10mm] {$y_1(n) = h_1 * x(n)$};
 
      \node [output] (y0down) [right of=y0, xshift=15mm] {$\tilde{y_0}(n) = \downsample{2}y_0(n)$};
      \node [output] (y1down) [right of=y1, xshift=15mm] {$\tilde{y_1}(n) = \downsample{2}y_1(n)$};
 
			%% .. e li colleghiamo
			\draw[->] (inputsignal.east) -- (y0.west);
			\draw[->] (inputsignal.east) -- (y1.west);
 
			\draw[->] (y0.east) -- (y0down.west);
			\draw[->] (y1.east) -- (y1down.west);
 
		\end{tikzpicture}
		\caption{Analysis filter bank}
	\end{figure}
 
 
	\begin{figure}
    \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
    \tikzstyle{title}=[rectangle,draw=blue!80,fill=white!20]
    \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
    \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
 
 
    	%% Disegnamo i pezzetti
      \node [input] (inputsignal0) [xshift=10mm, yshift=3.5mm]  {$\tilde{y_0}(n)$};
      \node [input] (inputsignal1) [xshift=10mm, yshift=-3.5mm] {$\tilde{y_1}(n)$};
 
      \node[input] (inputsignal0up) [right of=inputsignal0, xshift=5mm] {$z_0(n) = \upsample{2} \tilde{y_0}(n)$};
      \node[input] (inputsignal1up) [right of=inputsignal1, xshift=5mm] {$z_1(n) = \upsample{2} \tilde{y_1}(n)$};
 
      \node [output] (xn) [right of=inputsignal0up, xshift=25mm, yshift=-3.5mm]  {$x(n) = f_0*z_0(n) + f_1*z_1(n)$};
 
			%% .. e li colleghiamo
			\draw[->] (inputsignal0up.east) -- (xn.west);
			\draw[->] (inputsignal1up.east) -- (xn.west);
			\draw[->] (inputsignal0.east) -- (inputsignal0up.west);
			\draw[->] (inputsignal1.east) -- (inputsignal1up.west);
 
 
		\end{tikzpicture}
		\caption{Synthesis filter bank}
	\end{figure}
	\begin{problema}
	Trovare condizioni necessarie per ricostruire un segnale decomposto con l'analysis filter bank
	tramite la synthesis filter bank.
	\end{problema}
\end{frame}
 
\begin{frame} \frametitle{Analysis filter bank}
 
  Analizziamo un segnale ad una frequenza fissata $\{e^{in\omega}\}$.
 
  \vskip 10pt
 
	$\{e^{in\omega}\}$ è un autovalore per
	$h_0$ e $h_1$ e quindi dopo il primo passaggio dell'Analysis filter bank si ottiene
	\[
	y_0(n) = H_0(\omega)e^{in\omega} \qquad y_1(n) = H_1(\omega)e^{in\omega}
	\]
 
	\vskip 15pt
%
%  \begin{os}
%  Con questo filtraggio abbiamo separato le alte frequenze dalla basse frequenze; ora però
%  ci sono \textbf{il doppio} dei samples di prima e quindi il segnale occupa
%  il doppio dello spazio.
%	\end{os}
 
 
  Per liberarci dell'informazioni in eccesso ne scartiamo la metà effettuando un downsampling,
  ovvero ponendo
  \[
    \tilde y_0(n) = \downsample{2} y_0(n) \qquad \tilde y_1(n) = \downsample{2} y_1(n)
  \]
\end{frame}
 
%
%\begin{frame} \frametitle{Liberarsi della ridondanza}
%  Il problema dell'informazione in eccesso è stato sicuramente risolto, ma sarà possibile
%  recuperare il segnale originale? \\[15pt]
%
%  Per fortuna la risposta è affermativa. Supponiamo ora di conoscere solamente i segnali
%  $\tilde y_0$ e $\tilde y_1$ ottenuti da questo processo, ovvero
%  \[
%    \tilde{y_0}(n) = H_0(\omega)e^{2in\omega} \qquad \tilde{y_1}(n) = H_1(\omega)e^{2in\omega}
%  \]
%\end{frame}
 
\begin{frame} \frametitle{Il ritorno dell'aliasing}
 
	\begin{problema} Cosa succede ad un segnale $\{e^{in\omega}\}$ se effettuiamo un downsampling
	seguito da un upsampling?
	\end{problema}
  \vskip 15pt
  \uncover<2-> {
  Osserviamo che per ogni $\omega$ vale la seguente uguaglianza
  \[
    \upsample{2}\downsample{2} \{e^{in\omega}\} = \{\frac{1}{2} ( e^{in\omega} + e^{in(\omega+\pi)})\}
  \]
  ovvero l'upsampling ci restituisce il segnale originale ``sporcato'' con dell'aliasing.
  }
 
  \only<3-> {
  \[
    z_0(n) = \upsample{2}\downsample{2} h_0 * x(n) \qquad z_1(n) = \upsample{2}\downsample{2} h_1 * x(n)
  \]
  }
 
\end{frame}
 
\begin{frame} \frametitle{La sintesi}
%   Osserviamo cosa succede ora se consideriamo
  \begin{eqnarray*}
    r(n) &=& f_0 * z_0(n) + f_1 * z_1(n) = \\
    &=& \frac{f_0}{2} * (\tilde{y_0}(n) + e^{in\pi}\tilde{y_0}(n)) + \frac{f_1}{2} * (\tilde{y_1}(n) + e^{in\pi}\tilde{y_1}(n)) = \\
    &=& \frac{f_0}{2} * H_0(\omega)(e^{in\omega} + e^{in(\omega + \pi)}) + \frac{f_1}{2} * H_1(\omega)(e^{in\omega} + e^{in(\omega + \pi)})
  \end{eqnarray*} \vskip 10pt
  e sviluppando in funzione del segnale iniziale $e^{in\omega}$ si ottiene che $r(n)$ si può scrivere come
  (consideriamo $-\omega = \omega + \pi$)
  % Fare un riqadro
  \[
    \frac{(F_0(\omega)H_0(\omega) + F_1(\omega)H_1(\omega))e^{in\omega} + (F_0(-\omega)H_0(\omega) + F_1(-\omega)H_1(\omega))e^{-in\omega}}{2}
    \]
  % e quindi $r(n)$ è combinazione lineare di $\{e^{in\omega}\}$ e di $\{e^{in(\omega + \pi)}\}$.
\end{frame}
 
\begin{frame} \frametitle{La sintesi}
  La condizione per riottenere il segnale originale è $r(n) = x(n)$ che è equivalente a
  \[
    \left\{ \begin{array}{l}
      F_0(\omega)H_0(\omega) + F_1(\omega)H_1(\omega) = 1 \\
      F_0(\omega+\pi)H_0(\omega) + F_1(\omega+\pi)H_1(\omega) = 0
    \end{array}
    \right.
  \]
  In realtà è sufficiente che la prima equazione valga $e^{-il\omega}$ per ogni $\omega$ e per qualche
  $l \in \N$. \\[5pt]
 
  \vskip 10pt
 
  In questo modo avremmo che $r(n) = e^{-il\omega}x(n) = e^{i(n-l)\omega}$, cioè è $x(n)$
  con un ritardo di $l$. \\[5pt]
 
\end{frame}
 
\begin{frame} \frametitle{Il caso di Haar}
  Ricordando i filtri $h_0, h_1, f_0, f_1$ che avevamo scelto all'inizio, calcoliamo le relative
  response function $H_0, H_1, F_0, F_1$.
 
  \vskip 10pt
 
 Ricordando la formula $H(\omega) = \sum_{k=0}^{N} h(k) e^{-ik\omega}$ si ottiene:
 
 \vskip 10pt
  \[
    H_0(\omega) = \frac 1 2 ( 1 + e^{-i\omega} ) \qquad H_1(\omega) = \frac 1 2 (1 - e^{-i\omega})
  \]
  \[
    F_0(\omega) = 1 + e^{-i\omega} \qquad F_1(\omega) = -1 + e^{-i\omega}
  \]
\end{frame}
 
\begin{frame} \frametitle{Il caso di Haar}
  Valutando le equazioni della PR condition si ottiene:
  \[
    \left\{ \begin{array}{l}
      F_0(\omega)H_0(\omega) + F_1(\omega)H_1(\omega) = e^{-i\omega} \\
      F_0(\omega+\pi)H_0(\omega) + F_1(\omega+\pi)H_1(\omega) = 0
    \end{array}
    \right.
  \]
  La Filterbank di Haar ci permette quindi di decomporre e ricomporre esattamente un segnale
  con un ritardo di $1$! \\[10pt]
  \uncover<2> {
  \begin{example}
  Consideriamo il vettore $x = (6,4,5,2)$ ed applichiamoci i filtri $h_0$ e $h_1$:
  \begin{eqnarray*}
		y_0 = h_0 * x = (3,5,4.5.3.5,1)  &  y_1 = h_1 * x = (3,-1,0.5,-1.5,-1) \\
    \tilde{y_0} = \downsample{2}y_0 = (3,4.5,1)  & \tilde{y_1} = \downsample{2}y_1 = (3,0.5,-1) \\
    z_0 = \upsample{2}\tilde{y_0} = (3,0,4.5,0,1,0) &  z_1 = \upsample{2}\tilde{y_1} = (3,0,0.5,0,-1,0) \\
  \end{eqnarray*}
  $$ f_0 * z_0 + f_1 * z_1  = (0,6,5,4,2,0,0) $$
 
  \end{example}
  }
\end{frame}
 
 
 
%
%
%                          %%%%%%%%%%%%%%%%
%                          SEZIONE WAVELETS
%                          %%%%%%%%%%%%%%%%
%
%
%
%
 
\section{Wavelets}
\subsection{Refinement function}
\begin{frame} \frametitle{Refinement equation}
  Cerheremo ora di estendere l'esempio precedente ad un procedimento generale per
  analizzare segnali. \\[15pt]
 
  Introduciamo un'importante equazione detta \emph{Refinement equation}:
  \[
    \Phi(t) = 2 \sum_{k=0}^{N} h(k)\Phi(2t-k)
  \]
  dove $h$ è un lowpass filter di lunghezza $N$ e $\Phi(t)$ una funzione da $\R$ in $\R$.
\end{frame}
 
\begin{frame} \frametitle{Trovare una soluzione}
  Supponiamo di aver fissato il filtro e di voler trovare una soluzione alla \emph{refinement equation}.
 
  \begin{os} Se $\Phi(t)$ è soluzione, allora anche $\lambda \Phi(t)$ lo è. La normalizzazione
  che generalmente si utilizza è
  \[
    \int_{-\infty}^{\infty} \Phi(t) dt = 1
  \]
  \end{os}
 
  Infatti se $\Phi(t)$ è soluzione allora è una funzione a supporto compatto, e quindi l'integrale è finito.
 
\end{frame}
 
\begin{frame} \frametitle{Il caso di Haar}
  \begin{example}
  Consideriamo ancora il filtro $h_0 = (\frac 1 2 , \frac 1 2)$. La refinement equation diventa
  \[
    \Phi(t) = \Phi(2t) + \Phi(2t - 1)
  \]
  e la soluzione è la funzione $\chi_{[0,1]}(t)$.
  \end{example} \vskip 15pt
 
	Possiamo osservare un'altra interessante proprietà. \\[10pt]
 
  Se $h$ e $j$ sono due filtri per cui $\Phi$ e $\Psi$ sono refinement function (ovvero soluzione
  della refinement equation) allora $\Phi * \Psi$ è una refinement function per $h*j$, ovvero per
  la composizione dei filtri.
\end{frame}
 
\begin{frame} \frametitle{Come calcolare effettivamente la soluzione?}
  Per il caso del filtro di Haar abbiamo trovato la soluzione per verifica diretta. \\[10pt]
  Sfruttando l'osservazione precedente possiamo trovare la refinement function per una qualsiasi
  combinazione di filtri di cui la conosciamo singolarmente. Come possiamo risolvere il problema
  in generale? \\[15pt]
 
  \uncover<2> {
 
  Consideriamo il seguente metodo iterativo:
  \[
		\left\{\begin{array}{lcl}
    \Phi_0(t) &=& \chi_{[0,1]}(t) \\
    \Phi_{j+1}(t) &=& 2\sum_{k=0}^{N} h(k) \Phi_{j}(2t - k)
    \end{array} \right.
  \]
 
  Se il metodo converge ad una funzione $\bar\Phi$ questa sarà soluzione
  della refinement equation.  }
 
\end{frame}
 
\begin{frame} \frametitle{Condizioni per la convergenza}
  \begin{problema}
    Trovare condizione necessarie e sufficienti per la convergenza della successione $\Phi_k(t)$.
  \end{problema}
 
  \vskip 10pt
 
	Si può trovare una condizione sugli autovalori della matrice $2(\downsample{2})HH^{t}$, dove
	$H$ è la matrice di dimensione infinita associata al filtro $ h = (h_0 \ldots h_n) $, ovvero
 
	\vskip 10pt
 
  \begin{teo}
    La successione $\Phi_k(t)$ converge $\iff$ tutti gli autovalori di $2(\downsample{2})HH^t$ sono
    di modulo minore di $1$.
  \end{teo}
 
 
%
%	\begin{example}
%	 Se $ h = \frac 1 4 (1, 2, 1)$. Possiamo scrivere un pezzo della matrice $H$ (gli elementi rossi stanno
%	 sulla diagonale):
%	 \[
%	   H = \left[ \begin{array}{ccccc}
%	     & \alert 1 & & &   \\
%	     & 2 & \alert 1 & &   \\
%	     & 1 & 2 & \alert 1 &
%	   \end{array} \right]
%	 \]
%	\end{example}
\end{frame}
 
\begin{frame} \frametitle{Un altro punto di vista}
  Scegliamo una funzione $\Phi(t) \in L^2(\R)$ e i seguenti sottospazi:
 
  \vskip 5pt
 
  \begin{description}
    \item[$V_0$] il sottospazio di $L^2(\R)$ generato degli shift di $\Phi$, ovvero dall'insieme
                 $\{ \Phi(t-k) \: | \: k \in \Z \}$.
    \item[$V_1$] il sottospazio di $L^2(\R)$ generato dagli shift di $\Phi(2t)$.
\only<1> {    \item[$\vdots$] }
    \item[$V_j$] il sottospazio di $L^2(\R)$ generato dagli shift di $\Phi(2^j t)$.
\only<1> {    \item[$\vdots$] }
  \end{description}
  \uncover<2-> {
  \vskip 15pt
  Valgono le seguenti proprietà:
  \vskip 10pt
  \begin{description}
    \item[Invarianza per shift] $f(t) \in V_j \iff f(t - \frac 1 j) \in V_j$;
    \item[Downsampling] $f(t) \in V_j \iff f(2t) \in V_{j+1}$;
    \item[Refinement equation] $V_j \subseteq V_{j+1} \iff \textrm{esistono } a_1 \ldots a_k \: | \: \Phi(t) = \sum_{i=0}^{N} a_i \Phi(2t - i)$;
  \end{description}
  }
\end{frame}
 
\begin{frame} \frametitle{Due possibili scelte:}
 
  \vskip 15pt
 
  \begin{columns}
  \column{0.5\linewidth}
    \textbf{Trovare $\Phi(t)$ partendo dal filtro}
 
    Possiamo assumere di aver fissato il filtro
    $h(0) \ldots h(k)$ e trovare $\Phi(t)$ con
    il metodo iterativo esposto prima.
 
    \[
      \left\{ \begin{array}{lcl}
        \Phi_0(t) &=& \chi_{[0,1]}(t) \\
        \Phi_{j+1}(t) &=& \sum_{k=0}^{N} h_k \Phi(2t - k)
      \end{array} \right.
    \]
 
  \column{0.5\linewidth}
    \textbf{Trovare il filtro partendo da $\Phi(t)$}
 
    Possiamo scegliere $\Phi(t)$ in modo che i
    sottospazi $V_j$ siano uno contenuto nell'altro
    e poi porre i coefficienti del filtro $h(0) \ldots h(k)$ come
    il doppio degli $a_i$ in
    \[
      \Phi(t) = \sum_{i=0}^{N} a_i \Phi(2t-i)
    \]
  \end{columns}
\end{frame}
 
\begin{frame} \frametitle{Valutazione dell'errore}
  Sia $f \in L^2(\R)$. Supponiamo di scrivere un'approssimazione di $f$ come
  \[
    \tilde f = \sum_{i} a_i \Phi(2^j t - i) \in V_j
  \]
  \`E possibile dare una maggiorazione dell'errore in funzione di $j$?
 
  \vskip 10pt
 
  \begin{teo}
    Per ogni $f \in L^2(\R)$ esistono dei coefficienti $\{a_{jk}\}$ tali
    che
    \[
      || f - \sum_{-\infty}^{\infty} a_{jk} \Phi(2^jt - k) || \leq C2^{-jp} ||f^{(p)}(t)||
    \]
  \end{teo}
 
  dove $p$ è la molteplicità dello zero di $H(e^{i\omega})$ per $\omega = \pi$.
\end{frame}
 
\begin{frame} \frametitle{Spazi wavelet}
  Abbiamo costruito una struttura di spazi contenuti uno dentro l'altro
  \[
    V_0 \subseteq V_1 \subseteq \ldots \subseteq V_j \subseteq \ldots
  \]
 
  \vskip 10pt
 
  Ricordiamo che lo scopo della decomposizione wavelet è \textbf{separare i dettagli del segnale dal resto}.
 
  \begin{example}
    Sia $f \in L^2(\R)$ e $f_j$ la sua proiezione ortogonale su $V_j$. Possiamo scrivere:
    \[
      f_j(t) = f_0(t) + \underbrace{(f_1(t) - f_0(t))}_{d_1(t)} + \ldots + \underbrace{(f_j(t) - f_{j-1}(t))}_{d_j(t)}
    \]
    In questo modo abbiamo scritto $f_j$ come una successione di approssimazioni sempre migliori.
  \end{example}
\end{frame}
 
\begin{frame} \frametitle{Spazi wavelet}
 
  Consideriamo per ogni $j$ lo spazio $W_j$ delle funzioni che stanno in $V_j$ ma non in $V_{j-1}$, ovvero
  lo spazio dei dettagli $j$-esimi.
 
  \begin{de}
    Una funzione $w(t)$ si dice \emph{wavelet} se per ogni $j$ si ha che $\{w(2^jt-k) \: | \: k \in \Z \}$ è
    una base per $W_j$.
  \end{de}
 
  \vskip 10pt
 
  \begin{teo}
    $w(t) = \sum_{i=0}^{N} h_1(k) \Phi(2t-k)$ dove $h_1$ è l'highpass filter della filter bank
    è una wavelet.
  \end{teo}
  \vskip 10pt
  Se ad esempio $h_0 = \left(\frac 1 2, \frac 1 2\right)$ e $h_1 = \left(\frac 1 2, - \frac 1 2\right)$ si ha
  che $w(t)$ è ortogonale a $\Phi(t-k)$ per ogni $k$.
\end{frame}
 
\begin{frame} \frametitle{Conclusioni}
  La \textrm{DWT} scompone un segnale in ``details'' e ``averages'' riscrivendolo come
  una somma
  \[
    x(n) = \sum_{j} x_j(n)
  \]
  dove $x_j(t)$ sono dei segnali che contengono alte frequenze se $j$ è grande, e basse frequenze
  se $j$ è piccolo.
 
  \vskip 15pt
 
  Questo permette di rappresentare il segnale $x_0(n)$ con un \textbf{numero minore di sample} rispetto
  al campionamento del segnale originale.
 
  \vskip 10pt
 
  I segnali con $j$ grande avranno alte frequenze (e quindi necessiteranno di un gran numero di sample)
  ma saranno di \textbf{modulo inferiore} ai segnali principali.
\end{frame}
 
\begin{frame} \frametitle{Un esempio pratico}
 
  \vskip 45pt
  Mostriamo la decomposizione wavelet di un pezzo musicale. Dovremmo riconoscere le basse
  frequenze con un'ampiezza maggiore dei dettagli.
  \begin{center}
    \texttt{./dwt.py {-}{-}show file.raw}
  \end{center}
 
  \vskip 30pt
  Il programma (insieme alle slide) è liberamente scaricabile tramite \texttt{git}: \\[10pt]
  \begin{center}
  \scriptsize
  \texttt{git clone http://poisson.phc.unipi.it/\symbol{126}robol/gits/SignalProcessing.git}
  \end{center}
\end{frame}
 
 
\end{document}