EFINIZIONE DELL ’ ARITMETICA DI MACCHINA C APITOLO 3 D

CAPITOLO 3

DEFINIZIONE DELL’ARITMETICA DI MACCHINA

Dopo aver introdotto l’algoritmo su cui si basa il lavoro che si sta trattando e dopo aver effettuato alcune operazioni di ottimizzazione volte all’implementazione hardware di un sorgente C, è giunto il momento di soffermarci sull’aritmetica di macchina del sistema. In questo capitolo vedremo quali sono i ragionamenti da fare per realizzare il dimensionamento del sistema.

Il problema è particolarmente importante, poiché le decisioni prese in questa fase del progetto si ripercuoteranno sulla sintesi finale. Ad esempio, il numero di bit su cui si desidera allocare un dato influenzerà la dimensione di registri, di rom e di altre entità che saranno sintetizzate sulla FPGA di destinazione. In altre parole, in questa fase è necessario cercare di trovare un dimensionamento minimo in modo da non sprecare risorse sul Chip. Il dimensionamento delle varie sezioni del progetto può essere variato e come parametro di scelta, ancora una volta, sarà considerato il PSNR. Lo scopo è sempre quello di ottenere immagini con PSNR maggiore di 30 dB. Durante il dimensionamento del sistema è possibile perdere molto in termini di prestazioni, dato che l’algoritmo C utilizza una codifica di tipo

floating point, quindi ottiene la massima prestazione disponibile sul calcolatore. La codifica floating point, come si evince dal nome, è tale che i numeri decimali vengono trattati in modo da poter variare la dimensione della parte seguente la virgola, in base alle necessità del caso. In pratica, la virgola è mobile. Il numero di cifre decimali massimo è comunque fissato a 6 e qualunque numero può essere rappresentato come il prodotto tra una mantissa ed un esponenziale.

Ovviamente questa codifica per i numeri con parte frazionaria è particolarmente onerosa da un punto di vista di risorse richieste, pertanto viene adottata di solito nel caso di implementazione su processori. Quando invece si ha a che fare con hardware come FPGA, si preferisce far uso di un’aritmetica di tipo fixed point.

Quest’ultima consiste nell’allocazione di una quantità fissa di bit per la parte frazionaria dei numeri che si devono trattare. Ad esempio, si potrebbe scegliere di svolgere i calcoli facendo uso di sole 3 cifre decimali, che corrisponderebbero ad una rappresentazione fixed point con 10 bit riservati alla parte frazionaria.

Un’altra possibilità di codifica per numeri razionali, sarebbe quella di definire un’aritmetica di macchina diversa sia dal modello floating point che da quello fixed. Avremmo allora a che fare con un’aritmetica di tipo custom, ridefinibile a piacere anche per i singoli blocchi dell’architettura. Questo approccio è però sconveniente in quanto necessita di logiche aggiuntive per convertire i dati presi in ingresso e per quelli forniti in uscita, ma la vera difficoltà consiste nel fatto che queste logiche di interfacciamento sarebbero necessarie anche tra un blocco e l’altro dell’architettura. Abbandoniamo dunque quest’idea e proseguiamo sulla strada della codifica fixed point.

Il dimensionamento del sistema sarà condotto tenendo sempre presente i risultati ottenuti in termini di PSNR, in modo da poter scegliere il numero di bit necessari prima e dopo la virgola per ottenere certe prestazioni.

Bisogna tener presente che, per definizione, la codifica fixed point imporrebbe, in realtà, un numero fissato di bit anche per la parte intera di un certo valore. Si potrebbe dunque pensare di soddisfare questa definizione dimensionando il sistema sul caso peggiore ottenibile, vale a dire sul massimo valore che si può presentare nello svolgimento di tutti i calcoli, anche quelli

intermedi. Questa scelta porterebbe ad un dimensionamento rapido, efficace solo se i valori da rappresentare fossero tutti dello stesso ordine di grandezza. Nel nostro caso, abbiamo già osservato che i valori di ingresso e uscita sono interi compresi tra 0 e 255, i coefficienti So ed Sv possono variare tra 0 e 1000, ed i coefficienti Fo ed Fv hanno ancora un altro range. Presumibilmente i moltiplicatori daranno vita a valori ben diversi. Si capisce quindi come sia preferibile studiare la dinamica dei numeri per ciascun blocco dell’architettura, e adattare, caso per caso, la codifica fixed point. In particolare, sceglieremo di tenere fissa la dimensione della parte frazionaria, altrimenti il sistema non sarebbe più ad aritmetica fixed, mentre il numero di bit riservati alla parte che precede la virgola sarà deciso di volta in volta. Otterremo dunque un’aritmetica di macchina di tipo fixed point con parte intera a dimensione variabile ed ottimizzata. Sarà così evitato qualsiasi spreco in termini di risorse sulla FPGA, almeno per quanto riguarda questa fase del progetto.

Scegliamo fin d’ora un limite per la parte frazionaria del sistema. Definito N il parametro che indica la dimensione della parte che segue la virgola, prendiamo l’algoritmo originale Ret_soft.c e studiamone le prestazioni al variare di N, prendendo al solito come riferimento le immagini ottenute dal Ret_soft ottimo che opera in aritmetica floating point.

3.1

S

’

3.1.1 Blocchi di ingresso e uscita

In base alle espressioni (2.3) e (2.5) di y(i,j), l’architettura del filtro RRF può essere immaginata come proposto nella prossima pagina in figura 40.

Il dimensionamento è già espresso in forma parametrica. Nei prossimi paragrafi giustificheremo i valori di bit riportati nella figura con uno studio della dinamica dei valori numerici ottenibili, a partire dall’ingresso fino all’uscita del sistema.

Figura 40. Schema a blocchi dell’architettura del filtro RRF,con dimensionamento parametrico.

L’immagine monocromatica d’ingresso, in formato .img, è strutturata come una matrice di dimensione pari a quella dell’immagine, i cui valori sono quelli dei pixel che possono assumere tutti i toni di grigio a partire dal valore del nero, codificato come 0, fino al bianco, a cui corrisponde il valore 255. Questi dati vengono scritti, come già abbiamo sottolineato, nella Ram X. Per rappresentare questi valori, interi positivi e strettamente minori di 256, sono dunque sufficienti 8 bit, che consentono di raggiungere il limite (28 –1) che è pari proprio a 255.

