Corso di "Matematica per l'analisi e il trattamento di immagini" per il Master in matematica applicata

• Note di lezione
  
• Tutorial: nel notebook di Mathematica (Wolfram Research) Gabor.nb viene presentata l'implementazione numerica degli strumenti per l'analisi-tempo frequenza relativi al Capitolo 3 (Analisi tempo-frequenza: frame di Gabor) delle note e l'applicazione alla compressione di un segnale audio.
  
• Tutorial: viene presentata l'applicazione di frame di armoniche circolari local al 2D pattern matching e al restauro di affreschi, come descritto nel Capitolo 4 (2D pattern matching: armoniche circolari) delle note.
  
• Pagina del Dipartimento di Matematica
  

Introduzione alle note

Queste note si riferiscono alle lezioni di Matematica per l'analisi e il trattamento di immagini per il corso di Master in matematica applicata di circa 20 ore frontali tenutosi presso l'Università degli Studi di Padova nel A.A. 2002-2003. I prerequisiti per una comprensione adeguata delle note sono i corsi di Analisi Matematica del biennio di ingegneria, matematica o fisica, un corso di introduzione alla Analisi Numerica (con particolare riferimento a elementi di algebra lineare computazionale) ed elementi di Analisi funzionale (spazi di Hilbert ed operatori lineari, nozioni di serie e integrali di Fourier). Tuttavia, si è cercato di rendere la lettura consistente ed agevole e rivolta all'utilizzo degli strumenti matematici, limitandosi a volte ad una descrizione puramente intuitiva, sebbene sempre rigorosa ed accompagnata da riferimenti di approfondimento. Per lo svolgimento di alcuni esercizi al calcolatore si presuppone una conoscenza di base dei linguaggi C/C++ o Matlab e verranno presentati dei tutorial come notebook di Mathematica (Wolfram Research), che garantisce la possibiltà di operare in modo sufficientemente intuitivo e di disporre di una semplice interfaccia grafica per la visualizzazione dei risultati. Lo scopo del corso e delle note è quindi di fornire una panoramica degli strumenti di lavoro in questo settore, una introduzione al loro utilizzo e una conoscenza delle loro potenzialità per le applicazioni.

Un'immagine può venir rappresentata come una funzione matematica, che ad ogni punto associa un corrispondente valore di colore, spesso espresso come combinazione di colori fondamentali. Tale rappresentazione consente quindi una interpretazione puramente matematica ed astratta di una immagine. Il dominio di un'immagine, interpretata come funzione matematica, può essere pensato come continuo, ma al fine di poter eseguire una eleborazione numerica occorrerà definire una rappresentazione anche su un dominio discreto. Tali rappresentazioni, continua e discreta, devono essere equivalenti, ossia si deve poter passare dall'una all'altra senza perdita di informazione. Questo garantisce che l'elaborazione che eseguiamo numericamente corrisponda alla fine ad un trattamento dell'immagine anche come funzione definita nel continuo. Un processo di digitalizzazione di un segnale $f$ è quindi l'associazione di $f$ ad una successione di dati $\stackrel{\rightarrow}{c} = (c_n(f))_{n \in \mathbb{N}}$, rappresentanti $f$. Tali dati $\stackrel{\rightarrow}{c}$ potranno essere trattati numericamente, inviati attraverso un mezzo o trasmessi mediante comunicazioni senza cavo. Tutte queste operazioni richiedono tuttavia due condizioni/principi:

(I)

la rappresentazione digitale deve essere stabile: questo significa che piccole perturbazioni sui dati sono legate a piccole perturbazioni della funzione originaria. Questa è una naturale richiesta di continuità;

(II)

robustezza al rumore e tolleranza dell'errore: possibili errori importanti sui dati non dovrebbero modificare troppo la rappresentazione di una funzione $f$. Infatti la trasmissione attraverso un mezzo, ma anche semplici operazioni numeriche possono produrre errori e la loro propagazione.

