Assemblaggio di codici per scene generiche

In generale non è semplice identicare quale codice sia da usare senza la conoscenza dell'errore dominante indotto dalla indiretta illuminazione.Oltretutto nella maggior parte degli scenari si ha la compresenza di eetti a lungo e corto raggio. In questo paragrafo si cercherà di risolvere questo problema.

Algoritmo per la ricostruzione della profondità a più codici Si dimostra che dalla proiezione di un piccolo insieme di codici ottimizzati per i probabili difetti è possibile gestire un'ampia famiglia di situazioni, senza una conoscenza a priori delle proprietà della scena. L'idea principale è che gli errori provocati da codici diversi sono approssimativamente casuali. Per cui, se il valore della profondità ottenuto utilizzando due dierenti codici è lo stesso, con

alta probabilità, questo valore sarà corretto. Sono stati realizzati quattro dierenti codici: due ottimizzano gli eetti a lungo raggio (XOR-04 e XOR-02), gli altri due quelli a corto raggio (codice Gray convenzionale e maximum min-SW Gray codes). Ogni codice restituisce una mappa della profondità della scena come mostrato nelle gure 4.1.9 (a-d). Il valore nale della profondità è ricavato ricorrendo ad una verica di congruenza tra i valori delle profondità ottenuti mediante l'impiego dei singoli codici. Se due di quei valori dieriscono poco tra loro, essi approssimeranno bene il valore esatto. Essendoci due codici per ciascun eetto, la verica di congruenza ci permetterà di estrarre il corretto valore della profondità.

Si noti che il codice Gray convenzionale può presentare un errore nella risoluzione della pro- fondità a causa della defocalizzazione e della dispersione. Pertanto se i due codici Gray concordassero, si accetterebbe il valore della profondità ricavato dal maximum min-SW Gray codes.I pattern binari sono decodicati binarizzando le immagini catturate in pixel illuminati e non. Un metodo robusto per far questo consiste nel catturare due immagini L e ¯L che corrispondono, rispettivamente, ad un pattern P ed il suo negativo ¯P . Per un punto della scena Si_{, le intensità luminose L}i _{e ¯L}i vengono comparate. Se Li _{> ¯L}i ,

Nelle gure sopra si mostra la mappa di profondità ottenuta dall'algoritmo. Mentre ogni codice produce singolarmente errori signicativi, la mappa nale di profondità (4.1.9-e) è approssimativamente error-free.

Figura 4.1.9: Ricostruzione della profondità della scodella

Analisi dell'errore per l'algoritmo a più codici Il proiettore emette strisce verticali, le quali sono identicate da un codice univoco. Per pattern binari, il codice è binario. Se il numero totale di colonne è M, il codice sarà composto da N bit, dove N = log2(M ). Essendo

N i pattern proiettati, le telecamere cattureranno N immagini, una per ogni pattern. Sia CS a il

codice binario per la colonna a; con S si indica il tipo di codice utilizzato (CG,MM-SW,XOR- 02,XOR-04). Supponiamo che un pixel della colonna a, sia correttamente illuminato, da un pixel x della camera. Sia IS

x il vettore dei valori delle intensità assunte da x. Al ne di stabilire

una corretta corrispondenza, è necessario che il codice CS

a possa essere ricostruitoa partire da

I_xS. Sfortunatamente vari fattori come rumori di misura, uttuazioni luminose o illuminazione indiretta possono causare l'inversione di qualche bit da 0 a 1 e viceversa. Questo porta ad una decodica errata e ad un diverso codice associato, CS

b.La probabilità che un codice CaS

sia codicato come codice CS b è:

P r[C_aS → CS b] = pd

dove p è la probabilità di inversione di un bit e d è la distanza di Hamming2 _{fra C}S a e CbS

(0≤d≤N). p dipende dai rumori di misura, livello di illuminazione, albedo3_{. Un piccolo valore}

di p si traduce in una codica adabile; un grande valore di p indica un codica scorretta. Finora si è supposto p costante per tutte le posizioni dei bit, ma in realtà non è così. Per esempio per i codici Gray convenzionali, dal momento che, in presenza di interriessione, i pattern a bassa frequenza (che rappresentano i bit più signicativi) sono più facilmente decodicati in modo errato, p assume un valore più alto per i bit più signicativi rispetto a quelli meno importanti.

