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

i

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

i

4.2. DESCRIZIONE DELL’ALGORITMO

4.2.2

i

50

Backtracking

Il processo di backtracking è piuttosto semplice. Si parte dal punteggio più alto
posizionato nell’ultima riga e nell’ultima colonna. Individuata la cella si segue
a ritroso la direzione che ha portato a quella cella e così via fino a raggiungere l’angolo superiore sinistro della matrice che contiene un valore indicativo
che segnala il termine della procedura di backtracking. Al termine di questa
procedura il risultato ottenuto è una serie di allineamenti con punteggio ottimale. Affinché sia possibile individuare una soluzione super-ottima gli autori
dell’algoritmo hanno imposto una serie di vincoli sulla sequenza allineata.

Figura 4.2.1: Rappresentazione grafica degli allineamenti ottimi di due scanilnes.
In particolare per l’allineamento della riga i rispettivamente dell’immagine sinistra li e la corrispondente riga sull’immagine destra ri vengono calcolati dei
vincoli di allineamento tra li e la media di ri e ri+1 . Le soluzioni presenti
in entrambi gli allineamenti sono da favorire. Estendendo questo ragionamento
possiamo considerare tutte le possibili combinazioni tra (li ), (li +li+1 ), (li−1 +li ),
(li−1 + li + li−1 ), e (ri ), (ri + r1+1 ), (ri−1 + ri ), (ri−1 + ri + ri+1 ) e considerando anche la lettura da destra verso sinistra delle scanline, per un totale di 32
vincoli comple