A Gromov–Hausdorff-távolság

A hétköznapi életben két dolgot sokszor hasonlónak nevezünk, ha valamilyen (az aktuális feladathoz jól passzoló) mérőszám szerint kicsi az eltérésük. Vagy ha úgy tetszik: valamilyen alkalmas távolságfogalom szerint a távolságuk kicsi. Nézzünk egy egyszerű példát: tömegközlekedéssel akarunk eljutni a moziba, és azt látjuk, hogy a buszmegálló $170$ méterre van a mozitól, a villamosmegálló pedig $174$ méterre. Ilyenkor azt mondhatjuk, hogy a feladat szempontjából a két megálló hasonló, hiszen az általuk meghatározott két útvonal eltérése kicsi. Két útvonal eltérésén itt most a $\vert 174-170\vert=4$ mérőszámot értjük, ami ha gyaloglásról van szó, méterben számolva valóban elenyésző.

Ebben a rövid írásban két távolságfogalomról lesz szó, a Hausdorff-távolságról, és a Gromov–Hausdorff-távolságról. Annak idején mindkettőt tisztán elméleti okokból definiálták, manapság azonban (a továbbfejlesztett verzióikkal együtt) az alkalmazott tudományokban is komoly szerepet játszanak.

1. Halmazok Hausdorff-távolsága

Két lépésben fogunk eljutni a Gromov–Hausdorff-távolsághoz. Elsőként a Hausdorff-távolságról lesz szó, ami azt méri, hogy egy adott tér részhalmazai milyen távol vannak egymástól. Pongyolán szólva, két halmaz, $A$ és $B$ akkor van egymáshoz közel, ha $A$ minden eleméhez van olyan eleme $B$ -nek, ami hozzá közel van, és megfordítva, $B$ minden eleméhez található olyan elem $A$ -ban, ami hozzá közel van. Nézzünk egy nagyon egyszerű példát: vegyük a piros pontokból álló $A$ halmazt és a kék pontokból álló $B$ halmazt.

1. ábra. halmaz: piros pontok, $B$ halmaz: kék pontok.

Az $A$ halmazt befedhetjük $r$ sugarú gömbökkel úgy, hogy minden egyes pontjára ráteszünk egyet-egyet, jelöljük az így kapott halmazt $A_r$ -rel:

2. ábra. $A_r$ : az $A$ halmaz befedése $r$ sugarú gömbökkel.

Olyan $r$ számot keresünk, amelyre az $A_r$ halmaz lefedi $B$ -t is, és a hasonlóképp elkészített $B_r$ halmaz is lefedi $A$ -t.

3.ábra. $A_r$ lefedi $B$ -t, és $B_r$ is lefedi $A$ -t.

A legkisebb ilyen $r$ számot nevezzük $A$ és $B$ Hausdorff-távolságának. Ezt a távolságot Felix Hausdorff vezette be az 1914-ben megjelent, A halmazelmélet alapjai című könyvében. Manapság rengeteget használják többek közt a számítógépes látásban: tipikus feladat, hogy egy képen be kell azonosítani egy objektumot (lásd például [5] 858. oldal, vagy [6]). Az alábbi ábrán a bal oldali kis repülőt kell megtalálni a középső képen. A jobb oldali képen láthatjuk, hogy a kép mely részén lép fel az alakzatok közti legkisebb Hausdorff-távolság.

4. ábra. A képek Grégoire-tól és Bouillot-tól származnak [6]

Felix Hausdorff a XX. századi matematika egyik legnagyobb hatású alakja. A topológia, a halmazelmélet, a mértékelmélet és a funkcionálanalízis területén is maradandót alkotott, de nevezhetnénk akár ezen tudományterületek egyik megalapozójának is. Egyebek mellett ő vezette be a fraktálok elméletében oly fontos mérték és dimenzió fogalmakat, amelyeket ma már Hausdorff-mértéknek és Hausdorff-dimenziónak neveznek. Paul Mongré néven irodalmi munkákat is publikált [9]. 1900-ban kiadott egy verseskötetet Ekstasen címmel, a Den Ungeflügelten című verse németül és angolul elolvasható a [3] cikkben

