DE102004049676A1

DE102004049676A1 - Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern, Anordnung zur rechnergestützten Bewegungsschätzung, Computerprogramm-Element und computerlesbares Speichermedium

Info

Publication number: DE102004049676A1
Application number: DE102004049676A
Authority: DE
Inventors: Axel Techmer
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2004-10-12
Filing date: 2004-10-12
Publication date: 2006-04-20
Also published as: WO2006039906A2; US20090052743A1; WO2006039906A3

Abstract

Bei einem Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern wird eine Bewegung dadurch bestimmt, dass, basierend auf einer Teilbewegungsschätzung, in einem zweiten digitalen Bild gegenüber einem ersten digitalen Bild eine Referenzbildstruktur aufgebaut wird und die Bewegung in einem dritten digitalen Bild gegenüber dem ersten digitalen Bild, basierend auf einer Teilbewegungsschätzung, gegenüber dem zweiten digitalen Bild und einer Teilbewegungsschätzung gegenüber der Referenzbildstruktur bestimmt wird.

Description

Die Erfindung betrifft ein Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern, eine Anordnung zur rechnergestützten Bewegungsschätzung, ein Computerprogramm-Element und ein computerlesbares Speichermedium.

Die Entwicklung im Bereich der Mobilfunktelefone und der digitalen Fotoapparate hat zusammen mit der hohen Verbreitung von Mobilfunktelefonen und der hohen Beliebtheit von digitalen Fotoapparaten dazu geführt, dass moderne Mobilfunktelefone häufig eingebaute Digitalkameras aufweisen.

Zusätzlich werden Dienste, wie beispielsweise der Multimedia-Message-Service (MMS), bereitgestellt, die es ermöglichen, mit dafür geeigneten Mobilfunktelefonen digitale Bildmitteilungen zu senden und zu empfangen.

Typischerweise sind die Komponenten von Mobilfunktelefonen, die das Aufnehmen von digitalen Bildern ermöglichen, verglichen mit den handelsüblichen Digitalkameras nicht sehr leistungsfähig.

Dies hat beispielsweise die Gründe, dass Mobilfunktelefone kostengünstig und von geringer Größe sein sollen.

Insbesondere ist die Auflösung von digitalen Bildern, die mit Mobilfunktelefonen mit eingebauter Digitalkamera aufgenommen werden können, für manche Zwecke zu gering.

Beispielsweise besteht prinzipiell die Möglichkeit, mit einem Mobilfunktelefon mit eingebauter Digitalkamera gedruckten Text zu fotografieren und in Form einer Bildmitteilung mittels eines geeigneten Dienstes, beispielsweise dem Multimedia-Message-Service (MMS), an einen anderen Mobilfunktelefonbenutzer zu versenden, doch die Auflösung der eingebauten Digitalkamera reicht dazu bei einem heutigen handelsüblichen Gerät mittlerer Preisklasse nicht aus.

Es besteht jedoch die Möglichkeit, aus einer geeigneten Folge von digitalen Bildern, die jeweils eine Szene von einer jeweiligen Aufnahmeposition aus darstellen, ein digitales Bild der Szene zu erzeugen, das eine höhere Auflösung als die der digitalen Bilder der Folge von digitalen Bildern aufweist.

Diese Möglichkeit besteht beispielsweise dann, wenn die Positionen, aus der digitale Bilder einer Folge von digitalen Bildern der Szene aufgenommen wurden, in geeigneter Weise unterschiedlich sind.

Die Aufnahmepositionen, das heißt, die Positionen, aus der die digitalen Bilder der Folge von digitalen Bildern der Szene aufgenommen wurden, können beispielsweise dann in geeigneter Weise unterschiedlich sein, wenn die Mehrzahl von digitalen Bildern erzeugt wurde, indem mehrere digitale Bilder mit einem digitalen Fotoapparat aufgenommen wurden, der von Hand über einen gedruckten Text gehalten wurde.

In diesem Fall reichen die durch die leichte Bewegung des digitalen Fotoapparats, die durch das Zittern der Hand entsteht, erzeugten Unterschiede der Aufnahmepositionen typischerweise aus, um die Erzeugung eines digitalen Bildes der Szene mit hoher Auflösung zu ermöglichen.

Dazu ist es allerdings erforderlich, dass die Unterschiede der Aufnahmepositionen berechnet wird.

Wird ein erstes digitales Bild aus einer ersten Aufnahmeposition aufgenommen und wird ein zweites digitales Bild aus einer zweiten Aufnahmeposition aufgenommen, wird ein Bildinhaltsbestandteil, beispielsweise ein Objekt der Szene, in dem ersten digitalen Bild an einer ersten Bildposition und in einer ersten Form, womit im Weiteren die geometrische Form gemeint ist, dargestellt und in dem zweiten digitalen Bild an einer zweiten Bildposition und in einer zweiten Form dargestellt.

Die Änderung der Aufnahmeposition von der ersten Aufnahmeposition zu der zweiten Aufnahmeposition spiegelt sich in der Änderung der ersten Bildposition zu der zweiten Bildposition und der ersten Form zu der zweiten Form wider.

Deshalb kann eine Berechnung einer Aufnahmepositionsänderung, die zur Erzeugung eines digitalen Bildes mit höherer Auflösung als die der digitalen Bilder der Folge digitaler Bilder erforderlich ist, durch Berechnen der Änderung der Bildposition, an denen Bildinhaltsbestandteile dargestellt werden, und der Form, in der Bildinhaltsbestandteile dargestellt werden, erfolgen.

Wird ein Bildinhaltsbestandteil in einem ersten Bild an einer ersten (Bild-)Position und in einer ersten Form dargestellt und in einem zweiten Bild an einer zweiten Position und in einer zweiten Form dargestellt, so wird im Folgenden von einer Bewegung des Bildinhaltbestandteils oder von einer Bildbewegung von dem ersten Bild zu dem zweiten Bild oder von dem zweiten Bild gegenüber dem ersten Bild gesprochen.

Es kann sich nicht nur die Position der Darstellung eines Bildinhaltsbestandteils in aufeinanderfolgenden Bildern verändern, sondern die Darstellung kann auch verzerrt werden oder ihre Größe kann sich ändern.

Außerdem kann die Darstellung eines Bildinhaltbestandteils sich von einem digitalen Bild der Folge digitaler Bilder zu einem anderen digitalen Bild der Folge digitaler Bilder ändern, beispielsweise kann sich die Helligkeit der Darstellung ändern.

Für die Bestimmung der Bildbewegung kann nur die zeitliche Änderung der Bilddaten genutzt werden. Diese zeitliche Änderung wird aber nicht allein durch die Bewegung von Objekten in der beobachteten Umgebung und durch die Eigenbewegung des Beobachters verursacht, sondern auch durch die mögliche Verformung von Objekten und durch wechselnde Beleuchtungsverhältnisse in natürlichen Szenen.

Zusätzlich müssen Störungen berücksichtigt werden, z.B. das Schwingen der Kamera oder das Rauschen der verarbeitenden Hardware.

Die reine Bildbewegung kann daher nur unter Kenntnis der zusätzlichen Einflüsse gewonnen oder aus Annahmen über sie geschätzt werden.

Für die Erzeugung eines digitalen Bildes mit höherer Auflösung als die der digitalen Bilder der Folge digitaler Bilder ist es sehr vorteilhaft, dass die Berechnung der Bewegung der Bildinhalte von einem digitalen Bild der Folge digitaler Bilder zu einem anderen digitalen Bild der Folge digitaler Bilder subpixelgenau erfolgt.

Unter Subpixelgenauigkeit ist zu verstehen, dass die Bewegung auf eine Länge genau berechnet wird, die geringer ist als der Abstand zweier örtlich benachbarter Bildpunkte der digitalen Bilder der Folge digitaler Bilder.

Verfahren zur Bewegungsschätzung und Verfahren zur subpixelgenauen Bewegungsschätzung in digitalen Bildern können außer für die oben beschriebene "Super-Resolution", also die Erzeugung von hochaufgelösten Bildern aus einer Folge von niedrig aufgelösten Bildern, ferner eingesetzt werden

– für Structure-From-Motion-Verfahren, die dazu dienen, aus einer Folge von Bildern, die von einer sich bewegenden Kamera aufgenommen wird, auf die 3D-Geometrie der Umgebung zu schließen;
– für Verfahren zur Erzeugung von Mosaikbildern, bei denen ein großes hochaufgelöstes Bild aus einzelnen kleineren Bildern zusammengefügt wird; sowie
– für Verfahren zur Videokomprimierung, bei denen mittels einer Bewegungsschätzung eine verbesserte Kompressionsrate erreicht werden kann.

Für gewisse Anwendungen, beispielsweise für die Erzeugung von Mosaikbildern, ist es neben der Bewegungsbestimmung in zwei zeitlich aufeinanderfolgenden digitalen Bildern, also der Bestimmung der Bildbewegung in einem zweiten digitalen Bild gegenüber einem ersten, dem zweiten digitalen Bild zeitlich vorhergehenden digitalen Bild, wobei das erste digitale Bild und das zweite digitale Bild einen Überlappungsbereich aufweisen, also Bildinhaltsbestandteile existieren, die in dem ersten digitalen Bild und in dem zweiten digitalen Bild angezeigt werden, ferner erforderlich, eine genaue Zuordnung nicht zeitlich aufeinanderfolgender Bilder zu einem Gesamtbild zu bestimmen. Dies wird mit Bezug auf 1 genauer erläutert.

