DE10139846C1

DE10139846C1 - Geometrisches Matching zur Lösung von Lokalisationsproblemen

Info

Publication number: DE10139846C1
Application number: DE10139846A
Authority: DE
Inventors: Claus Aufmuth; Henrik Baur
Original assignee: DaimlerChrysler AG
Current assignee: Mercedes Benz Group AG
Priority date: 2001-08-14
Filing date: 2001-08-14
Publication date: 2003-02-06
Anticipated expiration: 2021-08-15

Abstract

In vielen Bereichen der Bildverarbeitung ist es gewinnbringend, wenn aus den Bilddaten der Kamera auf deren aktuelle Position und Lage geschlossen wird. Hierzu wird in vorteilhafter Weise eine objektbildungsfreie Zielfunktion definiert. Durch die Optimierung dieser Zielfunktion wird derjenige Parametersatz der Transformation gefunden, welcher Modellstruktur und Bilddaten optimal aufeinander abbildet. Dieser Variationsansatz erlaubt es, die Bildung diskreter Bildobjekte und damit auch das Zuordnungsproblem gänzlich zu vermeiden, falls es gelingt, eine objektbildungsfreie Zielfunktion zu formulieren. Hierbei besteht generell das Problem, dass im Rahmen einer Parameteroptimierung ein Nebenoptimum der Zielfunktion ausgewählt wird, wobei es in der Regel keine Möglichkeit gibt, zu entscheiden, ob es sich bei einer Lösung um ein lokales oder globales Optimum handelt. Durch den Entwurf einer gutartigen Zielfunktion und die Investition von Modellwissen kann diese Problematik jedoch weitgehend entschärft werden. Solche Optimierungsalgorithmen arbeiten in der Regel iterativ, wodurch sie hinsichtlich Rechenaufwand und -genauigkeit skalierbar werden.

Description

Die Erfindung betrifft ein Verfahren nach dem Oberbegriff des Patentanspruchs 1.

In vielen Bereichen der Bildverarbeitung ist es gewinnbringend, wenn aus den Bilddaten der Kamera auf deren aktuelle Position und Lage geschlossen werden kann.

Aus US 5850469 A ist ein Verfahren zur Inspektion von Maschinen in bezug auf Verschleiß und Defekte bekannt. Dabei wird aus den 3D-Strukturdaten eines Objekts eine Sammlung synthetischer Kamerabilder erzeugt und diese mit den Bilddaten eher Kamera verglichen, welche dieses Objekt betrachtet und deren Position und Lage bestimmt werden soll. Da die Lage und Position der Kamera bei der Inspektion eines Maschine nur in einem ziemlich eingeschränkten Umfang veränderlich ist, ist es im allgemeinen auf einfache Weise möglich bereits im Vorfeld einer exakten Lage und Positionsbestimmung deren Lage zu schätzen und ein möglichst optimales synthetisches Kamerabild für einen Vergleich mit den Kameradaten auszuwählen. Aus diesem Grund liefert dieses Verfahren zuverlässige Ergebnisse, trotz der Tatsache das die Ermittlung der Positions- und Lagedaten auf den Vergleich berechneter Jakobi-Matrizen beruht, was eine gu te Übereinstimmung des synthetischen Bildes mit den Bilddaten der Kamera voraussetzt.

Bei der Lageschätzung im Zusammenhang mit autonomen Flugkör pern ist es das Ziel diese anhand der ermittelten Position und Lage so zu steuern, dass sie anhand eines programmierbaren Missionsplanes ihr Ziel erreichen. Derzeit wird eine solche Zielführung mit Hilfe konventioneller Navigationssysteme wie Trägheitsnavigations-Systemen und GPS durchgeführt.

In Bezug auf eine kamerabasierte Lageschätzung zeigen die Schriften GB 2237951 A sowie die Schriften GB 2116 000 A für Fluggeräte Navigationssysteme, welche die Lage auf Grund von auf dem zu überwachenden Boden angebrachten künstlichen Re flexionskörpern schätzen. Desweiteren ist aus der Schrift DE 41 38 270 A1 ein Verfahren zur Navigation eines selbstfahrenden Landfahrzeugs bekannt, bei welchem zur Navigation Marken wäh rend der Fahrt erfasst, digitalisiert und mit abgespeicherten Daten verglichen werden. Auf Grund der Korrelation der Bildda ten mit den bekannten Koordinaten der Marken kann so eine Aus richtung des Fahrzeugs im Raum ermittelt werden.

Es sind auch Schriften bekannt, bei welchen Verfahren be schrieben werden, bei denen die Lageschätzung eines Fahrzeugs ohne Zuhilfenahme künstlicher Reflexionskörper geschätzt wer den kann. Hierbei werden die Bilddaten des Fahrzeuges mit zuvor in einem Speicher abgelegten Koordinaten der Umgebungen korreliert; beispielhaft sei hier die Schrift DE 195 05 487 A1 genannt, bei der charakteristische optische Merkale aus der unmittelbaren Umgebung des Fahrzeugs in einem Speicher abge legt sind und eine Recheneinrichtung anhand vorgegebener Daten über charakteristische optische Merkmalen mit den von dem op tischen Sensor erfassten Daten korreliert, um eine genaue Po sitionsbestimmung vornehmen zu können. Aus der Schrift DE 35 23 303 C2 ist ein System bekannt, welches in einem ersten Schritt Messungen während Aufklärungsflügen ermittelt und die aus diesem Daten gewonnenen Ortskoordinaten in einem Speicher abgelegt Mengen zweitens Schritt kann nun das Fahrzeug in ei ner autonomen Betriebsweise Daten aufnehmen, um so eine Lage schätzung vornehmen zu können.

Aufgabe der Erfindung ist es, ein neues Verfahren nach dem Oberbegriff des Patentanspruchs 1 zu finden, welches insbeson dere bei der Navigation von autonomen Flugkörpern die Lang zeitstabilität der Positions- und Lageschätzung erhöht.

Die Aufgabe wird durch ein Verfahren mit den Merkmalen des Patentanspruchs 1 gelöst. Vorteilhafte Ausgestaltungen und Weiterbildungen der Erfindung sind durch die Unteransprüche gegeben.

In besonders vorteilhafter Weise beruht das erfindungsgemäße Verfahren zur Positions- und Lageschätzung durch einen Ab gleich von Bilddaten einer Kamera mit den Modellstrukturen, insbesondere zur Erhöhung der Langzeitstabilität und der Au tonomie von Flugkörpern, auf einen Variationsansatz. Dabei er folgt der Abgleich von Modellstrukturen und Bilddaten mittels einer Variation der Parameter einer Transformation, welche die Modellstrukturen mit den Bilddaten der Kamera aufeinander ab bildet. Hierzu wird in erfinderischer Weise eine objektbil dungsfreie Zielfunktion definiert.

Der besondere Vorteil der Verwendung einer objektbildungs freien Zielfunktion liegt in der Tatsache begründet, dass eine Objektbildung stets eine Art von Segmentierung voraussetzt, z. B. kanten- oder regionen-basiert. Eine solche Segmentierung ist meist sehr rechenintensiv und fehleranfällig. Scheitert die Objektbildung, so scheiter auch die Lösung des Grundpro blems, nämlich der Selbstlokalisation (Egolokalisation) der Kamera. Darüber hinaus ergibt sich durch die Verwendung einer objektbildungsfreien Zielfunktion der Vorteil, dass kein Kor respondenz- bzw. Zuordnungsproblem für Modell- und Bildobjekte gelöst werden muß, welches einen derart hohen rechnerischen Verarbeitungsaufwand darstellen kann (kombinatorische Explosion), daß eine technische Anwendung oft nicht praktikabel ist.

Durch die Optimierung der objektbildungsfreien Zielfunktion wird derjenige Parametersatz der Transformation gefunden, welcher Modellstruktur und Bilddaten optimal aufeinander abbildet. Der Variationsansatz erlaubt es die Bildung diskreter Bildobjekte und damit auch das Zuordnungsproblem gänzlich zu vermeiden, falls es gelingt, eine objektbildungsfreie Zielfunktion zu formulieren. Als problematisch gelten mögliche Nebenoptima. Gerade die zeiteffizienten Optimierungsverfahren, welche aus dem Stand der Technik bekannt sind, können eine optimale Lösung meist nicht garantieren. Es besteht in der Regel keine Möglichkeit zu entscheiden, ob es sich bei einer Lösung um ein lokales oder globales Optimum handelt. Durch den Entwurf einer gutartigen Zielfunktion und die Investition von Modellwissen kann diese Problematik jedoch weitgehend entschärft werden. Optimierungsalgorithmen arbeiten in der Regel iterativ, wodurch sie hinsichtlich Rechenaufwand und -genauigkeit skalierbar werden.