Dunque la ram X avrà celle di dimensione pari a 8 bit, tutti allocati per la parte frazionaria. Solo ed esclusivamente per l’ingresso del sistema si ha a che fare con numeri interi e quindi si può fare a meno dell’approccio fixed point preferendogli la rappresentazione unsigned. Potremmo pensare di fare lo stesso in uscita, tagliando la parte frazionaria. Sappiamo infatti che in uscita dovremo ottenere dei dati analoghi a quelli ricevuti in ingresso, ovvero una matrice di interi. Questa operazione è però inaccettabile, come si era visto nel caso del sorgente Ret_hard, che dà luogo ad immagini distorte dal punto di vista dell’ illuminazione ( fig. 9 a pag. 34) dato che il sistema completo prevede, dopo le stime di luminanza e riflettanza, altri blocchi di elaborazione, come visto in fig. 1 a pag. 20.

In pratica è necessario conservare i bit della parte frazionaria anche in uscita dal filtro RRF, ed effettuare il troncamento brutale solo in prossimità dell’uscita del sistema completo. Ecco perché a differenza della catena di destra che ha inizio con 8 bit di parte intera e nessun bit per la parte frazionaria, la catena di sinistra prevede il blocco RamY con dimensione 8+N dove N è il parametro che indica la grandezza della parte frazionaria. Il valore di N sarà deciso in seguito.

3.1.2 Blocchi di calcolo Fo ed Fv

L’espressione analitica per il calcolo di tali coefficienti è:

( 1, ) (1 ) ( , ) ( , 1) (1 ) ( , ) fo y i j y i j fv y i j y i j α α α α = − + − = − + − (3.1)

In base alle scelte fatte in precedenza, il parametro α può assumere i tre valori: 0.500 ; 0.750 ; 0.900 Volendo essere coerenti con quanto detto finora a proposito della precisione del sistema, faremo in modo che le cifre decimali per α siano al massimo 3.

Supponiamo che α =0.500, allora (1-α ) = 0.500.

min max 0.500 1 0.500 1 1.000 0.500 255 0.500 255 127.5 127.5 255 f f = ⋅ + ⋅ = = ⋅ + ⋅ = + = se invece α =0.900 min max 0.900 1 0.100 1 1.000 0.900 255 0.100 255 229.5 25.5 255 f f = ⋅ + ⋅ = = ⋅ + ⋅ = + =

Lo stesso succede per α = 0.750, data l’espressione dei coefficienti F, la cui dinamica è dunque indipendente dal valore del coefficiente di ricorsività ed è compresa tra i valori 0 e 255.

Saranno sufficienti, pertanto, 8 bit di parte intera a cui se ne aggiungono N per la parte frazionaria. In totale: (8+N).

3.1.3 Blocchi di calcolo So ed Sv

I coefficienti S sono stati ottenuti per mezzo di una Look Up Table, riportata nella tabella 9 a pag. 65. Concentriamoci sui valori numerici ottenuti in ingresso ed in uscita dalla Lut:

• Precisione richiesta in ingresso alla LUT: i numeri sono sempre positivi e prevedono una parte intera che va da 0 a 180, mentre la parte decimale è a 4 cifre. Dunque sono necessari 8 bit per la parte intera, e ben 14 bit per la parte decimale. Totale: 22 bit.

• Precisione richiesta in uscita: numeri sempre positivi, con parte intera che va da 0 a 1000 e parte frazionaria a 5 cifre. Servono 10 bit per la prima, 17 bit per la seconda, totale 27 bit.

Il numero di cifre binarie che serve è enorme, molto vicino a quello necessario per implementare una codifica di tipo floating point. Osserviamo però che in pratica a questo livello non è richiesta una precisione così spinta per indirizzare la Lut, ma è sufficiente trovare l’intervallo della Lut che si deve leggere.

Cerchiamo allora di ridurre in qualche modo il numero di bit richiesti.

Cominciamo dal caso dell’uscita della Lut: per la parte decimale proviamo a troncare almeno due cifre, portando a 3 il numero di cifre decimali dopo la virgola.

Un’altra cosa che sembra possibile è troncare la parte frazionaria nel caso che la parte intera sia maggiore di 1, considerandola altrimenti.

Dal punto di vista aritmetico non ci sono obiezioni, almeno nel caso di numeri con parte intera maggiore di dieci, ma dobbiamo verificarne le conseguenze sulle immagini prodotte in uscita.

Se quest’idea fosse valida, sarebbe possibile ridurre notevolmente il numero di bit, che sarebbero: 10 per la parte intera, 10 per la parte decimale, dato che 2-10 = 0.0009 approssimabile in 0.001. Con il decimo bit della parte frazionaria, si riesce quindi ad ottenere una rappresentazione con risoluzione pari a 10-3.

Proviamo allora ad effettuare le approssimazioni appena introdotte e vediamo che succede: i risultati sulle immagini di uscita sono riportati nella tabella 10.

Al solito come termine di riferimento per il calcolo del PSNR sono state considerate le immagini generate dall’algoritmo originale Ret_soft.c, mentre gli algoritmi approssimati Ret_soft_lut_high e Ret_soft_lut_high* sono stati ottenuti a partire da Ret_soft.c cambiando, rispetto a questo, solo il calcolo dei coefficienti S che ora viene realizzato per mezzo della Lut implementata nel capitolo 2. In questo momento ci interessa, infatti ragionare solo sugli errori introdotti dal troncamento dei valori di So ed Sv campionati.

Algoritmo

approssimato Swan.img _(dB) Bedroom.img _(dB) Alpi.img _(dB)

Ret_soft_lut_high 38.84 51.42 46.56

Ret_soft_lut_high * 3 _{38.89 51.02 46.57}

Differenza di prestazioni: _{+ 0.05 - 0.40 + 0.01}

Tabella 10. Prestazioni ottenute in seguito al troncamento della terza cifra frazionaria decimale

