A.a. 2010/2011
Elaborazione dell’immagine M
Individuazione di Forme – Integrazione
Luigi Di Stefano
Template Matching veloce nel dominio di Fourier
(1)
• Utilizzando la NCC:
NCC (i, j ) 
1
T (i, j) I (i, j)  ,
K  i, j 
K  i , j   I  i, j   T
T (i, j ) I (i, j )  I (i, j )  T ( i,  j )
I (i, j ) T (i,  j )   I (i, j)    T (i,  j)    I (i, j )    T (i, j )   I (u, v)  T (u, v)
IFFT
NCC (i, j ) 
FFT
1
1  I (u, v)  T  u, v  
K  i, j 
FFT
Elaborazione dell’immagine M
Luigi Di Stefano
Template Matching veloce nel dominio di Fourier
(2)
• Utilizzando la SSD
M 1 N 1
SSD(i, j )     I (i  m, j  n)  T  m, n  
2
m 0 n 0
M 1 N 1
M 1 N 1
  I (i  m, j  n)    T  m, n 
2
m 0 n 0
m 0 n 0
I  i, j 
2
IFFT
T
2
M 1 N 1
 2   I (i  m, j  n)  T  m, n 
m 0 n 0
2 T (i, j ) I (i, j ) 
2
FFT
1  I (u , v)  T  u , v  
FFT
Elaborazione dell’immagine M
Luigi Di Stefano
Template Matching veloce mediante bounds
efficienti
 x1 
X     X
 xN 

   xi
 i 1

N
p
p 1 p



p  1, X  I  i, j  , Y  T
  i, j   SADmin
T
skip (i,j) !
Disuguaglianza Triangolare: X p  Y
M 1 N 1
M 1 N 1
m 0 n 0
m 0 n 0
 XY
  I  i  m, j  n     T  m, n   SAD i, j 
F
SAD  i, j 
SAD  i, j   SADmin
Elaborazione dell’immagine M
p
  i, j 
lower-bound
calcolabile
efficientemente !
Algoritmi veloci basati su
bounds anche per SSD, NCC e
ZNCC.
Luigi Di Stefano
p
GHT: Generalized Hough Transform (1)
• Estensione della HT a forme non descrivibili analiticamente.

x
B
Fase Off-line (costruzione del modello)
r
y
1. Scelta di un punto di riferimento y.
2. Scelta di un passo di quantizzazione della direzione
del gradiente ∆φ
3. Per ciascun punto x del contorno B:
1. Calcolo della direzione del gradiente φ(x)
2. Determinazione del vettore r che va dal punto x
al riferimento y.
4. Memorizzazione di r come funzione di ∆φ (R-Table)
Ogni entry della tabella
può contenere più di un
vettore R
Elaborazione dell’immagine M
Luigi Di Stefano
GHT: Generalized Hough Transform (2)
Fase On-line (riconoscimento)
1.
B
Inizializzazione di una immagine A[y] come accumulatore
Per ciascun edge pixel x dell’immagine analizzata:
2.
Calcolo della direzione del gradiente φ
3.
Quantizzazione di φ ed accesso alla R-Table. Per
ogni vettore ri memorizzato nella riga acceduta:
y
x
4.
a)
Calcolo della posizione del punto di
riferimento associato a Ri: y=x + ri
b)
Incremento della corrispondente cella
dell’accumulatore: A[y]++
Ricerca dei picchi dell’accumulatore, al fine di individuare
possibili istanze della forma cercata.
r1,r2,r3
Elaborazione dell’immagine M
Luigi Di Stefano
GHT: Generalized Hough Transform (3)
• Riconoscimento invariante per rotazione

x
 =  + 
B
x
r
r
r
B
y
y
T  R    R     mod 2 
• Invarianza per scala
r : y  x  rs  x  s  r , A y, s   
Elaborazione dell’immagine M
 r : y  x  r  x  ROT  r,  , A y,   
• Invarianza per rotazione e scala
r : y  x  s  r , A y, , s   
Luigi Di Stefano