Studio e realizzazione di un modulo software per la creazione assisita di modelli 3D di bassorilievi

FACOLTÀ DI SCIENZE MATEMATICHE,FISICHE E NATURALI

CORSO DI LAUREA SPECIALISTICA IN TECNOLOGIE INFORMATICHE

TESI DI LAUREA

Studio e realizzazione di un modulo

software per la creazione assistita di

modelli 3D di bassorilievi

RELATORI

Chiar.mo Prof. Marcello Carrozzino

CANDIDATO

Cristian Lorenzini Chiar.mo Prof. Franco Tecchia

1 “Tu osservi un bassorilievo dei pesci, illustre opera di Fidia. Sommergili nell’acqua: nuoteranno.” Marco Valerio Marziale, Augusta Bilbilis, 40 d.C. – 104 d.C.

2

Indice

Indice ... 2

1. Introduzione ... 4

1.1 Scopo della tesi ... 4

1.2 Il Bassorilievo ... 7

2. Stato dell’arte... 9

2.1 Realtà Virtuale... 9

2.2 Applicazioni software per i beni culturali ... 11

2.3 Modellazione tridimensionale ... 15

2.4 Riconoscimento facciale attraverso ricostruzione: potenzialità e limiti ... 17

2.5 Shape from shading ... 23

3. Metodologia... 33

3.1 Analisi degli studi ... 33

3.2 Funzionalità dell’editor ... 34

3.2.1 Creazione delle height map usando la luminanza ... 34

3.2.2 Costruzione delle normal map ... 36

3.2.3 Costruzione della height map a partire dalla normal map. Teoria sui cerchi osculatori ... 43

3.2.4 Utilizzo della Shapelet di Bézier ... 51

3.2.5 Modifica manuale delle altezze... 59

4. Architettura dell’editor ... 62

3

4.1.1 OpenGL e GLSL Shading language ... 62

4.1.2 L’ambiente di sviluppo dell’editor (Visual Studio .Net) ... 66

4.1.3 Visualizzazione delle anteprime (la tecnologia XVR) ... 69

4.1.4 Esportazione dei dati. I formati OFF e AAM ... 75

4.2 Descrizione della struttura dell’editor ... 78

4.2.1 L’ambiente di lavoro ... 79

4.2.2 Il tool di gestione della forma della Bézier ... 83

4.2.3 Il wrapper XVR e la sua configurazione ... 84

4.2.4 La barra dei menu ... 87

4.3 Pipeline di elaborazione per ogni modifica ... 89

4.4 Descrizione del programma XVR ... 94

4.5 Formato dei messaggi editor-componente XVR... 95

4.5.1 Messaggi dall’editor al componente XVR ... 96

4.5.2 Messaggi dal componente XVR all’editor ... 98

4.5.3 Analisi del protocollo ... 99

4.6 Implementazione dello shader GLSL ... 103

4.7 Il visualizzatore del bassorilievo ... 105

5. Risultati, considerazioni qualitative e sviluppi futuri ... 106

5.1 Strumenti per misurare le prestazioni ... 106

5.2 Tempi di elaborazione ... 108

5.3 Confronti ... 113

5.4 Bassorilievi ottenuti ... 115

5.5 Sviluppi futuri ... 118

Bibliografia e Paper Reference ... 122

Indice delle Figure ... 126

4

Capitolo 1

Introduzione

1.1 Scopo della tesi

Al giorno d’oggi i modelli tridimensionali e le applicazioni di realità virtuale sono di grande utilizzo nel campo della conservazione, della comunicazione e della fruizione dei beni culturali, anche per categorie di utenti particolari come i non vedenti.

Il progetto di tesi in esame si propone di studiare la possibilità di modificare “artisticamente” un ritratto, in modo da ricavarne un modello tridimensionale a forma di bassorilievo. Per modello deve intendersi un insieme di vertici, spigoli e superfici che rappresentano un poliedro in uno spazio tridimensionale, detto anche mesh poligonale. Quando si parla di una modifica artistica, si intende un processo di modellazione della mesh per cui non sono necessarie particolari competenze tecniche. L’attenzione particolare ai ritratti ha portato, in un primo momento, ad uno studio dei sistemi di riconoscimento facciale tramite ricostruzione in un modello tridimensionale, e successivamente ad uno sviluppo di un sistema interattivo per eseguire uno Shape from Shading1 _{della mesh. Lo} studio preventivo delle tecniche esistenti, l’introduzione del concetto di Shapelet2, lo sviluppo di una nuova funzionalità per la gestione dei

1 _{Tecnica di modifica delle forme tridimensionali, vedi capitolo 2.5 per maggiori dettagli.} 2 _{Strumento per la modifica di forme tridimensionali, vedi capitolo 2.5 per maggiori dettagli.}

5 possibili bordi presenti in un’immagine e l’utilizzo di varie tecniche per la determinazione della variazione altezze della superficie del bassorilievo sono la struttura portante della ricerca e dell’innovazione del progetto. Esso si può inquadrare nella branca informatica della Computer Vision, una tecnologia che, utilizzando tecniche matematiche, si occupa di interpretare una scena grafica. Tra queste tecniche, ad oggi, ne esistono per la ricostruzione di modelli tridimensionali di ambienti che impiegano centinaia di foto sovrapposte, per la tracciabilità del movimento di persone su sfondi complessi, per l’individuazione dei nomi delle persone presenti in una foto usando il riconoscimento dei volti, del vestiario e del colore dei capelli in modo combinato e per altro ancora. Nonostante gli sviluppi intrapresi la Computer Vision ha ancora forti limitazioni e non è in grado di interpretare un’immagine alla stessa maniera di un uomo, dato che le tecniche menzionate costituiscono un problema complesso formato da diversi sottoproblemi: decidere quali informazioni presenti in una scena sono utili, riconoscerle, renderle elaborabili ed elaborarle. Soprattutto le prime due fasi non costituiscono un’operazione immediata data la vastità di dettagli presenti nelle immagini. Tra queste procedure, ad esempio, potrebbe annoverarsi il conteggio di tutti gli animali presenti in una foto: risulta assai difficoltosa la scelta delle informazioni utili per individuare il tipo “animale”.

Nella branca della Computer Vision che si occupa dell’interpretazione tridimensionale di una scena relativa a un’immagine vengono utilizzati modelli fisici e modelli di Computer Graphics. Questi ultimi indicano

6 come un oggetto è posizionato e si muove nello spazio, come la luce riflette su di esso, quanto è il suo grado di opacità, ecc... Sebbene la Computer Graphics non sia ancora perfetta, in un dominio limitato (come una scena di science-fiction) può creare un perfetto senso di realismo. Nella Computer Vision si sta provando a fare l’inverso, ossia descrivere una situazione già rappresentata in una o più immagini e ricostruire tutte le sue proprietà tra cui forme presenti, illuminazione e distribuzione di colore [1].

Algoritmi di Computer Vision sono oggi utilizzati in vari campi, tra i quali l’Optical character recognition (OCR), la ricostruzione di immagini mediche, il Motion capture, i sistemi di sorveglianza, la modellazione 3D, il Face Detection e Recognition e molto altro ancora. Ad oggi esistono già numerosi software per la creazione di modelli 3D (compresi bassorilievi) a partire da immagini. L’obiettivo principale del progetto è la creazione di un sistema di facile utilizzo che non richieda capacità di modellazione avanzata e che funzioni in modalità semiautomatica e assistita. Lo scopo non è creare un bassorilievo di un’immagine ad hoc (per il quale sarebbe più indicato commissionare il lavoro ad un unico artista) o crearne un numero limitato (che potrebbero essere realizzati utilizzando i vari plug-in messi a disposizione da software come 3d Studio Max o Blender), ma creare un sistema adatto alla creazione di bassorilievi utilizzando strumenti automatici o semiautomatici al fine di ottenere una produzione numericamente soddisfacente in tempi limitati. Questi bassorilievi saranno meno dettagliati di quelli realizzati tramite una modellazione con i software

7 canonici, ma potranno funzionare da un’ottima base di partenza per essere semplicemente migliorati.