A Hausdorff-távolság fenti bevezetésénél több ponton is pongyolák voltunk. Jöjjön most a pontos definíció. Egy $\varrho$ függvénnyel ellátott $X$ halmazt – röviden: az $(X,\varrho)$ párt – metrikus térnek nevezünk, ha $\varrho$ teljesít három nagyon természetes tulajdonságot (az ilyen függvényeket metrikának nevezzük):

$\bullet$ $\varrho(x,y)=0$ akkor és csak akkor, ha $x=y$ . Tehát két pont pontosan akkor van egymástól nulla $\varrho$ -távolságra, ha $x$ és $y$ ugyanaz a pont.

$\bullet$ $\varrho(x,y)=\varrho(y,x)$ . Tehát az $x$ pont $\varrho$ -távolsága $y$ -tól ugyanannyi, mint az $y$ pont $\varrho$ -távolsága $x$ -től.

$\bullet$ . Tehát egy harmadik $z$ pontot beiktatva, az $x$ és $z$ , valamint $z$ és $y$ $\varrho$ -távolságát megmérve és összeadva legalább akkora értéket kell kapnunk, mintha közvetlenül az $x$ és $y$ $\varrho$ -távolságát mértük volna meg. (Ez az úgynevezett háromszög-egyenlőtlenség.)

Egy metrikus térben ugyanúgy vezetjük be az $x$ középpontú $r$ sugarú gömb fogalmát, mint a síkon: azon $y$ pontok halmaza, amelyekre $\varrho(x,y)<r$ teljesül. Hasonlóan a fentiekhez, $A_r$ -rel és $B_r$ -rel fogjuk jelölni azokat a halmazokat, amelyeket úgy kapunk, hogy $A$ illetve $B$ minden pontjára ráteszünk egy-egy $r$ sugarú gömböt. Olyan $r$ -eket keresünk, amelyekre $B\subseteq A_r$ és $A\subseteq B_r$ egyszerre teljesül. Lehet, hogy nincs legkisebb ilyen $r$ , de a $d_{\mathcal{H}}^X(A,B)$ -vel jelölt Hausdorff-távolság alábbi definíciója értelmes:

$\displaystyle d_{\mathcal{H}}^X (A,B):=\inf\{r\geq0 \mid B\subseteq A_r,~A\subseteq B_r\}.$

A jelölésben feltüntettük, hogy $A$ és $B$ az $X$ térnek a részhalmazai, később ez fontos lesz.

Az alakfelismerés szempontjából a Hausdorff-távolságnak van egy gyenge pontja. Gondoljunk arra, hogy mi történne, ha a 4. ábrán látható kis repülőt (amit a középső képen fel kell ismerni) $45$ fokkal elforgatnánk a pilótafülke körül. Az így kapott képnek és a középső képen látható másának Hausdorff-távolsága már nagy lenne, így az az eljárás, ami a kicsi Hausdorff-távolságot keresi, már nem találná őket hasonlónak. Térjünk vissza az 1. ábrán látható ponthalmazokhoz. Láttuk, hogy elég nagy $r$ -re van szükségünk, hogy $A\subseteq B_r$ és $B\subseteq A_r$ is fennálljon. Hogy milyen értelemben nagy ez az $r$ , az rögtön kiderül. Képzeljük úgy, hogy a kék és piros ponthalmaz egy-egy üveglapra van felfestve.

6.ábra. $A$ és $B$ egy-egy üveglapra felfestve, egymásra helyezve és külön-kölön.

Ha jogunkban áll ezt a két üveglapot mozgatni, sőt akár meg is lehet őket fordítani, akkor könnyen észrevehetjük, hogy a két alakzat nagyon hasonló.

7. ábra. $A$ és $B$ egymáshoz igazítva.

Látható, hogy a korábbinál sokkal kisebb $r$ is elegendő, hogy $A_r$ lefedje $B$ -t, és $B_r$ is lefedje $A$ -t.

8.ábra. A korábbinál sokkal kisebb $r$ is elegendő.

2. Metrikus terek Gromov–Hausdorff-távolsága

