Proprietà dell’Immagine digitale
1
[email protected]
Metrica e Proprieta` topologiche
Distanza Euclidea DE
Siano (i,j) e (k,l) le coordinate di due pixel, si definisce distanza euclidea DE, la
classica misura geometrica ottenuta dalla nota relazione:
D E [(i, j), (k, l)]  (i  k ) 2  ( j  l ) 2
La distanza Euclidea dal punto di vista computazionale risulta onerosa a causa
dell’operatore di radice
2
[email protected]
4-Distanza (City Block)
Un approccio alternativo al calcolo della distanza tra due pixel e` data dal
numero minimo di movimenti da effettuare sulla griglia matriciale per passare da
un pixel all’altro
D 4 [(i, j), (k, l)]  i  k j  l 
3
[email protected]
8-Distanza (chessboard)


D8[(i, j), (k, l)]  max i  k , j  l 
Le distanze D4 e D8 sono misure convenienti rispetto alla distanza Euclidea per la
loro semplicita` computazionale.
4
[email protected]
Vicinanza tra pixel
4-Vicinanza (4-neighborhood)
Quando due qualunque pixel hanno distanza D4=1 da ciascun altro
(i+1,j) (i-1,j) (i,j+1) (i,j-1)
8-Vicinanza (8-neighborhood)
Quando due qualunque pixel hanno distanza D8=1 da ciascun altro
5
[email protected]
Percorso path
Il percorso tra due pixel A e B è definito come sequenza di pixel
S1, S2,------Sn
dove S1=A, Sn=B
il pixel Si+1 e` vicino al pixel Si per i=1,....,n-1
Percorso Semplice nessun pixel ripetuto (ad esclusione del primo e l’ultimo) in
cui nessun pixel ha piu’ di due vicini
Percorso Chiuso è un percorso semplice in cui il primo pixel è vicino all’ultimo
Si possono definire allo stesso modo
4-percorso e 8-percorso che scaturiscono dal concetto di vicinanza a 4 o 8
Ambiguità della vicinanza (fig. 1.3b)
Soluzione per immagini binarie: usare 8-vicinanza per oggetti e 4-vicinanza per lo
sfondo (o viceversa)
6
[email protected]
Regione
Insieme di pixel in cui è possibile definire un percorso considerando qualsiasi
coppia dei pixel stessi.
Esempio di Regione: una porzione dell’immagine
Connettività
Due pixel P e Q in una immagine I sono connessi se esiste tra P e Q un percorso
La connettivita` e` una relazione di equivalenza ossia definisce una decomposizione
dell’immagine in regioni di equivalenza
Siano P, Q ed R tre pixel dell’immagine I, la relazione di connettività stabilisce le
seguenti proprieta`:
-Riflessività, il pixel P è connesso a P.
-Commutatività, se P è connesso a Q → Q è connesso a P.
-Transitività, se P è connesso a Q e Q è connesso a R consegue
anche P è connesso ad R.
7
[email protected]
che
Componenti Connesse
Un insieme di pixel di una immagine in cui ciascun pixel è connesso a tutti gli altri
Foreground S
L’insieme S di tutti i pixel a 1 di una immagine binaria
Background (sfondo) ed Holes (buchi)
L’insieme di tutte le componenti connesse di S (complemento di S) che comprende
anche i punti sul bordo dell’immagine
Sono chiamate Holes invece tutte le altre componenti di S. Se in una regione
dell’immagine non vi sono buchi si parla di regione semplice connessa
Si chiama regione multipla connessa se una regione presenta buchi
Per eliminare le ambiguità si usano 8-connettività per S e 4-connettività per S
8
[email protected]
Oggetto
Il concetto di regione usa soltanto le proprietà di connettività
E` usuale chiamare alcune regioni dell’immagine con oggetti.
La procedura che elabora una immagine per ricercare particolari regioni che
corrispondono a oggetti del mondo e` chiamata segmentazione.
Un oggetto è rappresentato nell’immagine da una componente connessa.
I buchi sono pixel non appartenenti all’oggetto.
Esempio:
Se consideriamo questo foglio come una immagine,
il foglio bianco rappresenta il background,
gli oggetti sono tutti i caratteri individuali in nero,
i buchi sono le aree bianche che circondano le lettere (nella
lettera “O” è rappresentata dall’area interna bianca).
9
[email protected]
Contorno
Una caratteristica importante di una regione R è il contorno che assume una
importanza notevole nell’analisi dell’immagini.
Il contorno è l’insieme dei pixel R interni alla regione che hanno una o piu`
vicinanze esterne ad R.
In altre parole il contorno delimita tutti i pixel di una regione contorno interno.
Il contorno esterno coincide, invece, con il contorno del background ossia del
complemento della regione R.
10
[email protected]
Bordi (Edges)
Mentre il contorno è un concetto associato globalmente ad una regione, il bordo
costituisce una proprietà locale di un pixel con i suoi vicini ed è caratterizzato
come un vettore definito dal modulo e dalla direzione.
I bordi, normalmente individuati ai confini tra regioni omogenee di una immagine,
sono fondamentali per il sistema visivo umano in quanto costituiscono le
informazioni di base per la percezione del mondo.
Normalmente rappresentano le forti variazioni geometriche degli oggetti
osservati e sono i pixel sui quali si concentra la massima attenzione per la
ricostruzione 3D degli oggetti stessi.
Diversi sono gli operatori locali che verranno utilizzati per l’estrazione dei bordi
partendo dalla funzione di livello di grigio di una immagine