Il progetto svolto rientra nel software in dotazione del laboratorio in cui è stato sviluppato, accentuando quindi lo sfruttamento delle tecnologie proprietarie e in dotazione.

1.2 Il Bassorilievo

Per bassorilievo si intende quella tecnica di scultura per cui si intagliano su di una superficie (sia essa legno, pietra o marmo) delle particolari forme o scene. Il termine sta ad indicare che “le figure emergono dallo sfondo con poco distacco”3 e si differenzia dall’altorilievo in base a quanto le figure emergono dallo sfondo in proporzione all’altezza della lastra originaria. Questa tecnica di scultura fu largamente impiegata nell’antichità e nel Medioevo, mentre nel periodo classico venne abbandonata a favore dell’altorilievo e del tutto tondo.

Tralasciando gli aspetti storico-artistici, in informatica per bassorilievo si intende una struttura in uno spazio tridimensionale che si discosta da una mesh piana. È quindi possibile affermare che, in Computer Graphics, lavorare su un bassorilievo software è come lavorare in due dimensioni e mezzo, dove la mezza dimensione è data dalla profondità che si sviluppa solo in una direzione, ovvero verso il punto di vista, come accade nel bassorilievo scultoreo. A differenza del tutto tondo, il bassorilievo software consente a chi lo costruisce di non creare lo sfondo nascosto dietro il soggetto.

3 _{Dizionario Italiano Garzanti, 2011}

8 Un utilizzo tipico del bassorilievo software, in Computer Graphics, è legato alla realizzazione delle mappe di dislivello delle aree geografiche, fornendo una simulazione migliore delle alture o delle valli rispetto all’astrazione dei colori tipico delle cartine fisiche. La conversione delle mappa di dislivello software in mappe solide, utili per l’istruzione, è immediata, data la mappatura perfetta delle coordinate rispetto al piano utilizzato. Analogamente, ogni forma tridimensionale è facilmente riconducibile e trasformabile in una forma materiale solida, dal momento in cui tutte le coordinate nello spazio sono note.

Una mappa di dislivello, e quindi il bassorilievo in generale, oltre ad essere maggiormente espressiva rispetto alla normale cartina fisica, è interpretabile da categorie di utenti a cui queste ultime sono precluse, come i non vedenti, analogamente al bassorilievo scultoreo.

Attualmente esistono infatti ricostruzioni di quadri o, più specificatamente, ritratti in bassorilievo realizzati al fine di rendere fruibile a questa categoria di persone particolari opere: un lavoro in questo senso è il rilievo tattile dell’immagine della Nostra Signora di Guadalupe, realizzata nell’ambito del progetto “Integrazione delle disabilità attraverso la Cultura” curato dalla Direzione Regionale dell’Emilia-Romagna del Ministero per i Beni e le attività Culturali nel 20094.

9

Capitolo 2

Stato dell’arte

2.1 Realtà Virtuale

La Realtà Virtuale è una disciplina informatica che sviluppa ambienti in grado di fornire esperienze di immersione e immedesimazione agli utenti che ne fanno uso. Gli ambienti non esistono realmente ma sono costruiti su piattaforme informatiche e una loro visita da parte degli operatori fornisce a questi ultimi stimoli talmente verosimili da dare l’impressione di esserne parte. Affinché l’ambiente virtuale abbia successo, esso deve rispettare le leggi fisiche dell’ambiente reale o simularle in modo estremamente accurato. Negli ultimi anni sono state sviluppate varie tecnologie che possono essere sfruttate per aumentare l’immersione dell’utente (presenza), senza produrre eccessivi ritardi nell’elaborazione dei dati, come:

• la rappresentazione grafica in tempo reale; • i display stereoscopici;

• il motion capture;

• il ritorno di forza e di sensazioni tattili e molto altro ancora.

In particolare, l’elaborazione grafica tridimensionale può consentire la creazione dell’ambiente virtuale e strumenti come la visione stereoscopica possono far sì che gli utenti si sentano immersi

10 nell’ambiente. I fattori che caratterizzano la presenza in ambienti virtuali sono tre:

1. _{la quantità di informazioni dirette verso gli utenti, per cui la} quantità di dettaglio offerto è direttamente proporzionale all’immersione dell’operatore;

2. _{la possibilità di modificare i sensori umani nell’ambiente, ossia la} possibilità di direzionare i sensori verso le fonti di input come direzionare la testa verso la sorgente di un suono per percepirlo in modo migliore;

3. _{la possibilità di modificare l’ambiente, ovvero la possibilità di} spostare gli oggetti contenuti nell’ambiente o alterarne l’aspetto in conformità con l’aspettativa dell’utente secondo le leggi fisiche del mondo reale, come ad esempio la possibilità di accartocciare un foglio di carta e lanciarlo lontano.

Per risolvere questi tre fattori è necessario mettere a punto sistemi di fisica per il controllo ambientale.

Il laboratorio PERCRO5 della Scuola Sant’Anna di Pisa opera nella branca

della Realtà Virtuale su tre diversi ambiti:

• lo sviluppo di sistemi di interfaccia e per il ritorno di forza e tattile;

• lo sviluppo di rendering grafico ad alta definizione in tempo reale; • lo studio delle problematiche relative alla modellazione.

5 _{Il PERCeption RObotics è un laboratorio di ricerca che ha come missione lo sviluppo di nuovi}

11 Tra questi aspetti, quello che risulta il primo in ordine di importanza per la creazione di un ambiente virtuale è senza dubbio il sistema grafico tridimensionale, in altre parole la Computer Graphics tridimensionale.

2.2 Applicazioni software per i beni culturali

In questo paragrafo trattiamo alcuni approcci in merito all’insieme di tecnologie che provengono dallo sviluppo dell’informatica che trattano i beni culturali secondo l’accezione che gli anglosassoni chiamerebbero Cultural Heritage, ossia l’insieme degli artefatti, delle tradizioni e dei costumi che costituiscono il patrimonio culturale tramandato da chi ha preceduto le attuali generazioni. In generale, per artefatto “culturale” si intende un oggetto di interesse che ha una storia che viene da lontano nel tempo e che possiede un qualche valore essendo correlata alla società odierna. Sul valore dell’oggetto deve esistere una forma di consenso non necessariamente universale [2].

Per meglio caratterizzare le applicazioni informatiche per i beni culturali possiamo classificarle secondo la loro destinazione d’uso piuttosto che le tecnologie utilizzate, senza alcuna pretesa di scientificità. I principali software per i beni culturali possono essere distinti, quindi, per:

• la gestione del patrimonio culturale;

• lo studio e la ricerca inerenti ai beni culturali;

• la diagnostica dello stato di conservazione dei beni culturali; • il restauro dei beni culturali;

12 • la catalogazione e la divulgazione del patrimonio culturale, per favorirne la conoscenza e quindi il turismo a esso legato, la formazione degli studenti nell’ambito dei beni culturali e il miglioramento e la semplificazione della fruizione dei beni culturali.

In merito alla gestione del patrimonio culturale, si tratta sostanzialmente di sistemi di basi di dati col fine di tenere traccia dei beni esistenti anche per i fini di assistenza allo studio e alla ricerca, alla loro tutela e alla possibilità di assegnare un valore al patrimonio culturale.

Per quanto riguarda lo studio e la ricerca si possono annoverare sia le già citate tecnologie per la catalogazione, ma anche sistemi cartografici per studiare la dislocazione geografica sul territorio e applicazioni che consentono di analizzare gli oggetti in questione. Fanno parte di questo ambito anche le tecniche di ricostruzione virtuale di edifici o ambienti non più esistenti o gravemente danneggiati per poter discutere ipotesi scientifiche su di essi; queste applicazioni sono di interesse anche per la comunicazione e la divulgazione.

Per quanto riguarda le tecniche di diagnosi, esse sono state sviluppate per consentire l’ottenimento di informazioni sullo stato dei beni senza danneggiarli in alcun modo. Queste tecniche, a seconda del bene in studio, possono basarsi sui raggi-X, sui raggi laser o sulle onde sonore, e vengono spesso usate per determinare se un oggetto necessita o meno di un restauro.

