ELITE NETZWERK BAYERN

Deutsch  Language Icon  |  Gebärdensprache  |  Leichte Sprache  |  Kontakt


Forschungsarbeit

Smooth Minimum Arc Paths

von Dr. rer. nat. Georg Maier (20.12.2011)

Bei starker Vergrößerung eines digitalen Bildes wird eines sofort sichtbar: Der Umriss des fotografierten Objektes ist keine durchgehende Linie, sondern er besteht aus vielen einzelnen Pixeln. Soll von einem fotografierten Bauteil später ein Musterplan erstellt werden, müssen diese vielen Pixel in eine möglichst realitätsgetreue Kurve umgewandelt werden. Nur wie?

Häufig werden Bauteile hergestellt, ohne im Vorfeld eine genaue Zeichnung des Werkstücks angefertigt zu haben. Wie kann aber dann ohne Bauplan, ohne eine genaue Zeichnung, trotzdem in Serienproduktion gegangen werden? Man könnte das vorhandene Bauteil etwa mit einer Kamera erfassen. Aber Kameras oder auch Laserscanner und andere optische Sensoren können Objekte nur an einzelnen Punkten abtasten. Im Klartext heißt das, es werden nur für einzelne Stellen des Objekts Sensorwerte ermittelt. Auch, wenn die Auflösung der Geräte noch so hoch sein sollte, das Ergebnis wäre in jedem Fall eine Kontur, die aus einzelnen, unzusammenhängenden Pixeln und nicht aus Linien oder Kurven besteht. Die Umrandung des Bauteils kann also lediglich als Kette einzelner Pixelkoordinaten wiedergegeben werden. Verbindungsstrecken zwischen benachbarten Punkten liefern keine zufrieden stellende Lösung. Ein kreisrundes Bohrloch beispielsweise würde als Vieleck mit mehreren tausend kleinen Ecken dargestellt. Eine solche Darstellungsart ist nicht geeignet, um daraus einen Bauplan zu erstellen. Denn zum einen entspricht das entstandene Bild nicht der Realität. Zum anderen ist ein solches Vieleck zu komplex. Die Datenmenge ist viel zu groß, um diese effizient in einer Software weiterverarbeiten zu können. Da Strecken wegen ihrer Geradlinigkeit alleine keine sinnvolle Darstellung liefern, müssen Kurven als Beschreibung herangezogen werden. Die beschreibende Kurve soll die einzelnen Konturpunkte des Bauteils möglichst genau annähern, zu komplex darf sie aber wegen der daraus resultierenden Datenmenge auch nicht sein. Das Abfotografieren ist, wie jede sensorische Erfassung, ein physikalischer Prozess. Dieser liefert Werte mit begrenzter Genauigkeit, da die Sensoren lediglich endlich viele, aber eben nicht alle Punkte einer Kurve liefern können. Zudem werden diese Kurven-Koordinaten beim Digitalisieren gerundet und weichen so leicht von der Realität ab. Folglich wäre es nicht sinnvoll zu fordern, dass die beschreibende Kurve direkt durch jeden der Konturpunkte verlaufen soll. Allerdings sollte sie auch keinen zu großen Abstand zu ihnen haben, damit das Bauteil immer noch originalgetreu abgebildet wird.

 

 

Eine Kombination aus Strecken und Kreisbögen, Kreisbogensplines genannt, erweist sich am zweckmäßigsten, um die Konturen des Bauteils zu beschreiben. Denn die Abstandsberechnung von den erfassten Punkten zur beschreibenden Kurve kann damit mit sehr geringem Rechenaufwand erfolgen. Zudem benötigt eine Darstellung einer Kontur als Kreisbogenspline sehr geringen Speicherplatz. Daher eignen sich Kreisbogensplines für die Vermessung von Bauteilen besonders gut. Außerdem können die Bauteile mit einer Darstellung als Kreisbögen anschließend auch auf ihre Qualität sowie die korrekte Beschaffenheit überprüft werden. Berührungslose Messverfahren werden mit Kreisbogensplines deutlich effizienter bewältigt. Das ist ein entscheidender Vorteil für viele Anwendungen, da häufig gerade bei diesen Messungen eine Vielzahl von Abständen innerhalb weniger Millisekunden bestimmt werden muss.

