Strukturen für geometrische Muster

• Applicant: Professor Dr. Christian Knauer, since 4/2010
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 15027391

Das zentrale Problem der geometrischen Mustererkennung lässt sich folgendermaßen formalisieren: gegeben sind zwei geometrische Objekte (wie z.B. Polygonzüge) A und B - die Muster - und es soll festgestellt werden, wie ähnlich diese zueinander sind. Üblicherweise darf eines der Objekte dabei durch eine geometrische Abbildung (z.B. Translation, Rotation) transformiert werden, damit es dem anderen Objekt möglichst ähnlich wird. Die Ähnlichkeit von zwei Mustern wird dabei durch eine geeignete Abstandsfunktion bewertet (wie z.B. den Hausdorffabstand). In vielen Anwendungen steht man speziell vor dem Problem, aus einer Menge von geometrischen Mustern (der Datenbank) ein Muster zu finden, das möglichst ähnlich zu einem Anfragemuster ist; wieder darf eventuell das Anfragemuster dabei transformiert werden. Wenn es sich um eine große Datenbank handelt, ist es nicht praktikabel, das Anfragemuster mit allen Mustern der Datenbank einzeln zu vergleichen. Stattdessen möchte man die Muster aus der Datenbank vorverarbeiten, und eine Suchstruktur aufbauen, um dann schnell eine Anfrage beantworten zu können. Die Bedeutung dieser Fragestellung spiegelt sich in der Vielzahl kommerzieller und akademischer sogenannter Image-Retrieval-Systeme (IRS) wider, die in den letzten zehn Jahren entwickelt wurden, wie z.B. das QBIC System von IBM [35], die Princeton 3D Model Search Engine [55], PicHunter [29], Blobworld [22], oder das ASSERT System [63]. In [64] findet sich eine systematische Auflistung von 58 solchen IR-Systemen. Die Autoren von [64] kommen bei Ihrer Untersuchung zu dem Schluß, dass keines dieser Systeme voll überzeugen kann, geschweige denn in der Lage ist, den menschlichen Erkennungsprozess nachzuahmen. Eine Ursache für die Unzulänglichkeiten der untersuchten IRS liegt darin, dass keines die geometrische Form von Objekten direkt zur Ähnlichkeitsbewertung verwendet. Stattdessen finden merkmalsbasierte Verfahren Anwendung, die einfachere Eigenschaften wie Farbe, Textur, Fläche, etc. heranziehen. Der direkte Vergleich von Formen stellt daher nach wie vor ein schwieriges ungelöstes Problem dar zu dessen Lösung es weiterer Grundlagenforschung bedarf. In dem Projekt soll untersucht werden, wie sich Methoden der algorithmischen Geometrie und der geometrischen Mustererkennung beim Entwurf von Suchstrukturen für geometrische Muster anwenden lassen. Der Schwerpunkt liegt dabei auf der Entwicklung effizienter Algorithmen für die jeweiligen Probleme. Es ist auch beabsichtigt, einige der entwickelten Verfahren zu implementieren und auf realen Daten zu testen. Insbesondere sollen die neu entwickelten Methoden untereinander und mit bereits existierenden Systemen und Lösungen verglichen werden.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Professor Dr. Helmut Alt, until 3/2010