Elaborazione delle immagini - Algoritmi

SKELETONIZATION

Attraverso l’operazione di erosione, è definito un metodo per ricavare lo scheletro degli oggetti, cioè l’intelaiatura filiforme che

ne descrive la struttura.

NOTA 1 - Lo scheletro degli oggetti costituisce un’informazione utile a classificarli, considerando una quantità ridotta di pixel

significativi in luogo dei pixel che li compongono per intero.

NOTA 2 - Intuitivamente, lo scheletro è definito come la linea di estinzione lungo la quale si incontrano e si elidono gli incendi

ipoteticamente innescati lungo il contorno dell’oggetto considerato, supponendo che quest’ultimo sia composto, in massima

parte, da materiale infiammabile.

NOTA 3 - Lo scheletro risulta, quindi, da una sorta di thinning degli oggetti.

1 Si erode l’oggetto tante volte quante sono necessarie per rimuoverlo completamente dall’immagine. Ad ogni passaggio ,

si considera la differenza tra l’erosione e l’apertura di quest’ultima.

2 L’unione delle differenze effettuate costituisce lo scheletro dell’oggetto.

( ) ) ) ( )

{( [( ] }

⋃ 17

Lo scheletro di un oggetto approssima la Medial Axis Transform (MAT), cioè l’operazione che restituisce il luogo dei punti la cui

distanza dai bordi dell’immagine è massima.

La MAT deriva, a sua volta, dalla Distance Transform (DT), l’operazione che costruisce l’immagine in scala di grigi proporzionale

alla distanza di ciascun pixel dal bordo.

NOTA - Sostanzialmente, la MAT corrisponde ai punti di massimo della DT.

6.4 Algoritmo Watershed

IDEA CHIAVE Le immagini possono essere interpretate attraverso un criterio topografico, secondo il quale il livello di grigio

associato ai pixel ne rappresenta la “quota”. Sulla base di questa interpretazione, si identificano:

 i punti (pixel) di minimo locale, in corrispondenza dei quali la quota è minima;

 i punti in pendenza, in corrispondenza dei quali una goccia d’acqua fluirebbe nella direzione del declivio;

 i punti di “picco”, in corrispondenza dei quali una goccia d’acqua potrebbe fluire in più direzioni diverse.

Le regioni all’interno delle immagini corrispondono, quindi, a bacini idrografici (catchment basins), caratterizzati da una quota

minima e da un insieme di pixel tendenti ad essa. I pixel di picco costituiscono, invece, gli spartiacque (watershed lines) che

suddividono le regioni adiacenti.

PRINCIPIO Le immagini possono essere segmentate semplicemente trovando le linee di demarcazione che costituiscono gli

spartiacque tra una regione e l’altra.

Si immagina di allagare ciascuna regione a partire dalla quota minima. Non appena i bacini adiacenti confluiscono l’uno

nell’altro al crescere uniforme del livello dell’acqua, si erige la diga corrispondente alla loro separazione. L’allagamento

prosegue fino a sommergere, dighe escluse, l’intera immagine (cioè fino al raggiungimento del livello di grigio massimo).

ALGORITMO ( ) [ ]…

Data l’immagine in scala di grigi, che associa a ciascun pixel un tono di grigio

1 [Inizializzazione] Poni al minimo l’indice corrispondente al “livello dell’acqua”, cioè (essendo il minimo tono di

grigio ammesso dall’immagine ). ( )

Inizializza l’insieme , corrispondente all’unione dei bacini al passo .

( )

⋃

NOTA 1 - Il termine indica l’ -esimo punto di minimo locale entro l’immagine , tra gli minimi presenti.

( )

NOTA 2 - Chiamati gli bacini idrografici facenti capo al rispettivo punto di minimo locale , l’insieme dei

bacini all’ultimo passo ( ) corrisponde alla loro unione: ( )

⋃

Inizializza l’insieme di tutti i pixel sommersi dal livello dell’acqua al passo .

( )

{ | } ( )

NOTA 1 - Geometricamente, appartengono all’insieme tutti i pixel collocati sotto il piano di equazione .

NOTA 2 - Si noti che l’ -esimo bacino al passo è pari all’intersezione di tutti i suoi pixel con l’insieme dei pixel sommersi,

( ) ( )

ossia .

Poni .

NOTA - A seguito dell’inizializzazione, gli insiemi e sono costruiti in funzione dei loro elementi al passo precedente

( e ), poiché possono esclusivamente crescere o restare invariati.

2 [Passo iterativo] Finché ()…

Incrementa , ossia , ed aggiungi all’insieme i pixel sommersi per effetto dell’incremento.

Chiamate le generiche componenti connesse incluse nell’insieme , costruisci in funzione di considerando ogni

secondo la seguente valutazione:

 se , la componente corrisponde a un nuovo minimo locale e va incorporata nell’insieme dei bacini al

passo corrente;

 se contiene un qualsiasi elemento dell’insieme , la componente è un’estensione di quel bacino e va

incorporata ad esso entro l’insieme ;

 se contiene due o più elementi dell’insieme , la componente corrisponde ad altrettanti bacini che, al

crescere di , sono confluiti l’uno nell’altro, perciò occorre costruire una diga che li separi.

18

NOTA 1 - L’algoritmo Watershed è spesso applicato all’immagine del gradiente in luogo dell’immagine originale.

NOTA 2 - L’algoritmo può essere semplificato considerando, attraverso l’istogramma dell’immagine , i soli livelli di grigio

effettivamente presenti.

NOTA 3 - Per effetto del rumore o di dettagli irrilevanti, l’algoritmo può produrre immagini sovrasegmentate. Un metodo per

evitare il problema consiste nell’applicazione di un filtro di smoothing, che elimini le piccole irregolarità dell’immagine, e dalla

scelta dei cosiddetti marker: componenti connesse selezionate secondo particolari pattern, al fine di discriminare i punti di

minimo rilevanti da quelli che attengono a depressioni insignificanti.

COSTRUZIONE DELLE DIGHE

Le dighe che separano le regioni dell’immagine sono costruite, all’occorrenza, attraverso l’operazione morfologica di

dilatazione, semplicemente portando il tono di grigio associato ai pixel che le compongono oltre il livello massimo ammesso

dall’immagine (normalmente a ).

Due o più bacini confluiscono quando, al crescere di , una componente connessa racchiude la loro estensione al passo

precedente ( ). La dilatazione dei due bacini al passo secondo un elemento strutturante quadrato di pixel

restituirebbe, entro l’estensione di , un unico oggetto. Perciò, è sufficiente selezionare i pixel di intersezione tra la dilatazione

dell’uno e dell’altro bacino per ottenere la diga da costruire.

In simboli, se, al passo , i bacini facenti capo ai punti di minimo locale e confluiscono, allora la diga che li separa risulta

dall’intersezione: ( ) ) ( ( ) ))