11
[email protected]
PROPRIETA` TOPOLOGICHE DI UNA IMMAGINE
Sono quelle proprietà che non variano quando una immagine subisce una
trasformazione che modifica la sua forma geometrica.
Immaginate per esempio la deformazione che subisce una immagine disegnata su un
pallone che gonfiato perde la sua figura sferica.
Le deformazioni subite dall’immagine non alterano l’omogeneità degli oggetti
rappresentati dall’immagine stessa, ne’ alterano l’eventuale presenza di buchi nelle
regioni.
NUMERO DI EULERO
Il numero di Eulero E è usato come caratteristica dell’oggetto.
E` definito come la differenza tra le componenti connesse (regioni) C ed il numero
di buchi B presenti nell’immagine
E=C-B
12
[email protected]
INVOLUCRO CONVESSO (CONVEX HULL)
L’involucro convesso è la regione più piccola che contiene un oggetto, tale che, presi
due punti qualunque della regione, possono essere connessi da un segmento, i cui
punti appartengono alla regione stessa.
Esempio:
Sia R un oggetto che rassomiglia alla lettera R e supponiamo di avvolgere un
elastico sottile intorno ad R.
La figura rappresentata dall’elastico costituisce l’involucro convesso.
Deficit di convessità: regione intorno all’involucro convesso non appart. all’oggetto
Questa può essere divisa in due sotto regioni.
• LAKES sono completamente circondati dall’oggetto,
• BAYS sono connesse con il contorno dell’involucro convesso.
13
[email protected]
AREA, PERIMETRO E COMPATTEZZA
-L’area e perimetro costituiscono altri due parametri topologici che caratterizzano
le componenti connesse S1, S2---------Sn presenti nell’immagine.
-L’area per ogni componente Si è data dal numero dei pixel contenuti
-Il perimetro di una componente connessa è definito come la somma dei pixel che
costituiscono il contorno della componente. Esistono altre definizioni che saranno
introdotte nel seguito.
-L’area ed il Perimetro sono grandezze dipendenti dalle operazioni di trasformazioni
geometriche eseguite sull’immagine.
-La compattezza è un altro parametro topologico di una figura geometrica connessa.
Esprime una misura di ineguaglianza isoperimetrica di una componente connessa
p2
C
 4
