Capitolo 4 ELABORAZIONE DI IMMAGINI

4.1 Introduzione

Per poter, a partire dalle foto scattate, mappare la rete neurale in un grafo e analizzarne le differenti proprietà quali la raggiungibilità dei nodi, è stato realizzato un algoritmo in Matlab che sfrutta numerose tecniche di elaborazione dell’immagine.

Quello dell’elaborazione delle immagini è un settore estremamente ampio e complesso e risulta difficile, nonché estraneo agli scopi di tale lavoro, descrivere una materia così estesa.

In questo capitolo ci limiteremo perciò a definire alcuni concetti chiave e ad esporre molto sinteticamente solamente le metodologie più utilizzate.

4.2 Le immagini digitali

Un’immagine digitale è una tabella di valori numerici, è una matrice di pixel, a ciascuno dei quali è associato un valore. [1]

Il pixel (Picture Element) è il più piccolo tra gli elementi che vengono visualizzati sullo schermo ed il valore ad esso associato ne rappresenta il colore.

Per un’immagine monocromatica o a livelli di grigio il pixel è definito da un solo valore numerico che rappresenta l’intensità luminosa dell’immagine in quel punto.

In un’immagine a colori il pixel è composto da tre valori numerici che rappresentano la quantità di rosso, verde e blu del colore dell’immagine in quel punto. Ogni colore, secondo l’acronimo RGB, può infatti essere definito come una combinazione dei tre colori fondamentali.

4.3 Elaborare le immagini

L’elaborazione dell’immagine mira alla modifica di un’immagine, finalizzata alla rimozione dei difetti di acquisizione ed al ripristino dell’immagine “vera”, oppure all’aumento della visibilità di alcune parti rispetto ad altre.

Lo scopo è l’estrazione dell’informazione “importante” dalle immagini: una struttura, una forma, un conteggio o un semplice si/no.

L’elaborazione dell’immagine può essere:

¾ reversibile: a partire dall’immagine elaborata è possibile riottenere l’immagine originale applicando le opportune trasformazioni inverse;

¾ irreversibile: non è più possibile riottenere l’immagine originale a partire da quella elaborata.

Gli operatori utilizzati per l’elaborazione si possono classificare in tre categorie:

™ operatori puntuali: il valore di ogni singolo pixel dell’immagine elaborata dipende solamente dal valore che esso aveva nell’immagine originale;

™ operatori locali: il valore di ogni singolo pixel dell’immagine elaborata dipende dal valore dei pixel di un suo intorno nell’immagine originale;

™ operatori globali: il valore di ogni singolo pixel dell’immagine elaborata dipende dal valore di tutti i pixel dell’immagine originale.

Gli algoritmi sono piuttosto complessi e vengono divisi, talvolta in modo arbitrario, in fasi.

La prima fase è detta pre-elaborazione. Si compone tipicamente di algoritmi quasi standard e serve per modificare l’immagine in modo che le successive fasi siano facilitate.

Nella fase di pre-elaborazione si cercano di compensare difetti tipici, inserendo correzioni geometriche (compensazione delle distorsioni degli obiettivi e delle distorsioni geometriche) e radiometriche (compensazione delle disuniformità di illuminazione).

Sempre nella fase di pre-elaborazione vengono utilizzati algoritmi standard quali l’estrazione dei contorni e la generazione di immagini binarie. La trasformazione dell’immagine da mappa a livelli di grigio a mappa binaria permette di ridurre molto la quantità dei dati da elaborare senza perdite significative dell’informazione utile.

Le fasi successive sono molto meno standard perché dipendono in modo maggiore dalla specifica applicazione.

4.4 Concetti base

Prima di descrivere gli operatori di elaborazione è necessario definire alcuni concetti base. [2]

4.4.1 Sistemi di coordinate

Le posizioni in un’immagine possono essere espresse in due sistemi di coordinate: coordinate del pixel e coordinate spaziali.

Nel sistema di coordinate del pixel l'immagine è trattata come una griglia di elementi discreti, ordinata dall'alto al basso e dalla sinistra alla destra, come illustrato dalla figura 4.1.

Figura 4.1 Sistema di coordinate del pixel

Il pixel è trattato come un'unità discreta, identificata unicamente da un singolo accoppiamento di coordinate (r, c).

L’origine del sistema è nell'angolo in alto a sinistra e il primo componente r (la fila) aumenta verso il basso, mentre il secondo

componente c (la colonna) aumenta verso destra. Le coordinate del pixel sono valori interi da 0 alla lunghezza della fila o della colonna.