Doch wie sollen nun die Kreisbögen verlaufen, damit sie den Umriss des Bauteils realitätsgetreu abbilden? Einerseits sind so wenige Teilstrecken und Kreisbögen, Segmente genannt, wie möglich erstrebenswert, damit die Datenmenge gering bleibt. Andererseits ist eine passgenaue Darstellung wünschenswert. Bei einer strengen Orientierung an den einzelnen Konturpunkten des Objekts werden sehr viele Segmente benötigt. Werden hingegen wenige Teilstücke verwendet, wird die Kontur ungenau. Diese Situation modellierte ich wie folgt: Ich minimierte die Anzahl der Segmente, legte aber zuvor einen Maximalabstand der Kurve zu den erfassten Punkten fest. Einem Tunnel gleich legte ich einen gedachten Kanal um die Konturpunktkette. Jede Kurve, die nun innerhalb dieses Tunnels verläuft, kann nur mehr höchstens um den Maximalabstand von den Konturpunkten abweichen. Typischerweise besteht ein solcher Toleranzkanal aus einer Folge von Strecken, weshalb jener recht eckig aussieht. Um den gesamten Umriss des Objektes genau wiedergeben zu können, gibt es - wie bei einem Tunnel - einen Ein- und einen Ausgang, also eine Start- und eine Zielstrecke, die die Kurve durchlaufen muss. Meine Herausforderung bestand darin, das „Runde ins Eckige“ zu bringen; sprich, die runden Kreisbögen mit möglichst wenigen Segmenten im eckigen Kanal zu positionieren.

 

Jeder Kreisbogenspline ohne Knickstellen, der innerhalb des Toleranzkanals die Start- und Zielstrecke miteinander verbindet und die kleinstmögliche Anzahl an Segmenten besitzt, ist eine Lösung des skizzierten Problems, Smooth Minimum Arc Path (S M A P) genannt. Dass es zu jedem Toleranzkanal immer einen SMAP gibt, ist nicht schwer zu beweisen. Doch für eine praktische Umsetzung wird eine exakt definierte Anleitung benötigt, ein Algorithmus, wie man die Kreisbögen um die von der Kamera erfasste Konturpunktkette legen soll. Solch ein Algorithmus muss immer das Richtige und zudem möglichst schnell berechnen. Mathematische Aussagen über eine Mindestzahl abwechselnder, sprich alternierender, linker und rechter Randberührungen der Kurven an den Kanal bilden dabei die Grundlage für eine effiziente softwareseitige Umsetzung. Auf die Idee, die Konturen eines Bauteils zur Weiterverarbeitung am Rechner mittels Kreisbögen darzustellen, kamen bereits andere Forscher vor mir. Allerdings können alle bisher bekannten Verfahren entweder die Minimalität der benötigten Kreisbögen oder die gewünschte Genauigkeit nicht garantieren.


Georg Maier
Georg Maier
* 1984

Stationen
  • 10/2003–06/2007
  • Universität Regensburg: Diplom-Mathematikstudium mit Nebenfach Naturwissenschaftliche Informatik
  • 09/2007–08/2010
  • Universität Passau: Promotion am Lehrstuhl für Numerische Mathematik und Analysis
  • Seit 01/2008
  • Universität Passau: Wissenschaftlicher Mitarbeiter am Institut für technische Anwendungen der Informatik, FORWISS.

Stipendien & Auszeichnungen
  • 12/2008
  • „Nachwuchsforscher-Preis” (Anerkennungspreis) für herausragende Dissertationen und Habilitationen des „Universität Bayern e.V.”
  • 05/2008–08/2010
  • Forschungsstipendium des „Elitenetzwerks Bayern” basierend auf dem Bayerischen Elitefördergesetz (BayEFG)
  • 11/2007
  • „Förderpreis 2007” der Universität Regensburg im Rahmen des „Dies academicus”
  • Seit 2003
  • Onlinestipendium „e-fellows.net”
  • Bis 2002
  • Diverse Preise im Bundeswettbewerb Mathematik und der Mathematikolympiade