A


2
16  25
2
Una regione circolare ha un valore di compattezza C minimo (raggiunge il valore 4).
Nell’ellisse, l’area diminuisce in proporzione maggiore rispetto al perimetro che varia
leggermente. Conseguentemente il valore di compattezza aumenta.
14
[email protected]
PROPRIETA` INDIPENDENTE DALLA POSIZIONE DEL PIXEL
Istogramma
L’istogramma HI(L) di una immagine I è un vettore che fornisce la frequenza dei
livelli di grigio presenti nell’immagine compresi nell’intervallo Lmin  L  Lmas
Algoritmo istogramma:
1. Inizializza a zero tutti gli elementi del vettore H(L).
2.
Esamina tutti i pixel (x,y) dell’immagine; per ogni pixel considerato utilizza
il valore di livello di grigio I(x,y) come puntatore al vettore istogramma
HII(x,y)) ed incrementalo di 1
Se l’immagine è prodotta da un processo stocastico, l’istogramma rappresenta una
stima della distribuzione di probabilità dei livelli di grigio.
L’istogramma è l’unica informazione globale disponibile per l’immagine.
L’istogramma sarà utilizzato in molti algoritmi di elaborazione dell’immagine:
•
modificare i livelli di grigio,
•
segmentare una immagine,
•
estrarre gli oggetti dal background,
•
ecc..
15
[email protected]
16
[email protected]
Grani di riso
Il valore 100 si riferisce al background
17
[email protected]
Dall’istogramma si ricavano parametri statistici del primo ordine quali
m  I 
L max
 k  p(k )
k 0
H (k )
p(k ) 
NxM
0  p(k )  1 k  0, , L max
La varianza (momento di ordine 2) è data invece da
 2  ( I   I ) 2
 p(k )  1
k 0
L max
 p ( k )  ( k  m)

2
k 0
i momenti di ordine n sono dati da
Mn 
L max
L max
n
p
(
k
)

(
k

m
)

k 0
Il momento di ordine 3 rappresenta una misura di asimmetria della funzione di
probabilità intorno al valore della media (skewness)
Viceversa se tale funzione di distribuzione è simmetrica rispetto al valore medio, i
momenti di ordine 3 e gli altri di ordine dispari maggiore, hanno valore zero
18
[email protected]
PROPRIETA` DIPENDENTE DALLA CORRELAZIONE TRA PIXEL
Correlazione
La statistica del primo ordine considerata con il calcolo dell’istogramma, non
contiene informazioni sulla relazione tra i pixel
L’istogramma calcolato può appartenere a diverse immagini e non contiene
informazioni sul numero degli oggetti e la loro dimensione
Per considerare anche la disposizione spaziale dei livelli di grigio, è necessario
considerare la statistica del secondo ordine.
La matrice rappresentante l’immagine consisterebbe di NxM variabili random.
Questo implica il calcolo della funzione di probabilità per ciascun pixel dell’immagine.
Le medie per ciascun pixel (i,j) sarebbero calcolate come segue
 I (i, j ) 
L max
 k  p ( k , i, j )
k 0
19
[email protected]
la cui stima è ottenuta dalla media integrata IT, che nelle stesse condizioni di
acquisizione sarebbe
1 Q
 IT   I k
Q k 1
Relativa a Q osservazioni dello stesso pixel I(i,j)
La varianza è stimata come segue
1 Q
 ( I K   I ) 2
 
Q  1 K 1
2
I
Misura di correlazione
Per porre in relazione pixel di posizione diversa nell’immagine, si utilizza la misura di
correlazione dei livelli di grigio data come il prodotto dei livelli di grigio nelle due
posizioni considerate.
Ciò viene realizzato dalla funzione di autocorrelazione
RII (i, j; k , l )  I ij , I kl 
L max 1 L max 1
 I
r 0
s 0
r
 I s  p ( r , s; i , j ; k , l )
