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

i

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

i

3.1. CREAZIONE DELLA MATRICE DEI PUNTEGGI

i

39

esaminato il valore di north e west con l’aggiunta del gap, il valore massimo
fra questi tre diventerà il contenuto della casella analizzata. Ecco un esempio (Tab:3.1) di come la matrice può presentarsi alla fine della computazione,
avendo come input: sequence1 = EDECE, sequence2 = ADCE, match = 2,
mismatch = 0, gap = -1.

Tabella 3.1: Allineamento
Ma questa è solo una delle possibili implementazione dell’algoritmo, a voler
essere precisi, pur essendo molto semplice, alcune specializzazioni di questo algoritmo in campo didattico sono molto utili, primo fra tutti l’algoritmo per
la ricerca della più lunga sottosequenza comune (LCS), basta fissare match=1,
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:3.2, abbiamo 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 provate 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.

i

i
i

i