Trasformata di Hough
http://slipguru.disi.unige.it
Caratteristiche di immagini
In Visione Computazionale il termine feature di
immagini si può riferire a due entità possibili:
Una proprietà globale di un’immagine o una
regione (es. il livello di grigio medio, la
distribuzione di colore, ...);
Una parte dell’immagine con alcune proprietà
speciali (es. una linea, un’ellisse,...).
2
Feature locali
Un passo importante dell’elaborazione visiva consiste
nell’identificare feature locali che siano utili ad
interpretare l’immagine
Le feature locali sono parti dell’immagine “facilmente”
rilevabili, che possono corrispondere o meno a parti
della scena
Abbiamo già visto:
Edge
Corner e SIFT
Oggi parliamo della ricerca di feature per le quali esiste
una descrizione analitica, tramite un semplice esempio:
le linee
3
Rilevamento di linee
Le linee sono feature importanti perché
permettono di definire analiticamente o
approssimare molte forme
(in particolare di oggetti costruiti dall’uomo)
Le linee possono essere rilevate in (almeno) due
modi diversi:
Tramite template matching, utilizzanto un insieme
di maschere che modellino l’andamento locale di
una retta
Tramite trasformata di Hough, ossia tramite un
sistema di voting che segue una fase di edge
detection
4
Template matching (velocemente)
IDEA: cercare i picchi nella convoluzione tra l’immagine
e un insieme di maschere che modellano la struttura
locale di rette.
Se una maschera M in un punto p ritorna una risposta
superiore ad una soglia, diciamo che in quel punto
passa un segmento di retta la cui orientazione e spessore
è modellato da M
-1 -1 -1
2 2 2
-1 -1 -1
Esempio di maschera che definisce un segmento di retta
con orientazione 0
5
Trasformata di Hough (HT)
IDEA CHIAVE
Mappare un problema difficile di riconoscimento di
forme nel seguente problema (più facile):
rilevare i picchi nello spazio dei parametri
della curva cercata (linee nel nostro caso)
6
HT per il rilevamento di rette
Una retta
y=mx+n
è identificata dalla coppia di parametri (m,n)
Nel caso delle rette lo spazio dei parametri è un
piano (ho 2 soli parametri: m e n)
Nello spazio dei parametri la retta è
rappresentata da un punto
7
HT per il rilevamento di rette
n
y
.
x
m
8
HT per il rilevamento di rette
Al contrario, un punto nello spazio di partenza
(x,y)
rappresenta una linea
n=x(-m)+y
nello spazio dei parametri
Ogni punto di questa linea corrisponde ad una
linea nello spazio di partenza che passa per il
punto (x,y).
9
HT per il rilevamento di rette
n
y
. (m1,n1)
. (m2,n2)
.(x,y)
. (m3,n3)
x
m
10
HT per il rilevamento di rette
n
y
.P2
.Q
.P1
x
m
Due punti appatenenti alla stessa retta r, corrispondono
nello spazio dei parametri a due rette, la cui intersezione ci
11
fornisce i parametri (m,n) della retta r
HT per il rilevamento di rette
Quindi una retta nello spazio di partenza
definita da N punti P1, ..., PN viene identificata
come intersezione nello spazio dei parametri di
N rette, ognuna corrispondente ad un Pi
y
.
n
P4
.
P3
Caso ideale...
.Q
.
P2
.P1
x
m
12
HT per il rilevamento di rette
In presenza di rumore non è detto che i Pi siano
esattamente collineari
Quindi l’intersezione può non essere unica
y
.
P3
.
n
P4
.
P2
.
.. .
?
.P1
x
m
13
HT per il rilevamento di rette
Se si hanno abbastanza punti nello spazio di
partenza, il problema può essere tradotto in un
problema di detezione di picchi nello spazio dei
parametri
y
.
P3
.
n
P4
.
.
P2
!
.P1
x
m
14
Nel caso di immagini...
I punti dello spazio di partenza possono essere
punti di edge
15
Un algoritmo semplice
Assumiamo che un’immagine contenga solo 1
retta, di parametri (m’,n’) costituita dai punti di
edge P1, ..., PN
Dividiamo lo spazio dei parametri (m,n) in una griglia finita
di celle e associamo ad ognuna di esse un contatore C(m,n)
Per ogni punto Pi=(xi,yi)
calcoliamo la retta si nello spazio dei parametri che abbia (xi,yi)
come coefficienti
Incrementiamo tutti i contatori relativi alla retta si nello spazio
dei parametri
In assenza di rumore tutte le si passano per la cella (m’,n’) quindi
C(m’.n’)=N e tutte le altre celle hanno valori più piccoli (quali?)
La retta viene identificata trovando questo picco
16
Un algoritmo semplice
Due problemi:
In caso di rumore non è detto che tutte le rette si
incontrino nella stessa cella
Se ci sono più rette nell’immagine
Per questi motivi si individuano i massimi locali
nello spazio dei parametri (fissando una
soglia...)
17
Una piccola modifica
Lo spazio dei parametri è infinito
Nell’implementare l’algoritmo occorre fissare un
valore minimo e massimo per n ed m:
Come?
Una semplificazione si può ottenere scegliendo
una rappresentazione alternativa delle rette:
x cosθ +y sinθ = r
18
Una piccola modifica
Una semplificazione si può ottenere scegliendo
una rappresentazione alternativa delle rette:
x cosθ +y sinθ = r
θ
y
θ[0,π]
.
r
θ
x
r
19
Una piccola modifica
Considerando anche il fatto che i punti nello spazio di
partenza appartengono ad un’immagine anche r
appartiene ad un intervallo finito
θ
y
θ[0,π]

r  0, M2  N2
M
.
r
θ
N
x
r
20

Schema algoritmo:
costruzione dello spazio dei
parametri
max_r=sqrt((M^2)+(N^2));
delta_r=max_r/(R-1);
drom=dro/2;
delta_teta=pi/(T-1);
r=[0:delta_r:max_r];
teta=[0:delta_teta:pi];
A=zeros(R,T);
[i,j]=find(image==1);
for h=1:T
r_h=(i*cos(teta(h)))+(j*sin(teta(h)));
for y=1:size(i,1)
[c,k]=min(abs(r-r_h(y)));
if (c<delta_r)
A(k,h)=A(k,h)+1;
end;
end;
end;
21
1. Edge detection
Materiale tratto da CVonline
22
2. Lo spazio dei parametri
23
3. Stima dei picchi e riproiezione
sullo spazio di partenza
Al variare della sogliatura.....
24
Generalizzazioni..
Possiamo utilizzare la stessa procedura per rilevare altre
forme
Ad esempio nel caso delle circonferenze
(x  a)2  (y  b)2  r 2
In questo caso lo spazio dei parametri è 3D (a,b,r)
Per curve più complesse questo approccio diventa
sempre meno pratico
25