Algoritmi di Restituzione Prospettica

"Algoritmi di Restituzione Prospettica"

BobMaX - Luglio 2004

KEYWORDS: CAD-based Photogrammetry, Camera Matching

ABSTRACT

Il presente documento descrive l’evoluzione dei sistemi fotogrammetrici, da semplici produttori di cartografia vettoriale a modellatori tridimensionali e l’evoluzione degli algoritmi di calcolo prospettico per la restituzione metrica da singola foto.

1 INTRODUZIONE

L'idea di usare la fotografia a scopo di rilievo viene storicamente attribuita al francese Laussedat, nel 1850. Soltanto nei primi anni del 1900, tuttavia, vi sono state le prime applicazioni pratiche in cartografia, con l'avvento della fotogrammetria aerea. Dal 1946, dopo la fine della seconda guerra e dei segreti militari, sono iniziati i primi corsi universitari all' Istituto di Fotogrammetria e Remote Sensing in Finlandia. Il passaggio dai metodi ottico-meccanici di restituzione a quelli digitali sono avvenuti dopo il 1980. Da questa data, la fotogrammetria ha seguito l'evoluzione dei sistemi grafici computerizzati.

Negli ultimi anni i programmi CAD sono evoluti da semplice tool per il disegno 2d a sistemi complessi per la gestione della qualità del progetto. Le funzioni necessarie al disegno di organismi architettonici possono essere usate ora all'interno di programmi di restituzione fotogrammetrica, chiudendo un cerchio intorno alle necessità di modellizzazione dell'esistente.

Fig. 1 Classica Restituzione Fotogrammetrica Aerea

Fig. 2 Moderna Restituzione Tridimensionale Urbana

Fig. 3 Rilevamento Tridimensionale Laser

Ad oggi, le moderne tecniche di misurazione Laser, da terra o da piattaforma aerea, vengono integrate alla più tradizionale fotogrammetria monoscopica, riuscendo ad ottenere una "fotografia solida" di complessi organismi urbani.

Fig. 4 Restituzione Urbana tramite "Canoma"

2 La Fotogrammetria "CAD-based"

Prima di descrivere le tendenze della Fotogrammetria "CAD-based", è utile definire questi termini.

2.1 Definizioni

La sigla CAD sta per Computer Aided Design, ovvero Disegno Assistito da Computer. Il CAD è divenuto sinonimo di programma di gestione, manipolazione e visualizzazione di dati tridimensionali.

Dall'altro lato, tradizionalmente, la fotogrammetria si concentra sulla misurazione accurata di coordinate 3d, a partire da coppie di foto, terrestri o aeree, di organismi architettonici, o territoriali.

Generalmente, la fotogrammetria si è limitata alla restituzione, a partire da zero, dei contorni delle gronde degli edifici, o in genere alla proiezione in pianta dei manufatti architettonici, ad un livello di dettaglio cartografico.

Una caratteristica dei programmi di fotogrammetria tradizionali è quasi sempre stata la partenza dal nulla, cioè il ridisegno della geometria senza l'uso di cartografia esistente, quasi a sottolineare una forte scientificità di metodo.

Le funzioni grafiche presenti in un software di disegno fotogrammetrico, in genere si sono limitate fino a poco tempo fa al disegno di primitive grafiche bidimensionali su piani paralleli all'orizzontale.

Fig. 5 Cartografia vettoriale

3 Evoluzione della Fotogrammetria

Con l'avvento della fotogrammetria del vicino o "close-range" si sono applicate le tecniche di ripresa stereoscopica a facciate di edifici o interni, ottenendo, tuttavia, sempre rappresentazioni vettoriali degli spigoli significativi degli organismi ripresi.

Dal punto di vista matematico, la fotogrammetria stereoscopica usa sistemi di equazioni lineari per risolvere l'orientamento reciproco dei fotogrammi, note le coordinate di coppie di punti sulle prese fotografiche. Una volta orientati i fotogrammi e costruito il cosiddetto "modello stereoscopico", il programma si limita a restituire coordinate tridimensionali di punti collimati sulle due immagini tramite l'intersezione dei raggi visivi partenti dai due centri di presa [1].

