Appunti di 3d modelling and mapping from drone images

Appunti di 3D modelling

Indice

Indice generale

• Least squares adjustment...................................2
• Test statistici.....................................................15
• Formula della rotazione da 2D a 2D.............4
• Foto digitale.....................................................16
• Linearizzazione.............................................4
• Differenze tra foto digitale e foto analogica16
• Overparametrization......................................5
• Differenti risoluzioni:..................................16
• Analitical Fotogrammetry..................................6
• Miglioramento delle immagini....................16
• Processo fotogrammetrico.............................6
• Appunti primo lab............................................17
• I due sistemi di coordinate............................6
• Appunti secondo lab........................................19
• Equazione di colinearità................................6
• Image Sharpening............................................20
• Colinearity equation...........................................8
• Sharpen Sharpening....................................20
• Rototraslazione..............................................8
• Variance based henancement.......................20
• Cardan Angles...............................................9
• Wallis operator............................................21
• Nadiral acquisition........................................9
• Riconoscitore di angoli...............................21
• Modello della camera....................................9
• Resampling..................................................22
• Prova della equazione di colinearità...........10
• Image Piramid.............................................22
• DLT.............................................................11
• Come trovare punti interessanti.......................23
• Fotografare un piano...................................12
• Tie points matching..........................................24
• Caso normale...............................................12
• Relational Matching....................................25
• Come orientare foto.....................................14
• Quali sono i prodotti finali?.............................26
• Self calibration vs pre calibration...............14
• Appunti lab 2 parte 2.......................................26
• Brown model...............................................15

Least squares adjustment

Cominciamo con un fatto: Ogni osservazione è soggetta ad un errore. Quindi per ogni A=∗v AX X osservazione (o per ogni gruppo di osservazioni) possiamo scrivere: con X la verità, XA=Y ∗eY la quantità misurata, e v l’errore. Passando attraverso un modello possiamo riscrivere, dove (spero) di generare un errore e minore dell’errore iniziale v.

Bisogna inoltre ricordare che l’errore (almeno stimato) è una parte fondamentale della misura, perché altrimenti le misure non hanno senso (lungo 20 cm +- 1 m ha senso, ma non serve a nulla).

Il modello serve, innanzitutto, per ipotizzare quanto è il segnale e quanto è l’errore. Il modello del segnale è deterministico (almeno nell’approccio minimi quadrati), mentre il modello dell’errore è stocastico (e non potrebbe essere diversamente, essendo una quantità ignota). Modello deterministico significa che ‘ho la presunzione di affermare che’, dato un input conosco perfettamente l’output. Inoltre, nei minimi quadrati, il modello deterministico è lineare (ossia la funzione è ottenibile grazie ad una somma dei parametri).

Modello lineare significa che =C ∗X +C ∗X +...+C ∗X (valida Y per la a° incognita) che può essere riscritto come a 1 a;1 2 a;2 N a;N sistema Y=A*X. (Vettore dei risultati= vettore dei parametri * matrice delle misure).

Il rumore/errore è definito attraverso una distribuzione di probabilità, descritta da una funzione, e il set dei suoi parametri, il tutto connesso tra di loro. L’approssimazione fatta è che il rumore sia univocamente descritto da media e da varianza (ossia sia distribuito gaussianamente). La media viene assunta pari a zero, perché una media non nulla può essere rimossa deterministicamente.

Nella maggioranza dei casi noi abbiamo molti più dati (equazioni) dei parametri (incognite) del problema. Per questo dobbiamo definire una metrica per scegliere la parametrizzazione migliore. Il metodo utilizzato è la minimizzazione della somma dei quadrati degli errori commessi dalla parametrizzazione scelta. In astratto da solo questo indicatore porterebbe alla generazione di un processo iterativo (trovo una soluzione, calcolo gli errori, calcolo l’indicatore, finisco se sono soddisfatto, altrimenti ho solo perso tempo e cerco un’altra soluzione…). Per fortuna esiste un’alternativa molto migliore, permessa unicamente da questo indicatore, e solo per problemi lineari. Con questo “trucco matematico” posso calcolare immediatamente la soluzione ottima, oltre che il suo errore.

Σ² 2 t= (Y −(a∗X +b)) =(Y −(beta∗X )) ∗(Y −(beta∗X )) E i i

