ALGORITMO RETINEX C APITOLO 1 L’

C

APITOLO

1

L’

ALGORITMO RETINEX

L’algoritmo Retinex prende il nome dalla teoria omonima formulata nel 1971 da E. H. Land, scienziato americano che condusse numerosi studi sulla percezione del colore. Il nome della teoria deriva dalla contrazione dei due termini “retina” e “cortex”, ed il suo scopo è quello di riprodurre una qualità dell’occhio umano, ovvero il fatto che la percezione di un qualsiasi oggetto è indipendente dal modo in cui sia esso illuminato: un oggetto deve sembrarci sempre lo stesso, sia esso illuminato dal sole, o esposto ad illuminazione luce artificiale o immerso nell’ombra. La sensazione di luminosità non deve cambiare. Questo concetto viene definito costanza della luminosità o, più generalmente, costanza del colore. La teoria Retinex afferma che la sensazione del colore è strettamente legata alla riflettanza degli oggetti, cioè alla radiazione da essi riflessa, mentre la quantità di luce che raggiunge l’occhio è il prodotto della riflettanza per l’illuminazione dovuta a fattori esterni. Pertanto, l’abilità dell’occhio umano consisterebbe nella capacità di separare le due informazioni di illuminazione e riflettanza, riuscendo ad estrapolare indipendentemente dalla sorgente di illuminazione l’esatto colore

degli oggetti. Land iniziò con lo studio dei processi di costanza percettiva del colore in differenti contesti di illuminazione e dei molteplici strani casi di non rispondenza tra variazioni di luce e percezione visiva, considerati fino ad allora illusioni cromatiche, proprio in quanto non erano inquadrabili nell’ambito della teoria della percezione del colore elaborata da I. Newton prima e da T. Young e H.L.F. Helmholtz1 poi. Ad esempio, un quadratino grigio in campo rosso viene percepito come azzurro chiaro, mentre in campo giallo è percepito come verde. Analizzando tali fenomeni, ritenuti come trascurabili eccezioni in relazione alle concezioni ormai acquisite e sperimentate dagli altri studiosi, E. Land fece nuove osservazioni; ad esempio, osservò come un panno rosso visto ad una certa distanza attraverso un filtro gelatinoso rosso, appare come se fosse bianco. Allora Land ipotizzò che uno stesso colorante chimico poteva stimolare la formazione cerebrale di vari colori a seconda delle condizioni di illuminazione realizzate mediante filtri e ritenne che ciò avrebbe condotto ad una notevole semplificazione e conseguente diminuzione di costi della produzione fotografica. Land chiamò Retinex la sua innovativa teoria sulla percezione cerebrale del colore, proprio per indicare che le informazioni sulle condizioni di illuminazione, recepite dalla retina, vengono elaborate come confronto tra varie aree della corteccia cerebrale, per poi dare vita ad un’unica percezione cromatica finale per mezzo di una sorta di media. Quest’ipotesi di analisi per confronto è stata confermata dai moderni studi neurologici. Land proseguì le sue ricerche applicandole alle tecniche di stampa fotografica, giungendo al brevetto della nota fotocamera “Polaroid”, con processo di sviluppo istantaneo, nel 1937. In seguito si concentrò sui problemi relativi all’ acquisizione delle immagini con apparecchi ottici quali fotocamere in caso di scarsa illuminazione e, tentando di riprodurre il funzionamento fisiologico dell’occhio umano, capace di percepire adeguatamente i colori anche in condizioni non ottimali di luminosità, mise appunto vari algoritmi [1], tra cui il Retinex, omonimo della teoria su cui si fonda.

1 _{Visione tricromatrica del colore, o RGB che prevedeva l’esistenza di tre colori primari,}

L’algoritmo in questione può essere applicato non solo allo studio di immagini a colori, ma ad immagini monocromatiche, al fine di ottenere un controllo della luminosità ed un aumento del contrasto dove sia necessario. Proprio su questa applicazione si basa questo lavoro di tesi. A tutti sono noti i problemi che si presentano nell’acquisizione di immagini per mezzo di fotocamere o videocamere nel caso di condizioni critiche di illuminazione. Il rischio è quello di ottenere immagini sottoesposte e quindi con aree scure che nascondono dei dettagli dell’immagine. Nel caso di acquisizione analogica con impressionamento di una pellicola fotografica, è molto difficile, per non dire impossibile, migliorare la situazione, mentre nel caso di acquisizione digitale è possibile intervenire con software di fotoritocco per la correzione delle immagini.