nella Lut per il calcolo di So ed Sv.

3 _{“*” indica che i valori della lut sono quelli approssimati in seguito al troncamento alla terza cifra}

Le prestazioni ottenute sono in alcuni casi migliori, in altri peggiori, rispetto alla Lut precedente. In ogni caso, la differenza è minima, sempre inferiore al dB, quindi la semplificazione sul numero di bit è accettabile.

Spostiamo ora la nostra attenzione in ingresso alla LUT: il discorso fatto per l’uscita può essere ripetuto. Se osserviamo i valori degli intervalli di quantizzazione per X4, è evidente che la parte decimale è necessaria se la parte intera vale 1, altrimenti è nulla. Proviamo a troncare la parte decimale alla terza cifra: ridurremmo così a 10 il numero di bit necessari per la parte frazionaria anche in ingresso alla Lut.

Per ridurre le cifre della parte decimale è necessario cambiare alcune soglie della Lut:

1) Accorpiamo gli intervalli di quantizzazione 2 e 3 ottenendo : X ∈] 1.000 ; 1.001] ⇒ y = 991

2) stessa operazione per 4 e 5 , da cui scaturiscono : X ∈] 1.001 ; 1.002] ⇒ y = 956

X ∈] 1.002 ; 1.003] ⇒ y = 893

3) analogamente per gli intervalli 7,8,9,10, da cui derivano : X ∈] 1.004 ; 1.005] ⇒ y = 725

X ∈] 1.005 ; 1.006] ⇒ y = 639

Sono stati eliminati 8 intervalli di quantizzazione, sostituiti da 5 intervalli nuovi. Volendo sfruttare tutta la LUT abbiamo a disposizione 3 intervalli, che scelgo di mettere in:

X ∈] 1.006 ; 1.007] ⇒ y = 559 X ∈] 1.007 ; 1.008] ⇒ y = 488

al posto dell’undicesimo intervallo che è abbastanza ampio e quindi si presta ad essere spezzato in due parti.

4 _{Si ricorda che con X si intende l’argomento del logaritmo presente al denominatore dei}

A questo punto rimangono 2 intervalli da riempire: conviene sostituire a X ∈] 1.1200 ; 1.2000] ⇒ y = 5

X ∈] 1.2000 ; 1.3000] ⇒ y = 1.325

tre nuovi intervalli, visto che si passa velocemente da 5 a 1.325, una variazione del 73.5 % che potrebbe essere troppo brusca.

Sostituiamoli quindi con i nuovi:

X ∈] 1.1200 ; 1.1800] ⇒ y = 3 X ∈] 1.1800 ; 1.2400] ⇒ y = 1.535 X ∈] 1.2400 ; 1.3000] ⇒ y = 0.955

Rimane infine 1 intervallo da completare. Conviene utilizzarlo per rendere meno ripida la variazione del 50% da 30 a 15. Elimino dunque gli intervalli

X ∈] 1.0360 ; 1.0520] ⇒ y = 30 X ∈] 1.0520 ; 1.0750] ⇒ y = 15 espandendoli in: X ∈] 1.0360 ; 1.0490] ⇒ y = 31.65 ≅ 32 X ∈] 1.0490 ; 1.0620] ⇒ y = 18.54 ≅ 19 X ∈] 1.0620 ; 1.0750] ⇒ y = 12.24 ≅ 12

Siamo finalmente giunti alla verifica delle approssimazioni effettuate. La speranza è che il peggioramento delle prestazioni causato dalla riduzione della precisione in ingresso ed in uscita alla Lut sia stato bilanciato dall’introduzione di nuovi intervalli.

Nella tabella 11 possiamo trovare una risposta ai nostri quesiti:

Algoritmo approssimato Swan.img (dB) Bedroom.img (dB) Alpi.img (dB) Ret_soft_lut_high 38.84 51.42 46.56 Ret_soft_lut_high * 38.96 53.86 46.84 Differenza di prestazioni: + 0.12 + 2.44 + 0.28

Il temuto peggioramento delle prestazioni non c’è stato, anzi, le prestazioni sono aumentate in media.

Concludiamo allora che possiamo limitare le cifre decimali a 3: serviranno 10 bit per rappresentare la parte che segue la virgola.

Riportiamo in tabella 12 la nuova versione, definitiva, della Lut per il calcolo di So ed Sv.

LUT_HIGH

Precisione richiesta: per la parte intera sono necessari 10 bit, poiché il valore massimo che si deve rappresentare è 1000. Anche la parte frazionaria richiede 10 bit in quanto non si va oltre le 3 cifre decimali per i numeri memorizzati nella Lut. In totale, i blocchi per il calcolo dei coefficienti S richiedono un’aritmetica a 20 (10+10) bit. Il coefficiente parametrico N è stato fissato definitivamente al valore 10, per quanto concerne i blocchi per il calcolo dei coefficienti S. Questa scelta è dovuta a due motivi. Il primo è che se N fosse minore di 10, non sarebbe più possibile discriminare tra gli ultimi due intervalli della Lut, per via della sensibilità fornita dal decimo bit della parte frazionaria. Il secondo motivo è invece una considerazione puramente architetturale: l’allocazione di 2 o 3 bit in più per una Rom di dimensioni così limitate, certamente non costituirà un problema di spreco di risorse in fase di sintesi.

Tabella 12. Lut per il calcolo di So ed Sv.

X ∈ Valore LUT 1 1000 ] 1.000 ; 1.001 ] 991 ] 1.001 ; 1.002 ] 956 ] 1.002 ; 1.003 ] 893 ] 1.003 ; 1.004 ] 812 ] 1.004 ; 1.005 ] 725 ] 1.005 ; 1.006 ] 639 ] 1.006 ; 1.007 ] 559 ] 1.007 ; 1.008 ] 488 ] 1.008 ; 1.010 ] 402 ] 1.010 ; 1.012 ] 310 ] 1.012 ; 1.014 ] 243 ] 1.014 ; 1.016 ] 195 ] 1.016 ; 1.018 ] 159 ] 1.018 ; 1.023 ] 118 ] 1.023 ; 1.029 ] 77 ] 1.029 ; 1.036 ] 50 ] 1.036 ; 1.049 ] 32 ] 1.049 ; 1.062 ] 19 ] 1.062 ; 1.075 ] 12 ] 1.075 ; 1.120 ] 7 ] 1.120 ; 1.180 ] 3 ] 1.180 ; 1.240 ] 1.535 ] 1.240 ; 1.300 ] 0.955 ] 1.300 ; 1.400 ] 0.620 ] 1.400 ; 1.500 ] 0.390 ] 1.500 ; 1.600 ] 0.280 ] 1.600 ; 1.750 ] 0.205 ] 1.750 ; 3.000 ] 0.105 ] 3.000 ; 60.000 ] 0.021 ] 60.0000 ; 120.000 ] 0.003 ] 120.0000 ; 180.000 ] 0.002