Il problema di sta roba è che non dipende dall’errore, potrei ignorare la varianza degli errori, e tutto andrebbe bene uguale. Quindi devo far rientrare dalla finestra Q (matrice di covarianza) modificando la formula facendo pesare di più i dati con minore varianza (quindi più corretti).

2(Y −(a∗X +b))Σ −1² ti i= =(Y −(beta∗X )) ∗Q ∗(Y −(beta∗X )) E q i

Ora, il gioco è trovare il minimo di questa funzione che trasforma n variabili in un singolo numero. Essendo una funzione di forma nota, ossia una parabola in nD, che ammette solo un minimo e nessun massimo, io posso calcolare la “derivata in nD”, trovare dove essa vale 0, e avrò trovato le coordinate perfette.

−1 −1 −1t t=( ) ∗A ∗(Y −b) A è la matrice delle X. X A Q A Q

Questa cosa però non mi basta. Ho bisogno anche della variabilità dei dati, ossia di una stima dell’errore commesso. Questa stima la posso ottenere producendo la matrice di covarianza delle incognite. Per calcolarla posso utilizzare ancora gli errori commessi dal modello, infatti, dal momento che considero il modello come giusto a priori (deterministico), la sola possibile fonte di errore sono le misure.

Cominciamo a calcolare la varianza degli errori, come −1t ∗Q ∗E1 EΣ 2∗ ( −media ( =var= E E))i− −dati para dati para

Il numero di errori è pari al numero di dati, mentre il numero di parametri mi serve di sottrarlo perché ho già usato n dati per calcolarmi i parametri stessi.

La varianza degli errori dovrebbe essere simile alla precisione dello strumento utilizzato (varianza a posteriori = varianza a posteriori). Se la varianza degli errori risulta molto elevata significa che ci sono dei problemi:

• Lo strumento funziona male
• Il modello è errato
• Qualche dato è errato (essi sono gli outliers, e sono i valori con l’errore associato più alto, che vanno rimossi)

Test statistici

Come so se sono contento della media? Test statistici (aggiungere un alfa, tipo 5%)

Test di uguaglianza tra varianze (di cose gaussiane normali e scorrelate): ki quadro

Questo confronto mi serve per vedere se il modello è corretto (e quindi se il mio modello è corretto, lo strumento funziona bene, non sono commessi errori e) se la varianza degli errori è uguale alla varianza a priori.

Test di uguaglianza tra medie (di variabili gaussiane indipendenti di varianza calcolata) (quindi il valore che ho misurato 100 volte, posso dire che abbia per media quello che spero?), t di student.

Cosa interessante, la variabilità degli errori dipende sia dallo strumento, sia dalle misure che vengono effettuate (e dal come vengono effettuate), ed è qui che dovremmo servire noi. Nello specifico, matrici delle X (anzi, della matrice N=Xt*X) (dove prendiamo i dati) con determinante basso (valori vicini fra loro) generano più variabilità nei risultati (quindi male).

La varianza (singola variabile) è sempre positiva. La matrice di covarianza (molte variabili) è definita positiva. Per dimostrarlo basta che il determinante della matrice sia maggiore di 0. Di solito la matrice di covarianza è definita come un fattore (uguale alla precisione supposta dello strumento) moltiplicato per una matrice (n° oss x n° oss), spesso presa uguale alla matrice identità (le osservazioni sono indipendenti e di pari varianza). Inoltre la matrice di covarianza è simmetrica (quindi lo è anche la sua inversa)!

La matrice di covarianza è il metodo che serve per pesare l’affidabilità dei dati. Tanto più la varianza di un dato sarà alta rispetto a quella di tutti gli altri, tanto meno quel dato sarà affidabile.

Precisione= variabilità delle misure. Accuratezza = correttezza della media

• Accurate Non accurate
• Misure coincidenti al valore corretto Misure coincidenti ad un valore errato
• Precise Misure molto disperse attorno al valore corretto Misure molto disperse attorno ad un valore
• Non precise sbagliato

Formula della rotazione da 2D a 2D

Il sistema X Y è il sistema ruotato di alfa a partire dal sistema originario x y.