Tali programmi fanno uso di algoritmi come il Retinex, che possono essere implementati al meglio facendoli girare sui potenti processori oggi disponibili. In questo lavoro ci proponiamo di realizzare un simile sistema che possa essere integrato sul dispositivo di acquisizione stesso, in modo da poter operare la correzione delle immagini in tempo reale, evitando così di dover intervenire successivamente. Si tratterà, dunque, di tradurre un software scritto sulla base dell’algoritmo in una qualche realizzazione hardware. Le possibili applicazioni di questo lavoro saranno: immagini statiche (fotografie), ma anche applicazioni dinamiche come la video sorveglianza ed altre acquisizioni in tempo reale. Obiettivi importanti da raggiungere sono: la programmabilità del sistema, in modo da ottenere diverse prestazioni a discrezione dell’utente, basso consumo in potenza, dato che si suppone l’impiego in dispositivi alimentati a batterie, ed infine il funzionamento in tempo reale. Questo problema è fondamentale nel caso di applicazioni dinamiche, in cui i frame da processare si susseguono continuamente ad una certa frequenza.

In tutta questa trattazione non si prenderà in considerazione il problema del colore, opereremo dunque su immagini monocromatiche. L’algoritmo di miglioramento di luminosità e del contrasto può essere esteso alle immagini a colori, seppur con qualche difficoltà.

I colori sono acquisiti secondo la modalità RGB, dunque abbiamo tre segnali monocromatici ( R,G,B ) oltre alla luminosità. L’alterazione del segnale

luminosità si ripercuoterebbe sulla dinamica dei tre segnali di colore; il risultato sarebbe una distorsione del colore dell’immagine. Si perderebbero dunque informazioni cromatiche. Volendo seguire questa strada, sarebbe necessario progettare un ulteriore sistema in grado di ristabilire i rapporti tra i colori nell’immagine ed in definitiva i colori originali. Si capisce che questa strada è troppo complicata e potrebbe rappresentare un bottle-neck per il funzionamento a tempo reale.

Una possibile alternativa consiste nell’operare in modo da separare la luminanza dall’informazione di colore, ma il problema è che la sensazione di colore non è del tutto del tutto indipendente dalla luminanza: nel buio ogni oggetto ci appare nero, anche se è di altro colore, mentre se c’è una buona illuminazione siamo in grado di percepire il colore. Sono stati studiati allora vari approcci alternativi e quello che dà i migliori risultati, comunque non eccezionali, è lo spazio HLS, in cui un colore è identificato dal segnale H (hue o tinta), mentre il segnale S (saturation o saturazione) regola l’intensità del colore (colore più chiaro o più scuro) e L è il segnale di luminanza. Se cambiamo L, la variazione di H ed S, segnali di colore, è, fortunatamente, trascurabile. Resterebbe comunque il problema del passaggio da modalità RGB a HLS. Tuttavia è molto più conveniente un’operazione di conversione tra spazi di colore, piuttosto che implementare un sistema di correzione del colore. Queste problematiche non sono oggetto di questo lavoro e sono rimandate a trattazioni future.

Concentriamoci sull’algoritmo Retinex applicato alla luminanza di immagini espresse su scala di grigio. Ne esistono varie versioni, in continuo aggiornamento, ma tra queste, prendiamo in considerazione quella messa a punto dagli studiosi dell’Università di Trieste [2].

L’algoritmo si basa sulla divisione di un’immagine I(n,m) nelle due componenti luminanza y(n,m) e riflettanza r(n,m). La prima contiene informazioni sulla luminosità locale e globale dell’immagine, ed è composta da componenti a bassa frequenza, mentre la seconda ha in sé le informazioni riguardanti i dettagli ed i contorni tra i vari soggetti dell’immagine, ed è dovuta alle componenti ad altra frequenza della variazione dei toni di grigio. Questi due segnali vengono poi elaborati con sistemi non lineari per ottenere, rispettivamente,

