Subsections

Determinazione delle matrici

La matrice Essenziale si può ricavare in forma chiusa conoscendo le pose relative tra i sensori e, con la conoscenza dei parametri intrinseci delle camere coinvolte, è possibile ottenere la matrice Fondamentale.

L'applicazione però più diffusa della matrice Essenziale (o Fondamentale) è quella di ricavare la posa relativa tra le camere, data la conoscenza di un elenco di punti omologhi: conoscendo i parametri intrinseci si può ricavare la matrice Essenziale (e da questa ricavare la matrice Fondamentale) o senza nessuna conoscenza dei paramtri delle camere poter ricavare la matrice Fondamentale.

Algoritmo degli 8 punti

Il criterio per ottenere la matrice $\mathbf{F}$ si può formalizzare come una minimizzazione di una funzione costo

\begin{displaymath}
\min_\mathbf{F} \sum_{i=1}^n \left( \mathbf{p}^{\top}_{2,i} \mathbf{ F } \mathbf{p}_{1,i} \right)^2
\end{displaymath} (9.47)

sotto ulteriori vincoli che riguardano questa volta la struttura di $\mathbf{F}$.

Si può notare che il vincolo epipolare (9.43) può essere riscritto anche come

\begin{displaymath}
(\mathbf{p}_1 \otimes \mathbf{p}_2)^{\top} \text{vec}(\mathbf{F}) = 0
\end{displaymath} (9.48)

avendo sfruttato la sintassi compatta offerta del prodotto di Kronecker $\otimes$ o alternativamente
\begin{displaymath}
\mathbf{u}_i \mathbf{f} = 0
\end{displaymath} (9.49)

in forma più esplicita definendo
\begin{displaymath}
\begin{array}{rl}
\left( \mathbf{p}_1 \otimes \mathbf{p}_2 \...
...,3} ,
f_{3,1} , f_{3,2} , f_{3,3}
\right)^{\top}
\end{array}\end{displaymath} (9.50)

con $\mathbf{p}_{1,i}=(x_1,y_1)$ e $\mathbf{p}_{2,i}=(x_2,y_2)$. Con questo formalismo è possibile mettere in evidenza una tecnica che permette di ricavare gli elementi di $\mathbf{F}$ come soluzione di un sistema lineare omogeneo formato da vincoli come in equazione (9.49).

Raccolti tutti i vincoli $\mathbf{u}_i$, si ottiene un sistema omogeneo del tipo

\begin{displaymath}
\mathbf{U} \mathbf{f} = 0
\end{displaymath} (9.51)

di $n$ equazioni in 9 incognite.

Per ricavare la matrice Essenziale il discorso è analogo ed è soluzione di un sistema $\mathbf{n}_i \mathbf{e}=0$ nella forma

