Pattern matching using similarity measures

Abstract

Computers kunnen gebruikt worden om geometrische vormen te herkennen. Dit heeft toepassingen zoals het automatisch lezen van handgeschreven tekst, het zelfstandig oppakken van objecten door robots en het vinden van het meest gelijkende plaatje op internet, gegeven een zoekplaatje. Gelijkenismaten zijn een solide basis voor zulke technieken. Dit proefschrift behandelt de wiskundige en algoritmische aspecten van geli- jkenismaten. Het eerste aspect heeft te maken met de vraag hoe de gelijkenis tussen geometrische patronen zou moeten worden gemeten. Het tweede aspect heeft te maken met de berekening van een gelijkenismaat en de minimalisatie van de waarde van een gelijkenismaat onder geometrische transformaties. In Hoofdstuk 2 presenteer ik een nieuwe theorie die gebruikt wordt voor de analyse van verschillende gelijkenismaten. De aandacht ligt bij gelijkenis- maten die pseudometrieken zijn op een collectie van deelverzamelingen van een ruimte. Zoals de \grote-oh" notatie kan worden gebruikt om uitspraken te doen over de ecientie van algoritmen, zo kan de nieuwe theorie in dit proef- schrift worden gebruikt om zinvolle uitspraken te doen over de robuustheid van gelijkenismaten. The theorie voor gelijkenismaten wordt toegepast in de analyse van zowel bekende gelijkenismaten als nieuwe gelijkenismaten die wor- den geintroduceerd in dit proefschrift. De bestaande gelijkenismaten zijn o.a. de Hausdor metriek en het volume van het symmetrische verschil. De nieuwe gelijkenismaten zijn o.a. het genormaliseerde volume van het symmetrische ver- schil en de re ectie-zichtbaarheids afstand. Eerst bespreek ik de theorie van algemene pseudometrische ruimten. Deze verhandeling gaat onder meer over de transformatiegroep waaronder een pseu- dometrische ruimte invariant is, de topologie behorende bij een pseudometrische ruimte en de operaties die kunnen worden toegepast op een pseudometrische ruimte. Ook laat ik zien hoe de minimalisatie van een pseudometriek onder een transformatiegroep tot een nieuwe pseudometriek leidt die onafhankelijk is van transformaties. Verder laat ik zien hoe een pseudometrische ruimte kan worden uitgebreid met een nieuw element zonder dat de essenti?ele eigenschappen van 171?de oorspronkelijke ruimte verloren gaan. Deze techniek kan worden toegepast om het domein van een gelijkenismaat uit te breiden met de lege verzameling. Vervolgens introduceer ik een nieuwe structuur: de pseudometrische pa- troonruimte. Deze structuur is rijker dan pseudometrische ruimten in het al- gemeen. In het bijzonder maken pseudometrische ruimten de formalisatie van verschillende soorten robuustheid mogelijk. In de vakliteratuur wordt het be- lang van robuustheidseigenschappen voor een gelijkenismaat bevestigd. Echter, zover ik weet, zijn dit soort eigenschappen tot nu toe nooit precies gemaakt. In de vorm van vier axioma's druk ik vier soorten robuustheid uit. Deze vormen van robuustheid heten vervormings robuustheid, vervagings robuustheid, barst robuustheid en ruis robuustheid. Ik bewijs dat de axioma's zich netjes gedragen onder de toepassing van verschillende standaard operaties op pseudometrische patroonruimten. Hierna geef ik een nieuwe methode waarmee verschillende pseudometrieken op een collectie patronen kunnen worden geconstrueerd. De constructie meth- ode is gebaseerd op de toekenningvan re?elwaardige functies aan patronen. Ik bewijs dat eenvoudige voorwaarden op deze toekenning voldoende zijn om de invariantie onder een gegeven transformatiegroep te garanderen. De con- structie methode wordt op verschillende plaatsen in dit proefschrift toegepast, resulterend in nieuwe gelijkenismaten. De nieuw ontwikkelde theorie wordt eerst toegepast om de Hausdor me- triek te analyseren. Dit resulteert in een aantal nieuwe resultaten voor de Hausdor metriek. Ik breid een bestaan resultaat van Matheron [94] uit door te laten zien dat de met de lege verzameling uitgebreide Hausdor metriek precies de \bijziende" topologie denieert op de collectie van alle compacte deelverza- melingen van een metrische \basisruimte". Deze topologie wordt vervolgens gebruikt om eenvoudig te bewijzen dat de Hausdor metriek vervormings, ver- vagings, en barst robuust is. Verder toon ik aan dat in een groot aantal gevallen de Hausdor metriek niet ruis robuust is. Vervolgens analyseer ik een andere gelijkenismaat, het volume van het sym- metrische verschil. In de analyse komen de volgende nieuwe resultaten voort. Ik bewijs dat het volume van het symmetrische verschil een topologie voortbrengt die onvergelijkbaar is met die van de Hausdor metriek. Ook introduceer ik een nieuwe gelijkenismaat die het genormaliseerde volume van het symmetrische verschil wordt genoemd. Ik laat zien dat deze afstandmaat invariant is onder ratio-van-volume behoudende transformaties. Verder bewijs ik dat het volume van het symmetrische verschil en de genormaliseerde versie daarvan aan elk van de vier robuustheidsaxioma's voldoen. Verder introduceer ik een nieuwe gelijkenismaat: de re ectie-zichtbaarheids afstand. De denitie hiervan is gebaseerd op de bovengenoemde construc- tiemethode. De re ectie-zichtbaarheids afstand is een metriek op een vrij al- 172?gemene klasse van (k