Nel sistema di coordinate spaziali il pixel è pensato come una zona quadrata e le posizioni in un'immagine sono posizioni su un piano e sono descritte in termini di x e y (figura 4.2).

Figura 4.2 Sistema di coordinate spaziale

E’ da notare il fatto che la coordinata y aumenta verso il basso. Esiste una corrispondenza tra i due sistemi, in quanto le coordinate spaziali del punto centrale di un certo pixel sono identiche alle coordinate in pixel dello stesso pixel.

Tuttavia, ci sono alcune importanti differenze.

Nelle coordinate del pixel, l’angolo di sinistra superiore di un'immagine è (0, 0), mentre nelle coordinate spaziali questa posizione è (-0.5, -0.5). Questa differenza è dovuta al fatto che il sistema di coordinate del pixel è discreto, mentre il sistema

coordinate spaziale è continuo. Inoltre, l’angolo di sinistra superiore è sempre (0, 0) nelle coordinate del pixel, ma è possibile specificare un'origine non default per il sistema di coordinate spaziale.

Un'altra differenza potenzialmente confusionaria è in realtà dovuta alla convenzione. L'ordine dei componenti orizzontali e verticali è invertito nella notazione per i due sistemi: mentre, come detto sopra, le coordinate del pixel sono espresse come (r, c), le coordinate spaziali sono espresse come (x, y).

4.4.2 Definizione di vicinato

Consideriamo un certo pixel nella posizione (x, y).

Viene definito quattro-vicinato N4 l’insieme di pixel che hanno un lato in comune con il pixel considerato, ovvero l’insieme di pixel che si trovano rispettivamente nelle posizioni (x+1, y), (x-1, y), (x,

y+1), (x, y-1).

Viene definito vicinato diagonale ND l’insieme di pixel che hanno un vertice in comune con il pixel considerato, ovvero l’insieme di pixel che si trovano rispettivamente nelle posizioni (x+1, y+1),

(x+1, y-1), (x-1, y+1), (x-1, y-1).

Viene definito otto-vicinato N8 l’unione del quattro-vicinato e del vicinato diagonale.

Continuando in questo modo si possono definire i vicinati N12, N20,

Figura 4.3 Tipi più comuni di vicinato

4.4.3 Definizione di distanza

Il concetto di distanza si basa sul concetto di vicinato.

Dati tre pixel p=(x, y), q=(s, t) e z=(u, v), la distanza gode delle seguenti proprietà:

1) D(p, q)≥0 e D(p, q)=0 se e solo se p=q

cioè la distanza tra 2 punti è sempre una quantità positiva ed è nulla solo se i 2 punti hanno coordinate equivalenti;

2) D(p, q)=D(q, p)

cioè la distanza tra 2 punti non cambia invertendo il loro ordine;

cioè la distanza tra 2 punti p e z è minore o uguale alla somma delle distanze parziali che si possono calcolare introducendo un terzo punto q. Saranno uguali solo se il punto q giace sulla retta che passa per p e z.

Si hanno inoltre tre possibili modi per calcolare la distanza (figura 4.4):

Figura 4.4 Tipi di distanza

a) distanza euclidea:

D(p,q)=[(x-s)2+(y-t)2]1/2;

D=│x-s│+│y-t│;

c) distanza a scacchiera:

D=max(│x-s│,│y-t│).

4.4.4 Definizione di connettività

Due pixel si dicono connessi se appartengono alla stessa regione o classe di equivalenza.

La definizione di connettività dipende dal concetto di vicinanza. Consideriamo il pattern di pixel di contorno riportato in figura 4.5 e numeriamo le diverse posizioni in maniera univoca.

Figura 4.5 Intorno del pixel X

Supponiamo inoltre, per semplicità, di avere un’immagine binaria, ovvero un’immagine in cui ogni pixel può avere solamente due valori: 1 o 0.

Il generico pixel binario F(x,y)=X, dove X=0 (bianco) o X=1 (nero), è circondato dagli 8 pixel più prossimi.

9 Il pixel X si dice 4-connesso ad un oggetto se almeno uno dei pixel ad esso 4-vicino ha il suo stesso valore.

9 Il pixel X si dice 8-connesso ad un oggetto se almeno uno dei pixel ad esso 8-vicino ha il suo stesso valore.

In termini matematici: X and (X0 or X1 or X2 or X3 or X4 or X5 or

X6 or X7).

4.5 Segmentazione