Aus dem erfindungsgemäß resultierenden, optimalen Parametersatz kann nun in vorteilhafter Weise direkt mittels des Variationsansatzes auf die Position der Kamera geschlossen werden, oder es kann alternativ auch gewinnbringend analog zu einem kombinatorischen Vergleichsansatz ein Zuordnungsproblem formuliert werden, das jedoch durch die Kenntnis der optimalen Abbildung von Modellstruktur und Kamerabild trivial ist. Die Repräsentation des jeweiligen Ergebnisses ist für diesen Fall bei beiden Ansätzen äquivalent.

Im nachfolgenden soll die Erfindung im Detail im Rahmen von Ausführungsbeispielen und mit Hilfe von Figuren beschrieben werden.

Fig. 1 zeigt die Geometrien und die Physik, im wesentlichen die Strahlenoptik, im Zusammenhang mit dem Lochkameramodell.

Fig. 2 zeigt unterschiedliche zu beachtende Koordinatensysteme

Fig. 3 zeigt das Ablaufdiagramm des erfindungsgemäßen Verfahrens (mit optionalen Pfaden)

Fig. 4 stellt die Verhältnisse der Integration innerhalb eines Akkumulatorbildes klar

Fig. 5 zeigt einen zweidimensionalen Suchraum und einen Startsimplex für die Optimierung mittels dem Downhill-Simplex-Verfahren.

Parameterraum

In vorteilhafter Weise bildet im Rahmen des Variationsansatzes innerhalb erfindungsgemäßen Verfahrens die Definition einer parametrisierbaren Transformation, die Modell und Bild aufeinander abbilden, den ersten Schritt. Es handelt sich hierbei um eine Designentscheidung, die heuristisch oder analytisch getroffen werden kann. Die einer Kamera zugrundeliegenden Geometrie und Physik, im wesentlichen die Strahlenoptik, wird jedoch im allgemeinen so gut verstanden, daß die Entscheidung für eine perspektivische Transformation leicht fällt.

In der Literatur sind verschiedene Kameramodelle bekannt, die im wesentlichen auf einem Lochkameramodell beruhen und sich darin unterscheiden mit welcher Näherung die Eigenschaften realer Optiken erfaßt werden. In besonders vorteilhafter Weise werden Objektive mit langen Brennweiten eingesetzt, die in der Regel idealen Optiken sehr nahekommen. Daher ist das Lochkameramodell, entsprechend Fig. 1 mit seiner reinen perspektivischen Transformation eine adäquate Beschreibung und durch seine Einfachheit und Linearität mit Hilfe linearer Algebra explizit und effizient berechenbar.

Die perspektivische Transformation, die einen Punkt im Raum auf eine Bildebene projiziert läßt sich in homogenen Koordinaten entsprechend der Gleichung 1 als Produkt schreiben:

Dabei erfaßt die linke Matrix die inneren und die rechte die äußeren Kameraparameter. Die rechte Matrix ist eine rigide Transformation, d. h. sie bewirkt eine Translation und Rotation, jedoch keine Skalierung oder Scherung. Dies ist mathematisch äquivalent mit der Eigenschaft, daß die Submatrix R orthonormal ist. Dies ist insofern bemerkenswert, als daß ihre Parameter r₁₁ bis r₃₃ dann keineswegs unabhängig sind, sondern auf genau drei unabhängige Parameter zurückgeführt werden können, welche die Rotation beschreiben. Mit den drei Parametern t₁ bis t₃, welche die Translation beschreiben, enthält die rechte Matrix also genau sechs äußere Kameraparameter für die jeweils drei Positions- und Orientierungsfreiheitsgrade der Kamera im Raum. Da ja gerade die Position und Orientierung des Flugkörpers variabel sind und bestimmt werden sollen, sind die äußeren Kameraparameter für den Variationsansatz relevant.

Die linke Matrix bewirkt die eigentliche perspektivische Projektion in die Bildebene durch den Quotienten w. Sie enthält genau sechs innere Kameraparameter, welche die Rasterung der Bildebene beschreiben. Der Parameter b wird mit Bildweite bezeichnet und hängt mit der Gegenstandsweite g und der Brennweite f wie folgt zusammen:

Offenbar sind Bildweite und Brennweite für weit entfernte Gegenstände näherungsweise äquivalent. Die Parameter s_x und s_y beschreiben eine Skalierung und s_xy, eine Scherung in der Bildebene. Die Parameter c_x und c_y beschreiben eine Translation in der Bildebene. Sie bestimmen den Schnittpunkt der optischen Achse mit der Bildebene, den sogenannten Kamerahauptpunkt.

In elektronischen Kameras befindet sich regelmäßig in der Bildebene ein lichtempfindlicher CCD- oder CMOS-Chip mit einem orthogonalen Raster zumeist nahezu quadratischer Pixel. Die Indizierung dieses Rasters orientiert sich an einem seit langem in der Computergrafik und Bildverarbeitung etablierten Koordinatensystem, das wohl durch die zeilenweise Bildübertragung der frühen Fernsehtechnik motiviert ist. Es handelt sich hierbei um ein kartesisches Linkssystem, bei dem sich der Nullpunkt in der linken oberen Bildecke befindet. Jedes Pixel wird durch zwei ganzzahlige positive Indizes adressiert. In diesem Kontext können die inneren Kameraparameter wie folgt erklärt werden:
b: Bildweite, praktisch in der Regel durch Brennweite ersetzbar;
s_x: Kehrwert des horizontalen Pixelabstands (Pixeldichte), positives Vorzeichen;
s_y: Kehrwert des vertikalen Pixelabstands (Pixeldichte), negatives Vorzeichen;
s_xy: Pixelscherung, praktisch in der Regel vernachlässigbar, näherungsweise null;
c_x: Index des Kamerahauptpunktes horizontal, praktisch nahe Bildzentrum;
c_y: Index des Kamerahauptpunktes vertikal, praktisch nahe Bildzentrum.

Bemerkenswert ist, daß im Kontext der konkreten Anwendung alle inneren Kameraparameter konstant sind und nur einmal ermittelt und vorgegeben werden müssen. Die inneren Kameraparameter sind für den Variationsansatz nicht relevant.

Der nächste Schritt innerhalb des erfindungsgemäßen Verfahrens ist die Definition geeigneter Koordinatensysteme. Definitionsgemäß werden kartesische Koordinaten eingesetzt, weil sie am gebräuchlichsten und für diese Anwendung auch am kooperativsten sind. Entsprechend der Darstellung in Fig. 2 stehen insgesamt fünf verschiedene Koordinatensysteme zur Diskussion:
Weltkoordinatensystem: dreidimensionales, kartesisches Rechtssystem;
Modellkoordinatensystem: dreidimensionales, kartesisches Rechtssystem; Flugkörper- bzw.
Objektkoordinatensystem: dreidimensionales, kartesisches Rechtssystem;
Kamerakoordinatensystem: dreidimensionales, kartesisches Rechtssystem;
Bildkoordinatensystem: zweidimensionales, kartesisches Linkssystem;

Zwischen dem Weltkoordinatensystem und dem Modellkoordinatensystem besteht ein statischer Zusammenhang. Falls die Modellierung in Weltkoordinaten erfolgt, sind die beiden Systeme identisch. Zwischen den Objektkoordinaten, beziehungsweise den Flugkörperkoordinaten falls das Objekt als Träger der Kamera im Rahmen des erfindungsgemäßen Verfahrens einen Flugkörper darstellt, und den Kamerakoordinaten besteht ebenfalls ein statischer Zusammenhang, weil die Kamera fest am Flugkörper montiert ist. In analoger Weise besteht auch für den Fall eine definierte Zuordnung zwischen den Koordinaten der Kamera und einem Flugkörper bzw. Objekt, in welchem sich die Verhältnisse der Koordinatensysteme zueinander dynamisch verändern. Dies ist beispielsweise die Situation, wenn die zugrundeliegende Kinematik und ihre Parameter, beispielsweise bei der Verwendung eines programmierbaren, steuerbaren Schwenk- Neige-Kopfes, bekannt sind. Es existiert hierbei also eine konstante, rigide Transformation zur Umrechnung von Kamerakoordinaten und Flugkörperkoordinaten und umgekehrt, die von der Montage abhängt und einmal bestimmt werden muß. Das Kernproblem der Bestimmung der Flugkörperposition und -orientierung in Weltkoordinaten läßt sich offenbar umformulieren in ein Problem der Schätzung der Kameraposition und -orientierung in Modellkoordinaten aufgrund der zugehörigen Bildinformation.

Nun kann die zweiteilige perspektivische Transformation, entsprechend Gleichung Gl. 1, sehr anschaulich interpretiert werden. Die Lesart ist von rechts nach links. Der rechte Teil transformiert Punkte von Welt- oder Modellkoordinaten in Kamerakoordinaten und der linke weiter in Bildkoordinaten. Der rechte Teil kann auch als Position und Orientierung der Kamera in Welt- oder Modellkoordinaten betrachtet werden. Gesucht ist also gerade dieser rechte Teil, der von sechs unabhängigen Parametern abhängt.