Questo sistema di rilevamento, sebbene caratterizzato da notevole rigorosità, è tuttavia contraddistinto dagli elevati costi di gestione, legati alla necessità di effettuare riprese doppie, e da notevoli difficoltà di ripresa.

Inoltre, l'obbligo di riprese stereoscopiche ne limita l'uso al presente, e alla non utilizzabilità del patrimonio storico di immagini di repertorio, o illustrazioni e dipinti, per la ricostruzione di modelli di beni architettonici perduti, o perduti in parte.

3.1 Il Software "Facade"

Dal 1996 in poi si è assistito ad una evoluzione della fotogrammetria, a partire dalle esperienze di Paul Debevec, dell'Università di Berkeley, in California. La sua tesi in dottorato "Modeling and Rendering Architecture from Photographs" [2], è divenuto il testo di riferimento nella nuova tendenza della fotogrammetria. Il suo software "Facade" permette di calcolare i parametri prospettici da geometrie note e di restituire il modello tridimensionale con resa fotografica dell'esistente.

Fig. 6 Dal video "Campanile Movie" di Paul Debevec

Il risultato del procedimento di Debevec è un modello 3D "vestito" con i materiali desunti dalle foto.

Pur rimanendo un software sperimentale, nato all'interno di una ricerca universitaria , "Facade" è riuscito ad imporre una metodologia operativa e una tipologia di dati innovativa nel campo della fotogrammetria.

3.2 Costruzione della topologia del modello

Il punto di forza di "Facade" sta nel fatto che il modello che si va costruendo non è soltanto lineare, cioè costituito dalle linee rappresentanti i bordi dell'edificio, ma è determinato da oggetti base, quali parallelepipedo, piramide, tronco di piramide e altro, che possono essere legati da vincoli topologici, come adiacenza, sovrapposizione, centratura.

Questa "filosofia" di base rende molto più intuitivo la costruzione del modello, partendo da immagini prospettiche.

Fig. 7 Collimazione del modello 3D sulle foto

Fig. 8 Proiezione delle texture sul modello

In "Facade" i singoli componenti che compongono l'edificio si muovono insieme, solidali l'uno all'altro, quando si deve compiere l'operazione di associare i punti oggetto con quelli dell'immagine.

Parametri come l'altezza reale di un componente dell'oggetto verranno calcolati successivamente dal programma, risolvendo l'insieme dei vincoli.

Fig. 9 Schermata principale del Software "Facade" di Debevec

3.3 Il Software "Canoma"

Sulla stessa linea metodologica tracciata da "Facade", una serie di programmi sono stati sviluppati.

Il primo software commerciale a basso costo basato sulla fotogrammetria CAD-based è "Canoma", del 1998, creato da Robert Seidl e Tilman Reinhardt [3].

"Canoma" è caratterizzato da una notevole intuitività, per quanto riguarda l'interfaccia grafica, e da una forte interattività.

L'utente ha a disposizione una palette di primitive grafiche tridimensionali che possono essere posizionate sulla foto, e quindi ruotate e deformate come dimensioni base, fino a corrispondere visivamente all'immagine. Una volta "fissato" l'oggetto, il programma calcola i parametri prospettici, tramite un innovativo algoritmo che verrà descritto più avanti.

Fig. 10 Il Software "Canoma" di Robert Seidl e Tilman Reinhardt

Inserendo altre primitive grafiche, l'utente può definire il tipo di legame esistente con l'oggetto precedente, oppure un altro da lui scelto. Possono essere quindi sovrapposti, affiancati ed incollati i componenti visibili di un edificio.

Il catalogo degli oggetti grafici include il parallelepipedo, il piano orizzontale, quello verticale, il solido di estrusione, verticale o orizzontale, l'oggetto scalinata, l'arco, il cilindro ed addirittura il tavolo.

Una volta composto l'insieme di oggetti, inserendo i puti di collimazione, può essere richiamata la procedura finale che effettuata l'elaborazione del modello.

