Stima della posa della mano
4.2 SCELTA DELL’ALGORITMO DI OTTIMIZZAZIONE
corrente che comporti il massimo decremento del valore del modello della funzio-ne obiettivo. Per modello della funziofunzio-ne obiettivo si intende un’approssimaziofunzio-ne di quest’ultima tramite espansione secondo serie di Taylor troncata in genere al secondo termine. In questo caso il modello si dice quadratico e assume la forma indicata nell’Equazione 4.5
p, xc∈ Rn
f : Rn→ R
mc(xc+ p) , f (xc) + ∇f (xc)Tp + 12pT∇2f (xc)p con pT∇2f (xc)p > 0 (semidefinita positiva)
(4.5)
Gli algoritmi a discesa di gradiente cercano il decremento del modello qua-dratico lungo una direzione discendente a partire dal valore attuale assunto da ogni parametro. Il nome “discesa di gradiente” deriva dalla dimostrabilit`a che la direzione lungo la quale si verifica il massimo decremento `e la direzione oppo-sta alla direzione del gradiente della funzione obiettivo. Pi`u in generale, vale la definizione seguente:
p, xc∈ Rn, kp = 1k, p is descent direction from xc ⇒ ∇f (xc)Tp < 0 (4.6) Gli algoritmi a regione di confidenza sono molto simili agli algoritmi a discesa di gradiente, in quanto differiscono solo per la lunghezza massima del passo di ricerca: i primi cercano il massimo decremento lungo una direzione discendente (non necessariamente la direzione opposta al gradiente) entro una sfera in Rn di raggio limitato, mentre i secondi non hanno un limite sulla lunghezza del passo. Gli algoritmi ibridi, invece, adottano l’una o l’altra strategia a seconda della vicinanza della stima attuale all’ottimo.
Avendo espresso la funzione obiettivo nell’Equazione4.1come somma di quadrati di residui, il problema si configura come un’ottimizzazione ai minimi quadrati. Data la particolare forma della funzione obiettivo, indicata nell’Equazione 4.7, l’algoritmo per l’ottimizzazione `e il metodo di Levenberg-Marquardt. Si tratta di una variante dell’algoritmo di Gauss-Newton per l’ottimizzazione di una generica funzione non lineare con approccio trust-region, e il procedimento ricalca in parte quello impiegato nella soluzione di un sistema di equazioni non lineari.
S(β) =PN
i=1(yi− f (xi, β))2 = kY − F (X, β)k2
dove yi `e la y-esima misura, f (xi, β) il modello della curva funzione dei parametri da ottimizzare, X = [x1, x2, ..., xN]T, Y = [y1, y2, ..., yN]T e F (X, β) = [f (x1, β), f (x2, β), ..., f (xN, β)]T.
(4.7) Per una trattazione approfondita si rimanda a [26, 9], mentre ai fini della motivazione delle scelte effettuate e della comprensione dei risultati illustrati suc-cessivamente si riportano solo alcuni punti fondamentali dell’algoritmo. Il primo riguarda il modello della curva da adattare al vettore delle misure Y, specificato nell’Equazione 4.8.
mc(xc+ β) ,Ni=1 P yi− f (xi, β) − Jiδ)2 = kY − F (X, β) − J δk2 dove Ji `e la i-esima della matrice jacobiana J (ovvero il gradiente) di f (xi, β) e δ il vettore degli incrementi per il vettore dei parametri β.
(4.8)
Ancora pi`u importante `e il calcolo di δ a ogni iterazione, indicato nell’Equa-zione4.9, dove emerge la dipendenza del risultato da un parametro dimensionato nella Sezione4.3.2. Il calcolo consiste nella risoluzione di un sistema di equazioni lineari, e la sua efficienza `e migliorabile applicando alcune tecniche di scomposi-zione delle matrici. Il parametro µ assolve due funzioni: evita la possibile non-invertibilit`a della matrice JTJ e regola indirettamente la lunghezza del passo della trust-region; un suo corretto dimensionamento `e, quindi, indispensabile.
(JTJ + µJTJ )δ = JT[Y − F (X, β)]
dove µ `e il parametro di damping. (4.9)
Il secondo punto fondamentale deriva dalle Equazioni 4.8, 4.9 e riguarda il calcolo della matrice jacobiana, o equivalentemente il calcolo del singolo gradiente della funzione di β. I gradienti calcolati analiticamente, ove possibile, comportano in genere una convergenza rapida al minimo locale; tuttavia, se il calcolo non `e possibile o risulta eccessivamente oneroso, l’approssimazione alle differenze finite `e spesso una valida alternativa ma con il rischio di una convergenza pi`u lenta. Come accennato nella Sezione 4.1.1, a causa dell’impossibilit`a di specificare il modello (intendendo f (xi, β)) analiticamente per via del rendering, non `e stato possibile calcolare il gradiente ma solo approssimarlo alle differenze finite. Nell’Equazione
4.2 SCELTA DELL’ALGORITMO DI OTTIMIZZAZIONE
approssimazione alle differenze in avanti approssimazione alle differenze centrali
Il calcolo di J ∈ Rn×mrichiede per la prima m(n+1) valutazioni della funzione, mentre per la seconda ne richiede il doppio comportando, per`o, una migliore approssimazione.
Ji,j = fi(β+ej∆)−fi(β)
∆ Ji,j = fi(β+ej∆)−fi(β−ej∆) 2∆
a)differenze in avanti b)differenze centrali
dove∆`e la lunghezza del passo di derivazione eejil j-esimo vettore canonico diRm. (4.10) Ai fini del progetto si `e ritenuto opportuno non implementare l’algoritmo nel codice, ma di avvalersi di una sua implementazione di libero utilizzo codificata nella libreria Levmar2.5[20]. Essa si appoggia alla libreria Lapack[2] per il calcolo algebrico efficiente, la quale `e realizzata rispettando le specifiche BLAS[17]. Lev-mar2.5 raccoglie diverse varianti dell’algoritmo di Levenberg-Marquardt, classifi-cabili in base al tipo di dati utilizzato, dal tipo di calcolo della matrice Jacobiana e dall’eventuale tipo di vincoli imponibili. Per chiarezza si riportano qui sotto solamente le caratteristiche principali della libreria.
Tipo di dati
virgola mobile doppia precisione Matrice Jacobiana
analitica
approssimata alle differenze finite – differenze forward
– differenze centrali Tipo di vincoli
nessuno (ottimizzazione unconstrained) lineari (Ax = b)
limiti superiori e inferiori (box constraints)
compresenza di due o pi`u tipi di vincoli precedenti
Il processo di ottimizzazione `e quasi del tutto trasparente al programmatore, infatti, oltre all’impostazione di alcuni parametri dell’algoritmo, `e richiesta so-lamente la specifica di un metodo che calcoli per ogni residuo i-esimo il valore f (xi, β) ed eventualmente un metodo che calcoli il gradiente del modello per ogni residuo.
Un’altra peculiarit`a della libreria riguarda l’approssimazione della matrice jaco-biana alle differenze finite: ove possibile, al posto di ricalcolare l’intera matrice a ogni iterazione, l’implementazione dell’algoritmo impiega l’approssimazione di Broyden, che richiede solo m rivalutazioni della funzione per aggiornare J ma pu`o essere usata al massimo n volte consecutivamente. Per completezza, tale appros-simazione `e riportata nell’Equazione 4.11. Per una trattazione approfondita si rimanda a [8,1].
Jk+1 = Jk+(F (βk+ δk) − F (βk) − Jk∗ δk)δkT
kδkk2 (4.11)
4.3 Calibrazione parametri di ottimizzazione
I risultati dei primi test di ottimizzazione, che consideravano il problema nel-la sua interezza e non comportavano nel-la modifica delle impostazioni di default dell’algoritmo erano, come aspettato, diversi da quelli desiderati. La causa del fallimento era difficile da determinare, data l’elevata complessit`a del problema di ottimizzazione dovuta all’elevato numero di parametri da ottimizzare e di vin-coli da rispettare. Si `e deciso, pertanto, operare una prima semplificazione del problema:
sostituzione delle depthmap acquisite con depthmap sintetiche;
ottimizzazione di al pi`u tre parametri contemporaneamente a scelta tra le coordinate della posizione del giunto radice nello spazio;
perturbazioni limitate (pochi millimetri); rimozione dei vincoli;