Azt láttuk, hogy ugyanazoknak a halmazoknak különböző realizációihoz más Hausdorff-távolság tartozik. A fenti eljárással akár két különböző térben lévő halmaz Hausdorff-távolságát is megmérhetjük. Legyen $A$ az $(X_,\varrho_X)$ , $B$ pedig az $(Y,\varrho_Y)$ metrikus tér egy-egy részhalmaza. Legyen továbbá $(Z,\varrho_Z)$ egy harmadik metrikus tér, amelybe $X$ és $Y$ is izometrikusan beágyazható, azaz léteznek olyan $f\colon X\to Z$ és $g\colon Y\to Z$ függvények, amelyekre $\varrho_Z\big(f(x_1),f(x_2)\big)=\varrho_X(x_1,x_2)$ minden $x_1,x_2\in X$ -re és $\varrho_Z\big(g(y_1),g(y_2)\big)=\varrho_Y(y_1,y_2)$ minden $y_1,y_2\in Y$ -ra. Ekkor megadhatjuk $A$ és $B$ Hausdorff-távolságát a $(Z,\varrho_Z)$ metrikus térben az $f$ és $g$ realizációk mentén:

$\displaystyle d_{\mathcal{H}}^{f,g,Z}(A,B):=d_{\mathcal{H}}^Z\big(f(A),g(B)\big).$

(1)

A Gromov által felfedezett távolság célja, hogy különböző metrikus terek hasonlóságát mérje: két metrikus tér $(X,\varrho_X)$ és $(Y,\varrho_Y)$ Gromov–Hausdorff-távolsága azt mondja meg, hogy a két tér milyen távol van attól, hogy egymással izomorf legyen. (Két metrikus tér izomorf, ha van köztük olyan kölcsönösen egyértelmű megfeleltetés, amely megőrzi a távolságot.)

Ha a fenti (1) formulába $A$ helyére magát $X$ -et, $B$ helyére pedig $Y$ -t helyettesítjük, akkor azt kapjuk, hogy $X$ és $Y$ realizációi az $f$ és $g$ függvények mentén mennyire térnek el egymástól a $(Z,\varrho_Z)$ térben. Két tér $d_{\mathcal{GH}}(X,Y)$ -nal jelölt Gromov–Haudorff-távolságát úgy kapjuk meg, hogy vesszük $X$ és $Y$ összes lehetséges $f,g$ realizációját az összes lehetséges $Z$ térben, kiszámítjuk a $d_{\mathcal{H}}^{f,g,Z}(X,Y):=d_{\mathcal{H}}^Z\big(f(X),g(Y)\big)$ értékeket, és vesszük ezeknek a legnagyobb alsó korlátját:

$\displaystyle d_{\mathcal{GH}}(X,Y)=\inf_{f,g,Z}d_{\mathcal{H}}^{f,g,Z}(X,Y).$

A Gromov–Hausdorff-távolságnak (és a bizonyos értelemben vett továbbfejlesztésének, így például a Gromov–Wasserstein-távolságnak) is vannak modern alkalmazásai például az alakfelismerésben és a gépi tanulásban, lásd például [1], [4], [7], [2]. Itt most ezekre nem térünk ki. A cikket a Gromov–Hausdorff-tér és a Gromov–Hausdorff-konvergencia vázlatos bemutatásával zárjuk. Ezek a fogalmak fontos szerepet játszottak a híres Milnor-Wolf sejtés igazolásánál (lásd a Gromovról szóló színes írást a cikk végén).

Be lehet bizonyítani, hogy a fent bevezetett $d_{\mathcal{GH}}$ távolsággal a kompakt metrikus terek izometriaosztályai maguk is egy kompakt metrikus teret alkotnak, ezt nevezik a Gromov–Hausdorff-térnek. Mint minden metrikus térben, itt is bevezethető a konvergencia fogalma: az $\big((X_n,\varrho_n)\big)_{n\in\mathbb{N}}$ térsorozat konvergál az $(X,\varrho)$ metrikus térhez, ha a $d_{\mathcal{GH}}(X,X_n)$ számsorozat 0-hoz tart.