Si possono distinguere restauri per preservare la situazione corrente dei beni, per ripristinare la loro condizione ottimale o per ricostruire la

13 condizione originale. Ad oggi, la disputa tra chi sostiene che il restauro dovrebbe avere il compito di ricostruire le parti danneggiate o non più esistenti oppure di conservare i beni nello stato in cui si trovano ma nelle migliori condizioni possibili è ancora in corso (sebbene in Italia i secondi siano di gran lunga più numerosi dei primi). Di questo ambito si occupano applicazione utili a simulare la qualità estetica di un restauro prima di compierlo o la ricostruzione virtuale dell’aspetto originale da abbinare ad un restauro solamente conservativo del bene.

La tutela del patrimonio è importante data la vastità e la dispersione dello stesso sul territorio: applicazioni che consentono la mappa del rischio contro calamità (terremoti, incendi, alluvioni…) o database per la gestione del patrimonio accessibili anche dalle forze dell’ordine sono lo stato dell’arte di questo ambito.

La comunicazione applicata ai beni culturali è un aspetto estremamente importante e probabilmente non molto compreso. Come si è anticipato, il bene culturale è un oggetto che, avendo una storia e un legame col passato, può suscitare emozioni o scatenare curiosità. Per rendere importante, quindi, un bene culturale agli occhi della grande massa del pubblico è importante comunicarne gli aspetti salienti valorizzandone l’importanza. Sono varie le tecnologie che offrono possibilità di comunicazione, come le applicazioni multimediali e interattive, i siti web, le applicazioni per palmari e apparecchi mobili per la realtà aumentata, le ricostruzioni virtuali e molte altre ancora. Tra queste possono essere comprese anche le applicazioni per la formazione e la fruizione, per tutte le categorie di persone, come i non vedenti.

14 Il laboratorio PERCRO ha al suo interno l’ACE Group6, che lavora con le

metodologie di storytelling digitale e interattivo e dei serious games per l’apprendimento, utilizzando tecnologie per la Realtà Virtuale.

In questi ambiti possono essere riconosciute tutte le tecniche atte alla ricostruzione virtuale, alla preservazione, alla comunicazione, alla fruizione e all’apprendimento per quanto riguarda il Cultural Heritage. Tra le applicazioni sviluppate si possono citare musei virtuali (l’Artistic Craftsmanship in Lucchesia – 2009, il Virtual Museum of Noh Masks – 2009, ...), web tridimensionale (Web3D per Cultural Heritage – 2010, ...), software per l’educazione (San Pietro a Grado – 2010, ...) e ricostruzioni tridimensionali (Museo Fattori – 2000, Lucca Romana in 3D – 2009, ...).

Tra i progetti sui beni culturali realizzati dal PERCRO ve ne è uno

riguardante l’accessibilità del patrimonio culturale per i non vedenti; si tratta del Museo delle Pure Forme – 2004, un sistema di ambienti virtuali che unisce l’esplorazione visiva dei modelli tridimensionali di sculture alla possibilità di ricevere anche stimoli tattili dalle stesse attraverso speciali dispositivi robotici denominati interfacce aptiche.

Il lavoro sviluppato in questa tesi può essere considerato nella categoria delle applicazioni per la ricostruzione tridimensionale atte alla comunicazione e alla fruizione dei beni culturali, ponendo l’attenzione a un diverso modo di interpretare il ritratto, anche per i non vedenti.

Per riuscire a ottenere un risultato di questo tipo è necessario quindi creare la forma in uno spazio tridimensionale, ossia un modello, per il

15 soggetto raffigurato, i cui dati devono essere estrapolati analogamente alle tecniche di Computer Vision. La tecnica di creazione, definizione e modifica di una forma nello spazio è definita modellazione tridimensionale.

2.3 Modellazione tridimensionale

La modellazione tridimensionale è un insieme di procedure utili per la definizione di una qualsiasi forma in uno spazio a tre dimensioni. Essa costituisce generalmente il primo passaggio nella creazione di istanze in grafica tridimensionale, sia che si voglia creare un modello foto-realistico di un animale, sia che si voglia realizzare un particolare componente di una catena di montaggio. Si può distinguere la modellazione in organica, quando viene utilizzata per oggetti con superfici morbide e arrotondate, generalmente ricche di particolari, e in geometrica, quando viene impiegata per oggetti di tipo tecnico o meccanico, dotati di spigoli.

Esistono vari paradigmi di modellazione, tra cui la modellazione per superfici, che consiste nella creazione di una rete di curve che racchiude varie superfici parametriche, chiamata patch di Bézier. Queste superfici, se particolarmente complesse, sono dotate di un elevato numero di punti di controllo, come vedremo in seguito nella trattazione matematica delle curve di Bézier. Un altro tipo di modellazione è quella poligonale, basilare nella grafica tridimensionale, che opera su superfici organizzate in maglie di facce poligonali e che permette l’elaborazione della superficie gestendo tre elementi fondamentali: le facce, i lati e i vertici

16

Figura 1: Modellazione poligonale

(Figura 1). Per vertice si intende una posizione nello spazio dotata di altre informazioni, quali il colore, il vettore della normale e le coordinate di texture. Un lato è una

connessione tra due vertici, mentre una faccia è un insieme chiuso di più lati, di solito tre. Per variare il modello è sufficiente spostare uno di questi elementi. Il modello, composto da una griglia non strutturata di vertici, lati e facce, è chiamato mesh poligonale. Esistono varie forme di

rappresentazione delle mesh poligonali, per cui basta salvare l’informazione relativa alla posizione di uno degli insiemi di elementi per conservare l’informazione in modo corretto.

La divisione della mesh in più poligoni è anche chiamata tassellazione. Si può distinguere in tassellazione uniforme e non uniforme (o adattiva), che si differenziano nella frequenza dei poligoni in base alla zona in cui sono presenti. Una zona con maggiore dettagli, ad esempio potrebbe essere formata da poligoni più piccoli e più frequenti, mentre una zona con poco dettaglio, come la superficie di un piano, potrebbe essere formata da pochi poligoni.

17

2.4 Riconoscimento facciale attraverso ricostruzione

tridimensionale: potenzialità e limiti

Il progetto sviluppato si occupa della ricostruzione in due dimensioni e mezzo di volti raffigurati in ritratti; trattando di facce, un insieme di strumenti che hanno caratteristiche di localizzazione e successiva ricostruzione facciale possono essere i software che si occupano di riconoscimento facciale. Il Face Recognition è una branca della Computer Vision composta da due diversi step: in primo luogo vengono localizzate tutte le facce presenti nell’immagine, successivamente può essere ricostruita la faccia o le facce interessanti su di un modello tridimensionale. Il riconoscimento facciale si può quindi dividere in un primo step di Face Detection e in un secondo di Face Reconstruction. Il primo step può essere risolto con varie metodologie:

• Usare l’algoritmo della pelle per localizzare tutte le aree nell’immagine con un colore approssimativamente uguale al colore della pelle stessa [3]. Questo sistema da luogo a diversi problemi nell’impostazione di un intervallo di colori della pelle per ridurre i falsi positivi, dal momento che ogni immagine si trova in un contesto diverso, con differenti condizioni di saturazione e di illuminazione. Oltre a questo è necessario un intervento manuale per deselezionare le “aree di pelle” diverse dalle facce, come le mani, le spalle o le gambe. Sarebbero inoltre da prevedere eventuali colori diversi della pelle, cosa che potrebbe portare ad altri falsi positivi, a discapito degli ulteriori riconoscimenti ottenuti.

18 • Usare l’algoritmo di Viola e Jones [4], che suddivide l’immagine in regioni, a loro volta costruite in forma matriciale a basso costo computazionale. L’algoritmo localizza le aree che hanno particolari caratteristiche facciali e le analizza a cascata in modo sempre più particolareggiato. Questo algoritmo risolve il problema delle differenze di illuminazione delle immagini e gestisce con discreto successo le facce che mantengono una struttura regolare (sebbene questa caratteristica possa pregiudicare, con falsi positivi o negativi, i casi di facce non regolari).