Uno degli esempi più semplici che si possono cosiderare come processo di digitalizzazione è quello di associare a una funzione continua $f$ la sequenza dei suoi campioni su un reticolo discreto o insieme di nodi $c_n(f) = f(\tau n)$, dove $\tau>0$ è il passo di campionamento. Se si assume che $f$ appartenga ad uno spazio normato di funzioni, si chiami esso $(B,\Vert\cdot\Vert _B)$, e che la sequenza dei dati appartenga ad uno spazio normato di successioni $(Y,\Vert\cdot\Vert _Y)$, una relazione di equivalenza e di continuità è data dalla equivalenza delle norme:

$$\Vert (c_n(f))_{n \in \mathbb{N}} \Vert _Y \asymp \Vert f\Vert _B,$$ (1.1)

ove per ``$\asymp$'' si intende che esistono due costanti $A, B>0$, indipendenti da $f$, tali che

$$A \Vert (c_n(f))_{n \in \mathbb{N}}\Vert _Y \leq \Vert f\Vert _B \leq B \Vert (c_n(f))_{n \in \mathbb{N}}\Vert _Y .$$

Assumiamo che la funzione $f$ venga affetta da un errore

$$\tilde f = f + \delta f.$$

Allora da (1) si ha che

$$\Vert \tilde f \Vert _B \asymp \Vert (c_n(f)+ c_n(\delta f))_{n \in \mathbb{N}} \Vert _Y,$$

e $\Vert (c_n(\delta f))_{n \in \mathbb{N}} \Vert _Y \leq A^{-1} \Vert \tilde f -f \Vert _B$. Quindi con tale equivalenza di norme si assicura la validità del principio/condizione (I).

Per esempio se $f \in L^p(\mathbb{R}^d)$ è una funzione^1.1 a banda limitata, cioè per cui la sua trasformata di Fourier ha supporto compatto^1.2, allora esiste $\tau_0 >0$ piccolo a sufficienza tale che per ogni $0< \tau \leq \tau_0$

$$\Vert (f(\tau n))_{n \in \mathbb{Z}}\Vert _{l^p} \asymp \Vert f\Vert _{L^p},$$

Questa equivalenza di rappresentazione continua e discreta/numerica/digitale si realizza in particolare per la possibilità di riprodurre $f$ dall'insieme dei suoi campioni. Infatti per un opportuna successione di funzioni a banda limitata $f_n \in L^1(\mathbb{R}^d)$, $n \in \mathbb{Z}$, si può scrivere:

$$f = \sum_n f( \tau n) f_n.$$

Così il processo di analisi o digitalizzazione (mappa dei coefficienti)

$$\matrix{f &\stackrel{C}{\rightarrow} &(c_n(f))_{n \in \mathbb{N}}}$$

può essere invertito sulla sua immagine da un processo di sintesi o riproduzione (mappa di recupero)

$$\matrix{(c_n(f))_{n \in \mathbb{N}} &\stackrel{R}{\rightarrow}& f}.$$

L'equivalenza di norme espressa in (1) è equivalente alla continuità (o alla limitatezza) degli operatori lineari di analisi e sintesi rispettivamente.

Quindi, data una immagine e una funzione $f$ che la rappresenti, si può considerare la decomposizione astratta in pacchetti di informazione numerici e discreti:

$$\matrix{ & &f& & & \cr &\swarrow&\downarrow&\searrow& \cr...&c_{k-1}(f)&c_k(f)&c_{k+1}(f)&... }$$

magari indipendenti o correlati tra loro. Ma una decomposizione allo scopo di essere ``utile'' e fedele (ossia che garantisca che le operazioni numeriche equivalgano a operazioni sulla rappresentazione continua) deve essere associata ad una riproduzione/sintesi:

$$\matrix{ ...&c_{k-1}(f)&c_k(f)&c_{k+1}(f)&...\cr\cr &\searrow&\downarrow&\swarrow& \cr& &f& & & }$$