Damit ist ein sechsdimensionaler Parameterraum definiert, in dem genau ein Punkt (6- Tupel) und eine zugehörige perspektivische Transformation existiert, die Modell und Bild optimal aufeinander abbilden. Das Ziel des Variationsansatzes besteht im Auffinden genau dieser Transformation.

Zielfunktion

Um nach dem Variationsansatz eine optimale Lösung zu ermitteln, ist es gewinnbringend den Begriff "optimal" zunächst zu objektiveren. Das heißt, es muß eine Möglichkeit geschaffen werden, eine beliebige Lösung (n-Tupel im Parameterraum) hinsichtlich ihrer Güte zu bewerten, um sie mit anderen Lösungen vergleichen, sie gegebenenfalls zielgerichtet verbessern oder verwerfen zu können. Genau diesem Zweck dient die sogenannte Zielfunktion (Objective Function).

Aus mathematischer Sicht handelt es sich hierbei um eine Funktion, die einen vektoriellen Definitionsbereich (Parameterraum) auf einen skalaren Wertebereich (Güte) eindeutig abbildet.

Die Zielfunktion ist typischerweise hochgradig anwendungsspezifisch und an das Problem angepaßt. Sie bestimmt maßgeblich die Systemleistung. Die Verfahren hingegen, mit denen eine im Sinne der Zielfunktion optimale Lösung gesucht wird, sind prinzipiell austauschbar und frei wählbar. Bei ihrer Auswahl sind die jeweils gegebenen zum Teil diametralen Rahmenbedingungen beispielsweise hinsichtlich Rechenaufwand, Parallelisierbarkeit, Sicherheit, Konvergenzradius und dergleichen zu berücksichtigen. Für den Entwurf der Zielfunktion besteht in der Regel ein nahezu unbegrenzter Gestaltungsspielraum, der möglichst virtuos genutzt werden sollte. Eine gute Zielfunktion ist im Sinne der Aufgabenstellung signifikant und objektiv, effizient auswertbar, stetig und konvex (d. h. genau ein Optimum) oder, falls das nicht möglich ist, zumindest stetig und weich (d. h. wenige Nebenoptima).

In besonders vorteilhafter Weise läßt sich das erfindungsgemäße Verfahren mittels dreier unterschiedlicher Zielfunktionen ausgestalten, welche von zwei unterschiedlichen Optimierungsverfahren ausgewertet werden. Im nachfolgenden werden diese unterschiedlichen gewinnbringenden Ausgestaltungen der Erfindung im Detail erläutert. Hierbei beruhen alle drei unterschiedlichen Zielfunktionen im wesentlichen auf einer perspektivischen Transformation der Modellobjekte in Abhängigkeit des zu bewertenden Parametersatzes.

Bei den Modellobjekten handelt es sich um ungerichtete Strecken mit zwei Endpunkten, die im folgenden Kanten genannt werden, und die zu Polygonen zusammengesetzt sein und Kurven annähern können. Um eine solche Strecke perspektivisch zu transformieren, reicht es aus, die beiden Endpunkte zu transformieren, denn Geraden sind unter der perspektivischen Transformation invariant. Nachdem die Modellobjekte auf das Bild abgebildet worden sind, brauchen nur noch diejenigen Objekte weiter betrachtet werden, die auch tatsächlich innerhalb des Bildbereiches liegen. Um diese Selektion aus Effizienzgründen noch vor der Transformation vornehmen zu können, wurde das bereits in Fig. 1 beschriebene Lochkameramodell um einen Sichtbarkeitskegel ergänzt, wodurch sich die Relevanz einzelner Modellobjekte aufgrund einfacher geometrischer Berechnungen (Strahlensatz) entscheiden läßt.

Um die Güte einer Abbildung angeben zu können, muß für jedes einzelne Modellobjekt im Bildbereich untersucht werden, wie nahe es an einem korrespondierenden Bildobjekt liegt. Je besser das Mittel der Übereinstimmungen der Einzelobjekte ist, desto besser ist auch die Güte der Abbildung. Durch statistische Untersuchungen höherer Ordnung kann die Signifikanz des Gütemaßes weiter gesteigert werden. Beispielsweise ist eine höhere Güte anzunehmen, wenn alle Modellobjekte nur mäßig mit entsprechenden Bildobjekten korrespondieren, als wenn nur wenige Modellobjekte sehr gut mit entsprechenden Bildobjekten korrespondieren.

Ein großer Vorteil des Variationsansatzes im Gegensatz zum kombinatorischen Ansatz liegt darin begründet, dass es möglich wird, bei einem geeigneten Entwurf der Zielfunktion auch ohne explizite Extraktion von diskreten Bildobjekten auszukommen. Dies ist insofern besonders vorteilhaft, als daß somit gleich zwei möglicherweise sehr aufwendige und fehlerträchtige Verfahrenschritte vermieden werden können, nämlich zum einen die Objektbildung selbst und zum andern die Lösung des Zuord nungsproblems von Bild- und Modellobjekten. Beispielsweise kann die Übereinstimmung von Modellkanten mit dem Bild einer Kamera auch ohne explizite Kanten in den Bilddaten mit Hilfe einer sogenannten Kantenabstandsfunktion, die an jeder beliebigen Position im Bild ein Maß für den Abstand zu den nächstgelegen Kanten liefert, bewertet werden.

Eine Kantenabstandsfunktion kann beispielsweise mit Hilfe eines geeigneten Kantenoperators, wie dem Sobeloperator, dem Prewittoperator oder dem Cannyoperator (Canny, J., A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No. 6, November 1986, p. 679-698), und eines Diffusionsmechanismus, wie der Auflösungspyramide, erreicht werden. Der Kantenoperator ermittelt für jeden Bildpunkt eine kontinuierliche Kantenstärke. Insbesondere wird weder eine harte, mehr oder weniger fehlerbehaftete Entscheidung über das Vorhandensein einer Kante, noch über deren Länge oder deren Endpunkte getroffen. Der Diffusionsmechanismus "ver schmiert" nun die kontinuierliche Kantenstärke über die umliegenden Bildpunkte, so daß anschließend für jeden Bildpunkt ein Maß für den Kantenabstand zur Verfügung steht. Er verleiht der Zielfunktion den gewünschten Grad an Unschärfe entsprechend den gewählten Auflösungsstufen.

Von besonderem Interesse sind in diesem Zusammenhang die Hough-Transformationen des Bildes und des Modells. Da der Cannyoperator neben der Kantenstärke auch eine Kantenorientierung liefern kann, erfüllt er die Voraussetzung zu einer besonders effizienten Spielart der Hough-Transformation, bei der pro Bildpunkt lediglich ein Punkt im Houghraum akkumuliert werden muß. Der Houghraum stellt neben dem Bildraum und dem Modellraum einen dritten, sehr kooperativen Raum zur Bewertung einer Abbildung dar. Im Bildbereich kann die Antwort eines Kantenoperators insbesondere bei schwachen oder verrauschten Kanten zum Teil sehr unbefriedigend ausfallen. Dadurch, daß bei der Hough-Transformation alle Beiträge von Bildpunkten entlang einer geraden und eventuell auch unterbrochenen Kante idealerweise auf einen Punkt im Houghraum konzentriert werden, führt sie ein integrierendes Verhalten ein. Auch im Houghraum kann ein Diffusionsmechanismus, wie die Auflösungspyramide, angewendet werden, um solche Konzentrationen (Cluster) zu "verschmieren", und um wiederum zu einer Kantenabstandsfunktion zu gelangen, die der Zielfunktion die gewünschte Weichheit verleiht.

Im Bildraum kann die Bewertung einer Modellkante durch hinreichend viele Abtastungen der Kantenabstandsfunktion entlang einer abgebildeten Modellkante gewonnen werden. Da eine Gerade im Bildraum mit genau einem Punkt im Houghraum korrespondiert, reduziert sich dieser Aufwand im Houghraum in vorteilhafter Weise auf eine einzige Abtastung der Kantenabstandsfunktion. Dabei bleiben jedoch die Endpunkte der Modellkanten unberücksichtigt, da unter der Hough-Transformation nur die Steigung und der Abstand zu einem Referenzpunkt erhalten werden.

Optimierungsverfahren

In der Literatur sind eine Vielzahl von Verfahren zur numerischen Bestimmung von Funktionsminima oder -maxima bekannt. Die Funktionen in diesem Kontext sind meist hoch-dimensional, nicht-linear und nicht explizit analytisch bekannt, da ja die Bestimmung von Extremwerten sonst trivial wäre. Die meisten dieser Verfahren arbeiten iterativ, indem sie von einem mehr oder minder guten Startwert ausgehend durch zielgerichtetes Probieren schrittweise gegen eine Lösung konvergieren. In jeder Iteration werden die jeweilige Zielfunktion und je nach Verfahren auch deren partiellen Ableitungen ausgewertet. Verfahren, die partielle Ableitungen benötigen, konvergieren in der Regel schneller, jedoch ist die Berechnung dieser Ableitungen oft mit einem erheblichen Mehraufwand und einer erheblichen Einschränkung des Gestaltungsspielraumes für den Entwurf der Zielfunktion verbunden.