La segmentazione è l’individuazione delle parti costituenti una scena. Serve per isolare gli oggetti di interesse dal resto dall’immagine. [3]

Esistono due approcci per la segmentazione di un’immagine: • estrazioni delle regioni omogenee;

• ricerca dei contorni o edge detection.

Dato che contorni e regioni sono due concetti complementari, rilevare gli uni o gli altri da alla fine lo stesso risultato.

4.5.1 Estrazione delle regioni omogenee

L’algoritmo più diffuso è il region growing, il quale segmenta un’immagine, suddividendola in regioni costituite da pixel simili tra loro.[4] Il criterio di similarità dipende da quali sono le caratteristiche che si intende studiare, come ad esempio l’intensità, la varianza, il colore, etc.

Per segmentare una struttura occorre prima di tutto individuare un pixel ad essa appartenente, chiamato seed pixel o seme. A partire dal seme viene fatta crescere una regione di interesse, prendendo in considerazione i suoi adiacenti, usando la topologia 4-connessa o 8-connessa. I vicini sono aggiunti alla regione se superano il test di

La sequenza descritta viene ripetuta anche su tutti i nuovi pixel appena aggiunti, ed il processo termina quando nessun altro può essere inglobato, ossia quando non ci sono più pixel adiacenti alla regione che superano il test di similarità.

Figura 4.6 Situazione al primo passo di Region Growing e

dopo poche iterazioni

4.5.2 Rilevamento dei bordi

L’idea base che sostiene gli algoritmi di ricerca dei bordi di oggetti all’interno di un’immagine è racchiusa nel principio che in un’immagine ogni oggetto apporta dei cambiamenti locali. Questi cambiamenti delle proprietà di ogni pixel sono molto netti e

coinvolgono quelli che fanno parte dei contorni. Quindi il contorno in un’immagine risulta essere un cambio locale e significativo nell’intensità dei pixel.

Esistono differenti tecniche di rilevamento dei bordi e, tra queste, quelle più usate sono quelle basate sul gradiente.

4.5.3 Rilevamento dei bordi basato sul gradiente

L’operazione fondamentale nella ricerca dei confini è, come già detto, trovare i bruschi cambiamenti nell’intensità di un’immagine. Questa ricerca si limita a cercare delle discontinuità nella derivata prima della funzione di intensità dell’immagine. Il gradiente è appunto la misura di quanto la derivata prima varia e, potendo ipotizzare un’immagine come una funzione continua dell’intensità dei pixel che la compongono, si avrà che elevati sbalzi della funzione gradiente identificano un punto di discontinuità.

Il gradiente è la funzione bidimensionale delle derivate parziali ed è definito come:

( )

[

]

Il vettore G[f(x,y)] indica la direzione della massima variazione incrementale della funzione f(x,y), la cui ampiezza è data dalla formula: 2 2 ) , (x y G_x G_y s = +

La direzione del vettore gradiente è data da:

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

=

G

G

arctn

y

x )

,