=x∗cos(α )− (α ) =x∗sin (α )+ )X y∗sin Y y∗cos(α

L’equazione di rotazione è deterministica, è lineare nelle incognite, ma non nel parametro alfa!

Per determinare i parametri io devo utilizzare “double points”, ossia punti le cui coordinate siano note in due sistemi di riferimento. Nello specifico dell’esercizio io ho bisogno di n coppie di coordinate X;Y e x;y, in maniera da poter scrivere almeno 1 equazione (avendo 1 incognita, alfa, anche se vedremo che le cose sono più complesse). Nello specifico io ho bisogno di almeno 1 punto (per avere un sistema risolvibile), ma meglio averne di più (2, 3, 5) per evitare problemi di outliers, anche se meglio non esagerare.

Ora proviamo a scrivere il sistema con i minimi quadrati, avendo 3 double points.

Y=[X1 Y1 X2 Y2 X3 Y3}, beta =[alfa], X=[Matrice 6x1 che non posso scrivere! Il sistema non è lineare in alfa]

Ok, posso prendere tutta la teoria dei minimi quadrati e buttarla via! Oppure…

Linearizzazione

Esistono due metodi per risolvere questo problema, ossia usare l’approccio minimi quadrati per risolvere problemi con equazioni non lineari (ricordo che altrimenti dovrei semplicemente procedere per tentativi ed errori nel calcolo della soluzione buona, non avendo idea di come trovare quella ottima). Il primo di tali metodi è la linearizzazione della funzione. Essendo f(x) una funzione qualsiasi, anche non lineare, come nel caso di sopra, essa può essere linearizzata, con un certo grado (di affidabilità, nell’intorno del punto P, come Taylor insegna, ossia l( x)=f P)+ f ’( P)∗( x−P). Si noti che, a patto di saper calcolare la derivata di f nell’intorno del punto p, la funzione l(x) è lineare succeda quel che succeda (essendo f(p) e f’(p) dei numeri). Per linearizzare però devo conoscere un punto iniziale, ossia P. Come fare a conoscere P? Sembra un gatto che si morde la coda, visto che per conoscere correttamente la soluzione (valore di x che ottimizzi i minimi quadrati) dovrei conoscere un valore approssimato della soluzione stessa…

Ma se io avessi un modo, partendo da una parte dei dati, di calcolare un valore approssimato (magari scrivendo un sistema isodeterminato) potrei partire da quel valore, e vedere di avvicinarmi un poco al valore ottimo attraverso la linearizzazione.

Quindi, nell’esempio, f(α) non è lineare, ma a partire da un punto posso calcolare un α stimato (che chiamerò β), e poi scrivere la linearizzazione come: l(x)=f(β)+f’(β)*(x-β).

=x∗cos( ( =x∗sin (f(β): X β)− y∗sin β;) Y β)+ y∗cos( β)

=−x∗sin ( =x∗cos( (f’(β): X β)− y∗cos( β;) Y β)− y∗sin β;)

(ricordo infatti che derivata di cos è -sen, e derivata di sen è cos, entrambe vanno moltiplicate per la derivata dell’argomento della funzione, in questo caso pari a 1). Essendo β noto ed avendo 3 double points (ognuno dotato di proprie coordinate x;y e X;Y) posso scrivere 3 coppie di equazioni di questo tipo:

=x ∗cos( ∗sin ( ∗sin ( ∗cos(X β)− y β)+[−x β)− y β)]∗(α−β;)1 1 1 1 1

=x ∗sin ( ∗cos( ∗cos( ∗sin (Y β)+ y β)+[ x β)− y β)]∗(α−β;)1 1 1 1 1

Avendo un valore di beta, posso riscrivere il sistema nell’incognita Δ alfa = α – β, rendendolo così un sistema di 6 equazioni lineari, riscrivibile in forma matriciale come: Y=B*X+C, con Y= vettore colonna delle X e delle Y, B= numero Δ α, incognito, X= vettore colonna delle 6 derivate, C= vettore colonna delle 6 costanti.

Questo sistema di 6 equazioni in 1 incognita può essere risolto mediante i minimi quadrati. Tuttavia non è definito un metodo per sapere se si è arrivati alla soluzione ottima del problema (certamente si è in un ottimo locale, ma sarà anche quello globale? Dipende). Per avere questa informazione posso iterare il processo di linearizzazione, stavolta attorno al valore ottenuto. E quando finisco? In tre casi:

• Quando l’errore commesso è sufficientemente basso
• Quando le soluzioni stanno andando a convergere (è inutile iterare 100 volte per avere alfa al millesimo di gon se uso un goniometro). Per questo mi serve una metrica di distanza.
• Un’interruzione a forza bruta oltre n tentativi fa sempre comodo

Ovviamente ancora non so se sono arrivato davvero al meglio possibile (potrei solo essere in una valletta piccola), ma le funzioni che usiamo sono tendenzialmente semplici, quindi questo problema non si pone.

Overparametrization

Questo è l’altro metodo per risolvere equazioni non lineari. Esso consiste nel creare artificialmente incognite nuove, funzione dei parametri incogniti, allo scopo di rendere lineare il sistema. Nel caso del sistema in oggetto io posso definire due parametri incogniti, ossia a=sen(alfa) e b=cos (alfa), e riscrivere le equazioni precedenti come funzione di questi parametri: X=x*a-y*b e Y=x*b+y*a, e da qui scrivere un sistema di 6 equazioni lineari (è questo il gioco) costituito da Y= [X1 Y1 X2 Y2 X3 Y3], beta=[a, b], X= [x y ; y x ; x y ; y x x y ; y x ].1 1 1 1 2 2 2 2 3 3 3 3

Ora il problema è lineare, quindi posso risolvere il problema coi minimi quadrati trovando a e b, ma alla fine io voglio tornare al problema di partenza, trovando alfa. Per farlo devo scrivere una funzione apposta, che cambia in funzione del problema, e che leghi le incognite reali a quelle matematiche definite. In questo caso la funzione è semplice: alfa= arco tangente(b/a), ma potrebbe non esserlo. Inoltre io devo scoprire come la varianza dei risultati (che conosco per le incognite create) si trasmette all’incognita fisica.

Per sapere come la covarianza delle variabili algebriche (quelle generate per linearizzare il problema) si trasmette nella covarianza delle variabili fisiche (quelle in cui il problema non è lineare) devo effettuare la propagazione della covarianza. Il problema è che la funzione che lega le variabili fisiche a quelle algebriche non è lineare (se lo fosse non avrei alcun bisogno di variabili algebriche e non starei facendo tutto questo), e quindi non posso sapere come varia esattamente la varianza. E questo sarebbe un altro ciclo infinito, se non fosse che, come nel caso precedente, posso linearizzare le funzioni, questa volta una volta sola, attorno al valore calcolato delle variabili algebriche, e da li effettuare la propagazione della varianza per una funzione lineare. Nel caso specifico…

(a (aD f , b) Df , b)=alfa+ ( (Y x−alfa)+ x−alfa)Da Db

In sostanza questa linearizzazione porta l(alfa) ad essere una somma di tre costanti più due termini in x che dipendono dalle derivate. Definisco la matrice J come matrice 2x1 contenente le due derivate, la matrice X come matrice 1x2 [a, b], ho che: l(alfa)=J*X+C. Avendo la matrice di covarianza di X (a e b sono risultati di un minimi quadrati normale, quindi non ho problemi ad averla) e chiamandola Q, so che la propagazione della covarianza si comporta così:

t(var y)=J∗Q∗J (se J fosse un numero solo, quindi singola variabile, la formula sarebbe ²( ) ∗var ( come ha senso).var y J x)

Ultima cosa importante sulla overparametrizzazione è l’inserimento di limiti sui parametri (per esempio se overparametrizzo troppo e due variabili algebriche sono dipendenti). In questi casi posso ‘chittare’ il metodo, inserendo una o più osservazioni false, ossia una o più equazioni che leghino i parametri dipendenti fra di loro. Queste operazioni avranno, nella matrice di covarianza, una varianza molto più bassa delle altre, rendendo così il loro soddisfacimento molto più rilevante rispetto al soddisfacimento degli altri vincoli (non posso inserire varianze nulle per motivi logici e matematici, ma se, come spesso accade, pongo Q=I (matrice quadrata con 1 sulla diagonale e 0 altrove, azione che indica il fatto che le osservazioni sono scorrelate fra loro, e di uguale varianza, assunzione logica visto che sono fatte con lo stesso strumento), posso aggiungere una riga e una colonna di 0, e magari 10^(-5) sulla diagonale aggiunta. Il vincolo non sarà rispettato matematicamente, ma con una precisione molto maggiore del previsto.

In sostanza l’overparametrizzazione è un metodo più veloce della lin