È inoltre piuttosto intuitivo che se i pacchetti di informazione sono totalmente indipendenti allora possibili errori sono individualmente interpretati da ciascun elemento $c_n(f)$ di informazione con possibili errori importanti locali/globali nella consequente sintesi/ricostruzione. D'altra parte, possibili correlazioni tra i pacchetti di informazione possono distribuire gli errori su tutto l'insieme dei dati, magari riducendo cattive distorsioni locali, magari compensando completamente un errore prodotto ad un certo punto, recuperandolo in un punto successivo. Questo si realizza e può essere intepretato come una intrinseca ridondanza della rappresentazione numerica/digitale: la ridondanza di informazione è piuttosto comune in natura ed è fortemente raccomandabile ogni volta che errori si possono presentare e il grado di ridondanza dovrebbe quindi dipendere dalla frequenza di tali possibili errori. Basti giusto pensare al DNA umano: è un lungo flusso di informazioni ove solo una minima parte è considerata effettivamente ``utile''. Il resto è protezione e parte in qualche senso ridondante. Alcune modificazioni possono essere compensate, e, magari, i loro effetti negativi essere controllati o ridotti. Questo corrisponde al principio/condizione (II) e alla seguente formulazione matematica:

per una medesima operazione di sintesi/ricostruzione $R: Y \rightarrow B$ definita da un insieme di funzioni $(f_n)_{n \in \mathbb{N}}$ esistono molteplici operazioni di analisi/decomposizione $C: B \rightarrow Y$ tali che $I_B = R \circ C$.

Questo equivale a dire che possono esistere $(c_n(f))_{n \in \mathbb{N}}$ e $(d_n(f))_{n \in \mathbb{N}}$ distinti tali che

$$f = \sum_{n \in \mathbb{N}} c_n(f) f_n = \sum_{n \in \mathbb{N}} d_n(f) f_n$$

Quindi un processo di digitalizzazione ridondante può offrire diverse possibili realizzazioni e si può quindi adattare la scelta di una realizzazione, in dipendenza del particolare uso che se ne vuol fare. A prima vista, la ridondanza può considerarsi in contrasto con il concetto di compressione. Come si vedrà in seguito, in realtà un sistema ridondante di pattern (pacchetti di informazione) può aumentare la possibilità di identificazione: è vero che due differenti pattern possono condividere parte del medesimo contenuto di informazione, ma uno può corrispondere meglio alla data funzione: ``più grande è il dizionario, tante più frasi si è in grado di costruire''.

Il corso e le note descrivono quindi i fondamenti matematici per la costruzione di sistemi di digitalizzazione fedeli (completi), stabili (I) e in alcuni casi ridondanti (II). Verranno mostrate infine applicazioni per la rappresentazione di immagini, la compressione e l'identificazione di immagini a meno di trasformazioni affini (rotazioni, dilatazioni e traslazioni). Le note sono accompagnate da esercizi che si consiglia vivamente di svolgere per una miglior comprensione e per sviluppare una capacità d'uso degli strumenti. Alcuni esercizi suggeriti sono di carattere pratico, essenzialmente implementazioni al computer. Il corso si limita ad una analisi dei segnali in spazi di Hilbert (essenzialmente $L^2$, $l^2$) ed è diviso in quattro lezioni.

1.

Dopo una breve introduzione sugli spazi di Hilbert, descriveremo il concetto di sviluppo in serie di Fourier, trasformata di Fourier e sua implementazione discreta. L'algoritmo FFT (Fast Fourier Transform).

2.

Formula della somma di Poisson. Teoria del campionamento per funzioni a banda-limitata e conversioni digitale-analogico. Stime degli errori di aliasing per funzioni non a banda-limitata. Deduzione di un primo esempio di sistema tempo-frequenza (frame di Gabor) e tempo-scala (ondine-wavelets). Accenni al campionamento irregolare.

3.

Frame in spazi di Hilbert. Analisi tempo-frequenza e frame di Gabor, continue e discrete e implementazione dei duali. Applicazioni ai segnali audio e alla compressione di immagini. Accenni sulle ondine.

4.

Generalizzazione delle frame di Gabor su geometria circolare: le armoniche circolari discrete. Rappresentazione di immagini secondo frame di armoniche circolari, proprietà rispetto all'azione di rotazioni. Metodi ed algoritmi di calcolo per l'indentificazione di immagini. Discussione del caso applicativo della ricostruzione assistita dal computer di affreschi minutamente frammentati.