(

φ

dove l’angolo

φ

In un’immagine digitale un metodo per calcolare le derivate di primo ordine consiste nel calcolare le differenze di primo ordine tra pixel adiacenti.

Una definizione più complessa di gradiente coinvolge i pixel di un intorno 3x3 con centro in (x, y). Su di essa si basano, ad esempio, gli operatori di Prewitt e Sobel.

Nell’operatore diPrewittl le 2 derivate vengono calcolate come segue:

Gx = f(x+1,y-1) + f(x+1,y) + f(x+1,y+1) - f(x-1,y-1) - f(x-1,y) +

- f(x-1,y+1)

Gy = f(x-1,y+1) + f(x,y+1) + f(x+1,y+1) - f(x-1,y-1) - f(x,y-1) +

- f(x,y-1)

Nell’operatore di Sobel le 2 derivate vengono calcolate come segue:

Gx = [f(x+1,y-1) - f(x-1,y-1)] + [f(x+1,y+1) - f(x-1,y+1)] +

2[f(x+1,y) - f(x-1,y)]

Gy = [f(x-1,y+1) - f(x-1,y-1)] + [f(x+1,y+1) - f(x+1,y-1)] +

L’immagine dei contorni è un’immagine a tono continuo ma può essere “binarizzata” attraverso l’ operazione di sogliatura.

Si calcola l’intensità del gradiente per ogni pixel e il valore ottenuto è confrontato con una soglia T, determinata empiricamente. Se tale valore supera la soglia, al pixel è dato il valore 1, diversamente zero.

Vengono quindi estratti solo quei pixel caratterizzati da significativi cambiamenti di intensità.

4.6 Operazioni morfologiche

Le operazioni morfolologiche sono le più comuni tecniche specifiche per l’elaborazione di immagini binarie. [5, 6, 7]

Modificano la forma o la struttura spaziale degli oggetti bidimensionali nell’immagine.

Gli operatori morfologici si basano su un processo di convoluzione fra un’immagine binaria ed un elemento strutturante, chiamato anche maschera o kernel, che agisce da sonda sensibile a determinati aggregati di pixel. Generalmente l’elemento strutturante è un piccolo quadrato avente lati di un numero dispari di pixel (3x3, 5x5, ...), e del quale si definisce origine quel pixel corrispondente al centro del quadrato (figura 4.7).

L’immagine di input e la maschera sono combinati usando un insieme di operatori di base quali intersezione, unione, differenza e complemento, in modo da produrre l’effetto desiderato.

La maschera è traslata sopra l’immagine confrontando i valori dei pixel della maschera con quelli dell’immagine sottostante; se sono soddisfatte certe condizioni, diverse a seconda dell’operatore, allora

il pixel origine è posto ad un valore predefinito (0 o 1 nel caso di immagini binarie).

Figura 4.7 Esempio di applicazione di un’operazione morfologica con

elemento strutturante quadrato di dimensione 3x3.

Le operazioni morfologiche fondamentali sono: ™ dilatazione o somma di Minkowski;

™ erosione o sottrazione di Minkowski.

4.6.1 Dilatazione

Con l’operazione di dilatazione l’oggetto cresce in maniera uniforme.

Il più semplice tipo di dilatazione prevede di trasformare in un punto oggetto ogni punto dello sfondo che abbia un vicino oggetto.

Il pixel dell’immagine corrispondente al pixel centrale del kernel viene convertito dal valore logico 0 al valore logico 1 se almeno uno dei suoi vicini ha il valore logico 1.

Il risultato dipende dal tipo di connettività usata. Consideriamo ad esempio la figura 4.8.

Figura 4.8 Esempio dell’operatore dilatazione

Se si usa la 4-connettività si trasformano in punti oggetto i punti blu, se si usa la 8-connettività anche quelli gialli.

Questo tipo di dilatazione può creare dei problemi, come unire più oggetti insieme.

Un altro operatore di somma è l’interior fill.

Esso converte il pixel dell’immagine corrispondente al pixel centrale del kernel dal valore logico 0 al valore logico 1 se tutti i pixel ad esso 4-vicini hanno il valore logico 1.

Tale operatore consente di riempire piccole cavità eventualmente presenti nell’oggetto (figura 4.9).

Figura 4.9 Esempio dell'operatore Interior Fill

4.6.2 Erosione

Con l’operazione di erosione un oggetto si rimpicciolisce spazialmente in maniera uniforme.

Il tipo più semplice di erosione prevede di rimuovere ogni pixel dell’oggetto che abbia un vicino di sfondo.

In altre parole tale operatore converte il pixel dell’immagine corrispondente al pixel centrale del kernel dal valore logico 1 al valore logico 0, se almeno uno dei suoi vicini ha il valore logico 0. Anche in questo caso il risultato dipende dal tipo di connettività usata (figura 4.10).

Figura 4.10 Esempio dell’operatore erosione

Nell’esempio è visualizzata un’iterazione in cui si è usata la 4-connettività.

Questo semplice tipo di erosione può creare dei problemi, come dividere l’oggetto in più parti o farlo sparire del tutto.

Bibliografia

1. Prof. Paolo Dario, Lucidi del corso di Robotica Biomedica, anno 2005-2006

2. Elaborato di robotica: La visione robotica, redatto da Zanotti Daniele e Bettinsoli Stefano, università di Brescia

3. Dott. Cecilia Laschi, Lucidi del corso di Percezione Robotica, anno 2005-2006

4. sito web: Vision Systems.

url:http://www.cs.cf.ac.uk/Dave/Vision_lecture/Vision_lecture_

caller.html.

5. J. Serra, “Image Analysis and Mathematical Morphology”, New York, Academic Press, 1982

6. L. Vicent, “Morphological transformations of Binary Images

with Arbitrary Structuring Elements in Signal Processing”,

Elsevier Science Publishers, 1991

7. P. Soille, “Morphological Operators, Handbook of Computer

Vision and Applications”, Volume 2, London, Academic Press,