• Eseguire una selezione manuale dell’area che comprende la faccia. Attualmente alcuni software gratuiti e commerciali usano semplici algoritmi di riconoscimento facciale per creare corrispondenze tra più immagini. Google Picasa e Facebook costituiscono alcuni degli esempi più noti. Dopo una preventiva etichettatura di alcune foto, infatti, utilizzando l’algoritmo della pelle, sono in grado di creare corrispondenze con altre foto che presentano modelli simili, riconoscendo di fatto le facce presenti. In ogni caso, questi software non utilizzano informazioni sulle caratteristiche facciali contenute nelle immagini, ma soltanto analogie tra le immagini stesse.

Gli esempi citati non eseguono nessuno step di Face Reconstruction. La ricostruzione facciale su modelli tridimensionali a partire da immagini bidimensionali può essere utilizzata per l’effettivo riconoscimento (software per la sicurezza), per costruire animazioni facciali per video conferenze o altri task analoghi. Ovviamente, il metodo intuitivo per creare questi modelli è scansionare le persone usando scanner

19 tridimensionali, estremamente costosi e non sempre impiegabili. Vari sistemi propongono algoritmi che utilizzano una o due immagini di facce per ricostruire i modelli.

Ricordando che lo scopo della tesi è ricostruire un modello a due dimensioni e mezzo di un ritratto, si può supporre che si abbia un’unica immagine facciale (il ritratto) ragionevolmente in posizione frontale, e per questo è necessario escludere a priori tutti i sistemi di ricostruzione facciale con più di un’immagine in input.

La prima parte del nostro progetto è stata interessata dall’analisi dei molti metodi di ricostruzione facciale illustrati in vari paper, tanto che abbiamo provveduto ad una classificazione delle ricostruzioni studiate, utilizzando tre criteri: l’utilizzo di algoritmi automatici, semi-automatici o totalmente manuali; il tipo di input di cui necessitano e il tipo di output prodotto. Per verificare le performance di somiglianza tra i modelli iniziali e quelli prodotti dalle ricostruzioni abbiamo considerato il Principal Component Analysis (PCA) e il Linear Discriminate Analysis (LDA), i cui dati erano comunque forniti dai paper stessi.

Il PCA è una procedura matematica che utilizza una trasformazione ortogonale per convertire un insieme di osservazioni a possibili variabili correlate in un insieme di variabili non correlate, chiamate componenti principali, che solitamente sono in numero inferiore o al massimo uguale al numero delle variabili iniziali. Le componenti principali possono essere facilmente confrontate tra i modelli. Il LDA produce invece una combinazione lineare di caratteristiche che descrivono diverse classi di oggetti, nel nostro caso immagini. La risultante della combinazione può

20 essere quindi utilizzata per ottenere una classificazione lineare che descrive il modello iniziale. Mentre LDA attinge esplicitamente al modello per ottenere le differenze tra le classi di oggetti, PCA non ne tiene conto, e l’analisi fattoriale costruisce la funzione di combinazione in base alle differenze piuttosto che alle somiglianze tra i modelli in fase di confronto.

Le performance temporali considerate, invece, sono state verificate e confrontate solo in relazione ai paper che li hanno resi disponibili.

Hu, Jiang e altri hanno realizzato un metodo di ricostruzione tridimensionale automatico [5]. L’algoritmo localizza automaticamente dei punti caratteristici nell’immagine e la applica ad un generico modello ottenuto dal USF Human ID 3D database per una ricostruzione personalizzata della faccia tridimensionale; vengono quindi effettuati una compressione in PCA, più compatta, e un allineamento tra l’immagine bidimensionale e la geometria ottenuta. L’algoritmo è automatico e prende in input una singola immagine bidimensionale e un riferimento al USF Human ID 3D database. Il suo output è lo specifico modello tridimensionale, e ottiene una precisione del 85-92% nella comparazione di facce virtuali con vista frontale, utilizzando rispettivamente PCA e LDA.

Guan, nei suoi studi [6], migliora l’algoritmo precedente, deformando un unico modello generico per adattarlo alla faccia specifica, ruotandolo se necessario. Dopo che la geometria tridimensionale è costruita, l’immagine bidimensionale della faccia viene proiettata ortogonalmente

21 alla geometria. Le prestazioni sono migliori rispetto al metodo di Hu e Jiang, mantenendo una precisione analoga sia per PCA che per LCA. Fooprateepsiri, Kurutach e Duangphasuk hanno proposto un framework integrato di analisi e sintesi per il riconoscimento facciale che tiene conto di variazioni di posizione, illuminazione e espressione della faccia [7]. Il sistema è diviso in tre fasi differenti: nella prima viene effettuata un’estrazione della faccia dall’immagine utilizzando la localizzazione delle iridi e delle caratteristiche della bocca, come i suoi angoli e la linea delle labbra, per orientare l’immagine tramite una stima basata sulle proiezioni ortografiche standard per parti antropologiche. La seconda fase consiste in un’ottimizzazione e riduzione dei vertici della mesh, che produrrà una maschera a minor precisione composta di lati “elastici” (Figura 2). La terza fase si concreta nello spostamento manuale dei vertici della maschera, al fine di adattarla perfettamente all’immagine di partenza. Utilizzando l’equazione di Lagrange per lo spostamento di sistemi dinamici, si ottiene una modellazione che avrà effetto sulla mesh ad alta risoluzione. L’algoritmo è, in questo caso, semi-automatico e prende ancora in input un’immagine bidimensionale. La percentuale di precisione nella

22 comparazione con facce virtuali con posizione frontale è di 70-85% per PCA e 87-95% per LDA.

In questa trattazione si è scelto di citare alcuni dei più significativi studi riguardanti il Face Recognition e Reconstruction. L’ultimo algoritmo che è stato analizzato, in particolare, è chiarificatore dei limiti di un approccio di questo tipo al nostro problema. Diventa chiaro e importante l’intervento dell’operatore nel modificare manualmente la mesh ottenuta dopo una prima estrazione automatica di informazioni delle immagini, a partire da una maschera standard. Il framework che è stato utilizzato, quindi, è riconducibile a un editor di mesh, che ottiene in input un insieme di informazioni derivanti

dalla prima elaborazione o, viceversa, si occupa di creare sia le informazioni preliminari, che attuare le modifiche che vengono applicate successivamente ai lati “elastici”. Avendo necessità di lavorare su ritratti frutto dell’interpretazione (e dell’immaginazione) di artisti, è inoltre ancora più evidente la possibile discordanza tra i tratti del

disegno e possibili facce standard contenute in un database. Un artista, infatti, secondo la propria sensibilità può anche disegnare ritratti che non seguono alcuna forma di realismo (Figura 3).

Figura 3: Esempio di ritratto non realistico (Pablo Picasso, Donna con cappello verde, 1939)

23

2.5 Shape from shading

Lo Shape from Shading (SfS), letteralmente Forma dall’Ombreggiatura, è una tecnica scoperta negli anni ’70 da Horn [8]. Si tratta di un classico problema di Computer Vision, come approfondito in [9]. Lo scopo di questa tecnica è ricostruire una scena tridimensionale a partire da una o più immagini, che possono essere descritte in vari modi tra cui i più comuni sono per profondità
(, ), con la normale alla superficie (,  , ) e con il gradiente della superficie (, ). La ricostruzione si

ottiene ricoprendo la superficie con una graduale variazione dell’ombreggiatura dell’immagine.

In particolare, la profondità può essere considerata come la distanza dalla camera al punto della superficie o, viceversa, l’altezza relativa della superficie a partire da un piano; la normale alla superficie è l’orientamento del vettore perpendicolare alla tangente del piano; il gradiente della superficie (, ) = 

, 

  è il tasso di variazione della

profondità nelle varie direzioni.

Per risolvere il problema è importante studiare come è formata l’immagine attraverso un modello: quello di riferimento è il modello Lambertiano, in cui il livello di grigio nell’immagine dipende dalla posizione della sorgente di luce e dalla normale alla superficie. Dato che non tutte le immagini seguono il modello in questione, a maggior ragione quelle frutto dell’interpretazione di artisti, si può facilmente intuire che sono molti gli approcci alla tecnica.

24

Figura 4: Modello Lambertiano

