Ein von der DFG gefördertes Projekt am Fachbereich für Mathematik und Informatik der Freien Universität Berlin.

Beteiligte Mitarbeiter und Studenten

Projektleiter:	Prof. Dr. Helmut Alt
Wissenschaftliche Mitarbeiter:	Christian Knauer
	Lutz Meissner
	Carola Wenk
Diplomanden:	Oliver Timm

Die behandelten Probleme

In vielen Teilbereichen der Computergraphik, der Bildverarbeitung und der Computer-Vision stellt sich das Problem die Ähnlichkeit zweier gegebener Formen festzustellen oder herauszufinden, welcher Figur aus einer fest vorgegebenen Menge die Eingabefigur am ähnlichsten sieht (Beispiel: Schrifterkennung). Um Formen möglichst gut zur Deckung zu bringen (matching) sind dabei verschiedene Transformationen denkbar, wie etwa Translationen, starre Bewegungen, Ähnlichkeitsabbildungen oder beliebige affine Abbildungen.

Eine der Ähnlichkeitsbestimmung verwandte Frage ist die Approximation oder Vereinfachung von Formen, wobei es darum geht, eine vorgegebene Form durch eine möglichst einfache Form gut zu approximieren, z.B. ein Polygon mit vielen Ecken durch eines

mit wenigen.

Weiterhin gehören zu diesem Problemkreis Probleme der Symmetriebestimmung, dh. von gegebenen Figuren oder Punktmustern die Symmetriegruppe zu berechnen.

Ziel unseres Projektes ist es, diese Problemstellungen mit Mitteln der algorithmischen Geometrie zu behandeln. Es geht also zum einen darum, Algorithmen zur Ähnlichkeitsmessung zu entwickeln, die es erlauben, effizient einen kleinsten Abstand

zwischen Figuren in der Ebene oder im Raum unter den erlaubten Matching-Transformationen zu berechnen. Zunächst stellt sich die Frage, welches Abstandsmaß zur Messung der Ähnlichkeit geeignet ist. Wir betrachten dabei insbesondere den Hausdorffabstand oder die Fläche der symmetrischen Differenz zweier Figuren. Wenn man den Abstand von Kurven in Raum und Ebene oder Flächen im Raum berechnen möchte bietet sich auch die

Fréchet-Metrik an, die für einige Beispiele ein adäquateres Maß ist als der Hausdorff-Abstand, dafür ist sie aber auch wesentlich schwerer zu berechnen.

Approximationsprobleme und Matchingprobleme lassen sich im allgemeinen auf das folgende Grundproblem zurückführen:

• Gegeben sei eine Figur F in der Ebene oder im Raum, eine Menge M von Figuren und ein Ähnlichkeitsmaß zwischen Figuren.
  Gesucht: Eine zu F möglichst ähnliche Figur aus M.

Je nachdem in welcher Form F und M vorliegen und um welches Ähnlichkeitsmaß, z.B. Hausdorffabstand oder symmetrische Differenz, es sich handelt, gestaltet sich die Suche nach effizienten Algorithmen sehr vielfältig. Da es im allgemeinen zu schwer, manchmal sogar NP-schwer ist, das Grundproblem optimal zu lösen sind auch Algorithmen von Interesse, die approximative Lösungen liefern, also die Figuren aus M finden, deren Ähnlichkeit zu F sich nur um einen festen Faktor von der bestmöglichen mit Figuren aus M erreichbaren Ähnlichkeit unterscheiden.

Eine Übersicht über die wichtigsten bisherigen Arbeiten zu dem genannten Themenkreis wird in [AG] gegeben. Dieser Artikel ist als ein Kapitel im geplanten Handbook on Computational Geometry vorgesehen.

 Matching von Formen mit Referenzpunktmethoden

Um approximative Lösungen zu finden, haben wir insbesondere die früher von uns entwickelte Idee der Referenzpunktmethoden weiterentwickelt. Ein Referenzpunkt ist ein fester, einer Figur zugeordneter Punkt mit der Eigenschaft, daß beim optimalen Matching zweier Figuren auch die beiden Referenzpunkte nahe zusammenliegen. Umgekehrt kann man eine approximative Lösung dadurch finden, daß man zunächst die beiden Referenzpunkte aufeinander abbildet und dann die optimale Lösung unter Fixierung dieser Referenzpunkte bestimmt. Diese ist meist viel einfacher zu berechnen als das uneingeschränkte Optimum.

In [AAR] haben wir gezeigt, daß für Matching beliebiger kompakter Formen in beliebigen Dimensionen unter Translationen, starren Bewegungen oder Ähnlichkeitsabbildungen bezüglich des Hausdorff-Abstands der aus der konvexen Geometrie bekannte Steiner-Punkt ein Referenzpunkt ist. Dies liefert direkt effiziente approximative Algorithmen für das Matchingproblem zum Beispiel von einfachen Polygonen in der Ebene oder von Polyedern im dreidimensionalen Raum.

In [AFRW] zeigen wir, daß der Schwerpunkt einer konvexen Menge in zwei Dimensionen einen Referenzpunkt für die symmetrische Differenz als Abstandsmaß unter den oben genannten Transformationsklassen und auch für beliebige affine Abbildungen darstellt und damit effektive Matching-Verfahren zur Verfügung stehen. In dieser Arbeit wird somit einerseits ein Beitrag zur konvexen Geomtrie geliefert und andererseits werden effiziente Algorithmen für die Anwendung enwickelt.

