La soluzione mediante programmazione dinamica

La minizzazione dell'equazione è un classico problema di assegnamento pesato. Esistono algoritmi ben noti per risolverlo con tempi di calcolo di ordine . Applicando questi algoritmi risolutivi del problema di assegnamento direttamente al problema di stereo si ottengono soluzioni non fisiche, perché l'equazione non vincola l'accoppiamento ad essere simile all'accoppimento , come invece spesso avviene nelle immagini reali. Per imporre questo vincolo di lisciezza viene spesso introdotto un fattore di penalizzazione nella funzione costo [13, 21]. Tuttavia l'aggiunta di questo ulteriore fattore comporta l'introduzione di altri parametri liberi, difficilmente valutabili, e inoltre l'algoritmo modificato tende a lisciare impropriamente i salti di profondità. Invece, nell'algoritmo da noi utilizzato, per restringere la ricerca ed eliminare le soluzioni non fisiche si fa uso di due vincoli:

1. Unicità di accoppiamento: un pixel nell'immagine sinistra corrisponde a non più di un pixel nell'immagine destra, e vice versa.
2. Ordinameto monotonico: se è fatto corrispondere a , allora il successivo accoppiamento può venire accoppiato solo con per j>0

questi vincoli sono illustrati nella figura , dove un percorso rappresenta gli accoppiamenti tra pixel dell'immagine sinistra e pixel dell'immagine destra.

  
Figure: Un percorso rappresenta gli accoppiamenti tra pixel dell'immagine sinistra e pixel dell'immagine destra. La linea solida rappresenta un percorso valido, mentre la linea tratteggiata rappresenta un percorso che viola i vincoli di unicità e ordinamento. Una linea verticale denota un'occlusione nell'immagine destra, una linea orizzontale un'occlusione nell'immagine sinistra, un segmento diagonale nel punto denota l'accoppiamento del pixel i nell'immagine sinistra con il pixel j nell'immagine destra.