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

i

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

i

4.2. DESCRIZIONE DELL’ALGORITMO

i

49

c’era già un gap, oppure la penalizzazione gap altrimenti. La stessa cosa viene
fatta prelevando il valore della cella ad ovest di quella attuale, ed infine il terzo punteggio viene calcolato prelevando la cella a nord-ovest ed effettuando il
seguente calcolo (pjL e pjR sono i pixel j-esimi della riga in esame):
match − |pjL − pjR |
dove match è il punteggio assegnato a due pixel uguali. Oltre al valore del punteggio attuale, all’interno della matrice viene anche memorizzata la posizione
della cella che si è deciso di estendere. Quest’informazione sarà essenziale durante la fase di backtracking per poter ricostruire l’allineamento ottimo tra le
due scanline.
Algoritmo 4.1 Pseudo-codice del riempimento dei valori della matrice.
1

6

for i = 1 to length(sequence1)
{
for j = 1 to length(sequence2)
{
mismatch = -|IL(line, i) - IR(line,j)|
if(M(i-1, j) è un gap)
nord <- M(i-1, j) + egap
else
nord <- M(i-1, j) + gap
diagonal <- M(i-1,j-1) + match + mismatch
if(M(i, j-1) è un gap)
west <- M(i, j-1) + egap
else
west <- M(i, j-1) + gap

11

16

M(i, j) <- max(north, diagonal, west)
}
}

Come possiamo notare la matrice ha dimensione WL × WR dove WL e WR
sono le larghezze delle due immagini. Una volta che la matrice è completa dei
punteggi e delle direzioni si passa alla fase di backtracking.

i

i
i

i