Nézzünk egy egyszerű példát: tegyük fel, hogy egy négyzetlapra illesztett négyzetrácson élünk. (Legyen a rács az $X_n$ , két pont $\varrho_n$ távolsága pedig legyen az őket összekötő legrövidebb út hossza.) Mondhatjuk, hogy ez a négyzetlapnak egy leegyszerűsített változata. Az egyszerűsítés ára, hogy a kék $(x_1,y_1)$ pontból a piros $(x_2,y_2)$ pontba csak meglehetősen szögletes utak mentén tudunk eljutni.

9. ábra. Legrövidebb út a rácson és a hagyományos négyzetlapon.

Persze gondolhatjuk, hogy minél finomabb rácsot veszünk, annál jobban fog hasonlítani az utunk a megszokotthoz, azaz ahhoz, amikor a négyzetlap két pontját egyenes vonallal kötjük össze.

10. ábra. Út az egyre finomodó rácsokon.

A kérdés, hogy valóban a szokásos négyzetlapot kapjuk-e meg határértékben. Azt kell észrevenni, hogy bármilyen finom négyzetrácsot is választunk, és bármennyire is hasonlít a töröttvonalunk az egyenes vonalhoz, a töröttvonal hossza mindig $\vert x_1-x_2\vert+\vert y_1-y_2\vert$ . Tehát az $(X_n,\varrho_n)$ térsorozat Gromov–Hausdorff limesze a négyzetlap, de nem a hagyományos euklidészi távolsággal: $\varrho_{E}\big((x_1,y_1),(x_2,y_2)\big)=\sqrt{\vert x_1-x_2\vert^2+\vert y_1-y_2\vert^2}$ , hanem a $\varrho\big((x_1,y_1),(x_2,y_2)\big)=\vert x_1-x_2\vert+\vert y_1-y_2\vert$ távolsággal.

Mihail Gromov orosz–francia matematikus, a metrikus geometria, a szimplektikus geometria, és a geometriai csoportelmélet úttörője. Egyik leghíresebb eredménye a Milnor és Wolf nevéhez fűződő sejtés igazolása: egy végesen generált csoport pontosan akkor polinomiális növekedésű, ha van véges indexű nilpotens részcsoportja. Elnyerte többet közt az Élie Cartan-díjat, a Wolf-díjat, a Kiotó-díjat és az Abel-díjat. Mihail Gromov a 2005-ös Bolyai János nemzetközi matematikai díj kitüntetettje, 2010 óta a Magyar Tudományos Akadémia tiszteletbeli tagja.

Irodalomjegyzék

[1] Bronstein, A.M.; Bronstein, M.M.; Bruckstein, A.M.; Kimmel, R., Analysis of Two-Dimensional Non-Rigid Shapes, International Journal of Computer Vision, 78(1), 2007, 67–88.

[2] Chowdhury, S.; Miller, D.; Needham, T., Quantized Gromov–Wasserstein, ArXiv: 2104.02013.

[3] ELKINS, B., Felix Hausdorff’s Poem “Den Ungeflügelten”, Journal of Humanistic Mathematics, 11 (2), 2021, pages 405–408.

[4] Fehri, A.; Velasco-Forero, S.; Meyer, F., Characterizing Images by the Gromov-Hausdorff Distances Between Derived Hierarchies, 25th IEEE International Conference on Image Processing (ICIP), 2018, 1213–1217.

[5] Huttenlocher, D.P.; Klanderman, G.A.; Rucklidge, W.J., Comparing images using the Hausdorff distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15 (9), 1993, 850–863.

[6] Grégoire, N.; Bouillot, M., Hausdorff distance between convex polygons

[7] Mémoli, F., Gromov–Wasserstein Distances and the Metric Approach to Object Matching, Found Comput Math 11, 2011, 417–487.

[8] Mongré, P., Ekstasen, Verlag H. Seemann Nachf., Leipzig, 1900.

[9] Purkert, W, The double life of Felix Hausdorff/ Paul Mongré, The Mathematical Intelligencer, 30(4), 2008, 36–50.

Titkos Tamás
Rényi Alfréd Matematikai Kutatóintézet