3.1.4 Dimensionamento dei moltiplicatori

I moltiplicatori presenti nello schema a blocchi dell’architettura generale hanno il compito di calcolare i prodotti So⋅ Fo ed Sv⋅Fv, i primi due addendi del numeratore dell’espressione di y(i,j). Dato che abbiamo scelto di percorrere la strada dell’aritmetica fixed point, la moltiplicazione tra numeri con parte frazionaria è banale, poiché sarà sempre riconducibile al prodotto tra interi, come se si stesse lavorando in codifica unsigned. E’ noto infatti che è sempre possibile, al momento di calcolare un prodotto togliere l’eventuale virgola presente nei fattori, ottenere quindi numeri interi, ed effettuare la moltiplicazione tra essi, per poi reintrodurre la virgola, in una posizione che dipende dal numero delle cifre della parte frazionaria dei fattori. Per fare un esempio, si supponga di voler calcolare il prodotto tra i fattori 1.500 e 2.250. Il risultato è 3.375 e può essere calcolato anche facendo il prodotto tra 1500 e 2250. Si ottiene 3375000. E’ sufficiente a questo punto posizionare la virgola facendola scorrere di 6 posizioni a partire dall’ultima cifra a destra verso sinistra, dato che i fattori avevano 3 cifre decimali ciascuno dopo la virgola, per un totale di 6 cifre. Questo ragionamento può essere esteso anche alla codifica binaria, semplicemente concatenando la parte frazionaria a quella intera, niente di nuovo quindi. Vediamo lo stesso esempio binario:

1.500 e 2.250 corrispondono ai numeri binari 01.10 e 10.01 Parte intera e parte frazionaria, supposta a 2 bit, sono state separate dalla virgola, cosa che tipicamente non si fa quando si esprimono i numeri in base 2. Facciamo dunque il prodotto tra 0110 e1001, il cui risultato è 110110. Posizionata la virgola, abbiamo 11.0110 che corrisponde a 21 + 20 + 2-2 + 2-3 = 2 + 1 + 0.25 + 0.125 = 3.375, dunque c’è corrispondenza in questo senso tra i sistemi di numerazione decimale e binario. Ne segue che per il dimensionamento dei moltiplicatori potremo seguire la legge per la moltiplicazione tra numeri unsigned: “Il prodotto tra fattori rappresentabili rispettivamente su n e su m bit è rappresentabile su (n+m) bit.” [8]

La distinzione tra parte intera e parte frazionaria, se necessaria, potrà essere realizzata semplicemente a partire dal numero di bit dedicato alla parte frazionaria nei fattori d’ingresso.

Nel caso del prodotto S F⋅ abbiamo già stabilito che S è rappresentato su 20 (10+10) bit, mentre F è su 8 bit + ulteriori N bit per la parte frazionaria. I moltiplicatori daranno quindi in uscita un prodotto esprimibile su 18 + (10 + N) bit, dove al solito il primo numero si riferisce alla parte intera, mentre il secondo è relativo alla parte frazionaria.

3.1.5 Dimensionamento dei sommatori

In aritmetica fixed point la somma è ancor più semplice della moltiplicazione, in quanto la posizione della virgola non cambia. E’ possibile ancora una volta ragionare come se stessimo trattando numeri unsigned interi eliminando prima la virgola, effettuando l’operazione di somma, e rimettendo alla fine la virgola nella posizione in cui si trovava negli addendi. Ad esempio, volendo calcolare la somma tra 2.750 e 1.250, il risultato sarebbe ovviamente 4.000, a cui si potrebbe giungere sommando 1250 a 2750, ottenendo 4000. Resterebbe infine da scalare la virgola di tre posizioni per arrivare al risultato corretto.

Nel caso in cui gli addendi abbiano parte frazionaria a dimensione diversa, sarà necessario incolonnare adeguatamente i numeri aggiungendo al numero che presenta la parte frazionaria a dimensione minore una quantità di zeri pari alla differenza tra le dimensioni delle parti frazionarie dei due addendi, per non incorrere in errori. Per esempio, volendo calcolare la somma 1.25 + 1.5 passando agli interi si avrebbe 125 + 15 che fornirebbe 135, da cui inserendo la virgola si

otterrebbe il risultato 1.35, ovviamente errato. L’operazione corretta è 125 + 150 = 175 e con la virgola: 1.75. In binario: 1.01 + 1.1 da cui 101 + 110 =

1011. La virgola deve essere posizionata in modo da avere due bit per la parte frazionaria: 10.11 che corrisponde proprio a 3.75 in decimale.

3.1.5.1 Dimensionamento di Adder1

Si deve calcolare il numeratore dell’espressione di y(i,j), pertanto gli ingressi sono 3, in particolareSv Fv⋅ , Sv Fv⋅ ed y(i,j) stessa. Le dimensioni degli addendi, sono, rispettivamente, (18+N) per i primi due, e (8+N) per y. Per l’uscita, anziché

applicare regola generica “la somma di due addendi rappresentati su n bit è esprimibile su n+1 bit” [8] , si può pensare di effettuare un dimensionamento ottimo, realizzabile conoscendo il valore massimo raggiungibile dagli addendi. Essi infatti hanno una propria dinamica. Il prodotto dei coefficienti S ed F può raggiungere, al massimo, il valore: 1000 x 255 = 255000, dunque il numeratore ha come limite superiore: 2 x 255000 + 255 = 512255. Calcolando log2 512255 = 19 dunque l’uscita di adder1 ha dimensione (19 + N), perché in generale sarà presente una parte frazionaria di dimensione parametrica N.

