1:
12: procedure PESOELEMENTOVDI(immsx, immdx, riga, disparita, peso)
13: peso ← 0
L’algoritmo 1 mette in evidenza il tipo di criterio utilizzato per valutare la corre-lazione tra una coppia di righe omologhe, per un certo valore di disparit`a: la somma
1Tenendo comunque presente che, detto c il numero di colonne di una delle immagini di partenza, deve sempre valere che
−c < dmin< c 1 ≤ cvdi≤ c − dmin
elevate [18], e si `e scelto di impiegarlo anche in questa occasione dal momento che, tra le istruzioni del set Intel R SSE, ne esiste una in grado di calcolare in parallelo tale costo di abbinamento.
Per poter comprendere come sia possibile applicare il modello computazionale SIMD al problema in esame occorre, per`o, conoscere prima pi`u in dettaglio come le immagini da elaborare vengano memorizzate all’interno del calcolatore e come sia possibile accedervi tramite le istruzioni Intel R MMX ed SSE.
Per prima cosa dalle immagini acquisite dalle telecamere viene estratta l’informa-zione sulla luminanza, codificata come una serie di valori compresi tra 0 e 2552(dove 0 rappresenta il nero, e 255 il bianco); viene quindi applicato su di esse il filtraggio che produce le immagini di Sobel ternarizzate, operando, per`o, la sostituzione illustrata nella tabella 3.1 rispetto ai valori in uscita originariamente previsti dal filtro.
Valori in uscita dal filtro originale nuovo
-1 0
0 127
1 254
Tabella 3.1: Sostituzione sui valori del filtro di Sobel ternarizzato
A questo punto in memoria sono presenti due immagini filtrate, costituite da una serie di pixel contigui, ciascuno dei quali occupa un solo byte, e assume uno tra i tre valori positivi (0, 127, 254).
Come si `e visto, nel corso dell’elaborazione, fissate la riga e la disparit`a in esame, si deve procedere calcolando i valori assoluti delle differenze pixel a pixel tra le due porzioni di immagini sovrapposte, sommandoli, e dividendo il risultato per il numero di elementi analizzati; l’istruzione cui si faceva riferimento poc’anzi, il cui opcode3
`epsadbw, effettua con un buon grado di parallelismo gran parte delle operazioni ri-chieste, dal momento che, agendo su 64 bit per volta, computa le differenze in valore
2Dunque rappresentabili tramite log2(256) = 8 bit, ovvero 1 byte, ciascuno
3Ossia lo mnemonico utilizzato per invocarla all’interno del codice assembly
assoluto byte a byte tra le porzioni corrispondenti dei suoi operandi e le somma, secon-do o schema riportato in figura 3.5: ci`o significa che `e possibile suddividere ciascuna riga in finestre di 8 pixel, e per ciascuna calcolare un unico contributo di correlazione, pari alla somma di quelli dei suoi elementi.
Figura 3.5: Elaborazione svolta dall’istruzionepsadbw
L’impiego di questa istruzione richiede, comunque, alcuni accorgimenti, dal mo-mento che vengono fatte in modo implicito almeno due ipotesi sui dati trattati, ovvero che questi siano costituiti da una serie di interi senza segno di lunghezza 1 byte, e che tutti gli 8 byte presenti in ciascun registro vadano elaborati.
La sostituzione presentata in tabella 3.1 risolve il primo problema, mentre per quanto riguarda il secondo si deve tener conto che, nella rappresentazione in memoria utilizzata per le immagini, l’ultimo pixel di ciascuna riga precede immediatamente il primo di quella successiva: se la differenza tra i valori degli indici denominati nell’al-goritmo 1 inizio e f ine non risulta multipla di 8, le finestre su cui eseguire il confronto non possono coprire esattamente l’intera area di sovrapposizione tra le righe (come si pu`o vedere in figura 3.6).
Figura 3.6: Calcolo della correlazione tra due righe omologhe
Supponendo che le immagini utilizzate siano larghe 13 pixel, si vede come, per una dispa-rit`a di -2, l’istruzionepsadbwpossa essere invocata senza ulteriori interventi correttivi una sola volta (pixel azzurri), dato che una sua seconda esecuzione andrebbe ad inte-ressare altri elementi oltre a quelli rossi (gli unici su cui il calcolo debba essere ancora svolto)
I dati vengono prelevati dalla memoria sempre a gruppi di 4 od 8 byte, tramite le istruzionimovd(move doubleword) e movq(move quadword), ed inseriti nei registri MMX, dove sono elaborati; dalle considerazioni appena esposte appare evidente come le opzioni disponbili al momento di effettuare il calcolo della correlazione siano due:
gestire in qualche modo i casi di bordo, o semplicemente ignorarli, evitando di tenerne conto ai fini del computo del valore di match per la riga in esame.
numero bit nome
Tabella 3.2: Nomi dei pi`u comuni raggruppamenti di bit
La prima strada comporta delle operazioni aggiuntive, e in generale una efficienza leggermente minore, in quanto il flusso di controllo risulta pi`u complesso, mentre la seconda fornisce risultati meno accurati, dal momento che questi vengono in generale ricavati da un numero inferiore di pixel (pi`u precisamente, ( f ine − inizio) mod 8 pixel4 in meno rispetto a quelli disponibili).
Sperimentalmente si `e potuto osservare che la versione approssimata della V-disparity image risulta comunque pressoch`e indistinguibile da quella calcolata in modo esat-to, con in pi`u il vantaggio che il codice risulta semplice (come si pu`o osservare nel-l’algoritmo 2, dove l’elaborazione svolta dall’istruzionepsadbw `e stata indicata con SAD 8) e veloce.
Un aspetto critico nell’utilizzo della tecnologia Intel R MMX ed SSE `e costituito dalla elevata latenza5 legata alla lettura dei dati in memoria [1]; completare il cari-camento di un registro MMX pu`o richiedere fino a 12 cicli di clock, e, se la succes-siva istruzione lo utilizza, il processore si ritrova in una condizione di stallo, in cui,
4L’operatore mod indica il resto della divisione tra due numeri interi
5Ovvero il numero di cicli di clock che devono trascorrere prima di poter utilizzare il valore conte-nuto nel registro di destinazione; si definisce invece throughput il numero di cicli di clock che bisogna attendere prima che il processore possa cominciare ad eseguire di nuovo la medesima istruzione