\begin{displaymath}
\begin{array}{l}
\mathbf{n}_i = (
x_{1} x_{2}, y_{1} x_{2...
..._{2,2} , e_{2,3} ,
e_{3,1} , e_{3,2} , e_{3,3}
)
\end{array}\end{displaymath} (9.52)

con $\mathbf{m}_{1,i}=(x_1,y_1,z_1)$ e $\mathbf{m}_{2,i}=(x_2,y_2,z_2)$. Con tutti i vincoli $\mathbf{n}_i$, questo è un sistema omogeneo del tipo
\begin{displaymath}
\mathbf{N} \mathbf{e} = 0
\end{displaymath} (9.53)

Di fatto, usando le coordinate omogenee, i sistemi (9.50) e (9.52) sono equivalenti dal punto di vista algoritmico.

Ai vincoli espressi in questi sistemi omogenei, ne va sempre aggiunto uno ulteriore, per esempio $\Vert \mathbf{f} \Vert =1 $, normalmente già soddisfatto dai risolutori lineari di sistemi omogenei. Questo algoritmo è pertanto chiamato eight-point algorithm in quanto la soluzione del problema richiede almeno 8 punti per essere determinata. Ulteriori vincoli, per raggiungere gli effettivi gradi di libertà delle matrici, non sono invece esprimibili sotto forma lineare.


Rafforzamento dei vincoli

A causa del rumore, normalmente le matrici ottenute dal sistema lineare non soddisfano il requisito che siano di rango 2 (e nel caso di matrice Essenziale, perciò con un ampio numero di gradi di libertà, che non appartengano proprio al sottospazio delle matrici Essenziali). Una possibile soluzione a questo problema è quella di cercare la matrice più vicina a quella restituita dal sistema lineare che soddisfa però il vincolo sul rango. Tale risultato si ottiene per esempio usando una decomposizione SVD seguita da una composizione, come suggerito da Tsai, Huang e Hartley:

\begin{displaymath}
\begin{array}{rl}
\mathbf{F} &= \mathbf{U}\diag (r,s,t)\ma...
...bf{F}' &= \mathbf{U}\diag (r,s,0)\mathbf{V}^{\top}
\end{array}\end{displaymath} (9.54)

Questo procedimento è chiamato constraint enforcement. La matrice Essenziale rispetto a quella Fondamentale ha in più il vincolo di avere i 2 valori singolari non nulli uguali:
\begin{displaymath}
\begin{array}{rl}
\mathbf{E} &= \mathbf{U}\diag (r,s,t)\ma...
...bf{E}' &= \mathbf{U}\diag (1,1,0)\mathbf{V}^{\top}
\end{array}\end{displaymath} (9.55)

Se i valori singolari (in seguito a una SVD) della matrice sono 1, la matrice si dice matrice Essenziale normalizzata (normalized essential matrix). La matrice Essenziale ottenuta ponendo $\mathbf{D}' = \diag (1, 1, 0)$ è la matrice essenziale normalizzata più vicina a quella data, in accordo con la norma di Frobenius. La matrice Essenziale generata attraverso l'equazione (9.55) soddisfa la cubic trace-constraint (Demazure, 1988)
\begin{displaymath}
\mathbf{E}\mathbf{E}^{\top} \mathbf{E} - \frac{1}{2} \trace \left( \mathbf{E}\mathbf{E}^{\top} \right) \mathbf{E} = 0
\end{displaymath} (9.56)

Tale vincolo è condizione necessaria perchè la matrice in analisi sia effettivamente Essenziale.

Le matrici ottenute attraverso questo procedimento di rafforzamento soddisfano tutti i requisiti per essere matrici Fondamentali o Essenziali, ma non rappresentano una minimizzazione algebrica, ne tantomento geometrica, dei vincoli originali.

Algoritmo dei 7 punti

Gli algoritmi che sfruttano meno di 8 punti per estrarre una matrice Essenziale o Fondamentale si basano più o meno tutti sullo stesso principio: viene estratto il kernel multidimensionale di $\mathbf{U}$ o $\mathbf{N}$, visto che la matrice Fondamentale o Essenziale deve appartenere a un elemento di questo spazio, e vengono forzati alcuni vincoli tipici del problema in questione.

In maniera non lineare è relativamente facile poter ottenere una matrice Fondamentale con soli 7 punti, considerando il fatto che la matrice $\mathbf{U}$, formata dagli elementi di equazione (9.50), deve essere di rango 7, in quanto 7 sono in effetti i gradi di libertà della matrice Fondamentale. Risolvendo il sistema (9.50) formato da (almeno) 7 punti si ottiene un sottospazio di dimensione 2, formato da due basi $\mathbf{f}_1$ e $\mathbf{f}_2$, a cui sono associate due matrici $\mathbf{F}_1$ e $\mathbf{F}_2$: nello spazio delle possibili soluzioni è necessario trovare una matrice $\mathbf{F} = \alpha \mathbf{F}_1 + (1 - \alpha) \mathbf{F}_2$ tale che abbia rango 2 ovvero imponendo $\det \mathbf{F} = 0$, equazione non lineare di terzo grado in $\alpha$. In questo caso le soluzioni reali di $\alpha$ possono essere 1 o 3: nel caso di 3 soluzioni reali, vanno tutte e 3 valutate sui dati per individuare quella più plausibile.

Algoritmo dei 5 punti

Con meno di 7 punti esistono solo algoritmi per determinare la matrice Essenziale. La matrice Essenziale infatti è formata da soli 5 gradi di libertà e in linea teorica può essere stimata attraverso l'analisi di corrispondenze fra solo 5 punti (Nis04). L'algoritmo dei 5 punti è di fatto lo standard per la stima della matrice essenziale, tuttavia la sua implementazione è estremamente complessa.

Sfruttando solo 5 corrispondenze, la matrice $\mathbf{N}$ del sistema (9.53) ha un difetto 4 di rango. La matrice Essenziale deve essere pertanto formata come combinazione lineare delle ultime 4 colonne della matrice $V$ ottenuta dalla SVD, ovvero:

\begin{displaymath}
\mathbf{E} = x \mathbf{X} + y \mathbf{Y} + z \mathbf{Z} + \mathbf{W}
\end{displaymath} (9.57)

con $\left(\mathbf{X}, \mathbf{Y}, \mathbf{Z}, \mathbf{W}\right)$ ultime 4 colonne di autovettori della matrice $V$ e $(x,y,z)$ incognite. Per ottenere tali incognite è necessario soddisfare i vicoli
\begin{displaymath}
\begin{array}{l}
\det \mathbf{E} = 0 \\
\mathbf{E}\mathbf...
...thbf{E}\mathbf{E}^{\top} \right) \mathbf{E} = 0 \\
\end{array}\end{displaymath} (9.58)

