RICERCA ITALIANA     

Modellazione Multirisoluzione di Campi Scalari e Forme Digitali Multidimensionali

Università degli Studi di Genova

Abstract

Negli ultimi anni, vi è stata una forte tendenza verso la generazione ed interazione con insiemi di dati di simulazione tempo-varianti nel contesto di svariati domini applicativi, quali la medicina, la meteorologia, l’astrofisica, l’ingegneria. Insiemi di dati tempo-varianti sono usati per studiare la dinamica e lo sviluppo di fenomeni in contesti applicativi, e sono caratterizzati dalle loro grandi dimensioni, e da campi scalari e vettoriali multipli e sovrapposti. L’attività di ricerca che proponiamo considererà i problemi computazionali derivanti dal trattamento di insiemi di dati volumetrici tempo-varianti di grandi dimensioni e di forme implicite statiche e dinamiche. Nella nostra ricerca, proponiamo di sviluppare modelli multi-risoluzione per la gestione di insiemi di dati dinamici di grandi dimensioni. Un modello multi-risoluzione racchiude svariate rappresentazioni di una forma geometrica ad un insieme, virtualmente continuo, di diverse risoluzioni. Lo scopo di tali modelli è di permettere di effettuare in modo efficiente sia il raffinamento selettivo (vale a dire, l’estrazione di rappresentazioni ad attive della forma digitale) che la trasmissione progressiva, riducendo così i requisiti di spazio ed aumentando le prestazioni dell’elaborazione. Le rappresentazioni multi-risoluzione sono state sviluppate per griglie di triangoli, che descrivono un terreno o il contorno di una forma tridimensionale. Recentemente, si sono fatte ricerche su modelli multi-risoluzione per campi scalari basati su griglie di tetraedri nell’ambito dell’analisi ad elementi finiti e nella visualizzazione scientifica. Le rappresentazioni multi-risoluzione saranno uno strumento efficace per la gestione di insiemi di dati molto grandi che descrivono campi scalari tempo-varianti anche grazie alla loro capacità di poter focalizzare l’attenzione su una regione di interesse specifica e di ridurre la dimensione della rappresentazione estratta. Ciò permetterà non soltanto la visualizzazione ed il controllo in tempo reale di grandi insiemi di dati, ma inoltre l'analisi e la visualizzazione delle caratteristiche salienti di tali insiemi di dati. Un modo efficace per modellare insiemi di dati tempo-varianti consiste nel considerarli come campi scalari quattro-dimensionali.

I problemi di ricerca più promettenti in questo contesto sono: la progettazione e lo sviluppo di modelli multi-risoluzione per campi scalari 4D, con la definizione e l’implementazione di nuove operazioni di analisi e visualizzazione su campi scalari tempo-varianti a risoluzione variabile; la modellazione in memoria secondaria basata su griglie di campi scalari tridimensionali o di dimensione maggiore. Affronteremo alcuni di questi problemi con un approccio indipendente dalla dimensione ed applicheremo una nuova struttura multi-risoluzione per modellare forme dinamiche 3D descritte da campi distanza adattivi e variabili nel tempo. I contributi originali della ricerca proposta sono nella progettazione e nello sviluppo di
- modelli multi-risoluzione per campi scalari 4-dimensionali e forme implicite dinamiche basate su una scomposizione del dominio del campo in una griglia regolare annidata;
- modelli multi-risoluzione per campi scalari 4-dimensionali basati su scomposizioni del dominio del campo in una griglia simpliciale non strutturata;
- strutture dati ed algoritmi in memoria secondaria per la modellazione multi-risoluzione e la visualizzazione di campi multidimensionali descritti da griglie non strutturate;
- rappresentazioni morfologiche multi-scala che combinano modelli multi-risoluzione basati su griglie simpliciali con una descrizione della morfologia di un campo scalare a diversi livelli di astrazione. <<<

Coordinatore Scientifico del Programma di Ricerca

Leila De Floriani Università degli Studi di GENOVA

Obiettivo del Programma di Ricerca