Il modello Lambertiano (Lambertian reflectance model, Figura 4) è spesso usato come modello di riflessione diffusa, che permette di riflettere la luce in ogni direzione, in base alla normale della

superficie e alla posizione della sorgente di luce. Misurando l’angolo tra la normale  e il vettore direzione della luce , è possibile conoscere il comportamento della luce nel punto in questione. Se l’angolo è piccolo il punto sarà ben illuminato perché la luce vi cade in modo perpendicolare rispetto alla superficie, mentre se l’angolo è grande il punto sarà poco illuminato in quanto la superficie non sarà diretta verso la luce. La formula del modello è:

à =  ∙  dove ∙ è il prodotto scalare tra i due vettori.

In genere, per memorizzare le informazioni sulla normale della superficie, si utilizza un’immagine in formato RGB, chiamata normal map. Questo formato, impiegato fin dagli anni ’30, descrive i colori tramite un modello di tipo additivo che, attraverso la combinazione dei tre colori base rosso (Red), verde (Green) e blu (Blue), da cui il nome, riesce a descrivere quasi tutto lo spettro dei colori visibili. Questo è il formato standard per tutte le periferiche elettroniche, ad eccezione delle stampanti. In questo formato, se  =  =  per ogni pixel, si avrà

25 un’immagine in scala di grigi. Le stampanti usano il modello sottrattivo CMYK, da ciano (Cyan), magenta (Magenta) e giallo (Yellow), che sono le varie combinazioni due a due dei colori RGB, mentre K indica il canale di colore nero. Se RGB è additivo in quanto la somma del massimo dei tre colori fornisce il colore bianco, CMYK è sottrattivo in quanto l’assenza dei tre colori indica la presenza del bianco, e per questo il secondo formato è utilizzato per le periferiche di stampa.

La normal map memorizza le direzioni delle normali in ciascun punto. Blender, un applicativo rilasciato sotto la licenza open source GNU General Public Licence per modellazione, animazione, composizione e rendering di immagini tridimensionali, utilizza i tre canali di colore del formato RGB per salvare le informazioni sulla direzione della superficie secondo il seguente schema:

• Rosso da 0 a 255 indica la direzione X da 1 a 1; • Verde da 0 a 255 indica la direzione Y da 1 a 1; • Blu da 0 a 255 indica la direzione Z da 0 a 1.

Dato che le normali sono sempre dirette nella direzione dell’osservatore, i valori negativi di Z non sono memorizzati (dato che sarebbero superfici invisibili). Esistono comunque altri formati dove viene utilizzato un range di colore tra 128 e 255.

26 Con le schede grafiche di ultima generazione è possibile utilizzare la tecnica detta normal mapping, ovvero l’applicazione della normal map come texture di una mesh al fine di simulare la porosità di una superficie, come vedremo meglio in seguito.

Come si può ben intendere, un sistema per indicare la profondità
(, ) di un’immagine è utilizzare una matrice che salva il valore # per ogni pixel. Un sistema analogo è utilizzare la height map, che altro non è che un’immagine in scala di grigi. Supponendo ancora di utilizzare il formato dell’immagine in RGB, si può considerare un solo canale di colore (dato che tutti hanno lo stesso valore) per che indica l’altezza: dato il valore rosso in (, ) 0 ≤ _, ≤ 255, avremo che se _, = 0, ossia siamo in presenza di colore nero, la profondità non sarà discosta dal piano di superficie originale, mentre se _, = 255, ovvero in presenza del bianco, sarà lontana. Per ogni valore intermedio si avrà una profondità intermedia. In altre parole, dato il valore della superficie
' = 0 per ogni pixel (, ), e una funzione a piacere monotòna