Oltre al calcolo del punto di vista e della dimensione degli oggetti, "Canoma" estrae dall'immagine fotografica, per ogni faccia dell'oggetto, la porzione corrispondente, e ne effettua il raddrizzamento ortogonale, creando i materiali che verranno visualizzati sul modello 3D finale.

Una volta ottenuto il modello, può essere inserita una seconda immagine, presa da un altro punto di vista, per ripetere il procedimento di collimazione, ed ottenere la copertura dell'oggetto con altri materiali, invisibili dalla prima foto. Per ottenere questo, l'operatore, semplicemente, deve ruotare l'oggetto fino a farlo corrispondere sommariamente a come appare dal nuovo punto di vista. Dopo questa operazione, deve inserire nuovi punti di collimazione. Per una registrazione più precisa, è possibile ingrandire la foto, fino a visualizzare i singoli pixel.

Quando anche la seconda foto risulta collimata, si può ripetere il calcolo, renderizzando di nuovo il modello.

La procedura può essere ripetuta con altre foto, anche a dettaglio maggiore, fino alla copertura totale del modello.

Fig 11 Immagine del fronte di S.Pietro in Montorio a Roma

Nel caso in cui un corpo interposto, quale una alberatura, risultasse creare coni d'ombra sulle texture, queste possono essere corrette individualmente, con una funzione di correzione pittorica, chiamata automaticamente da "Canoma", servendosi del programma preferito dall'operatore.

Corrette, nel caso, tutte le texture, il modello tridimensionale può essere salvato, nei formati standard previsti, verso i programmi CAD.

Tra i vari formati grafici è previsto il VRML97, divenuto oggi il file di interscambio di dati tridimensionali tra i più diffusi.

Un'altra possibilità, meno scientifica, prevista da "Canoma", è quella di permettere il salvataggio di una sequenza di punti di vista a scelta dell'operatore, per realizzare una animazione di percorso intorno o attraverso gli oggetti realizzati.

"Canoma" rappresenta oggi un esempio di un ottimo ed innovativo software fotogrammetrico, il cui sviluppo è terminato, e non è più distribuito.

Un limite di "Canoma" è stato, finora, la mancata possibilità di caricare la geometria di modelli tridimensionali provenienti da altri programmi.

Il presente articolo nasce dallo scambio di eMail tra lo scrivente e Robert Seidl, uno degli autori di "Canoma", riguardante la realizzazione di un modulo di conversione degli oggetti tridimensionali da un programma CAD al formato nativo di Canoma. Tale collaborazione ha prodotto il software ExportToCanoma [14], attualmente distribuito gratuitamente tramite il sito exporttcanoma.blogspot.com.

Fig. 12 Il Software ExportToCanoma

3.4 Altri programmi di Fotogrammetria CAD-based

Ad oggi, il numero di programmi a basso costo di restituzione tridimensionale da foto è in crescente aumento.

Fig. 13 Il Software "PhotoModeler" di Eos Systems

PhotoModeler Pro della Eos Systems permette di usare primitive grafiche di tipo CAD, per disegnare i contorni architettonici direttamente al di sopra delle foto, usate come sfondo.

Un altro programma usato nel campo della fotogrammetria CAD-based è ImageModeler, della RealViz, che produce anche MatchMover, un programma che applica l'algoritmo di calcolo su sequenze video.

Fig. 14 Il Software "ImageModeler" della RealViz

Il Software "Marina" usa la modellazione parametrica di poliedri per lala restituzione anche da antiche stampe, vecchie foto non calibrate o, addirittura, da schizzi progettuali.

Fig. 15 Il Software "Marina" dell' École des Mines de Nantes

Recentemente, è stato realizzato un programma gratuito, dell'Università di Hannover, in Germania, chiamato VoodooCameraTracker, che collima automaticamente sequenze di foto, ed esporta i punti tridimensionali trovati e i parametri della camera.

Fig. 16 Il Software Voodoo Camera Tracker dell'Università di Hannover

Si può facilmente dedurre una tendenza in atto che costituisce una ulteriore evoluzione della fotogrammetria: il calcolo dei parametri prospettici a partire non solo da sequenze di foto statiche, ma da sequenze video. In questo modo si ottengono i parametri del movimento allo scopo, tra gli altri, di favorire il montaggio di oggetti sintetizzati al calcolatore all'interno di riprese cinematografiche del reale.

