Simmetrie e processi visivi



Scaricare 3.72 Mb.
12.11.2018
Dimensione del file3.72 Mb.

Simmetrie e processi visivi
Vito Di Gesù

Università di Palermo, Dipartimento di Matematica ed Applicazioni, Italia


In questo contributo sono introdotti concetti fondamentali di visione artificiale al fine di mettere in evidenza le connessioni che intercorrono fra tale settore della informatica applicata e quelli della matematica che sono utilizzati nella progettazione e l’implementazione degli algoritmi. Particolare rilevanza è data al concetto di simmetria spaziale e al suo ruolo nelle varie fasi che compongono i sistemi di visione artificiale. Sono inoltre brevemente elencate alcune applicazioni della visione artificiale in vari domini di interesse.

Cosa è la visione artificiale?
Il senso della vista ha un ruolo importante in quasi tutte le nostre attività. Al punto che l’informazione visiva, raccolta ed elaborata dal nostro cervello, è fondamentale per la nostra stessa sopravvivenza. Questi concetti sono presenti in quasi tutti i manuali che si occupano di visione, sia essa naturale o artificiale. Per visione artificiale si intende lo studio e la realizzazione di apparati che emulano con un buon grado di efficienza processi umani, in particolare quelli in cui l’informazione visiva è determinante nel prendere una decisione.
Il processo di visione interviene nelle nostre attività a livelli di astrazione diversi; per esempio le azioni di fermare l'automobile se il semaforo indica rosso o selezionare i pomodori maturi si basano su operatori a soglia di tipo SI/NO il cui valore è determinato da un algoritmo di classificazione che riconosce i colori {rosso, verde, giallo} o stabilisce, sulla base di parametri caratterizzanti, lo stato maturo (SI) non maturo (NO). Processi cognitivi più complessi intervengono quando si legge il quotidiano preferito. Infatti l’operazione di lettura utilizza la vista per individuare caratteri, parole e frasi, ma l’elaborazione delle informazioni è molto più articolata; in questo caso processi semantici e sintattici si combinano per arrivare alla comprensione del testo. L’integrazione dell’informazione visiva con modelli cognitivi consente attività intellettuali molto complesse; ad esempio, l’analisi di immagini di risonanza magnetica, unitamente a misure di laboratorio e a modelli di conoscenza medica, è alla base dei sistemi C.A.D. (Computer Aided Diagnosis).
L’avvento della tecnologia digitale e la nascita della cibernetica [1] intorno al 1940, determinarono un interesse crescente verso lo sviluppo di sistemi di visione artificiale; i primi approcci tentarono di emulare i processi di visone naturale, cercando di incorporare in essi anche meccanismi neurobiologici. Il programma cibernetico era molto ambizioso e alla sua realizzazione collaborarono in modo interdisciplinare biologi, fisici, matematici e ingegneri. I risultati non sono stati sempre confortanti, ma il contributo dato al pensiero scientifico da Walter Pitts (un logico), Warren McCulloch (un neurofisiologo), Arturo Rosenblueth (un medico) e fra tutti Nobert Wiener (un matematico) hanno influenzato generazioni di ricercatori.
A dispetto del sogno cibernetico, si è ancora lontani dal realizzare un sistema visivo artificiale capace di emulare il sistema umano in modo accurato; tuttavia, i risultati ottenuti sono notevoli tanto che esistono robot capaci di muoversi ed agire autonomamente in ambienti semplici, ma non necessariamente di laboratorio o ricostruiti. Risultati molto incoraggianti sono invece stati ottenuti nella progettazione e l’implementazione di sistemi di visione artificiale per la soluzione di problemi in contesti ben definiti.
Formalmente le immagini digitali sono delle funzioni, , definite in domini finiti e con valori in detti livelli di grigio. Nel caso in cui R è un reticolo rettangolare esso si chiama retina digitale. Ogni elemento della retina si chiama pixel (voxel) a seconda che il reticolo sia bi- o tri-dimensionale. Nel seguito ci occuperemo di immagini bidimensionali. Queste si possono rappresentare al calcolatore mediante matrici a due indici di dimensioni . In molte applicazioni N=M=1.024, G={0,1,…,255}; quando G={0,1} le immagini sono dette binarie e, per convenzione, i valori f(x,y)=1 rappresentano pixel degli oggetti e f(x,y)=0 pixel dello sfondo.
Nel caso di immagini a colori ad ogni pixel sono assegnati valori che sono mescolanze di tre componenti :

con , , [0,1] e per motivi di normalizzazione. In quest’ultimo caso si parla di immagini a colori RGB e ovviamente il colore è determinato dalla mescolanza delle componenti rosso, verde, blu. La Figura 1 mostra una immagine a colori RGB del Parco e Castello Sforzesco di Milano. È fuori dallo scopo di questo articolo illustrare i meccanismi che consentono di passare da un quadro ad una immagine digitale (il lettore pensi intuitivamente ad una macchina fotografica digitale o ad uno scanner). Ciò che accade comunque è che l’immagine analogica viene trasformata in un mosaico in cui ogni tessera corrisponde ad un pixel. È facile comprendere, quindi, che la qualità dell’immagine è determinata dalla risoluzione (numero di pixel per unità di lunghezza) e dalla accuratezza (numero di livelli di grigio o colore). La determinazione di questi valori si fonda su teoremi di teoria dell’informazione alla quale ha dato fondamentali contributi Claude E. Shannon, ricercatore dei laboratori della Bell [2].

Figura 1. Un esempio di immagine digitale a colori RGB di dimensione 415×294 pixel (immagine di proprietà dell’Autore).