(( [ ]

19

7 Codifica JPEG

DEFINIZIONE

L’acronimo JPEG (dal nome del comitato Joint Photographic Experts Group) corrisponde allo standard internazionale per la

codifica e la compressione di immagini a colori o in scala di grigi. Pubblicato nel 1994 con la specifica JPEG baseline, è stato

esteso sei anni dopo con la specifica JPEG 2000.

NOTA - Lo standard JPEG definisce un metodo per trasformare le immagini in flussi di byte, non le modalità per memorizzarle su

un qualsivoglia supporto (es. i formati JFIF o EXIF, specificati a parte).

PIPELINE

La codifica JPEG si articola, essenzialmente, in tre fasi distinte.

Immagine L’immagine è tradotta in una rappresentazione più adatta alla

Trasformazione

e compressione, attraverso un’operazione tipicamente reversibile.

originale I valori che rappresentano l’immagine a seguito della

trasformazione sono ricondotti a un range più contenuto, attraverso

Quantizzazione un’operazione di approssimazione.

NOTA: Questa fase produce un’effettiva perdita di informazione.

I valori rappresentanti l’immagine sono ordinati e codificati nel

Flusso di modo più efficiente per ottenere la massima compressione.

Codifica

bit NOTA: Questa fase non produce perdite di informazione.

FASE DI TRASFORMAZIONE

1 Conversione dello spazio colore

I valori dell’immagine sono convertiti dallo spazio colore allo spazio colore : l’informazione che attiene alla

luminanza (la componente ) è separata dalle componenti cromatiche, per essere trattata diversamente.

Il sistema visivo umano è più sensibile alle variazioni di luminanza (di livello di grigio) che alle differenze cromatiche. La

conversione dello spazio colore consente di privilegiare la codifica della componente rispetto alla codifica delle

componenti e .

NOTA - La conversione dello spazio colore non è necessaria se l’immagine originale è in scala di grigi.

2 [Opzionale] Sotto-campionamento della crominanza

Le informazioni che attengono alla crominanza (le componenti e ) sono sotto-campionate rispetto all’informazione di

luminanza , per ottenere un tasso di compressione maggiore.

Solitamente, il passo di campionamento è stabilito in una delle seguenti proporzioni:

 4:4:4 - le componenti , e sono campionate alla stessa risoluzione, senza perdita di informazione;

 4:2:2 - le componenti cromatiche e sono campionate, in senso orizzontale, a un passo pari alla metà della

risoluzione riservata alla componente (in questo caso, l’informazione complessiva è ridotta di un terzo rispetto al

modello di campionamento loseless 4:4:4);

 4:2:0 - le componenti cromatiche e sono campionate alla metà della risoluzione riservata alla componente , sia

orizzontalmente, sia verticalmente (in questo caso, l’informazione complessiva è dimezzata rispetto al modello di

campionamento 4:4:4).

3 Suddivisione in blocchi

L’immagine è ripartita logicamente in blocchi di pixel, per semplificare i calcoli successivi.

NOTA 1 - Se le dimensioni dell’immagine non sono divisibili per , si usa replicare l’ultima riga e l’ultima colonna tante volte

quanto è necessario.

NOTA 2 - La suddivisione in blocchi tende a produrre un artefatto grafico noto come blocking artefact, particolarmente

20

visibile a tassi di compressione elevati. La specifica JPEG 2000 definisce una trasformata wavelet allo scopo di ridurre tale

effetto.

4 Applicazione della trasformata discreta del coseno

La trasformata discreta del coseno DCT (Discrete Cosine Transform), derivata dalla trasformata di Fourier, è applicata a

ciascun blocco di pixel dell’immagine campionata, per ottenere i coefficienti che la rappresentano nel dominio delle

frequenze. Tali coefficienti, reali, corrispondono all’ampiezza delle basi della trasformata, in combinazione (lineare) con le

quali ricostruiscono l’immagine originale.

( )

DCT per una funzione continua: ( ) )

∑ [( ]

⁄

NOTA - Il termine corrisponde alla frequenza delle basi cosinusoidali; qui è espressa in radianti al secondo

&f