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

i

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

i

66

i

2. APPROCCI ALTERNATIVI

Algoritmo 2.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)
}
}

gap=0 e mismatch=0.
Una versione successiva dell’algoritmo è stata implementata tenendo conto delle
esigenze specifiche del problema, ovvero le occlusioni.
Come si può vedere in Alg:2.2, si ha l’aggiunta di una nuova variabile chiamata
egap (extended gap). Un’occlusione (nel campo della stereoscopia) è una parte
della scena visibile da un punto di vista ma nascosta all’altro. Per capire meglio
questo concetto basta provare a mettere un dito ad un palmo dal naso. Osservando lo sfondo (aldilà del dito) prima chiudendo un occhio e poi l’altro, si nota
che il dito occupa il campo visivo in modi diversi a seconda dell’occhio aperto,
e di conseguenza occlude alla vista certe zone anziché altre. La modifica del
codice originale è stata effettuata tenendo conto del fatto che in una scena è
più probabile che ci siano poche occlusioni di grande dimensione che non invece
molte occlusioni ma di piccola dimensione.

2.2.2

Backtracking

Durante la creazione della matrice dei punteggi viene segnata anche la direzione
da cui si è provenuti, seguendo all’indietro queste direzioni è possibile ottenere

i

i
i

i