Minimizzazione della funzione costo

La particolare forma della funzione , con i vincoli di ordinamento e unicità, ne permette la soluzione efficiente mediante programmazione dinamica. Questo si ottiene ``mappando'' la funzione su un problema di cercare il percorso a costo minimo in un grafo orientato e pesato. I vertici del grafo rappresentano i possibili valori di disparità assegnabili a ogni pixel (figura ). I costi vengono assegnati ai nodi mediante una funzione che dipende dalla differenza di intensità luminosa dei pixel. I costi degli archi valgono 0 per percorsi diagonali, mentre i percorsi ortogonali (che rappresentano una occlusione) hanno un costo dipendente dalla probabilità di occlusione. Gli archi sono orientati in modo da permettere solo percorsi che rispettano i vincoli di unicità e ordinamento (figura ). Il costo totale della funzione obiettivo per un percorso si ottiene sommando insieme tutti i costi degli archi con tutti i costi dei nodi. La soluzione più probabile al problema di accoppiamento di pixel è rappresentata dal percorso di costo minimo.

  
Figure: Il grafo corrispondente al problema di stereo. I punti rappresentano i nodi del grafo e corrispondono ai possibili accoppiamenti tra pixel dell'immagine sinistra e dell'immagine destra, un possibile percoso è rappresentato da un insieme di archi che parte dal primo punto dell'immagine sinistra e arriva all'ultimo punto.

  
Figure: Dettaglio degli archi del grafo corrispondente al problema di stereo. Gli archi sono orientati in modo da rispettare i vincoli di unicità e di ordinamento.

Per un grafo con questa struttura il percorso minimo può essere trovato mediante programmazione dinamica [20]. La struttura dati necessaria consiste di due campi per ogni vertice, il primo per contenere il costo totale del percorso ottimo fino a questo nodo, il secondo per contenere il puntatore che indica il vertice immediatamente precedente lungo questo percorso. Più precisamente, il puntatore di un vertice nella colonna i punta a un vertice nella colonna i-1. L'algoritmo si compone di due passi, un passo in avanti che computa i costi dei vertici e imposta i puntatori, un passo all'indietro che ricostruisce il percorso a costo minimo seguendo i puntatori. Lo pseudocodice dell'algoritmo viene riportato in figura . Nello pseudocodice la matrice dei costi viene denotata con costo . La matrice prec ] memorizza i puntatori alla riga colonna precedente, con la convenzione: prec significa che il punto precedente di i,j è il punto i-1,j-1; prec significa che il punto precedente di i,j è il punto i-1,j; prec significa che il punto precedente di i,j è il punto i,j-1.

  
Figure: Pseudocodice dell'algoritmo di programmazione dinamica

La correttezza dell'algoritmo si dimostra mediante induzione sulla lunghezza del percorso.

Esaminando il codice, è facile rendersi conto che il costo computazionale dell'algoritmo è pari a . Infatti, l'inizializzazione ha complessità , il passo all'indietro ha complessità , il passo in avanti ha complessità , costituendo quindi il costo dominante.

È possibile diminuire ulteriormente il costo computazionale dell'algoritmo restringendo la disparità massima tra due pixel. Se un pixel è vincolato ad essere accoppiato solo con pixel per i quali allora il costo dell'algoritmo si riduce a .

Altri algoritmi di stereo basati su programmazione dinamica hanno una complessità computazionale . Nel nostro caso, l'introduzione dei vincoli di unicità e di ordinamento monotonico pemettono di risparmiare un fattore uno all'esponente, rendendo particolarmente veloce il calcolo.

Secondo quanto riportato dagli autori, l'algoritmo, testato su stereogrammi a punti casuali, ricostruisce correttamente la disparità del 95,4% dei punti.

Gli autori propongono ulteriori elaborazioni dell'algoritmo-base. Per esempio, aggiungendo tre matrici, , , , per memorizzare in che modo l'algoritmo è giunto al vertice , è possibile scegliere tra i possibili percorsi ottimi quello che minimizza il numero di discontinuità orizzontali, (nella sua forma base, l'algoritmo di programmazione dinamica è garantito trovare un percorso con costo minimo, ma, nel caso ve ne siano più d'uno, non il medesimo per ogni riga). Lo pseudocodice per l'algoritmo modificato è riportato nelle figure e . In questa versione la matrice dei puntatori all'indietro prec non è più necessaria: il percorso ottimo può venire ricostruito direttamente dalle tre matrici , , . Il costo computazionale di questa seconda versione dell'algoritmo ha un costo computazionale lievemente superiore, ma la percentuale di punti per i quali viene determinata la disparità corretta, negli stereogrammi a punti casuali, sale al 98,7%.

  
Figure: Pseudocodice dell'algoritmo di programmazione dinamica, con minimizzazione delle discontinuità orizzontali, passo in avanti. La costante GRANDE indica un costo molto alto, utilizzato per penalizzare i percosi subottimali. La funzione argmin ritorna 1,2 o 3 a seconda che il minimo sia il primo, il secondo o il terzo argomento.

  
Figure: Pseudocodice dell'algoritmo di programmazione dinamica, con minimizzazione delle discontinuità orizzontali, passo all'indietro.

Gli autori introducono poi un ulteriore passo di minimizzazione sulle discontinuità verticali. Questa modifica raddoppia i tempi di calcolo, a fronte di un miglioramento sino al 99,1% di accoppiamenti corretti su sterogrammi a punti casuali. Sul robot sono state sperimentate tutte e tre le versioni dell'algoritmo. A fronte dei dati sperimentali si è deciso di utilizzare la versione descritta nelle figure e , non ritenendo conveniente l'ulteriore incremento dei tempi di calcolo richiesto dalla minimizzazione delle discontinuità verticali, a fronte del modesto miglioramento dei risultati su immagini reali.