Ossia la probabilità che viene simultaneamente stimata per il pixel (i,j) con livello di
grigio r e per il pixel (k,l) con livello di grigio s
20
[email protected]
La funzione di autocorrelazione ha 4-dimensioni e diventa complicato utilizzarla
Il problema si semplifica se si assume che la statistica non sia dipendente dalla
posizione del pixel
In questo caso il campo random è detto omogeneo, ed il valore della media non
dipendendo più dalla posizione di ciascun pixel, è costante per tutta l’immagine:
<I> = costante
la funzione di autocorrelazione diventa SHIFT INVARIANT, ossia indipendente
dalla posizione dei due pixel:
RII (i+n,j+m;k+n,l+m)= RII(i,j;k,l)
= RII(i-k,j-l;0,0)
= RII(0,0;k-i,l-j)
Le ultime identità si ottengono ponendo
(n,m)=-(k,l)
ed
(n,m)=-(i,j).
In pratica la funzione di autocorrelazione R dipende solo dalla distanza dei due
pixel e conseguentemente la dimensionalità della funzione passa da 4 a 2.
M 1 N 1
RII (kl)   I ij  I i  k , j l
i 0 j o
21
[email protected]
QUALITA` DELL’IMMAGINE
Durante le varie fasi di acquisizione, di elaborazione e trasmissione, una immagine
può subire delle degradazioni.
Una misura della qualità dell’immagine può essere adottata per stimare il livello di
degradazione, in relazione al campo di applicazione.
Metodi quantitativi misurano la qualità dell’immagine confrontando una immagine con
quella di riferimento (immagine modello).
Normalmente come immagine modello si scelgono quelle (acquisite realmente), che
sono ben calibrate di cui si conoscono bene sia le condizioni radiometriche, sia quelle
geometriche
In alternativa in alcune applicazioni si è costretti ad utilizzare solo immagini modello
ottenute in modo sintetico.
  ( g  f )dxdy  minimo
22
[email protected]
QUALITA` DELL’IMMAGINE
MSE – Mean Squared Error
eMSE
1

MN
M
N
2


g
(
i
,
j
)

f
(
i
,
j
)