In besonders vorteilhafter Weise läßt sich das erfindungsgemäße Verfahren zur Positions- und Lageschätzung durch die Verwendung des Downhill-Simplex-Verfahren (Press, W. H.; Teulosky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical Recipes in C, Reprinted Second Edition 1994, Press Syndicate of the University of Cambridge) oder des Bipartitionsverfahren im Rahmen der Optimierung bezüglich des Abgleichs zwischen den Bilddaten einer Kamera und Modellstrukturen ausgestalten. Dies vor allem aus dem Grund, dass diese beiden Optimierungsverfahren ohne partielle Ableitungen auskommen.

Bei nichtlinearen Funktionen kann es neben einem globalen Optimum noch weitere lokale Optima geben. Unglücklicherweise kann kein aus dem Stand der Technik bekanntes praktikables Verfahren garantieren, gegen das globale Optimum zu konvergieren. Es besteht vielmehr stets die Gefahr der Konvergenz gegen ein lokales Optimum. Ob es sich bei einer Lösung um ein globales oder ein lokales Optimum handelt, kann in der Regel nicht festgestellt werden. Falls mehrere, teilweise bessere Lösungen existieren und bekannt sind, kann lediglich ausgeschlossen werden, daß es sich bei einer Lösung um ein globales Optimum handelt. Da man praktisch aber nur an globalen Optima interessiert ist, müssen geeignete Maßnahmen ergriffen werden, um diese Problematik zu entschärfen. Bestimmte Optimierungsverfahren sind sehr robust gegenüber lokalen Optima, wie beispielsweise das Simulated Annealing. Diese Robustheit geht jedoch mit einem meist inakzeptablen Rechenaufwand einher. Lokale Optima können auch durch die Wahl des Startwertes vermieden werden. Denn meist sind durch die Investition von anwendungsspezifischem Modellwissen gute Schätzungen für das globale Optimum möglich und damit auch engere Konvergenzradien zugänglich. Der Konvergenzradius kann mit Hilfe weicher Zielfunktionen vergrößert werden.

Das Downhill-Simplex-Verfahren beruht auf einem Simplex, der von einer Menge von Eckpunkten im Parameterraum aufgespannt wird. Ein Simplex ist eine einfache geometrische Struktur mit n + 1 Ecken im n-dimensionalen Raum. Dies ist beispielsweise ein Dreieck in 2D oder ein Tetraeder in 3D. Zunächst wird jeder Eckpunkt des Simplex im Sinne der Zielfunktion bewertet. Anschließend wird iterativ der jeweils schlechteste Eckpunkt durch einen besseren ersetzt. Dafür stehen vier verschiedene Regeln zur Verfügung: Reflektion, Reflektion mit Expansion, Kontraktion und multiple Kontraktion. In Abhängigkeit vom Startsimplex expandiert sich der Simplex, schreitet in Richtung Optimum und kontraktiert sich schließlich. Die Iteration wird nach einer maximalen Anzahl von Schritten abgebrochen oder wenn sich der Simplex an einem Optimum kontraktiert hat. Der Parameterraum wird dabei jeweils an den Eckpunkten des Simplex diskret abgetastet und bewertet.

Beim Bipartitionsverfahren werden im Gegensatz zum Downhill-Simplex-Verfahren nicht diskrete Punkte im Parameterraum, sondern kontinuierliche Volumina bewertet. Ausgehend von einem hinreichend großen Startvolumen, das die optimale Lösung sicher enthält, wird in jeder Iteration das jeweilige Volumen in jeder Dimension halbiert. So entstehen 2ⁿ Subvolumina, die im Sinne der Zielfunktion bewertet werden. Das jeweils beste Subvolumen wird bis zu einer minimalen Größe weiterverarbeitet, mit dem Ziel die optimale Lösung sukzessive einzugrenzen. Im Interesse der Effizienz kann es vorteilhaft sein, Zugeständnisse an die Objektivität der Zielfunktion zu machen. In diesem Fall ist es möglich die jeweils n besten Subvolumina weiterzuverarbeiten, um etwaige Fehlentscheidung wieder heilen zu können.

In besonders vorteilhafter Weise eignet sich die Hough-Transformation als sehr effiziente Zielfunktion zur Bewertung solcher Volumina. Eine mit einer bestimmten perspektivischen Transformation in den Bildraum abgebildete Modellkante korrespondiert im Houghraum mit einem Punkt. Ein Volumen im Parameterraum beinhaltet eine Menge von Parametersätzen mit den zugehörigen Transformationen. Unter der Wirkung dieser Menge von Transformationen wird eine Modellkante auf eine Kantenschar im Bildraum, die mit einem zusammenhängenden Gebiet im Houghraum korrespondiert, abgebildet. Dies läßt sich aus einfachen Überlegungen zur Stetigkeit schlußfolgern. Das zusammenhängende Gebiet im Houghraum läßt sich effizient abschätzen, indem man nur die Transformationen, die zu den Ecken des zu bewertenden Volumens gehören, betrachtet. Da sie das zu bewertende Volumen im Parameterraum aufspannen, spannen sie angewandt auf jede Modellkante näherungsweise auch die zusammenhängenden Gebiete im Houghraum auf.

Vorteilhaft ist eine Approximation dieser Gebiete im Houghraum mit achsenparallelen Rechtecken (bounding box), da man die darin enthaltene Kantenstärke sehr effizient wiederum über die Betrachtung ihrer Ecken berechnen kann. Etwaige durch diese Näherungen verursachte Fehlentscheidungen, können wieder geheilt werden, indem man mehrere Alternativen bei der Optimierung verfolgt. Die Näherungen sind um so gröber, je größer die zu bewertenden Volumina sind. Die Anzahl der Alternativen kann also über die Iteration degressiv eingestellt werden. Der Aufwand pro Iteration sinkt demnach mit der Größe der zu bewertenden Volumina. Dadurch kann überproportionale Effizienzsteigerung erreicht werden, falls sich das Anfangsvolumen aufgrund von anwendungsspezifischem Modellwissen verkleinern läßt.

Systemimplementierung

Fig. 3 zeigt das Ablaufdiagramm des erfindungsgemäßen Verfahrens zur Lage- und Positionsschätzung. In dem Diagramm sind als parallele Pfade, mögliche vorteilhafte Ausgestaltungen des Verfahrens, welche optional beschritten werden können, aufgezeigt.

In gewinnbringender Weise ist das erfinderische Verfahren modular aufgebaut und gliedert sich in die zwei Bereiche

- Vorverarbeitung
- und Matching-Verfahren,

welche in der Prozesskette aufeinander folgen.

Die einzelnen Schritte der Vorverarbeitung gliedern sich dabei in die sequentiell aufeinander folgenden, zum Teil optionalen Module

- Kantenoperator (Sobel oder Canny),
- optional Transformation (Hough, Distanz),
- optional Kantenabstandsfunktion (Auflösungspyramide und Rekomposition zur Diffusion),
- sowie optional Integration des Akkumulatorbildes

Bei der Implementierung der einzelnen Module der Vorverarbeitung ist es vorteilhaft darauf zu achten, dass möglichst hardware-orientierte Verfahren und Strukturen zu verwenden, um eine hardware-technische Realisierung des Verfahrens in integrierter Form als Prozessor-Bauteil zu erleichtern.

Filter

Die erfindungsgemäße Aufgabe besteht in einem Abgleich von Bilddaten, insbesondere von darin enthaltenen linienartigen Strukturen, einer Kamera mit Modellstrukturen. Daher steht am Anfang der Vorverarbeitung als erster Schritt ein Kantenfilter. Mit Hilfe eines solchen Kantenfilters wird versucht, die Original-Bilddaten der Kamera so zu verarbeiten, dass nur noch kantenhafte Strukturen übrigbleiben (Kantenbild). In besonders vorteilhafter Weise eignet sich hierzu ein Sobel-Filter. Es ist gleichwohl aber auch denkbar an dessen Stelle ein Canny-Filter zu verwenden.

Hough-Transformation

In realen Bilddaten treten häufig Texturen mit zum Teil starken Gradienten in wechselhaften Richtungen auf, die sich schädlich auf die Systemleistung des erfindungsgemäßen Verfahrens auszuwirken drohen. Um dies zu vermeiden kann in einer vorteilhaften Ausgestaltung der Erfindung als optionaler Zwischenschritt eine vereinfachte Hough-Transformation eingeführt werden. Voraussetzung ist hierfür ein vorangestellter Kantenfilter, der neben der Kantenstärke auch eine hinreichend genaue Schätzung für die Kantenrichtung (dx, dy) innerhalb der zweidimensionalen Bilddaten liefert. In vorteilhafter Weise genügt der zuvor erwähnte Canny-Filter diesen Anforderungen.

