Hausdorffova vzdálenost - Hausdorff distance

v matematika, Hausdorffova vzdálenostnebo Hausdorffova metrika, také zvaný Vzdálenost Pompeiu – Hausdorff,^[1][2] měří, jak daleko dva podmnožiny a metrický prostor jsou od sebe navzájem. Ukazuje sadu neprázdný kompaktní podmnožiny metrického prostoru do samostatného metrického prostoru. Je pojmenován po Felix Hausdorff a Dimitrie Pompeiu.

Neformálně jsou dvě sady blízko Hausdorffovy vzdálenosti, pokud je každý bod kterékoli sady blízko nějakému bodu druhé sady. Hausdorffova vzdálenost je nejdelší vzdálenost, na kterou vás může přinutit protivník, který si vybere bod v jedné ze dvou sad, odkud pak musíte cestovat do druhé sady. Jinými slovy, je to největší ze všech vzdáleností od bodu v jedné sadě k nejbližšímu bodu ve druhé sadě.

Zdá se, že tuto vzdálenost poprvé představil Hausdorff ve své knize Grundzüge der Mengenlehre, poprvé publikováno v roce 1914, ačkoli v disertační práci z Maurice Fréchet v roce 1906, ve své studii o prostoru všech spojitých křivek z ${ displaystyle [0,1] to mathbb {R} ^ {3}}$.

Definice

Součásti výpočtu Hausdorffovy vzdálenosti mezi zelenou čarou X a modrá čára Y.

Nechat X a Y být dvě neprázdné podmnožiny metrického prostoru ${ displaystyle (M, d)}$. Definujeme jejich Hausdorffovu vzdálenost ${ displaystyle d _ { mathrm {H}} (X, Y)}$ podle

${ displaystyle d _ { mathrm {H}} (X, Y) = max vlevo {, sup _ {x v X} inf _ {y v Y} d (x, y), , sup _ {y in Y} inf _ {x in X} d (x, y) , right }, !}$

kde sup představuje supremum a inf the infimum.

Ekvivalentně

${ displaystyle d_ {H} (X, Y) = inf { varepsilon geq 0 ,; X subseteq Y _ { varepsilon} { text {a}} Y subseteq X _ { varepsilon} }, quad}$^[3]

kde

${ displaystyle X _ { varepsilon}: = bigcup _ {x v X} {z v M ,; d (z, x) leq varepsilon },}$

tj. množina všech bodů uvnitř ${ displaystyle varepsilon}$ sady ${ displaystyle X}$ (někdy nazývaný ${ displaystyle varepsilon}$-zkrmování ${ displaystyle X}$ nebo zobecněný míč poloměru ${ displaystyle varepsilon}$ kolem ${ displaystyle X}$).

Ekvivalentně

${ displaystyle d_ {H} (X, Y) = sup _ {w v M} vlevo | inf _ {x v X} d (w, x) - inf _ {y v Y} d (w, y) right | = sup _ {w in X cup Y} left | inf _ {x in X} d (w, x) - inf _ {y in Y} d (w, y) vpravo |,}$^[1]

to je ${ displaystyle d _ { mathrm {H}} (X, Y) = sup _ {w v M} | d (w, X) -d (w, Y) |}$, kde ${ displaystyle d (w, X)}$ je vzdálenost od bodu ${ displaystyle w}$ do sady ${ displaystyle X}$.

Poznámka

To neplatí pro libovolné podmnožiny ${ displaystyle X, Y podmnožina M}$ že ${ displaystyle d _ { mathrm {H}} (X, Y) = varepsilon}$ naznačuje

${ displaystyle X subseteq Y _ { varepsilon} { mbox {a}} Y subseteq X _ { varepsilon}.}$

Zvažte například metrický prostor reálných čísel ${ displaystyle mathbb {R}}$ s obvyklou metrikou ${ displaystyle d}$ vyvolané absolutní hodnotou,

${ displaystyle d (x, y): = | y-x |, quad x, y in mathbb {R}.}$

Vzít

${ displaystyle X: = (0,1] quad { mbox {a}} quad Y: = [- 1,0).}$

Pak ${ displaystyle d _ { mathrm {H}} (X, Y) = 1 }$. nicméně ${ displaystyle X nsubseteq Y_ {1}}$ protože ${ displaystyle Y_ {1} = [- 2,1) }$, ale ${ displaystyle 1 v X}$.

Ale je pravda, že ${ displaystyle X subseteq { overline {Y _ { varepsilon}}}}$ a ${ displaystyle Y subseteq { overline {X _ { varepsilon}}}}$ ; zejména platí, pokud ${ displaystyle X, Y}$ jsou zavřené.

Vlastnosti

