viewgit/index.php:465 Only variables should be passed by reference [2048]
viewgit/index.php:466 Non-static method GeSHi::get_language_name_from_extension() should not be called statically [2048]
\mode<presentation> % \usepackage[T1]{fontenc} % Comandi miei, ovvero piccole cose matematiche che % ci saranno utili in seguito. \begin{frame} \frametitle{Outline} \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 \subtitle{Trasformata wavelet discreta e dintorni} \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} % % Cominciamo a capire cosa ci interessa di un segnale e come lo vogliamo % guardare. % \pausaindice % FRAME: Cosa sono i segnali \begin{frame}\frametitle{Segnali} Quasi tutti i sengali ``nascono'' \[ \left\{ \begin{array}{ll} x_{digital}(n): & \Z \to \R \\ x_{digital}(n)= & x_{analog}(nT) \\ \end{array} \right. \] 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 \begin{teo} Ogni segnale analogico le cui frequenze non superano un dato $\omega_{max} \in \R_+$ \end{teo} %% Commento allo shannon sampling theorem \begin{de} \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} 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} \end{figure} \end{frame} % FRAME: Cosa sono i filtri \begin{frame} \frametitle{Filtri} Supponiamo di avere il segnale campionato $x(nT)$; d'ora in poi supporremo $T = 1$ per semplicità. \begin{de} Diremo che un filtro è \begin{description} campioni di $x(n)$ per ogni $n$; \end{description} \end{de} I filtri FIR e causali sono interessanti perché possono essere calcolati \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} \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 \vskip 10pt 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} } \end{figure} \end{frame} \begin{frame} \frametitle{Lowpass e Highpass} a bassa frequenza, mentre elimina quelli ad alta frequenza. \vskip 25pt 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) \] \vskip 25pt \end{frame} \begin{frame} \frametitle{Downsampling} In seguito ci troveremo molto spesso nella condizione di avere "troppa informazione", ovvero di avere gruppi di segnali che contengono informazioni ridondanti. \\[15pt] Per ovviare a questo trasformeremo i segnali $x(n)$ in degli altri segnali $y(n)$ \begin{de} $y(n) = \downsample{k}x(n)$ se \[ y(n) = x(kn) \quad \textrm{dove } k \in \N \] \end{de} In questo modo scarteremo una parte dell'informazione (a seconda del $k$ scelto, solitamente avremo $k = 2$). \\[5pt] \end{frame} \begin{frame} \frametitle{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 FILTERBANK % %%%%%%%%%%%%%%%%%% % % % % \pausaindice \begin{frame} \frametitle{Struttura di una filterbank} 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} \end{figure} \end{frame} \begin{frame} \frametitle{Perché una filterbank?} Potremmo chiederci: \begin{quote} Qual'è la relazione fra le wavelet e le filterbank? \end{quote} \\[15pt] La risposta breve è che le filterbank (in realtà delle opportune filterbank) sono l'equivalete discreto della trasformata wavelet. \\[15pt] Cominciamo a considerare \end{frame} \begin{frame} \frametitle{Haar filterbank} Consideriamo i seguenti filtri: \[ \] \[ h_0 * x(n) = y_0(n) \qquad h_1 * x(n) = y_1(n) \] e restituisce un segnale $x(n)$ calcolato mediante \[ x(n) = f_0 * y_0(n) + f_1 * y_1(n) \] Prendiamo poi un segnale di esempio. Scegliamo un segnale finito $x(n) = \{e^{i\omega n}\}$. Estenderemo poi questo caso particolare ad un segnale qualsiasi. \end{frame} \begin{frame} \frametitle{Discrete Wavelet Transform} Osserviamo cosa succede al segnale quando viene trasformato tramite la filterbank. Come abbiamo osservato prima otteniamo $\{e^{in\omega}\}$ è un autovalore per questi filtri e quindi otteniamo due segnali \[ y_0(n) = H_0(\omega)e^{in\omega} \qquad y_1(n) = H_1(\omega)e^{in\omega} \] \begin{os} Con questo filtraggio abbiamo separato le alte frequenze dalla basse frequenze; ora però il doppio dello spazio. \end{os} \end{frame} \begin{frame} \frametitle{Liberarsi della ridondanza} 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) \] 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} Cominciamo con il cercare di invertire (per quanto possibile) il downsampling. Poniamo quindi: \[ z_0(n) = \upsample{2} \tilde y_0(n) \qquad z_1(n) = \upsample{2} \tilde y_1(n) \] e osserviamo che per ogni $\omega$ vale questa 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. Come liberarsene? \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) = \\ \end{eqnarray*} e sviluppando in funzione del segnale iniziale $e^{in\omega}$ si ottiene che $r(n)$ si può scrivere come (consideriamo $-\omega = \omega + \pi$) \[ \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} \] \normalsize e quindi $r(n)$ è combinazione lineare di $\{e^{in\omega}\}$ e di $\{e^{in(\omega + \pi)}\}$. \end{frame} \begin{frame} \frametitle{La sintesi} Per recuperare il segnale iniziale farebbe comodo avere $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] In questo modo avremmo che $r(n) = e^{-il\omega}x(n) = e^{i(n-l)\omega}$ è uguale a $x(n)$ con un ritardo di $l$. \\[5pt] Purtroppo questo è inevitabile, perché i filtri ``guardano solamente indietro'', e quindi introducono un ritardo. \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. \end{frame} % % % %%%%%%%%%%%%%%%% % SEZIONE WAVELETS % %%%%%%%%%%%%%%%% % % % % \begin{frame} \frametitle{Refinement equation} Cerheremo ora di estendere l'esempio precedente ad un procedimento generale per analizzare segnali. \\[15pt] \[ \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 è \[ \] \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} \[ \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) \\ \] Se il metodo converge ad una funzione $\bar\Phi$ questa sarà forzatamente soluzione della refinement equation. } \end{frame} \begin{frame} \frametitle{Condizioni di convergenza} \end{frame} \end{document}