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]

  1. \documentclass[mathserif,professionalfonts,compress,slidestop,10pt]{beamer}
  2.  
  3. \mode<presentation>
  4.  
  5. \usepackage[utf8x]{inputenc}
  6. \usepackage[italian]{babel}
  7. \usepackage{default}
  8. \usepackage{iwona}
  9. \usepackage[T1]{fontenc}
  10. % \usepackage{rotate}
  11.  
  12.  
  13. \usepackage{amsmath}
  14. \usepackage{tikz}
  15. \usepackage{subfigure}
  16.  
  17. % Comandi miei, ovvero piccole cose matematiche che
  18. % ci saranno utili in seguito.
  19. \newcommand{\R}{\mathbb{R}}
  20. \newcommand{\Z}{\mathbb{Z}}
  21. \newcommand{\N}{\mathbb{N}}
  22. \renewcommand{\hat}{\widehat}
  23. \renewcommand{\tilde}{\widetilde}
  24. \newcommand{\upsample}[1]{\makebox[0.85\width]{$\uparrow$}_{#1}}
  25. \newcommand{\downsample}[1]{\makebox[0.85\width]{$\downarrow$}^{#1}}
  26. \newcommand{\pausaindice}{
  27. \begin{frame} \frametitle{Outline}
  28. \tableofcontents[current]
  29. \end{frame}}
  30. % \newcommand{\downsample}[1]{\downarrow{#1}}
  31.  
  32. % Il nostro tema
  33. % \usetheme{CambridgeUS}
  34. \usetheme{Antibes}
  35. \usecolortheme{dolphin}
  36. \beamertemplateshadingbackground{blue!10}{blue!2}
  37. \setbeamercovered{transparent=15}
  38.  
  39. % Chi siamo e cosa facciamo
  40. \author{Leonardo Robol \\ \scriptsize \href{mailto:robol@poisson.phc.unipi.it}{\texttt{robol@poisson.phc.unipi.it}} \normalsize }
  41. \title{Wavelet e signal processing}
  42. \subtitle{Trasformata wavelet discreta tramite filter banks}
  43.  
  44. \begin{document}
  45.  
  46. % Pagina principale
  47. \begin{frame}[plain]
  48. \titlepage
  49. \end{frame}
  50.  
  51. % \begin{frame} \frametitle{Outline}
  52. % \tableofcontents[pausesections]
  53. % \end{frame}
  54.  
  55. %
  56. % Teoremi
  57. %
  58. \theoremstyle{plain} \newtheorem{teo}{Teorema}
  59. \theoremstyle{remark} \newtheorem{de}{Definizione}
  60. \theoremstyle{remark} \newtheorem{os}{Osservazione}
  61. \theoremstyle{remark} \newtheorem{problema}{Problema}
  62.  
  63. %
  64. % Cominciamo a capire cosa ci interessa di un segnale e come lo vogliamo
  65. % guardare.
  66. %
  67. \section{Manipolazione di segnali}
  68. \subsection{Segnali analogici e segnali digitali}
  69. \pausaindice
  70. % FRAME: Cosa sono i segnali
  71. \begin{frame}\frametitle{Segnali}
  72. Un \emph{segnale analogico x} è una funzione $x_{analog}: \R \to \R$.
  73.  
  74. Quasi tutti i sengali ``nascono''
  75. in forma analogica ma vengono \emph{campionati} per essere rappresentati come
  76. \[
  77. \left\{ \begin{array}{ll}
  78. x_{digital}(n): & \Z \to \R \\
  79. x_{digital}(n)= & x_{analog}(nT) \\
  80. \end{array} \right.
  81. \]
  82. dove $T \in \R$ è l'\emph{intervallo di campionamento}.
  83.  
  84. Questo permette di memorizzare un segnale analogico su un supporto digitale (i.e. un computer).
  85. \end{frame}
  86.  
  87. % FRAME: Shannon sampling theorem
  88. \begin{frame} \frametitle{Shannon sampling theorem}
  89.  
  90. Quando un segnale viene campionato molta ``informazione'' viene scartata. Se però il segnale
  91. è \emph{band-limited} allora questo non crea nessun problema, come ci dice il seguente teorema:
  92. \begin{teo}
  93. Ogni segnale analogico le cui frequenze non superano un dato $\omega_{max} \in \R_+$
  94. può essere ricostruito dal suo campionamento $x(nT)$ se $\frac{1}{T} > \frac{\omega_{max}}{\pi}$.
  95. \end{teo}
  96.  
  97. %% Commento allo shannon sampling theorem
  98. \begin{de}
  99. Il valore $\frac{\omega_{max}}{\pi}$ viene chiamato \emph{Nyquist period}.
  100. \end{de}
  101. \end{frame}
  102.  
  103. % FRAME: Aliasing
  104. \begin{frame} \frametitle{Aliasing}
  105.  
  106. % Un po' di spettacolo
  107. \transdissolve[duration=0.2]<2>
  108. \transdissolve[duration=0.2]<3>
  109.  
  110. Cosa succede quando non è soddisfatta l'identità $T^{-1} > \omega_{max} \pi^{-1}$?
  111.  
  112. Osserviamo il seguente esempio:
  113.  
  114. \begin{itemize}
  115. \only<1-> {\item Sia $x(t) = sin(\omega x)$. }
  116. \uncover<2-> { \item Consideriamo il sampling $x(nT)$ con $T = \frac{3\pi}{2\omega}$. }
  117. \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ò
  118. venire ricostruito. }
  119. \end{itemize}
  120.  
  121. \begin{figure}
  122. \begin{tikzpicture}[domain=0:7,samples=150]
  123. \draw[->] (0,0) -- (8,0) node[anchor=west]{$t$};
  124. \draw[->] (0,0) -- (0,1.5) node[anchor=south]{$sin(\omega t)$};
  125.  
  126. % Disegno la funzione
  127. \only<1->{
  128. \draw[color=blue] plot[id=signal] function {sin(5*x)};
  129. }
  130.  
  131. % Disegno i puntini del sampling
  132. \visible<2->{
  133. \foreach \x in {0,1.8849,...,7}
  134. {\fill (\x, 0) circle (0.05cm);}
  135. \foreach \x in {0.94,4.71,...,7}
  136. {\fill (\x, -1) circle (0.05cm);}
  137. \foreach \x in {2.81,6.59,...,7}
  138. {\fill (\x, 1) circle (0.05cm);}
  139. }
  140.  
  141. % Disegno la funzione alias
  142. \visible<3-> {
  143. \draw[color=red] plot[id=aliasedsignal] function {-1 * sin( 1.666667 * x)};
  144. }
  145. \end{tikzpicture}
  146. \caption{Esempio di aliasing}
  147. \end{figure}
  148. \end{frame}
  149.  
  150. % FRAME: Cosa sono i filtri
  151. \subsection{Filtri e FIR}
  152. \begin{frame} \frametitle{Filtri}
  153. Supponiamo di avere il segnale campionato $x(nT)$; d'ora in poi
  154. supporremo $T = 1$ per semplicità.
  155.  
  156. \begin{de}
  157. Un \emph{filtro} è un'applicazione che manda $x(n)$ in un altro segnale $y(n)$.
  158. Diremo che un filtro è
  159. \begin{description}
  160. \item[causale] se $y(n)$ è funzione unicamente di $x(n), x(n-1), \ldots$;
  161. \item[FIR\footnote{che sta per finite impulse response.}] se $y(n)$ si può ottenere con un numero finito di
  162. campioni di $x(n)$ per ogni $n$;
  163. \end{description}
  164. \end{de}
  165.  
  166. I filtri FIR e causali sono interessanti perché possono essere calcolati
  167. in \emph{real--time}.
  168.  
  169. \end{frame}
  170.  
  171. % FRAME: Esempio di filtro
  172. \begin{frame} \frametitle{Esempio di filtro}
  173. Sia $h \in \R^n$ e consideriamo il filtro:
  174. \[
  175. x(n) \longrightarrow y(n) = \sum_{i=1}^{n} h_{i} x(n - i)
  176. \]
  177. Questo è sia FIR che causale. Consideriamo i seguenti segnali:
  178. \[
  179. \left\{ \begin{array}{l}
  180. x_1(n) = ( \ldots , 1 , 1 , 1 , 1 , 1 , \ldots ) \\
  181. x_2(n) = ( \ldots , 1 , -1 , 1 , -1 , 1 , \ldots ) \\
  182. \end{array} \right.
  183. \]
  184. ed i seguenti filtri:
  185. \[
  186. \left\{ \begin{array}{l}
  187. h_0 = ( \frac{1}{2}, \frac{1}{2} ) \\
  188. h_1 = ( \frac{1}{2}, - \frac{1}{2} ) \\
  189. \end{array} \right.
  190. \]
  191.  
  192. Si ottengono i seguenti output:
  193. \[
  194. h_0x_0 = x_0 \qquad h_1x_0 \equiv 0 \qquad h_0x_1 \equiv 0 \qquad h_1x_2 = x_2
  195. \]
  196.  
  197. \end{frame}
  198.  
  199. \begin{frame} \frametitle{Frequency response}
  200. %$h_0$ è un \emph{lowpass filter}, perché elimina le alte frequenze lasciando invariate quelle
  201. %basse, mentre $h_1$ è un \emph{highpass filter} perché mantiene le alte frequenze eliminando
  202. %quelle basse.
  203. %
  204. % Osserviamo che per ogni $\omega$ e per ogni $h$, $h * {e^{in\omega}} = H(\omega)e^{in\omega}$ e quindi
  205. % $e^{inw}$ è un autovettore per il filtro. Il suo autovalore $H(\omega)$ viene detto
  206. % \emph{frequency response} del filtro alla frequenza $\omega$.
  207.  
  208. Sia $x(n) = e^{in\omega}$. Questo è un autovettore per il filtro:
  209. \[
  210. h * \{e^{in\omega}\} = \sum_{i=0}^{N} h_i e^{i(n-i)\omega} =
  211. e^{in\omega} \underbrace{\sum_{i=0}^{N} e^{-i\omega}}_{\textrm{autovalore } H(\omega)}
  212. \]
  213.  
  214. \vskip 10pt
  215.  
  216. \uncover<2-> {
  217. Consideriamo un segnale generico $x(n)$, e la sua trasformata di Fourier $X(\omega)$.
  218.  
  219. La trasformata di Fourier $Y(\omega)$ del segnale $y(n)$ ottenuto dopo l'applicazione del filtro
  220. sarà
  221. \[
  222. Y(\omega) = X(\omega) H(\omega)
  223. \]
  224. }
  225. \end{frame}
  226.  
  227.  
  228. \begin{frame} \frametitle{Lowpass e Highpass}
  229.  
  230. % Nell'esempio precedente abbiamo
  231. \begin{figure}
  232. \subfigure{
  233. \begin{tikzpicture}[domain=0:1.57, samples=150,scale=1.5]
  234. \draw[->] (0,0) -- (1.9,0) node[anchor=west] {$\omega$};
  235. \draw[->] (0,-0.1) -- (0,1.1) node[anchor=south] {$H_0(\omega)$};
  236.  
  237. \draw[color=blue] plot[id=h0resp] function {cos(x)};
  238. \end{tikzpicture}
  239. }
  240. \subfigure {
  241. \begin{tikzpicture}[domain=0:1.57, samples=150,scale=1.5]
  242. \draw[->] (0,0) -- (1.9,0) node[anchor=west] {$\omega$};
  243. \draw[->] (0,-0.1) -- (0,1.1) node[anchor=south] {$H_1(\omega)$};
  244.  
  245. \draw[color=blue] plot[id=h1resp] function {sin(x)};
  246. \end{tikzpicture}
  247. }
  248.  
  249. \caption{Frequency response di $h_0$ ed $h_1$}
  250. \end{figure}
  251.  
  252. \begin{description}
  253. \item[$H_0(\omega)$] Il filtro $h_0$ si dice \emph{lowpass} perché lascia invariati i segnali
  254. a bassa frequenza, mentre elimina quelli ad alta frequenza.
  255.  
  256. \item[$H_1(\omega)$] Analogamente $h_1$ si dice \emph{highpass}.
  257. \end{description}
  258.  
  259. \end{frame}
  260.  
  261. \subsection{Upsampling e downsampling}
  262. \begin{frame} \frametitle{Downsampling}
  263.  
  264. \begin{de}
  265. Diremo che $y(n)$ è il \emph{downsampling} di $x(n)$ e lo indicheremo con
  266. $y(n) = \downsample{k}x(n)$ se
  267. \[
  268. y(n) = x(kn) \quad \textrm{dove } k \in \N
  269. \]
  270. \end{de}
  271.  
  272. \begin{example}
  273. Applichiamo il downsampling ad un numero finito di samples:
  274. Se $x = (1, 5, 3, 2, 6, 4, 8) = x(0) \ldots x(6)$ si ha
  275. \[
  276. \downsample{3}x = (1, 2, 8) \qquad \downsample{2}x = (1,3,6,8)
  277. \]
  278. \end{example}
  279.  
  280. \end{frame}
  281. \begin{frame} \frametitle{Upsampling}
  282.  
  283. Per ``invertire'' il downsampling applicheremo l'\emph{upsampling}:
  284. \begin{de}
  285. Diremo che $x(n)$ è l'upsampling di $y(n)$ di un fattore $k$ e lo
  286. indicheremo con $x(n) = \upsample k y(n)$ se
  287. \[
  288. x(n) = \left\{ \begin{array}{ll}
  289. y(\frac{n}{k}) & \textrm{se } n \textrm{ è multiplo di } k \\
  290. 0 & \textrm{altrimenti}
  291. \end{array} \right.
  292. \]
  293. \end{de}
  294. \begin{os}
  295. Il downsampling è l'inverso dell'upsampling ma non viceversa, ovvero
  296. \[
  297. \downsample{k}\upsample{k} x(n) = x(n) \quad \textrm{ma} \quad \upsample{k}\downsample{k} x(n) \neq x(n)
  298. \]
  299. \end{os}
  300. \end{frame}
  301.  
  302.  
  303.  
  304.  
  305.  
  306. %
  307. %
  308. % %%%%%%%%%%%%%%%%%%
  309. % SEZIONE filter bank
  310. % %%%%%%%%%%%%%%%%%%
  311. %
  312. %
  313. %
  314. %
  315. \section{Filter Bank}
  316. \pausaindice
  317. \subsection{Cos'è una filter bank}
  318. \begin{frame} \frametitle{Struttura di una filter bank}
  319. Possiamo immaginare una \emph{filter bank} come una successione di filtri
  320. che, partendo, da uno o più segnali di input $x(n)$ produca uno o più segnali
  321. di output $y_{0}(n) \ldots y_{1}(n)$. \\[15pt]
  322. Questo esempio prende un input (in giallo) e restituisce tre output (in blu).
  323. \begin{figure}
  324. \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
  325. \tikzstyle{place}=[rectangle,draw=blue!80,fill=white!20]
  326. \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
  327. \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
  328.  
  329. %% Disegnamo i pezzetti
  330. \node [input] (inputsignal) {$x(n)$};
  331. \node [place] (y0) [right of=inputsignal, yshift=25pt] {$y_0(n)$};
  332. \node [output] (y1) [right of=inputsignal, yshift=-25pt] {$y_1(n)$};
  333. \node [output] (y00)[right of=y0, yshift=20pt] {$y_{00}(n)$};
  334. \node [output] (y01)[right of=y0, yshift=-20pt] {$y_{01}(n)$};
  335.  
  336. %% .. e li colleghiamo
  337. \draw[->] (inputsignal.east) -- (y0.west);
  338. \draw[->] (inputsignal.east) -- (y1.west);
  339. \draw[->] (y0.east) -- (y01.west);
  340. \draw[->] (y0.east) -- (y00.west);
  341.  
  342. \end{tikzpicture}
  343. \caption{Esempio di filter bank}
  344. \end{figure}
  345. \end{frame}
  346.  
  347. \begin{frame} \frametitle{Perché una filter bank?}
  348.  
  349. Le filter bank ci permettono di scomporre (e ricomporre un segnale). Questo ci è utile per:
  350.  
  351. \vskip 20pt
  352.  
  353. \begin{description}
  354. \item[Analisi] Vorremmo avere il segnale in una forma che metta in evidenza
  355. la decomposizione in frequenze del segnale e contemporaneamente la localizzazione
  356. temporale degli ``eventi'';
  357.  
  358. \vskip 25pt
  359.  
  360. \item[Compressione] Vorremmo scomporre il segnale in piccole componenti più idonee ad
  361. essere compresse (ovvero che contengano dati omogenei);
  362. \end{description}
  363.  
  364. \end{frame}
  365.  
  366. \subsection{Analysis e Synthesis filter bank}
  367.  
  368. \begin{frame}
  369. \frametitle{}
  370. % Consideriamo i seguenti filtri e filter bank:
  371. % \[
  372. % h_0 = (\frac{1}{2}, \frac{1}{2}) \qquad h_1 = (\frac 1 2 , - \frac{1}{2}) \qquad
  373. % f_0 = (\frac{1}{2}, \frac{1}{2}) \qquad f_1 = (-\frac 1 2 , \frac{1}{2})
  374. % \]
  375.  
  376. \begin{figure}
  377. \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
  378. \tikzstyle{title}=[rectangle,draw=blue!80,fill=white!20]
  379. \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
  380. \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
  381.  
  382. %% Disegnamo i pezzetti
  383. \node [input] (inputsignal) [xshift=10mm] {$x(n)$};
  384. \node [input] (y0) [right of=inputsignal, yshift=10pt, xshift=10mm] {$y_0(n) = h_0 * x(n)$};
  385. \node [input] (y1) [right of=inputsignal, yshift=-10pt, xshift=10mm] {$y_1(n) = h_1 * x(n)$};
  386.  
  387. \node [output] (y0down) [right of=y0, xshift=15mm] {$\tilde{y_0}(n) = \downsample{2}y_0(n)$};
  388. \node [output] (y1down) [right of=y1, xshift=15mm] {$\tilde{y_1}(n) = \downsample{2}y_1(n)$};
  389.  
  390. %% .. e li colleghiamo
  391. \draw[->] (inputsignal.east) -- (y0.west);
  392. \draw[->] (inputsignal.east) -- (y1.west);
  393.  
  394. \draw[->] (y0.east) -- (y0down.west);
  395. \draw[->] (y1.east) -- (y1down.west);
  396.  
  397. \end{tikzpicture}
  398. \caption{Analysis filter bank}
  399. \end{figure}
  400.  
  401.  
  402. \begin{figure}
  403. \begin{tikzpicture}[rounded corners=2pt, scale=0.5, thick, node distance=50pt]
  404. \tikzstyle{title}=[rectangle,draw=blue!80,fill=white!20]
  405. \tikzstyle{input}=[rectangle,draw=blue!80,fill=yellow!50]
  406. \tikzstyle{output}=[rectangle,draw=blue!80,fill=blue!20]
  407.  
  408.  
  409. %% Disegnamo i pezzetti
  410. \node [input] (inputsignal0) [xshift=10mm, yshift=3.5mm] {$\tilde{y_0}(n)$};
  411. \node [input] (inputsignal1) [xshift=10mm, yshift=-3.5mm] {$\tilde{y_1}(n)$};
  412.  
  413. \node[input] (inputsignal0up) [right of=inputsignal0, xshift=5mm] {$z_0(n) = \upsample{2} \tilde{y_0}(n)$};
  414. \node[input] (inputsignal1up) [right of=inputsignal1, xshift=5mm] {$z_1(n) = \upsample{2} \tilde{y_1}(n)$};
  415.  
  416. \node [output] (xn) [right of=inputsignal0up, xshift=25mm, yshift=-3.5mm] {$x(n) = f_0*z_0(n) + f_1*z_1(n)$};
  417.  
  418. %% .. e li colleghiamo
  419. \draw[->] (inputsignal0up.east) -- (xn.west);
  420. \draw[->] (inputsignal1up.east) -- (xn.west);
  421. \draw[->] (inputsignal0.east) -- (inputsignal0up.west);
  422. \draw[->] (inputsignal1.east) -- (inputsignal1up.west);
  423.  
  424.  
  425. \end{tikzpicture}
  426. \caption{Synthesis filter bank}
  427. \end{figure}
  428. \begin{problema}
  429. Trovare condizioni necessarie per ricostruire un segnale decomposto con l'analysis filter bank
  430. tramite la synthesis filter bank.
  431. \end{problema}
  432. \end{frame}
  433.  
  434. \begin{frame} \frametitle{Analysis filter bank}
  435.  
  436. Analizziamo un segnale ad una frequenza fissata $\{e^{in\omega}\}$.
  437.  
  438. \vskip 10pt
  439.  
  440. $\{e^{in\omega}\}$ è un autovalore per
  441. $h_0$ e $h_1$ e quindi dopo il primo passaggio dell'Analysis filter bank si ottiene
  442. \[
  443. y_0(n) = H_0(\omega)e^{in\omega} \qquad y_1(n) = H_1(\omega)e^{in\omega}
  444. \]
  445.  
  446. \vskip 15pt
  447. %
  448. % \begin{os}
  449. % Con questo filtraggio abbiamo separato le alte frequenze dalla basse frequenze; ora però
  450. % ci sono \textbf{il doppio} dei samples di prima e quindi il segnale occupa
  451. % il doppio dello spazio.
  452. % \end{os}
  453.  
  454.  
  455. Per liberarci dell'informazioni in eccesso ne scartiamo la metà effettuando un downsampling,
  456. ovvero ponendo
  457. \[
  458. \tilde y_0(n) = \downsample{2} y_0(n) \qquad \tilde y_1(n) = \downsample{2} y_1(n)
  459. \]
  460. \end{frame}
  461.  
  462. %
  463. %\begin{frame} \frametitle{Liberarsi della ridondanza}
  464. % Il problema dell'informazione in eccesso è stato sicuramente risolto, ma sarà possibile
  465. % recuperare il segnale originale? \\[15pt]
  466. %
  467. % Per fortuna la risposta è affermativa. Supponiamo ora di conoscere solamente i segnali
  468. % $\tilde y_0$ e $\tilde y_1$ ottenuti da questo processo, ovvero
  469. % \[
  470. % \tilde{y_0}(n) = H_0(\omega)e^{2in\omega} \qquad \tilde{y_1}(n) = H_1(\omega)e^{2in\omega}
  471. % \]
  472. %\end{frame}
  473.  
  474. \begin{frame} \frametitle{Il ritorno dell'aliasing}
  475.  
  476. \begin{problema} Cosa succede ad un segnale $\{e^{in\omega}\}$ se effettuiamo un downsampling
  477. seguito da un upsampling?
  478. \end{problema}
  479. \vskip 15pt
  480. \uncover<2-> {
  481. Osserviamo che per ogni $\omega$ vale la seguente uguaglianza
  482. \[
  483. \upsample{2}\downsample{2} \{e^{in\omega}\} = \{\frac{1}{2} ( e^{in\omega} + e^{in(\omega+\pi)})\}
  484. \]
  485. ovvero l'upsampling ci restituisce il segnale originale ``sporcato'' con dell'aliasing.
  486. }
  487.  
  488. \only<3-> {
  489. \[
  490. z_0(n) = \upsample{2}\downsample{2} h_0 * x(n) \qquad z_1(n) = \upsample{2}\downsample{2} h_1 * x(n)
  491. \]
  492. }
  493.  
  494. \end{frame}
  495.  
  496. \begin{frame} \frametitle{La sintesi}
  497. % Osserviamo cosa succede ora se consideriamo
  498. \begin{eqnarray*}
  499. r(n) &=& f_0 * z_0(n) + f_1 * z_1(n) = \\
  500. &=& \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)) = \\
  501. &=& \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)})
  502. \end{eqnarray*} \vskip 10pt
  503. e sviluppando in funzione del segnale iniziale $e^{in\omega}$ si ottiene che $r(n)$ si può scrivere come
  504. (consideriamo $-\omega = \omega + \pi$)
  505. % Fare un riqadro
  506. \[
  507. \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}
  508. \]
  509. % e quindi $r(n)$ è combinazione lineare di $\{e^{in\omega}\}$ e di $\{e^{in(\omega + \pi)}\}$.
  510. \end{frame}
  511.  
  512. \begin{frame} \frametitle{La sintesi}
  513. La condizione per riottenere il segnale originale è $r(n) = x(n)$ che è equivalente a
  514. \[
  515. \left\{ \begin{array}{l}
  516. F_0(\omega)H_0(\omega) + F_1(\omega)H_1(\omega) = 1 \\
  517. F_0(\omega+\pi)H_0(\omega) + F_1(\omega+\pi)H_1(\omega) = 0
  518. \end{array}
  519. \]
  520. In realtà è sufficiente che la prima equazione valga $e^{-il\omega}$ per ogni $\omega$ e per qualche
  521. $l \in \N$. \\[5pt]
  522.  
  523. \vskip 10pt
  524.  
  525. In questo modo avremmo che $r(n) = e^{-il\omega}x(n) = e^{i(n-l)\omega}$, cioè è $x(n)$
  526. con un ritardo di $l$. \\[5pt]
  527.  
  528. \end{frame}
  529.  
  530. \begin{frame} \frametitle{Il caso di Haar}
  531. Ricordando i filtri $h_0, h_1, f_0, f_1$ che avevamo scelto all'inizio, calcoliamo le relative
  532. response function $H_0, H_1, F_0, F_1$.
  533.  
  534. \vskip 10pt
  535.  
  536. Ricordando la formula $H(\omega) = \sum_{k=0}^{N} h(k) e^{-ik\omega}$ si ottiene:
  537.  
  538. \vskip 10pt
  539. \[
  540. H_0(\omega) = \frac 1 2 ( 1 + e^{-i\omega} ) \qquad H_1(\omega) = \frac 1 2 (1 - e^{-i\omega})
  541. \]
  542. \[
  543. F_0(\omega) = 1 + e^{-i\omega} \qquad F_1(\omega) = -1 + e^{-i\omega}
  544. \]
  545. \end{frame}
  546.  
  547. \begin{frame} \frametitle{Il caso di Haar}
  548. Valutando le equazioni della PR condition si ottiene:
  549. \[
  550. \left\{ \begin{array}{l}
  551. F_0(\omega)H_0(\omega) + F_1(\omega)H_1(\omega) = e^{-i\omega} \\
  552. F_0(\omega+\pi)H_0(\omega) + F_1(\omega+\pi)H_1(\omega) = 0
  553. \end{array}
  554. \]
  555. La Filterbank di Haar ci permette quindi di decomporre e ricomporre esattamente un segnale
  556. con un ritardo di $1$! \\[10pt]
  557. \uncover<2> {
  558. \begin{example}
  559. Consideriamo il vettore $x = (6,4,5,2)$ ed applichiamoci i filtri $h_0$ e $h_1$:
  560. \begin{eqnarray*}
  561. y_0 = h_0 * x = (3,5,4.5.3.5,1) & y_1 = h_1 * x = (3,-1,0.5,-1.5,-1) \\
  562. \tilde{y_0} = \downsample{2}y_0 = (3,4.5,1) & \tilde{y_1} = \downsample{2}y_1 = (3,0.5,-1) \\
  563. 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) \\
  564. \end{eqnarray*}
  565. $$ f_0 * z_0 + f_1 * z_1 = (0,6,5,4,2,0,0) $$
  566.  
  567. \end{example}
  568. }
  569. \end{frame}
  570.  
  571.  
  572.  
  573. %
  574. %
  575. % %%%%%%%%%%%%%%%%
  576. % SEZIONE WAVELETS
  577. % %%%%%%%%%%%%%%%%
  578. %
  579. %
  580. %
  581. %
  582.  
  583. \section{Wavelets}
  584. \subsection{Refinement function}
  585. \begin{frame} \frametitle{Refinement equation}
  586. Cerheremo ora di estendere l'esempio precedente ad un procedimento generale per
  587. analizzare segnali. \\[15pt]
  588.  
  589. Introduciamo un'importante equazione detta \emph{Refinement equation}:
  590. \[
  591. \Phi(t) = 2 \sum_{k=0}^{N} h(k)\Phi(2t-k)
  592. \]
  593. dove $h$ è un lowpass filter di lunghezza $N$ e $\Phi(t)$ una funzione da $\R$ in $\R$.
  594. \end{frame}
  595.  
  596. \begin{frame} \frametitle{Trovare una soluzione}
  597. Supponiamo di aver fissato il filtro e di voler trovare una soluzione alla \emph{refinement equation}.
  598.  
  599. \begin{os} Se $\Phi(t)$ è soluzione, allora anche $\lambda \Phi(t)$ lo è. La normalizzazione
  600. che generalmente si utilizza è
  601. \[
  602. \int_{-\infty}^{\infty} \Phi(t) dt = 1
  603. \]
  604. \end{os}
  605.  
  606. Infatti se $\Phi(t)$ è soluzione allora è una funzione a supporto compatto, e quindi l'integrale è finito.
  607.  
  608. \end{frame}
  609.  
  610. \begin{frame} \frametitle{Il caso di Haar}
  611. \begin{example}
  612. Consideriamo ancora il filtro $h_0 = (\frac 1 2 , \frac 1 2)$. La refinement equation diventa
  613. \[
  614. \Phi(t) = \Phi(2t) + \Phi(2t - 1)
  615. \]
  616. e la soluzione è la funzione $\chi_{[0,1]}(t)$.
  617. \end{example} \vskip 15pt
  618.  
  619. Possiamo osservare un'altra interessante proprietà. \\[10pt]
  620.  
  621. Se $h$ e $j$ sono due filtri per cui $\Phi$ e $\Psi$ sono refinement function (ovvero soluzione
  622. della refinement equation) allora $\Phi * \Psi$ è una refinement function per $h*j$, ovvero per
  623. la composizione dei filtri.
  624. \end{frame}
  625.  
  626. \begin{frame} \frametitle{Come calcolare effettivamente la soluzione?}
  627. Per il caso del filtro di Haar abbiamo trovato la soluzione per verifica diretta. \\[10pt]
  628. Sfruttando l'osservazione precedente possiamo trovare la refinement function per una qualsiasi
  629. combinazione di filtri di cui la conosciamo singolarmente. Come possiamo risolvere il problema
  630. in generale? \\[15pt]
  631.  
  632. \uncover<2> {
  633.  
  634. Consideriamo il seguente metodo iterativo:
  635. \[
  636. \left\{\begin{array}{lcl}
  637. \Phi_0(t) &=& \chi_{[0,1]}(t) \\
  638. \Phi_{j+1}(t) &=& 2\sum_{k=0}^{N} h(k) \Phi_{j}(2t - k)
  639. \end{array} \right.
  640. \]
  641.  
  642. Se il metodo converge ad una funzione $\bar\Phi$ questa sarà soluzione
  643. della refinement equation. }
  644.  
  645. \end{frame}
  646.  
  647. \begin{frame} \frametitle{Condizioni per la convergenza}
  648. \begin{problema}
  649. Trovare condizione necessarie e sufficienti per la convergenza della successione $\Phi_k(t)$.
  650. \end{problema}
  651.  
  652. \vskip 10pt
  653.  
  654. Si può trovare una condizione sugli autovalori della matrice $2(\downsample{2})HH^{t}$, dove
  655. $H$ è la matrice di dimensione infinita associata al filtro $ h = (h_0 \ldots h_n) $, ovvero
  656.  
  657. \vskip 10pt
  658.  
  659. \begin{teo}
  660. La successione $\Phi_k(t)$ converge $\iff$ tutti gli autovalori di $2(\downsample{2})HH^t$ sono
  661. di modulo minore di $1$.
  662. \end{teo}
  663.  
  664.  
  665. %
  666. % \begin{example}
  667. % Se $ h = \frac 1 4 (1, 2, 1)$. Possiamo scrivere un pezzo della matrice $H$ (gli elementi rossi stanno
  668. % sulla diagonale):
  669. % \[
  670. % H = \left[ \begin{array}{ccccc}
  671. % & \alert 1 & & & \\
  672. % & 2 & \alert 1 & & \\
  673. % & 1 & 2 & \alert 1 &
  674. % \end{array} \right]
  675. % \]
  676. % \end{example}
  677. \end{frame}
  678.  
  679. \begin{frame} \frametitle{Un altro punto di vista}
  680. Scegliamo una funzione $\Phi(t) \in L^2(\R)$ e i seguenti sottospazi:
  681.  
  682. \vskip 5pt
  683.  
  684. \begin{description}
  685. \item[$V_0$] il sottospazio di $L^2(\R)$ generato degli shift di $\Phi$, ovvero dall'insieme
  686. $\{ \Phi(t-k) \: | \: k \in \Z \}$.
  687. \item[$V_1$] il sottospazio di $L^2(\R)$ generato dagli shift di $\Phi(2t)$.
  688. \only<1> { \item[$\vdots$] }
  689. \item[$V_j$] il sottospazio di $L^2(\R)$ generato dagli shift di $\Phi(2^j t)$.
  690. \only<1> { \item[$\vdots$] }
  691. \end{description}
  692. \uncover<2-> {
  693. \vskip 15pt
  694. Valgono le seguenti proprietà:
  695. \vskip 10pt
  696. \begin{description}
  697. \item[Invarianza per shift] $f(t) \in V_j \iff f(t - \frac 1 j) \in V_j$;
  698. \item[Downsampling] $f(t) \in V_j \iff f(2t) \in V_{j+1}$;
  699. \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)$;
  700. \end{description}
  701. }
  702. \end{frame}
  703.  
  704. \begin{frame} \frametitle{Due possibili scelte:}
  705.  
  706. \vskip 15pt
  707.  
  708. \begin{columns}
  709. \column{0.5\linewidth}
  710. \textbf{Trovare $\Phi(t)$ partendo dal filtro}
  711.  
  712. Possiamo assumere di aver fissato il filtro
  713. $h(0) \ldots h(k)$ e trovare $\Phi(t)$ con
  714. il metodo iterativo esposto prima.
  715.  
  716. \[
  717. \left\{ \begin{array}{lcl}
  718. \Phi_0(t) &=& \chi_{[0,1]}(t) \\
  719. \Phi_{j+1}(t) &=& \sum_{k=0}^{N} h_k \Phi(2t - k)
  720. \end{array} \right.
  721. \]
  722.  
  723. \column{0.5\linewidth}
  724. \textbf{Trovare il filtro partendo da $\Phi(t)$}
  725.  
  726. Possiamo scegliere $\Phi(t)$ in modo che i
  727. sottospazi $V_j$ siano uno contenuto nell'altro
  728. e poi porre i coefficienti del filtro $h(0) \ldots h(k)$ come
  729. il doppio degli $a_i$ in
  730. \[
  731. \Phi(t) = \sum_{i=0}^{N} a_i \Phi(2t-i)
  732. \]
  733. \end{columns}
  734. \end{frame}
  735.  
  736. \begin{frame} \frametitle{Valutazione dell'errore}
  737. Sia $f \in L^2(\R)$. Supponiamo di scrivere un'approssimazione di $f$ come
  738. \[
  739. \tilde f = \sum_{i} a_i \Phi(2^j t - i) \in V_j
  740. \]
  741. \`E possibile dare una maggiorazione dell'errore in funzione di $j$?
  742.  
  743. \vskip 10pt
  744.  
  745. \begin{teo}
  746. Per ogni $f \in L^2(\R)$ esistono dei coefficienti $\{a_{jk}\}$ tali
  747. che
  748. \[
  749. \| f - \sum_{-\infty}^{\infty} a_{jk} \Phi(2^jt - k) \| \leq C2^{-jp} \|f^{(p)}(t)\|
  750. \]
  751. \end{teo}
  752.  
  753. dove $p$ è la molteplicità dello zero di $H(e^{i\omega})$ per $\omega = \pi$.
  754. \end{frame}
  755.  
  756. \begin{frame} \frametitle{Spazi wavelet}
  757. Abbiamo costruito una struttura di spazi contenuti uno dentro l'altro
  758. \[
  759. V_0 \subseteq V_1 \subseteq \ldots \subseteq V_j \subseteq \ldots
  760. \]
  761.  
  762. \vskip 10pt
  763.  
  764. Ricordiamo che lo scopo della decomposizione wavelet è \textbf{separare i dettagli del segnale dal resto}.
  765.  
  766. \begin{example}
  767. Sia $f \in L^2(\R)$ e $f_j$ la sua proiezione ortogonale su $V_j$. Possiamo scrivere:
  768. \[
  769. 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)}
  770. \]
  771. In questo modo abbiamo scritto $f_j$ come una successione di approssimazioni sempre migliori.
  772. \end{example}
  773. \end{frame}
  774.  
  775. \begin{frame} \frametitle{Spazi wavelet}
  776.  
  777. Consideriamo per ogni $j$ lo spazio $W_j$ delle funzioni che stanno in $V_j$ ma non in $V_{j-1}$, ovvero
  778. lo spazio dei dettagli $j$-esimi.
  779.  
  780. \begin{de}
  781. Una funzione $w(t)$ si dice \emph{wavelet} se per ogni $j$ si ha che $\{w(2^jt-k) \: | \: k \in \Z \}$ è
  782. una base per $W_j$.
  783. \end{de}
  784.  
  785. \vskip 10pt
  786.  
  787. \begin{teo}
  788. $w(t) = \sum_{i=0}^{N} h_1(k) \Phi(2t-k)$ dove $h_1$ è l'highpass filter della filter bank
  789. è una wavelet.
  790. \end{teo}
  791. \vskip 10pt
  792. 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
  793. che $w(t)$ è ortogonale a $\Phi(t-k)$ per ogni $k$.
  794. \end{frame}
  795.  
  796. \begin{frame} \frametitle{Conclusioni}
  797. La \textrm{DWT} scompone un segnale in ``details'' e ``averages'' riscrivendolo come
  798. una somma
  799. \[
  800. x(n) = \sum_{j} x_j(n)
  801. \]
  802. dove $x_j(t)$ sono dei segnali che contengono alte frequenze se $j$ è grande, e basse frequenze
  803. se $j$ è piccolo.
  804.  
  805. \vskip 15pt
  806.  
  807. Questo permette di rappresentare il segnale $x_0(n)$ con un \textbf{numero minore di sample} rispetto
  808. al campionamento del segnale originale.
  809.  
  810. \vskip 10pt
  811.  
  812. I segnali con $j$ grande avranno alte frequenze (e quindi necessiteranno di un gran numero di sample)
  813. ma saranno di \textbf{modulo inferiore} ai segnali principali.
  814. \end{frame}
  815.  
  816. \begin{frame} \frametitle{Un esempio pratico}
  817.  
  818. \vskip 45pt
  819. Mostriamo la decomposizione wavelet di un pezzo musicale. Dovremmo riconoscere le basse
  820. frequenze con un'ampiezza maggiore dei dettagli.
  821. \begin{center}
  822. \texttt{./dwt.py {-}{-}show file.raw}
  823. \end{center}
  824.  
  825. \vskip 30pt
  826. Il programma (insieme alle slide) è liberamente scaricabile tramite \texttt{git}: \\[10pt]
  827. \begin{center}
  828. \scriptsize
  829. \texttt{git clone http://poisson.phc.unipi.it/\symbol{126}robol/gits/SignalProcessing.git}
  830. \end{center}
  831. \end{frame}
  832.  
  833.  
  834. \end{document}
  835.