Una interessante osservazione da fare riguarda i punti di controllo, detti "Tie Points", che questa generazione di programmi ottengono per collimazione automatica, tramite pattern matching, ovvero riconoscimento statistico della conformazione delle maschere di pixel da un fotogramma all'altro. Un primo vantaggio dell'uso di sequenze video è che l'elevato numero di fotogrammi porta come conseguenza positiva una minore differenza tra le immagini, e quindi un più facile riconoscimento dei punti, che risultano solo "slittati" di modeste quantità.

Ma il secondo vantaggio è che l'elevato numero di Tie Points forma una nuvola di punti nello spazio che già di per sé costituisce una sorta di "rilievo" dell'oggetto, risultando simile ad un rilievo laser, anche se meno dettagliato.

4 Descrizione Matematica della Restituzione Prospettica

Il processo di formazione dell'immagine deve essere modellato in maniera rigorosamente matematica. Il più generale modello di camera è quello conosciuto come proiezione centrale. Un punto 3D è proiettato sul piano immagine dalle linee dei raggi visivi. Il corrispondente punto immagine è l'intersezione del piano immagine con i raggi visivi partenti dal centro ottico ed il punto 3D.

4.1 La trasformazione di Helmert

Partendo da un classico metodo di trasformazione, cercheremo di seguire l’evoluzione degli algoritmi di calcolo dei parametri della Restituzione Prospettica.

Secondo quanto sostenuto da Beinat [8]: "Nelle discipline del rilievo, il modello per eccellenza, è la trasformazione di similitudine rappresentata dalla formulazione di Helmert." In essa, il calcolo della deformazione di due forme ritenute simili, in partenza, è ottenuto tramite la minimizzazione della somma dei quadrati delle distanze tra i punti omologhi delle due figure, quella iniziale e quella finale. In sostanza, con un metodo di iterazione ai minimi quadrati, si ottiene la matrice di rototraslazione che porta da una figura A ad una figura B.

In sostanza si ottengono: Fattore di Scala S, Traslazione T, Matrice di Rotazione R, ed i valori di scarto tra i punti omologhi. Questa tecnica viene comunemente usata nelle trasformazioni di coordinate tra diversi sistemi geografici.

Il primo passo nell’implementazione dell’algoritmo di Helmert e’ quello di sovrapporre le due figure piane costituite dai punti di Origine e quelli di Destinazione basandosi sui loro baricentri. Vengono, quindi, calcolati i coefficienti della matrice di rototraslazione.

La trasformazione di Helmert, comunque, può determinare una deformazione dell'ortogonalità degli assi e non può essere usata nel caso della restituzione prospettica.

4.2 La definizione degli angoli di rotazione

Una attenzione particolare va posta nella espressione della matrice di rotazione, in quanto non esiste un metodo unico per definire gli angoli, ma questi dipendono dalla priorità che si sceglie negli assi che fungono da "cardine". Possiamo, infatti definire prima una rotazione intorno ad X, poi una intorno a Y e poi una intorno a Z; ma possiamo anche definire, invece, prima una rotazione intorno a Z, poi una intorno a X e poi di nuovo una intorno a Z . In totale, possono essere definiti 24 tipi diversi di rotazione, intorno a tutti e tre, o intorno soltanto a due assi, di cui uno ripetuto nella permutazione; in "GraphicsGems" [9] sono definiti tutti i tipi di rotazione possibile. Una di queste rappresentazioni è di particolare importanza ed assume il nome di "angoli di Eulero". A seconda della disciplina in cui viene applicata, la rotazione intorno ad un certo asse può prendere un nome diverso; in generale, chiameremo Rollio la rotazione intorno all'asse Y; chiameremo Beccheggio la rotazione intorno all'asse X; Imbardata o Sbandamento sarà la rotazione intorno all'asse Z.

Tuttavia, la rappresentazione tramite gli angoli di Eulero, anche se intuitiva, risulta essere di difficile utilizzo. E' infatti molto più utile la rappresentazione tramite una matrice contenente i valori di Seno e Coseno degli angoli.

