Distâncias
Paulo Sérgio Rodrigues
PEL205
Casamento de Curvas
=
Casamento de Curvas
Seja a seqüência n dimensional ordenada de pontos:
C p  [ p 1 , p 2 ,  , p n ], p i  
onde o ponto pi vem antes do ponto pi+1 e pn vem antes de p1.
n
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
=
?
C
p
C
q
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
Problemas:
a) Translação
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
Problemas:
b) Rotação
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
Problemas:
c) Escala
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
Problemas:
d) Dimensão
Casamento de Curvas
Considerando duas curvas Cp e Cq, qual a distância entre elas?
• Distância de Hausdorff
• Distância PDM
• Distância Euclidiana
• Distância de Kulback-Leibler
• Distância Vetorial
=?
Cp
Cq
Distância de Hausdorff
A distância de Hausdorff é uma medida entre dois conjuntos de pontos, não necessariamente com a
mesma dimensão. Ela mede o quento um conjunto de pontos A está perto de um conjunto de pontos B
Formalmente, dado dois conjuntos de pontos A e B, a distância
de Hausdorff entre eles é definida como:
H ( A , B )  max( h ( A , B ), h ( B , A ))
onde
h ( A , B )  max
a A
(min
b B
ab )
Distância de PDM (PolyLine Distance Measure)
Seja B1 e B2 duas bordas em coordenadas cartesianas. A
medida PDM entre elas é definida como:
d b ( A , B 2 )  min
d vb ( B1 , B 2 ) 
SB2
d
b
d ( A, S )
( A, B2 )
A B1
d
Error
poly

d vb ( B1 , B 2 )  d vb ( B 2 , B1 )
# vértice  B1  # vértice  B 2
Distância Euclidiana e Variações
Seja dois vetores que representam quaisquer tipo de informação
H 0  h 2 , h 2 ,..., h n 
H 1  h 2 , h 2 ,..., h n 
Distância Euclidiana e Variações
Para p = 1 d é a distância Manhattan
Para p = 2 d é a distância Euclidiana
Distância/Divergência de Kulback-Leibler
Sejam duas distribuições de Probabilidades quaisquer
H1
H
2
Distância/Divergência de Kulback-Leibler
A distância de Kulback-Leibler entre
como:
D KL ( H 1 , H 2) 
H
n
1
H1
( i ) log(
e
H
H 1 (i )
H 2 (i )
2
)
é dada
Distância/Divergência de Kulback-Leibler
No entanto, pelo fato de não existir garantias de que:
D KL ( H 1 , H 2)  D KL ( H 2 , H 1)
A Equação anterior não é considerada uma distância, e sim uma
divergência.
Sendo assim, a Distância de Kulback-Leibler é definida como:
D KL ( H 1 , H 2) 
H
n
1
( i ) log(
H 1 (i )
H 2 (i )
)
H
n
2
( i ) log(
H 2 (i )
H 1 (i )
)
Divergência de Kulback-Leibler Extendida
Distância Vetorial
Sejam as mesmas duas distribuições de Probabilidades quaisquer
H1
H
2
Distância Vetorial
A distância Vetorial entre ambas as distribuições é dada como:
n
Sim  H 1 , H 2  
H
1
(i ) * H 2 (i )
i 1

n
2
H 1 (i ) *

n
2
H 2 (i )
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Entre Descritores
Distância Bidimencional:
Matching de Template e Objeto em Cena por Correlação
Distância Bidimencional:
Matching de Template e Objeto em Cena por Correlação
c( x, y ) 

s
D ( x , y )  max
f (s, t )w( x  s, y  t )
t
   f (s, t ) 
s


 s

t
  f (s, t ) 
t

f (s, t ) w( x  s, y  t )  w

2
f (s, t )
s
t


w( x  s, y  t )  w 

2
Distância Bidimencional:
Matching de Template e Objeto em Cena por Correlação
Distância Entre Descritores
Door-In-Door-Out Algoritmo para extrair coordenadas
de Bordas