Forschungsprofil Udo Frese

(Visuelles) Simultaneous Localization and Mapping (SLAM)

ist mein Hauptarbeitsgebiet und auch der Schwerpunkt meiner internationalen Bekanntheit (vgl. Publikationsliste). Es geht dabei ganz allgemein darum, aus Daten eines sich bewegenden Sensors sowohl die Bewegung des Sensors selbst als auch die Geometrie der Umgebung zu bestimmen. Bei einer Kamera als Sensor entspricht SLAM daher dem Structure-from-Motion-Problem der Bildverarbeitung bzw. dem Bündelausgleich in der Photogrammetrie. Historisch entstanden Bündelausgleich und Structure from Motion vor der SLAM-Formulierung in der Robotik, jedoch hat diese den Fokus auf Echtzeitfähigkeit und inkrementellem Rechnen gelenkt. Mein Schwerpunkt innerhalb von Structure from Motion bzw. SLAM ist die hocheffiziente und inkrementelle quadratische Ausgleichsrechnung mit Methoden aus der Numerik. Mein meistzitiertes Papier ("A multilevel relaxation algorithm for simultaneous localization and mapping") ist eine Anwendung von Mehrgitterverfahren aus dieses Problem. Der Treemap- Algorithmus ist ein inkrementeller Algorithmus basierend auf multi-frontal sparse-QR Methoden. Er verwaltet eine hierarchische Unterteilung der Umgebung in einem Baum und propagiert niedrigdimensionale Wahrscheinlichkeitsverteilungen von Kindern zu Eltern und zurück. Die Baumstruktur ermöglicht allerdings, in Echtzeit zu aktualisieren, weil im Idealfall nur von einem Blatt zur Wurzel neu gerechnet werden muss. Der Baum wird automatisch erstellt und so optimiert, dass diese Aktualisierung effizient ist. Außerdem erlaubt die Sichtweise als Wahrscheinlichkeitsverteilungen anstelle der Sichtweise als dünnbesetzte Matrix, die Nichtlinearitäten unmittelbar im Baum zu berücksichtigen.

Mit dem Sparse Least Squares on Manifolds (SLoM)-Framework versuchen wir, dem Anwender die Definition von Problemen der quadratischen Ausgleichsrechnung zu vereinfachen („Nur die Messgleichung hinschreiben.“). Dies ist besonders dann nötig, wenn die zu schätzenden Größen Mannigfaltigkeiten sind (z.B. 3D-Orientierung) und deren topologische Struktur berücksichtigt werden muss.

Wir haben dieser Vorgehensweise einen axiomatischen Rahmen als sogenannte [+]-Mannigfaltigkeit (“boxplus”) gegeben. Eine solche verfügt über Operatoren (Bild rechts) um eine als Vektor dargestellte Änderung auf ein Element der Mannigfaltigkeit anzuwenden und deren Umkehroperation. Dadurch können viele Schätzalgorithmen, u.a. quadratische Ausgleichsrechnung und Kalman Filter, auf [+]-Mannigfaltigkeiten arbeiten, indem man im wesentlichen + durch [+] und − durch [-] ersetzt. Die topologische Struktur der Mannigfaltigkeit wird im [+]-Operator verkapselt.

Mittelfristiges Ziel ist, SLoM und die oben erwähnten effizienten Algorithmen zu kombinieren. Eine Zielanwendung könnte die visuelle Lokalisation eines kleinen autonomen Fluggerätes mit beschränkter Rechenkapazität in unbekannter Umgebung sein. Visuelles SLAM in Echtzeit ist aber eine Aufgabe in der Bildverarbeitung mit vielen Anwendungen. Bei dieser Problemstellung liefert die Kamera die große Masse an Daten, die mit einer speziell darauf abgestimmten Implementierung verarbeitet werden soll. SLoM als allgemeines Rahmenwerk ermöglicht aber, zusätzliche Sensoren (z.B. Inertialsensor) flexibel zu integrieren. Als Ansatz soll problemspezifisch vorkonditioniertes nichtlineares CG verwendet werden, um das Aufstellen einer Jakobi- oder Normalenmatrix zu vermeiden, welches nach Modellrechnungen bei der grossen Menge an Daten ein Flaschenhals ist.

Das laufende Anwendungsprojekt FreePerspective verfolgt eine wichtige SLAM-Anwendung im Rettungswesen: Mit photogrammetrischen Methoden (und einer 3D-Kamera) soll der Trümmerhaufen eines vom Erdbeben zerstörten Gebäudes von innen vermessen werden, um das Rettungspersonal bei der Suche nach Verschütteten zu unterstützen (Bild rechts). Ein derartiges 3D-Modell kann dann einem Foto von außen überlagert werden, um z.B. den Zugang zu einem Verschütteten zu planen.