1 zeigt ein zu scannendes Dokument 101 und ein gescanntes Dokument 102.
Das zu scannende Dokument 101 bildet in diesem Fall eine Szene, von der ein digitales Gesamtbild, das heißt das gescannte Dokument 102, erstellt werden soll. Dies erfolgt in diesem Beispiel durch die Erzeugung eines Mosaikbildes, beispielsweise da die digitale Kamera, die zur Erzeugung des digitalen Gesamtbildes verwendet wird, nicht geeignet ist, das zu scannende Dokument 101 auf einmal, das heißt durch eine einzige Aufnahme eines digitalen Bildes, zu erzeugen.
Deshalb wird anschaulich die digitale Kamera entlang eines Kamerapfades 103 über das zu scannende Dokument 101 bewegt und eine Vielzahl von digitalen Bildern mittels der digitalen Kamera aufgenommen.
Beispielsweise wird ein Ausschnitt 104 des zu scannenden Dokuments 101 aufgenommen und ein entsprechender erster Gesamtbildteil 105 erzeugt. Im weiteren Verlauf werden ein zweiter Gesamtbildteil 106 und ein dritter Gesamtbildteil 107, die entsprechende Ausschnitte des zu scannenden Dokuments 101 darstellen, erzeugt.
Um die Gesamtbildteile 105, 106, 107 so zusammenzufügen, dass ein digitales Gesamtbild des zu scannenden Dokuments 101 entsteht, ist es erforderlich, den Kamerapfad 103 zu bestimmen, das heißt anschaulich, die Zuordnung der Gesamtbildteile 105, 106, 107 zu dem zu scannenden Dokument 101 zu bestimmen, das heißt zu bestimmen, welchen Auschnitt des zu scannenden Dokuments die Gesamtbildteile 105, 106, 107 jeweils darstellen.
Beispielsweise ist es erforderlich, dass im Laufe der Erzeugung des Gesamtbildes, also des zu gescannenten Dokuments 102, festgestellt wird, dass der erste Gesamtbildteil 105 und der zweite Gesamtbildteil 107 einen Überlappungsbereich 108 aufweisen und dass dementsprechend beide einen Auschnitt des zu scannenden Dokuments 101 darstellen. Würde das nicht festgestellt werden, würde dieser Ausschnitt in dem schließlich erzeugten Gesamtbild zweimal dargestellt werden.
Anschaulich schwenkt die Position der digitalen Kamera auf die Anfangsposition zurück, sodass zwei zeitlich nicht unmittelbar aufeinanderfolgende digitale Bilder, in diesem Beispiel der erste Gesamtbildteil 105 und der zweite Gesamtbildteil 107, einen Überlappungsbereich 108 aufweisen.
Es ist somit erforderlich, eine Zuordnung der Gesamtbildteile zu dem scannenden Dokuments 101 zu bestimmen, das heißt, zu bestimmen, welchen Ausschnitt des zu scannenden Dokuments 101, oder allgemein einer darzustellenden Szene, die Gesamtbildteile darstellen. Dieser Vorgang wird als Bildregistrierung bezeichnet. Darunter ist auch zu verstehen, dass bestimmt wird, wie ein jeweiliger Ausschnitt von einem Gesamtbildteil dargestellt wird, beispielsweise rotiert oder verzerrt.
Diese Zuordnung könnte derart bestimmt werden, dass für jeweils zwei aufeinanderfolgende digitalen Bilder die relative Bildbewegung zwischen den Bildern geschätzt wird und auf diese Weise der gesamte Kamerapfad 103 bestimmt wird. Dies hat jedoch den Nachteil, dass der Fehler, der bei jeder Bewegungsschätzung zwischen zwei aufeinanderfolgenden digitalen Bildern gemacht wird, sich im Laufe der Bestimmung des Kamerapfads 103 akkumuliert. Dies ist insbesondere dann von großem Nachteil, wenn zwei zeitlich nicht unmittelbar aufeinander folgende Bilder einen Überlappungsbereich 108 aufweisen, wie es in obigem Beispiel bei dem ersten Gesamtbildteil 105 und dem dritten Gesamtbildteil 107 der Fall ist.
In diesem Fall kann das erzeugte Mosaikbild, in obigem Beispiel das gescannte Dokument 102 einen Versatz aufweisen, da anschaulich der erste Gesamtbildteil 105 und der dritte Gesamtbildteil 107 fälschlicherweise beispielsweise gegeneinander verschoben sind.
Zur Zuordnung zweier nicht zeitlich unmittelbar aufeinanderfolgender digitaler Bilder zu einem Gesamtbild eignen sich bekannte Verfahren zur Bewegungsschätzung zeitlich aufeinanderfolgender Bilder nicht. Dies hat insbesondere den Grund, dass die digitalen Bilder eventuell keinen Überlappungsbereich aufweisen und entsprechend keine Bewegung zwischen den Bildern bestimmt werden kann. Ferner beruhen Verfahren zur Bewegungsschätzung typischerweise auf der Annahme, dass nur geringe Änderungen der Bilddaten vorhanden sind. Bei digitalen Bildern, deren Aufnahmezeitpunkte verhältnismäßig lang auseinanderliegen, kann die Änderung der Bilddaten zwischen den digitalen Bildern jedoch erheblich sein.
Druckschrift [1] offenbart ein iteratives Verfahren zur Bildregistrierung. Im Rahmen des offenbarten Verfahrens wird eine grobe Bewegungsschätzung für Paare von zeitlich aufeinanderfolgenden Bildern einer Videosequenz, das heißt eine Bewegungsschätzung mit relativ geringer Genauigkeit, durchgeführt. Die grobe Bewegungsschätzung wird dazu verwendet, um eine Topologie der Nachbarschaftsbeziehungen der Bilder der Videosequenz zu bestimmen, beispielsweise wird bestimmt, dass der erste Gesamtbildteil 105 in 1 und der dritte Gesamtbildteil 107 topologische Nachbarn, das heißt in dem gescannten Dokument 102 (räumliche) Nachbarn mit einem Überlappungsbereich 108 sind. Wie erläutert entstehen solche topologischen Nachbarn, wie der erste Gesamtbildteil 105 und der zweite Gesamtbildteil 107 beispielsweise beim Zurückschwenken einer Digitalkamera, mit welcher die Bilder der Videosequenz aufgenommen werden. In einem weiteren Schritt des Verfahrens wird eine Bewegungsschätzung zwischen topologischen Nachbarn durchgeführt, sodass die für die digitalen Bilder der Videosequenz geschätzte Bildbewegung, das heißt die Zuordnung der digitalen Bilder der Videosequenz zu einem Gesamtbild, das die aufgenommene Szene darstellt, konsistent ist. Da bei diesem Verfahren zunächst die Topologie der Nachbarschaftsbeziehungen der digitalen Bilder bestimmt wird, und dies erst geschehen kann, wenn eine ausreichende Anzahl von digitalen Bildern vorhanden ist, beispielsweise mittels einer Digitalkamera aufgenommen worden sind, und anschließend erst die Bildregistrierung mit hoher Genauigkeit durchgeführt wird, kann die Bildregistrierung nur offline erstellt werden, das heißt, erst dann wenn alle (bzw. ausreichend viele) digitalen Bilder der Videosequenz bereits vorhanden sind. Insbesondere kann die Bildregistrierung nicht während der Aufnahme der Videosequenz durchgeführt werden. Ferner besteht aufgrund der zunächst durchgeführten groben Bewegungsschätzung ein Problem darin, dass bei der (anschließend an die Bestimmung der topologischen Nachbarn) mit hoher Genauigkeit durchgeführten endgültigen Bildregistrierung eine hohe Anzahl von Freiheitsgraden berücksichtigt werden müssen. Bei dem Verfahren gemäß [1] werden parametrische Bewegungsmodelle verwendet, deren Bestimmung iterativ erfolgt. Zunächst werden Translationsparameter, anschließend Parameter, die eine affine Transformation spezifizieren, und schließlich Parameter, die eine projektive Transformation spezifizieren, bestimmt. Als Maß für die Qualität der Zuordnung der digitalen Bilder zu einem Gesamtbild wird die absolute Differenz der Bildwerte, beispielsweise der Grauwerte, gewählt, die gemäß der Zuordnung den gleichen Punkt der aufgenommenen Szene darstellen, also dem gleichen Punkt des Gesamtbildes entsprechen. Konsistenz wird im Rahmen des offenbarten Verfahrens hergestellt, indem die Zuordnung zwischen topologischen Nachbarn global verifiziert wird. Dieser Schritt wird iterativ durchgeführt.
Druckschrift [2] offenbart ein Verfahren zur Bildregistrierung, bei dem ein merkmalsbasierter Ansatz verwendet wird. Als Merkmale werden signifikante Bildpunkte in den digitalen Bildern einer Videosequenz verwendet. Die räumliche Zuordnung der digitalen Bilder der Videosequenz zu einem Gesamtbild wird mittels eines statistischen Verfahrens bestimmt, wobei es nicht erforderlich ist, dass die Bilder zeitlich aufeinander folgen. Als Modell für die Zuordnung der Bilder der Videosequenz zu einem Gesamtbild wird eine projektive Transformation verwendet. Die Zuordnung wird merkmalsbasiert durchgeführt, um zeitlich nicht aufeinanderfolgende Bilder verarbeiten zu können und um somit die Zuordnung robust gegenüber Beleuchtungsunterschieden in den Bildern zu gestalten. Zur Bestimmung der Zuordnung von Merkmalen, anschaulich der Ähnlichkeit von Merkmalen, werden Intensitätsmuster der lokalen Umgebung der Merkmale verwendet. Diese lokale Umgebung ist jedoch von der gesuchten Transformation, die der gesuchten räumlichen Zuordnung entspricht, und Beleuchtungsunterschieden zwischen den digitalen Bildern abhängig.
Die in [1] und [2] offenbarten Verfahren sind beide nicht online, das heißt in Echtzeitanwendungen einsetzbar, das heißt die Bildregistrierung kann nicht während der Aufnahme einer Folge von digitalen Bildern mit einer Digitalkamera erfolgen, sondern erst dann, wenn die digitalen Bilder (oder ausreichend viele der digitalen Bilder) bereits aufgenommen wurden.
Der Erfindung liegt das Problem zu Grunde, ein einfaches und effizientes Verfahren zur Bildregistrierung bereitzustellen, das online, das heißt in Echtzeitanwendungen, einsetzbar ist.
Das Problem wird durch ein Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern, eine Anordnung zur rechnergestützten Bewegungsschätzung, ein Computerprogramm-Element und ein computerlesbares Speichermedium mit den Merkmalen gemäß den unabhängigen Patentansprüchen gelöst.
Es wird ein Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern bereitgestellt, bei dem eine erste Teilbewegungsschätzung in einem zweiten digitalen Bild gegenüber einem dem zweiten digitalen Bild zeitlich vorhergehenden ersten digitalen Bild durchgeführt wird, bei dem aus dem ersten digitalen Bild und dem zweiten digitalen Bild basierend auf der ersten Teilbewegungsschätzung eine Referenzbildstruktur aufgebaut wird, welche zumindest Merkmale aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthält und bei dem eine zweite Teilbewegungsschätzung in einem dem zweiten digitalen Bild zeitlich nachfolgenden dritten digitalen Bild gegenüber dem zweiten digitalen Bild durchgeführt wird. Eine dritte Teilbewegungsschätzung wird unter Vergleichen von Merkmalen des dritten digitalen Bildes und der in der Referenzbildstruktur enthaltenen Merkmale durchgeführt und basierend auf der dritten Teilbewegungsschätzung, der zweiten Teilbewegungsschätzung und der ersten Teilbewegungsschätzung wird die Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild bestimmt.
Es werden ferner eine Anordnung zur rechnergestützten Bewegungsschätzung, ein Computerprogramm-Element und ein computerlesbares Speichermedium gemäß dem oben beschriebenen Verfahren bereitgestellt.
Die Vielzahl zeitlich aufeinanderfolgender digitaler Bilder wird beispielsweise dadurch erzeugt, dass mittels einer Digitalkamera die Vielzahl digitaler Bilder aufgenommen wird und die Digitalkamera zwischen den Aufnahmezeitpunkten bewegt wird, so dass zwischen zwei digitalen Bildern der Vielzahl digitaler Bilder eine Bildbewegung besteht.
Wie oben erwähnt wird im Folgenden von einer Bildbewegung in einem zweiten digitalen Bild gegenüber einem ersten digitalen Bild gesprochen, wenn (mindestens) ein Bildinhaltsbestandteil in dem ersten digitalen Bild an einer ersten (Bild-)Position und/oder in einer ersten Form dargestellt und in einem zweiten Bild an einer zweiten Position und/oder in einer zweiten Form dargestellt wird. Anschaulich weisen das erste digitale Bild und das zweite digitale Bild in diesem Fall also einen gemeinsamen Bildinhaltsbestandteil auf, der gemäß der Bildbewegung unterschiedlich, beispielsweise an unterschiedlichen Positionen, dargestellt wird.
Ferner wird im Folgenden von einer Bildbewegung in einem zweiten digitalen Bild gegenüber einem ersten digitalen Bild gesprochen, wenn das erste digitale Bild einen Teil einer Szene und das zweite digitale Bild einen anderen Teil einer Szene darstellen.
Unter der Bewegungsschätzung in dem zweiten digitalen Bild gegenüber dem ersten digitalen Bild ist in diesem Fall die Zuordnung zu einem Gesamtbild der Szene gemeint, also die Bestimmung, welchen Ausschnitt des Gesamtbildes das zweite digitale Bild relativ zu dem ersten digitalen Bild darstellt und somit anschaulich, auf welche Art, das heißt gemäß welcher Bewegung, sich der dargestellte Ausschnitt von dem ersten digitalen Bild zu dem zweiten digitalen Bild in dem Gesamtbild bewegt hat.
Bei dem bereitgestellten Verfahren wird anschaulich jeweils die Bewegung zwischen zwei zeitlich aufeinanderfolgenden Bildern, die sich überlappen, bestimmt. Das oben als erstes digitales Bild bezeichnete Bild dient anschaulich als Referenzbild, also als das digitale Bild, gegenüber dem die Bewegung der anderen digitalen Bilder bestimmt wird.
Eine der Erfindung zu Grunde liegende Idee kann anschaulich darin gesehen werden, dass die Bewegung in einem digitalen Bild gegenüber einem zeitlich vorhergehenden digitalen Bild, das sich mit dem digitalen Bild überlappt und für das die Bewegung bereits bestimmt ist, zunächst durch eine erste Bewegungsschätzung der Bewegung in dem digitalen Bild gegenüber dem zeitlich vorhergehenden Bild geschätzt wird und diese erste Bewegungsschätzung anschließend durch eine zweite Bewegungsschätzung korrigiert wird, wobei im Rahmen der zweiten Bewegungsschätzung die Bewegung des gemäß der ersten Bewegungsschätzung auf ein Gesamtbild (oder eine Referenzbildstruktur) projizierten digitalen Bildes gegenüber dem Gesamtbild bestimmt wird. Das Gesamtbild enthält dabei Informationen zeitlich vorangegangener digitaler Bilder, deren Bewegung gegenüber einem Referenzbild bereits bestimmt ist.
Anschaulich wird somit das Gesamtbild sukzessive aus den digitalen Bildern aufgebaut und jedes neu hinzukommende digitale Bild an das Gesamtbild durch eine entsprechende Bewegungsschätzung, bei der anschaulich topologisch benachbarte Daten (nicht zeitlich benachbarte Daten) verwendet werden, angepasst.
Auf diese Weise wird es erreicht, dass der Fehler, der bei der Bewegungsschätzung zwischen zwei zeitlich aufeinanderfolgenden Bildern entsteht, sich nicht akkumuliert.
Es ist nicht erforderlich, dass die Referenzbildstruktur ein Gesamtbild ist. Die Referenzbildstruktur kann auch nur aus Merkmalspunkten bestehen, da diese für eine Bewegungsschätzung ausreichen.
Merkmale sind Punkte des Bildes, die in einem gewissen, vorgebar definierten Sinn signifikant sind, beispielsweise Kantenpunkte.
Ein Kantenpunkt ist ein Punkt des Bildes, an dem eine starke örtliche Helligkeitsänderung auftritt, beispielsweise ist ein Punkt, dessen linker Nachbar schwarz und dessen rechter Nachbar weiß ist, ein Kantenpunkt.
Formal wird einen Kantenpunkt als ein lokales Maximum des Bildgradienten in Gradientenrichtung bestimmt oder als Nulldurchgang der zweiten Ableitung der Bildinformation bestimmt.
Weitere Bildpunkte, die bei dem bereitgestellten Verfahren als Merkmalspunkte verwendet werden können, sind z.B.:

– Grauwertecken, das heißt Bildpunkte, die ein lokales Maximum des Bildgradienten in x- und y-Richtung aufweisen.
– Ecken in Konturverläufen, das heißt Bildpunkte an denen eine signifikante hohe Krümmung einer Kontur auftritt.
– Bildpunkte mit einer lokalen, maximalen Filterantwort bei Filterung mit örtlichen Filtermasken (z.B. Sobeloperator, Gaborfunktionen, usw.).
– Bildpunkte, die die Grenzen unterschiedlicher Bildregionen charakterisieren. Diese Bildregionen werden z.B. durch Bildsegmentierungen wie „Region Growing" oder „Watershed Segmentierung" erzeugt.
– Bildpunkte, die Schwerpunkte von Bildregionen beschreiben, wie sie beispielsweise durch die oben genannten Bildsegmentierungen erzeugt werden.

