Tesi Robotica Un co-processore per Stereo-Matching: Architettura | Page 40

i

i
“LP_Tesi” — 2011/9/9 — 21:20 — page 40 — #40

i

3.2. BACK TRACKING

i

40

Algoritmo 3.2 Needleman–Wunsch con gap esteso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for i = 1 to length(sequence1){
for j = 1 to length(sequence2){
mismatch = -|IL(line,i) -IR(line,j)|
if( M(i-1,j) is a gap )
north <- M(i-1,j) +egap
else
north <- M(i-1,j) +gap
endif
diagonal <- M(i-1,j-1) +match +mismatch
if( M(i,j-1) is a gap )
west <- M(i,j-1) +egap
else
west <- M(i,j-1) +gap
endif
M(i,j) <- max(north, diagonal, west)
}
}

3.2

Back Tracking

Durante la creazione della matrice dei punteggi viene segnata anche la direzione
da cui si è provenuti, seguendo all’indietro queste direzioni è possibile ottenere
il backtracking. Questo procedimento in genere porta alla generazione di più
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 bordi, i
quali vengono identificati in una fase di pre-processazione. Queste intersezioni
vengono utilizzare per costruire vincoli che a seconda che vengano soddisfatti o
meno rendono un percorso migliore o peggiore rispetto ad un altro. In Fig:3.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.

i

i
i

i