Con l'espressione analisi di immagini si intende l'insieme di procedimenti (algoritmi) atti alla scoperta, identificazione e comprensione dei pattern che sono rilevanti per il raggiungimento di un determinato risultato funzione delle immagini stesse.
Ad esempio, in un sistema di lettura automatica di documenti dattiloscritti, i pattern di interesse sono i caratteri alfanumerici, e l'obiettivo e' quello di raggiungere un'elevata percentuale di riconoscimento dei caratteri stessi.
I pattern, dal punto di vista della macchina, sono
descrizioni quantitative e/o strutturali di un oggetto o di
una qualche entita' di interesse presente in un'immagine;
in generale un pattern sara' formato da uno o piu' descrittori
('features').
Una
Il riconoscimento automatico di pattern (pattern recognition) implica l'utilizzo di tecniche per assegnare i pattern stessi alle rispettive classi.
La risoluzione di tale problema implica diverse fasi:
In questo lavoro si tratta del riconoscimento di caratteri (cifre da 0 a 9) tratti da lettere manoscritte, spedite da Pechino e da Macao nei primi anni del 1700, da Gesuiti che stavano sul posto, e riguardanti alcune controversie in merito ai riti cinesi. Si tratta di documenti cifrati che sono stati recentemente scoperti negli archivi del Vaticano e decrittati [1] e di cui si propone un campione nell'immagine sottostante.
Si sono sperimentati come features i cosiddetti descrittori di Fourier, riconducibili alla trasformata discreta di Fourier DFT (Discrete Fourier Transform) applicata ai contorni dei caratteri.
Se si segue nel continuo il contorno di una curva chiusa, la sua forma puo' essere descritta da coordinate parametriche del tipo x(t),y(t). Le forme d'onda risultanti x(t),y(t) sono periodiche con periodo 2¶. Queste forme d'onda possono venire campionate e combinate in modo da produrre nel discreto una forma d'onda complessa periodica di periodo N:
Un segnale del genere puo' essere rappresentato dai coefficienti della sua trasformata discreta di Fourier Z(k), chiamati anche descrittori di Fourier:
La rappresentazione di Fourier ha diverse proprieta' interessanti:
Il coefficiente Z(0) rappresenta il centro di gravita' della curva. I coefficienti di Fourier Z(k) rappresentano le variazioni di forma lente e veloci rispettivamente per piccoli e grandi indici k.
Una traslazione di coordinate pari a 
:
dove
cambia solo il termine Z(0) della rappresentazione:
Una rotazione della curva di un angolo 
:
da' come risultato uno sfasamento dei coefficienti della trasformata di uguale ampiezza:
Un'operazione di 'scaling' per un fattore a rispetto ad un sistema di coordinate con origine nel centro di gravita' della curva, da' come risultato un uguale 'scaling' dei coefficienti di Fourier:
Un cambiamento del punto di partenza dell'operazione di 'contour following' della curva:
produce una modulazione dei descrittori di Fourier:
Pertanto ne consegue che i descrittori di Fourier godono di interessanti e utili proprieta' di invarianza nella descrizione dei contorni.
Il modulo dei coefficienti |Z(k)|, per k=0,...,N-1 e' invariante alla rotazione; il modulo degli N-1 coefficienti |Z(k)|, per k=1,...,N-1, risulta invariante anche alla traslazione.
Infine la fase arg(Z(k)), per k=0,...,N-1 e' invariante alla scala.
Pertanto se ne deduce che i descrittori di Fourier hanno proprieta' interessanti di invarianza che si possono utilmente impiegare in applicazioni di 'object recognition'.
A tal fine l'espressione:
puo' venire usata come misura di errore del confronto di due curve z1(n) e z2(n). Tale errore e' piccolo (in teoria zero, ma in pratica no considerati gli errori dovuti al campionamento ed alla discretizzazione) se z2(n) e' una versione ruotata della curva z1(n).
Se N viene scelto come potenza di 2, i descrittori di Fourier possono venire calcolati in modo efficiente tramite la Fast Fourier Transform in radice 2. Se N non e' potenza di 2, altri algoritmi FFT possono venire usati (es. algoritmo ai fattori primi).
Le proprieta' di invarianza sopra menzionate sono valide per curve z(n) campionate in modo uniforme; altrimenti vi sono conseguenze soprattutto a carico della fase: solo il modulo continua a possedere informazione attendibile.
I descrittori di Fourier possono venire usati per rigenerare il contorno originario utilizzando la trasformata inversa. Tuttavia, considerando gli inevitabili errori di troncamento (quantizzazione), la IDFT puo' non generare rappresentazioni esatte del contorno originario e puo' accadere di avere come risultato curve anche non piu' chiuse. Dopo la necessaria applicazione a ciascun oggetto connesso presente nell'immagine di un algoritmo di contour following per l'individuazione dei contorni, per la descrizione e la memorizzazione di questi ultimi, si sono usati i cosiddetti "chain codes" o catene di Freeman di cui nell'applet che segue si possono avere alcuni esempi:
Una volta ottenuta la descrizione dei contorni, a questi ultimi si e' applicata la DFT onde ricavarne i descrittori di Fourier. Nell'applet che segue si puo' visualizzare, scegliendo un carattere, il grafico relativo del modulo della DFT del contorno.
Uno dei vantaggi principali dell'applicazione dell'analisi di Fourier al contorno dei caratteri e' la significativa compressione dei dati che si ottiene. Si nota infatti che solamente 5 coefficienti hanno valori significativi, mentre gli altri sono di fatto trascurabili. Si puo' avere un'ulteriore conferma di questo fatto, ricostruendo i caratteri usando solamente i primi M coefficienti nelle espressioni della trasformata inversa:
Nell'applet che segue si provi a scegliere carattere e numero dei coefficienti di Fourier da usare nella ricostruzione, tramite IDFT, del contorno originario:
Appare chiaro che gia' con un numero limitato di coefficienti si riesce a ricostruire le caratteristiche salienti dei contorni. La capacita' di compressione dei dati appare ancora piu' evidente se si considera che il contorno originario dei caratteri usati nelle prove supera i 100 punti (corrispondenti ciascuno ad una coppia di coordinate x,y), mentre vengono usati nella ricostruzione solamente (4M + 2) parametri (con M tipicamente compreso tra 4 e 6) costituiti dalle M coppie di parti reali ed immaginarie di a(n) e b(n) (con n compreso tra 1 ed M) piu' a(0) e b(0).
Si e' quindi usato un cosiddetto classificatore a distanza minima "minimum distance classifier" detto anche metodo dei prototipi applicando la formula:
vista piu' sopra.
I risultati, pur necessitando di ulteriori prove e verifiche, appaiono incoraggianti, consentendo una percentuale di riconoscimento superiore all' 80%.