crescente ((), la profondità calcolata tramite la height map sarà
, =
'+ ((, ). Questa tecnica è chiamata displacement mapping,

e viene usata intensamente nei sistemi di generazione e caratterizzazione dei terreni con lo scopo di deformare la mesh. Si può distinguere in displacement mapping geometrico e displacement mapping per micropoligoni: mentre il primo agisce direttamente sui punti della mesh poligonale suddivisa precedentemente in triangoli, il secondo genera i poligoni in fase di rendering o pre-rendering a partire da una forma più elementare.

27 Se i colori della mesh non sono costanti e derivano, ad esempio, da un’immagine, viene utilizzata la tecnica di diffuse mapping: in sostanza l’immagine viene spalmata sulla mesh secondo delle ben determinate coordinate e ne rappresenta il colore. La diffuse map, a differenza della normal map, non contiene informazioni in merito alla direzione dell’illuminazione. Di una mesh, anche se alterata con le tecniche suddette, è possibile visualizzare il wireframe, ossia lo scheletro dei poligoni che rappresenta la forma; questa modalità può essere significativa per capire il modo in cui la mesh è costruita a prescindere dalla presenza della texture.

L’applicazione delle tecniche di displacement mapping, normal mapping e diffuse mapping si può chiamare image mapping.

Esistono diversi studi in merito alla creazione di applicativi per lo Shape from Shading a partire da una singola immagine, molti dei quali sfruttano le informazioni date dalla sua normale alla superficie, supponendo che essa sia disponibile.

L’approccio tradizionale per ricostruire una superficie a partire dalla sua normale è quello via integrazione, ma rimane comunque particolarmente complesso trovare appropriate tecniche di regolarizzazione per imporre i requisiti necessari al fine di rendere il gradiente alla superficie integrabile.

Terzopoulos, già a partire dalla fine degli anni ’80, ha proposto una variazione alla formulazione del problema [10] che consiste nella creazione di una funzione che minimizza la differenza tra profondità e contrasto di orientazione. In effetti viene minimizzata la discontinuità

28 delle superfici e del loro orientamento sfruttando aggiornamenti dinamici e successivi delle superfici visibili.

Franktot e Chellappa [11], in seguito, hanno introdotto un semplice e versatile algoritmo che proietta il gradiente della superficie in un insieme di funzioni integrabili da cui viene ricostruita la superficie.

Peter Kovesi dimostra, a sua volta, che la ricostruzione delle forme delle superfici a partire dalle immagini è possibile utilizzando Shapelets e le normali alla superficie [12]. La Shapelet, ovvero un insieme di funzioni base utili a rappresentare la forma, è un termine coniato da Refregier, che utilizzava questo strumento per decomporre gli oggetti contenuti nelle immagini in una serie di funzioni su diverse forme [13] e deriva dai due termini inglesi shape e palette, letteralmente forma e tavolozza. Altri studi mantengono il termine Shape-Palette [14][15], ma per semplicità in questo studio continueremo ad utilizzare il neologismo coniato da Refrieger. La teoria di Kovesi si sostanzia nell’idea che la forma della superficie dipende strettamente dalle normali ad essa, e che applicandovi una serie di funzioni fornite dalle Shapelets, è possibile ricostruire la forma della superficie. Astraendo l’algoritmo di Kovesi a un’analisi bidimensionale, le funzioni scelte sono una serie di Gaussiane, la cui altezza è proporzionale al punto più alto della superficie ricostruita. Nell’effettiva ricostruzione, nello spazio tridimensionale, è necessaria una serie di correzioni per le ambiguità di pendenza e inclinazione, che sono a loro volta dipendenti strettamente dal soggetto in questione e vengono pertanto scelti dall’utente. Nel caso di soggetti con contorni occlusi a 90 gradi rispetto all’osservatore, ad esempio quelli presenti in

29 un ritratto, per ottenere un buon risultato l’utente è costretto alla selezione manuale dei bordi per la ricostruzione, ottenendo poi, con la corretta impostazione di inclinazione e pendenza, un’approssimata ricostruzione a due dimensioni e mezzo del ritratto. Seppure la ricostruzione di Kovesi è precisa rispetto alla posizione nello spazio, tuttavia è povera dei dettagli propri dell’immagine e si può definire non accurata, sebbene sia pulita da rumore, come dimostra la Figura 6.

Più recenti studi condotti da Wu, Tang, Shum e altri, hanno ripreso le Shapelets per creare dei metodi di ricostruzione di forme a partire da immagini.

Il primo studio riguarda l’utilizzo interattivo di una Shapelet [14]: l’interazione è piuttosto semplice in quanto viene disegnata una semplice primitiva bidimensionale sull’immagine in input, quindi

viene specificato

l’orientamento tridimensionale tracciandone il corrispettivo nella Shapelet. Come dimostrano questi studiosi, questo semplice sistema di interazione può essere usato per creare superfici

Figura 6: Ricostruzione della forma con selezione manuale dei bordi con metodo di Kovesi

30 tridimensionali significative. La Shapelet utilizzata altro non è che un’immagine bidimensionale che ha una qualche corrispondenza con informazioni geometriche nello spazio (nel caso in esame vengono usate alcune sfere di raggio differente).

Il secondo studio presenta un sistema interattivo per la ricostruzione di normali alle superfici e la loro rappresentazione in modelli tridimensionali a partire da singole immagini [15]. Il sistema interattivo è suddiviso in due fasi: la prima è costituita dalla presentazione di un innovativo algoritmo per la ricostruzione di normali della superficie nelle regioni dell’immagine con alta frequenza di particolari, la seconda consiste in un sistema (interattivo) per la correzione delle normali nelle regioni dell’immagine povere di particolari. Per correggere le normali viene usata una Rotation Palette che prende spunto dalla Shapelet dello studio precedente ma è utile esclusivamente per indicare la direzione della normale: per questo è sufficiente che appaia come una sfera che rappresenta tutte le possibili direzioni di rotazione. Ogni parte di calcolo, sia la prima stima nelle aree ricche di particolari che le successive interattive, ha una partizione funzionale che ricorda una pipeline a tre stadi:

31 1. _{la stima della posizione della fonte di illuminazione,}

2. _{il calcolo delle normali alla superficie,}

3. _{il calcolo delle altezze che si discostano dal piano originario che} dipendono dal gradiente della superficie.

Come si può notare, i primi due passi seguono la ricostruzione del modello Lambertiano dell’illuminazione. Questo approccio produce un buon output, e il grado di accuratezza del risultato finale dipende esclusivamente dalle correzioni dell’utente tramite l’interazione con la Rotation Palette.

La validità della costruzione di editor per la modifica di forme mediante l’uso di tecniche di selezione di linee sulla superficie viene valorizzata anche da Gingold e Zorin [16], che hanno studiato un sistema per la modellazione tramite il disegno di tratti sulle superfici, indicando in quali aree applicarle. Gli utenti possono quindi dedurre la struttura tridimensionale a partire dall’immagine di partenza, sia per quanto riguarda le fotografie che per i quadri o semplici bozze. Astrarre queste informazioni al fine di utilizzarle in un applicativo di editing trasforma le criticità del problema dello Shape from Shading, inizialmente costituite dalla scelta di informazioni da specificare ed elaborarle secondo un certo criterio, riducendolo al modo in cui l’utente può specificare le modifiche alla struttura tridimensionale, ovvero come rendere l’editor intuitivo e utilizzabile dall’utente. Gli approcci di Wu, Tang e altri ci aiutano non poco ad astrarre alcune caratteristiche basilari per la creazione dell’editor, e confermano che i modelli tridimensionali possono essere creati e manipolati attraverso interfacce bidimensionali.

32 La natura general purpose, e quindi di modifica di qualsiasi possibile soggetto, dei sistemi che sfruttano lo Shape from Shading rende inoltre l’editor che si sta andando a sviluppare più potente rispetto all’editor per la ricostruzione facciale di Fooprateepsiri e altri [7] già analizzato nel capitolo 2.4, sebbene possa considerarsi ancora valida l’idea di intervento da parte dell’utente per adattare i risultati automatici ottenuti. La natura generale di questi algoritmi, come è facile intuire, produce una mesh a forma di piano di natura generica, ossia una griglia regolare i cui vertici vengono spostati e modificati, allungando e accorciando quindi i lati che li collegano. Viene perciò abbandonata la maschera per i volti propria dei sistemi di Face Recognition, difficilmente adattabile ai ritratti non propriamente realistici, mentre si mantiene un piano generico diviso in modo regolare in triangoli. Infine, occorre specificare che dovendo lavorare su ritratti frutto dell’immaginazione e dell’interpretazione di un artista, non è assicurato che il modello di illuminazione Lambertiano sia corretto per la data immagine, non essendoci pretesa, da parte dell’artista, di mantenere ad ogni costo il realismo o comunque sia la coerenza con un qualche modello di natura fisica o matematica.

33

Capitolo 3

Metodologia

3.1 Analisi degli studi

Lo studio preliminare ha mostrato come possano esistere diversi tipi di approccio per la creazione di forme a tre o a due dimensioni e mezzo a partire da singole immagini. Sebbene la ricostruzione facciale automatica possa apparire un interessante sistema con solide applicazioni esistenti, le tecniche necessitano spesso di database contenti informazioni relative a facce simili da ricostruire e sono in difetto per quanto riguarda le immagini non realistiche. La ricostruzione facciale, intesa come fase del riconoscimento facciale, infatti, necessita di una foto (e non un ritratto), il cui modello di illuminazione rispecchia la realtà. Attraverso tecniche di Shape from Shading, invece, è possibile agire interattivamente sulle superfici tridimensionali per modificarne la forma secondo delle ben determinate leggi, che consentono di adattare e modificare la superficie come in una qualsiasi fase di modellazione tridimensionale. Un effetto del genere si può ottenere tramite un editor, che può usufruire di semplificazioni e astrazioni utili e immediate per l’utente che lo utilizza. Gli studi nel settore possono venire in aiuto, rendendo possibile la fusione di varie tecniche, come lo sfruttamento delle normali alla superficie per ricavarne la forma e l’utilizzo di Shapelet come funzioni per calcolare l’orientamento della forma. La scelta della funzione da

34 usare per la realizzazione della Shapelet è un problema interessante, che si è risolto introducendo una nuova classe di funzioni parametriche, il cui utilizzo viene astratto e reso immediato per gli utenti. A queste tecniche, se ne possono aggiungere altre come lo sfruttamento della luminanza delle immagini per stimarne la forma e la possibilità di modificare manualmente le altezze secondo la volontà dell’operatore.

3.2 Funzionalità dell’editor

Dagli algoritmi analizzati per la realizzazione dello Shape from Shading, sono emerse alcune caratteristiche importanti, tra cui la possibilità di indicare la presenza marcata di bordi, utilizzando delle Shapelets per poter modificare le altezze. Si sono studiate quindi delle soluzioni matematiche per la risoluzione della creazione di una height map a partire dalla normal map e la combinazione delle varie tecniche di editing applicabili, in modo da utilizzare la height map per modificare il piano su cui viene rappresentato il quadro creandone il bassorilievo.

3.2.1 Creazione delle height map usando la luminanza

Un applicativo esistente, che viene usato assai frequentemente in fase di creazione di texture per la normal map e la height map, è Crazybump7. Questo software, estremamente intuitivo, ha un largo utilizzo tra i creatori di videogiochi e i modellatori, producendo, infatti, le rispettive texture relativamente accurate in modo stand-alone, a partire solamente dall’immagine che raffigurerà la texture principale di diffuse map. Nel

35 creare la height map, Crazybump genera un’immagine in scala di grigio. Esistono vari modi per il calcolo dell’immagine in scala di grigio a partire dall’immagine, uno dei quali è sicuramente il metodo della somma di un terzo dei tre colori principali, in modo che essi siano distribuiti uniformemente e ripartiti su tutti i canali (così che, nella resa, ogni componente di colore dell’immagine possa apparire bianca dove i valori sono alti, e nera dove sono bassi), ossia la semplice media matematica tra i tre canali di colore. Crazybump utilizza invece un sistema che sfrutta il concetto di luminanza, la quale rappresenta la misura fisica della lucentezza, cioè la proiezione tra l’intensità luminosa emessa da una sorgente di luce verso una superficie e l’area della superficie stessa. Per fare questo, viene applicata la formula standard della luminanza, per ogni pixel (, ) viene calcolato:

*, = 0.2989 ∗ , + 0.587 ∗ , + 0.114 ∗ , 8

A partire da un’immagine in formato RGB, questa formula calcola la

8 _{Secondo lo standard CCIR Rec. 601-2}

Figura 8: Autoritratto di Van Gogh in scala di grigio, a sinistra calcolato con la media dei colori, a destra tramite la luminanza.

36 luminanza pixel per pixel a partire da una somma pesata delle componenti RGB [17].

La differenza tra le due immagini in scala di grigio prodotte non viene distinta chiaramente dall’occhio umano, come si può ben vedere dalla Figura 8, ma sono concettualmente molto diverse: la prima è una mera media matematica dei colori presenti, ripartita quindi su ogni canale, mentre la seconda dipende sia dalla luminanza che dai colori. Entrambe potrebbero essere usate come height map ed usano la forte assunzione per cui un’area poco luminosa (scura) è necessariamente in basso e un’area molto luminosa (chiara) è in alto; la seconda metodologia, basandosi sul concetto di luminanza, è da ritenersi meno scorretta perché meno dipendente dalla sola distribuzione di colore.

3.2.2 Costruzione delle normal map

Come sappiamo, la normal map è un’immagine che mappa nei pixel la direzione della normale sul pixel, nel formato di colore RGB (capitolo 2.5). Esistono vari tool per la generazione di normal map di immagini, il già citato Crazybump, e i plug-in di vari editor di immagini come quello per Photoshop sviluppato da Nvidia9, e quello per Gimp10. Questi editor utilizzano sistemi di Edge Detection (determinazione dei contorni) delle immagini, tramite l’applicazione ripetuta di filtri.

L’Edge Detection è una branca fondamentale dalla Computer Vision e riguarda l’estrazione di caratteristiche che vengono riscontrate nelle immagini, in particolare le forti discontinuità dell’intensità luminosa nei

9 _{http://developer.nvidia.com/nvidia-texture-tools-adobe-photoshop} 10 _{http://code.google.com/p/gimp-normalmap/}

37 pixel delle immagini. Sotto particolari condizioni, si può assumere che a una discontinuità di illuminazione di un’immagine può corrispondere:

• una discontinuità in profondità;

• una discontinuità nell’orientamento della superficie; • un cambiamento del materiale;

• una variazione dell’illuminazione della scena [18].

In sostanza, nel caso ottimo, applicando un algoritmo di determinazione dei contorni si potrebbero trovare molte delle caratteristiche necessarie per un’analisi accurata delle immagini, utilizzando sistemi che sfruttano bruschi cambiamenti dell’intensità luminosa delle immagini.

Esistono diversi metodi per riconoscere i contorni contenuti in un’immagine, e la maggior parte di essi può essere raggruppata in due diverse categorie: metodi basati sulla ricerca che riconoscono i contorni cercando massimi e minimi della derivata del primo ordine dell’immagine (cercando la direzione in cui si ha il massimo gradiente locale) e metodi sull’attraversamento dello zero, ossia che cercano i punti in cui la derivata del secondo ordine passa per lo zero (solitamente la funzione laplaciana ∆(() = ∇ ∙ (∇ (()) = ∇3((), definito in coordinate cartesiane con ∇3= 4

4+  4

 4).

Una tecnica particolarmente performante in termini di tempi di calcolo per trovare i contorni in un’immagine è quella di utilizzare delle convoluzioni dell’immagine utilizzando dei filtri di valore intero, applicati sia in direzione verticale che orizzontale, chiamati operatori. Tecnicamente questi sono operatori differenziali che calcolano valori approssimati del gradiente in ciascun punto dell’immagine trovando la

38 direzione lungo la quale si ha il massimo incremento possibile dal chiaro allo scuro, e la velocità con cui avviene questo cambiamento lungo la direzione trovata. Il chiaro e lo scuro possono essere forniti attraverso la luminanza. Viene eseguita questa operazione invece di ricostruire un’immagine continua al fine di ottenere il gradiente che fornisce la derivata discreta. Dato che il risultato ottenuto fornisce informazioni anche sulla velocità di cambiamento, c’è la probabilità di riscontrare sia un contorno che l’orientamento del contorno stesso.

In termini matematici, il gradiente di una funzione in due variabili (nel nostro caso la luminanza) è in ciascun punto un vettore bidimensionale le cui componenti sono le derivate del valore della luminanza in direzione orizzontale e verticale, che è diretto verso la direzione del massimo aumento di luminanza possibile e la sua lunghezza corrisponde alla velocità di cambiamento di luminanza. I valori della derivata in ciascun punto dell’immagine sono funzioni dei valori della luminanza in quel punto.

Attraverso l’applicazione della convoluzione di due matrici bidimensionali, la prima delle quali rappresenta l’immagine originale e la seconda il filtro da applicare (kernel), si possono applicare i filtri alle immagini. Il funzionamento è abbastanza semplice: per ciascun valore della matrice 5, che rappresenta i valori in scala di grigio dei pixel dell’immagine, viene sovrapposta la matrice 6 che rappresenta il kernel, per cui il centro di 6 è posto nella posizione del pixel di 5. Il valore di ciascun pixel di A viene ricalcolato come somma dei prodotti di ciascun elemento del kernel col corrispondente pixel della matrice 5 sottostante.

39 La tecnica in questione è quella scelta nell’editor per la produzione di normal map. Gli operatori utili per le tecniche di Edge Detection sono rappresentati da kernel diversi a seconda che operino nella direzione orizzontale o verticale, e variano a seconda del soggetto che ha ideato l’operatore. Normalmente vengono usati semplici kernel di dimensione 3x3, che già forniscono buone approssimazioni dei risultati, e in alcuni casi di dimensione 5x5.

L’operatore di Sobel [19] è stato il primo degli operatori creati, ed è la magnitudo del gradiente calcolato da 78_3 +  ₃, per cui

 = (93+ :9;+ 9<) (9'+ :9=+ 9>)  = (9'+ :9?+ 93) (9>+ :9@+ 9<) ed è così definito: • _ = A +1 0 1 +2 0 2 +1 0 1B ∗ 5 •  = A +1 +2 +1 0 0 0 1 2 1B ∗ 5.

Questo operatore fornisce maggiore enfasi ai pixel che sono ortogonali al centro del kernel. L’operatore di dimensione 5x5, l’operatore di Sobel è:

• _ = C D D D E+1₊₄ +6 +4 +1 +2 +8 +12 +8 +2 0 0 0 0 0 2 8 12 8 2 1 4 6 4 1GH H H I ∗ 5 •  = C D D D E+1₊₂ 0 2 1 +4 +8 0 8 4 +6 +12 0 12 6 +4 +8 0 8 4 +1 +2 0 2 1GH H H I ∗ 5.

40 L’operatore di Prewitt differisce dall’operatore di Sobel per avere come costante : = 1, mantenendo invece la stessa equazione, per cui non viene data alcuna enfasi come per Sobel per i pixel che sono al centro del kernel.

Esso è definito come:

• J_ = A +1 0 1 +1 0 1 +1 0 1B ∗ 5 • J = A +1 +1 +1 0 0 0 1 1 1B ∗ 5 E in 5x5 è definito come: • J_ = C D D D E+1₊₁ +1 +1 +1 +2 +2 +2 +2 +2 0 0 0 0 0 2 2 2 2 2 1 1 1 1 1GH H H I ∗ 5 • J = C D D D E+1₊₂ 0 2 1 +1 +2 0 2 1 +1 +2 0 2 1 +1 +2 0 2 1 +1 +2 0 2 1GH H H I ∗ 5.

L’operatore di Sobel non mantiene comunque una perfetta simmetria nella rotazione.

L’operatore di Scharr prova ad ottimizzare questa proprietà [21]. Esso è definito, in 3x3, come: • K_ = A +3 0 3 +10 0 10 +3 0 3 B ∗ 5 • K = A +3 +10 +3 0 0 0 3 10 3B ∗ 5.

41 Come si vedrà in seguito, più grande è il kernel, maggiore è la sensibilità al rumore della normal map creata. Il kernel di Scharr di dimensione 3x3, tuttavia, mantiene una sensibilità al rumore paragonabile al filtro di Sobel o di Prewitt di dimensione 5x5. A partire dalla matrice di convoluzione ottenuta applicando uno dei filtri, si utilizza il formato delle immagini RGB per mappare nel canale rosso la risultante della convoluzione nella direzione

orizzontale, nel canale verde la risultante della convoluzione verticale, mentre il canale blu sarà sempre perpendicolare al piano dell’immagine. La tabella presentata mostra le diverse normal map ottenute applicando i vari filtri alla stessa immagine (Figura 9).

Tutte le normal map approssimano lo stesso risultato con particolare attenzione al rumore per quanto riguarda i filtri di maggior dimensione, quindi accentuando il riscontro di dettagli dove, ad esempio, il bordo è meno marcato.

Figura 9: Fernando Botero, Monna Lisa all’età di 12 anni, 1960.

42

Tabella 1: Esempi di normal map.

(a) (b) (c)

(d) (e)

(a) Filtro di Sobel 3x3 (b) Filtro di Prewitt 3x3 (c) Filtro di Scharr 3x3 (d) Filtro di Sobel 5x5 (e) Filtro di Prewitt 5x5

Tabella 2: Confronti di normal map.

Filtro di Prewitt 3x3 Filtro di Prewitt 5x5 Filtro di Scharr 3x3

Un ulteriore algoritmo per la determinazione di contorni fu presentato da Canny nel 1986 e consisteva in un algoritmo per determinare il maggior numero di bordi nelle immagini [21]. L’algoritmo si preoccupa in primo luogo di diminuire il rumore dell’immagine, nel ricercare il gradiente della luminosità e l’individuazione dei bordi operando su massimi e

43 minimi locali del gradiente. Utilizza un filtro Gaussiano per sfuocare l’immagine, e utilizza diverse soglie impostabili per individuare i minimi e i massimi da scartare.

Sebbene questo algoritmo possa essere considerato uno dei migliori prodotti, risulta essere eccessivamente costoso per quanto riguarda le prestazioni e non è accettabile in una applicazione interattiva. I risultati ottenuti con i filtri di Sobel, Prewitt e Scharr sono ottime approssimazioni.

3.2.3 Costruzione della height map a partire dalla normal map. Teoria sui cerchi osculatori

A partire dalle normal map è possibile calcolare un’altra forma di height map, sfruttando i cerchi osculatori [22].

Come sappiamo la mappa delle normali alla superficie indicano il modo in cui la pendenza della superficie varia e riflette la luce. La normale è, per definizione, la perpendicolare alla superficie. Sul piano cartesiano, la normale di una linea curva in un punto è la perpendicolare alla retta tangente in quel punto. In particolare, data una curva M(, ) = 0, la sua retta tangente nel punto (_', _') è M_ ∙ ( _') + M ∙ ( _') = 0, mentre la normale è M ∙ ( _') M_ ∙ ( _') = 0.

44 Graficamente, le normale (_?e ₃) e le tangenti (NO_? e NO₃) per i punti (?, ?) e (3, 3) sono raffigurate nella Figura 10.

Si definisce cerchio osculatore di una curva P = M(, ) in un dato punto J(_', _') la circonferenza che ha la stessa tangente di P nel punto J e la sua stessa curvatura. Proprio come la tangente è la migliore retta che approssima la curva nel punto J, il cerchio osculatore è la miglior circonferenza che approssima la curva in J.

Ad esempio, se si considera un’ellisse centrata nel punto (, 0), e supponendo che  = 9 +  per un qualche  Q 0, quindi l’ellisse si sviluppa nel primo e nel quarto quadrante del piano

Figura 10: Tangenti e Normali.

45 cartesiano ( Q 0), definita dall’equazione

( )3

93 + 3

R3 = 1

il cerchio osculatore ha equazione ( :)3+ ( S)3 = T3, come nella Figura 11 che rappresenta la situazione tipica.

È necessario quindi determinare :, S e T al fine di ricavare l’equazione del cerchio osculatore, che, nel caso in esempio, deve soddisfare le seguenti condizioni:

1. _{La circonferenza deve passare dal punto} (, 0);

2. _{La tangente alla circonferenza nel punto} (, 0) deve coincidere con la tangente all’ellisse nello stesso punto;

3. _{La curvatura della circonferenza nel punto} (, 0) deve coincidere con la curvatura dell’ellisse nello stesso punto.

Si tratta quindi di un sistema di tre equazioni in tre variabili. La condizione 2 viene soddisfatta se il centro del cerchio osculatore è posto sull’asse delle ascisse, il che riduce l’equazione della circonferenza in ( :)3_{+ }3 _{= T}3_{, quindi S = 0. Per determinare la condizione 3,}

sappiamo che la curvatura della circonferenza è ?

U e la curvatura

dell’ellisse in (, 0) è data da VV(, 0) per cui ′′ denota la derivata seconda X4

X 4. Una volta ottenuto T è possibile ottenere facilmente :.

Oltre che alle ellissi, si possono calcolare i cerchi osculatori anche per le curve. Data una curva M(, ), infatti, esiste un unico cerchio osculatore in un dato punto (, ). Rispetto a una retta ((), invece, per qualsiasi punto di essa esistono infiniti cerchi osculatori, a raggio variabile. Si tratta infatti del fascio di circonferenze avente per retta tangente la retta

46

Figura 12: Cerchi osculatori di una retta.

data (() e passante per il punto (, ). Ogni cerchio osculatore appartenente al fascio di circonferenze ha l’interessante proprietà di possedere il centro nella retta perpendicolare alla retta ((), come mostra la Figura 12.

Come sappiamo, per ogni fascio di circonferenze esiste una sola circonferenza tangente a una retta e passante per due punti. Data quindi una curva M(, ) passante per J_?(_?, _?) e J₃(₃, ₃), e le due normali ? e 3, esiste un solo cerchio osculatore P? alla normale ? passante

per J_? e per J₃ e un solo cerchio osculatore P₃ alla normale ₃ passante per J₃e per J_?, e P_? = P₃, infatti posto il sistema le tre condizioni:

1. Circonferenza passante per il punto J?;

2. _{Circonferenza passante per il punto} J₃; 3. _{Circonferenza tangente a} _? in J_?.

Il sistema ha una unica soluzione, che risolve anche il sistema: 1. _{Circonferenza passante per il punto} J_?;

2. Circonferenza passante per il punto J3;

4. _{Circonferenza tangente a} ₃ in J₃.

La circonferenza ottenuta ha il centro nel punto di intersezione tra le tangenti a M(, ) nei punti J_? e J₃, rispettivamente NO_? e NO₃ (Figura 13).

47 Questa proprietà può essere sfruttata per calcolare la height map di un’immagine, data la sua normal map. Supponendo che ogni altezza è mappata sull’ordinata del piano cartesiano, è infatti possibile calcolare localmente, punto per punto, le varie altezze in base alla normale alla superficie, i due coefficienti angolari delle normali _? e ₃, le coordinate di uno dei due punti J_?o J₃ e l’ascissa  dell’altro punto, risolvendo il seguente sistema a tre equazioni e tre incognite

Y Z [ Z \( ?)3+ ( ?)3 = ( 3)3+ ( 3)3 ( ?) = _1 ?( ?) ( 3) = _1 3( 3)

le cui equazioni corrispondono a:

Figura 13: Cerchio osculatore di una retta normale a una curva F(x,y) nel punto P, passante per due punti di cui uno il punto P.

48 1. Il raggio della circonferenza con centro nel punto J? è uguale al

raggio della circonferenza con centro in J₃. Data l’equazione generica della circonferenza

( ])3+ ( ])3 = T3

è sufficiente porre uguali i raggi delle due circonferenze, in modo che J_? = J₃.

2. L’equazione della retta tangente alla curva M(, ) passante per il punto J_? e perpendicolare alla normale _?, di cui è noto il coefficiente angolare _?;

3. _{L’equazione della retta tangente alla curva} M(, ) passante per il punto J₃ e perpendicolare alla normale ₃, di cui è noto il coefficiente angolare ₃.

Conoscendo quindi i valori _? e ₃, le coordinate di J_? e ₃ di J₃, risolvendo il sistema è possibile ottenere il valore di ₃ (Figura 14).