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

i

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

i

Capitolo

i

3

N-W1 Algorithm
L’algoritmo studiato per risolvere il problema dello Stereo-Matching e stato
proposto recentemente dai ricercatori della Kingstone University, comprende
l’uso di un algoritmo di ispirazione bio-informatico per l’allineamento delle due
immagini stereoscopiche.
L’algoritmo bio-informatico per l’allineamento di sequenze geniche utilizzato è
il Needleman–Wunsch, algoritmo di programmazione dinamica sviluppato nel
1970 da Saul B. Needleman e Christian D. Wunsch.
Per comprendere meglio la relazione che c’è fra le sequenze geniche e le righe
delle immagini basta pensare alle due immagini come a una la mutazione (genetica) dell’altra. Pensata la questione in questi termini i ragionamenti successivi
saranno più chiari e lineari. L’algoritmo ottimizza l’allineamento globale di tutti
i caratteri delle stringhe in accordo ad una funzione di scoring che tiene presente di tutte le possibili mutazioni. In pratica, l’allineamento viene prodotto
attraverso due fasi: Fase1 la matrice (programmazione dinamica) dei punteggi
viene riempita fino all’ultima riga e colonna, Fase2 Backtracking (tracciamento
all’indietro) dal valore più alto dell’ultima colonna/riga fino a ritornare alla cella in prima posizione. Ogni cella della matrice contiene il massimo valore che
può essere raggiunto estendendo i precedenti allineamenti, ad esempio potremmo avere due stringhe di dimensione n e m, il valore che abbiamo nel la cella
1 N-W:

Needleman–Wunsch

37

i

i
i

i