equivalente a un problema di 10 polinomi di terzo grado nelle 3 incognite.

La richiesta comunque di risolvere un sistema non-lineare fa diminiure i vantaggi rispetto alle soluzioni proposte in sezione 9.4.2.

Condizionamento del sistema

La generazione, attraverso tecnica SVD, delle matrici Essenziale e Fondamentale e in seguito l'irrobustimento di queste, forzando i valori singolari ad essere uguali, è un processo molto sensibile al rumore.

La matrice (9.50) è mal condizionata: questo accade quando si cerca di risolvere un sistema lineare i cui termini noti sono formati da numeri con ordini di grandezza differenti. Il metodo proposto da Hartley (Har95) propone di migliorare la soluzione normalizzando le coordinate dei punti.

Le coordinate $\mathbf {p}_1$ e $\mathbf {p}_2$ vengono traslate separatamente in modo da avere centroide nullo e riscalate in modo da avere come valor medio $1$ (o $\sqrt{2}$ valor medio del modulo) nel nuovo sistema di coordinate $\tilde{\mathbf{p}}_1$ e $\tilde{\mathbf{p}}_2$ rispettivamente. Definiamo pertanto due matrici di trasformazione $\mathbf{T}_1$ e $\mathbf{T}_2$ tali che

\begin{displaymath}
\begin{array}{l}
\tilde{\mathbf{p}}_1 = \mathbf{T}_1 \math...
...ilde{\mathbf{p}}_2 = \mathbf{T}_2 \mathbf{p}_2 \\
\end{array}\end{displaymath} (9.59)

in questo modo è possibile determinare la matrice fondamentale compatibile $\tilde{\mathbf{F}}$
\begin{displaymath}
\mathbf{p}^{\top}_{2} \mathbf{ F } \mathbf{p}_1 = \tilde{\m...
...thbf{p}}_2^{\top} \tilde{\mathbf{F}} \tilde{\mathbf{p}}_1 = 0
\end{displaymath} (9.60)

da cui poi ricavare la matrice originale $\mathbf{F} = \mathbf{T}^{\top}_2 \tilde{\mathbf{F}} \mathbf{T}_1$.

Paolo medici
2024-11-07