Bei der vereinfachten Hough-Transformation wird ein Akkumulatorbild erzeugt. Dabei wird gedanklich durch jeden Bildpunkt des Kantenbildes eine Gerade mit der geschätzten Kantenrichtung gelegt. Diese Gerade wird beschreiben durch den Steigungswinkel Phi und den Abstand r von einem Referenzpunkt, beispielsweise dem Mittelpunkt des Kantenbildes. Die Parameter r und Phi ergeben die Position der Geraden durch diesen Bildpunkt im Akkumulatorbild wieder. Der Wert des Akkumulators an der Position (r, Phi) wird gewichtet mit dem Wert der Kantenstärke an diesem Bildpunkt inkrementiert. Dadurch sammeln sich die Intensitäten entlang einer idealen Kante in einem Punkt des Akkumulatorbildes. Da ein Kantenfilter insbesondere bei realem, Datenmaterial im allgemeinen keine idealen, sondern "ausgefranste" Kanten liefert, erhält man für eine Kante im Kantenbild nicht einen Punkt, sondern einen Cluster im Akkumulator. Die erzielbare Genauigkeit wird einerseits von der Güte des Kantenfilters und andererseits von der Dimension des Akkumulatorfeldes bestimmt.

Bei gerichteten Kanten, wenn also ihre Orientierung definiert ist (z. B. links hell, rechts dunkel), ergibt sich ein Wertebereich von ±r für den Abstand der Kante vom Referenzpunkt, sowie ±180 Grad für den Steigungswinkel. Das erfindungsgemäße Verfahren sollte jedoch in gewinnbringender Weise so ausgelegt werden, dass es in der Lage ist generell mit ungerichteten Kanten umzugehen, so dass die Orientierung der Modellkanten nicht berücksichtigt werden muss. In diesem Fall ist die Adressierung des Akkumulatorfeldes nicht eindeutig, beispielsweise sind die Positionen (r, Phi) und (-r, Phi ±180°) substituierbar. Daher werden sowohl die vom Canny-Filter gelieferten Richtungswerte für beide Orientierungen (dx, dy) und (-dx, -dy) in das Akkumulatorfeld eingetragen. Vermutlich läßt sich die Systemleistung durch die Berücksichtigung der Orientierung der Modellkanten noch steigern, falls diese gegenüber meteorologischen und klimatischen Einflüssen invariant sind. Die Orientierungsinformation ist beispielsweise gerade bei parallelen Doppelkanten (z. B. dunkel, hell, dunkel) signifikant.

In der Praxis ist es denkbar das die zur Verfügung stehenden Bilddaten eine Auflösung von 256 × 256 Pixeln haben. Dies entspräche einer Diagonale von rund 362 Pixeln. Dementsprechend wären bei einem Referenzpunkt in der Bildmitte eine Auflösung des Akkumulatorfeldes von 768 = 3.28 für -180° < r < +180° und 512 = 2.2⁸ für -180° < Phi < +180° eine gute Wahl. Dies entspräche einem Quantisierungsfehler von weniger als einem Pixel und weniger als einem Grad.

In besonders vorteilhafter Weise könnte bei ungerichteten Kanten die Hälfte des Akkumulatorfeldes (r < 0 bzw. Phi < 0) eingespart werden, da durch die doppelte Inkrementierung des Akkumulators eine Punktsymmetrie entsteht.

Da am Rand des Akkumulatorfeldes unter Umständen aufwendige und eventuell fehlerträchtige Fallunterscheidungen auftreten, kann in gewinnbringender Weise der Winkelbereich in obigem Bild links und rechts um jeweils 180 Grad periodisch fortgesetzt werden. Dabei muss jedoch eine Verdopplung des Speicheraufwandes in Kauf genommen werden. Der Rechenaufwand für das Kopieren der Daten in diesen zusätzlichen Speicherbereich ist jedoch verschwindend gering gegenüber der für die Fallunterscheidungen notwendigen Rechenleistung.

Distanztransformation

Die Distanztransformation beschreibt für jedes Pixel eines Kantenbildes den Abstand zum nächst liegenden Pixel einer Kante. Dabei bietet es sich gewinnbringend an, vor der eigentlichen Distanztransformation das kantengefilterte Bild zu binarisieren, die Binärkanten ggf. auszudünnen, sowie das restliche Rauschen zu unterdrücken.

Binarisierung

Zur Binarisierung eines Grauwertbildes mit Werten z. B. zwischen 0-255 benötigt man zunächst eine geeignete Binarisierungsschwelle innerhalb des Wertebereiches (z. B. 20). Alle Pixel mit einem Wert größer als der Schwellwert werden auf den Maximalwert, alle Pixel mit kleineren Werten auf den Minimalwert gesetzt.

Ausdünnung von Kanten

Da ein Kantenfilter je nach eingestellten Parametern unter Umständen Kanten liefert, die mehr als ein Pixel breit sind, bietet es sich an die Kantenbilder entsprechen auszudünnen. Dies geschieht im Rahmen des erfindungsgemäßen Verfahrens in vorteilhafter Weise im Anschluß an die Binarisierung. Hierzu eignet sich gewinnbringend ein Algorithmus der auf einem Verfahren nach Haralick und Shapiro (Haralick; Shapiro, Computer and Robot Vision, Vol. 1, Chapter 5) basiert. Durch ein solches Ausdünnen der Kanten erhält man in späteren Stufen des erfindungsgemäßen Verfahrens ein genaueres Distanzbild.

Rauschunterdrückung

Des weiteren ist es denkbar gewinnbringend einen weiteren optionalen Vorverarbeitungsschritt dahingehend in des erfindungsgemäße Verfahren einzufügen, dass kleine Kantenfragmente unterdrückt werden. Eine solche Unterdrückung kommt einer Rauschunterdrückung gleich. Einstellbare Parameter können hierbei die minimale akzeptable Länge von Kantenfragmenten, sowie die Nachbarschaftsbeziehungen der einzelnen Pixel (z. B.: 4 oder 8 Nachbarpixel) sein.

Distanztransformation

Die Distanztransformation wird auf einem nach den vorab beschriebenen Schritten vorverarbeiten Binärbild ausgeführt. Dabei werden vorzugsweise alle Pixel des Bildes mit Binärwerten < 0 auf den Wert 0, mit Binärwerten = 0 auf einen maximalen Wert (maxDist) initialisiert. Dieser Maximalwert maxDist gibt an, wie weit die Distanz berechnet werden soll, d. h. Pixel mit einer weiteren Distanz zu einem Kantenpixel werden auf diesen Maximalwert gesetzt.

Anschließend wird in gewinnbringender Weise das Bild jeweils von links oben nach rechts unten durchlaufen und die Entfernung der jeweiligen Pixel zu einer Kante mittels einer 3 × 3-Distanzmatirx vorwärts bzw. rückwärts propagiert. Die Distanzmatrix D hat dabei folgende Form:

Die Werte der Distanzmatrix D stellen eine recht gute ganzzahlige Näherung der euklidischen Distanz dar, wobei die Einträge gedanklich halbiert werden müssen. Die horizontalen und vertikalen Nachbarn der Matrixmitte (0) haben den Distanzwert 2 (Distanz = 1), die diagonalen Nachbarn haben den Distanzwert 3 (Distanz = 1.5 als Näherung zu √2).

Trifft man beim Vorwärtsdurchlauf durch das Bild erstmals auf ein Pixel mit dem Wert 0, so kann man ausgehend von dieser Position anhand der Distanzmatrix die Distanzen der nachfolgenden Pixel (rechts unten) ausgehend von diesem Pixel berechnen. Beim Rückwärtsdurchlauf erfolgt die Distanzpropagation genau umgekehrt, ausgehend von einem Pixel mit Wert 0 nach links oben. Sind hierbei schon Distanzwerte kleiner als der initialisierte Maximalwert eingetragen, so ist das jeweilige Minimum aus bisherigem Wert und neu propagiertem Distanzwert einzutragen. Abschließend ergibt sich ein Distanzbild als Grauwert-Bild, bei dem die Entfernung eines Pixels zum nächsten Kantenpixel einem Helligkeitswert entspricht, wobei die genäherte euklidische Distanz zwischen Pixel und nächstem Kantenpixel der Hälfte des Grauwertes entspricht.

Durch die Distanztransformation entsteht ein diffuses Bild, das ähnliche Eigenschaften mit der in nächsten Abschnitt beschriebene Auflösungspyramide hat.

Auflösungspyramide