un aumento del contrasto e del dettaglio dell’immagine. Il segnale di uscita viene quindi ricostruito effettuando il prodotto pixel a pixel dei due segnali trattati.

La stima della luminanza viene ottenuta attraverso un sistema che sostanzialmente si comporta come un filtro passa basso e che vedremo in dettaglio.

Nel mondo digitale luminanza, riflettanza e qualunque immagine possono essere pensate come matrici di pixel. Le operazioni necessarie per le stime di luminanza e riflettanza, come prodotti, quozienti e somme, saranno dunque realizzate pixel a pixel. Si può immaginare di impiegare un sistema detto maschera in grado di raccogliere i valori dei pixel che servono e che spostandosi lungo le direzioni spaziali volute acquisisce i valori dei pixel adiacenti a quelli che già si sono elaborati, fino a percorrere tutta la matrice. Con questa tecnica è possibile cambiare il contrasto delle immagini in modo da rendere maggiormente visibili dei dettagli che si trovano in aree caratterizzate da differenti condizioni di illuminazione, aree chiare e aree scure.

Ottenuta la stima di luminanza, la stima di riflettanza è ottenibile per mezzo del rapporto tra immagine originale da processare e l’uscita di luminanza.

Il filtro RRF indicato nello schema a blocchi dell’algoritmo, in figura 1, ed il divisore che estrae la riflettanza r sono oggetto di questo lavoro, che chiamiamo Retinex_A, a differenza dei blocchi a valle, dei quali si fornisce solo l’espressione analitica dei relativi operatori, senza entrare nel dettaglio. Per maggiori approfondimenti si rimanda alle pubblicazioni degli studiosi di Trieste [3] e ad altri lavori che hanno come scopo la trattazione di tali blocchi [4], in un progetto dal nome Retinex_B.

Il blocco 1/ N è un adattatore di dinamica che trasla il range [0; 255] in [0 ; 1] ed il suo compito è quello di semplificare l’operazione compiuta dal blocco Γ, che opera l’aumento del contrasto globale dell’immagine, a seguito del quale viene effettuato uno stretching lineare al fine di massimizzare la dinamica dell’illuminazione.

Detto p il valore di pixel prelevato dall’uscita di luminanza y(n,m), Γ è esprimibile come una funzione esponenziale di p, in cui l’esponente è funzione di p stesso, in modo che al crescere di p aumenti anche l’esponente, il che corrisponde a schiarire molto le zone scure e meno le zone chiare. In simboli:

p

pγ⋅ +γ (1.1)

Il blocco β opera l’aumento del contrasto locale, tramite l’amplificazione del dettaglio ottenuta elaborando il segnale riflettanza r(n,m). Analiticamente:

⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ ≤ ≤ + − + ⋅ > < + + = − − ⋅ − 1 . 1 r 1 . 1 k r k r k log k 1 . 1 r , 1 . 1 r 2 1 e 1 1 ) r ( β 1 3 2 2 1 1 r log b (1.2)

I valori di k1, k2 e k3 vengono determinati in modo da assicurare la continuità della curva. Il parametro b, invece, rappresenta il fattore di scelta della maggiore o minore pendenza della curva.

Il blocco che esegue il linear stretching serve per riportare la dinamica nel range originale [0 ; 255]. Infine, l’immagine finale viene ricostruita per mezzo del prodotto dei segnali luminanza e riflettanza così elaborati.

1.1

S

:

RRF

Il primo tentativo per ottenere il segnale stima di luminanza fu quello di impiegare un filtro passa basso a banda fissata, ma si presentò subito il problema di come trattare i bordi, zone adiacenti ad alta ed a bassa luminosità: il filtro passa basso elimina le componenti ad alta frequenza che sono tipiche di queste aree. Laddove la luminosità variava bruscamente, si presentava il fastidioso effetto di fluttuazioni dell’illuminazione con fenomeni di overshoot e undershoot dovuti al fatto che il taglio delle alte frequenze non rendeva possibile transizioni rapide dell’illuminazione. Furono allora proposti altri metodi, tra cui quello di Jobson [5], che propose di far uso di un Retinex Multiscala (MSR), la cui uscita è una somma pesata di diversi operatori a singola scala. Ciascun pixel è definito in una scala con una funzione gaussiana con la relativa sigma associata.

L’alternativa migliore fu quella proposta da Ogata [6], il quale realizzò la stima della luminanza con un filtro non lineare passa basso accordabile in modo da poter decidere attraverso alcuni parametri le componenti frequenziali da reiettare. Dopodiché si seguiva un approccio multiscala, con un filtro IIR (Infinite Impulse Response) per integrare le stime della luminanza sulle varie scale.

Questo metodo, seppur efficiente, presenta delle notevoli difficoltà realizzative, a partire dal fatto che si rende necessario variare i parametri del filtro, poiché questi devono essere accordati in base alla luminosità dell’immagine da elaborare. Questo dà luogo ad un anello di retroazione nel sistema ed inoltre, l’integrazione delle componenti multiscala deve essere fatta con un coefficiente che possa variare sia spazialmente che sulla scala.

Si pensò allora di semplificare la situazione ricorrendo ad un filtro razionale, aumentando però la mole delle computazioni, dato che avendo ridotto la complessità delle operazioni, esse aumentano in quantità. In pratica servirebbero decine di iterazioni dello stesso calcolo e questo non è accettabile nel funzionamento real-time. Le ultime versioni dell’algoritmo fanno uso di un ulteriore tipo di filtro reazionato, ricorsivo e razionale, capace di adattare la propria banda di filtraggio a seconda di alcuni parametri locali di gradiente che informano il filtro sulla vicinanza di zone con brusche transizioni, in modo da

conservare i dettagli dell’immagine e di concentrare la sua opera laddove l’immagine è omogenea. In questo modo si riesce a schiarire l’immagine solo dove è necessario, senza perdere in qualità sui dettagli fini come si ottiene, invece, con un approccio lineare quale l’equalizzazione di istogramma. Un filtro di questo tipo non è lineare ma può essere visto come un filtro IIR con coefficienti, però, non costanti; da ciò deriva la non linearità. Un filtro del genere, in grado di raggiungere risultati tipici dei filtri razionali, ma con uno sforzo molto minore nella computazione dei calcoli, si indica con la sigla: RRF (Recursive Rational Filter).

Definita l’immagine di ingresso I(n,m) con n e m coordinate spaziali del piano, I viene vista, secondo questo modello, come il prodotto, punto per punto del segnale luminanza e del segnale riflettanza, anche esse funzioni di n e m. In simboli:

I(n,m) = y(n,m) r(n,m)⋅ (1.3)

Ottenuta la stima della luminanza attraverso il filtro RRF, la stima della riflettanza r(n,m) può essere ottenuta come rapporto tra I(n,m) e y(n,m) appena stimata.

L’espressione analitica da implementare per la stima di y(n,m) è:

(

)

(

)

dove So ed Sv si esprimono come:

o 2 10 K S = x(n-1,m)+1 log +δ x(n+1,m)+1 ⎛ ⎛ _⎞⎟⎞ ⎜ ⎜ ⎟_⎟⎟ ⎜ ⎜ _⎟⎟ ⎜ ⎜ ⎟⎟ ⎜ ⎝ ⎠ ⎝ ⎠ _{v 2} 10 K S = x(n,m-1)+1 log +δ x(n,m+1)+1 ⎛ ⎛ _⎞⎟⎞ ⎜ ⎜ ⎟_⎟⎟ ⎜ ⎜ _⎟⎟ ⎜ ⎜ ⎟⎟ ⎜ ⎝ ⎠ ⎝ ⎠ (1.5)

x(n,m) rappresenta l’attuale pixel di ingresso, y(n-1,m) e y(n,m-1) sono i precedenti pixel già elaborati lungo le direzioni orizzontale e verticale.

Il parametro α può assumere un qualunque valore compreso tra 0 e 1 e rappresenta il coefficiente ricorsivo. All’aumentare di α, l’effetto passa basso del filtro viene enfatizzato. Osservando l’espressione analitica di y(n,m) è possibile intuire che α rappresenta il peso dei pixel adiacenti a quello su cui è centrata la maschera. Si tratta di un’operazione di media pesata, volta all’eliminazione delle componenti ad alta frequenza, dovute alla riflettanza.

L’espressione è tipica dei filtri razionali in cui però i coefficienti non sono costanti: si ottiene una funzione non lineare. Se usassimo filtri lineari il risultato sarebbe l’introduzione di artefatti nell’immagine soprattutto ai suoi confini, dove si mescolano componenti ad alta e bassa frequenza difficili da estrarre con un passa basso. Il risultato sarebbe un’immagine schiarita uniformemente con perdita di molti dettagli, come si ottiene con una semplice operazione di equalizzazione di istogramma, come vedremo in seguito in un esempio visivo. Per evitare questi problemi è necessario schiarire l’immagine originale dove i dettagli sono pochi e diminuire il potere passa basso del filtro laddove sono presenti dettagli molto fini, al fine di preservarli. Il filtro RRF è, dunque, un sistema reazionato che, considerando i valori dei pixel vicini a quello attualmente in elaborazione, è in grado di valutare l’eventuale presenza di bordi, adattando così la propria banda a seconda del caso. Si parla ricorsività spaziale dell’operatore.

Nell’accordare la banda del filtro, entrano in gioco i coefficienti So ed Sv, che si chiamano Sensori di margine orizzontale e verticale. Essi prevedono al numeratore una costante impostabile, ed al denominatore una funzione non lineare. K è un opportuno coefficiente (tipicamente 0,01) utilizzato per dimensionare la risposta del sensore, mentre δ assume un valore molto piccolo (tipicamente 10-5) per evitare di avere divisioni per zero.

Maggiore è la componente del gradiente lungo queste due direzioni, minore è il valore rilevato dal sensore corrispondente. In aree uniformi di un’immagine, So e Sv assumono valori molto grandi ed il comportamento del filtro è quello tipico di un filtro passa basso IIR bidirezionale, poiché l’effetto equivalente è quello di aumentare il valore di α. Al contrario, lungo i bordi dell’immagine, dove c’e’ un forte contrasto, il valore di uno dei due o di entrambi i sensori, in dipendenza dalla direzione del bordo, diminuisce rapidamente ed il contributo sulla direzione

corrispondente nell’equazione del filtro è limitata. Ciò corrisponde ad abbassare bruscamente il valore del parametro di ricorsività α, ed al limite, si ottiene un filtro passa tutto, l’ideale per conservare il dettaglio.

Grazie a questi coefficienti si riesce ad accordare il comportamento del filtro in dipendenza dell’immagine che si sta elaborando. L’andamento dei coefficienti So ed Sv in funzione del termine argomento del logaritmo è riportato in figura 3.

Figura 3. Grafico di So ed Sv in doppia scala logaritmica .

Il filtro è in grado di ottenere prestazioni molto soddisfacenti, anche se si introduce sull’immagine di uscita una distorsione di fase, eliminabile con un filtro equalizzatore, oppure applicando il metodo dell’inversione dei tempi [7,8], estendendolo a due dimensioni. Si tratta di effettuare più scansioni dell’immagine, in modo da bilanciare il rumore di fase introdotto. In pratica, la maschera deve essere spostata in più direzioni sulla matrice dell’immagine da processare. L’ideale sarebbe fare 4 scansioni lungo le direzioni orizzontale e verticale, ma già con 2 scansioni si ottengono risultati accettabili. Vedremo che, fra l’altro, la conseguenza di incrementare il numero di scansioni sarà un aumento dell’effetto passa-basso, e dunque un miglioramento ulteriore delle prestazioni del filtro RRF.

1.2

N

Il divisore nello schema a blocchi di figura 1 ha il compito di estrarre l’immagine di riflettanza da quella originale e da quella di illuminazione. Queste ultime sono sottoforma di matrici di pixel la cui dinamica è compresa tra 0 a 255. Al fine di evitare divisioni senza senso del tipo 1

0 o 0 0

, l’operazione che viene eseguita in realtà è:

I(n,m) + 1 r(n,m)=

y(n,m) + 1 (1.6)

1.3

E

Nella figura 4 è riportato un esempio visivo del funzionamento del sistema globale, considerando anche le parti che non interessano questo lavoro. La prima immagine a partire dall’altro è l’originale sotto esposta. Nel livello immediatamente inferiore, da sinistra, seguono le immagini di luminanza e riflettanza prodotte dai blocchi oggetto di questa trattazione; scendendo ancora di un livello troviamo le immagini di luminanza e riflettanza come appaiono dopo le elaborazioni dei blocchi Beta e Gamma, ed infine l’ultima immagine l’uscita che scaturisce dal blocco di moltiplicazione finale.

L’algoritmo prevede anche dei parametri impostabili, che conferiscono al sistema un certo grado di programmabilità che sarà studiato più avanti. In questo esempio sono stati impostati dei valori di default per i parametri, vale a dire: K =0.01, α = 0.75 , Nc (Numero cicli di scansione) = 4, γ = 0.25, Beta = 4.

Infine, in figura 5 è possibile rendersi conto dei migliori risultati ottenuti con l’approccio non lineare Retinex rispetto ad un algoritmo lineare come l’equalizzazione di istogramma. Tale immagine può essere ottenuta in ambiente Matlab invocando la funzione predefinita histeq.

Figura 5. Immagini di uscita ottenute con l’algoritmo Retinex a sinistra, e con il metodo di equalizzazione di istogramma.

1.4

I

’

L’algoritmo Retinex, dal 1971 in cui è stato ideato, ha subito vari aggiornamenti nel tentativo di ridurre l’ingente mole di calcoli necessari per la sua applicazione, e per raggiungere prestazioni sempre migliori. In sostanza però non è stato possibile metterlo in pratica fino a che il progresso del calcolatore elettronico non ha reso possibile svolgere uno svariato numero di calcoli in tempi molto brevi. Negli ultimi anni sono dunque tornate di attualità teorie come questa, anche grazie all’avvento della fotografia digitale che ha permesso di acquisire immagini in formato numerico, l’ideale per un calcolatore. Sono così nati software di fotoritocco e di elaborazione delle immagini.

Nuovi problemi si sono presentati, quando si è pensato di implementare tali algoritmi direttamente sugli apparecchi fotografici e di videoripresa digitali, in modo da consentire la correzione anche real-time dei frame.

Innanzitutto due parole sulle modalità di acquisizione delle immagini. Tipicamente si utilizzano sensori CMOS a risposta lineare o logaritmica [9]. Per i primi vale la relazione (1.3), e sono impiegati di solito nelle applicazioni statiche come le fotografie. I sensori logaritmici sono così definiti in quanto la loro risposta all’eccitazione ha caratteristica logaritmica, tale che:

in questo modo le operazioni sopra definite di quoziente per l’estrazione della riflettanza e di prodotto per ricostruire l’immagini di uscita divengono, in dominio logaritmico, semplici differenze e somme. Questi sensori sono più costosi, ma rendono le computazioni più semplici ed in definitiva molto più rapide, infatti trovano impiego nelle applicazioni dinamiche come le riprese video in cui è necessario processare i frame uno dopo l’altro con specifiche di velocità molto stringenti per avere un filmato fluido.

In questo lavoro ci proponiamo di realizzare un dispositivo hardware in grado di implementare una versione di questo algoritmo la più fedele possibile all’originale. Sarà, comunque, necessario introdurre delle approssimazioni compatibili con le attuali possibilità operative dei moderni sistemi digitali, che non consentono di eseguire operazioni trascendenti come il logaritmo o l’esponenziale. Altri problemi saranno la scelta dell’aritmetica opportuna di macchina e la limitazione del consumo di potenza, problemi che non sorgono nel caso di implementazione software, poiché l’aritmetica è data dal processore, e non si deve tener conto dell’alimentazione del sistema, questione che invece sorge quando si ha a che fare con dispositivi portatili alimentati a batteria, come gli apparecchi fotografici.

Le operazioni di semplificazione necessarie per passare dal software al dispositivo hardware comporteranno un peggioramento delle prestazioni: cercheremo di limitare tali perdite prendendo come modello teorico l’algoritmo software.

Concludiamo con alcune considerazioni riguardanti le possibile tecnologie di implementazione. Nella tabella 1 sono riassunti i vantaggi e gli svantaggi di alcuni dei possibili approcci.

Tecnologia Prestazioni Flessibilità Tempi di progetto

Asic Ottime Bassa Alti

DSP Discrete Ottima Bassi

FPGA Ottime Buona Bassi

Tabella 1. Riassunto delle caratteristiche delle diverse tecnologie di implementazione.

Il trade-off costi-prestazioni suggerisce quindi l’implementazione su dispositivi FPGA (Field Programmable Gate Array).