Teoria e Tecniche del Riconoscimento Hausdorff Distance http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html Cosimo Distante [email protected] • 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. D( A, B) min min d (a, b) aA bB - 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 Oss. Il concetto classico di distanza non tiene conto della forma degli oggetti Esempio 2 D 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: h( A, B) max min d (a, b) aA bB Si può considerare “d(∙, ∙)” come la distanza Euclidea 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 h( A, B) max min d (a, b) ovvero h(A,B)≠h(B,A) aA bB • Causato dal fatto che le funzioni di massimo sono asimmetriche, mentre quelle di minimo sono simmetriche Cos’è la distanza di Hausdorff? • Una definizione generale della distanza di Hausdorff è data da H ( A, B) max h( A, B), h( B, A) • 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) • 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