Negli ultimi anni si e’ vista una generale tendenza ad aumentare l'interazione con insiemi di dati tempo-varianti molto grandi nella simulazione scientifica. Questi insiemi di dati sono usati per studiare la dinamica e l’evoluzione di fenomeni in una varietà di domini applicativi, come la medicina, la meteorologia, l’astrofisica, l’ingegneria. Questi insiemi di dati sono caratterizzati da grandi dimensioni, di centinaia di gigabytes, e da campi scalari e vettoriali multipli. Come esempio, possiamo menzionare l’insieme di dati di instabilità di Ritchmyer Meshkov del gruppo ASCI del Lawrence Livermore National Laboratories. Esso rappresenta una simulazione nella quale due gas sono inizialmente separati da una membrana spinta contro una rete metallica, e consiste di 270 frames, ed ogni istante è simulato su una griglia di 2048x2048x1920. I sistemi di visualizzazione attuali possono gestire insiemi di dati più piccoli di vari ordini di grandezza, e analizzano gli insiemi di dati tempo-varianti come collezioni di dati volumetrici, ciascuno ad un istante di tempo differente. Inoltre non sono disponibili strumenti per estrarre conoscenza dagli insiemi di dati a disposizione. Con l’enfasi recente sullo sviluppo di una infrastruttura informatica per il trattamento di insiemi di dati ancora più grandi, vi è l'esigenza urgente di strumenti di visualizzazione e di esplorazione di alta qualità. Lo sviluppo delle capacità di elaborare e memorizzare insiemi di dati di grandi dimensioni ha provocato la generazione di enormi quantita’ di di grandi dati di simulazione.

I modelli multi-risoluzione sono stati usati per gestire grandi insiemi di dati poiche’ racchiudono svariate rappresentazioni di una forma geometrica ad un insieme, virtualmente continuo, di diverse risoluzioni. Lo scopo di tali modelli è di permettere di effettuare in modo efficiente sia il raffinamento selettivo (vale a dire, l’estrazione di rappresentazioni ad attive della forma) che la trasmissione progressiva, riducendo così i requisiti di spazio ed aumentando le prestazioni di calcolo. Le rappresentazioni multi-risoluzione sono state sviluppate per griglie di triangoli, che descrivono campi scalari bidimensionali (terreni) o il contorno di una forma tridimensionale. Recentemente, si sono fatte ricerche su modelli multi-risoluzione per campi scalari basati su griglie di tetraedri nell’ambito dell’analisi ad elementi finiti e nella visualizzazione scientifica.

