Lecture 2: Matching

point sets

Wesley Snyder, Ph.D., EMT-P

(co-)conqueror of Kilimanjaro!

2y = x dx (1)

Provide a survey of the state of the art

Shape Features/descriptors•

Desirable Properties•

Point Set Matching•

Bottleneck distance

Hausdorff Distance

Fréchet Distance

NEM Distance

Symmetric Distance

1Desirable Properties of

shape similarity measure

Nonnegativity: d(A,B)≥0

Identity: d(A,A) = 0

Uniqueness: d(A,B)=> A=B

Strong triangle inequality d(A,B)+d(B,C) ≥ d(A,C)Properties

Does the triangle inequality make sense?

d(man,centaur) + d(centaur,horse) ≤ d(man,horse)

Figure ripped off from R. Veltcamp and M. Hagedoorn, Shape Similarity Measures, Properties, and Constructions More About Shape Measures

Invariance under transformations:

d(g(A),g(B)) = cd(A,B) for constant c

Robustness to perturbations, cracks,

blur, noise, occlusion. Some example measures

No, I don’t have comparative data

This lecture is not sufficiently detailed

for implementation. You need to go to

the original work to get the subtle

details.Shape Metrics Surveyed here

Bottleneck distance

Hausdorff Distance

Fréchet Distance

NAM Distance

Symmetric DistanceAn ordered set of points in the plane,

i i i iC = { C , C ,..., C }1 2 N

where

i i i TC = [ x , y ]k k k

2P

t =

A!

p qm = x y f(x,y)pqDistance between point sets

m m10 01m = m = (1)x ym m00 00

γ p+qη = µ /µ , whereγ = + 1.pq pq 00 2Before we can think about distances !

p qµ = (x− m ) (y− m ) f(x,y) (2)pq x ybetween point SET, we need to consider

φ = η +η1 20 02just distance between points.

2 2φ = (η +η ) + 4η2 20 02 11

2 2φ = (η − 3η ) + (3η −η ) (3)3 30 12 21 03The Minkowski distance between two

" #1/pd!POINTS, is

pL (a,b) = ||a − b ||p i i

i=0

Leta∈ A. Find theb∈ B such thatd(a,b) is maximal. Do this for all

a∈ A. The BD is the minimum such distance.$ %→− →−

H(A,B) = max h (a,b), h (b,a) Stretchs(a ,b )i j

is 1 iff(a ) = b orf(a ) = b and zero otherwise.i−1 j i j−1

1An ordered set of points in the plane,

i i i iC = { C , C ,..., C }An ordered set of points in the plane, 1 2 NAn ordered set of points in the plane,

wherei i i ii i i i

i i i TC = { C , C ,..., C }C = { C , C ,..., C }1 2 N1 2 N C = [ x , y ]k k k

wherewhere 2i i i Ti i i T PC = [ x , y ]C = [ x , y ]k k kk k k t =

22 APP !

p qt =t = m = x y f(x,y)pqAA !!

m mp q 10 01p q m = m =m = x y f(x,y)m = x y f(x,y) (1)x ypqpq m m00 00

γ p+qm mm m10 0110 01 η = µ /µ , whereγ = + 1.m = m =m = m = pq pq(1)x y (1)x y 00 2m mm00 0000 !γγ p+qp+q p qη = µ /µ , whereγ = + 1.η = µ /µ , whereγ = + 1.pq pqpq pq 00 µ = (x− m ) (y− m ) f(x,y) (2)00 22 pq x y

!!

p qp qµ = (x− m ) (y− m ) f(x,y) (2)µ = (x− m )y f(x,y) (2)pq x ypq x y φ = η +η1 20 02

2 2φ = (η +η ) + 4η2 20 02 11φ = η +ηφ = η +η1 20 021 20 02 2 2

2 2 φ = (η − 3η ) + (3η −η ) (3)2 2 3 30 12 21 03φ = (η +η ) + 4ηφ = (η +η ) + 4η2 20 022 20 02 1111 " #2 22 2 1/pdφ = (η − 3η ) + (3η −η ) (3)φ = (η − 3η ) + (3 −η ) (3)3 30 12 21 033 30 12 21 03 !

pBottleneck Distance" #" # L (a,b) = ||x − y ||1/p1/p p i idd !!

i=0ppL (a,b) = ||x − y ||L (a,b) = ||x − y ||p i ip i iLet A and B be point sets. Let . Find Leta∈ A. Find theb∈ B such thatd(a,b) is maximal. Do this for all

i=0i=0 a∈ A. The BD is the minimum such distance.

Leta∈ A. Find theb∈ B such thatd(a,b) is maximal. Do this for allLeta∈ A. Findthe such that is maximal. Do theb∈ B such thatd(a,b) is maximal. Do this for all

a∈ A. The BD is the minimum such distance.a∈ A. The BD is the minimum such distance.

this for all a. The BD is the minimum

1

such distance.

11

In their first book on Pattern Recognition in 1973, Duda and Hart used this measure for distance between

clusters. They called it DmaxAn ordered set of points in the plane,

i i i iC = { C , C ,..., C }1 2 N

where

i i i TC = [ x , y ]k k k

2P

An ordered set of points in the plane, t =

Ai i i i !C = { C , C ,..., C }1 2 N p qm = x y f(x,y)pqwhere

i i i T

m mC = [ x , y ] 10 01k k km = m = (1)x ym m00 002P γ p+qη = µ /µ , whereγ = + 1.t =pq pq 00 2A!!

p qp qµ = (x− m ) (y− m ) f(x,y) (2)m = pqx y f(x,y) x ypq

m m10 01m = m = (1)x ym m00 00 φ = η +η1 20 02

γ p+q 2 2η = µ /µ , whereγ = + 1.pq pq φ = (η +η ) + 4η00 2 2 20 02 11! 2 2φ =p (η − 3qη ) + (3η −η ) (3)3 30 12 21 03µ = (x− m ) (y− m ) f(x,y) (2)pq x y

" #1/pd!

pφ = η +η1 20 02L (a,b) = ||x − y ||p i i

2 2Hausdorff Distanceφ = (η +η ) + 4η2 20 02 i=011

2 2φ = (η − 3η ) + (3η −η ) (3)3 30 12 21 03

Leta∈ A. Find theb∈ B such thatd(a,b) is maximal. Do this for all" #1/p →− →−d!Directed Hausdorff distance, , the a∈ A. The BD is the minimum such distance. h (a,b) h (b,a)pL (a,b) = ||x − y ||p i i1maximum over all the points in A of the i=0

11minimum distances to B.

Leta∈ A. Find theb∈ B such thatd(a,b) is maximal. Do this for all

a∈ A. The BD is the minimum such distance.$ %→− →− H(A,B) = max h (a,b), h (b,a)

1Sensitive to outliers.

Well, technically it’s the supremum and infimum, since the sets don’t have to correspond 1:1.

Also, note that this is the largest minimum distance, not the smallest maximum distance like the Bottleneck.