Generalmente ad un sistema di visione artificiale viene richiesto di effettuare la classificazione, la descrizione e l’interpretazione automatica di una scena a partire dalla sua rappresentazione digitale, f(x,y). Questa definizione è vaga in quanto il significato dei termini classificazione, descrizione e interpretazione devono essere meglio precisati di volta in volta e in considerazione del contesto in cui sono utilizzati.
Per esempio nella realizzazione di un sistema automatico capace di stabilire che:
Nella stanza ci sono tre bambini allegri seduti davanti ad un televisore
il processo decisionale si fonda sul riconoscimento delle entità stanza, bambino e televisore e delle relazioni spaziali e di inclusione esistenti fra tali entità. Inoltre, l’attributo allegri deriva da un’interpretazione semantica dell’espressione dei volti dei bambini.
Nel caso di un sistema di analisi automatica di dati astrofisici in grado di stabilire che:
L'immagine del cielo, vista da un telescopio ottico, contiene una galassia a spirale con nucleo; i due bracci della spirale sono orientati di -gradi rispetto alla direzione del piano galattico. La probabilità di tale affermazione è: P(galassia,spirale,nucleo,bracci, )=0.85
i termini riconoscere e classificare hanno un significato diverso da quello del primo esempio, in quanto il fatto percettivo (riconoscimento e descrizione di una galassia) si integra ad altri dati sperimentali e modelli teorici per stabilire nuove conoscenze scientifiche.
La complessità del processo visivo ha suggerito un’architettura dei sistemi di visione artificiale di tipo gerarchico i cui livelli hanno compiti specifici realizzati mediante opportuni operatori (vedi Figura 2).

Figura 2 Schema classico di un sistema di visione artificiale. Gli operatori di basso livello agiscono a livello di pixel o loro intorni; gli operatori di livello intermedio agiscono su caratteristiche globali dell'immagine; gli operatori di alto livello consentono di classificare oggetti e forniscono descrizioni geometriche degli stessi; la fase di interpretazione presuppone una comprensione semantica della scena da cui deriva una decisione.


Il livello Visione preliminare è dedicato all’estrazione e alla selezione delle caratteristiche salienti di un’immagine (come i bordi e le simmetrie locali); in questo livello sono anche individuate le zone di interesse su cui concentrare le operazioni di tipo cognitivo. Questa fase dell’elaborazione, detta in gergo visione di basso livello, ha un’importanza fondamentale a dispetto del nome. Il mal funzionamento degli algoritmi utilizzati può compromettere l’efficienza di tutto il sistema di visione artificiale. Facendo un’analogia con la lettura di un testo, il risultato della sua comprensione non può prescindere dal riconoscimento dei singoli caratteri (caratteristiche) e dalla individuazione delle parole (aree di interesse).
Il livello Visione cognitiva, detta anche visione di alto livello, classifica gli oggetti presenti nell’immagine da elaborare e ne dà una descrizione. L’operazione di classificazione equivale alla determinazione di classi di equivalenza nello spazio degli oggetti. La descrizione riguarda la suddivisione dell’oggetto in parti di cui si forniscono proprietà quantitative (area, perimetro, convessità, elongazione) e relazioni spaziali fra esse intercorrenti: la parte A è alla destra di B. L’interpretazione è strettamente legata ai modelli cognitivi di cui il sistema è stato dotato in relazione allo scopo a cui esso è destinato. La fase di interpretazione è inclusa nei sistemi artificiali più semplici là dove la decisione che ne consegue è facilmente codificabile (ad esempio passa se il semaforo è di colore verde).
Si noti che i livelli mostrati non si sviluppano in modo strettamente sequenziale, anzi spesso interagiscono attraverso meccanismi di contro-reazione per il controllo semantico (feedback). Per esempio un algoritmo utilizzato nella fase preliminare dovrà essere modificato se porta a delle inconsistenze nelle fasi successive.
Inoltre il modello di visione illustrato è debolmente ispirato a quelli della visione naturale; in essa il segnale acquisito dall’occhio, dopo opportune codifiche e trasformazioni, viene inviato alle aree del cervello in cui sono eseguite le elaborazioni che portano al riconoscimento, dal quale conseguono azioni e decisioni. Le analogie fra la visione naturale e quella artificiale si fermano qui; infatti gli operatori implementati nella visione artificiale si fondano su strumenti matematici e proprietà fisiche, che non hanno necessariamente una controparte neuro-fisiologica.
Non deve comunque essere esclusa la possibilità di incorporare soluzioni derivanti dalle scienze cognitive, specialmente quando il fenomeno visivo non può essere adeguatamente descritto da operatori classici di tipo matematico. Per esempio illusioni ottiche, come il triangolo di Kanizsa [3] e la percezione del colore a partire dalle componenti base (rosso, verde e blu), possono richiedere l’applicazione di soluzioni non standard.
Gli algoritmi di elaborazione di immagini utilizzano rappresentazioni sempre più complesse per codificare i dati e tale complessità è in relazione al livello di astrazione del problema da risolvere.
Nei primi livelli della visione si utilizzano operatori “locali” che modificano l’intensità di un pixel, x, sulla base dei livelli di grigio dei pixel appartenenti ad un suo intorno digitale. Tali operatori sono anche detti filtri digitali; esempi di filtri digitali sono la media che assegna ad x il valore medio dei livelli di grigio in un suo intorno, il gradiente che assegna ad x una direzione con la sua intensità; quest’ultima tecnica consente l’estrazione dei bordi di una immagine. Le strutture dati utilizzate per l’implementazione dei filtri digitali sono insiemi o sequenze ordinate (per esempio, vettori e matrici).
Nel caso degli operatori di alto livello i dati di ingresso sono entità strutturate rappresentanti le caratteristiche estratte nelle fasi precedenti o elementi linguistici rappresentati mediante opportuni descrittori e relazioni. Le strutture dati costituiscono entità matematiche come grafi e alberi orientati, liste, memorie associative.
Ulteriori approfondimenti su argomenti riguardanti l’analisi di immagini si trovano in un contributo di Massimo Ferri sul Bollettino UMI Sezione A [4].
L’attenzione visiva
Terminiamo questa introduzione alla visione artificiale con un approfondimento sul concetto di attenzione visiva. Forse non è un’affermazione eccessiva dire che di informazione visiva si potrebbe anche impazzire e forse anche morire se non ci fosse un meccanismo capace di eliminare tutta o parte dell’informazione ridondante; cioè di quella parte di dati che non è utile agli scopi che si intendono raggiungere. Infatti se il nostro sistema visivo (occhio più cervello) dovesse elaborare tutti i bit di informazione che provengono dal mondo esterno non saremmo in grado di rispondere agli stimoli visivi in un tempo utile, in quanto il tempo di elaborazione per prendere una decisione sarebbe troppo grande e il nostro cervello entrerebbe in uno stato confusionale di fronte ad un numero esponenziale di possibili scelte.
Una delle proprietà più straordinarie dei sistemi di visione naturale è la capacità di selezionare in modo estremamente efficiente le aree di interesse su cui focalizzare l’elaborazione visiva, riducendo in modo drastico i bit da elaborare. Questo meccanismo di selezione è detto attenzione visiva e non è ancora stato completamente spiegato; molto probabilmente si basa su criteri di scelta estremamente semplici e utilitaristici, cioè tarati ai nostri scopi.
L’efficienza e l’accuratezza dei sistemi di visione artificiale dipende anche in gran parte dal meccanismo dell’attenzione visiva in essi implementati, per cui un grande interesse è stato rivolto alla progettazione di moduli specializzati alla sua realizzazione. Nel seguito sarà mostrato come gli algoritmi per la ricerca di simmetrie locali siano in grado di individuare le potenziali zone di interesse in una immagine.

