Teoria e Tecniche del Riconoscimento

Cosimo Distante

cosimo.distante@ino.it

Hausdorff Distance

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

• Quando si parla di distanze di solito intendiamo quelle minime.

• Esempio: Se un punto X è alla distanza D da un poligono P intendiamo dire che X è a distanza D dal punto più vicino di P.

• Lo stesso dicasi per due poligoni. Se A e B sono due poligoni, la distanza minima è quella più corta tra tutti i punti di A e quelli di B

• D è una funzione in cui va trovato il minimo.

),(minmin),( badBADBbAa

- Per ogni punto a di A trova il punto di B a distanza minima.

- Quindi trova tra tutti i punti di A quello che ha minima distanza

Limitazioni del concetto classico di distanza che si possono avere in alcune applicazioni

Esempio 1

D

Esempio 2

D

Oss. Il concetto classico di distanza non tiene conto della forma degli oggetti

Stessa D tra i due esempi ma qualcosa è cambiato!

Cos’è la distanza di Hausdorff?

• Introdotta da Felix Hausdorff (1868-1942)

• “È la distanza massima di un insieme di punti vicini ad un altro insieme”

• Ovvero:

Si può considerare “d(∙, ∙)” come la distanza Euclidea

),(minmax),( badBAhBbAa

Cos’è la distanza di Hausdorff?

• Brute Force algorithm

1. h = 0

2.for every point ai of A,      2.1  shortest = Inf ;      2.2  for every point bj of B                    dij = d (ai , bj )                    if dij

< shortest then                              shortest = dij

      2.3  if shortest > h then

                    h = shortest

This general condition also holds for the example, as

• h(A, B) = d(a1, b1),

• while h(B, A) = d(b2, a1).

Cos’è la distanza di Hausdorff?

• La distanza di Hausdorff è orientata ovvero h(A,B)≠h(B,A)

• Causato dal fatto che le funzioni di massimo sono asimmetriche, mentre quelle di minimo sono simmetriche

),(minmax),( badBAhBbAa

Cos’è la distanza di Hausdorff?

• Una definizione generale della distanza di Hausdorff è data da

• Che è la distanza tra i due insiemi A e B mentre:

• h(A,B) è la distanza da A a B (forward)

• h(B,A) distanza da B ad A (backward)

),(),,(max),( ABhBAhBAH

• If sets A and B are made of lines or polygons instead of single points, then H(A, B) applies to all defining points of these lines or polygons, and not only to their vertices.

• The brute force algorithm could no longer be used for computing Hausdorff distance between such sets, as they involve an infinite number of points.

Hausdorff distance shown around extremum of each triangles. Each circle has a radius of H( P1 , P2).

Hausdorff distance for the triangles at the same shortest distance, but in different position

Application Examples

One of the main application of the Hausdorff distance is image matching, used for instance in image analysis, visual navigation of robots, computer-assisted surgery, etc.

Basically, the Hausdorff metric will serve to check if a template image is present in a test image ;  the lower the distance value, the best the match.

That method gives interesting results, even in presence of noise or occlusion (when the target is partially hidden).

Application Examples

Template

Application Examples

Template