Darunter, dass die Referenzbildstruktur "zumindest Merkmale" enthält, ist insbesondere zu verstehen, dass die Referenzbildstruktur auch andere Bildinformationen und Codierungsinformationen, wie beispielsweise Farbinformationen, Helligkeitsinformationen oder Sättigungsinformationen aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthalten kann.
Beispielsweise kann die Referenzbildstruktur auch ein aus dem ersten digitalen Bild und dem zweiten digitalen Bild zusammengesetztes Mosaikbild sein.
Das bereitgestellte Verfahren zeichnet sich durch seine hohe erreichbare Genauigkeit und durch seine Einfachheit und geringen Rechenleistungsanforderungen aus.
Aufgrund der Einfachheit des bereitgestellten Verfahrens ist es möglich, das Verfahren beispielsweise in einem zukünftigen Mobilfunktelefon zu implementieren, ohne dass dieses eine leistungsfähige und kostenintensive Datenverarbeitungseinheit aufweisen muss.
Ferner ist das bereitgestellte Verfahren für eine Online-Bildregistrierung, anders ausgedrückt, für eine Berechnung in Echtzeit, einsetzbar ist, das heißt, dass die Zuordnung einer Folge digitaler Bilder zu einem Gesamtbild während der Aufnahme der Folge digitaler Bildern mit einer Digitalkamera erfolgen kann. Dadurch kann insbesondere dem Benutzer der Digitalkamera online eine Rückmeldung über den Weg der Digitalkamera, das heißt über die Bewegung der Digitalkamera gegeben werden, so dass beispielsweise vermieden werden kann, dass der Benutzer die Digitalkamera so bewegt, dass "Löcher" in einem zu erzeugenden Gesamtbild einer Szene entstehen.
Bevorzugte Weiterbildungen der Erfindung ergeben sich aus den abhängigen Ansprüchen. Die weiteren Ausgestaltungen der Erfindung, die im Zusammenhang mit dem Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern beschrieben sind, gelten sinngemäß auch für die Anordnung zur rechnergestützten Bewegungsschätzung, das Computerprogramm-Element und das computerlesbare Speichermedium.
Es ist bevorzugt, dass nach Bestimmen der Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild die Referenzbildstruktur um zumindest ein Merkmal aus dem dritten Bild ergänzt wird.
Anschaulich wird die Referenzbildstruktur im Laufe der Bewegungsschätzung um die Merkmale (zusammen mit der jeweiligen Positionsinformation), deren Positionen im letzten Schritt bestimmt wurden, ergänzt, so dass im nächsten Schritt, das heißt bei der Bestimmung der Bewegung in dem zeitlich nachfolgenden digitalen Bild gegenüber dem ersten digitalen Bild, eine "umfangreichere" Referenzbildstruktur verwendet wird.
Es ist ferner bevorzugt, dass die Bewegung in einem dem ersten digitalen Bild, dem zweiten digitalen Bild und dem dritten digitalen Bild zeitlich nachfolgenden vierten Bild gegenüber dem ersten digitalen Bild

– unter Verwendung einer weiteren Referenzbildstruktur, die zumindest Merkmale mindestens eines dem vierten Bild zeitlich vorhergehenden Bildes enthält, bestimmt wird, indem
– eine vierte Teilbewegungsschätzung in dem vierten digitalen Bild gegenüber einem dem vierten digitalen Bild zeitlich vorhergehenden weiteren digitalen Bild, in dem die Bewegung gegenüber dem ersten digitalen Bild bereits bestimmt ist, bestimmt wird
– eine fünfte Teilbewegungsschätzung unter Vergleichen von Merkmalen des vierten digitalen Bildes und der in der Referenzbildstruktur enthaltenden Merkmale durchgeführt wird;
– basierend auf der fünften Teilbewegungsschätzung, der vierten Teilbewegungsschätzung und der Bewegung des weiteren digitalen Bildes, die Bewegung bestimmt wird.