Sempre secondo Beinat, "Oggigiorno per di più è invalsa la tendenza a considerare le matrici di rotazione direttamente nella loro forma naturale, rappresentata dalle componenti esplicite, proprio come è gestita nella memoria del calcolatore. Raramente c'è la necessità di 'estrarre' il valore degli angoli di Eulero celati nel valore delle componenti di una matrice."

4.3 La soluzione dei Punti di Fuga

Una prima implementazione del programma di restituzione fotogrammetrica è basata sulle leggi prospettiche della geometria descrittiva. Tale approccio lega l’algoritmo alla restituzione di oggetti scatolari, e figure ad angoli retti.

In sostanza, vengono calcolati i punti di fuga delle rette a cui appartengono gli spigoli di una rettangolo rappresentato nell’immagine, e tramite i primi due punti di fuga viene calcolato il terzo, determinato attraverso il centro dell’immagine, che è geometricamente l’ortocentro del triangolo delle fughe. Una volta determinato il triangolo delle fughe, viene calcolata la focale, ovvero la scala, dell’immagine.

Si passa quindi a restituire i punti del rettangolo, con una semplice proporzione tra triangoli simili.

Questo procedimento restituisce il rettangolo in una scala determinata da una distanza dal punto di vista fissata ad 1. A questo punto si può scalare il rettangolo, imponendo la misura reale di un suo lato. Si calcola il rapporto di scala ed il fattore 1 viene sostituito da questo nuovo valore. Continuando ad inserire le coordinate immagine dei punti ed indicando il piano a cui esso appartiene, ovvero i punti di fuga, il programma calcola le coordinate del punto nello spazio, legandolo al punto precedente.

Nel caso in cui il poligono che si sta ricostruendo è un rettangolo, parallelo agli assi, possono essere restituiti automaticamente anche tutti i punti immagine contenuti in esso, tramite un algoritmo basato sulla omologia e su una suddivisione dicotomica.

Infatti, si impone, sul rettangolo reale, una griglia determinata da un valore di copertura ritenuto accettabile e si divide il rettangolo a metà. Si continua la suddivisione, sempre a metà, della sua parte in alto a sinistra. Quando questo procedimento raggiunge il valore di risoluzione imposto, si calcola la stessa griglia sul poligono immagine corrispondente al rettangolo, suddividendo il poligono a sua volta a metà, però proiettando le rette secanti verso i punti di fuga. Si ottiene così la griglia prospettica, in cui i punti corrispondono a quelli della griglia del rettangolo reale. A questo punto si leggono dall’immagine i punti, in termine di valori colore, e trasferiscono questi valori verso i corrispondenti punti del rettangolo reale, archiviandoli in un file immagine, legato al rettangolo.

Come già sottolineato, questo algoritmo restituisce solo oggetti scatolari o riconducibili a parallelepipedi. La parte principale di questo algoritmo è riportata nella Appendice B.

4.4 L' Algoritmo Ricostruttivo di "Facade"

Nel programma "Facade", realizzato da Paul Debevec nel Computer Science Division della University of California a Berkeley [2], viene usato un algoritmo di ottimizzazione dei parametri del modello e le posizioni della camera per rendere il modello conforme agli spigoli osservati nelle immagini.

L'algoritmo usa anche una procedura di stima iniziale a due tempi, che calcola automaticamente una stima delle posizioni della camera e i parametri del modello, stima che sia vicina alla soluzione corretta; questo rende la ottimizzazione non lineare fuori del minimo locale e facilita una convergenza.

4.4.1 La Funzione Obiettivo

L'algoritmo ricostruttivo di "Facade" lavora minimizzando una funzione obiettivo O che somma le disparità tra gli spigoli proiettati del modello e gli spigoli marcati nelle immagini, O = ∑Err , dove Err rappresenta la disparità calcolata per ogni spigolo.

Così, i parametri incogniti del modello e le posizioni della camera sono calcolati minimizzando O rispetto a queste variabili.

5 Verso la soluzione SVD

Stima dell’omografia Immagine -> Oggetto [13].