Die Auflösungspyramide ist ein probates Mittel zur Diffusion, um aus dem Kantenbild oder Hough-Bild eine weiche Kantenabstandsfunktion und damit eine gutartige Zielfunktion zu realisieren.

Die Anzahl der Stufen einer Auflösungspyramide hängt in der Regel von ihrer Steigung und von der Größe des zugrundeliegenden Bildes ab. In besonders gewinnbringender Weise wird innerhalb des erfindungsgemäßen Verfahren die Anzahl der Pixel in jeder Stufe halbiert oder geviertelt, bis zu einer Anzahl von typisch 6 Stufen. Die Basis der Auflösungspyramide ist das Kantenbild oder das Hough-Bild selbst. Jede weitere Stufe ergibt sich aus der vorgehenden Stufe durch Tiefpassfilterung und Unterabtastung. Als Tiefpassfilter ist es denkbar aus Effizienzgründen ein 3 × 3 Binomialfilter zu verwenden. Bei dieser Informationsreduktion werden je nach Reduktionsfaktor mehrere Pixel der aktuellen Ebene zu einem Pixel der darüberliegenden Ebene zusammengefaßt. Dadurch wird die Information von einer Ebene zur nächsten um den Faktor 4 ausgedünnt.

Komposition der Pyramide

Eine sehr gutartige Kantenabstandsfunktion erhält man beispielsweise durch gewichtete Addition über alle Pyramidenstufen, wobei die nächste Stufe immer mit dem doppelten Gewicht der Vorgängerstufe gewichtet wird. Die einzelnen Stufen werden durch Interpolation auf das Format des Basisbildes gebracht.

Integration des Akkumulatorbildes

Ausschließlich für die Anwendung des Bipartitionsverfahrens ist der im folgenden beschriebene Vorverarbeitungsschritt nötig, der an Stelle der Pyramidenbildung auf das houghtransformierte Akkumulatorbild angewandt wird. Die einzelnen Verhältnisse einer solchen Integration innerhalb eines Akkumulatorbildes sind in Fig. 4 dargelegt.

Das Bipartitionsverfahren benötigt zur Berechnung der Zielfunktion im Gegensatz zum Downhill-Simplex-Verfahren auf Hough-Bildern nicht die Bewertung eines einzelnen Punktes des Akkumulatorbildes, sondern eines in Näherung rechteckigen; entsprechend der obigen Diskussion des Optimierungsverfahrens auf Basis des Bipartitionsverfahrens. Zur Vermeidung unzähliger Summationen bei jeder Berechnung der Zielfunktion wird vorzugsweise das Akkumulatorbild vorab integriert, das heißt zuerst zeilenweise und dann spaltenweise aufaddiert. Dadurch enthält ein Punkt P im integrierten Akkumulatorfeld die Bewertung aller Punkte in dem durch die Diagonale zwischen Ursprung (0) und P aufgespannten Rechteck des originalen Akkumulatorbildes (Fig. 4a), b)).

Die Bewertung aller Punkte innerhalb eines beliebigen achsenparallelen Rechtecks (A, B, C, D) erhält man, indem im integrierten Akkumulatorfeld von der Bewertung im Punkt D die Bewertungen für B und C subtrahiert und die Bewertungen für A wieder addiert werden.

Matching-Verfahren

Im nachfolgenden werden die vier, im Rahmen des erfindungsgemäßen Verfahrens zur Positions- und Lageschätzung besonders vorteilhaften Algorithmen zum Abgleich von Bilddaten einer Kamera mit Modellstrukturen im Detail diskutiert; dies sind:

- das Downhill-Simplex-Verfahren auf dem Originalbild,
- das Downhill-Simplex-Verfahren auf dem Hough-Bild,
- das Downhill-Simplex-Verfahren auf dem Distanzbild,
- sowie das Bipartitionsverfahren.

Downhill-Simplex-Verfahren auf dem Originalbild

Das Downhill-Simplex-Verfahren auf dem Originalbild benötigt die in den Unterpunkten Filter, Pyramidenaufbau und Komposition der Pyramide zuvor erläuterten Schritte der Vorverarbeitung, die als Ergebnis ein gewichtetes Summenbild der Auflösungspyramide ergeben. Dieses Summenbild ist die Datenbasis zur Berechnung der jeweiligen Werte der Zielfunktion Z_DS

Die Zielfunktion Z_DS liefert eine summarische Bewertung für die Güte des Abgleichs der n einzelnen Modellkanten im Bild. Die zu bewertenden Positionen der Modellkanten in den Bilddaten erhält man durch Transformation T der Modellkanten über das Kameramodell in Bildkoordinaten. In obiger Formel bezeichnen t₀ und t₁ Endpunkte der jeweiligen Modellkante in Weltkoordinaten, während T(t₀) und T(t₁) den entsprechenden Endpunkten in Bildkoordinaten entsprechen. Zwischen den beiden Endpunkten T(t₀) und T(t₁) ist nun die Kantenabstandsfunktion F zu integrieren, d. h. es werden die Werte der Gradienten des Summenbildes der Auflösungspyramide durch Unterabtastung zwischen den Bildendpunkten der jeweiligen Kante aufaddiert. Die Summe der Integrale über alle n Kanten ergibt dann den Wert der Zielfunktion, die ein Maß für die Güte der Abstimmung des Modells mit den Bilddaten bezüglich der aktuellen Transformation T liefert. Da es sich beim Downhill-Simplex-Verfahren um ein Minimierungsverfahren handelt wird der Wert der Zielfunktion, die stets nicht negative Werte besitzt, mit umgekehrtem Vorzeichen interpretiert. Dadurch wird erreicht, dass eine Kante mit den höchsten Werten der Gradienten den Minimalwert der Zielfunktion bildet.

Optimierung mit dem Downhill-Simplex-Verfahren

Das Downhill-Simplex-Verfahren arbeitet bei einer Optimierung von n Parametern mit einem n-dimensionalen Simplex, der aus n + 1 Eckpunkten besteht. In der bildgestützten Navigation sind Optimierungsprobleme mit bis zu 6 Freiheitsgraden (jeweils 3 Rota tions- und Translationsparameter) zu lösen. Daher müssen für eine solche Aufgabe, insbesondere für die Navigation eines autonomen Flugkörpers, bis zu 7 geeignete Eckpunkte für den Startsimplex ermittelt werden.

Dazu bietet es sich an für jeden Freiheitsgrad ein hinreichend großes Intervall vorzugeben, in dem die optimale Lösung enthalten ist. Somit entsteht ein 6- dimensionaler Suchraum mit 2⁶ = 64 Eckpunkten. Jeder Punkt dieses Suchraums steht für eine mögliche Transformation T, mittels derer die Modellkanten auf das Bild abgebildet werden. Der Einfachheit halber wählt man für den Startsimplex die 7 im Sinne der Zielfunktion am besten bewerteten Eckpunkte, deren Verbindungsvektoren den Lösungsraum aufspannen. Um zu vermeiden, daß der Simplex den vorgegebenen Lösungsraum verläßt, wird das Ergebnis der Zielfunktion in den Randbereichen mit einem Malus versehen. Damit der Simplex nicht schon beim ersten Spiegelschritt über den Rand des zulässigen Bereiches hinausläuft, empfiehlt es sich, den zur Berechnung des Startsimplex vorgegebenen Lösungsraum um mindestens 50% zu reduzieren.

Die Vorgehensweise ist in Fig. 5 schematisch für 2 Parameter dargestellt. Die resultierenden Eckpunkte des vorgegebenen Lösungsraumes sind P₁, . . ., P₄. Die möglichen Punkte für den Startsimplex sind S₁, . . ., S₄. Die Vektoren durch jeweils 3 dieser Punkte spannen den Lösungsraum auf und sind somit linear unabhängig. Somit bilden 3 Punkte aus S₁, . . ., S₄ einen zulässigen Startsimplex. Die lineare Unabhängigkeit der Vektoren durch n + 1 Eckpunkten eines n-dimensionalen Quaders ist für n = 2 trivial, nicht jedoch für höhere Dimensionen.

Selbstverständlich kann man jede Kombination von n + 1 Punkten des Lösungsraums als Startsimplex eines n-dimensionalen Optimierungsproblems wählen, deren Vektoren den Lösungsraum aufspannen.

Die besten Ergebnisse erzielt man, wenn es gelingt, den Startsimplex möglichst gleichseitig zu gestalten. Dies ist bei Verwendung von Parametern unterschiedlicher Größenordnungen (Transformationen in Metern, Rotationen in Bogenmaß) nur durch entsprechende Skalierung möglich. So empfiehlt es sich in vorteilhafter Weise den im Vergleich zu den Translationsparametern kleinen Wertebereich der Rotationsparameter (Längen in Metern versus Winkel in Bogenmaß) durch entsprechende Skalierungsfaktoren einander anzupassen. Selbstverständlich wird dies bei der Interpretation der Ergebnisse wieder kompensiert.

