Tesi Robotica Un coprocessore per Stereo-Matching: Profiling ... | Page 48

i

i
“MF_Tesi” — 2011/9/12 — 11:39 — page 48 — #48

i

4.2. DESCRIZIONE DELL’ALGORITMO

i

48

corrispondenti l’allineamento ottimale. Questa metodologia è suggerita dal fatto
che possiamo immaginare che l’immagine destra sia una versione modificata
dell’immagine di sinistra. Dunque una volta allineate nel modo ottimo le due
righe si passa ad analizzare appunto le disparità che intercorrono in modo da
ottenere una misura della distanza relativa degli oggetti nella scena.
L’algoritmo si basa sull’approccio della programmazione dinamica, quindi per
quanto detto nel capitolo precedente questo problema mostra i due aspetti fondamentali necessari per la creazione di un algoritmo di programmazione dinamica: la sotto-struttura ottima e la sovrapposizione dei problemi. In questo caso
la sotto-struttura ottima è da ricercare nel fatto che un allineamento ottimale
è costituito estendendo all’ottimo un sotto-allineamento ottimale. L’estensione
di un sotto-allineamento ottimo costituisce anche l’elemento di sovrapposizione
dei sotto-problemi.

4.2.1

Costruzione della matrice dei punteggi

L’estensione del punteggio si effettua tramite un sistema di premi e penalizzazioni. Il punteggio da cui si parte è match, che corrisponde a due pixel identici.
Inoltre esistono le penalizzazioni gap ed egap. La prima viene utilizzata quando
si considera l’inizio di un’occlusione, mentre la seconda si utilizza quando si è nel
mezzo di un’occlusione (un’occlusione corrisponde ad una porzione della scena
che è visibile in una delle immagini, ma non in entrambe in seguito al cambiamento di angolazione di ripresa). Si utilizzano due penalizzazioni diverse, di cui
egap è quella minore in modo da favorire il raggruppamento dei gap in cluster,
dato che ci si aspetta di avere poche occlusioni di tanti pixel piuttosto che molte
occlusioni di un pixel.
Data la coppia di immagini stereo IL e IR e prese le i-esime righe viene effettuata
la costruzione di una matrice, detta dei punteggi, in cui ogni cella contiene il
massimo punteggio ottenibile estendendo il precedente allineamento. La prima
operazione che viene effettuata consiste nel riempire la prima riga e la prima
colonna della matrice con una sequenza cumulativa di gap. Il riempimento della
tabella avviene scandendo le celle da sinistra verso destra e dall’alto verso il
basso. Come appena detto, ogni cella contiene il punteggio massimo ottenibile
estendendo un precedente allineamento. Alla generica iterazione il calcolo del
sotto-allineamento ottimo avviene scegliendo il migliore di tre possibili allineamenti. Il primo valore si ottiene prelevando il punteggio nella cella a nord di
quella attuale ed aggiungendoci la penalizzazione di egap, se nella cella nord

i

i
i

i