i 1 j 1
Con MSE ci sono problemi di scala
PSNR – Peak Signal-to-Noise Ratio
40dB
eMSE
PSNR  1030dB
log 10 2
S
20dB
Dove S rappresenta il valore di grigio massimo
10dB
0dB
23
[email protected]
RUMORE DELL’IMMAGINE
Le immagini reali sono normalmente degradate da errori casuali introdotti
•
dal processo di digitalizzazione dell’immagine,
•
durante l’elaborazione
•
in trasmissione
Tale degradazione è usualmente chiamata rumore.
Questo fenomeno è consuetudine modellarlo come un processo stocastico.
Un rumore ideale è chiamato white noise che ha spettro di potenza costante ossia
la sua intensità non diminuisce con l’incremento delle frequenze
INFORMAZIONI PERCETTIVE DELL’IMMAGINE
Il sistema visivo umano utilizza alcuni parametri psico-fisici per la percezione degli
oggetti della scena.
Gli algoritmi di percezione sono sviluppati tentando di emulare alcuni meccanismi del
sistema visivo umano.
Nella percezione umana gli oggetti sono piu` localizzati ed identificati se sono ben
contrastati rispetto allo sfondo.
In alcuni contesti è noto che anche il sistema umano fallisce
24
[email protected]
CONTRASTO
Definisce un cambiamento locale della intensità luminosa ed è definito come il
rapporto tra la brillanza media di un oggetto e la brillanza di uno sfondo
Il sistema visivo umano è sensibile alla brillantezza logaritmica e conseguentemente
per la stessa percezione, valori di brillanza più alti richiedono contrasti più alti.
ACUTEZZA
Esprime l’abilità a determinare i dettagli in una immagine.
Dipende dall’ottica del sistema e dalla distanza tra oggetto e osservatore.
La risoluzione dell’immagine deve essere appropriata rispetto alla capacità
percettiva del sistema di visione.
25
[email protected]
Matrice di co-occorrenza
È un altro esempio di informazione globale dell'immagine
Consideriamo una stima di probabilità congiunta associata alla coppia di pixel I(i,j) e
I(k,l), di una immagine I, con livelli di grigio da 0 a Lmax, legati da una qualunque
relazione geometrica (per esempio distanza espressa in coordinate cartesiane Δx,
Δy oppure polari r,θ)
La matrice di co-occorrenza rappresenta l'istogramma bidimensionale P(L1,L2;i,j,k,l)
considerato come una stima delle distribuzioni della probabilità congiunta che una
coppia di pixel hanno rispettivamente intensità L1 ed L2, ossia:
P(L1,L2)=Prob. cong. {I(i,j)=L1 ∧ I(k,l)=L2}
Ogni elemento dell'istogramma bidimensionale è dato da:
P ( L1 , L2 ) 
F ( L1 , L2 )
NT
Freq. Co-occorrenza che I(i,j)=L1 e
I(k,l)=L2 secondo una relazione
geometrica di distanza (Δx, Δy)
26
[email protected]
Per una data relazione geometrica R tra coppie di pixel di intensità
L1 ed L2, la matrice di co-occorrenza PR(L1,L2) ha dimensioni quadrate NLmax×NLmax
corrispondente al massimo numero di livelli di grigio presenti nell'immagine
Algoritmo per il calcolo della matrice di co-occorrenza
Sia R una generica relazione (per esempio geometrica, di vicinanza, ecc.) tra coppie
di intensità L1, ed L2, segue:
1.
(Inizializzazione) FR(L1,L2)=0 ∀ L1,L2 ∊ (0,Lmax) con Lmax il massimo
valore di intensità dell'immagine I.
2.
 pixel (i,j) nell'immagine, calcola il pixel (k,l) che soddisfa la relazione R
con il pixel (i,j) ed aggiorna la matrice di co-occorrenza:
FR(I(i,j),I(k,l)) = FR(I(i,j),I(k,l))+1
Esempio
Consideriamo una immagine di 5×5 pixel con intensità 0,1 e 2
Nell'immagine vi sono tre livelli di grigio pertanto la matrice di co-occorrenza
risulterà di dimensioni 3×3
27
[email protected]
La relazione geometrica che lega tutte le possibili coppie di livello di grigio (L1,L2) è
del tipo (Δx, Δ y)=(1,1) ossia
la relazione della coppia di pixel sarà:
considera il pixel alla destra e l'adiacente sottostante (pixel lungo la diagonale
dall'alto in basso)
Esaminiamo l'elemento della matrice di co-occorrenza FR(2,1)=3 ciò è giustificato
poiché vi sono tre coppie di pixel con intensità (2,1) che soddisfano la relazione
geometrica R e corrispondono ai pixel
(i,j) (k,l) → (i+1,j+1)
(0,2) (1,3)
(2,3) (3,4)
(3,1) (4,2)
28
[email protected]
29
[email protected]
La matrice PR(L1,L2) non è simmetrica poichè il numero di coppie di pixel con livello di
grigio (L1,L2) non necessariamente eguaglia il numero di coppie di intensità (L2,L1)
Gli elementi della diagonale principale FR(Li,Li) rappresentano l'area delle regioni
nell'immagine con livelli di grigio corrispondenti a Li
Conseguentemente corrispondono all'istogramma del primo ordine
La funzione di probabilità congiunta espressa da ogni elemento di PR può essere
normalizzata con il numero di coppie di pixel (N-1) (M-1) invece di NT numero totale
di casi in cui si realizza la relazione nella griglia
La matrice di co-occorrenza contiene l'informazione globale di distribuzione
spaziale dei livelli di grigio di una immagine
Il calcolo di PR richiede notevole calcolo intensivo in quanto per accumulare
l'istogramma 2D deve essere elaborato ogni pixel (i,j) dell'immagine ed applicata la
relazione R per il pixel da correlare
Per ridurre i tempi di calcolo può essere ristretta la relazione geometrica R per la
coppia dei pixel da considerare
30
[email protected]
Ciò è possibile in due modi:
 Ridurre i livelli di grigio dell'immagine
 Ridurre il dominio di influenza della relazione R
Questo comporta
• perdita di accuratezza sulle strutture di intensità presenti nell'immagine
(tessitura)
• mentre ridurre il dominio della relazione R comporta errori in presenza di
strutture geometriche estese.
Un buon compromesso si ottiene utilizzando immagini con 16 livelli di grigio e
finestre quadrate di circa 30÷50 pixel.
La matrice di co-occorrenza è applicata per la descrizione delle microstrutture
(tessitura) presenti nelle immagini
Se le coppie di pixel di una immagine sono molto correlate gli elementi di PR(L1,L2)
della diagonale principale contengono la maggior parte dell'informazione
31
[email protected]
ENTROPIA
Una caratteristica che misura la casualità della distribuzione di livello di grigio è
l'entropia; definita come
L max L max
E
r 0
 P( L , L )  log
r
s 0
s
2
P( Lr , Ls )
Il valore più alto dell'Entropia si ha quando tutti gli elementi di P sono equiprobabili
Ciò corrisponde quando l'immagine non presenta coppie di livello di grigio con
particolare preferenza rispetto ad altre
Contrasto o Inerzia
C
L max L max

r 0
Energia
Energia 
2
(
L

L
)
 r s  P(Lr , Ls )
s 0
L max L max
 P
r 0
Omogeneità
H
2
s 0
(Lr , Ls )
L max L max

r 0
P( Lr , Ls )

s 0 1 | Lr  Ls |
32
[email protected]
Valore Assoluto
V 
L max L max
 | L
r 0
s 0
r
 L s |  P ( Lr , L s )
Per diverse applicazioni, la matrice di co-occorrenza è calcolata per una stessa
immagine variando il tipo di relazione R .tra le coppie di livello di grigio
La matrice P, che massimizza una data misura statistica, viene scelta per l'analisi
dell'immagine, per l’identificazione di microstrutture
Un buon impiego della matrice di co-occorrenza è avvenuta per la classificazione del
territorio utilizzando immagini multispettrali provenienti da satelliti
33
[email protected]
Proiezioni Orizzontali e Verticali
Con questo tipo di codifica è possibile ricavare alcune informazioni utili come:
•Proiezioni orizzontali
•Proiezioni verticali
La prima è ottenuta in modo immediato come è indicato nella figura
y1
ym
yc -
y2
x1
xc xm
34
x2
[email protected]
RUMORE GAUSSIANO
E` un altro modello di approssimazione del rumore. Sia x la variabile casuale che
descrive il rumore , segue:
1
p( x) 
e
 2
( x )2
2 2
dove  e` la media e  la deviazione standard della
variabile casuale.
Nella elaborazione delle immagini risulta essere
una buona approssimazione del rumore per i
sistemi di acquisizione tipo ccd. Il rumore
interessa qualunque livello di grigio
35
[email protected]
SALT E PEPPER
E` un rumore dovuto alla presenza casuale di entrambi valori di intensita` bianchi e
neri.
Questo rumore può essere dovuto ad errori di
•
Classificazione risultante da:
o variazioni di illuminazione;
o da caratteristiche della superficie del materiale;
•
Rumore causato dalla conversione analogico/digitale del frame grabber
•
Dalla costruzione di un'immagine binaria ottenuta con un'operazione di
thresholding (soglia)
Per rimuovere l’effetto si possono usare due maschere 8-vicinanza
36
[email protected]