3.1.5.2 Dimensionamento di Adder2

In questo caso si sta calcolando il denominatore dell’espressione originale di y(i,j), che è composto da tre termini: (So + Sv + 1). Gli ingressi del sommatore in questione sono però solo due, dato che uno di essi è costante. Consideriamo quindi soltanto So ed Sv che, come visto in precedenza, hanno dimensione pari a 20 (10+10) bit. Il valore massimo che la somma può raggiungere vale: 1000 + 1000 +1 = 2001, quindi sono necessari 11 bit per la parte intera più N per la parte frazionaria. In totale: (11+N) bit.

3.1.6 Rom per inversione di (So + Sv + 1)

Nella catena di destra, prima di giungere al blocco di moltiplicazione finale, c’è

un ulteriore circuito, il cui compito è quello di calcolare il reciproco di (So + Sv +1) affinché y(i,j) possa essere calcolata come prodotto di due fattori,

anziché come il loro rapporto. E’ molto importante infatti evitare di dover sintetizzare un divisore, che richiederebbe troppe risorse sulla FPGA e inficerebbe la velocità di elaborazione di tutto il sistema.

L’inversione del denominatore, come visto nel cap. 2 par. 2.4.6 è stata realizzata per mezzo di una Rom o Lut contenente i valori del denominatore preventivamente invertiti. Si tratta di una memoria da 2441 locazioni in cui sono presenti altrettanti valori campionati della funzione da invertire.

Le strategie di campionamento sono già state descritte nel capitolo 2, l’obiettivo di questo capitolo è il problema del dimensionamento dell’aritmetica di macchina.

Una volta deciso come operare la quantizzazione, il passo successivo è quello di scrivere i 2441 valori di 1/( So + Sv +1) nella Lut che sarà simulata in VHDL come una Rom da precaricare. Andando a calcolare tali numeri, servendoci di una funzione Matlab realizzata per la circostanza, ci si rende conto di avere a che fare con valori molto piccoli. In particolare il range è [ 1/2001 ; 1/1.004] = [0.000499 ; 0.996]. Ci sono dunque problemi di compatibilità con l’aritmetica del nostro sistema, che sappiamo essere al più a 3 cifre decimali per la parte frazionaria. Per risolvere la questione scegliamo di applicare un fattore di scala, ovvero non calcoliamo 1/( So + Sv +1) ma K/( So + Sv +1). Logicamente al momento del calcolo di y come moltiplicazione, sarà necessario dividere per K. Se scegliamo come valore di K una potenza di 2, la moltiplicazione e la divisione per K saranno banalmente realizzabili rispettivamente aggiungendo e togliendo degli zeri ai numeri calcolati di volta in volta: come si dice, un’operazione a complessità nulla. Osservando i numeri generati dal programma Matlab sopra indicato, si è scelto di porre K = 4096 in modo che i numeri da trattare tornino ad essere compatibili con l’aritmetica a 3 cifre frazionarie. Dunque nella Lut scriveremo valori moltiplicati per 4096 e al momento del calcolo di y come prodotto, il moltiplicatore descritto in VHDL effettuerà uno shift verso destra di 12 posizioni ( 212 = 4096 ), sul numero ottenuto dalla moltiplicazione.

Il massimo numero da rappresentare è 4096 ⋅ 0.996 = 4079.616, quindi servono 12 bit per la parte intera e N per la parte frazionaria. Globalmente: (12 + N).

3.1.7 Calcolo della luminanza y(i,j)

All’inizio di questo capitolo abbiamo affermato, sulla base di ragionamenti intuitivi, come i valori assumibili da y(i,j) fossero numeri positivi al massimo pari a 255. Dimostriamo ora questa assunzione, per poter procedere al dimensionamento del blocco per il calcolo della luminanza: cerchiamo di trovare il valore minimo ed il valore massimo.

Valore minimo: in teoria dovremmo minimizzare il numeratore e massimizzare il denominatore, ma purtroppo numeratore e denominatore non sono indipendenti, visto che entrambi contengono i termini So ed Sv.

Studiamo dunque i due casi separatamente:

1) minimizziamo il numeratore ponendo So ed Sv al loro valore minimo, così facendo però si rende minimo anche il denominatore:

2 0.002 1 1 1.004

( , ) 1

2 0.002 1 1.004

y i j = ⋅ ⋅ + = =

⋅ +

2) massimizziamo il denominatore ponendo So ed Sv pari al loro valore massimo, minimizzando per quanto possibile il numeratore:

2 1000 1 1 2001

( , ) 1

2 1000 1 2001 y i j = ⋅ ⋅ + = =

⋅ +

Dunque il valore minimo è 1.

Valore massimo: in teoria dovremmo massimizzare il numeratore e minimizzare il denominatore, ma abbiamo lo stesso problema di prima.

Proviamo dunque i due casi separatamente:

1) massimizziamo il numeratore ponendo So ed Sv al loro valore massimo, così facendo però si rende massimo anche il denominatore:

2 1000 255 255 510255

( , ) 255

2 1000 1 2001

y i j = ⋅ ⋅ + = =

⋅ +

2) minimizziamo il denominatore ponendo So ed Sv pari al loro valore minimo, massimizzando per quanto possibile il numeratore:

2 0.002 255 255 256.02

( , ) 255

2 0.002 1 1.004

y i j = ⋅ ⋅ + = =

Dunque il valore massimo è proprio 255. Effettivamente y(i,j) assume i valori tipici dei pixel, compresi tra 1 e 255.

In uscita, quindi servono 8 bit per la parte intera più N per la parte frazionaria. Globalmente (8 + N) bit. Gli ingressi sono invece l’uscita di adder1 e l’uscita della rom per l’inversione, rispettivamente rappresentati su (19 + N) e (12 + N). Il vero prodotto ottenuto, prima dello shift sarebbe su (31 + 2N) bit, a causa del fattore moltiplicativo K applicato dalla Rom per l’inversione.

3.

2

D

:

