Prof. Maurizio Falcone@. Dipartimento di Matematica. Sapienza - Università di Roma
Metodi numerici per le equazioni alle derivate
parziali nonlineari e applicazioni
Il tema della approssimazione numerica delle equazioni alle derivate parziali è stato sempre presente nelle attività di cal-colo scientifico presenti al CASPUR. Nell’ultimo anno si sono sviluppati in particolare alcuni progetti relativi al trattamento delle immagini, al controllo ottimo ed ai giochi differenziali e allo studio dei sistemi dinamici. Questi temi, apparentemente molto lontani tra di loro, hanno in comune il fatto che per ri-solverli occorre calcolare la soluzione “debole” di una equazio-ne alle derivate parziali non liequazio-neare (si dice debole perchè non si chiede che esistano tutte le derivate). Si tratta, ad esempio, di equazioni di tipo “eiconale” nel caso del problema di Shape-from-Shading [4,5,6] o di equazioni paraboliche degeneri, nel caso della evoluzione di un fronte secondo la curvatura media [2].
Fig 1.Shape-from-Shading: foto e superficie ricostruita. Questo elemento comune ha portato a maturare l’idea di una libreria dedicata alla approssimazione di questi problemi, la libreria HJPACK [9]. E’ bene chiarire subito che la difficoltà principale che si incontra nella risoluzione di questi problemi è nel fatto che le soluzioni rilevanti che interessa calcolare non sono funzioni regolari [1], dunque non è lecito consi-derare le loro derivate prime o seconde. Grazie al lavoro di numerosi ricercatori in molti casi, ma non in tutti, è possibile affermare che una soluzione “debole” (nel senso detto “di viscosità”) esiste ed è unica.
Questo apre la strada allo studio di metodi numerici conver-genti alla soluzione e permette anche di sviluppare una teoria dell’errore, cioè di sapere che errore dobbiamo aspettarci da un algoritmo di approssimazione che converga alla soluzione quando i passi di discretizzazione tendono a zero. Dal punto di vista applicativo questi risultati sono di notevole importan-za proprio perché permettono di scegliere in modo opportuno i parametri di discretizzazione per ottenere un risultato
approssimato con la precisione necessaria. Un’altra difficoltà riguarda la soluzione numerica. Dal punto di vista computa-zionale si tratta spesso di problemi molto costosi per l’altissi-mo numero di nodi necessari nella discretizzazione e questo rende necessario lo sviluppo di algoritmi paralleli. Nel caso del controllo e dei giochi lo spazio degli stati supera facilmente le dieci variabili (e la griglia ha quindi n10 nodi) [3, 7] mentre per le immagini i nodi corrispondono ai pixel di una immagine e si arriva facilmente al milione.
Vediamo qualcuno dei problemi affrontati. Nel problema di Shape-from-Shading [6, 10] si tratta di calcolare la superficie di un oggetto rappresentato in una singola foto. E’ un proble-ma inverso molto studiato in letteratura per le sue possibilità di applicazione al riconoscimento automatico di oggetti ripresi da una telecamera (si parte dall’immagine per ricostruire la superficie). In alcuni problemi di sicurezza e di controllo del territorio l’oggetto è il viso di una persona che si vuole riconoscere tra quelle presenti in una base di dati. Nel caso della archiviazione di libri antichi, si tratta invece di calcolare la superficie del libro in modo da correggere automaticamente le deformazioni del testo dovute al fatto che la superficie del libro non è piatta e, magari, effettuare l’analisi del testo.
Fig 2.Segmentazione di una immagine medica. 56
Sempre nel campo del trattamento delle immagini, attraverso l’evoluzione di una curva con una velocità normale dipendente dai toni di grigio dell’immagine è possibile individuare (seg-mentare) il bordo di zone particolarmente interessanti per l’analisi biomedica. Più in generale il problema di seguire l’evoluzione di curve nel piano (e superfici nello spazio) trova applicazione in molti problemi fisici in cui la curva/superficie separa due fluidi o due stati fisici
(solido/liquido). Per questo motivo l’approssimazione numeri-ca di questo tipo di problemi evolutivi nonlineari, legati ad una particolare classe di metodi denominati “level-set” [11], è sta-ta al centro di varie simulazioni ed è contenusta-ta nella libreria HJPACK sviluppata in una collaborazione tra il Dipartimento di Matematica e il CASPUR.
La libreria è “public domain” (scaricabile dal sito www.caspur. it/hjpack) e “open source” e raccoglie vari metodi numerici per la soluzione di equazioni di Hamilton-Jacobi (da qui il nome). Al momento sono implementati metodi alle differenze e
semi-lagrangiani su griglie struttu-rate per differenti tipi di equazioni: evolutive e stazionarie, di primo e secondo ordine.
Attraverso la sua interfaccia gra-fica, realizzata utilizzando Tcl/Tk, un linguaggio particolarmente effi-cace in questo contesto, è possibile scegliere l’equazione, i dati, le con-dizioni al bordo, i passi di discre-tizzazione ed il metodo numerico per ottenere una rappresentazione grafica della soluzione. La libreria è aperta perché si propone come uno strumento utile per tutti i ricercatori sia per la soluzione di nuovi problemi (che possono essere facilmente aggiunti ai menu), sia per lo sviluppo di nuovi metodi numerici ed il confronto con i metodi già noti in letteratura. Alcuni interessanti risultati sono stati ottenuti nel calcolo della Hamiltoniana effettiva con applicazioni allo studio dei sistemi dinamici e a problemi di omogenizzazione [8].
Nel prossimo anno, grazie anche alla concreta collaborazio-ne del CASPUR, si prevedono degli sviluppi sia per quanto riguarda i metodi numerici che per l’utilizzo di griglie non strutturate.
Bibliografia
1. G. Barles, Solutions de viscosité des equations de Hamilton-Jacobi, Springer, 1995. 2. E. Carlini, M. Falcone e R. Ferretti
A semi-Lagrangian scheme for the curve shortening flow in codimension 2, Journal of Computational Physic, vol. 225, n. 3 (2007), 1388-1408.
3. E. Cristiani, M. Falcone
A fully-discrete scheme for the value function of differential games with state constraints, in corso di stampa su Annals of Dynamic Games.
4. E. Cristiani, M. Falcone
Fast semi-Lagrangian schemes for the eikonal equation and applications SIAM J. Num. Anal., vol. 45, n. 5 (2007), 1979-2011.
5. E. Cristiani, M. Falcone, A. Seghini
Some Remarks on Perspective Shape-from-Shading models, Proceedings of SSVM07, Ischia 2007.
6. J.D. Durou, M. Falcone e M. Sagona
Numerical Methods for Shape from Shading: a new survey with benchmarks Computer Vision and Image Understanding, Elsevier, vol. 109, n. 1 (2008), 22-43. 7. M. Falcone
Numerical Methods for Differential Games via PDEs
International Game Theory Review, vol. 8, 2 (2006), 231-272. 8. M. Rorro
An approximation scheme for the effective Hamiltonian and applications Applied Numerical mathematics, vol 56, 1238-1254.
9. Sito della libreria HJPACK http://www.caspur.it/hjpack
10. Sito dedicato a Shape-from-Shading http://www.irit.fr/sfs/sfs.html
11. J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999