L'obiettivo di questa analisi è quello di mostrare che la probabilità che due schemi di codica distinti provochino lo stesso errore è bassa. D'ora in avanti si suppone che p vari a seconda del bit considerato.

Si denisce matrice di scambio MS _{per il tipo di codice S come M}S_{(a, b) = P r[C}S

a → CbS],

dove a e b sono due colonne distinte proiettate. MS_{(a, b) indica la probabilità che C}S a sia

decodicata come CS

b. Questa matrice misura la resilienza dell'errore per un dato schema

di codice. Anchè si abbia la maggior robustezza all'errore la matrice di scambio dovrebbe essere diagonale. Si tenga conto che la matrice di scambio è funzione di p, la probabilità di single bit-ip. La gura 9 mostra la matrice di scambio per i quattro diversi codici e per due valori di p. Come ipotizzato, per un basso valore di p, la matrice è approssimativamente diagonale per tutti i codici. Contrariamente, con un alto valore di p, i termini fuori diagonale sono confrontabili con i termini in prossimità della diagonale principale. Questo può dar luogo

2_{La distanza di Hamming tra due codici binari, nella teoria dell'informazione, indica il numero di sostituzioni}

che si devono compiere per far sì che due codici distinti abbiano per ciascuna posizione valori identici (quindi i due codici saranno uguali).

3_{L'albedo indica la frazione di luce riessa da una supercie colpita da un fascio (di luce). Si misura con}

a importanti errori nella fase di decodica. L'algoritmo a più codici genera un errore se lo stesso errore di decodica si presenta in due dierenti codici. Dal momento che la presenza del medesimo errore in due dierenti codici è bassa, il procedimento può essere considerato error-free.

Figura 4.1.10: Matrici di scambio per distinti schemi di codica

Applicando tecniche combinatorie, la probabilità che la colonna a sia confusa con quella b, per due codici diversi S1 e S2 è:

P r[(C_aS1→ CS1

b )&(CaS2 → CbS2)] = P r[CaS1→ CbS1] ∗ P r[CaS2→ CbS2]

Questo segue dall'indipendenza del processo di decodica per i due schemi. E'possibile rap- presentare questa relazione utilizzando le matrici si scambio per ottenere l'errore congiunto P(S1,S2) dove:

P(S1,S2)(a, b) = MS1(a, b)xMS2(a, b)

La gura 10 mostra le matrici per sei coppie di codici: si osserva che i valori dei termini fuori diagonale sono piccoli. Dunque si nota che una colonna a può essere decodicata incorretta- mente come ciascun altra colonna b. Così, la probabilità che l'algoritmo a più codici manifesti un errore nella decodica della colonna a è:

P(S1,S2)(a) =P

bP(S1,S2)(a, b)

Queste sono riportate nella gura sottostante (graci in blu): si osservi che la maggior parte dei valori di probabilità è inferiore all' 1%.

Figura 4.1.11: Analisi dell'errore per due valori di probabilità p

La gura 4.1.12 mostra invece la probabilità di errore media per coppie di codici distinti, al variare del parametro p: la maggior parte di questi valori è inferiore all' 1% con un massimo di 1,4%.

Figura 4.1.12: Tabella degli errori medi

Errore medio di profondità Un errore in fase di decodica si ripercuote in una stima incorretta della profondità. L'intensità dell'errore di profondità è direttamente proporzionale all'errore di distanza|a − b|, dove a è il numero della colonna corretta e b il numero della colonna realmente codicata . L'errore di distanza per una coppia S1 e S2 è:

E(S1,S2) = _M1 P

(a,b)|a − b|P(S1,S2)(a, b)

Dove M è il numero totale di colonne proiettate. La gura 4.1.13 mostra l'errore medio nella decodica delle colonne per coppie di codici e valori di p diversi. La maggior parte degli errori sono inferiori ad 1 pixel con un massimo di 1,67.

Figura 4.1.13: Tabella degli errori medi in pixel