Ausgehend von dem mittels der Zielfunktion bewerteten Startsimplex versucht das Downhill-Simplex-Verfahren, wie bereits beschrieben, den schlechtesten Punkt des Simplex mittels den Operationen "Reflektion", "Reflektion mit Expansion" und "Kontraktion" durch einen besseren Punkt zu ersetzen. Ist das nicht möglich, führt es eine "multiple Kontraktion" durch, bei welcher der Simplex zum bisher besten Punkt hin kontraktiert wird, also n Eckpunkte durch neue ersetzt werden. Dieser Prozeß wird so lange wiederholt, bis die Bewertung aller Eckpunkte des Simplex und ihre Abweichungen untereinander eine definierbare Schwelle unterschreiten oder eine maxi mal zulässige Anzahl von Iterationen erreicht ist.

Downhill-Simplex-Verfahren auf dem Hough-Bild

Das Downhill-Simplex-Verfahren auf dem Hough-Bild benötigt gegenüber den Vorverarbeitungsschritten des Downhill-Simplex-Verfahren auf dem Originalbild unmittelbar nach dem Canny-Filter als Kantenoperator zusätzlich eine Hough- Transformation. Darauf folgt wie beim Verfahren auf dem Originalbild der Pyramidenaufbau und die Komposition der Pyramide.

Das am Ende der unterschiedlichen Schritte der Vorverarbeitung erzeugte Summenbild ist die Datenbasis zur Berechnung der jeweiligen Werte der Zielfunktion Z_DS

Die Berechnung der Zielfunktion ZDS gestaltet sich aufgrund der in der Vorverarbeitung durchgeführten Hough-Transformation gegenüber der Zielfunktion des Downhill- Simplex-Verfahren auf dem Originalbild deutlich einfacher. Die Parameter t0 und t1 bezeichnen die Endpunkte der jeweiligen Modellkante in Weltkoordinaten. Da nun auch die ins Bild projizierten Modellkanten T(t0, t1) in den Houghraum H(T(t0, t1)) transformiert werden und dort mit genau einem Punkt korrespondieren, reduziert sich die Abtastung der Kantenabstandsfunktion entlang einer Kante auf die Abtastung an genau diesem Punkt. Die Optimierung mit dem Downhill-Simplex-Verfahren erfolgt analog zum Originalbild.

Downhill-Simplex-Verfahren auf dem Distanzbild

Das Downhill-Simplex-Verfahren auf dem Distanzbild benötigt die unter den Punkten Filter und Distanztransformation vorab erläuterten Schritte im Rahmen der Vorverarbeitung. Diese Vorverarbeitung liefert als Ergebnis ein grauwertiges Distanzbild. Der Grauwert eines Pixels entspricht dabei dem genäherten doppelten euklidischen Abstand zum nächstgelegenen Pixel einer Bildkante.

Dieses Distanzbild bildet sodann die Datenbasis zur Berechnung der jeweiligen Werte der Zielfunktion Z_DS

Bei der Anwendung des Verfahrens auf das Distanzbild, liefert Zielfunktion Z_DS analog zu der Anwendung des Downhill-Simplex-Verfahren auf dem Originalbild eine summarische Bewertung für Güte des Abgleichs (Matchgüte) der n einzelnen Modellkanten im Bild. Die zu bewertenden Positionen im Bild erhält man durch Transformation T der Modellkanten über das Kameramodell in Bildkoordinaten. In obiger Formel bezeichnen t₀ und t₁ die Endpunkte der jeweiligen Modellkante in Weltkoordinaten, während T(t₀) und T(t₁) den entsprechend Endpunkten in Bildkoordinaten entsprechen. Zwischen den beiden Endpunkten T(t₀) und T(t₁) ist nun die Kantenabstandsfunktion F zu integrieren, d. h. die Werte von F(T(t)) werden durch Unterabtastung zwischen den Bildendpunkten T(t₀) und T(t₁) der jeweiligen Kante aufaddiert. Die Summe der Integrale über alle n Kanten ergibt dann den Wert der Zielfunktion, die ein Maß für die Matchgüte des Modells mit dem Bild bezüglich der aktuellen Transformation T liefert.

Sei t ein Punkt in Weltkoordinaten, so ist T(t) der entsprechende Punkt in Bildkoordinaten. Sei D(T(t)) der entsprechende Wert von T(t)) im Distanzbild, so gilt:

F(T(t)) = D(T(t)) - maxDist Gl. 7

wobei maxDist die größtmögliche berechnete Distanz im Distanzbild darstellt, entsprechend der vorangegangenen Diskussion bzgl. der Initialisierung der Distanztransformation.

Diese neue Interpretation der Kantenabstandsfunktion ist nötig, damit die Optimierung mit dem Downhill-Simplex-Verfahren auf dem Distanzbild analog zum Verfahren auf dem Originalbild funktioniert.

Beim Downhill-Simplex-Verfahren auf dem Originalbild ist die Datenbasis ein über Pyramidenstufen integriertes Gradientenbild, d. h. die beste Bewertung erhält man direkt auf einer Kante. Je weiter man von einer Kante entfernt ist, desto schlechter wird die Bewertung.

Im Distanzbild ist dies genau umgekehrt. Distanzbilder sind vom Prinzip her inverse Pyramidenstufen, so dass man die besten Bewertungen (hellster Grauwert) in möglichst weiter Entfernung von einer Bildkante erhält. Zieht man nun von einem solchen Distanzwert D(T(t)) eines Bildpunktes T(t) maxDist ab, so erhält man für das Minimierungsproblem entweder

- auf einer Kante den Wert: Minimalwert - maxDist
- weit weg von einer Kante den Wert: 0 = maxDist - maxDist

Die Optimierung mit dem Downhill-Simplex-Verfahren erfolgt analog zum Verfahren auf dem Originalbild mittels oben beschriebener Zielfunktion.

Verifikation des Ergebnisses

Durch den Einsatz von Distanztransformationen erhält man im Gegensatz zum Downhill- Simplex-Verfahren auf Original- bzw. Hough-Bildern, die Möglichkeit die vom jeweiligen Optimierungsverfahren erreichte optimale Transformation T_opt von Modell- auf Bildkante auf Plausibilität zu prüfen.

Dazu berechnet man für jede transformierte Modellkante die durchschnittliche Abweichung dist zu den entsprechenden Kantenpixeln des Distanzbildes nach folgender Gleichung

wobei T_opt(t₁) und T_opt(t₀) die Endpunkte einer Modellkante in Bildkoordinaten, sowie len(a, b) die Länge der Kante mit den Endpunkten a und b bedeuten.

Weiterhin lassen sich zu jeder Modellkante auf einfache Weise folgende Parameter in Bildkoordinaten bestimmen:

- Länge
- mittlere Abweichung vom Distanzbild
- Maximale Abweichung vom Distanzbild
- Minimale Abweichung vom Distanzbild
- Abweichung an den Kantenendpunkten
- Koordinaten der Kantenendpunkte

Daraus wiederum lassen sich Aussagen über die Lage der Modellkanten und der Güte der Übereinstimmung (Matchgüte) im Bild ableiten. So sind beispielsweise lange Kanten mit geringen Abweichungen ein Indiz für sicher erkannte Kanten, Kanten mit maximaler Abweichung an einem Endpunkt auf falsche Länge bei korrekter Richtung im Bild hinweisen.

Unter Umständen kann es zu schlechten Übereinstimmungen einzelner Modellkanten mit dem Bild bei ansonsten guter Matchgüte der übrigen Kanten kommen. Als Ursache hierfür kommen entweder falsche Ergebnisparameter aus dem Iterationsverfahren oder das Fehlen der Modellkanten in den Bilddaten der Kamera in Betracht. Letzteres kann u. U. an einer ungeschickten Wahl der Binarisierungsschwelle liegen.

Daher ist es möglicherweise hilfreich, in der Vorverarbeitung Distanzbilder mit unterschiedlichen Binarisierungen zu berechnen. Dann wäre das Ergebnis der Iteration auf unterschiedlichen Distanzbildern verifizierbar. Bei der Verarbeitung von Bildfolgen würde sich eine Mehrfachberechnung von Distanzbildern nach wenigen Elementen der Bildfolge aufgrund des gesammelten Vorwissens erübrigen.

Bipartitionsverfahren

Das Bipartitionsverfahren verwendet im Rahmen seiner Vorverarbeitung eine Zusammenschaltung eines Canny-Operators mit der Hough-Transformation und einer Integration des Akkumulator Bildes. Das integrierte Akkumulator Bild ist die Datenbasis zur Berechnung der jeweiligen Werte der Zielfunktion Z_BP, entsprechend:

Die Zielfunktion liefert eine summarische Bewertung für die Matchgüte der n einzelnen Modellkanten im Bild, jedoch nicht wie im Downhill-Simplex-Verfahren bezogen auf eine einzelne Transformation T, sondern für alle möglichen Transformationen innerhalb eines vorgegebenen Lösungsraumes L. Dieser Lösungsraum ist ein n-dimensionaler Quader, der entsteht, indem man sich für alle n Freiheitsgrade ein Intervall vorgibt, in dem die jeweils richtige Lösung enthalten ist.

Wie bei der Diskussion der Optimierungsfunktionen dargelegt, ergibt sich aus der houghtransformierten Menge aller möglichen Transformationen T aus L für eine Modellkante in Weltkoordinaten jeweils ein zusammenhängendes Gebiet G im (integrierten) Akkumulatorbild. Das G umschließende Rechteck R dient als Näherung zur Berechnung von G. Wie im Abschnitt zur Integration des Akkumulatorbild beschrieben, läßt sich für eine Modellkante der jeweilige Wert der Zielfunktion Z_BP für das durch R angenäherte Volumen G sehr einfach aus dem integrierten Akkumulatorbild ermitteln. Die Summation über alle Modellkanten ergibt den Gesamtwert der Zielfunktion Z_BP.

Das Bipartitionsverfahren teilt den n-dimensionalen Lösungsraum ausgehend von einem Startlösungsraum L in jedem Iterationsschritt in 2ⁿ Subvolumina. Das jeweils beste Subvolumen im Sinne der Zielfunktion wird bis zu einer minimalen Größe in Abhängigkeit von der Anzahl vorgegebener Iteration weiterverarbeitet, um die optimale Lösung sukzessive einzugrenzen. In den ersten Iterationen, bzw. bei großen Anfangsvolumina und der aus Effizienzgründen genäherten Zielfunktion kann es zu Fehlbewertungen der Subvolumina kommen. Daher ist es vorteilhaft, mehrere Alternativvolumina bei der Optimierung zu verfolgen, um Fehler bei der Näherung korrigieren zu können. Die Anzahl betrachteter Alternativen kann degressiv mit jedem Iterationsschritt vermindert werden. Der Algorithmus liefert nach Durchführung der voreingestellten k Iterationsschritte ein Lösungsvolumen, das gegenüber dem Startvolumen um den Faktor 2^kn reduziert wurde.

Die Funktionalität des erfindungsgemäßen Verfahrens ist selbstverständlich nicht auf die Verwendung der oben angeführten Filterfunktionen und Optimierungsalgorithmen beschränkt. Die hier aufgezeigten Algorithmen dienen nur einer anschaulichen, vorteilhaften Ausgestaltung des neuartigen Verfahrens zur Lösung von Lokalisationsproblemen (Positions- und Lageschätzung) auf der Basis von geometrischem Matching. Bei der Auswahl alternativer Algorithmen ist nur darauf zu achten, dass im Rahmen ihres Zusammenwirkens deren Funktionalitäten möglichst vorteilhaft aufeinander abgestimmt werden. So können beispielsweise neben dem Sobel-Filter oder Canny-Filter auch andere Filteralgorithmen zur Vorverarbeitung der Bilddaten verwendet werden. Hierbei ist aber insbesondere zu beachten, dass es etwa für das Bipartitionsverfahren notwendig ist, dass gute Schätzungen der Kantenrichtung durch den Filter erfolgen. Dies kann jedoch beispielsweise alternativ zur Verwendung eines Sobel- oder Canny-Filter auch mittels eines Deriche-Filters erreicht werden.

Claims

1. Verfahren zur Positions- und Lageschätzung durch einen Abgleich von Bilddaten einer Kamera mit Modellstrukturen, ins besondere zur Erhöhung der Langzeitstabilität und der Autono mie von autonomen Flugkörpern,
wobei der Abgleich mittels einer Variation der Parameter einer Geometrie-Transformation (Variationsansatz), welche die Mo dellstrukturen mit den Bilddaten der Kamera aufeinander ab bildet, erfolgt
und als Ergebnis des Abgleichs, welcher mittels eines Va riationsansatzes erfolgt, die Parameter der Geometrie-Trans formation zur Positions- und Lageschätzung vorliegen,
dadurch gekennzeichnet,
dass die Parameter der Geometrie-Transformation mittels der Optimierung einer objektbildungsfreien Zielfunktion bestimmt werden.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das Verfahren modular aufgebaut ist und sich in die zwei we sentlichen Bereiche Vorverarbeitung und Matching gliedert.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass der Variationsansatz auf einem Simplex-Verfahren basiert, welches auf ein aus den ursprünglichen Bilddaten der Kamera gewonnenes Distanzbild angewandt wird.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet,
dass im Rahmen der Vorverarbeitung in einem ersten Schritt die ursprünglichen Bilddaten mittels eines Sobel-Filters gefiltert werden,
dass in einem weiteren Schritt aus den gefilterten Daten ein Distanzbild berechnet wird,
und dass das Matching dieses Distanzbildes mit einer oder mehreren Zielfunktionen mittels des Downhill-Simplex-Verfahrens erfolgt.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass nach der Berechnung des Distanzbildes dieses binarisiert und durch Entfernen von Rauschen gereinigt wird.

6. Verfahren nach einem der Ansprüche 4 oder 5, dadurch gekennzeichnet, dass die Filterung an Stelle des Sobel-Filters mit einem Canny-Filter erfolgt.

7. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass der Variationsansatz auf einem Simplex-Verfahren basiert, welches auf die ursprünglichen Bilddaten der Kamera angewandt wird.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet,
dass im Rahmen der Vorverarbeitung in einem ersten Schritt die ursprünglichen Bilddaten mittels eines Sobel-Filters gefiltert werden,
dass in einem zweiten Schritt aus den gefilterten Daten ein Kantenbild berechnet wird,
dass in einem weiteren Schritt aus diesem Kantenbild eine Auflösungspyramide errechnet und dieses in ein Kantenabstandsbild transformiert wird,
und dass das Matching dieses Kantenabstandsbildes mit einer oder mehreren Zielfunktionen mittels des Downhill-Simplex-Verfahrens erfolgt.

9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass die Auflösungspyramide mittels Tiefpass/Unterabtastung aus dem Kantenbild errechnet wird.

10. Verfahren nach einem der Ansprüche 8 oder 9, dadurch gekennzeichnet, dass die Transformation der Auflösungspyramide in das Kantenabstandsbild durch eine gewichtete Addition erfolgt.

11. Verfahren nach einem der Ansprüche 8 bis 10, dadurch gekennzeichnet, dass die Filterung an Stelle des Sobel-Filters mit einem Canny-Filter erfolgt.

12. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass der Variationsansatz auf einem Simplex-Verfahren basiert, welches auf ein aus den ursprünglichen Bilddaten der Kamera gewonnenes Hough-Bild angewandt wird.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet,
dass im Rahmen der Vorverarbeitung in einem ersten Schritt die ursprünglichen Bilddaten mittels eines Canny-Filters gefiltert werden,
dass in einem weiteren Schritt aus den gefilterten Daten ein Akkumulatorbild berechnet wird,
dass in einem weiteren Schritt aus diesem Akkumulatorbild eine Auflösungspyramide errechnet und dieses in ein Kantenabstandsbild transformiert wird,
und dass das Matching dieses Kantenabstandsbildes mit einer oder mehreren Zielfunktionen mittels des Downhill-Simplex-Verfahrens erfolgt.

14. Verfahren nach Anspruch 13, dadurch gekennzeichnet, dass das Akkumulatorbild mittels Hough-Transformation berechnet wird.

15. Verfahren nach einem der Ansprüche 13 bis 14, dadurch gekennzeichnet, dass die Auflösungspyramide mittels Tiefpass/Unterabtastung aus dem Kantenbild errechnet wird.

16. Verfahren nach einem der Ansprüche 13 bis 15, dadurch gekennzeichnet, dass die Transformation der Auflösungspyramide in das Kantenabstandsbild durch eine gewichtete Addition erfolgt.

17. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass der Variationsansatz auf einem Bipartitionsverfahren basiert, welches auf ein aus den ursprünglichen Bilddaten der Kamera gewonnenes Hough-Bild angewandt wird.

18. Verfahren nach Anspruch 17, dadurch gekennzeichnet,
dass im Rahmen der Vorverarbeitung in einem ersten Schritt die ursprünglichen Bilddaten mittels eines Canny-Filters gefiltert werden,
dass in einem weiteren Schritt aus den gefilterten Daten ein Akkumulatorbild berechnet wird,
dass in einem weiteren Schritt aus diesem Akkumulatorbild ein integriertes Akkumulatorbild errechnet wird,
und dass das Matching dieses integrierten Akkumulatorbildes mit einer oder mehreren Zielfunktionen mittels des Bipartitionsverfahrens erfolgt.

19. Verwendung des Verfahrens nach einem der Ansprüche 1 bis 18, für die Positions- und Lageschätzung von Landfahrzeugen.