N

Lo studio che segue è stato condotto interamente in ambiente C, servendoci di Matlab per la verifica dei risultati. Per limitare il numero di bit dopo la virgola, è stata realizzata la semplice funzione cutfloat, il cui codice è riportato in appendice. Cutfloat riceve ingresso un valore di tipo float con numero di cifre decimali di parte frazionaria al massimo pari a 6 e restituisce un nuovo valore float ma con numero di cifre decimali e quindi di bit fissato. Il procedimento con cui è possibile simulare l’operazione di troncamento di una parte del valore dopo la virgola è il seguente: per mezzo della funzione floor predefinita in C è possibile prelevare la sola parte intera del numero in ingresso, eliminando tutto ciò che è presente dopo la virgola. Si può dunque pensare di spostare la virgola stessa per prelevare la parte frazionaria di dimensione voluta, essenzialmente con una prima moltiplicazione per una costante, poi applicando floor e quindi dividendo ciò che si è appena ottenuto per la costante usata prima. Per chiarire quanto detto a parole, vediamo un esempio pratico. Si supponga di avere a disposizione il numero reale 2.27 che corrisponde, al binario: 10.01000101... e di volerlo rappresentare con N pari a 2.

Applicando la funzione cutfloat:

1) 2.27 viene moltiplicato per 2N = 4 ⇒ 2.27 · 4 = 9.08 2) viene applicata la funzione floor ⇒ floor(9.08) = 9 3) il risultato di floor viene diviso per 2N ⇒ 9 / 4 = 2.25

Il numero ottenuto corrisponde al binario a 10.01. La simulazione del troncamento è avvenuta con successo. Ovviamente si è perso qualcosa in termini di precisione,

siamo infatti passati da 2.27 a 2.25, ottenendo in questo caso un errore percentuale del (2.27-2.25) / 2.27 x 100 = 0.88 %. Questo è evidente, in quanto sappiamo che nella rappresentazione in binario, i bit della parte frazionaria hanno peso pari a 2K con K intero minore od uguale a 0. Tagliando alcuni di questi bit, si perde dunque in precisione. In particolare sarà molto più difficile, se non impossibile, distinguere tra numeri molto vicini come ad esempio 1.001 e 1.002.

La funzione cutfloat dovrà essere invocata, nel codice C, ogni volta che si esegue un calcolo, a monte ed a valle di esso. Sarà quindi come limitare la parte frazionaria, per un blocco dell’architettura generale, in ingresso ed in uscita. Sfortunatamente, operando in questo modo, non si può comunque limitare la precisione dei calcoli intermedi effettuati dal processore, ci aspettiamo dunque di ottenere dei risultati che saranno rispettati in modo soddisfacente dall’implementazione definitiva in VHDL, ma non alla perfezione. In altri termini, mettiamo in conto finora un’ulteriore perdita in termini di PSNR, quando passeremo dall’algoritmo finale C all’implementazione hardware.

Vediamo quindi nella tabella 13 le prestazioni al variare delle cifre decimali da 1 a 6. Cifre parte frazionaria Dimensione p. fraz (N) Prestazioni medie (dB) Swan.img (dB) Bedroom.img (dB) Alpi.img (dB) 1 4 27.73 29.62 26.63 26.95 2 7 38.25 40.58 36.73 37.45 3 10 39.45 40.43 38.48 39.45 4 14 39.41 39.99 38.69 39.57 5 17 39.42 39.99 38.70 39.58 6 20 39.43 39.99 38.71 39.58

Tabella 13. Prestazioni dell’algoritmo linearizzato al variare del dimensionamento.

Al solito, nel calcolo del PSNR abbiamo usato come termine di confronto l’immagine di uscita ottenuta con l’algoritmo ret_soft.exe. Per immagine di uscita intendiamo l’uscita del sistema completo, nel quale le parti che non interessano

questo lavoro (blocchi a valle del divisore per il calcolo della riflettanza) sono state lasciate nella forma software come in ret_soft.exe e sono stati impostati per esse i parametri di default.

Le immagini da valutare sono quelle di uscita ottenute con l’algoritmo linearizzato, formulato in seguito ai processi di semplificazione illustrati nel capitolo 2, con Lut a 32 words per il calcolo di So ed Sv, Rom per inversione del valore (So + Sv + 1) e moltiplicatore con shift per il calcolo della luminanza.

Chiariamo ancora di più la situazione con alcuni diagrammi, in figura 41, che mettono a confronto la dimensione della parte decimale con la prestazione media in termini di dB sulle tre immagini di prova:

Figura 41. PSNR vs. numero cifre decimali

Dalla tabella e dai grafici si evince che le prestazioni migliori si ottengono nel caso di 3 cifre decimali, dopodichè il PSNR tende a saturare. Scegliamo dunque di procedere con 3 cifre decimali, per le quali è necessario allocare 10 bit. Dunque N = 10. Torniamo sull’andamento del PSNR nel caso di numero di cifre decimali

maggiore di 3. Si può notare che, raggiunto il valore massimo il PSNR anziché rimanere costante, come dovrebbe, diminuisce leggermente. Ciò è dovuto all’aver fissato la parte frazionaria dei valori della Lut a 3 cifre. Infatti, la Lut introduce un errore di quantizzazione sul calcolo di So ed Sv, mentre un’altra fonte di errore è il troncamento della parte frazionaria dei numeri. Al variare delle cifre decimali da 1 a 6, il primo contributo, dovuto alla Lut, è costante perché la Lut è sempre la solita, viceversa il secondo contributo dovuto al troncamento é massimo quando si usa 1 cifra decimale e diminuisce progressivamente. Il risultato sarebbe un aumento monotono della prestazione sull’immagine ottenuta, ma questo non può avvenire perché quando le cifre decimali superano il valore 3, la precisione imposta dalla LUT limita la prestazione del sistema. Allora il PSNR anziché saturare, in realtà tende mediamente a calare perché dalle simulazioni emerge che quando si introducono più cifre decimali di quelle imposte dalla Lut, non sempre vengono aggiunti degli zeri, ma valori vicini ( 1 o 9 ). Compare quindi una nuova fonte di errore. Per portare un esempio, se vogliamo scrivere il numero 26.3 con 5 cifre decimali dovrei avere 26.30000, in realtà, molto probabilmente, avremo valori del tipo 26.30001 o 26.29999. Dunque, il nuovo errore aumenta all’aumentare delle cifre decimali e quindi il PSNR tende a diminuire.

