Tesi Robotica Analisi, progettazione e implementazione... | Page 67

i

i
“LP_Tesi” — 2013/10/17 — 18:27 — page 67 — #67

i

2.2. N-W ALGORITHM

i

67

il Backtracking. Questo procedimento in genere porta alla generazione di più
percorsi, di conseguenza è necessario fornire nuovi parametri che consentano
di scegliere quale fra i vari cammini è quello giusto. Molte strategie sono state
fornite per risolvere questo problema. Alcune suggeriscono di scegliere i percorso
meno spigolosi e più smussati, altre sono basate sull’intersezione dei contorni, i
quali vengono identificati in una fase di pre-processazione. Queste intersezioni
vengono utilizzare per costruire vincoli che a seconda del loro soddisfacimento
o meno rendono un percorso migliore o peggiore rispetto ad un altro. In Fig:2.1
segnato in rosso è possibile vedere un allineamento, tenendo sempre a mente che
abbiamo come sequenze di input sequence1 = EDECE e sequence2 = ADCE
l’allineamento finale (rispetto a sequence2) porterà a: AD-CE, la sequenza è
identica all’originale tranne per il carattere “-” che indica una situazione di gap.
Come detto questo algoritmo permette di trovare più di un cammino durante
il Backtrack, questa naturale ambiguità è dovuta al fatto che esiste più di un
percorso con punteggio massimo che va dall’angolo inferiore destro a quello
superiore sinistro. Una volta realizzata la prima release del progetto ci si è
accorti però che i nel caso in cui siano presenti più di un allineamento ottimo non
c’è molta differenza fra i due, tale differenza diviene non significativa quando
il numero di frame al secondo computati aumenta. Per questo motivo si è
deciso quindi di applicare una strategia greedy per la risoluzione delle ambiguità.
Quando il Backtrack si trova ad un bivio sceglie semplicemente la prima via che
viene proposta. In tal modo è stato potuto adottare una miglioria al codice che
nel seguito verrà spiegata meglio.

2.2.3

Come Funziona

Una volta descritto l’algoritmo è possibile cominciare a capire come è possibile
che un metodo usato per allineare sequenze geniche possa fare ricostruzione di
mappe di disparità. Il fulcro della questione sta in cosa rappresenta il percorso
di backtrack.
In Fig:2.2.1 è rappresentata la matrice con ben due percorsi di backtrack, in
verde e in blu. Si guardi ora alla diagonale tracciata in rosso e mentalmente
si posizioni l’obbiettivo della telecamera al centro della diagonale puntandola
verso l’angolo in basso a sinistra della matrice. A questo punto si ha l’esatta
disposizione del mondo all’interno della matrice, tutte le celle che stanno nella
triangolare inferiore rappresenteranno una posizione nel mondo reale di fronte
all’obbiettivo, invece gli elementi che stanno nella triangolare superiore rappre-

i

i
i

i