Nel caso di una fotocamera non calibrata, una stima accurata dell’omografia tra i piani dell’immagine e dell’oggetto può essere raggiunta attraverso una serie di punti conosciuti corrispondenti immagine-oggetto.

Da ogni coppia di punti corrispondenti immagine-oggetto possiamo estrarre due equazioni che sono lineari negli elementi della matrice H. Essi sono:

h11x + h12y + h13 = h31xX + h32yX + h33X

h21x + h22y + h23 = h31xY + h32yY + h33Y

Per n corrispondenze otteniamo un sistema di 2n equazioni in otto incognite. Se n=4 si ottiene una soluzione esatta. Altrimenti, se n>4, la matrice è sovra-determinata, e H è stimato da uno schema di minimizzazione.

La soluzione è ottenuta usando il metodo della Singular Value Decomposition (SVD).

Questo metodo minimizza un errore algebrico che non ha un significato geometrico. E’ buona pratica impiegare questo metodo per ottenere una buona soluzione iniziale e, successivamente eseguire una minimizzazione non-lineare per rifinire la soluzione tramite la riduzione di un più significativo errore geometrico.

Descrizione del metodo SVD:

Ogni matrice a m x n (m >=n) può essere scritta come prodotto di una matrice u m x n “column-orthogonal”, una matrice diagonale n x n con elementi positivi o zero, e la trasposta di una matrice ortogonale v n x n.

Cioè:

A = u W v^t

dove:

e:

Gli elementi della diagonale della matrice W sono i Singular Values della matrice A e numeri non negativi.

REFERENCES:

[1] V.Franco – M.Lo Brutto “Elementi di Fotogrammetria Digitale” Università degli Studi di Palermo - Dispenza del corso di Topografia- Maggio 2003

[2] P. E. Debevec. “Modeling and Rendering Architecture from Photographs”. PhD thesis, University of California at Berkeley, Computer Science Division, Berkeley CA, 1996. http://www.debevec.org/Thesis.

[3] R.Seidl, T.Reinhardt, “Canoma User Guide” – MetaCreations 1998

[4] C. Bräuer-Burchardt , K. Voss - Digital Image Processing Group, Friedrich-Schiller-University - “Facade Reconstruction of Destroyed Buildings Using Historical Photographs”, 2000

[5] R.Cantoni, G.Vassena, C.Lanzi “FROM THE SURVEY TO THE 3D ANIMATION: THE SANTA MARIA IN SOLARIO CHAPEL IN BRESCIA” - University of Brescia, Civil Engineering Dep. – 2000

[6] Frank A. van den Heuvel -“RECONSTRUCTION FROM A SINGLE ARCHITECTURAL IMAGE FROM THE MEYDENBAUER ARCHIVES” - Delft University of Technology, Department of Geodesy Delft – 2001

[7] V. Gergely - “CAMERA MATCHING IN COMPUTER GRAPHICS” - Master’s Thesis Budapest University of Technology and Economics - 2003

[8] A. Beinat - "Tecniche di Analisi Procustiana e Trasformazioni di Datum in Topografia e Fotogrammetria" - Tesi di Dottorato Politecnico di Milano, 2000

[9] K. Shoemake, "Graphics Gems IV", Academic Press, 1994

[10] U.Neumann et al.- “Approaches to Large-Scale Urban Modeling” – University of Southern California, 2003

[11] J.E. Eaton, “GNU Octave Reference Manual” - Network Theory Ltd. , 1997

[12] S. Huot , Ch. Colin - “MARINA: 3D Reconstruction from Images using Formal Projective Geometry”- Department of Computer Science. École des Mines de Nantes France

[13] A. Criminisi - “Accurate Visual Metrology from Single and Multiple Uncalibrated Images” SPIN Springer's Computer Science - April 30, 2001

[14] R. Angeletti - "ExportToCanoma" - http://exporttocanoma.blogspot.com - Marzo 2004

[15] R. de Rubertis - "Il Disegno Elettronico" - Edizioni Kappa - 1979

[16] R. de Rubertis - "Computer Graphics - Ricerche ed Applicazioni del Laboratorio di Disegno Automatico" - Facoltà di Architettura 1985

PDF version of this post