Sichere Sensoralgorithmen

Hierbei geht es um Algorithmen, die Daten von Sensoren zu einem sicherheitsgerichteten Zwecke auswerten, so dass sie vor Gebrauch zertifiziert werden müssen, z.B. vom TÜV nach EN 61508. Ein Beispiel ist die Kollisionsvermeidung für Fahrzeuge in der Industrie (Projekt Sicherkeitskomponente für Autonome Mobile Systeme (SAMS), BMBF-Initiative Servicerobotik) und für Roboterarme humanoider Roboter (Projekt SAMS-3D, Bild rechts). In dem Projekt spielt mathematische Modellierung eine herausragende Rolle. Wir haben das Bremsverhalten des Fahrzeuges sowie den geometrischen Sachverhalt, was Kollision bedeutet, in Logik höherer Stufe mit dem Computer Aided Theoremeprover Isabelle definiert. Dadurch konnten wir die Sicherheitsfunktionalität der Kollisionsvermeidung direkt spezifizieren (“Die berechnete Teilmenge der Ebene enthält alle Punkte, die das Fahrzeug bei einem möglichen Bremsmanöver berühren könnte.”). Zusammen mit einer Spezifikation der Programmiersprache C ebenfalls in Isabelle konnten wir die Korrektheit der Implementierung beweisen. Dies, nicht Tests, war die Grundlage des erteilten TÜV Zertifikats. Diese erwähnten Arbeiten sind sehr industrienah. SAMS und iGEL sind Projekte mit Industriebeteiligung. In SAMS-3D bin ich Ko-Erfinder eines zum Patent angemeldeten Verfahrens. Das Projekt European Train Control System (ETCS) war ein Gutachten im Industrieauftrag. Sicherheitsgerichtete Anwendungen in der Bildverarbeitung sind eher selten, aber durchaus denkbar. In der Sicherheitstechnik dominieren andere Sensoren, wie Laserentfernungsmesser (z.B. bei SAMS). Mein Ansatz ist, den Sensor oder die Kombination von Sensoren nicht dogmatisch sondern nach der Aufgabenstellung zu wählen.

Kontextbasierte Bildverarbeitung

Der photogrammetrische Ansatz in der Bildverarbeitung erlaubt, aus im Bild zweidimensional erkannten Merkmalen dreidimensionale Information zu erschließen, z.B. die Position eines markanten Punktes in einem Gebäude, die Flugbahn eines Balles oder die Position und Orientierung der Kamera selbst. Im Projekt B-Catch beschäftigen wir uns mit der Ballflugbahnvorhersage. Ziel ist, dass ein Zuschauer dem humanoiden Roboter unserer Projektpartner (Deutsches Zentrum für Luft- und Raumfahrt, Bild rechts oben) zwei Bälle zuwirft und dieser sie mit beiden Händen fängt. Wie bei SLAM kommt es auf die probabilistische Modellierung von Unsicherheit und einen effizienten Inferenzalgorithmus in diesem Modell an. Anders als bei SLAM kommt zu der kontinuierlichen Messunsicherheit noch die diskrete Unsicherheit, ob der beobachtete Kreis im Bild wirklich von einem Ball stammt (Bild rechts unten). Beide Unsicherheiten zusammen führen zu einer mixture- of-Gaussian Verteilung anstelle einer, wenn auch sehr hochdimensionalen, einzelnen Gaußglocke wie für SLAM. Bemerkenswert ist auch erneut die Sensorfusion mit einem Inertial- sensor, da die Kameras am Kopf des Roboters wackeln, sobald sich dieser bewegt und nur durch den Inertialsensor Eigenbewegung von Ballbewegung unterschieden werden kann. Ein derartig komplexes System erfordert außerdem umfangreiche Kalibrierung von Kameras, Inertialsensor und Roboter zueinander, dies haben wir mit Hilfe des SLoM Frameworks erledigt. Die Demonstration des ballfangenden Roboters ist spektakulär und kommt auch sehr beim fachfremden Publikum an. Wir arbeiten gerade an einer Version mit einem minimalistischen Zweiachsroboter, die die Technologie als interaktives Eventmodul in die Anwendung bringen soll.