In seinem Dissertationsvorhaben beschäftigt sich Christian Knauer mit der praktischen Umsetzung von Matchingalgorithmen. Die Realisierung der Algorithmen wird einerseits durch die oftmals vorkommenden komplexen Datenstrukturen (z.B. Voronoi-Diagramme von Liniensegmenten) und Methoden (z.B. parametrische Suche) erschwert. Es wird daher untersucht, ob es sich lohnt, an Stelle von asymptotisch optimalen Verfahren, 'schlechtere', aber konzeptionell einfachere (und damit auch leichter zu implementierende) Methoden, oder an Stelle von exakten Verfahren, approximative (wie Referenzpunktmethoden) zu verwenden. Weiterhin wird untersucht, wie trotz der Darstellung geometrischer Daten durch Zahlentypen beschränkter Genauigkeit im Rechner die topologische Korrektheit gewährleistet werden kann.

In [AHS] wird eine mit dem Approximationsproblem verwandte Fragestellung betrachtet, nämlich für ein gegebenes konvexes Polygon das flächengrößte inbeschriebene Rechteck zu finden. Durch eine Erweiterung der Technik des tentative prune-and-search erhalten wir einen Algorithmus logarithmischer Laufzeit.

Symmetrieprobleme wurden in zwei Diplomarbeiten bearbeitet:

A.Papenberg beschäftigte sich mit Verfahren zur Bestimmung der Friesgruppe eines Frieses, von dem ein endlicher Ausschnitt vorliegt. Dabei gilt es, ein Grundmuster zu finden, aus dem durch durch periodische Wiederholung das Fries hervorgeht, und eventuelle Symmetrien dieses Grundmusters zu bestimmen. Insbesondere wird das Problem auch für ungenaue Eingabedaten untersucht. Das Verfahren wurde implementiert.

Ziel der Arbeit von S. Oesterreicher war das Erzeugen von Beispielen der planaren Symmetriegruppen mittels D0L-Systemen, einer speziellen Form von L-System, und umgekehrt, das Erkennen von Symmetrien anhand der die Objekte erzeugenden Grammatiken. Aus dieser Arbeit ist ein Graphikprogramm entstanden, das ein gegebenes Grundmuster zu einem Objekt in jeder beliebigen Symmetriegruppe vervielfältigt.

Die Programme für beide Arbeiten können auf Anfrage zur Verfügung gestellt werden.

Lutz Meißner untersucht in seinem Dissertationsvorhaben Datenstrukturen zum Auffinden von Formen. Zum Beispiel soll eine Menge von Polygonzügen so vorverarbeitet werden, daß

für einen weiteren Polygonzug sein nächster Nachbar effizient gefunden werden kann.

Carola Wenk beschäftigte sich in ihrer Diplomarbeit mit dem eindimensionalen Matching von Jahrringfolgen in der Dendrochronologie. Beim sogenannten Crossdating sind zwei Folgen von

Jahrringbreiten von Bäumen gegeben, und um die eine Folge anhand der anderen zu Datieren soll eine korrekte Überlagerung beider Folgen gefunden werden. Insbesondere wurde ein Verfahren entwickelt und implementiert, das implizit fehlende und doppelte Ringe (d.h. die Ausbildung keines bzw. zweier Ringe in einem Jahr) berücksichtigt.

Michael Godau untersuchte in seiner Dissertation ([G]) Verfahren zur Berechnung der Fréchet-Metrik. Dabei stellte sich heraus, daß das exakte Problem im Dreidimensionalen NP-schwer ist und auch hier approximative Lösungen gesucht werden müssen.

 References

[AAR] O. Aichholzer, H. Alt, G. Rote, Matching Shapes with a Reference Point,
Proceedings 10th Annual ACM Syposium on Computational Geometry, Stony Brook, USA, S. 85 - 92, 1994,
akzeptiert zur Veröffentlichung im Intern. Journal of Comp. Geometry and Appl., 7:349-363,1997

[AFRW] H. Alt, U. Fuchs, G. Rote, G. Weber, Matching Convex Shapes with Respect to Symmetric Difference.
Algorithmica, 21:89-103, 1998 und in Proc. 4th Annu. European Sympos. Algorithms, volume 1136 of Lecture Notes Comput. Sci., Seiten 320-333. Springer-Verlag, 1996 und als Technischer Bericht B96-03 des Fachbereichs Math. u. Inf. der FU Berlin.

[AG] H. Alt, L. Guibas, Resemblance of Geometric Objects,
erscheint in Handbook on Computational Geometry, Herausg. J. Sack, J. Urrutria.

[AHS] H. Alt, D. Hsu, J. Snoeyink, Computing the Largest Inscribed Isothetic Rectangle,
Proc. 7th Canad. Conf. Comput. Geom.,1995 S. 67-72.

[AWW]
In Proc. 13th Annu. ACM Sympos. Comput. Geom., Seiten 433-435, 1997

[G] Michael Godau, On the complexity of measuring the similarity between geometric objects in higher dimensions,
Dissertation, Fb. Mathematik und Informatik, FU Berlin, 1998

[O] S. Oesterreicher, Symmetriegruppen und D0L-Systeme,
Diplomarbeit, Fb. Mathematik und Informatik, FU Berlin, 1996.

[P] A. Papenberg, Algorithmen zur Bestimmung der Friesgruppe einer Punktmenge,
Diplomarbeit, Fb. Mathematik und Informatik, FU Berlin, 1996.

[W] C. Wenk, Algorithmen für das Crossdating in der Dendrochronologie,
Diplomarbeit, Fb. Mathematik und Informatik, FU Berlin, 1997