Come giustificazione di quest’ultimo ragionamento, è stato fatto un test con delle ulteriori versioni di ret_soft in cui il calcolo di So ed Sv è effettuato in modo esatto, e viene variata la dimensione della parte frazionaria. Come anticipato, la prestazione, in termini di PSNR, aumenta con la dimensione della parte frazionaria. Riportiamo nella tabella 14 i risultati, che si riferiscono all’immagine bedroom.img. Le altre immagini hanno fornito dati più o meno analoghi.

Dimensione parte frazionaria (Numero Cifre)

Calcolo esatto di So e Sv (dB) Lut_High (dB) 1 29.53 29.92 2 47.00 47.00 3 59.38 53.55 4 69.32 53.87 5 78.87 53.86 6 88.53 53.86

Tabella 14. Confronto tra prestazioni degli algoritmi ideale e linearizzato al variare del

Come possiamo notare, i dati della seconda colonna sono crescenti all’aumentare della dimensione della parte frazionaria. Nella terza colonna invece, ci sono le prestazioni fornite dall’algoritmo completo di Lut. Le prestazioni sono pressoché identiche finché si utilizzano 1 o 2 cifre decimali, poi si ha un massimo che in questo caso particolare è ottenuto per 4 cifre decimali ( ma mediamente lo si ha per 3 cifre) quindi tendono a calare leggermente.

Concludiamo che la scelta N = 10 che corrisponde ad avere 3 cifre decimali dopo la virgola, ci consente di ottenere immagini di ottima qualità.

3.2.1 Calcolo della riflettanza r(i,j)

Per il calcolo della riflettanza r(i,j) è necessario effettuare il rapporto tra I(i,j) ed y(i,j), vale a dire tra l’immagine originale e la stima di luminanza. Per il momento supponiamo di dover calcolare r(i,j) come da definizione, ovvero per mezzo dell’operazione di divisione. Nel cap. 4 vedremo come sia possibile realizzare tale calcolo.

Cerchiamo di indagare sulla dinamica del segnale di riflettanza. Intuitivamente, essendo il rapporto pixel a pixel tra matrici i cui valori non saranno molto diversi, perché comunque l’immagine stima di luminanza è semplicemente l’originale sottoposta a filtraggio passa basso, la matrice r(i,j) avrà valori non troppo diversi da 1. Servendoci di un’indagine statistica i cui risultati sono presentati per mezzo di istogrammi, verifichiamo la validità di questa supposizione.

Figura 42. Istogramma per l’immagine di riflettanza calcolata per swan.img.

Figura 43.Istogramma per l’immagine di riflettanza calcolata per bedroom.img.

Dall’ispezione degli istogrammi possiamo trarre due conclusioni: la prima, che la distribuzione dei valori di riflettanza è statisticamente la stessa per qualsiasi tipo di immagine e la seconda è che i valori di r(i,j) sono compresi tra 0 e 1.417 con picchi molto marcati nei pressi del valore 1. La scala orizzontale degli istogrammi, ovvero del valore di pixel, è infatti amplificata del fattore 127. In fase di salvataggio dell’immagine di riflettanza il codice C provvede a moltiplicare per questa costante tutti i valori di r, al fine di poter rendere visibile su schermo l’immagine stessa. Dunque i valori presenti sull’asse orizzontale delle figure 42,43,44 devono essere divisi per 127 per ottenere i valori effettivi della matrice r(i,j).

3.2.1.1 Dimensionamento parte intera

I risultati di questa indagine statistica sono molto importanti: in teoria si potrebbe decidere di allocare un solo bit per rappresentare la parte intera della riflettanza, mentre per la dimensione della parte frazionaria sarà condotta un’ulteriore indagine più avanti. Per essere sicuri di non incorrere in casi particolari che potrebbero essere stati trascurati con il set di immagini a disposizione, riserviamo un bit in più di quello che sembrerebbe sufficiente per rappresentare la parte intera di r. Dunque, allochiamo 2 bit per il valore che precede la virgola per quanto concerne la riflettanza. In questo modo r(i,j) potrà assumere 3 come massimo valore intero.

3.2.1.2 Dimensionamento parte frazionaria

Deciso il numero di bit da riservare per rappresentare la parte intera della riflettanza, lo stesso si deve fare per la parte frazionaria. Al fine di raggiungere tale obiettivo, sono stati effettuati dei test sul PSNR calcolato tra le immagini di riflettanza generate con l’algoritmo ottimo Ret_soft.c e le immagini che scaturiscono in seguito alla limitazione della dimensione della parte frazionaria nel calcolo di r(i,j). Il troncamento di parte delle cifre dopo la virgola è stato realizzato applicando la solita funzione cutfloat all’algoritmo originale preso come riferimento, di cui sono state create ulteriori versioni in cui solo il calcolo

della riflettanza è stato modificato come appena detto. In questo caso si è preferito procedere a partire dall’algoritmo ottimo e non da quello implementato nel capitolo 2, per quantificare gli effetti del troncamento della parte frazionaria per r(i,j) evitando di introdurre gli errori generati da altre operazioni di approssimazione come linearizzazioni e quantizzazioni.

Si osservi la tabella 15 in cui sono riportati i valori del PSNR per ogni immagine ed il valore mediato su tutte le immagini, al variare della dimensione della parte frazionaria del segnale di riflettanza.

Cifre parte frazionaria Dimensione p. fraz (N) Prestazioni medie (dB) Swan.img (dB) Bedroom.img (dB) Alpi.img (dB) 1 4 36.10 34.15 38.87 35.29 2 7 37.02 34.25 40.63 36.19 3 10 36.56 33.97 39.73 35.99 4 14 36.54 33.94 39.68 35.99 5 17 36.54 33.94 39.68 35.99 6 20 36.54 33.94 39.68 35.99