Simmetrie ovunque
La simmetria è un elemento percettivo importante; per esempio il volto e il corpo umano sono approssimativamente simmetrici rispetto ad un asse verticale e questo è un elemento che contribuisce al loro riconoscimento o individuazione. Anche gli psicologi della Gelstat hanno assegnato un ruolo importante alla simmetria nei meccanismi di attenzione sia in sistemi visivi che uditivi [5]. Per esempio esperimenti psicofisici mostrano che bambini nei primi due anni di età tendono a fissare lo sguardo su zone in cui lo stimolo presenta una simmetria locale circolare o su zone in cui ci siano intense variazioni di intensità luminosa nell’intorno di un punto (un esempio sono i vertici di un triangolo) [6].
La simmetria è una proprietà fondamentalmente matematica presente eventualmente nelle forme geometriche (vedi Figura 4a) e nelle espressioni algebriche (vedi Figura 3b); si dice che un elemento, , è simmetrico rispetto ad una data operazione, O, se O(x) = x. Nel caso di una funzione di più variabili essa si dice totalmente simmetrica se è invariante per qualunque permutazione, , delle sue variabili (.


(a) (b)

Figura 3. Esempi di simmetrie: (a) una simmetria di tipo geometrico, si noti che il colore dei pixel interviene nella definizione ed è facile verificare che ci sono 4 assi di simmetria; (b) una espressione algebrica simmetrica rispetto alle variabili “a” e “b”.


Due oggetti sono l’uno simmetrico dell’altro, rispetto ad un insieme di operazioni, (), se sono ottenibili l’uno dall’altro mediante l’applicazione di sequenze di tali operatori e viceversa. Per esempio, nel caso di oggetti bidimensionali le simmetrie si basano sulle isometrie euclidee: traslazione, rotazione, e riflessione. Per esempio, nell’esempio in Figura 4 l’oggetto A si può ottenere dall’oggetto B per traslazione seguita da una rotazione di -90° seguita da una riflessione rispetto all’asse orizzontale.

Figura 4. L'immagine A si ottiene da B per trasformazioni di traslazione, rotazione e riflessione. Notare che rotazione e riflessione non commutano tra di loro .


Il concetto di simmetria è utilizzato in fisica per indicare l’invarianza di un sistema a certe trasformazioni. Per esempio, il teorema di Noether stabilisce che ogni legge di conservazione di simmetria implica una legge di conservazione della fisica. La legge di conservazione dell’energia deriva dall’invarianza per traslazioni temporali, la legge di conservazione della quantità di moto dall’invarianza per traslazioni spaziali, la legge di conservazione del momento angolare dall’invarianza per rotazioni [7]. Un altro risultato fondamentale è dovuto al teorema di Wigner che lega le proprietà di simmetria della fisica alle proprietà delle particelle elementari trovate in natura. Esso stabilisce una connessione tra le proprietà delle particelle elementari, la teoria della rappresentazione dei gruppi e delle algebre di Lie e le simmetrie dell’universo [8].
La simmetria è presente anche in organismi biologici là dove sono presenti parti del corpo duplicate per esempio, le ali di una farfalla hanno una simmetria bilaterale, i tentacoli di una stella marina una simmetria radiale. In natura sono molto rari gli esempi di organismi asimmetrici.
La simmetria, come esempio di armonia, è inoltre stata sempre presente in architettura e nelle arti figurative in generale. In Figura 5 è riportato un vaso stile Moarda dell’età del rame III millennio A.C. . I disegni geometrici dei tappeti sono un altro esempio di legame fra simmetria e armonia.

Figura 5. Un esempio di simmetrie presenti in un vaso stile Moarda dell’età del rame III millennio A.C. (Museo Archeologico Regionale “Antonio Salinas” di Palermo)


Parlando di simmetria non si possono omettere i riferimenti alla musica. La simmetria è stato un vincolo utilizzato da molti compositori come la così detta forma ad arco (ABCBA) che è presente nelle composizioni di Steve Reich, Béla Bartók, e James Tenney. Johann Sebastian Bach utilizzava il concetto simmetrico di permutazione ed invarianza in alcune sue composizioni (per esempio, nella Fuga No. 21 in Si bemolle maggiore dal Clavicembalo Ben Temperato Libro II) [9].
Le simmetrie intervengono nella progettazione di molti giochi di pavimentazione del dominio fondamentale. Per esempio è interessante esplorare le pavimentazioni che si possono generare a partire dalle configurazioni in Figura 6 mediante la trasposizione di righe, colonne e quadranti (in figura il piano è diviso in una matrice 4×4). In [10] ci si può divertire a giocare e a saperne di più.

Figura 6. Il puzzle dei 18 diamanti ottenuta da [10].


Tuttavia non sempre la simmetria di un oggetto è un elemento essenziale della sua bellezza. La simmetria può rendere un disegno o un brano musicale noiosi e ripetitivi; piccole asimmetrie del volto umano gli conferiscono caratteri di simpatia ed attrazione; in ogni caso il retroterra culturale come l’educazione a certe musiche e forme può influenzare i nostri gusti estetici. Nel caso delle immagini altri fattori determinanti sono il colore, le proporzioni e la tessitura. Per esempio il Gecko di Escher [11] è invariante a seguito di due rotazioni di 90° o per riflessione orizzontale seguita da riflessione verticale (vedi Figura 7). È interessante notare come molte persone tendano a vedere simmetrie assiali inesistenti nel Gecko di Escher.

Figura 7. Il Gecko di M.C. Escher mostra simmetrie rotazionali e per riflessione.


Sebbene le simmetrie osservate in natura siano un’approssimazione di quelle matematiche l’occhio-cervello umano le percepisce in modo netto. Questa osservazione indica che un sistema di visione artificiale per rilevare simmetrie naturali dovrà essere dotato di meccanismi di ragionamento approssimato. Nelle Figure 8a,b,c sono mostrati il volto di una persona e le versioni matematicamente simmetriche ottenute unendo una metà con la sua simmetrica rispetto all’asse verticale. Si noti come, pur essendo somiglianti all’originale, le due versioni artificiali abbiano un’espressione più statica e innaturale [12].

Figura 8. (a) Il volto di una persona; (b) unione della metà di destra e della sua simmetrica; (c) unione della metà di sinistra e della sua simmetrica.


Il seguito di questo contributo sarà dedicato al modo in cui il concetto di simmetria spaziale e gli algoritmi proposti in letteratura per la sua stima (locale e globale) intervengono nella implementazione delle diverse fasi di un sistema di visione artificiale. In particolare si prenderanno in considerazione le simmetrie radiali e quelle assiali o bilaterali per la loro rilevanza nel campo della percezione.
Simmetria e attenzione visiva
Le prime fasi di elaborazione della visione artificiale sono realizzate da operatori locali definiti o sui singoli pixel dell’immagine, , o su loro intorni digitali, , di raggio . Esempi di operatori locali sono i filtri digitali e morfologici [13] i cui scopi sono la riduzione del rumore strumentale e dei difetti di illuminazione. Altri operatori individuano le zone di interesse, su cui focalizzare le elaborazioni successive; solitamente tali zone si ottengono mettendo in evidenza i bordi (vedere Figura 9b) e le simmetrie locali presenti nell’immagine (vedere Figura 9c).

Figura 9. Estrazione di zone di interesse. (a) immagine di ingresso; (b) estrazione dei bordi mediante l'algoritmo di Canny [14]; (c) estrazione delle simmetrie locali [15].


Un pixel può essere rappresentato con una terna , dove indicano rispettivamente le coordinate intere e l’intensità associata al pixel p. Nella retina discreta gli intorni di un pixel, sono definiti come segue: , dove è un’opportuna metrica definita in R; le due metriche più utilizzate sono:

La Figura 10 mostra gli intorni di raggio r=1 generati dalle metriche sopra definite. Gli algoritmi locali ed in particolare gli algoritmi per la ricerca di simmetrie presenti in una immagine digitale danno risultati che dipendono dalla scelta dell’intorno digitale.


Figura 10. Sulla retina quadrata si possono definire diversi tipi di intorni. A sinistra è dato un intorno di raggio r=1 derivante dalla metrica Manhattan (), a destra un intorno di raggio r=1 derivante dalla metrica Maximum ().


La forma generale degli operatori, K, utilizzati è quasi sempre lineare e il kernel dell’operatore è una matrice quadrata. La convoluzione è un esempio di operatore lineare. La convoluzione può anche essere prodotta dall’interazione del segnale visivo con lo strumento di acquisizione (telescopio, telecamera,...) ed in questo caso il kernel è la funzione di risposta dello strumento rivelatore. Per esempio, i nostri occhi sono le telecamere del nostro cervello e ognuno di noi vede il mondo con occhi diversi. Una persona miope, per esempio, tende a sfocare le immagini. Di contro l’operazione detta deconvoluzione ha lo scopo di correggere l’effetto dovuto alla convoluzione1. In un articolo apparso sul bollettino U.M.I. Sezione A [16] questo problema viene trattato in dettaglio.
Nel seguito sono descritti alcuni operatori in grado di stimare il livello di simmetria da attribuire ad un pixel a partire dalla distribuzione spaziale dei livelli di grigio di un suo intorno di raggio r. La ricerca delle aree di interesse è quindi determinata selezionando le zone di più alta simmetria locale.
Per esempio, la stima della simmetria circolare nell’intorno di un pixel è stata utilizzata da Reisfeld et al. per trovare aree di interesse di una immagine [17]. L’algoritmo di Reisfeld assegna ad ogni pixel un grado di simmetria dato da dove è una funzione che ha il massimo uguale ad 1 quando i livelli di grigio dei pixel q e s sono uguali () e i loro gradienti di intensità sono opposti (vedere Figura 11).

Figura 11. Stima della simmetria circolare locale mediante l’algoritmo proposto in [17].


La Figura 12. mostra come vengono stimati i punti di massima simmetria locale corrispondenti alla bocca, agli occhi, alle orecchie e alla fronte dell’orso.

Figura 12. Un esempio di estrazione di punti di interesse: (a) immagine di ingresso; (b) l’immagine delle simmetrie locali, mediante l’algoritmo descritto in [17]; (c) estrazione dei valori di simmetria al di sopra di una soglia calcolata sulla base della media e della varianza della immagine in (b) (da Reisfeld [17]).


In [15] è stata introdotta la Discrete Symmetry Transform (DST), come esempio di operatore di basso livello per l’estrazione di aree di interesse [18]. Il calcolo della DST si basa sull’applicazione di due operatori lineari all’immagine di ingresso con un evidente miglioramento dell’efficienza computazionale.
Il primo operatore calcola i momenti assiali rispetto al centro, p, dell’intorno discreto circolare di raggio r, , dove i livelli di grigio dei pixel corrispondono alle masse di corpi puntiformi:


dove h=0,1,2,...,n-1 ed n è il numero di assi di simmetria utilizzati. Il risultato sarà un vettore con n elementi.
Il secondo operatore valuta il gradiente dei livelli di grigio nella zona osservata mediante un operatore gradiente definito negli intorni :


dove i pixel q e s sono 4-connessi. È facile vedere che se l’immagine ha valori di grigio costanti. La DST è quindi data da:

Nel caso continuo l’operatore introdotto è invariante per traslazione, rotazione, espansione e contrazione dell’immagine. Nel caso discreto occorre tenere conto degli effetti dovuti alla digitalizzazione dell’immagine, ma tali proprietà sono ancora approssimativamente valide su immagini ad alta risoluzione.


Si noti che la definizione di area di interesse dipende dal problema in esame e una soluzione soddisfacente non può prescindere da informazioni relative alla applicazione specifica. Per esempio nell’analisi di volti occorre determinare la posizione degli occhi utilizzando le simmetrie locali. Le Figure 13a,b,c,d mostrano le varie fasi dell’algoritmo per la loro ricerca. La Figura 13c mostra che i punti di interesse ottenuti selezionando i valori della DST che superano una soglia data è ridondante ed include il lobo destro. L’individuazione dei soli occhi si ottiene in una fase successiva in cui si tiene conto di caratteristiche anatomiche del volto umano (Figura 13d).

Figura 13. Un’applicazione dell’operatore DST: (a) l’immagine di ingresso; (b) la DST dell’immagine di ingresso; (c) la selezione dei punti di interesse; (d) la selezione degli occhi.


L’algoritmo della DST è anche stato incorporato in un sistema di visione artificiale per la ricerca di zone di interesse da parte di un robot in navigazione autonoma in un ambiente non conosciuto [19]. La Figura 14 mostra un esempio di estrazione delle regioni di interesse da parte di un robot dotato di due telecamere e di algoritmi per l’estrazione di punti di massima simmetria locale radiale. Tali sistemi trovano applicazioni interessanti nel caso di sistemi di controllo in ambienti a rischio (vedi centrali nucleari o esplorazioni di fondi marini profondi).


(a) (b)

Figura 14. Un’applicazione dell’operatore DST: (a) l’immagine di ingresso; (b) estrazione delle aree di interesse (immagine di proprietà dell’Autore).



.
Dal locale al globale
Uno dei problemi più interessanti nel campo della percezione visiva riguarda lo studio delle relazioni fra informazioni globali e locali e la possibilità di ricavare proprietà globali dell’immagine a partire da operatori locali [20]. Per esempio, è stato dimostrato che il calcolo del numero di Eulero di un’immagine binaria, che è una proprietà globale, si può eseguire utilizzando operatori morfologici locali [13].
In questo ambito si colloca il lavoro pionieristico di Blum e Nagel [21] dove viene introdotto un metodo per il calcolo asse mediano, proprietà globale di una immagine binaria, mediante la Symmetry Axial Transform (SAT). Dove, il SAT di un oggetto binario è il luogo dei centri di cerchi massimali in esso contenuti. La Figura 15 mostra un esempio di SAT e una delle possibili applicazioni alla segmentazione di un immagine in parti elementari2. L’asse mediano fornisce molte informazioni sulla forma dell’oggetto ed è stato applicato al riconoscimento automatico di caratteri e oggetti binari [22].

Figura 15. La trasformata SAT: (a) l’immagine di ingresso X; (b) la ricerca dei centri di cerchi massimali; (c) la trasformata SAT(X) ottenuta come luogo dei centri di cerchi massimali contenuti nell’immagine di ingresso; (d) una possibile applicazione alla partizione dell’immagine di ingresso in parti significative (segmentazione) .


L’algoritmo SAT è stato l’ispiratore di altri algoritmi per la ricerca di simmetrie locali basati sullo studio di curve algebriche. Tra questi citiamo lo Smoothed Local Symmetry (SLS) [23] che si basa sulle informazioni relative alla curvatura dei bordi dell’immagine. Con riferimento alla Figura 16, l’SLS calcola il luogo dei punti medi, P, dei segmenti per cui è soddisfatta la condizione ; dove e sono le normali alle tangenti alle curve nei punti A e B. Dove s è il vettore spostamento lungo i bordi dell’immagine percorsi in senso orario.

Figura 16. La trasformata SLS.


L’algoritmo si basa sulle seguenti definizioni illustrate in Figura 17:

È interessante notare come le informazioni, derivanti dalla trasformata SLS, consentano di definire strutture geometriche di base caratterizzanti i contorni dell’oggetto (vedere tabella).



Il simbolismo introdotto in tabella ha suggerito la rappresentazione di oggetti mediante stringhe di simboli per il cui riconoscimento si possono utilizzare grammatiche pittoriche3 [24]. Per esempio il vaso in Figura 17 è rappresentato dalla sequenza dell’alfabeto pittorico {b, c, h, p, s, t} ottenuta concatenando in modo direzionale gli elementi pittorici con gli operatori (la direzione della freccia indica il verso della concatenazione).

Figura 17. Codifica di forme mediante parole.


Questi esempi mostrano come, da elaborazioni locali, si possa pervenire alla descrizione e al riconoscimento di oggetti.

Simmetria e trasformazioni geometriche
Il sistema visivo umano riesce a percepire la simmetria di un oggetto anche se deformato mediante trasformazioni geometriche. In Figura 18 sono mostrate varie versioni di un pino stilizzato ottenute mediante trasformazioni affini; la simmetria assiale viene distrutta da un punto di vista matematico, ma è ancora percepita dal nostro sistema visivo. Questa proprietà è legata forse alle capacità di generalizzazione del nostro sistema percettivo e non è facilmente realizzabile nei sistemi di visione artificiale che mostrano comportamenti più rigidi.

Figura 18. La proiezione inversa viene ottenuta supponendo l’esistenza di una trasformazione A funzione di tre parametri: .


In Mukhergee et.all. [25] è stata proposta una base matematica per studiare la simmetria di immagini affini ed è stato sviluppato un algoritmo basato sulla proiezione inversa anche nel caso di non-coplanarità (vedi Figura 19). Gli autori ipotizzano l’esistenza di una trasformazione lineare, A, che mappa pixel omologhi, . La soluzione esatta non è sempre facile da trovare nel caso di immagini molto complesse e rumorose. In [25] sono proposte soluzioni approssimate utilizzando tecniche di ottimizzazione combinatoria.

Figura 19. Un esempio di trasformazioni affini di un oggetto simmetrico con simmetria assiale. Il nostro sistema visivo continua a percepire la simmetria assiale dell’oggetto non trasformato (da Mukherjee et.all. [25]).



Figura 20. Algoritmo di Cipolla per riconoscere simmetrie sbilenche; (b) esempi di estrazione delle simmetrie in condizioni di trasformazioni affini e proiettive e occlusioni parziali (da Cipolla [27])


Questo approccio è stato utilizzato per l’estrazione di simmetrie sotto trasformazioni affini e proiettive [26]. In [27] è stato descritto un algoritmo che considera anche la parziale occlusione fra gli oggetti presenti nell’immagine. Gli autori propongono un metodo di proiezione inversa basato sulla definizione di un integrale del bordo dell’oggetto che sia invariante rispetto a rotazioni, a trasformazioni affini e proiettive. (vedere Figura 20).
Bruckstein e Shaked [28] hanno studiato la simmetria di oggetti binari complessi basandosi su invarianti per trasformazioni affini, (), e proiettive, (), del bordo dell’oggetto. A tal fine il bordo viene campionato in N punti. La definizione delle trasformazioni è data di seguito:



Il metodo proposto è interessante per la sua semplicità e l’efficienza computazionale. Di seguito è dato un esempio della sua applicazione.





Simmetrie e visione di alto livello
Gli algoritmi per la visione cognitiva o di alto livello utilizzano operatori globali applicati per la classificazione e il riconoscimento di oggetti in una scena. Tale obiettivo è ottenuto mediante l’estrazione di caratteristiche globali di forma e la loro integrazione con le informazioni ottenute nella fase di visione preliminare. Esempi di caratteristiche globali sono i contorni chiusi di un oggetto, rappresentati da liste ordinate di pixel. Ad ogni pixel sono associate le sue coordinate ed il vettore gradiente4; quest’ultimo fornisce molte informazioni sulla forma dell’oggetto. Inoltre l’ordinamento dei pixel è utile per la ricerca delle concavità e convessità del contorno, del perimetro e dell’area dell’oggetto nel caso di immagini binarie.
Recentemente sono stati introdotti vari algoritmi per la ricerca di simmetrie globali assiali di oggetti digitali, O. Uno di questi si basa sulla definizione di momento assiale introdotta in meccanica razionale; nel caso delle immagini i livelli di grigio, , giocano il ruolo delle masse. Il calcolo viene effettuato per l’asse, , passante per il centro di massa dell’oggetto e per angoli :

dove è una funzione distanza calcolata tra p e la retta .


In questa trasformazione si passa dalla rappresentazione spaziale dell’oggetto a quella nello spazio dei momenti. Nel caso discreto l’integrale diventa una sommatoria e il numero di direzioni è finito e proporzionale alla risoluzione dell’immagine digitale.
I momenti assiali sono stati utilizzati con successo all’analisi di volti e al riconoscimento di oggetti celesti. Le Figure 21a,b mostrano due esempi di trasformata S applicata al riconoscimento di galassie. È evidente la differenza di rappresentazione; nel caso della galassia con due bracci di spirale, la trasformata S mostra chiaramente due minimi mentre, nel caso della galassia ellittica con nucleo, è evidente solo un massimo relativo.


(a)


(b)

Figura 21. Esempi di trasformate S applicata ad oggetti astronomici: (a) la trasformata S di una galassia a spirale con due bracci; (b) la trasformata S di una galassia ellittica con nucleo.


La trasformata S può essere generalizzata al caso di oggetti tridimensionali ed è detta Simmetria Tomografica, TS. Intuitivamente la TS consiste nel calcolo della S per diverse viste dell’oggetto, , ottenute riprendendo lo stesso con una telecamera da angoli diversi, . Formalmente:

Il termine Simmetria Tomografica deriva dall’analogia con i metodi di ricostruzione della tomografia discreta in cui la rappresentazione dell’oggetto deriva dalla fusione delle informazioni di più prospettive. Per esempio, la tazza in Figura 22a, acquisita da diverse angolazioni, è rappresenta dalla TS in Figura 22b.




(a) (b)

Figura 22. Un esempio di trasformata simmetria: (a) l’oggetto di ingresso (tazzina da caffè); (b) la corrispondente TS.


I valori della TS di un oggetto possono essere quindi utilizzati, come caratteristiche di forma, in algoritmi di classificazione capaci di imparare a riconoscere oggetti a partire da esempi (prototipi). Fra i classificatori artificiali più comuni citiamo le reti neurali [29,30] e le Support Vector Machine [31], una loro descrizione esula da questo contributo; i lettori interessati ad approfondire l’argomento possono consultare i lavori citati in bibliografia.
Anche l’operatore TS, così come la DST, è stato incorporato nel sistema di visione robotica descritto in [19]. L’operatore TS è stato utilizzato per il riconoscimento di oggetti semplici (tazze, portapenne, il cubo di Rubik, boccale di birra). Il robot è di dimensioni ridotte in modo da poter esplorare agevolmente l’ambiente in zone difficilmente raggiungibili dall’uomo. Come detto precedentemente il robot è dotato di due telecamere e si muove in modo autonomo nell’ambiente da sorvegliare. Il robot, estratto il contorno dell’oggetto, ne calcola la TS girando a passi angolari costanti intorno ad esso. Per la classificazione degli oggetti viene eseguita da una rete neurale opportunamente addestrata mediante prototipi stilizzati degli oggetti da riconoscere (parallelogramma, cono, cubo, cilindro, piramide, ellissoide, sfera, tazza). Se l’oggetto non risulta compatibile con nessuno dei prototipi viene dato un segnale di allarme “Oggetto non riconosciuto”.

Quanto è simmetrico un oggetto
Fino ad ora abbiamo descritto come la simmetria possa essere utilizzata per stimare punti di attenzione e classificare oggetti. Alla base degli algoritmi descritti c’è una misura di simmetria dell’oggetto stimata globalmente o nell’intorno di un pixel. Uno dei problemi che ci si può porre è in che modo si possa misurare la simmetria di un oggetto, anche tenuto conto che la simmetria matematica non è quasi mai presente in natura.
A tale scopo in [32] è stato introdotto il concetto di kernel di simmetria assiale di un oggetto, definito come segue:
Dato un oggetto, O, per ogni asse di direzione passante per il baricentro di O, si definisce kernel interno, , il pattern di misura massima incluso in O simmetrico rispetto all’asse di direzione , da cui:



Dove indica la misura del kernel interno in direzione .
In modo analogo
Dato un oggetto, O, per ogni asse di direzione passante per il baricentro di O, si definisce kernel esterno, , il pattern di misura minima che include O simmetrico rispetto all’asse di direzione , da cui:



Dove indica la misura del kernel interno in direzione .

Figura 23. Esempi di kernel: (a) immagine di ingresso, O; (b) o; (c) .


Le Figure 23b,c danno un esempio di e dell’oggetto binario, O, in Figura 24a. L’algoritmo descritto in [32], assegna ai pixel, p e p’, simmetrici rispetto all’asse considerato un valore di grigio che è il minimo tra per il calcolo del kernel interno (esterno); notare che l’algoritmo vale sia per immagini binarie che a livelli di grigio. Si noti che nelle applicazioni all’analisi di immagini le “misure” assegnate a () sono la somma dei pixel che appartengono ai relativi pattern (area digitale). In certe applicazioni conviene utilizzare come misura la somma dei livelli di grigio dei pixel che appartengono ai pattern.
È possibile, a partire dalla definizione di kernel, definire molte misure di simmetria assiale introducendo opportune definizioni di similarità tra l’immagine considerata e i suoi kernel (interno, esterno). Le similarità introdotte in letteratura dipendono sia dalla distribuzione spaziale dei residui tra una immagine e i suoi kernel, che dalla differenza in valore assoluto delle loro misure in ogni pixel; è facile vedere che se l’oggetto è simmetrico coincide con i suoi kernel e quindi la similarità è massima. Le similarità introdotte in [33] sono normalizzate nell’intervallo [0,1], positive e simmetriche.

Osservazioni finali
In questo contributo sono stati discussi i concetti generali che stanno alla base dei sistemi di visione artificiale e sono stati introdotti alcuni algoritmi per l’implementazione di alcune delle sue fasi. Si è cercato di porre l’enfasi sulle relazioni esistenti fra gli algoritmi utilizzati e i concetti matematici da cui essi si fondano. In particolare sono stati illustrati i contributi dati dal concetto di simmetria, di per sé fisico e matematico, alle diverse fasi della visione artificiale. Gli algoritmi che implementano la simmetria in sistemi di elaborazione di immagini traggono spunto su strumenti matematici raffinati che spaziano dalla geometria differenziale alla teoria della misura e la loro implementazione pone problemi di approssimazione numerica molto delicati a causa della natura discreta dello spazio digitale e della precisione che si intende ottenere in molte applicazioni. Si spera che il lettore abbia colto l’importanza dei sistemi di visione artificiale in molti settori quali: la bio-medicina, le scienze fisiche, e la sicurezza. L’approccio adottato è detto pragmatico nel senso che le soluzioni non si ispirano necessariamente a paradigmi naturali, ma alla soluzione efficiente dei problemi, quando affrontati da un calcolatore. Questo non deve fare pensare che la visione naturale non possa dare suggerimenti utili, così come è avvenuto in altri campi (per esempio nell’ingegneria aeronautica). Un’ampia bibliografia è data alla fine di questo contributo per chi volesse approfondire tutti gli argomenti trattati attingendo a lavori e manuali più tecnici.

Bibliografia
[1] N.Wiener, “Cybernetics, or control and communication in the animal and the machine”, Massachusetts Institute of Technology, Cambridge 1965.
[2] C.E. Shannon, “A mathematical theory of communication”, Bell System Technical Journal, vol 27, 1948.
[3] G. Kanizsa, “Margini quasi percettivi in campi con stimolazione omogenea”, Rivista di Psicologia, Vol.49, No.1, pp.7-30, 1955.
[4] M. Ferri, “Visione delle macchine: una sfida anche per i matematici”, Bollettino U.M.I., Matematica nella scienza e nella cultura, Vol.8, 4-A, pp. 85-115, 2001.
[5] W. Khöler and H. Wallach, “Figural after-effects: an investigation of visual processes”, Proc. American Phil. Soc., Vol.88, pp.269-357, 1944.
[6] H. Zabrodsky, “Symmetry - a review”, Technical Report 90-16, CS Dep. The Hebrew University of Jerusalem, 1990.
[7] N. Byers, “E. Noether’s Discovery of the Deep Connection Between Symmetries and Conservation Laws”, Israel Mathematical Conference Proceedings Vol. 12, BarIlan University, Tel Aviv, Israel, December 2-3, 1996.
[8] A. M. Weinberg, ed., “The collected works of Eugene Paul Wigner”, vol. 5, Springer-Verlag, New York (1992).
[9] T. A. Smith, http://jan.ucc.nau.edu/~tas3/wtc/ii21s.pdf, 2005.
[10] A. Vernitski, http://privatewww.essex.ac.uk/~asvern/16/index.htm.
[11] http://fotos.pere.net/escher/.
[12] V.Bruce, “Recognizing faces”, Lawrence Erlbaum Associates, 1988.
[13] J. Serra, “Image analysis and mathematical morphology”, Academic Press, New York, 1982.
[14] J. Canny, “A computational approach to edge detection”, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.8, N.6, pp.679-698, 1986.
[15] V. Di Gesù, C. Valenti, “Symmetry operators in computer vision” Vistas in Astronomy, Elsevier Science, 1996.
[16] M. Bertero, “Matematica ed immagini: alcuni esempi e applicazioni”, Bollettino U.M.I., Matematica nella scienza e nella cultura, Vol.80, 2-A, pp. 47-67, 1999.
[17] D. Reisfeld, H. Wolfson, H.Yeshurun, “Context free attentional operators: the generalized symmetry transform”, Int.Journal of Computer Vision, Special Issue on Qualitative Vision, Vol.14, pp.119-130, 1995.
[18] V. Di Gesù, C. Valenti, L. Strinati, “Local operators to detect regions of interest”, Pattern Recognition Letters, Vol.18, pp.1077-1081, 1997.
[19] A. Chella, V. Di Gesù, I. Infantino, D. Intravaia, C. Valenti, “Cooperating strategy for objects recognition”, in Lecture Notes in Computer Science book “Shape, contour and grouping in computer vision”, Springer Verlag, Vol.1681, pp.264-274, 1999.
[20] M. Minsky and S. Papert, “Perceptrons”, Cambridge, MA, MIT Press, 1969.
[21] H. Blum and R. N. Nagel, “Shape description using weighted symmetric axis features”, Journal of Pattern Recognition, Vol.10, pp.167-180, 1978.
[22] A. Chianese, L.P. Cordella, M. De Santo, A. Marcelli, M. Vento, “A structural method for handprinted character recognition”, Recent Issues in Pattern Analysis and Recognition, pp. 289-302, 1998.
[23] M. Brady, H. Asada, “Smoothed local symmetries and their implementation”, The International Journal of Robotics Research, Vol.3, No.3, pp.36-61, 1984.
[24] A. Rosenfeld, “Picture Languages: Formal Models for Picture Recognition”, Academic Press, New York, 1979.
[25] D.P. Mukherjee, A. Zisserman, M. Brady, “Shape from symmetry: detecting and exploiting symmetry in affine images”, Philosofical Transaction of Royal Society of London Academy, Vol.351, pp.77-101, 1995.
[26] T.J. Chan, R. Cipolla, “Symmetry detection through local skewed symmetries”, Image and Vision Computing, Vol.13, No.5, pp.439-455, 1995.
[27] J. Sato, R. Cipolla, “Affine integral invariants for extracting symmetry axes”, Image and Vision Computing, Vol.15, No.5, pp.627-635, 1997.
[28] A.M. Bruckstein, D. Shaked, “Skew symmetry detection via invariant signatures”, Pattern Recognition, Vol. 31, N.2, pp. 181-192, 1998.
[29] C.M. Bishop, “Neural networks for pattern recognition”, Oxford University Press, 1995.
[30] R.O. Duda, P.E.Hart, D.G. Stork, “Pattern classification” (2nd edition), Wiley, 2001.
[31] V. N. Vapnik, “The Nature of statistical learning theory”, Springer, 1995.
[32] V. Di Gesù, B. Zavidovique, “The S-Kernel: a measure of symmetry of objects”, Pattern Recognition, Vol. 40, N. 3, pp. 839-852, 2006.
[33] V. Di Gesù, B. Zavidovique, “Robust measures of symmetry”, submitted to Image and Vision Computing, 2006.

1 Gli occhiali correggono il difetto di focalizzazione dovuto alla miopia.

2 Il risultato ottenuto dipende anche dal tipo di intorni considerati (, ).

3 Nelle grammatiche pittoriche i simboli dell'alfabeto sono elementi pittorici e le parole sono ottenute mediante regole di composizione spaziale fra elementi pittorici.

4 Nel caso di una immagine digitale il gradiente di un pixel p è un vettore la cui intensità rappresenta la variazione dei livelli di grigio, , in un intorno di raggio r=1 con direzione .


Condividi con i tuoi amici:


©astratto.info 2017
invia messaggio

    Pagina principale