Vorzugsweise ist die weitere Referenzbildstruktur die um Merkmale aus mindestens einem dem zweiten digitalen Bild zeitlich nachfolgenden und dem vierten digitalen Bild zeitlich vorhergehenden digitalen Bild erweiterte Referenzbildstruktur.
Es ist ferner bevorzugt, dass die Teilbewegungsschätzungen merkmalsbasiert durchgeführt werden.
Die Bewegungsschätzung basierend auf Merkmalen ist insbesondere stabil gegenüber Beleuchtungsänderungen.
Es ist ferner bevorzugt, dass die Teilbewegungsschätzungen subpixelgenau durchgeführt werden.
Dies erhöht die Genauigkeit der Bewegungsschätzung.
Vorzugsweise wird im Rahmen der Teilbewegungsschätzungen jeweils ein affines Bewegungsmodell oder ein perspektivisches Bewegungsmodell bestimmt.
Mittels solcher Bewegungsmodelle kann eine hohe Genauigkeit erreicht werden, die erforderliche Rechenleistung kann jedoch gering gehalten werden.
Es können jedoch auch beliebige andere Bewegungsmodelle verwendet werden, insbesondere solche, die sich durch Polynome oder rationale Funktionen darstellen lassen.
Es ist ferner bevorzugt, dass die erste Teilbewegungsschätzung, die zweite Teilbewegungsschätzung und die dritte Teilbewegungsschätzung mittels desselben Verfahrens zur Bewegungsschätzung in zwei zeitlich aufeinanderfolgenden Bildern durchgeführt werden.
Dies erhöht die Einfachheit des Verfahrens, da nicht unterschiedliche Verfahren für die Teilbewegungsschätzungen verwendet werden müssen.
Es ist ferner bevorzugt, dass zur Durchführung der dritten Teilbewegungsschätzung Merkmale auf die Referenzbildstruktur basierend auf der ersten Teilbewegungsschätzung und der zweiten Teilbewegungsschätzung abgebildet werden und die dritte Teilbewegungsschätzung durch Schätzung der Bewegung der abgebildeten Merkmale gegenüber der in der Referenzbildstruktur enthaltenen Merkmale durchgeführt wird.
Die Verwendung von Merkmalen im Rahmen der dritten Teilbewegungsschätzung hat den Vorteil, dass Merkmale ohne Verlust an Genauigkeit auf die Referenzbildstruktur abgebildet werden können.
Vorzugsweise wird das Verfahren zur Bewegungsschätzung im Rahmen einer Erzeugung eines Mosaikbilds, der Kalibrierung einer Kamera, eines Super-Resolution-Verfahrens, einer Videokomprimierung oder einer dreidimensionalen Schätzung durchgeführt wird.
Ausführungsbeispiele der Erfindung sind in den Figuren dargestellt und werden im Weiteren näher erläutert.
1 zeigt ein zu scannendes Dokument und ein gescanntes Dokument.
2 zeigt eine Anordnung gemäß einem Ausführungsbeispiel der Erfindung.
3 zeigt eine gedruckte Vorlage gemäß einem Ausführungsbeispiel der Erfindung.
4 zeigt ein Gesamtbild, ein erstes digitales Bild und ein zweites digitales Bild gemäß einem Ausführungsbeispiel der Erfindung.
5 zeigt ein Ablaufdiagramm gemäß einem Ausführungsbeispiel der Erfindung.
6 illustriert die Bewegungsschätzung zwischen zwei zeitlich aufeinanderfolgenden Bildern.
7 zeigt ein Ablaufdiagramm gemäß einem Ausführungsbeispiel der Erfindung.
8 illustriert die Bildregistrierung gemäß einem Ausführungsbeispiel der Erfindung.
9 zeigt ein Flussdiagramm eines Verfahren gemäß einem Ausführungsbeispiel der Erfindung;
10 zeigt ein Flussdiagramm einer Bestimmung einer Translation gemäß einem Ausführungsbeispiel der Erfindung;
11 zeigt ein Flussdiagramm einer Bestimmung einer affinen Bewegung gemäß einem Ausführungsbeispiel der Erfindung;
12 zeigt ein Flussdiagramm eines Verfahrens gemäß einem weiteren Ausführungsbeispiel der Erfindung;
13 zeigt ein Flussdiagramm einer Kantendetektion gemäß einem Ausführungsbeispiel der Erfindung;
14 zeigt ein Flussdiagramm einer subpixelgenauen Kantendetektion gemäß einem Ausführungsbeispiel der Erfindung;
15 zeigt ein Flussdiagramm eines Verfahrens gemäß einem weiteren Ausführungsbeispiel der Erfindung;
16 zeigt ein Flussdiagramm einer Bestimmung einer perspektivischen Bewegung gemäß einem Ausführungsbeispiel der Erfindung;
2 zeigt eine Anordnung 200 gemäß einem Ausführungsbeispiel der Erfindung.
Mittels einer Digitalkamera 201, die in diesem Beispiel in einem Mobilfunk-Teilnehmergerät enthalten ist, werden digitale Bilder einer Szene, von der ein Mosaikbild, das heißt ein Gesamtbild, erstellt werden soll, aufgenommen. In diesem Beispiel wird die Digitalkamera 201 über einen gedruckten Text 202, von dem ein Mosaikbild erstellt werden soll, von einem Benutzer gehalten.
Je nach Halteposition der Digitalkamera 201 wird mittels der Digitalkamera 201 ein Ausschnitt 203 des gedruckten Textes 202 aufgenommen, in diesem Beispiel die obere Hälfte des gedruckten Textes 202. Die Digitalkamera 201 ist mittels einer Videoschnittstelle 204 mit einem Prozessor 205 und einem Speicher 206 gekoppelt.
Die mittels der Digitalkamera 201 aufgenommenen digitalen Bilder, die jeweils einen Teil des gedruckten Textes 202 darstellen, können mittels des Prozessors 205 verarbeitet und mittels des Speichers 206 gespeichert werden. In diesem Beispiel verarbeitet der Prozessor 205 die digitalen Bilder derart, dass ein Mosaikbild des gedruckten Textes 202 erstellt wird. Der Prozessor 205 ist ferner mit Eingabe/Ausgabevorrichtungen 207 gekoppelt, beispielsweise mit einem Bildschirm, mittels welchem das gerade aufgenommene digitale Bild oder auch das fertige Mosaikbild angezeigt wird.
Die Video-Schnittstelle 204, der Prozessor 205, der Speicher 206 und die Eingabe-/Ausgabevorrichtungen 207 sind in einem Ausführungsbeispiel in dem Mobilfunk-Teilnehmergerät angeordnet, das auch die Digitalkamera 201 enthält.
Da der Ausschnitt 203 des gedruckten Textes 202 typischerweise nicht der gesamte gedruckte Text 202 ist, wird die Digitalkamera 201 von dem Benutzer über dem gedruckten Text 202 bewegt, damit ein Gesamtbild des gedruckten Textes 202 erstellt werden kann. Dies wird im Folgenden mit Bezug auf 3 erläutert.
3 zeigt eine gedruckte Vorlage 300 gemäß einem Ausführungsbeispiel der Erfindung.
Die gedruckte Vorlage 300 entspricht dem gedruckten Text 202. Zu einem ersten Zeitpunkt wird mittels der Digitalkamera 201 ein erstes digitales Bild aufgenommen, das einen ersten Ausschnitt 301 der gedruckten Vorlage 300 darstellt. In diesem Beispiel ist der erste Ausschnitt 301 nicht annähernd halb so groß wie die gedruckte Vorlage 300 sondern nur ungefähr ein Viertel so groß (im Gegensatz zu der Darstellung in 1).
Anschließend wird die Digitalkamera 201 entlang eines Kameraweges 302 bewegt und eine Vielzahl von digitalen Bildern aufgenommen, die entsprechend der jeweiligen Position der Digitalkamera 201 einen entsprechenden Ausschnitt der gedruckten Vorlage 300 darstellen. Nach einer Zeit t wird mittels der Digitalkamera 201, die sich inzwischen entlang des Kameraweges 302 bewegt hat, ein zweites digitales Bild aufgenommen, dass einen zweiten Ausschnitt 303 der gedruckten Vorlage 300 darstellt. Der erste Ausschnitt 301 und der zweite Ausschnitt 303 überlappen sich in einem Überlappungsbereich 304.
Die gedruckte Vorlage 300 befindet sich in der sogenannten Abbildungsebene. Im Falle einer dreidimensionalen Szene ist die Abbildungsebene die Ebene, auf die die dreidimensionale Szene projiziert wird, so dass das Gesamtbild entsteht, das aus einer Mehrzahl von Bildern erzeugt werden soll, bzw. dem eine Mehrzahl von Bildern zugeordnet werden sollen.
Die Bewegung von Bildausschnitten in der Abbildungsebene wird im Folgenden mit Bezug auf 4 genauer erläutert.
4 zeigt eine Gesamtbild 401, welches wie erwähnt in der Abbildungsebene liegt, ein erstes digitales Bild 402 und ein zweites digitales Bild 403 gemäß einem Ausführungsbeispiel der Erfindung.
Von dem Gesamtbild 401 soll ein digitales Mosaikbild erstellt werden.
Dementsprechend werden mehrere digitale Bilder des Gesamtbilds 401 mittels der Digitalkamera aufgenommen. Zu einem ersten Zeitpunkt wird ein erstes digitales Bild (nicht gezeigt) aufgenommen, das einen ersten Ausschnitt 404 des Gesamtbilds 401 darstellt.
Anschließend wird die Digitalkamera bewegt und zum Zeitpunkt t wird ein zweites digitales Bild 402 aufgenommen, das einen zweiten Ausschnitt 405 des Gesamtbilds 401 darstellt.
Nach einer weiteren Bewegung der Digitalkamera wird zum Zeitpunkt t+1 ein drittes digitales Bild 403 aufgenommen, das einen dritten Ausschnitt 406 des Gesamtbilds 401 darstellt.
In diesem Beispiel stellen das zweite digitale Bild 402 und das dritte digitale Bild 403 ein Objekt 407 (oder einen Bestandteil) der Szene dar, die von dem Gesamtbild 401 dargestellt wird. Die Darstellung des Objekts 407 ist entsprechend der Bewegung der Digitalkamera vom Zeitpunkt t zum Zeitpunkt t+1 in dem dritten digitalen Bild 403 jedoch gegenüber dem zweiten digitalen Bild verschoben und/oder rotiert und/oder skaliert. In diesem Beispiel ist das Objekt 407 in dem dritten digitalen Bild 403 gegenüber dem zweiten digitalen Bild 402 weiter links oben dargestellt, also nach links oben verschoben.
Zur Erzeugung eines Mosaikbilds der Gesamtbild 401 wird nun eine Bildregistrierung der digitalen Bilder, unter anderem des zweiten digitalen Bildes 402 und des dritten digitalen Bildes 403, durchgeführt, das heißt, die Zuordnung der digitalen Bilder zu dem Gesamtbild 401 wird bestimmt.
Anschaulich entspricht der Bewegung der Digitalkamera zum Zeitpunkt t zum Zeitpunkt t+1 einer entsprechenden Bewegung des zweiten Ausschnitts 405 zu dem dritten Ausschnitt 406 in einer Abbildungsebene. Entsprechend wird im Folgenden von einer Bewegung des Ausschnitts, beispielsweise von dem zweiten Ausschnitt 405 zu dem dritten Ausschnitt 406, gesprochen.
Das Gesamtbild ist mit einem ersten Koordinatensystem 408 versehen. Entsprechend ist das zweite digitale Bild 402 mit einem zweiten (lokalen) Koordinatensystem 409 versehen und das dritte digitale Bild 403 ist mit einem dritten (lokalen) Koordinatensystem 410 versehen.
Im Folgenden wird ein Verfahren zur Bildregistrierung gemäß einem Ausführungsbeispiel der Erfindung erläutert, wobei bei diesem Ausführungsbeispiel angenommen wird, dass die Bewegung der Ausschnitte des Gesamtbilds 401, die von den aufgenommenen digitalen Bildern dargestellt werden, durch ein affines Bewegungsmodel approximiert werden kann.
In dem folgenden Ausführungsbeispiel wird angenommen, dass die Digitalkamera nur so bewegt wird, dass nur Rotationen und/oder Skalierungen und/oder Translationen in der Bildebene entstehen, das heißt das zwei Ausschnitte des Gesamtbildes 401, die von jeweils einem digitalen Bild dargestellt werden, sich nur durch eine Rotation und/oder eine Skalierung und/oder eine Translation unterscheiden können.
Weiter unten wird eine weitere Ausführungsform der Erfindung erläutert, bei der diese Einschränkung nicht gilt.
5 zeigt ein Ablaufdiagramm 500 gemäß einem Ausführungsbeispiel der Erfindung.
Das im Folgenden erläuterte Verfahren dient zur Bildregistrierung einer Mehrzahl digitaler Bilder. Wie oben mit Bezug auf 4 erläutert zeigen die digitalen Bilder jeweils einen Ausschnitt eines Gesamtbildes, das eine Szene darstellt. Das Gesamtbild ist eine Projektion der Szene auf eine Abbildungsebene. Das Gesamtbild, das beispielsweise im Rahmen der Erzeugung eines Mosaikbildes erstellt werden soll, wird im Folgenden auch als Referenzbild bezeichnet.
Ein digitales Bild der Folge digitaler Bilder stellt wie erwähnt einen Ausschnitt des Gesamtbildes dar. Der Ausschnitt des Gesamtbildes hat eine bestimmte Lage (Position, Größe und Orientierung) in dem Gesamtbild, die durch die Angabe der Eckpunkte des Ausschnitts mittels eines Koordinatensystem des Gesamtbildes angegeben kann. Beispielsweise wird ein Eckpunkt des t-ten Ausschnitts, das heißt des Ausschnitts, der durch das digitale Bild, das zum Zeitpunkt t aufgenommen wurde, dargestellt wird, auf folgende Weise angegeben:
Analog werden die weiteren Eckpunkte des t-ten Abschnitts angegeben.
Ein Eckpunkt des t+1-ten Ausschnitts wird beispielsweise auf folgende Weise angegeben:
Analog werden die weiteren Eckpunkte des t+1-ten Ausschnitts angegeben.
Die Angabe der Eckpunkte erfolgt mittels homogener Koordinaten, das heißt mittels einer zusätzlichen z-Koordinate, die stets 1 ist, sodass eine effiziente Matrixschreibweise ermöglicht wird. Die jeweils erste Koordinate in Gleichung (1) und Gleichung (2) gibt die Lage des jeweiligen Eckpunkts bezüglich einer ersten Koordinatenachse des Koordinatensystems des Gesamtbildes (x-Achse) an und die jeweils zweite Koordinate in Gleichung (1) und Gleichung (2) gibt die Lage des jeweiligen Eckpunkts bezüglich einer zweiten Koordinatenachse des Koordinatensystems des Gesamtbildes (y-Achse) an.
Wie erwähnt führt eine Bewegung der Digitalkamera, mittels welcher die Folge digitaler Bilder aufgenommen wird, zu einer entsprechenden Bewegung des dargestellten Ausschnitts des Gesamtbildes, wobei mit dem dargestellten Ausschnitt zum Zeitpunkt t der Ausschnitt gemeint ist, der von dem zum Zeitpunkt t aufgenommenen digitalen Bild angezeigt wird. In diesem Ausführungsbeispiel wird für die Bewegung der Digitalkamera bzw. für die Bewegung des dargestellten Ausschnitts des Gesamtbildes ein affines Bewegungsmodell verwendet. Beispielsweise gilt zwischen einem ersten Eckpunkt des t-ten Ausschnitts, der gemäß Gleichung (1) gegeben ist, und einem ersten Eckpunkt des t+1-ten Ausschnitts, der durch Gleichung (2) gegeben ist, der Zusammenhang W t+1 = MW t (3)wobei
Die Parameter t_x und t_y sind Translationsparameter, das heißt sie spezifizieren den Translationsanteil der Bewegung, die durch M gegeben ist, und die Parameter m₀₀, ..., m₁₁ sind Rotationsparameter und Skalierungsparameter, das heißt bestimmen die Rotationseigenschaften und Skalierungseigenschaften der affinen Abbildung, die die durch M spezifizierte affine Bewegung angibt.
Entsprechendes gilt für die weiteren Eckpunkte des t-ten Ausschnitts und des t+1-ten Ausschnitts. Im weiteren wird stillschweigend stets vorausgesetzt, dass Operationen, die für einen Eckpunkt eines Ausschnitts durchgeführt werden, analog für die weiteren Eckpunkte des Ausschnitts durchgeführt werden.
Bei dem in S dargestellten Ablauf wird vorausgesetzt, dass der t+1-ten Ausschnitt registriert werden soll, das heißt, dass die Koordinaten der Eckpunkte des t+1-ten Ausschnitts in dem Koordinatensystem des Gesamtbildes bestimmt werden sollen. Es wird angenommen, dass alle vorhergehenden Ausschnitte, das heißt die Ausschnitte, die in digitalen Bildern dargestellt sind, die vor dem Zeitpunkt t+1 aufgenommen wurden, bereits registriert sind. Insbesondere sind die Koordinaten der Eckpunkte des t-ten Ausschnitts bekannt. Dementsprechend ist eine Matrix M _t bekannt, die die Eckpunkte eines 0-ten Ausschnitts auf die Eckpunkte des t-ten Ausschnitts gemäß folgender Gleichung abbilden: W t = M t W 0 (5)
Die Matrix M _t gibt die affine Bewegung an, gemäß welcher der dargestellte Ausschnitt sich vom 0-ten Ausschnitt vom Zeitpunkt 0 bis zum Zeitpunkt t zum t-ten Ausschnitt bewegt hat. Der 0-te Ausschnitt entspricht beispielsweise dem ersten Ausschnitt 404, der t-te Ausschnitt entspricht beispielsweise dem zweiten Ausschnitt 405 und der t+1-te Ausschnitt entspricht beispielsweise dem zweiten Ausschnitt 406 in 4.
Wie erwähnt seien nun die bis zum Zeitpunkt t aufgenommenen digitalen Bilder bereits registriert und ein zum Zeitpunkt t+1 aufgenommenes digitales Bild sei zu registrieren. Die Codierungsinformation des t+1-ten digitalen Bildes, das heißt des digitalen Bildes, das zum Zeitpunkt t+1 aufgenommen wurde, sei durch die Funktion I(u, v, t+1) gegeben, wobei u und v die Koordinaten eines Bildpunkts des t+1-ten digitalen Bildes sind, das heißt dass I(u, v, t+1) die Codierungsinformation des Punktes mit den Koordinaten (u, v) (in dem Koordinatensystem des t+1-ten digitalen Bildes) in dem t+1-ten digitalen Bild angibt.
In Schritt 501 wird eine Merkmalsdetektion zur Bestimmung von Merkmalen des t+1-ten digitalen Bildes durchgeführt. Diese Merkmalsdetektion erfolgt vorzugsweise subpixelgenau.
Im Schritt 502 wird eine Bewegungsschätzung zur Bestimmung der Bildbewegung des t+1-ten digitalen Bildes gegenüber dem t-ten digitalen Bild durchgeführt. Dies geschieht vorzugsweise merkmalsbasiert, das heißt unter Verwendung von Merkmalspunkten des t-ten digitalen Bildes und des t+1-ten digitalen Bildes. Die geschätzte Bewegung sei durch eine Matrix M _I gegeben. Das heißt, dass sich ein Punkt P _t mit den Koordinaten (u, v) in dem t-ten digitalen Bild zu dem Punkt P _t+1 mit den Koordinaten (u_t+1, v_t+1) in dem t+1-ten digitalen Bild bewegt hat, das heißt es gilt folgende Gleichung:
M _I gibt somit anschaulich die Bewegung von dem t-ten digitalen Bild zu dem t+1-ten digitalen Bild an. Aus M _I und M _t wird nun M _t+1 bestimmt, das anschaulich den Kameraweg zum Zeitpunkt t+1 angibt, das heißt die Lage des dargestellten Ausschnitts zum Zeitpunkt t+1. Für einen Eckpunkt des t+1-ten Ausschnitts gilt dementsprechend die Formel W t+1 = M t+1 W 0. (7)
Ist W ₀ identisch mit dem Ursprung des Koordinatensystems in dem Gesamtbild, so beschreibt Gleichung (7) eine Koordinatentransformation zwischen dem Koordinatensystem des t+1-ten digitalen Bildes und dem Koordinatensystem des Gesamtbildes. Anschaulich werden durch die Koordinatentransformation Punkte aus der Bildebene, das heißt in diesem Fall aus dem t+1-ten digitalen Bild, in die Abbildungsebene übertragen. Analoges gilt für M _t und somit gilt B = M t P t (8)wobei B die Koordinaten im Koordinatensystem des Gesamtbildes des Punktes enthält, dessen Koordinaten in dem Koordinatensystem des t-ten digitalen Bildes durch den Vektor P _t gegeben sind. Entsprechend gilt P t = M –1t B (9)
Analog gilt für Punkte des t+1-ten digitalen Bildes B = M t+1 P t+1 (10)und P t+1 = M –1t+1 B (11)
Kombination von Gleichung (6) und Gleichung (9) liefert P _t+1 = M _I P _t = M I M –1t B. (12)
Somit kann die Matrix M _t+1 aus der Matrix M _t und der zwischen dem t-ten digitalen Bild und dem t+1-ten digitalen Bild bestimmten Bildbewegung berechnet werden, anschaulich kann der Kameraweg iterativ berechnet werden. Es gilt M –1t+1 = M I M –1t . (13)
Wird der Kameraweg gemäß Gleichung (13) iterativ für alle Punkte t bestimmt, akkumulieren sich jedoch die Fehler, die bei der Bildbewegung zwischen zwei zeitlich aufeinanderfolgenden Bildern gemacht werden.
Deshalb wird in Schritt 503 die gemäß Gleichung (14) gegebene Matrix bestimmt und als Näherung des durch die Matrix M_t+1 gegebenen Kamerawegs (Bewegung des dargestellten Ausschnitts) vom Zeitpunkt t zum Zeitpunkt t+1 betrachtet. Diese Näherung wird mit
bezeichnet. Entsprechend gilt für
die Gleichung M t+1 = M t M –1I (14)
Analog zu Gleichung (10) gilt die Gleichung
wobei
die Schätzung der Koordinaten im Koordinatensystem des Gesamtbildes von dem Punkt, dessen Koordinaten im Koordinatensystem des t+1-ten digitalen Bildes durch den Vektor P_t+1 gegeben sind, gemäß des genäherten Kamerawegs, der durch
spezifiziert wird, ist.
In Schritt 504 werden die Koordinaten von Merkmalspunkten des t+1-ten digitalen Bildes in dem Koordinatensystem des Gesamtbildes gemäß Gleichung (16) und somit gemäß der durch
gegebenen Näherung des Kamerawegs bestimmt.
In Schritt 505 wird eine Bewegungsschätzung in der Abbildungsebene durchgeführt. Aus vorhergehenden Registrierungsschritten sind Teile des Gesamtbildes bereits bekannt, da die Lage von durch die dem t+1-ten digitalen Bild vorhergehenden digitalen Bildern dargestellten Ausschnitten bereits bestimmt worden ist. Da aus Schritt 504 die Koordinaten von Merkmalspunkten des t+1-ten digitalen Bildes in dem Gesamtbild bekannt sind, kann nun basierend auf diesen Merkmalspunkten eine merkmalsbasierte Bewegungsschätzung zwischen dem gemäß der geschätzten Kamerabewegung, die durch
angegeben wird, auf das Gesamtbild abgebildeten t+1-ten digitalen Bild und dem Gesamtbild durchgeführt werden.
Anschaulich wird der Ausschnitt des Gesamtbildes, der durch das t+1-te digitale Bild dargestellt wird und dessen Lage in dem Gesamtbild durch den geschätzten Kameraweg angegeben wird, an die aus der vorhergehenden Registrierung von digitalen Bildern gekannten Inhalte des Gesamtbildes angepasst.
Dies wird vorzugsweise mittels einer subpixelgenauen, merkmalsbasierten Bewegungsschätzung durchgeführt, wie sie unten erläutert wird.
Die geschätzte Bewegung in der Abbildungsebene zwischen dem Gesamtbild und dem gemäß
in die Abbildungsebene abgebildeten t+1-ten digitalen Bild sei durch die Matrix M_B gegeben. Somit gilt der Zusammenhang
wobei B die Koordinaten im Koordinatensystem des Gesamtbildes des Punktes enthält, dessen Koordinaten im Koordinatensystem des t+1-ten digitalen Bildes durch den Vektor P_t+1 gegeben sind.
In Schritt 506 wird die Schätzung des Kameraweges vom Zeitpunkt t zum Zeitpunkt t+1 verbessert.
Dies kann unter Verwendung von M _b geschehen, da gilt:
woraus folgt
M_t+1 gibt den Kameraweg vom Zeitpunkt t zum Zeitpunkt t+1 im Vergleich zu
mit verbesserter Genauigkeit an.
Mittels der Matrix M_t+1 können die Koordinaten im Koordinatensystem des Gesamtbildes der Punkte des t+1-ten digitalen Bildes gemäß B t+1 = M t+1 P t+1 (20)bestimmt werden.
In Schritt 507 werden die Koordinaten der Merkmalspunkte des t+1-ten digitalen Bildes im Koordinatensystem des Gesamtbildes bestimmt.
In Schritt 508 werden alle Merkmalspunkte des t+1-ten digitalen Bildes, die in dem Gesamtbild noch nicht enthalten sind, gemäß der in Schritt 507 bestimmten Koordinaten in das Gesamtbild integriert.
Anschaulich werden zur Bestimmung des Kamerawegs somit nur Merkmalspunkte verwendet und dementsprechend in dem Gesamtbild nur Merkmalspunkte bzw. die Koordinaten von Merkmalspunkten aufgenommen und erst nach Bestimmung des Kamerawegs für alle aufgenommenen digitalen Bilder das Gesamtbild basierend auf der bestimmten Bildregistrierung aufgebaut.
In dieser Ausführungsform wird angenommen, dass zu Beginn der Bildregistrierung die Abbildungsebene und die Bildebene identisch sind, das heißt, dass das erste digitale Bild der Folge digitaler Bilder einen Ausschnitt des Gesamtbildes identisch, das heißt ohne Verzerrungen, Rotationen, Skalierungen und Verschiebungen darstellt. Somit gilt
und entsprechend B = P 0 (22)für alle Punkte des ersten digitalen Bildes.
6 illustriert die Bewegungsschätzung zwischen zwei zeitlich aufeinanderfolgenden Bildern.
Ein erstes digitales Bild 601, das dem Zeitpunkt t zugeordnet ist und ein zweites digitales Bild 602, das dem Zeitpunkt t+1 zugeordnet ist, stellen in diesem Beispiel ein Objekt 603 dar.
Das Objekt 603 befindet sich in den ersten digitalen Bild an einer anderen Position als in dem zweiten digitalen Bild. Anschaulich wird nun ein Bewegungsmodell bestimmt, das die Position des Objekts 603 in dem ersten digitalen Bild 601 auf die Position des Objekts 603 in dem zweiten digitalen Bild abbildet, wie es in der mittleren 604 durch Überlagerung des Objekt 603 an der Position, die es in dem ersten digitalen Bild hat, und des Objekt 603 an der Position, die es in dem zweiten digitalen Bild 602 hat, dargestellt ist.
Verfahren zur Bewegungsschätzung zwischen zwei zeitliche aufeinander folgenden digitalen Bildern werden weiter unten erläutert.
Im Folgenden wird mit Bezug auf 7 und B ein weiteres Ausführungsbeispiel der Erfindung erläutert.
7 zeigt ein Ablaufdiagramm 700 gemäß einem Ausführungsbeispiel der Erfindung.
Die Ablaufsschritte 701 bis 704 und 706 bis 708 werden analog zu den Ablaufschritten 501 bis 504 und 506 bis 508, wie oben mit Bezug auf 5 erläutert, durchgeführt.
An Stelle der Bewegungsschätzung in der Abbildungsebene zur Bestimmung der Matrix Mg in Schritt 505 werden in dieser Ausführungsform jedoch zwei Ablaufschritte 709 und 705 durchgeführt.
In 709 wird zunächst der Überlappungsbereich zwischen den gemäß
in die Abbildungsebene, das heißt auf das Gesamtbild, projizierten t+1-te digitalen Bild und dem Gesamtbild bestimmt. Anschaulich wird somit der Ausschnitt des Gesamtbildes bestimmt, der dem durch
in die Abbildungsebene projizierten t+1-ten digitalen Bild entspricht.
In Schritt 705 wird die Bewegungsschätzung zwischen dem Überlappungsbereich und dem mittels
projizierten t+1-ten digitalen Bild bestimmt. Das Ergebnis dieser Bewegungsschätzung sei durch M_B gegeben.
Anschaulich wird somit das durch
in die Abbildungsebene projizierte t+1-te digitale Bild nicht mit dem vollständigen Gesamtbild zur Korrektur des Kamerawegs von t bis t+1 verglichen, sondern nur innerhalb des relevanten Überlappungsbereichs. Diese Ausführungsform ist deshalb gegenüber der mit Bezug auf 5 erläuterten Ausführungsform weniger rechenintensiv und weniger speicherintensiv.
Da der Überlappungsbereich sich an einer beliebigen Position im Gesamtbild befinden kann, stimmt das lokale Koordinatensystem des Überlappungsbereichs nicht mit dem Koordinatensystem des Gesamtbildes überein. Anschaulich wird somit beim Ausschneiden der Punkte des Gesamtbildes des Überlappungsbereich eine Koordinatentransformation durchgeführt. Hat beispielsweise der Überlappungsbereich die Form eines Rechtecks und der linke obere Eckpunkt hat bestimmte Koordinaten im Koordinatensystem des Gesamtbildes, so könnte der linke obere Eckpunkt im lokalen Koordinatensystem des Überlappungsbereichs die Koordinaten (0,0) haben.
Die Koordinatentransformation zwischen dem Koordinatensystem des Gesamtbildes und dem Koordinatensystem des Überlappungsbereichs kann durch eine Translation modelliert werden. Die Translation sei durch einen Translationsvektor
gegeben.
Zur Berücksichtigung der Koordinatentransformation werden für den Vektor
der wie oben beschrieben eine Schätzung der Koordinaten eines Punktes in dem Gesamtbild angibt, und den Vektor B, der wie oben beschrieben die Koordinaten eines Punktes im Koordinatensystem des Gesamtbilds angibt, Substitutionen gemäß B' = B + T Ü (24)bzw.
eingeführt. Analog zu Gleichung (17) gilt
Somit gilt
wobei
und
Mittels der abkürzenden Schreibweise
ergibt sich somit
wobei
Analog zur Gleichung (19) wird nun M _t+1 gemäß
bestimmt. Zum besseren Verständnis wird der in 7 dargestellte Ablauf im Folgenden mit Bezug auf 8 anschaulich erläutert.
8 illustriert die Bildregistrierung gemäß einem Ausführungsbeispiel der Erfindung.
In 8 sind das t-te digitale Bild 801 und das t+1-te digitale Bild 802 dargestellt.
Entsprechend Schritt 702 wird in Schritt 803 eine Bewegungsschätzung in der Bildebene durchgeführt, das heißt die Bildbewegung zwischen dem t-ten digitalen Bild 801 und dem t+1-ten digitalen Bild 802 bestimmt.
Daraus wird entsprechend Schritt 703 eine Schätzung des Kamerawegs und somit die Position des von de t+1-ten digitalen Bild 802 dargestellten Ausschnitts des Gesamtbildes in der Abbildungsebene 804 bestimmt. Entsprechend Schritt 704 werden in Schritt 808 die Merkmalspunkte des t+1-ten digitalen Bildes 802 in die Abbildungsebene 804 projiziert.
Der von dem t+1-ten digitalen Bild 802 dargestellte Ausschnitt des Gesamtbildes habe eine Position 805. Entsprechend Schritt 709 wird eine in Schritt 806 eine Bestimmung des Überlappungsbereichs durchgeführt.
Entsprechend Schritt 705 wird in Schritt 807 eine Bewegungsschätzung im Überlappungsbereich durchgeführt.
Basierend auf dem Ergebnis dieser Bewegungsschätzung wird in Schritt 809 eine gegenüber der geschätzten Kamerabewegung korrigierte Kamerabewegung bestimmt und gemäß der korrigierten Kamerabewegung die Merkmalspunkte des t+1-ten digitalen Bildes 802 in die Abbildungsebene projiziert und Merkmale, die in dem im Laufe der bisherigen Bildregistrierung erzeugten Gesamtbild noch nicht enthalten sind, in das Gesamtbild integriert.
Bei den im Rahmen der oben erläuterten Ausführungsbeispielen durchgeführten Bewegungsschätzungen wurden zur Modellierung der geschätzten Bewegungen affine Bewegungsmodelle verwendet. Da mittels einer Digitalkamera perspektivische Abbildungen von dreidimensionalen Szenen auf eine zweidimensionale Bildebene erzeugt werden, sind affine Modelle jedoch in manchen Fällen nicht ausreichend, und es kann bei Verwendung von affinen Modellen nur eine geringe Genauigkeit erreicht werden.
In einer weiteren Ausführungsform werden deshalb perspektivische Bewegungsmodelle verwendet, die es erlauben, die Abbildungseigenschaften einer idealen Lochpunkt-Kamera zu modellieren.
Die im Weiteren erläutere Ausführungsform unterscheidet sich von den oben erläuterten Ausführungsformeln nur darin, dass ein perspektivisches Bewegungsmodell anstatt eines affinen Bewegungsmodells verwendet wird.
Bei Verwendung eines perspektivischen Bewegungsmodells anstatt eines affinen Bewegungsmodells, das durch eine Matrix M der in Gleichung (4) gegebenen Form gegeben ist, hat Gleichung (3) die Form
wobei M nun nicht die Matrix ist, die eine affine Bewegung spezifiziert, sondern der Parametervektor des perspektivischen Bewegungsmodells ist und die Form M = [m1, m2, m3, m4, m5, m6, m7, m8, m9] (35)hat. Dementsprechend gilt analog zu Gleichung (5) die Gleichung
und analog zu Gleichung (7) die Gleichung:
Wie in den oben beschriebenen Ausführungsformen wird eine Bewegungsschätzung zwischen dem t-ten digitalen Bild und dem t+1-ten digitalen Bild durchgeführt, sodass analog zu Gleichung (6) gilt:
M ~_t+1 wird nun so bestimmt, dass analog zu Gleichung (12) gilt
Dabei geben M –1 / t und
die zu M_t bzw.
inversen Bewegungen an. Für zwei Punkte P₁, P₂ und eine Matrix M, die eine perspektivische Bewegung angibt, gilt also P 2 = Mot(P 1, M) ⇔ P 1 = Mot(P 2, M –1) (40)
Der Vektor M ^–1 kann direkt aus M bestimmt werden. Das verwendete Bewegungsmodell hat acht Freiheitsgrade (anschaulich kann eine der Komponenten des durch Gleichung 35 gegebenen Vektors M auf 1 nominiert werden). Werden vier paarweise linear unabhängige Punkte in die linke Gleichung von (40) eingesetzt, so erhält man vier Gleichungen gemäß P 2,i = Mot (P 1,i, M) mit i = 1, 2, 3, 4 (41)wobei der Punkt P _1,i (für i = 1, 2, 3, 4) durch die durch M gegebene perspektivische Bewegung auf den Punkt P _2,i abgebildet wird. Dadurch erhält man ein lineares Gleichungssystem mit acht Gleichungen gemäß
Durch analoges Vorgehen kann eine Matrix M₃, für die P 3 = Mot (P 2, M 2) = Mot (Mot(P 1, M 1), M 2) = Mot(P 1, M 3) (43) gilt, bestimmt werden. Insbesondere kann aus Gleichung (39) die Matrix
auf diese Weise bestimmt werden, also indem durch Einsetzen einer Menge von Punktepaaren jeweils bestehend aus einem Punkt des t-ten digitalen Bildes und des t+1-ten digitalen Bildes eine ausreichende Anzahl von linearen Gleichungen erzeugt werden. Punktepaare, die zum Einsetzen in Gleichung (39) verwendet werden können, sind solche, die demselben Punkt im Gesamtbild entsprechen und können beispielsweise mittels dem unten beschriebenen Verfahren zur Bewegungsschätzung zweier zeitlich aufeinander folgender digitaler Bilder bestimmt werden.
Analog zu den oben beschriebenen Ausführungsformen wird basierend auf der geschätzten Kamerabewegung, die durch
gegeben ist, und einer Bewegungsschätzung in der Abbildungsebene eine korrigierte Kamerabewegung bestimmt, die durch M _t+1 gegeben ist, und mittels welcher analog zu Gleichung (20) gilt
Ein Vergleich der beschriebenen Ausführungsform, bei der ein perspektivisches Modell verwendet wird, mit einem entsprechenden Verfahren zur Bildregistrierung, bei dem allerdings auf eine Bewegungsschätzung in der Abbildungsebene und eine entsprechende Korrektur des Kamerawegs verzichtet wird, zeigt, das sich bei dem herkömmlichen Verfahren die bei der Bewegungsschätzung zweier zeitlich aufeinanderfolgender digitaler Bilder gemachten Fehler akkumulieren, während das bei der oben beschriebenen Ausführungsform nicht der Fall ist, und deshalb der Gesamtfehler erheblich niedriger ist.
Besonders bei der Bestimmung von Bewegungsparametern, die einen Translationsanteil der berechneten Kamerabewegung beschreiben, wird mittels der beschriebenen Ausführungsform eine sehr hohe Genauigkeit erreicht.
Im Weiteren wird ein Verfahren zur Bewegungsschätzung in zwei zeitlich aufeinanderfolgenden Bildern erläutert, das im Rahmen der obigen Ausführungsbeispiele verwendet werden kann.
Anschaulich erfolgt bei dem im Weiteren beschriebenen Verfahren die Bewegungsbestimmung durch einen Vergleich von Merkmalspositionen.
Im Weiteren ist unter Bild stets ein digitales Bild zu verstehen.
Anschaulich gesprochen werden in zwei aufeinanderfolgenden Bildern Merkmale bestimmt und eine Zuordnung bestimmt, indem versucht wird, zu bestimmen, welchen Merkmalen im zweiten Bild die Merkmale im ersten Bild jeweils entsprechen. Wurde bestimmt, welchem Merkmal im zweiten Bild ein Merkmal im ersten Bild entspricht, so wird das so interpretiert, dass das Merkmal im ersten Bild zu der Position des Merkmals im zweiten Bild gewandert ist und diese Positionsänderung, die einer Bildbewegung des Merkmals entspricht, wird berechnet. Darüber hinaus wird an Hand der Positionsänderungen der einzelnen Merkmale, ein einheitliches Bewegungsmodell berechnet, das die Positionsänderungen möglichst gut modelliert.
Anschaulich wird somit eine Zuordnung fest gewählt und ein Bewegungsmodell bestimmt, das alle Merkmalspunkte des ersten Bildes auf die ihnen jeweils zugeordneten Mermalspunkte des zweiten Bildes in einem gewissen Sinne, beispielsweise in einem Least-Squares-Sinne wie unten beschrieben, am besten abbildet.
Insbesondere wird nicht für alle Werte der Parameter des Bewegungsmodells ein Abstand zwischen der mittels des Bewegungsmodells abgebildeten Menge der Merkmalspunkte des ersten Bildes und der Menge der Merkmalspunkte des zweiten Bildes berechnet. Somit wird ein geringer Rechenaufwand bei dem bereitgestellten Verfahrens erreicht.
Merkmale sind Punkte des Bildes, die in einem gewissen, vorgegebenen Sinn signifikant sind, beispielsweise Kantenpunkte.
Ein Kantenpunkt ist ein Punkt des Bildes, an dem eine starke örtliche Helligkeitsänderung auftritt, beispielsweise ist ein Punkt, dessen linker Nachbar schwarz und dessen rechter Nachbar weiß ist, ein Kantenpunkt.
Formal wird einen Kantenpunkt als ein lokales Maximum des Bildgradienten in Gradientenrichtung bestimmt oder als Nulldurchgang der zweiten Ableitung der Bildinformation bestimmt.
Weitere Bildpunkte, die bei dem bereitgestellten Verfahren als Merkmalspunkte verwendet werden können, sind z.B.:

