Una spiegazione completa degli algoritmi di Computer Vision utilizzati in questa applicazione si trova consultando i riferimenti. Qui vengono richiamati i punti principali di interesse in una fase operativa.
Il modello matematico della camera utilizzato è il classico pinhole con skew
zero e centro di proiezione al centro dell'immagine (u0, v0). Così facendo i parametri
intrinseci della camera si riducono a due: Fx ed Fy. Nel nostro caso i
parametri sono Fx ed il rapporto Fy/Fx chiamato aspect
ratio a. La matrice di proiezione K si può quindi scrivere come:
| [ f | 0 | u0 ] |
| [ 0 | a*f | v0 ] |
| [ 0 | 0 | 1 ] |
Si indicano poi con T la translazione della camera e con R
la rotazione. L'equazione di proiezione ricava le coordinate omogenee di un punto sull'immagine
x a partire da un punto nello spazio X in coordinate non
omogenee: x = KRt(X-T)
L'uso di questo modello di camera semplifica la formulazione degli algoritmi, ma non si riesce a
tener conto di eventuali distorsioni radiali delle lenti.
La calibrazione della camera consiste nell'estrarre, a partire dai punti di riferimento letti
sull'oggetto di riferimento, i parametri intrinseci della camera (lunghezze focali) ed i
parametri estrinseci (posizione ed orientamento della camera rispetto all'oggetto di
riferimento).
Ogni richiesta di calibrazione scatena due processi: una prima
calibrazione che fornisce un punto di partenza per un raffinamento dei parametri basato su di un algoritmo di
minimizzazione non lineare.
Per rendere il processo di calibrazione più robusto nei riguardi di errori nella definizione
dei punti di riferimento, si è utilizzata una strategia che ignora a turno uno o più
punti di riferimento mantenendo solo quell'insieme di vertici che soddisfa un certo criterio di
minimizzazione (LMedS).
Per avere una stima iniziale dei parametri della camera si utilizza un algoritmo basato sui
punti di fuga (vanishing points). Questi punti sono quelli dove convergono le immagini degli
spigoli paralleli dell'oggetto di rifierimento. Una volta estratti questi punti, si crea un
sistema di equazioni che li lega due a due attraverso la matrice di proiezione della camera (in
parole povere significa i parametri intrinseci della camera). Questa procedura è ripetuta
fino a convergenza.
La rotazione della camera è poi ricavata dai punti di fuga; non dipendono questi infatti
dalla translazione della camera.
La translazione si ricava da una rapida minimizzazione dell'errore di riproiezione.
In questa fase si riproiettano i punti di riferimento, di cui si conoscono le coordinate 3D, sull'immagine utilizzando i parametri (intrinseci ed estrinseci) calcolati e si ricava l'errore totale come distanza fra questi ed i veri punti marcati sull'immagine. Si utilizza poi una routine di minimizzazione non lineare (Levenberg-Marquardt modificato) per aggiustare i parametri e quindi minimizzare l'errore totale.
Per ottenere una stima robusta, cioè insensibile ai cosiddetti outliners, punti errati, si ripete la procedura per vari sottoinsiemi dei punti di riferimento. Nel nostro caso è possibile creare tutti i sottoinsiemi possibili. Per creare questi sottoinsiemi si eliminano nessuno, uno o due punti. Per ogni insieme di punti si effettua il raffinamento della soluzione e si calcola la mediana degli errori di riproiezione. Si utilizzano quindi i parametri per cui è minimo questo valore.
Per ogni contorno in ogni immagine si estraggono sei piani paralleli ad ognuno degli assi e
tangenti a due a due al contorno.
Per definire un piano sono necessarie due direzioni. Sul piano dell'immagine le direzioni
corrispondono a punti. Tre punti corrispondono alle direzioni dei tre assi. un punto sulla
congiungente due di questi punti individua una direzione contenuta nel piano definito dall due
direzioni. Per definire i piani tangenti basta quindi individuare la retta tangente al contorno e
passante per il punto di fuga (vanishing point) corrispondente and un asse. L'intersezione di
questa retta con la congiungente gli altri due individua la seconda direzione necessaria alla
definizione del piano.
Ogni piano individua un semispazio in cui deve trovarsi l'oggetto da ricostruire. L'intersezione
di questi semispazi definisce un volume di cui un apposito algoritmo (CDDlib) estrae i vertici. Ora per trovare il volume parallelepipedo in cui si
trova l'oggetto basta, per la base, trovare il minimo rettangolo che contiene i punti proiettati
sul piano XY(algoritmo "Minimum area oriented box containing a convex
polygon"), mentre per l'altezza si trovano i valori minimi e massimi di Z.
Il Bounding Box di ogni oggetto è suddiviso in una griglia regolare di spaziatura non
superiore al valore impostato nell'applicazione (Risoluzione). Questi punti sono poi raggruppati
in pilastri; ogni pilastro è composto da tutti i punti con un certo valore di coordinate X e
Y.
Ogni pilastro viene proiettato su ogni immagine e vengono individuate le intersezioni
fra la sua immagine ed in contorno dell'oggetto corrispondente. Questi punti vengono riportati in
3D e viene incrementato il valore associato ai punti interni al contorno. Quando questa
operazione viene ripetuta per tutte le immagini si troverà che i puunti che compongono
l'oggetto avranno dei valori al di sopra di una certa soglia.
Se il valore di Tolleranza è maggiore di zero allora viene considerata una transizione
graduale fra interno ed esterno. Questa banda è larga il numero di pixel impostati da ogni
lato del contorno. In sostanza comunque l'algoritmo non cambia.
Per migliorare la precisione della ricostruzione si devono utilizzare tutti i vincoli a
disposizione. Sono già stati utilizzati tutti quelli che riguardano l'oggetto di
riferimento. Si possono però utilizzare gli oggetti stessi da ricostruire. Un vincolo
riguarda ogni oggetto visto da una coppia di camere. Per ogni camera il cono di vista
dell'oggetto nell'altra camera deve essere tangente al contorno dell'oggetto nella camera in
considerazione.
Nel raffinamento della calibrazione si utilizza questo vincolo, minimizzando l'errore derivante
dalla non tangenza, per aggiustare i parametri delle varie camere una coppia alla volta.
Ovviamente le coppie sono scelte in modo che gli assi delle due camere siano per quanto possibile
perpendicolari.
Un problema intrinseco in questo algoritmo è un problema comune a tutti gli algoritmi di
ottimizzazione globale: la possibilità di cadere in un minimo locale. Per evitare ciò
si utilizza una strategia multistart: al termine di ogni iterazione si perturbano leggermente i
parametri e si fa partire un'altra iterazione. Se il nuovo errore è inferiore allora si
prosegue, se no si scarta il risultato e si perturba di nuovo l'insieme dei parametri
trovati.