Bei dem bisher realisierten Bildverarbeitungssystem zur Ballverfolgung fließt die Information von einer bildnahen 2D-Ebene zu einer abstrakteren 3D- Szenenebene. Aber durch probabilistische Modellierung kann der Informationsfluss auch umgekehrt werden, um durch Kontext aus der Szene die Robustheit der bildnahen Erkennungsalgorithmen zu erhöhen. Beispielsweise erzeugt die dreidimensionale Flugbahn eines Balles zusammen mit der perspektivischen Abbildung der Kamera eine „Erwartungshaltung“, wo etwas im Bild erscheinen müsste. Dadurch würde man dort etwas als Ball akzeptieren, weil es zum Kontext der restlichen Information passt, selbst wenn es so undeutlich ist, dass man es woanders im Bild nicht akzeptieren würde. Dieser Mechanismus ist in der Psychologie als Priming bekannt. In ihm steckt nach mei- ner Einschätzung ein großes Potential, um die Robustheit von Bildverarbeitung zu verbessern und die Lücke in der Leistungsfähigkeit zur menschlichen visuellen Wahrnehmung zu verkleinern. Zur Zeit arbeiten wir gerade daran, dieses Konzept mathematisch zu modellieren und algorithmisch effizient umzusetzen. Die Grundidee ist, mit Wahrscheinlichkeitsverteilungen zu arbeiten, die direkt für jede potentielle Ballposition davon abhängen, wie “kreisig” es an dieser Stelle im Bild aussieht, anstatt zuerst Kreise zu suchen und um die gefunden Positionen Gaussglocken zu legen.

Orthogonal zu den Themen zeigt die linke Spalte der Tabelle übergreifende Methoden, die sich quer durch die verschiedenen Themen in unseren Projekten ziehen:

Mathematische Strukturanalyse

In meinem wissenschaftlichen Werdegang war immer eine Schlüsselfähigkeit, mathematisch-formale Repräsentation und Anschauung miteinander zu verknüfen und leicht zwischen beiden Seiten wechseln zu können. Deshalb habe ich als Informatiker auch Mathematik bis zum Vordiplom studiert und gelte in meinem eher praktisch orientierten Anwendungsgebiet der Robotik als “gut verständlicher Theoretiker”. Diese Fähigkeit zur intuitiven Strukturanalyse ist enorm hilfreich, weil sie erlaubt, Ideen für Algorithmen zu entdecken, schwer aufzuspürende Fehler in Implementierungen zu finden und komplexe Zusammenhänge so darzustellen, dass der Zuhörer die Botschaft versteht. Beispielsweise war mein erstes Konferenzpapier ("Simultaneous localization and mapping - a discussion ") eine theoretische Auseinandersetzung mit dem SLAM-Problem im Wechselspiel zwischen mathematisch-formale Repräsentation und Anschauung und wird eben wegen dieses Wechselspiels häufig zitiert. Das Papier weist auch als erstes auf die entscheidende Dünnbesetztheit der auftretenden Matrizen hin. Diese war zu dem Zeitpunkt zwar schon in der Bildverarbeitung, nicht aber in dem damals noch getrennten SLAM-Feld bekannt.

Probabilistische Sensorfusion Sensorfusion ist die Verknüpfung von unsicherer Information aus verschiedenen Quellen, um eine möglichst genaue Gesamtinformation daraus zu erhalten. Die Faszination an sensoriellen Daten liegt darin, dass sie an der Grenze zwischen der „realen Welt“ und der „Welt im Rechner“ liegen und die reale Welt eine Vielzahl an Phänomenen hat, die Sensordaten unsicher machen. Dieses gilt für Bilder in besonderem Maße. Effiziente Algorithmen Die Motivation für effiziente Algorithmen speist sich aus zwei Gedanken. Zum einen beschäftige ich mich mit Bildverarbeitung bei bewegten Vorgängen und da muss die Rechnung mit der Bewegung mithalten können (Echtzeit). Zum anderen ist Effizienz ein spannendes Forschungsziel an sich mit einem sehr klaren, weil gut messbarem Erfolgskriterium, der Rechenzeit. Daher übt Effizienz auf mich als Informatiker eine ähnliche Faszination aus wie Schubkraft auf einen Raketenentwickler. Im Inneren der Tabelle finden sich Projekte und ihr Bezug zu den Themen und Methoden. Am- biguousSpace und FreePerspective sind von mir geleitete Projekte im SFB/TR 8, B-Catch ist ein DFG-Einzelprojekt, SAMS ist ein von mir mitgeleitetes Projekt in der BMBF-Initiative Servicerobo- tik und iGEL ein von mir mitgeleitetes Projekt im BMBF-Programm KMU Innovativ.