• Obecně, ${ displaystyle d _ { mathrm {H}} (X, Y)}$ může být nekonečný. Pokud obojí X a Y jsou ohraničený, pak ${ displaystyle d _ { mathrm {H}} (X, Y)}$ je zaručeno, že bude konečný.
• ${ displaystyle d _ { mathrm {H}} (X, Y) = 0}$ kdyby a jen kdyby X a Y mít stejné uzavření.
• Za každý bod X z M a všechny neprázdné sady Y, Z z M: d(X,Y) ≤ d(X,Z) + d_H(Y,Z), kde d(X,Y) je vzdálenost mezi bodem X a nejbližší bod v sadě Y.
• | průměr (Y)-průměr(X)| ≤ 2 d_H(X,Y).^[4]
• Pokud křižovatka X ∩ Y má neprázdný interiér, pak existuje konstanta r > 0, takže každá sada X' jehož Hausdorffova vzdálenost od X je méně než r také protíná Y.^[5]
• Na množině všech podskupin M, d_H poskytuje prodloužený pseudometrické.
• Na scéně F(M) všech neprázdných kompaktních podmnožin M, d_H je metrika.
  • Li M je kompletní, pak také je F(M).^[6]
  • Li M je kompaktní, tak také je F(M).
  • The topologie z F(M) závisí pouze na topologii M, ne na metriku d.

Motivace

Definici Hausdorffovy vzdálenosti lze odvodit řadou přirozených rozšíření funkce vzdálenosti ${ displaystyle d (x, y)}$ v podkladovém metrickém prostoru M, jak následuje:^[7]

• Definujte funkci vzdálenosti mezi libovolným bodem X z M a jakoukoli neprázdnou sadu Y z M podle:

${ displaystyle d (x, Y) = inf {d (x, y) uprostřed y v Y }. }$

Například, d(1, {3,6}) = 2 a d(7, {3,6}) = 1.

• Definujte funkci vzdálenosti mezi libovolnými dvěma neprázdnými sadami X a Y z M podle:

${ displaystyle d (X, Y) = sup {d (x, Y) střední x v X }. }$

Například, ${ textstyle d ( {1,7 }, {3,6 }) = sup {d (1, {3,6 }), d (7, {3,6 } ) } = sup {d (1,3), d (7,6) } = 2.}$

• Li X a Y jsou pak kompaktní d(X,Y) bude konečný; d(X,X) = 0; a d zdědí nerovnost trojúhelníku vlastnost z funkce vzdálenosti v M. Jak to stojí, d(X,Y) je ne metrika, protože d(X,Y) není vždy symetrický a d(X,Y) = 0 to neznamená X = Y (To naznačuje, že ${ displaystyle X subseteq Y}$). Například, d({1,3,6,7}, {3,6}) = 2, ale d({3,6}, {1,3,6,7}) = 0. Můžeme však vytvořit metriku definováním Hausdorffova vzdálenost být:

${ displaystyle d _ { mathrm {H}} (X, Y) = max {d (X, Y), d (Y, X) } ,.}$

Aplikace

v počítačové vidění, Hausdorffovu vzdálenost lze použít k vyhledání dané šablony v libovolném cílovém obrázku. Šablona a obrázek jsou často předem zpracovány prostřednictvím detektor hran dávat a binární obraz. Dále je každý 1 (aktivovaný) bod v binárním obrazu šablony považován za bod v množině, „tvar“ šablony. Podobně se s oblastí binárního cílového obrazu zachází jako s množinou bodů. Algoritmus se poté pokusí minimalizovat Hausdorffovu vzdálenost mezi šablonou a určitou oblastí cílového obrazu. Oblast v cílovém obrazu s minimální Hausdorffovou vzdáleností od šablony lze považovat za nejlepšího kandidáta pro umístění šablony v cíli.^[8]v počítačová grafika Hausdorffova vzdálenost se používá k měření rozdílu mezi dvěma různými reprezentacemi stejného 3D objektu^[9] zvláště při generování úroveň detailu pro efektivní zobrazení složitých 3D modelů.

Související pojmy

Míra odlišnosti dvou tvarů je dána vztahem Hausdorffova vzdálenost až do izometrie, označeno D_H. Jmenovitě X a Y být dvě kompaktní postavy v metrickém prostoru M (obvykle a Euklidovský prostor ); pak D_H(X,Y) je infimum of d_H(Já(X),Y) spolu izometrie Já metrického prostoru M pro sebe. Tato vzdálenost měří, jak daleko jsou tvary X a Y jsou izometrické.

The Konvergence Gromov – Hausdorff je související myšlenka: měříme vzdálenost dvou metrických prostorů M a N tím, že vezmeme infimum ${ displaystyle d _ { mathrm {H}} (I (M), J (N))}$ podél všech izometrických vložení ${ displaystyle I colon M to L}$ a ${ displaystyle J dvojtečka N až L}$ do nějakého společného metrického prostoru L.

Viz také

• Wijsmanova konvergence
• Kuratowského konvergence
• Hemikontinuita
• Fréchetova vzdálenost

Reference

externí odkazy

• Hausdorffova vzdálenost mezi konvexními polygony.
• Pomocí MeshLab k měření rozdílu mezi dvěma povrchy Krátký návod, jak vypočítat a vizualizovat Hausdorffovu vzdálenost mezi dvěma trojúhelníkovými 3D povrchy pomocí nástroje open source MeshLab.
• MATLAB kód pro vzdálenost Hausdorff: [1]