Distància de Hausdorff

Components del càlcul de la distància de Hausdorff entre la corba verda X i la corba blava Y .

En matemàtiques, la distància de Hausdorff, o mètrica de Hausdorff, també anomenada distància de Pompeu–Hausdorff, mesura la distància entre dos subconjunts d'un espai mètric. Converteix el conjunt de subconjunts compactes no buits d'un espai mètric en un espai mètric per dret propi. Porta el nom de Felix Hausdorff i Dimitrie Pompeiu.

De manera informal, dos conjunts estan propers a la distància de Hausdorff si cada punt de qualsevol conjunt està a prop d'algun punt de l'altre conjunt. La distància de Hausdorff és la distància més llarga que pot ser obligat a recórrer un adversari que escull un punt d'un dels dos conjunts, des d'on després hauràs de viatjar a l'altre conjunt. En altres paraules, és la més gran de totes les distàncies des d'un punt d'un conjunt fins al punt més proper de l'altre conjunt.

Aquesta distància la va introduir per primera vegada Hausdorff en el seu llibre Grundzüge der Mengenlehre, publicat per primera vegada el 1914, tot i que un parent molt proper va aparèixer a la tesi doctoral de Maurice Fréchet el 1906, en el seu estudi de l'espai de totes les corbes contínues des de $[0,1]\to \mathbb {R} ^{3}$.

Definició

Sigui$(M,d)$ un espai mètric. Per a cada parell de subconjunts no buits $X\subset M$ i $Y\subset M$, la distància de Hausdorff entre $X$ i $Y$ es defineix com$$d_{\mathrm {H} }(X,Y):=\max \left\{\,\sup _{x\in X}d(x,Y),\ \sup _{y\in Y}d(X,y)\,\right\},$$on $\operatorname {sup}$ representa l'operador suprem, $\operatorname {inf}$ l'operador infim, i on $d(a,B):=\inf _{b\in B}d(a,b)$ quantifica la distància des d'un punt $a\in X$ al subconjunt $B\subseteq X$ .

Una definició equivalent és la següent. Per a cada conjunt $X\subset M,$ sigui$$X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},$$que és el conjunt de tots els punts dins $\varepsilon$ del conjunt $X$ (de vegades anomenat $\varepsilon$ -engreix de $X$ o una bola de radi generalitzada $\varepsilon$ al voltant $X$). Aleshores, la distància entre Hausedorff $X$ i $Y$ es defineix com

$$d_{H}(X,Y):=\inf\{\varepsilon \geq 0\mid X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\}.$$

Aplicacions

Pol oceànic d'inaccessibilitat a

En visió per computador, la distància de Hausdorff es pot utilitzar per trobar una plantilla determinada en una imatge objectiu arbitrària. La plantilla i la imatge solen ser preprocessades mitjançant un detector de vores que dona una imatge binària. A continuació, cada punt 1 (activat) de la imatge binària de la plantilla es tracta com un punt d'un conjunt, la "forma" de la plantilla. De la mateixa manera, una àrea de la imatge binària objectiu es tracta com un conjunt de punts. Aleshores, l'algorisme intenta minimitzar la distància de Hausdorff entre la plantilla i alguna àrea de la imatge objectiu. L'àrea de la imatge de destinació amb la distància mínima de Hausdorff a la plantilla es pot considerar el millor candidat per localitzar la plantilla a l'objectiu. En gràfics per ordinador, la distància de Hausdorff s'utilitza per mesurar la diferència entre dues representacions diferents del mateix objecte 3D especialment quan es genera un nivell de detall per a la visualització eficient de models 3D complexos.

Si $X$ és la superfície de la terra, i $Y$ és la superfície terrestre de la terra, llavors en trobar el punt Nemo, veiem $d_{H}(X,Y)$ és d'uns 2.704,8 km.