Tabella 15. PSNR medio e sulla singola immagine di riflettanza, al variare della dimensione della

parte frazionaria.

Possiamo notare che anche con una sola cifra dopo la virgola, i risultati sono soddisfacenti, essendo sempre superiore al target stabilito, 30 dB di PSNR. Teniamo presente, però, che impiegando l’algoritmo semplificato, avremo valori sicuramente minori, anche perché la limitazione della parte frazionaria sarà applicata su tutto il sistema, mentre in questo caso è stata introdotta solo nel calcolo di riflettanza. Aumentare il valore di N porta dei benefici, ma per N maggiore di 7, ovvero nel caso di 2 cifre decimali, i valori di PSNR saturano e, paradossalmente, le prestazioni diminuiscono leggermente. La soluzione ottima sembrerebbe dunque essere quella con N = 7. Vedremo più avanti, nel prossimo paragrafo se sarà possibile adottarla.

3.3 M

In quest’ultima parte riassumeremo le scelte operate sul dimensionamento per ciascun blocco dello schema di figura 40 a pag. 73 e prenderemo una decisione sul problema lasciato in sospeso, quello del numero di bit da riservare alla parte frazionaria della riflettanza. Infine, saranno fornite le immagini prodotte dall’algoritmo modificato in seguito alle scelte architetturali operate nel cap. 2 ed al dimensionamento fin qui condotto. Sarà così possibile affiancare ai risultati del PSNR, l’ispezione visiva per un’indagine completa sulle prestazioni dell’algoritmo proposto.

Riepilogo dimensionamento:

Blocco Dimensionamento

Ingresso dati Ram X 8

Calcolo coefficienti S 20 (10+10) Calcolo coefficienti F 18 (8+10) Moltiplicatori 28 (18+10) Sommatore Adder1 29 (19+10) Sommatore Adder2 21 (11+10) Rom_Inversion 22 (12+10) Uscita di luminanza 18 (8+10)

Tabella 16. Riepilogo del dimensionamento.

E’ possibile, a questo punto, aggiornare lo schema a blocchi parametrico, rendendo effettiva la scelta N = 10. Il nuovo schema è riportato in figura 45 alla fine del capitolo.

3.3.1 Dimensionamento definitivo della riflettanza

Nel paragrafo 2.1 del presente capitolo, avevamo scelto di allocare 2 bit per la parte intera del segnale stima di riflettanza r(i,j), mentre era rimasto aperto il problema del dimensionamento della parte frazionaria. Una scelta soddisfacente

era quella di riservare 7 bit per la parte dopo la virgola, dato che le simulazioni avevano fornito eccellenti risultati.

Per la scelta finale del parametro N per la riflettanza, si deve tener presente che la matrice r(i,j) dovrà essere salvata su una memoria, in modo da poterla rendere disponibile per i blocchi che si trovano a valle del divisore di riflettanza. Quindi, anziché implementare una ram dedicata, che richiederebbe molte risorse della FPGA di arrivo, si può pensare di sfruttarne una tra quelle che già abbiamo definito. Sono disponibili le ram X ed Y, le cui celle hanno dimensione, rispettivamente, 8 e 18 bit. A parte questo, il vero problema di cui si deve tener conto è il fatto che, sfruttando una ram già presente, avremmo una ram condivisa a tempo, nel senso che in istanti diversi essa è utilizzata da parti diverse del sistema. Per la ram Y ci sono però grosse difficoltà, dato che questa viene utilizzata come memoria d’ingresso dati e per salvare le elaborazioni intermedie, mentre risulta più ovvio far uso della ram X, i cui dati, una volta precaricati nella fase di start, non vengono più modificati, se non al momento di acquisire un nuovo frame. Possiamo dunque scegliere la ram X per salvare la matrice r(i,j) e renderla disponibile per il secondo sistema, sfruttando anche il fatto che le sue locazioni hanno dimensione pari a 8 bit. Sorge però un nuovo problema: è necessario che il sistema responsabile dell’elaborazione dei segnali luminanza e riflettanza (Retinex_B) sia provvisto di proprie memorie su cui salvare tali dati, altrimenti non sarà possibile per il nostro sistema acquisire nuovi frame da elaborare finché Retinex_B non ha elaborato tutti i pixel. Supponiamo di trascurare tali questioni.

Abbiamo dunque 8 bit disponibili per rappresentare la riflettanza e di questi, 2 saranno riservati alla parte intera ed i restanti 6 saranno impiegati per la parte frazionaria. Raggiungeremo così, per r, prestazioni molto vicine a quelle ottime. Dunque il parametro N, per il divisore di riflettanza, e per la riflettanza in generale, vale 6, o, se si preferisce mantenere N fisso a 10 come parametro

generale per il sistema, possiamo dire che la dimensione parametrica è 8 [2 + (N-4)]. Nel capitolo 4 sarà implementato un divisore semplificato per

calcolare la riflettanza su 8 bit, di cui 2 per la parte intera ed i restanti 6 per la parte frazionaria.

Figura 45. Schema a blocchi dell’architettura del filtro RRF,completo di dimensionamento.

Nella figura 46 disponibile nella pagina seguente, riportiamo le immagini elaborate dall’algoritmo originale nella colonna di sinistra, e quelle ottenute dalla versione C modificata nella colonna di destra. A pagina 97 sono invece riportate le immagini relative all’uscita di luminanza. Seguono delle tabelle riassuntive delle prestazioni raggiunte nei due casi.

Figura 46. Confronto tra immagini di uscita prodotte dall’algoritmo ideale e dal linearizzato. Prestazioni medie (dB) Swan.img (dB) Bedroom.img (dB) Alpi.img (dB) 39.45 40.43 38.48 39.45

Tabella 17. Prestazioni ottenute dall’algoritmo linearizzato (con blocchi a valle del filtro

Figura 47. Confronto tra immagini di luminanza prodotte dall’algoritmo ideale e dal linearizzato. Prestazioni medie (dB) Swan.img (dB) Bedroom.img (dB) Alpi.img (dB) 36.88 38.06 40.98 31.59

Tabella 18. Prestazioni ottenute dall’algoritmo linearizzato (con blocchi a valle del filtro