Die Positionen einer Menge von Merkmalen bestimmt eine zweidimensionale räumliche Merkmalsverteilung eines Bildes.
Bei der Bestimmung der Bewegung von einem ersten Bild und einem zweiten Bild gemäß dem bereitgestellten Verfahren wird anschaulich die räumliche Merkmalsverteilung des ersten Bildes mit der räumlichen Merkmalsverteilung des zweiten Bildes verglichen.
Im Gegensatz zu einem Verfahren, das auf dem optischen Fluss basiert, wird bei dem bereitgestellten Verfahren die Bewegung nicht basierend auf der Helligkeitsverteilung der Bilder, sondern basierend auf der räumlichen Verteilung von signifikanten Punkten berechnet.
9 zeigt ein Flussdiagramm 900 eines Verfahrens gemäß einem Ausführungsbeispiel der Erfindung.
Das im Weiteren erläuterte Verfahren dient zur Berechnung der Bewegung in einer Folge von digitalen Bildern, die mittels einer Digitalkamera aufgenommen worden sind. Jedes Bild der Folge von digitalen Bildern wird durch eine Funktion I(x, y, t) ausgedrückt, wobei t der Zeitpunkt ist, zu dem das Bild aufgenommen wurde und I(x, y, t) die Codierungsinformation des Bildes an der Stelle (x, y), das zum Zeitpunkt t aufgenommen wurde, angibt.
In diesem Ausführungsbeispiel wird angenommen, dass keine Beleuchtungsschwankungen oder Störungen in der verarbeitenden Hardware bei der Aufnahme der digitalen Bilder aufgetreten sind.
Unter dieser Annahme gilt für zwei in der Folge von digitalen Bildern aufeinander folgende digitale Bilder mit der Codierungsinformation I(x, y, t) bzw. I(x, y, t + dt) die Gleichung I(x + dx, y + dy, t + dt) = I(x, y, t) (45)
Hierbei ist dt der Unterschied der Aufnahmezeitpunkte der beiden in der Folge von digitalen Bildern aufeinander folgende digitale Bilder.
Unter der Annahme, dass nur ein Verursacher für Bewegung existiert, kann Gleichung (45) auch durch I(x, y, t + dt) = I(Motion(x, y, t), t) (46)formuliert werden, wobei Motion(x, y, t) die Bewegung der Bildpunkte beschreibt.
Die Bildbewegung kann zum Beispiel mittels einer affinen Transformation
modelliert werden.
In Schritt 901 des Flussdiagramms 900 wird ein Bild der Folge digitaler Bilder bereitgestellt.
Es wird angenommen, dass das digitale Bild zu einem Zeitpunkt t+1 mittels der Digitalkamera aufgenommen wurde.
Ein Bild, dass zu einem Zeitpunkt τ aufgenommen wurde, wird im Folgenden kurz als Bild τ bezeichnet.
Somit wird beispielsweise das Bild, dass zu einem Zeitpunkt t+1 mittels der Digitalkamera aufgenommen wurde als Bild t+1 bezeichnet.
Ferner wird angenommen, dass ein digitales Bild, dass zu einem Zeitpunkt t aufgenommen wurde, vorliegt, und dass die Bildbewegung von dem Bild t zu dem Bild t+1 bestimmt werden soll.
In Schritt 902 wird die Merkmalsdetektion, das heißt die Bestimmung von Merkmalspunkten und Merkmalspositionen, vorbereitet.
Beispielsweise wird dazu das digitale Bild mittels eines Filters vorverarbeitet.
In Schritt 902 wird eine Merkmalsdetektion mit niedriger Schwelle durchgeführt.
Das bedeutet, dass bei der Merkmalsdetektion jedem Bildpunkt ein Wert zugeordnet wird, und ein Bildpunkt nur dann zu der Menge der Merkmalspunkte gehört, wenn der ihm zugeordnete Wert über einem gewissen Schwellwert liegt.
Bei der in Schritt 902 durchgeführten Merkmalsdetektion ist dieser Schwellwert niedrig, wobei unter "niedrig" zu verstehen ist, dass der Wert kleiner ist als der Schwellwert der in Schritt 905 durchgeführten Merkmalsdetektion.
Eine Merkmalsdetektion gemäß einer bevorzugten Ausführungsform der Erfindung wird weiter unten beschrieben.
Die bei der in Schritt 902 durchgeführten Merkmalsdetektion bestimmte Menge von Merkmalspunkten wird mit P K / t+1 bezeichnet: PKt+1 = {[Pt+1,x(k), Pt+1,y(k)]T, 0 ≤ k ≤ K – 1} (48)
Dabei bezeichnet P _t+1 = [P_t+1,x(k), P_t+1,y(k)]^T einen Merkmalspunkt mit dem Index k aus der Merkmalspunktmenge P K / t+1 in Vektorschreibweise.
Die Bildinformationen des Bildes t wird analog zu oben als Funktion I(x, y, t) geschrieben.
In Schritt 903 wird eine globale Translation bestimmt.
Dieser Schritt wird unten mit Bezug auf 10 beschrieben.
In Schritt 904 werden affine Bewegungsparameter bestimmt.
Dieser Schritt wird unten mit Bezug auf 11 beschrieben.
In Schritt 905 wird eine Merkmalsdetektion mit hoher Schwelle durchgeführt.
Das heißt, dass bei der in Schritt 905 durchgeführten Merkmalsdetektion der Schwellwert hoch ist, wobei unter hoch zu verstehen ist, dass der Wert größer ist als der Schwellwert der in Schritt 902 durchgeführten Merkmalsdetektion mit niedrigem Schwellwert.
Wie erwähnt wird eine Merkmalsdetektion gemäß einer bevorzugten Ausführungsform der Erfindung weiter unten beschrieben.
Die bei der in Schritt 905 durchgeführten Merkmalsdetektion bestimmte Menge von Merkmalspunkten wird mit O N / t+1 bezeichnet: ONt+1 = {[Ot+1(n), Ot+1,y(n)]T, 0 ≤ n ≤ N – 1} (49)
Dabei bezeichnet O _t+1(n) = [O_t+1,x(n), O_t+1,y(n)]^T den n-ten Merkmalspunkt der Menge O N / t+1 in Vektorschreibweise.
Die in Schritt 905 durchgeführte Merkmalsdetektion mit hoher Schwelle dient nicht zur Bestimmung der Bewegung von Bild t zu Bild t+1, sondern dient zur Vorbereitung der Bewegungsbestimmung von Bild t+1 zu Bild t+2.
Dementsprechend wird im Folgenden angenommen, dass eine Merkmalsdetektion mit hoher Schwelle für das Bild t analog zu Schritt 905 durchgeführt wurde, bei der eine Merkmalspunktmenge ONt = {[Ot,x(n), Ot,y(n)]T, 0 ≤ n ≤ N – 1} (50) bestimmt wurde.
Unter Verwendung der Merkmalspunktmenge O N / t werden Schritt 903 und Schritt 904 durchgeführt.
In Schritt 903 und Schritt 904 wird eine geeignete affine Bewegung, die durch eine Matrix
und einen Translationsvektor
bestimmt ist, berechnet, so dass für
die Beziehung ÔNt+1 ⊂ PNt+1 (52)gilt, wobei Ô N / t+1 die Menge der Spaltenvektoren der Matrix Ô N / t+1 ist.
Hierbei bezeichnet O N / t die Matrix, deren Spaltenvektoren die Vektoren der Menge O N / t sind.
Dies kann so interpretiert werden, dass eine Bewegung gesucht wird, die die Merkmalspunkte des Bildes t auf Merkmalspunkte des Bildes t+1 abbildet.
Die Bestimmung der affinen Bewegung wird dadurch ermöglicht, dass für die Detektion der Merkmalspunkte aus der Menge O N / t eine höhere Schwelle verwendet wird als für die Detektion der Merkmalspunkte aus der Menge P K / t+1.
Wird für beide Detektion dieselbe Schwelle verwendet, besteht die Möglichkeit, dass einige die den Merkmalspunkten aus O N / t entsprechenden Bildpunkte zum Zeitpunkt t+1 nicht als Merkmalspunkte detektiert werden.
Unter dem einem Merkmalspunkt in Bild t entsprechenden Bildpunkt in Bild t+1 ist der Bildpunkt zu verstehen, an dem der Bildinhaltsbestandteil, der durch den Merkmalspunkt in Bild t dargestellt wird, in Bild t+1 aufgrund der Bildbewegung dargestellt wird.
Im Allgemeinen können
nicht so bestimmt werden, dass (52) gilt, deshalb werden
so bestimmt, dass O N / t durch die affine Bewegung in einem gewissen Sinne, der unten definiert wird, möglichst gut auf P K / t+1 abgebildet wird.
In dieser Ausführungsform werden für ein Maß die Güte der Abbildung von O N / t auf P K / t+1 die minimalen Distanzen der Punkte aus Ô N / t zu der Menge P K / t+1 verwendet.
Die minimale Distanz
eines Punkts (x, y) von der Menge P K / t+1 ist definiert durch
Die minimalen Distanzen der Punkte aus O N / t von der Menge P K / t+1 können beispielsweise effizient mit Hilfe einer Distanztransformation, welche eine morphologische Operation ist, bestimmt werden (siehe [3]).
Bei einer Distanztransformation, wie sie in [3] beschrieben ist, wird aus einem Bild, in dem Merkmalspunkte gekennzeichnet sind, ein Distanzbild erzeugt, bei dem der Bildwert an einem Punkt die minimale Distanz zu einem Merkmalspunkt angibt.
Anschaulich gibt
für einen Punkt den Abstand zu dem Punkt aus P K / t+1 an, zu dem der Punkt (x, y) den kleinsten Abstand hat.
Die Bestimmung der affinen Bewegung erfolgt in den zwei Schritten 903 und 904.
Die in (51) formulierte affine Bewegung wird dazu in eine globale Translation und eine anschließende affine Bewegung zerlegt:
Der Translationsvektor
bestimmt die globale Translation und die Matrix
und der Translationsvektor
bestimmen die anschließende affine Bewegung.
Im Folgenden wird der Schritt 903 mit Bezug auf 10 erläutert.
10 zeigt ein Flussdiagramm 1000 einer Bestimmung einer Translation gemäß einem Ausführungsbeispiel der Erfindung. In Schritt 903, der durch Schritt 1001 des Flussdiagramms 1000 dargestellt ist, wird unter Verwendung von P K / t+1 und O N / t der Translationsvektor so bestimmt, dass
Der Schritt 1001 weist Schritte 1002, 1003, 1004 und 1005 auf.
Zur Bestimmung von
so dass Gleichung (55) gilt, wird in Schritt 1002 ein Wert T 0 / y in einem Intervall [T ^ 0 / y0, T ^ 0 / y1] gewählt.
In Schritt 1003 wird ein Wert T 0 / x in einem Intervall [T ^ 0 / x0, T ^ 0 / x1] gewählt.
In Schritt 1004 wird der Wert sum (T 0 / x, T 0 / y) gemäß der Formel
für die gewählten Werte T 0 / x und T 0 / y bestimmt.
Die Schritte 1002 bis 1004 werden für alle gewählten Paare von Werten T 0 / y ∊ [T ^ 0 / y0, T ^ 0 / y1] und [T ^ 0 / x0, T ^ 0 / x1] durchgeführt.
In Schritt 1005 werden
so bestimmt, dass sum
gleich dem Minimum aller in Schritt 1004 berechneten Summen ist.
Der Translationsvektor
ist gegeben durch
Im Folgenden wird der Schritt 904 mit Bezug auf 11 erläutert.
11 zeigt ein Flussdiagramm 1100 einer Bestimmung einer affinen Bewegung gemäß einem Ausführungsbeispiel der Erfindung.
Der Schritt 904, der durch Schritt 1101 des Flussdiagramms 1100 dargestellt ist, weist Schritte 1102 bis 1108 auf.
In Schritt 1102 wird die Matrix
berechnet, deren Spaltenvektoren eine Menge von Punkten O' N / t bilden.
Für jeden Punkt (x, y) aus der Menge O' N / t wird ein Distanzvektor
bestimmt.
Der Distanzvektor wird so bestimmt, dass er von dem Punkt (x, y) zu dem Punkt aus P K / t+1 zeigt, zu dem der Abstand des Punkts (x, y) minimal ist.
Die Bestimmung erfolgt somit gemäß der Gleichungen
Die Distanzvektoren können auch gemäß folgender Formel aus den minimalen Distanzen, die beispielsweise in Form eins Distanzbildes vorliegen, berechnet werden:
In den Schritten 1103 bis 1108 wird unter der Annahme, dass für die Merkmalspunktmenge O N / t+1 die Approximation
gilt, die affine Bewegung durch eine Kleinste-Quadrate-Schätzung bestimmt, das heißt, dass die Matrix
und der Translationsvektor
so bestimmt werden, dass der Term
minimal ist, was genau dann der Fall ist, wenn der Term
minimal ist.
Hierbei ist mit O'_t(n) und
die n-te Spalte der jeweiligen Matrix bezeichnet.
Die Verwendung der minimalen Distanzen in Gleichung (64) kann anschaulich so interpretiert werden, dass davon ausgegangen wird, dass ein Merkmalspunkt in Bild t dem Merkmalspunkt in Bild t+1 entspricht, der ihm am nächsten liegt, dass sich der Merkmalspunkt in Bild t also zu dem nächstliegenden Merkmalspunkt in Bild t+1 bewegt hat.
Die Kleinste-Quadrate-Schätzung wird in dieser Ausführungsform iteriert.
Dies erfolgt gemäß folgender Zerlegung der affinen Bewegung:
In Gleichung (65) wurde die zeitliche Abhängigkeit zur vereinfachten Schreibweise weggelassen.
Da heißt, dass L affine Bewegungen bestimmt werden, wobei die L-te affine Bewegung derart bestimmt wird, dass sie die Merkmalspunktmenge, die durch sukzessive Anwendung der 1-ten, 2-ten, ..., und der (l-2)-ten affinen Bewegung auf die Merkmalspunktmenge O' N / t entsteht, möglichst gut, in oben beschriebenen Sinne der Kleinste-Quadrate-Schätzung, auf die Menge P K / t+1 abbildet.
Die l-te affine Bewegung ist durch die Matrix
und den Translationsvektor
bestimmt.
Am Ende von Schritt 1102 wird der Iterationsindex l auf Null gesetzt und mit Schritt 1103 fortgefahren.
In Schritt 1103 wird der Wert von l um eins erhöht und überprüft, ob der Iterationsindex l zwischen 1 und L liegt.
Ist dies der Fall wird mit Schritt 1104 fortgefahren.
In Schritt 1104 wird die Merkmalspunktmenge O'^l, die durch die durch sukzessive Anwendung der 1-ten, 2-ten, ..., und der (l-2)-ten affinen Bewegung auf die Merkmalspunktmenge O' N / t entsteht, bestimmt.
In Schritt 1105 werden Distanzvektoren analog zu den Gleichungen (59) und (60) und eine Merkmalspunktmenge analog zu (62) bestimmt.
In Schritt 1106 wird eine Matrix
und ein Translationsvektor
berechnet, die die l-te affine Bewegung bestimmen.
Außerdem wird ein quadratischer Fehler analog zu (63) berechnet.
In Schritt 1107 wird überprüft, ob der berechnete quadratische Fehler größer ist als der in der letzten Iteration berechnete quadratische Fehler.
Ist dies der Fall, wird in Schritt 1108 der Iterationsindex l auf den Wert L gesetzt und anschließend mit Schritt 1103 fortgefahren.
Ist dies nicht der Fall wird mit Schritt 1103 fortgefahren.
Wird in Schritt 1108 der Iterationsindex auf den Wert L gesetzt, so wird in Schritt 1103 der Wert von l auf den Wert L+1 erhöht und die Iteration beendet.
In einer bevorzugten Ausführungsform werden die Schritte 902 bis 905 des in 9 dargestellten Flussdiagramms 900 mit Subpixelgenauigkeit durchgeführt.
12 zeigt ein Flussdiagramm 1200 eines Verfahrens gemäß einem weiteren Ausführungsbeispiel der Erfindung.
In dieser Ausführungsform wird ein digitales Bild, das zum Zeitpunkt 0 aufgenommen wurde, als Referenzbild, das im Folgenden als Referenzfenster bezeichnet wird, verwendet.
Die Codierungsinformation 1202 des Referenzfensters 1201 wird im Folgenden analog zu Obigem als Funktion I(x, y, 1) geschrieben.
In Schritt 1203 wird eine Kantendetektion mit Subpixelauflösung im Referenzfenster 1201 durchgeführt.
Eine Verfahren zur Kantendetektion mit Subpixelauflösung gemäß einer Ausführungsform wird unten mit Bezug auf 14 beschrieben.
In Schritt 1204 wird aus dem Ergebnis der Kantendetektion eine Menge von Merkmalspunkten O^N des Referenzfensters bestimmt.
Beispielsweise werden die besonders signifikanten Kantenpunkte als Merkmalspunkte bestimmt.
Anschließend wird der Zeitindex t auf den Wert null gesetzt.
In Schritt 1205 wird der Zeitindex t um eins erhöht und anschließend geprüft ob der Wert von t zwischen eins und T liegt.
Ist dies der Fall, wird mit Schritt 1206 fortgefahren.
Ist dies nicht der Fall, wird das Verfahren mit Schritt 1210 beendet.
In Schritt 1206 wird unter Verwendung der Codierungsinformation 1211 des t-ten Bildes, das analog zu oben als Bild t bezeichnet wird, eine Kantendetektion mit Subpixelauflösung durchgeführt.
Dies liefert, wie unten genauer beschrieben wird, ein t-tes Kantenbild, das im Folgenden als Kantenbild t bezeichnet wird, mit der Codierungsinformation e_h(x, y, t) zu dem Bild t.
Die Codierungsinformation e_h(x, y, t) des Kantenbildes t wird unten mit Bezug auf 13 und 14 genauer erläutert.
In Schritt 1207 wird eine Distanztransformation mit Subpixelauflösung des Kantenbildes t durchgeführt.
Das heißt, aus dem Kantenbild t wird ein Distanzbild erzeugt, bei dem der Bildwert an einem Punkt die minimale Distanz zu einem Kantenpunkt angibt.
Die Kantenpunkte des Bildes t sind die Punkte des Kantenbildes t, bei der die Codierungsinformation e_h(x, y, t) einen bestimmten Wert aufweist.
Dies wird unten genauer erläutert.
Die Distanztransformation erfolgt analog zu der mit Bezug auf 9, 10 und 11 beschriebenen Ausführungsform.
Dabei wird verwendet, dass die Positionen der Kantenpunkte des Bildes t in Schritt 1206 subpixelgenau bestimmt wurden.
Die Distanzvektoren werden subpixelgenau berechnet.
In Schritt 1208 wird analog zu dem Schritt 903 des mit Bezug auf 9, 10 und 11 beschriebenen Ausführungsbeispiels eine globale Translation bestimmt.
Die Bestimmung der globalen Translation erfolgt subpixelgenau.
In dem Verarbeitungsblock 1209 werden Parameter eines affinen Bewegungsmodells berechnet.
Die Berechnung erfolgt analog zu dem in 11 dargestellten Flussdiagramm, das oben erläutert wurde.
Die Berechnung der Parameter eines affinen Bewegungsmodells erfolgt subpixelgenau.
Nach Beendigung des Verarbeitungsblocks 1209 wird mit Schritt 1205 fortgefahren.
Insbesondere wird das Verfahren beendet, wenn t = T, das heißt, wenn die Bewegung des Bildinhalts zwischen dem Referenzfenster und dem T-ten Bild bestimmt wurde.
13 zeigt ein Flussdiagramm 1300 einer Kantendetektion gemäß einem Ausführungsbeispiel der Erfindung.
Die Bestimmung von Kanten stellt für die Bewegungschätzung einen sinnvollen Kompromiss bezüglich der Konzentration auf signifikante Bildpunkte bei der Bewegungsbestimmung und dem Erhalt möglichst vieler Informationen dar.
Kanten werden üblicherweise als lokale Maxima in der örtlichen Ableitung der Bildintensität bestimmt. Das hier eingesetzte Verfahren basiert auf den Arbeiten von Canny [4].
In Schritt 1302 wird ein digitales Bild und bei dem Kanten detektiert werden sollen, mittels eines Gaussfilters gefiltert.
Dies erfolgt durch Faltung der Codierungsinformation 1301 des Bildes, die durch die Funktion I(x, y) gegeben ist, mit einer Gaussmaske, die mit gmask bezeichnet ist.
In Schritt 1303 wird die partielle Ableitung nach der Variable x der Funktion I_g(x, y) bestimmt.
In Schritt 1304 wird die partielle Ableitung nach der Variable x der Funktion I_g(x, y) bestimmt.
In Schritt 1305 wird entschieden, ob an einem Punkt (x, y) ein Kantenpunkt vorliegt.
Dazu müssen zwei Bedingungen an dem Punkt (x, y) erfüllt sein.
Die erste Bedingung ist, dass die Summe der Quadrate der beiden in Schritt 1303 und Schritt 1304 bestimmten partiellen Ableitungen an dem Punkt (x, y), die mit I_g,x,y(x, y) bezeichnet wird, über einem Schwellwert liegt.
Die zweite Bedingung ist, dass I_g,x,y(x, y) an dem Punkt (x, y) ein lokales Maximum aufweist.
Das Ergebnis der Kantendetektion wird in einem Kantenbild, dessen Codierungsinformation 1306 als Funktion geschrieben wird und mit e(x, y) bezeichnet wird, zusammengefasst.
Die Funktion e(x, y) weist an einer Stelle (x, y) den Wert I_g,x,y(x, y) auf, falls in Schritt 1305 entschieden (x, y) worden ist, dass (x, y) ein Kantenpunkt ist und weist an allen anderen Stellen den Wert Null auf.
Der in 13 illustrierte Ansatz zur Detektion von Grauwertecken bietet die Möglichkeit, die Anzahl und die Signifikanz der Kanten durch eine Schwelle zu steuern.
Damit kann gewährleistet werden, dass O N / t+1 in P K / t+1 enthalten ist.
Die Punktmengen O N / t+1 und P K / t+1 können aus dem Kantenbild, das die Codierungsinformation e(x, y) aufweist, ausgelesen werden.
Wird das in 13 dargestellte Verfahren bei dem in 9 dargestellten Ausführungsbeispiel verwendet, so entspricht zur Erzeugung von P K / t+1 aus e(x, y) die in Schritt 1305 verwendete Schwelle der in Schritt 905 verwendeten "niedrigen Schwelle".
Zur Bestimmung von O N / t+1 wird unter Verwendung der in Schritt 905 verwendeten "hohen Schwelle" eine Auswahl aus den durch e(x, y) gegebenen Kantenpunkten getroffen.
Dies erfolgt beispielsweise analog zur Überprüfung der oben erläuterten ersten Bedingung aus Schritt 1305.
14 zeigt ein Flussdiagramm 1400 einer subpixelgenauen Kantendetektion gemäß einem Ausführungsbeispiel der Erfindung.
Die Schritte 1402, 1403 und 1404 unterscheiden sich nicht von den Schritten 1302, 1303 und 1304 des in 13 illustrierten Kantendetektionsverfahrens.
Um eine Detektion mit Subpixelgenauigkeit zu erreichen, weist das Flussdiagramm 1400 einen Schritt 1405 auf.
In Schritt 1405 werden die in Schritt 1403 und Schritt 1404 bestimmten partiellen Ableitungen in x-Richtung und y-Richtung, die als örtlichen Gradientenbilder mit Codierungsinformation I_gx(x, y) und I_gy(x, y) bezeichnet werden, auf eine höhere Bildauflösung extrapoliert.
Die fehlenden Bildwerte werden durch eine bikubische Interpolation bestimmt. Das Verfahren der bikubischen Interpolation wird z.B. in [5] erläutert.
Die Codierungsinformation der resultierenden hochaufgelösten Gradientenbilder werden mit I_hgx(x, y) und I_hgy(x, y) bezeichnet.
Der Schritt 1406 erfolgt analog zu Schritt 1305 unter Verwendung der hochaufgelösten Kantenbilder.
Die Codierungsinformation 1407 des in Schritt 1406 erzeugten Kantenbilds wird mit e_h(x, y) bezeichnet, wobei der Index h anzeigen soll, dass das Kantenbild ebenfalls hochaufgelöst ist.
Die in Schritt 1407 erzeugte Funktion e_h(x, y) weist im Unterschied zu der in Schritt 1406 in diesem Ausführungsbeispiel nicht den Wert I_g,x,y(x, y) auf, falls entschieden worden ist, dass an der Stelle (x, y) ein Kantenpunkt vorliegt, sondern den Wert 1.
15 zeigt ein Flussdiagramm 1500 eines Verfahrens gemäß einem weiteren Ausführungsbeispiel der Erfindung.
Dieses Ausführungsbeispiel unterscheidet sich von dem mit Bezug auf 9 erläuterten darin, dass statt eines affinen Bewegungsmodells, wie es beispielsweise durch Gleichung (47) gegeben ist, ein perspektivisches Bewegungsmodell verwendet wird.
Da eine Kamera eine perspektivische Abbildung der dreidimensionalen Umgebung auf eine zweidimensionale Bildebene erzeugt, liefert ein affines Modell nur eine Approximation der eigentlichen Bildbewegung, die durch eine sich bewegende Kamera erzeugt wird.
Wird eine ideale Kamera, d.h. ohne Linsenverzerrungen angenommen, kann die Bewegung durch ein perspektivisches Bewegungsmodell beschrieben werden, wie es beispielsweise durch die nachstehende Gleichung gegeben ist.
M bezeichnet den Parametervektor für das perspektivische Bewegungsmodell. M = [a1, a2, a3, b1, b2, b3, n1, n2, n3] (67)
Die Verfahrensschritte des Flussdiagramms 1500 sind analog zu denen des Flussdiagramms 900, es wird deshalb im Weiteren nur auf die Unterschiede eingegangen.
Insbesondere liegt wie bei dem mit Bezug auf 9 beschriebenen Verfahren eine Merkmalspunktmenge ONt = {[Otx(n), Oty(n)]T, 0 ≤ n ≤ N – 1 (68)vor.
Diese Merkmalspunktmenge repräsentiert einen Bildausschnitt oder ein Objekt des Bildes, das zum Zeitpunkt t aufgenommen wurde.
Gesucht wird nun die Bewegung, die O N / t auf die entsprechenden Punkte des Bildes, dass zum Zeitpunkt t+1 aufgenommen wurde, abbildet.
Im Unterschied zu dem mit Bezug auf 9 beschriebenen Verfahren werden in Schritt 1504 die Parameter eines perspektivischen Bewegungsmodells bestimmt.
Das Bewegungsmodell nach Gleichung (67) weist neun Parameter aber nur acht Freiheitsgrade auf, wie aus der nachstehenden Gleichung ersichtlich ist.
Die Parameter des perspektivischen Modells können wie die Parameter des affinen Modells mittels einer Kleinste-Quadrate-Schätzung bestimmt werden, indem der Term
minimiert wird.
Hierbei ist O' analog zu der mit Bezug auf 9 beschriebenen Ausführungsform gemäß Gleichung (58) definiert. O'_x(n) bezeichnet die erste Komponente der n-ten Spalte der Matrix O' und O'_y(n) bezeichnet die zweite Komponente der n-ten Spalte der Matrix O'.
Der gemäß Gleichung (60) berechnete minimale Distanzvektor
wird abkürzend als [d_n,xd_n,y]^T bezeichnet.
Der Zeitindex t wurde zur einfacheren Darstellung in Formel (70) weggelassen.
Analog zu dem mit Bezug auf 9 beschriebenen Verfahren, bei dem ein affines Bewegungsmodell verwendet wird, kann auch für das perspektivische mittels iterativem Vorgehen die Genauigkeit verbessert werden.
16 zeigt ein Flussdiagramm 1600 einer Bestimmung einer perspektivischen Bewegung gemäß einem Ausführungsbeispiel der Erfindung.
Der Schritt 1601 entspricht dem Schritt 1504 des in 15 dargestellten Flussdiagramms 1500.
Die Schritte 1602 bis 1608 sind analog zu den Schritten 1102 bis 1108 des in 11 dargestellten Flussdiagramms 1100.
Der Unterschied liegt in der Berechnung des Fehlers E_pers, der in Schritt 1606 gemäß Gleichung (70) berechnet wird.
In diesem Dokument sind folgende Veröffentlichungen zitiert:

[1] H. S. Sawhney, St. Hsu, R Kumar, Robust Video Mosaicing through Topology Inference and Local to Global Alignment, ECCV'98, pp. 103-118, 1998
[2] D. Capel, Image Mosaicing and Super-resolution, Springer Verlag, 2003
[3] G. Borgefors, Distance Transformation in Digital Images, Computer Vision, Graphics and Image Processing, 34, pp. 344-371, 1986
[4] J. Canny, A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 1986
[5] William H. Press, et al., Numerical Recipies in C, ISBN: 0-521-41508-5, Cambrige University Press

101: zu scannendes Dokument
102: gescanntes Dokument
103: Kamerapfad
104: Ausschnitt
105-107: Gesamtbildteile
108: Überlappungsbereich
200: Anordnung
201: Digitalkamera
202: gedruckter Text
203: Ausschnitt
204: Videoschnittstelle
205: Prozessor
206: Speicher
207: Eingabe/Ausgabevorrichtungen
300: gedruckte Vorlage
301: Ausschnitt
302: Kameraweg
303: Ausschnitt
304: Überlappungsbereich
401: Gesamtbild
402,403: digitale Bilder
404-406: Ausschnitte
407: Objekt
408-410: Koordinatensysteme
500: Flussdiagramm
501-508: Verarbeitungsschritte
601,602: digitale Bilder
603: Objekt
604: Abbildung
700: Flussdiagramm
701-709: Verarbeitungsschritte
801: t-tes digitales Bild
802: t+1-tes digitales Bild
803: Verarbeitungsschritt
804: Abbildungsebene
805: Position
806-809: Verarbeitungsschritte
900: Flussdiagramm
901-905: Verarbeitungsschritte
1000: Flussdiagramm
1001-1005: Verarbeitungsschritte
1100: Flussdiagramm
1101-1108: Verarbeitungsschritte
1200: Flussdiagramm
1201: Referenzfenster
1202: Codierungsinformation
1201-1210: Verarbeitungsschritte
1211: Codierungsinformation
1300: Flussdiagramm
1301: Codierungsinformation
1302-1305: Verarbeitungsschritte
1306: Codierungsinformation
1400: Flussdiagramm
1401: Codierungsinformation
1402-1406: Verarbeitungsschritte
1407: Codierungsinformation
1500: Flussdiagramm
1501-1505: Verarbeitungsschritte
1600: Flussdiagramm
1601-1608: Verarbeitungsschritte

Claims

Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern – bei dem eine erste Teilbewegungsschätzung in einem zweiten digitalen Bild gegenüber einem dem zweiten digitalen Bild zeitlich vorhergehenden ersten digitalen Bild durchgeführt wird; – bei dem aus dem ersten digitalen Bild und dem zweiten digitalen Bild basierend auf der ersten Teilbewegungsschätzung eine Referenzbildstruktur aufgebaut wird, welche zumindest Merkmale aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthält; – bei dem eine zweite Teilbewegungsschätzung in einem dem zweiten digitalen Bild zeitlich nachfolgenden dritten digitalen Bild gegenüber dem zweiten digitalen Bild durchgeführt wird; – bei dem eine dritte Teilbewegungsschätzung unter Vergleichen von Merkmalen des dritten digitalen Bildes und der in der Referenzbildstruktur enthaltenen Merkmale durchgeführt wird; – bei dem basierend auf der dritten Teilbewegungsschätzung, der zweiten Teilbewegungsschätzung und der ersten Teilbewegungsschätzung die Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild bestimmt wird.
Verfahren gemäß Anspruch 1, wobei nach Bestimmen der Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild die Referenzbildstruktur um zumindest ein Merkmal aus dem dritten Bild ergänzt wird.
Verfahren gemäß Anspruch 1 oder 2, wobei die Bewegung in einem dem ersten digitalen Bild, dem zweiten digitalen Bild und dem dritten digitalen Bild zeitlich nachfolgenden vierten Bild gegenüber dem ersten digitalen Bild – unter Verwendung einer weiteren Referenzbildstruktur, die zumindest Merkmale mindestens eines dem vierten Bild zeitlich vorhergehenden Bildes enthält; bestimmt wird, indem – eine vierte Teilbewegungsschätzung in dem vierten digitalen Bild gegenüber einem dem vierten digitalen Bild zeitlich vorhergehenden weiteren digitalen Bild, in dem die Bewegung gegenüber dem ersten digitalen Bild bereits bestimmt ist, bestimmt wird; – eine fünfte Teilbewegungsschätzung unter Vergleichen von Merkmalen des vierten digitalen Bildes und der in der Referenzbildstruktur enthaltenden Merkmale durchgeführt wird; – basierend auf der fünften Teilbewegungsschätzung, der vierten Teilbewegungsschätzung und der Bewegung des weiteren digitalen Bildes, die Bewegung bestimmt wird.
Verfahren gemäß Anspruch 3, wobei die weitere Referenzbildstruktur die um Merkmale aus mindestens einem dem zweiten digitalen Bild zeitlich nachfolgenden und dem vierten digitalen Bild zeitlich vorhergehenden digitalen Bild erweiterte Referenzbildstruktur ist.
Verfahren gemäß einem der Ansprüche 1 bis 4, wobei die Teilbewegungsschätzungen merkmalsbasiert durchgeführt werden.
Verfahren gemäß einem der Ansprüche 1 bis 5, wobei die Teilbewegungsschätzungen subpixelgenau durchgeführt werden.
Verfahren gemäß einem der Ansprüche 1 bis 6, wobei im Rahmen der Teilbewegungsschätzungen jeweils ein affines Bewegungsmodell oder ein perspektivisches Bewegungsmodell bestimmt wird.
Verfahren gemäß einem der Ansprüche 1 bis 7, wobei die erste Teilbewegungsschätzung, die zweite Teilbewegungsschätzung und die dritte Teilbewegungsschätzung mittels desselben Verfahrens zur Bewegungsschätzung in zeitlich aufeinanderfolgenden Bildern durchgeführt werden.
Verfahren gemäß einem der Ansprüche 1 bis 8, wobei zur Durchführung der dritten Teilbewegungsschätzung Merkmale auf die Referenzbildstruktur basierend auf der ersten Teilbewegungsschätzung und der zweiten Teilbewegungsschätzung abgebildet werden und die dritte Teilbewegungsschätzung durch Schätzung der Bewegung der abgebildeten Merkmale gegenüber der in der Referenzbildstruktur enthaltenen Merkmale durchgeführt wird.
Verfahren gemäß einem der Ansprüche 1 bis 9, wobei das Verfahren zur Bewegungsschätzung im Rahmen einer Erzeugung eines Mosaikbilds, der Kalibrierung einer Kamera, eines Super-Resolution-Verfahrens, einer Videokomprimierung oder einer dreidimensionalen Schätzung durchgeführt wird.
Anordnung zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern aufweisend – eine erste Verarbeitungseinheit, die eingerichtet ist, eine erste Teilbewegungsschätzung in einem zweiten digitalen Bild gegenüber einem dem zweiten digitalen Bild zeitlich vorhergehenden ersten digitalen Bild durchzuführen; – eine zweite Verarbeitungseinheit, die eingerichtet ist, aus dem ersten digitalen Bild und dem zweiten digitalen Bild basierend auf der ersten Teilbewegungsschätzung eine Referenzbildstruktur aufzubauen, welche zumindest Merkmale aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthält; – eine dritte Verarbeitungseinheit, die eingerichtet ist, eine zweite Teilbewegungsschätzung in einem dem zweiten digitalen Bild zeitlich nachfolgenden dritten digitalen Bildes gegenüber dem zweiten digitalen Bild durchzuführen; – eine vierte Verarbeitungseinheit, die eingerichtet ist, eine dritte Teilbewegungsschätzung unter Vergleichen von Merkmalen des dritten digitalen Bildes und der in der Referenzbildstruktur enthaltenden Merkmale durchzuführen; – eine fünfte Verarbeitungseinheit, die eingerichtet ist, basierend auf der dritten Teilbewegungsschätzung, der zweiten Teilbewegungsschätzung und der ersten Teilbewegungsschätzung die Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild zu bestimmen.
Computerprogramm-Element, das, nachdem es in einen Speicher eines Computers geladen worden ist, bewirkt, das der Computer ein Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern durchführt, – wobei eine erste Teilbewegungsschätzung in einem zweiten digitalen Bild gegenüber einem dem zweiten digitalen Bild zeitlich vorhergehenden ersten digitalen Bild durchgeführt wird; – aus dem ersten digitalen Bild und dem zweiten digitalen Bild basierend auf der ersten Teilbewegungsschätzung eine Referenzbildstruktur aufgebaut wird, welche zumindest Merkmale aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthält; – eine zweite Teilbewegungsschätzung in einem dem zweiten digitalen Bild zeitlich nachfolgenden dritten digitalen Bildes gegenüber dem zweiten digitalen Bild durchgeführt wird; – eine dritte Teilbewegungsschätzung unter Vergleichen von Merkmalen des dritten digitalen Bildes und der in der Referenzbildstruktur enthaltenden Merkmale durchgeführt wird; – basierend auf der dritten Teilbewegungsschätzung, der zweiten Teilbewegungsschätzung und der ersten Teilbewegungsschätzung die Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild bestimmt wird.
Computerlesbares Speichermedium, auf dem ein Programm gespeichert ist, das, nachdem es in einen Speicher eines Computer geladen worden ist, bewirkt, das der Computers ein Verfahren zur rechnergestützten Bewegungsschätzung in einer Vielzahl von zeitlich aufeinander folgenden digitalen Bildern durchführt – wobei eine erste Teilbewegungsschätzung in einem zweiten digitalen Bild gegenüber einem dem zweiten digitalen Bild zeitlich vorhergehenden ersten digitalen Bild durchgeführt wird; – aus dem ersten digitalen Bild und dem zweiten digitalen Bild basierend auf der ersten Teilbewegungsschätzung eine Referenzbildstruktur aufgebaut wird, welche zumindest Merkmale aus dem ersten digitalen Bild und/oder dem zweiten digitalen Bild enthält; – eine zweite Teilbewegungsschätzung in einem dem zweiten digitalen Bild zeitlich nachfolgenden dritten digitalen Bildes gegenüber dem zweiten digitalen Bild durchgeführt wird; – eine dritte Teilbewegungsschätzung unter Vergleichen von Merkmalen des dritten digitalen Bildes und der in der Referenzbildstruktur enthaltenden Merkmale durchgeführt wird; – basierend auf der dritten Teilbewegungsschätzung, der zweiten Teilbewegungsschätzung und der ersten Teilbewegungsschätzung die Bewegung in dem dritten digitalen Bild gegenüber dem ersten digitalen Bild bestimmt wird.