Geometrische Algorithmen

Algorithmische Aspekte geometrischer Probleme treten mit den wachsenden technischen Möglichkeiten der Datenverarbeitung immer stärker in den Blickpunkt des Interesses. Dies hat seinen Grund in den gewandelten Anforderungen, die in neuen und zunehmend anspruchsvolleren Rechneranwendungen an Bildverarbeitung, Bildgebung und Computer-Graphik gestellt werden. Die schnelle Entwicklung der zugrundeliegenden Paradigmen und Strukturen haben ein faszinierendes Gebiet entstehen lassen. In unserer Arbeitsgruppe wird z.B. das Problem der aktiven Teleskopsteuerung bearbeitet. In konventionellen passiven rechnergesteuerten Teleskopen führen Servomotoren nach einer anfänglichen hochpräzisen parallaktischen oder azimutalen Ausrichtung das Teleskop "blind'' nach, es findet keine Rückkopplung anhand des aktuellen Gesichtsfelds statt. Deshalb sind eine sehr stabile Teleskopmontierung und eine aufwendige Nachführungsmechanik unerläßlich, die die Kosten soweit in die Höhe treiben, daß weltweit zur Zeit nur zwei Firmen solche Teleskope in größerer Serie fertigen. Eine Alternative sind aktive Nachführsysteme, die anhand eines kontinuierlich ausgewerteten CCD-Bildes das Teleskop steuern. Ein solches System besteht aus nur wenigen vergleichsweise preiswerten Komponenten, die nicht auf eine hochstabile Montierung oder Nachführung angewiesen sind. Zur Realisierung eines solchen Systems sind Algorithmen zur Lokalisierung der CCD-Bilder innerhalb einer gespeicherten Sternkarte erforderlich. Dies läuft im Kern auf den Einsatz von sog. Voronoidiagrammen, einer vielfach verwendeten Datenstruktur, hinaus. Die besondere Schwierigkeit liegt hier darin. daß die Eingaben aufgrund von Luftbewegungen und unzureichender Auflösung der CCD-Bilder fehlerbehaftet sind. Ein zweistufiges Punktlokalisierungsverfahren, bei dem an den Rändern der Voronoizellen ein Korrekturalgorithmus aufgerufen wird, erlaubt es, auf einem Standard-PC soviele Bilder zu verarbeiten (etwa 10 pro Sekunde), daß eine gleichmäßige Nachführung möglich ist. Voronoidiagramme sind auch für sich genommen ein aktueller Forschungsgegenstand. In der Arbeitsgruppe wurde untersucht, wie schnell ein Parallelrechner vom Typ CGM ("Coarse Grained Multicomputer'') ein zweidimensionales Voronoidiagramm berechnen kann. Hierfür wurde ein beweisbar optimaler randomisierter Algorithmus gefunden. In Zusammenarbeit mit der Firma CLK, Münster, wurde eine weitere Anwendung von Voronoidiagrammen entwickelt, bei der der Zustandsraum eines Neuronalen Netzes durch Voronoizellen unterteilt wird. Damit kann die Trainingsphase des Netzes signifikant reduziert werden. Ein Verfahren zur automatischen Erkennung von Blindgängern in photographischen Luftbildaufnahmen aus dem Zweiten Weltkrieg, das auf solchen Netzen basiert, wurde gemeinsam mit der Fa. CLK auf der Hannover-Messe 1998 vorgestellt. Es ist in der Lage, die bisherige Auswertung durch Expertenbeurteilung mit gleicher Qualität zu ersetzen.

Beteiligter Wissenschaftler:

Prof. Dr. A. Clausing