Esistono diverse problematiche aperte nella rappresentazione di campi scalari multidimensionali. La disponibilità di insiemi enormi di dati volumetrici tempo-varianti propone sfide molto interessanti per il controllo, l’analisi e la visualizzazione di tali dati. Gli insiemi di dati volumetrici tempo-varianti sono insiemi di punti nello spazio Euclideo che descrivono un campo scalare a diversi intervalli di tempo. Molti strumenti di visualizzazione trattano tali insiemi di dati come collezioni di campi scalari 3D. Ciò non tiene conto del fatto che le sezioni trasversali oblique possono essere caratteristiche molto rilevanti del campo, o che l’animazione interattiva è spesso necessaria. Gli insiemi di dati volumetrici tempo-varianti possono essere descritti efficacemente come campi scalari 4-dimensionali, premettendo il controllo del campo ad una gamma continua di valori del tempo, o lungo piani di taglio arbitrari. Un modello multi-risoluzione è adatto all’estrazione di approssimazioni compatte ed adattive del campo ed a ridurre la complessità della gestione di tali insiemi di dati. Un tale modello richiede meno spazio rispetto alla codifica della rappresentazione a risoluzione completa (i nostri esperimenti nel caso di dati volumetrici hanno indicato che la struttura dati multi-risoluzione può richiedere 20% dello spazio richiesto per immagazzinare l'insieme di dati a risoluzione singola). Un modello multi-risoluzione permetterà non soltanto la visualizzazione ed l’analisi di grandi insiemi di dati tempo-varianti in tempo reale, ma analisi e visualizzazioni efficienti delle caratteristiche salienti di insiemi di dati scientifici. Inoltre, l’enorme dimensione degli insiemi di dati disponibili rende inadeguate per una codifica in memoria primaria persino rappresentazioni multi-risoluzione compatte. Da qui il bisogno di progettare strutture dati multi-risoluzione nuove e tali da permettere la stessa flessibilità delle rappresentazioni in memoria primaria, ma che possano funzionare in memoria esterna.

L'alto tasso di crescita di insiemi di dati scientifici provenienti da simulazione richiede nuovi metodi per l’analisi delle informazioni, che identifichino le caratteristiche di interesse nella forma geometrica, della topologia ed degli eventi temporali. In questo contesto, la sfida è lo sviluppo di tecniche per specificare, rilevare ed estrarre informazioni morfologiche da grandi insiemi di dati dinamici basati su decomposizioni del dominio del campo in regioni con caratteristiche di pendenza uniforme, o su decomposizioni guidate dalla topologia delle iso-superfici del campo.
La conoscenza della morfologia del campo può anche guidare gli strumenti di analisi delle caratteristiche per produrre descrizioni esatte e compatte. A questo scopo, abbiamo bisogno di nuovi modelli multi-scala, che uniscano le caratteristiche utili di un modello multi-risoluzione con una descrizione morfologica del campo. L'estrazione della conoscenza e l’analisi morfologica possono essere effettuate su tali modelli a livelli differenti di astrazione. La ricerca proposta affronta tutte queste problematiche. Altre applicazioni, quale la animazione nell'intrattenimento, la simulazione chirurgica nella medicina, la pianificazione del percorso o la rilevazione di scontri in robotica richiedono di utilizzare forme 3D che subiscano deformazioni al variare del tempo, dette forma dinamiche (o deformabili). Le forma 3D deformabili possono essere descritte efficacemente come superfici implicite tempo-varianti.

Le superfici implicite sono state usate come alternativa alle superfici parametriche per rappresentare forme 3D statiche, poiché permettono naturalmente di distinguere fra l'interno e l'esterno di una forma. Una superficie implicita è modellata spesso come campo di distanza, vale a dire come un campo scalare che specifica la distanza minima dalla forma che rappresenta. Una rappresentazione discreta di una superficie implicita è ottenuta campionando un campo distanza sui vertici di una griglia regolare. I campi di distanza discreti supportano efficientemente operazioni di modellazione. Una forma 3D dinamica puo’ essere descritta efficacemente come un campo di distanza tempo-variante, e quindi come campo distanza discreto. Un modello multi-risoluzione per campi scalari 3D e 4D basato su una suddivisione simpliciale annidata del dominio fornirà una base adatta alla realizzazione di operazioni di modellazione su forma 3D tempo-varianti. Ci proponiamo di studiare queste problematiche come parte del lavoro proposto.

I contributi della ricerca proposta risiedono nella progettazione e nello sviluppo di:
* modelli multi-risoluzione per campi scalari 4-dimensionali basati su una scomposizione del dominio del campo come griglia regolare annidata;
* modelli multi-risoluzione per campi scalari 4-dimensionali basati su scomposizioni del dominio del campo come griglia simpliciale non strutturata;
* strutture dati e algoritmi in memoria secondaria per la modellazione multi-risoluzione e la visualizzazione di campi multidimensionali descritti da griglie non strutturate;
* rappresentazioni morfologiche multi-scala che combinino modelli multi-risoluzione basati su griglie con una descrizione della morfologia di un campo a livelli di astrazione differenti.
* modelli multi-risoluzione per forme 3D statiche e dinamiche basate su griglie di tetraedri. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Le grigie di triangoli e tetraedri sono largamente utilizzate per rappresentare superfici free-form, di campi scalari e vettoriali. La grandissima quantità di dati disponibili per descrivere superfici e campi scalari ha condotto alla ricerca e allo sviluppo di metodi gerarchici per il controllo e la gestione del livello di dettaglio nella rappresentazione di un certo insieme di dati, detti anche modelli multirisoluzione o modelli a piu’ livelli di dettaglio o LOD (Level-Of-Detail). Un modello LOD comprende svariate rappresentazioni dello stesso oggetto spaziale a risoluzioni differenti e permette di effettuare efficientemente sia il perfezionamento selettivo che la trasmissione progressiva, riducendo così i requisiti di spazio ed aumentando le prestazioni di calcolo. Le rappresentazioni LOD sono state sviluppate per grigle di triangoli, ma più recentemente, diverse ricerche sono state fatte su modelli LOD per campi scalari basati su grigie di tetraedri, ad esempio nell’analisi ad elementi finiti e nella visualizzazione scientifica. In [10] abbiamo introdotto un modello LOD generale basato su grigle simpliciali, denominato Multi-Tessellation (MT). Il modello è definito per complessi simpliciali, il cui dominio e’ una varieta’ topologica, in dimensione arbitraria, ed è indipendente dalla strategia usata per generarlo. La MT è stata implementata in una libreria in linguaggio C++, ed e’ disponibile in pubblicamente [27].
Modelli LOD basati su griglie regolari sono stati sviluppati in computer graphics e nella letteratura su elementi finiti. Esempi sono forniti da griglie simpliciali annidate generate mediante bisezione ricorsiva di d-simplessi in tre o più dimensioni [16,20,23,29,31,42], grigie di tetraedri annidate generate da scomposizione regolare dei tetraedri (il cosiddetto red/green tetrahedral refinement) [1], o grigie generate da scomposizione del dominio in elementi annidati costituiti da tetraedri ed ottaedri [17]. I modelli LOD annidati basati su bisezione di d-simplessi sono rappresentazioni più flessibili, in quanto permettono di generare griglie altamente adattabili. Il problema di base è quello di riuscire ad estrarre da tali modelli griglia conformi, ovvero griglia senza discontinuità. Svariate tecniche sono state sviluppate per estrarre griglie conformi da griglie annidate di triangoli o tetraedri [22,37,25,42]. In [31,42], è stata applicata una tecnica, basata su procedura di controllo degli errori (detta saturazione di errore), forzando implicitamente la suddivisione dei padri prima della suddivisione dei loro discendenti. Un'alternativa molto efficiente consiste nell’estrarre insiemi di tetraedri che devono essere suddivisi contemporaneamente per mantenere la consistenza topologica, attraverso la tecnica di individuazione dei vicini. In [23] abbiamo proposto un algoritmo, che ha complessità costante nel caso pessimo, per l’individuazione dei vicini basata su codici di posizione. Le griglie estratte, usando la saturazione di errore, hanno in media il 5% in più di tetraedri rispetto a quelle estratte con la procedura d'individuazione dei vicini, e i tempi di estrazione della griglia sono gli stessi per versioni saturata e non saturata [11].
I modelli LOD più semplici basati su griglie irregolari forniscono griglie a risoluzione uniforme [18,22,34], ma non possono sostenere il perfezionamento selettivo. L’istanza tridimensionale della Multi-Tessellation (MT) richiede un po' più di due volte lo spazio usato da una griglia a risoluzione completa, il che non la rende adatta a gestire insiemi di dati di notevoli dimensioni [7]. Gli elementi di base di questa struttura dati LOD, denominata Full-Edge Tree (FET), sono una codifica compatta del full-edge collapse e del relativo operatore inverso, full-vertex split, e una codifica implicita delle dipendenze fra gli aggiornamenti. Abbiamo inoltre implementando una struttura dati LOD compatta sviluppata con un half-edge collapse, ovvero effettuata contraendo un edge ad uno dei relativi estremi, denominata Half-Edge Tree(HET) [7]. Le griglia raffinate selettivamente estratte da un HET, per un dato LOD, sono in media circa dal 34% al 75% più piccole di quelle che possono essere estratte da una FET.
Gli insiemi di dati volumetrici tempo-varianti sono insiemi di punti nello spazio Euclideo tridimensionale che descrivono un campo scalare al variare del tempo (per esempio, la pressione, la temperatura, la resistenza di un campo elettrico o magnetico). Il problema di modellare e codificare campi scalari tempo-varianti è stato recentemente considerato da alcuni autori [2,21,41]. In [21], è stato considerato il problema di come fare il tracking e di come visualizzare le caratteristiche locali di un insieme di dati volumetrico tempo-variante, sulla base dell'estrazione di iso-superfici tempo-varianti e di intervalli volumi usando iso-superfici a dimensione più alta. I campi tempo-varianti possono essere trattati anche come campi scalari 4-dimensionali considerando il tempo come quarta dimensione [35,68] ed possono essere analizzati estraendo iso-superfici, che consistono in celle tetraedriche, che possono poi essere visualizzate a diversi intervalli di tempo. Il dominio di un campo scalare 4D può essere modellato sia come una griglia iper-cubica, che come una griglia simpliciale con i vertici sui punti dati. Tuttavia, le procedure per l'estrazione di iso-superfici sono molto più semplici su griglia simpliciali.
Sono state proposte varie estensioni in 4 dimensioni dell’algoritmo di marching-cube che, in pratica, differiscono sul numero di casi da considerare nel caso di un cubo 4D. Weigle e Banks [41] hanno proposto una procedura ricorsiva per l'estrazione di iso-superfici a partire da complessi simpliciali, contando 5 diversi possibili casi per un 4-simplesso. La procedura è stata fatta applicata alla visualizzazione di campi scalari 3D instabili. In [24], abbiamo considerato una istanza 4D di un modello d-dimensionale basato su una decomposizione ricorsiva del dominio iper-cubico di un campo scalare 4D in una gerarchia 4-dimensionale di simplessi annidati (pentatopes), che abbiamo chiamato gerarchia di pentatopi (Hierarchy of Pentatopes (HP)). Per estrarre griglie conformi a risoluzione variabile, abbiamo progettato un algoritmo per l'individuazione dei vicini con complessità costante nel caso peggiore. L’algoritmo permette di rilevare in tempo reale cluster di pentatopi, che devono essere suddivisi allo stesso tempo al fine di mantenere la consistenza topologica.
Anche usando una struttura compatta di codifica, una rappresentazione LOD di insiemi di dati tempo-varianti di enormi dimensioni può facilmente eccedere la memoria disponibile. Sono state sviluppate in letteratura diverse tecniche in memoria secondaria per la semplificazione e per la rappresentazione dipendente dalla vista di griglia di triangoli, per la rappresentazione esterna di insiemi di grigie di tetraedri, e per la codifica di griglie di tetraedri annidate [5,9,14,20,25,26,37,39], ma non esistono tecniche, sviluppata per modelli LOD basati sulle grigie irregolari di tetraedri (come FET [4], o HET [7]).

Rappresentazioni basate su griglia approssimano arbitrariamente bene la geometria di un oggetto o di un campo scalare, ma falliscono nella descrizione della relativa struttura morfologica, definita da diverse caratteristiche critiche, come i punti critici, le linee integrali, o le regioni con caratteristiche di pendenza uniforme. Esiste in letteratura una quantità considerevole di lavori per l’estrazione di caratteristiche critiche da immagini a livelli di grigio e da modelli di terreno. La base matematica per la descrizione delle caratteristiche critiche è fornita dalla teoria di Morse [30]. Una funzione di Morse è una funzione C2-differenziabile in cui i punti critici sono isolati. Smale [30] ha dimostrato come le traiettorie che integrano il campo gradiente di una funzione di Morse formino celle che decompongono il dominio della funzione.Una cella manifold stabile per un punto integrale a e’ costituto dallle linee integrali che originano dal punto a. Le celle stabile decompongono il dominio in celle aperte, che formano un complesso, detto il complesso stabile di Morse. Il complesso instabile puo’ essere definito in modo simile in base alle linee integrali che convergono ad un un punto critico. L’intersezione dei complessi stabile ed instabile forma il complesso di Morse-Smale, quando è soddisfatta una proprietà specifica, detta di Morse-Smale [30]. La maggior parte dei metodi proposti per i terreni provano a simulare i suddetti concetti topologici su una rappresentazione lineare a tratti del campo, rilevando i punti critici ed approssimando le linee integrali [3,12,38]. In [8], abbiamo sviluppato una procedura euristica, basata su una tecnica incrementale, detta di region-growing, per generare una struttura simile al complesso di Morse-Smale nel caso lineare a tratti come base per un modello LOD di terreno che include le caratteristiche critiche a risoluzioni differenti.Le tecniche watershed sviluppate per la segmentazione di immagini possono essere applicate all’estrazione di caratteristiche critiche per un terreno [35}. Mentre la maggior parte degli algoritmi watershed si focalizzano su immagini raster, un metodo watershed [28] viene applicato alla segmentazione di superfici free-form triangolate basate su un'approssimazione discontinua. Molto meno lavoro è stato fatto nel caso 3D. In [13], viene descritto un algoritmo per la computazione dell'approssimazione di un complesso del Morse-Smale per campi scalari 3D lineari a tratti, che tuttavia e’ computazionalmente poco efficiente. In [8], abbiamo presentato una definizione costruttiva di un complesso di Morse-Smale discreto su una griglia simpliciale d-dimensionale, dove vengono usati soltanto i valori del campo ai vertici e la struttura di connessione della griglia, in modo simile a quello fatto in geometria digitale per le immagini. <<<