Pattern matching using similarity measures

Abstract

Computers kunnen gebruikt worden om geometrische vormen te herkennen.
\nDit heeft toepassingen zoals het automatisch lezen van handgeschreven tekst,
\nhet zelfstandig oppakken van objecten door robots en het vinden van het meest
\ngelijkende plaatje op internet, gegeven een zoekplaatje. Gelijkenismaten zijn
\neen solide basis voor zulke technieken.
\nDit proefschrift behandelt de wiskundige en algoritmische aspecten van geli-
\njkenismaten. Het eerste aspect heeft te maken met de vraag hoe de gelijkenis
\ntussen geometrische patronen zou moeten worden gemeten. Het tweede aspect
\nheeft te maken met de berekening van een gelijkenismaat en de minimalisatie
\nvan de waarde van een gelijkenismaat onder geometrische transformaties.
\nIn Hoofdstuk 2 presenteer ik een nieuwe theorie die gebruikt wordt voor
\nde analyse van verschillende gelijkenismaten. De aandacht ligt bij gelijkenis-
\nmaten die pseudometrieken zijn op een collectie van deelverzamelingen van een
\nruimte. Zoals de \\grote-oh" notatie kan worden gebruikt om uitspraken te
\ndoen over de ecientie van algoritmen, zo kan de nieuwe theorie in dit proef-
\nschrift worden gebruikt om zinvolle uitspraken te doen over de robuustheid
\nvan gelijkenismaten. The theorie voor gelijkenismaten wordt toegepast in de
\nanalyse van zowel bekende gelijkenismaten als nieuwe gelijkenismaten die wor-
\nden geintroduceerd in dit proefschrift. De bestaande gelijkenismaten zijn o.a.
\nde Hausdor metriek en het volume van het symmetrische verschil. De nieuwe
\ngelijkenismaten zijn o.a. het genormaliseerde volume van het symmetrische ver-
\nschil en de re ectie-zichtbaarheids afstand.
\nEerst bespreek ik de theorie van algemene pseudometrische ruimten. Deze
\nverhandeling gaat onder meer over de transformatiegroep waaronder een pseu-
\ndometrische ruimte invariant is, de topologie behorende bij een pseudometrische
\nruimte en de operaties die kunnen worden toegepast op een pseudometrische
\nruimte. Ook laat ik zien hoe de minimalisatie van een pseudometriek onder een
\ntransformatiegroep tot een nieuwe pseudometriek leidt die onafhankelijk is van
\ntransformaties. Verder laat ik zien hoe een pseudometrische ruimte kan worden
\nuitgebreid met een nieuw element zonder dat de essenti?ele eigenschappen van
\n171?de oorspronkelijke ruimte verloren gaan. Deze techniek kan worden toegepast
\nom het domein van een gelijkenismaat uit te breiden met de lege verzameling.
\nVervolgens introduceer ik een nieuwe structuur: de pseudometrische pa-
\ntroonruimte. Deze structuur is rijker dan pseudometrische ruimten in het al-
\ngemeen. In het bijzonder maken pseudometrische ruimten de formalisatie van
\nverschillende soorten robuustheid mogelijk. In de vakliteratuur wordt het be-
\nlang van robuustheidseigenschappen voor een gelijkenismaat bevestigd. Echter,
\nzover ik weet, zijn dit soort eigenschappen tot nu toe nooit precies gemaakt. In
\nde vorm van vier axioma's druk ik vier soorten robuustheid uit. Deze vormen
\nvan robuustheid heten vervormings robuustheid, vervagings robuustheid, barst
\nrobuustheid en ruis robuustheid. Ik bewijs dat de axioma's zich netjes gedragen
\nonder de toepassing van verschillende standaard operaties op pseudometrische
\npatroonruimten.
\nHierna geef ik een nieuwe methode waarmee verschillende pseudometrieken
\nop een collectie patronen kunnen worden geconstrueerd. De constructie meth-
\node is gebaseerd op de toekenningvan re?elwaardige functies aan patronen.
\nIk bewijs dat eenvoudige voorwaarden op deze toekenning voldoende zijn om
\nde invariantie onder een gegeven transformatiegroep te garanderen. De con-
\nstructie methode wordt op verschillende plaatsen in dit proefschrift toegepast,
\nresulterend in nieuwe gelijkenismaten.
\nDe nieuw ontwikkelde theorie wordt eerst toegepa