optical_flow_mg — Berechnung des optischen Flusses zwischen zwei Bildern.
optical_flow_mg(ImageT1, ImageT2 : VectorField : Algorithm, SmoothingSigma, IntegrationSigma, FlowSmoothness, GradientConstancy, MGParamName, MGParamValue : )
optical_flow_mg berechnet den optischen Fluss zwischen zwei
Bildern. Der optische Fluss stellt die Bewegungsinformation
zwischen zwei aufeinanderfolgenden Bildern einer monokularen
Bildfolge dar. Die Bewegung in den Bildern kann durch Objekte
entstehen, die sich zwischen den zwei Aufnahmen in der Welt bewegt
haben oder dadurch, dass sich die Kamera zwischen den zwei Aufnahmen
bewegt hat (oder beides). Die Projektion dieser 3D-Bewegungen in
die 2D-Bildebene wird als Optischer Fluss bezeichnet.
Die beiden aufeinanderfolgenden Bilder der Bildfolge werden in
ImageT1 und ImageT2 übergeben. Der berechnete
optische Fluss wird in VectorField zurückgeliefert. Die
Vektoren im Vektorfeld VectorField stellen die Bewegung
zwischen ImageT1 und ImageT2 in der Bildebene dar.
Der zu einem Punkt (r,c) in ImageT1 in ImageT2
zugeordnete Punkt ist also gegeben durch (r',c') =
(r+u(r,c),c+v(r,c)), wobei u(r,c) und v(r,c) den Wert der
Zeilen- bzw. Spaltenkomponente des Vektorfeldbildes
VectorField am Punkt (r,c) bezeichnen.
Der Parameter Algorithm erlaubt es, zwischen drei
verschiedenen Verfahren zur Berechnung des optischen Flusses
auszuwählen. Alle drei Verfahren sind mit Hilfe von numerischen
Mehrgitterverfahren implementiert, um eine effiziente Berechnung der
zugrundeliegenden partiellen Differentialgleichungen zu ermöglichen.
Für Algorithm = 'fdrig' wird das Verfahren von
Brox, Bruhn, Papenberg und Weickert verwendet. Dieses Verfahren ist
flussgetrieben, robust, isotrop und mit einem Gradientenkonstanzterm
(flow-driven, robust, isotropic
with gradient constancy).
Für Algorithm = 'ddraw' wird eine robuste
Variante des Verfahrens von Nagel und Enkelmann mit Warping
verwendet. Dieses Verfahren ist datengetrieben, robust, anisotrop
und verwendet (im Gegensatz zum Originalansatz) Warping
(data-driven, robust,
anisotropic with warping).
Für Algorithm = 'clg' wird das kombinierte
lokale-globale Verfahren (combined
local-global) von Bruhn, Weickert, Feddern,
Kohlberger und Schnörr verwendet.
In allen Verfahren können die Eingabebilder zunächst mit einem
Gaußfilter mit einer Standardabweichung von SmoothingSigma
geglättet werden (siehe derivate_gauss).
Alle drei Verfahren gehören zu der Klasse der sogenannten
Variationsansätze, die den optischen Fluss durch die Minimierung eines
geeigneten Energiefunktionals berechnen. Im allgemeinen haben
solche Energiefunktionale die Form
wobei w=(u,v,1) das gesuchte
Verschiebungsvektorfeld (mit einem Zeitschritt von 1 in der dritten
Koordinate) ist. Die Bildfolge wird als kontinuierliche Funktion
f(x) mit x=(r,c,t)
betrachtet, wobei (r,c) für den Ort im Bildbereich steht und t
die Zeit angibt. Weiterhin bezeichnen
den Datenterm,
den Glattheitsterm und
einen Regularisierungsparameter, der die
Glattheit der Lösung bestimmt. Der Regularisierungsparameter
wird in FlowSmoothness übergeben.
Während im Datenterm Annahmen über die Konstanz von Objektmerkmalen
in aufeinanderfolgenden Bildern formuliert werden, z.B. die Konstanz
des Grauwerts oder der ersten räumlichen Ableitung des Grauwerts,
verkörpert der Glattheitsterm Annahmen über die (stückweise)
Glattheit der Lösung, d.h. die Glattheit des gesuchten
Verschiebungsvektorfelds.
Das FDRIG-Verfahren basiert auf der Minimierung eines Energiefunktionals, das folgende Annahmen beinhaltet:
Konstanz des Grauwerts: Es wird angenommen, dass zueinander gehörende Pixel in aufeinanderfolgenden Bildern einer Bildfolge den gleichen Grauwert haben, also dass f(r+u,c+v,t+1) = f(r,c,t) gilt. Dies kann in Vektorschreibweise auch kompakter als f(x+w) = f(x) formuliert werden.
Konstanz der räumlichen Grauwertableitungen: Es wird angenommen, dass zueinander gehörende Pixel in aufeinanderfolgenden Bildern einer Bildfolge darüber hinaus auch die gleichen räumlichen Grauwertableitungen haben, also dass zusätzlich gilt, wobei . Dies kann kompakter als formuliert werden. Gegenüber der Grauwertkonstanz bietet die Gradientenkonstanz den Vorteil, dass sie invariant gegenüber additiven globalen Helligkeitsschwankungen ist.
Große Verschiebungen: Es wird außerdem angenommen, dass große Verschiebungen, d.h. Verschiebungen, die größer als ein Pixel sind, auftreten können. Unter dieser Annahme ist es sinnvoll, bewusst auf die Linearisierung der Konstanzannahmen im Modell zu verzichten, die üblicherweise in der Literatur vorgeschlagen werden.
Statistische Robustheit im Datenterm: Um starken Verletzungen der Konstanzannahmen durch Ausreißer weniger Bedeutung beizumessen, werden diese statistisch robust bestraft, d.h. die übliche nicht-robuste quadratische Bestrafung wird durch eine lineare Bestrafung mittels ersetzt, wobei eine feste Regularisierungskonstante ist.
Diskontinuitätenerhaltung im Flussfeld I: In Bezug auf die Lösung wird angenommen, dass diese stückweise glatt ist. Während die eigentliche Glattheit durch Bestrafungen der ersten Flussableitungen erreicht wird, sorgt die Verwendung einer robusten (linearen) Straffunktion mit für die gewünschten Erhaltung von Bewegungskanten im zu berechnenden Flussfeld. Dieser Typ des Glattheitsterms wird als flussgetrieben isotrop bezeichnet
Unter der Berücksichtigung all dieser Annahmen lässt sich das
Energiefunktional für das FDRIG-Verfahren als
schreiben. Hierbei ist der in
FlowSmoothness übergebene Regularisierungsparameter und
das in GradientConstancy übergebene
Gewicht der Gradientenkonstanz. Diese beiden Gewichte, die die
Modellparameter des FDRIG-Verfahrens darstellen, werden weiter unten
noch genauer beschrieben.
Das DDRAW-Verfahren basiert auf der Minimierung eines Energiefunktionals, das folgende Annahmen beinhaltet:
Konstanz des Grauwertes: Es wird angenommen, dass zueinander gehörende Pixel in aufeinanderfolgenden Bildern einer Bildfolge den gleichen Grauwert haben, also dass f(x+w) = f(x) gilt.
Große Verschiebungen: Es wird außerdem angenommen, dass große Verschiebungen, d.h. Verschiebungen, die größer als ein Pixel sind, auftreten können. Unter dieser Annahme ist es sinnvoll, bewusst auf die Linearisierung der Konstanzannahmen im Modell zu verzichten, die üblicherweise in der Literatur vorgeschlagen werden.
Statistische Robustheit im Datenterm: Um starken Verletzungen der Konstanzannahmen durch Ausreißer weniger Bedeutung beizumessen, werden diese statistisch robust bestraft, d.h. die übliche nicht-robuste quadratische Bestrafung wird durch eine lineare Bestrafung mittels ersetzt, wobei eine feste Regularisierungskonstante ist.
Diskontinuitätenerhaltung im Flussfeld II: In Bezug auf die Lösung wird angenommen, dass diese stückweise glatt ist. Im Gegensatz zum FDRIG-Verfahren, das Diskontinuitäten überall zulässt, respektiert das DDRAW-Verfahren nur Diskontinuitäten an Kanten im Originalbild. Dabei wird die lokale Glattheit so gesteuert, dass das Flussfeld über Bildkanten hinweg scharf ist, entlang von Bildkanten jedoch glatt. Dieser Typ des Glattheitsterms nennt sich datengetrieben anisotrop.
Alle Annahmen des DDRAW-Verfahrens lassen sich in einem einzigen Energiefunktional vereinigen: wobei eine normalisierte Projektionsmatrix orthogonal zu ist, für die gilt: Diese Matrix sorgt dafür, dass nur in Richtung der Bildkanten eine Glattheit des Flussfelds angenommen wird. Bezüglich der Glattheit über die Bildkanten hinweg werden jedoch keine Annahmen formuliert, so dass genau in diese Richtung Diskontinuitäten in der Lösung auftreten dürfen. In diesem Zusammenhang dient als Regularisierungsparameter, der verhindert, dass die Projektionsmatrix singulär wird. Im Gegensatz zum FDRIG-Verfahren gibt es beim DDRAW-Verfahren nur einen Modellparameter: den Regularisierungsparameter . Wie zuvor erwähnt, wird dieser unten noch genauer beschrieben.
Wie den beiden zuvor besprochenen Verfahren liegen auch dem CLG-Verfahren bestimmte Annahmen zu Grunde:
Konstanz des Grauwertes: Es wird angenommen, dass zueinander gehörende Pixel in aufeinanderfolgenden Bildern einer Bildfolge den gleichen Grauwert haben, also dass f(x+w) = f(x) gilt.
Kleine Verschiebungen: Im Gegensatz zu beiden vorigen Verfahren wird außerdem angenommen, dass nur kleine Verschiebungen auftreten können, d.h. Verschiebungen im Bereich weniger Pixel. Dies erlaubt eine Linearisierung der Konstanzannahmen im Modell. Dies führt auf die Approximation , d.h. es soll gelten: . Hiebei ist mit der Gradient über sowohl den Ort als auch die Zeit bezeichnet.
Lokale Konstanz der Lösung: Desweiteren geht man davon aus,
dass das zu berechnende Flussfeld lokal konstant ist. Dies erlaubt
die Integration der Bilddaten im Datenterm über die jeweilige
Umgebung eines Bildpunktes. Dies wiederum erhöht die Robustheit des
Verfahrens gegenüber Rauschen. Mathematisch lässt sich dies durch
eine Umformulierung des quadratischen Datenterms erreichen:
. Durch lokale
Gauß-gewichtete Integration über eine Nachbarschaft der Größe
(übergeben in IntegrationSigma) ergibt sich
dann folgender Datenterm: . Hierbei bezeichnet eine Faltung der 3x3
Matrix mit einem Gaußfilter mit einer
Standardabweichung von (siehe
derivate_gauss).
Allgemeine Glattheit des Flussfelds: Schließlich wird im Bezug auf die Lösung angenommen, dass sie überall im Bildbereich glatt ist. Dieser spezielle Typ des Glattheitsterms wird als homogen bezeichnet.
Auch im Fall des CLG-Verfahrens lassen sich alle Annahmen in einem
gemeinsamem Energiefunktional formulieren. Dieses lautet:
Die zugehörigen Modellparameter sind der Regularisierungsparameter
sowie die Integrationsskala
(übergeben in IntegrationSigma), die die Größe der zu
integrierenden Nachbarschaft im Datenterm angibt. Diese beiden
Parameter sind weiter unten genauer beschrieben.
Um das gewünschte Verschiebungsvektorfeld zwischen zwei aufeinanderfolgenden Bildern einer Bildfolge mit dem FDRIG-, dem DDRAW- oder dem CLG-Verfahren zu berechnen, muss diejenige Lösung gesucht werden, die die Annahmen des jeweiligen Verfahren am besten erfüllt. Aus mathematischer Sicht bedeutet das, dass man an einer Minimierung der oben beschriebenen Energiefunktionale interessiert ist. Bei dieser Minimierung spielen im Rahmen der ersten beiden Funktionale (FDRIG und DDRAW) sogenannte Coarse-to-Fine-Warping-Strategien eine wichtige Rolle, da sie es erlauben, große Verschiebungen zu schätzen. Sie sind damit ein geeignetes Mittel, um den bewussten Verzicht der beiden Verfahren auf eine Linearisierung der Konstanzannahmen im Datenterm numerisch umzusetzen.
Um große Verschiebungen schätzen zu können, machen Coarse-to-Fine-Warping-Strategien von zwei Konzepten Gebrauch, die beide eng miteinander verzahnt sind: Die sukzessive Verfeinerung der Problemstellung (Coarse-to-Fine) und die fortlaufende Kompensation des aktuelles Bildpaares um bereits berechnete Verschiebungen (Warping). Algorithmisch lässt sich eine solche Coarse-to-Fine-Warping-Strategie wie folgt formulieren:
1. Zunächst werden beide Bilder des aktuellen Bildpaares auf eine sehr grobe Auflösungsstufe heruntergesampelt.
2. Dann wird das Verschiebungsvektorfeld auf dieser groben Auflösung berechnet.
3. Dieses Vektorfeld wird auf der nächstfeineren Auflösungsstufe benötigt: Es wird dort aus dem zweiten Bild der Bildfolge herausgerechnet, d.h. die Problemstellung auf der feineren Auflösungsstufe wird um das bereits berechnete Flussfeld kompensiert. Dieser Schritt wird auch als Warping bezeichnet.
4. Das so modifizierte Problem (Differenzproblem) wird nun auf der feineren Auflösungsstufe gelöst, d.h. das Verschiebungsvektorfeld wird dort berechnet.
5. Die Schritte 3-4 werden wiederholt, bis die ursprüngliche Auflösung erreicht wird.
6. Das letzendliche Ergebnis wird durch Addition der Verschiebungsvektorfelder aller Auflösungsstufen gebildet.
Diese inkrementelle Berechnung des Verschiebungsvektorfelds bietet folgenden Vorteil: Während das Coarse-to-Fine-Konzept sicherstellt, dass die Verschiebungen auf der gröbsten Auflösungsstufe sehr klein sind, sorgt die Warping-Strategie dafür, dass das auch für die zu berechnenden Verschiebungsinkremente (Verschiebungsvektorfelder der Differenzprobleme) so bleibt. Da kleine Verschiebungen viel genauer berechnet werden können als größere, nimmt durch den Einsatz einer solchen Coarse-to-Fine-Warping-Strategie die Schätzqualität im allgemeinen deutlich zu. Jedoch muss anstelle eines einzelnen Korrespondenzproblems eine Hierarchie von ebensolchen Problemen gelöst werden. Im Rahmen des CLG-Verfahrens ist solch eine Coarse-to-Fine-Warping-Strategie nicht notwendig. Dort geht man bereits im Modell von kleineren Verschiebungen aus.
Die maximale Anzahl der Auflösungsstufen (Warpingebene), das Auflösungsverhältnis zwischen zwei aufeinanderfolgenden Auflösungsstufen, sowie die feinste Auflösungsstufe lassen sich sowohl beim FDRIG- als auch beim DDRAW-Verfahren spezifieren. Nähere Details hierzu sind weiter unten zu finden.
Die Minimierung von Funktionalen ist aus mathematischer Sicht sehr eng mit der Minimierung von Funktionen verwandt: So wie eine Nullstelle der ersten Ableitung eine notwendige Bedingung für ein Minimum einer Funktion ist, ist die Erfüllung der sogenannten Euler-Lagrange-Gleichungen eine notwendige Bedingung für die minimierende Funktion eines Funktionals (die minimierende Funktion entspricht hier dem gesuchten Verschiebungsvektorfeld). Die Euler-Lagrange-Gleichungen sind partielle Differentialgleichungen. Durch die Diskretisierung dieser Euler-Lagrange-Gleichungen mit Hilfe finiter Differenzen entstehen im Fall des FDRIG- und des DDRAW-Verfahrens große dünnbesetzte nichtlineare Gleichungssysteme. Aufgrund der Verwendung der oben beschriebenen Coarse-to-Fine-Warping-Strategien muss ein solches Gleichungssystem für jede Auflösungsstufe, d.h. für jede Warpingebene, gelöst werden. Im Fall des CLG-Verfahrens entsteht hingegen ein einzelnes großes dünnbesetztes lineares Gleichungssystem.
Um ein effizientes Lösen dieser nichtlinearen Gleichungssysteme zu gewährleisten, greifen sowohl das FDRIG- als auch das DDRAW-Verfahren auf sogenannte bidirektionale Mehrgitterverfahren zurück. Aus numerischer Sicht gehören diese Strategien zu den schnellsten Verfahren zum Lösen linearer und nichtlinearer Gleichungssysteme überhaupt. Im Gegensatz zu herkömmlichen nichthierarchischen iterativen Verfahren, wie z.B. den verschiedenen linearen und nichtlinearen Gauß-Seidel-Varianten, bieten solche Mehrgitterstrategien den Vorteil, Korrekturen der Lösung effizient auf gröberen Auflösungsstufen berechnen zu können. Dies führt wiederum zu einer erheblich schnelleren Konvergenz. Die grundlegende Idee von Mehrgitterverfahren besteht darüber hinaus darin, dass diese Korrekturschritte hierarchisch ausgeführt werden, d.h. dass die Berechnung des Fehlers auf der groben Auflösungsstufe selbst auf die gleiche Strategie zurückgreift und ihren eigenen Fehler (also den Fehler des Fehlers) durch Korrekturschritte auf einer noch gröberen Auflösungsstufe effizient berechnet. Je nachdem, ob ein oder zwei Fehlerkorrekturschritte pro Zyklus gemacht werden, spricht man von sogenannten V- oder W-Zyklen. Die zugehörigen Auflösungsdurchlaufstrategien sehen mit zwei bis vier Auflösungsstufen wie folgt aus: Hierbei werden Iterationen auf dem Originalproblem mit großen Markierungen symbolisiert, während kleine Markierungen für Iterationen auf Fehlerkorrekturproblemen stehen.
Algorithmisch lässt sich ein solcher Korrekturzyklus wie folgt beschreiben:
1. In einem ersten Schritt werden einige wenige Iterationen mit einem iterativen linearen oder nichtlinearen Basislöser (z.B. einer Gauß-Seidel-Variante) gemacht. Dieser Schritt nennt sich Fehlervorglättungsiterationsschritt.
2. In einem zweiten Schritt wird der aktuelle Fehler berechnet, um die bisherige Lösung (die Lösung nach Schritt 1) zu korrigieren. Aus Effizienzgründen findet diese Fehlerberechnung auf einer gröberen Auflösungsstufe statt. Dieser Schritt, der mehrfach wiederholt werden kann, nennt sich Grobgitterkorrekturschritt.
3. In einem letzten Schritt werden erneut einige wenige Iterationen mit dem gleichen iterativen linearen oder nichtlinearen Basislöser wie in Schritt 1 gemacht. Dieser Schritt nennt sich Fehlernachglättungsiterationsschritt.
Darüber hinaus besteht noch die Möglichkeit einer hierarchischen Initialisierung. Ausgehend von einer sehr groben Variante des ursprünglichen (nicht)linearen Gleichungssystems wird die Lösung sukzessive verfeinert. Dabei werden interpolierte Lösungen von gröberen Varianten des Gleichungssystems als Initialisierung der jeweils nächstfeineren Variante verwendet. Auf jeder Auflösungsstufe selbst kommen dann die zuvor beschriebenen V- oder W-Korrekturzyklen zum Einsatz, um das dortige (nicht)lineare Gleichungssystem effizient zu lösen. Die entsprechenden Mehrgitterverfahren werden in der Literatur als volle Mehrgitterverfahren bezeichnet. Diese Vorgehensweise kann wie folgt veranschaulicht werden: Dieses Beispiel stellt ein volles Mehrgitterverfahren mit zwei W-Korrekturzyklen pro Auflösungsstufe der hierarchischen Initialisierung dar. Die Interpolationsschritte der Lösung von einer Stufe zur nächsten sind mit i bezeichnet, die beiden W-Korrekturzyklen mit und . Während Iterationen auf dem Originalproblem mit großen Markierungen symbolisiert werden, stehen kleine Markierungen für Iterationen auf Fehlerkorrekturproblemen.
Im Rahmen der Mehrgitterimplementation des FDRIG-Verfahrens, des DDRAW- sowie des CLG-Verfahrens lassen sich folgende Parameter frei wählen: ob eine hierarchische Initialisierung stattfindet; die Anzahl der Grobgitterkorrekturschritte; die Anzahl der Korrekturzyklen; die maximale Anzahl an Korrekturebenen (Auflösungsstufen); die Anzahl der Fehlervorglättungsiterationen; die Anzahl der Fehlernachglättungsiterationen. Diese Parameter werden weiter unten noch genauer erklärt.
Als Basislöser für das FDRIG-Verfahren wird eine punktgekoppelte Fixpunktvariante des linearen Gauß-Seidel-Verfahrens verwendet, als Basislöser für das DDRAW-Verfahren eine alternierend liniengekoppelte Fixpunktvariante des gleichen Typs. Die Anzahl der Fixpunktschritte lässt sich dabei bei beiden Verfahren ebenfalls durch einen zusätzlichen Parameter spezifizieren. Der Basislöser für das CLG-Verfahren ist ein punktgekoppeltes lineares Gauß-Seidel-Verfahren. Der Transfer von Daten zwischen verschiedenen Auflösungsstufen erfolgt durch flächenbasierte Interpolation bzw. durch flächenbasierte Mittelung.
Nachdem die verwendeten Verfahren beschrieben wurden, können die Auswirkungen der einzelnen Parameter detailliert beschrieben werden.
Die Eingabebilder werden mit ihren Definitionsbereichen (Regionen)
in ImageT1 und ImageT2 übergeben. Die Berechnung
des Vektorfeldes VectorField erfolgt auf dem kleinsten
umschließenden Rechteck des Schnittes der Definitionsbereiche von
ImageT1 und ImageT2. Der Definitionsbereich von
VectorField ist der Schnitt der beiden Definitionsbereiche.
Daher kann durch Angabe von eingeschränkten Definitionsbereichen in
ImageT1 und ImageT2 die Verarbeitung fokussiert
werden, und u.U. Laufzeit gespart werden. Allerdings ist dabei zu
beachten, dass alle Verfahren eine globale Lösung des optischen
Flusses berechnen. Daraus folgt insbesondere, dass eine Lösung auf
einem eingeschränkten Definitionsbereich nicht die eingeschränkte
Lösung auf dem vollen Definitionsbereich sein muss (und kann).
SmoothingSigma beschreibt die Standardabweichung des
Gaußkerns, mit dem jedes Eingangsbild gefaltet wird. Je größer der
Wert für SmoothingSigma, desto größer ist die
Tiefpasswirkung des Gaußkerns, d.h. desto glatter wird das
vorverarbeitete Bild. Im Normalfall stellt ein Wert von
SmoothingSigma = 0.8 eine gute Wahl dar, aber auch andere
Werte im Intervall [0,2] sind denkbar. Größere
Standardabweichungen sollten nur in Betracht gezogen werden, falls
das Eingangsbild stark verrauscht ist. Dabei ist jedoch zu
beachten, dass größere Werte für SmoothingSigma eine
leichte Erhöhung der Laufzeit zur Folge haben.
IntegrationSigma beschreibt die Standardabweichung
des Gaußkerns , der zur lokalen
Integration der Nachbarschaftsinformation im Datenterm verwendet
wird. Dieser Parameter wird nur beim CLG-Verfahren verwendet und
hat bei den anderen beiden Verfahren keinen Einfluss auf das
Ergebnis. Im Normalfall stellt ein Wert von
IntegrationSigma = 1.0 eine gute Wahl dar, aber auch
andere Werte im Intervall [0,3] sind denkbar. Größere
Standardabweichungen sollten nur in Betracht gezogen werden, falls
das Eingangsbild stark verrauscht ist. Dabei ist jedoch zu
beachten, dass größere Werte für IntegrationSigma eine
leichte Erhöhung der Laufzeit zur Folge haben.
FlowSmoothness spezifiziert das Gewicht
des Glattheitsterms gegenüber dem Datenterm. Je größer der Wert für
FlowSmoothness ist, desto glatter wird das berechnete
Flussfeld. Dabei sollte beachtet werden, dass zu kleine Werte für
FlowSmoothness trotz statistisch robuster
Bestrafungsfunktionen zu unbrauchbaren Ergebnissen führen können,
insbesondere dann, wenn die verwendete Warping-Strategie zu viel
Information jenseits des Bildbereichs vorhersagen muss. Bei der
Verwendung von Byte-Bildern mit einem Wertebereich von [0,255]
liefern Werte für FlowSmoothness von etwa 20 im Fall des
flussgetriebenen FDRIG-Verfahrens und Werte von etwa 1000 im Fall
des bildgetriebenen DDRAW-Verfahrens bzw. des homogenen
CLG-Verfahrens im Normalfall gute Ergebnisse.
GradientConstancy beschreibt das Gewicht
der Gradientenkonstanz gegenüber der
Grauwertkonstanz. Dieser Parameter wird nur beim FDRIG-Verfahren
verwendet. Bei den anderen beiden Verfahren hat er keinen Einfluss
auf das Ergebnis. Für Grauwertbilder mit einem Wertebereich von
[0,255] ist meist ein Wert um GradientConstancy = 5
sinnvoll, da beide Konstanzannahmen in ähnlichem Ausmaß
berücksichtigt werden. Bei starken Beleuchtungswechseln können
jedoch auch wesentlich größere Werte für GradientConstancy
erforderlich sein, um gute Ergebnisse zu erzielen. Dabei ist zu
beachten, dass bei großen Werten für das Gradientengewicht auch der
Glattheitsparameter FlowSmoothness entsprechend größer
gewählt werden muss.
Die Parameter für den Mehrgitterlöser und die
Coarse-to-Fine-Warping-Strategie lassen sich mit den generischen
Parametern MGParamName und MGParamValue
einstellen. Im Normalfall ist es ausreichend, einen der vier weiter
unten beschriebenen Standardparametersätze über MGParamName
= 'default_parameters' und MGParamValue =
'very_accurate', 'accurate',
'fast_accurate' oder 'fast' auszuwählen. Falls
die Parameter einzeln angegeben werden sollen, ist in
MGParamName und MGParamValue jeweils ein
gleichlanges Tupel von Werten zu übergeben. Dabei müssen die Werte
für die in MGParamName angegebenen Parameter an der
jeweiligen Stelle des Tupels MGParamValue spezifiziert
werden.
Mit MGParamName = 'warp_zoom_factor' kann das
Auflösungsverhältnis zwischen zwei aufeinanderfolgenden
Warpingebenen in der Coarse-to-Fine-Warping-Hierarchie festgelegt
werden. Dabei muss 'warp_zoom_factor' im offenen Intervall
(0,1) gewählt werden. Aus Performanzgründen wird üblicherweise
'warp_zoom_factor' = 0.5 gewählt, d.h. die Pixelanzahl
der Eingangsbilder wird von einer Warpingebene zur nächsten in jede
Richtung halbiert. Dies führt zu einem zusätzlichen Rechenaufwand
von etwa 33% gegenüber einem Verfahren ohne Warping. Werte für
'warp_zoom_factor' näher bei 1 können zu qualitativ leicht
besseren Ergebnissen führen, benötigen aber unverhältnismäßig viel
Rechenzeit, z.B. einen Mehraufwand von 426% bei
'warp_zoom_factor' = 0.9.
Mit MGParamName = 'warp_levels' kann die
Warpinghierarchie auf eine maximale Anzahl von Ebenen beschränkt
werden. Für 'warp_levels' = 0 wird die maximal mögliche
Anzahl von Ebenen gewählt. Sollte die Bildgröße bei einem gegebenen
Auflösungsverhältnis 'warp_zoom_factor' die gewählte Anzahl
an Ebenen nicht zulassen, wird die maximal mögliche Anzahl an Ebenen
verwendet. Im Normalfall sollte 'warp_levels' auf 0
gesetzt werden.
Mit MGParamName = 'warp_last_level' kann die
Anzahl der Warpingebenen an, für die kein Bewegungsinkrement
mehr berechnet werden soll, festgelegt werden. Normalerweise wird
diese Anzahl entweder auf 1 oder 2 gesetzt, d.h. es wird entweder
auf jeder Warpingebene ein Bewegungsinkrement berechnet, oder die
feinste Warpingebene wird bei der Berechnung ausgelassen. Da im
letzten Fall nur auf halber Auflösung gerechnet wird, kann die
gewonnene Rechenzeit zur genaueren Bestimmung der Lösung verwendet
werden, d.h. es kann z.B. ein volles Mehrgitterverfahren mit
zusätzlichen Iterationen in Betracht gezogen werden. Die genauere
Lösung wird dann auf die volle Auflösung interpoliert.
Die drei Parameter, die die Coarse-to-Fine-Warping-Strategie bestimmen, haben nur bei dem FDRIG- und dem DDRAW-Verfahren einen Einfluss auf die Lösung. Bei dem CLG-Verfahren werden sie ignoriert.
Mit MGParamName = 'mg_solver' kann die
allgemeine Mehrgitterstrategie zur Lösung des (nicht)linearen
Gleichungssystems (in jeder Warpingebene) festgelegt werden. Für
'mg_solver' = 'multigrid' wird ein normales
Mehrgitterverfahren (ohne Coarse-to-Fine-Initialisierung)
verwendet, während für 'mg_solver' =
'full_multigrid' ein volles Mehrgitterverfahren (mit
Coarse-to-Fine-Initialisierung) verwendet wird. Da zwischen zwei
aufeinanderfolgenden Ebenen der Coarse-to-Fine-Initialisierung eine
Auflösungsreduktion um den Faktor 0.5 verwendet wird (dieser Wert
ist im Gegensatz zu der Auflösungsreduktion bei der
Warping-Strategie fest kodiert), bedeutet die Verwendung eines
vollen Mehrgitterverfahrens einen Mehraufwand von etwa 33%
gegenüber einem normalen Mehrgitterverfahren. Bei der Wahl von
'mg_solver' = 'full_multigrid' ergeben sich
typischerweise numerisch genauere Ergebnisse als für
'mg_solver' = 'multigrid'.
Mit MGParamName = 'mg_cycle_type' kann
festgelegt werden, ob ein V- oder ein W-Korrekturzyklus pro
Mehrgitterebene verwendet werden. Bei der verwendeten
Auflösungsreduktion um den Faktor 0.5 zwischen zwei
aufeinanderfolgenden Ebenen des jeweiligen Korrekturzyklus erhöht
die Verwendung eines W-Zyklus an Stelle eines V-Zyklus den
Rechenaufwand um 50%. Bei der Wahl von 'mg_cycle_type'
= 'w' ergeben sich typischerweise numerisch genauere
Ergebnisse als für 'mg_cycle_type' = 'v'.
Mit MGParamName = 'mg_levels' kann die
Mehrgitterhierarchie sowohl für die Coarse-to-Fine-Initialisierung
als auch für die eigentlichen V- oder W-Korrekturzyklen auf eine
maximale Anzahl von Ebenen beschränkt werden. Für
'mg_levels' = 0 wird die maximal mögliche Anzahl von
Ebenen gewählt. Sollte die Bildgröße die gewählte Anzahl an Ebenen
nicht zulassen, wird die maximal mögliche Anzahl an Ebenen
verwendet. Im Normalfall sollte 'mg_levels' auf 0 gesetzt
werden.
Mit MGParamName = 'mg_cycles' kann die gesamte
Anzahl von V- oder W-Korrekturzyklen, die durchgeführt werden,
festgelegt werden. Im Falle der Verwendung eines vollen
Mehrgitterverfahrens bezieht sich 'mg_cycles' auf
jede Ebene der Coarse-to-Fine-Initialisierung. Im Normalfall
sind ein oder zwei Zyklen ausreichend, um eine hinreichend genaue
Lösung des Gleichungssystems zu erhalten. Je größer
'mg_cycles' gewählt wird, desto genauer werden
typischerweise die numerischen Ergebnisse. Dieser Parameter geht
fast linear in die Laufzeit ein, d.h. eine Verdopplung der Zyklen
führt in etwa auch zu einer Verdopplung des Rechenaufwands.
Mit MGParamName = 'mg_pre_relax' kann die Anzahl
der Iterationen festgelegt werden, die auf jeder Ebene eines V- oder
W-Korrekturzyklus mit dem iterativen Basislöser vor der
eigentlichen Fehlerkorrektur durchgeführt werden. Im Normalfall
sind ein oder zwei Fehlervorglättungsiterationen ausreichend. Je
größer 'mg_pre_relax' gewählt wird, desto genauer werden
typischerweise die numerischen Ergebnisse.
Mit MGParamName = 'mg_post_relax' kann die
Anzahl der Iterationen festgelegt werden, die auf jeder Ebene eines
V- oder W-Korrekturzyklus mit dem iterativen Basislöser nach
der eigentlichen Fehlerkorrektur durchgeführt werden. Im Normalfall
sind ein oder zwei Fehlernachglättungsiterationen ausreichend. Je
größer 'mg_post_relax' gewählt wird, desto genauer werden
typischerweise die numerischen Ergebnisse.
Wie bei der Erhöhung der Anzahl der Korrekturzyklen geht eine gleichzeitige Erhöhung der Anzahl der Fehlervor- und Fehlernachglättungsiterationen asymptotisch linear in die Laufzeit ein, allerdings fallen keine zusätzlichen Restriktions- und Prolongationsoperationen (Verkleinerungen und Vergrößerungen der Fehlerkorrekturbilder) an. Für eine moderate Erhöhung nimmt der Mehraufwand deshalb nur leicht zu.
Mit MGParamName = 'mg_inner_iter' kann die
Anzahl der Iterationen zum Lösen der linearen Gleichungssysteme
innerhalb jeder Fixpunktiteration des nichtlinearen Basislösers
festgelegt werden. Im Normalfall ist eine Iteration ausreichend, um
eine ausreichende Konvergenzgeschwindigkeit des Mehrgitterverfahrens
zu erreichen. Die Zunahme des Rechenaufwandes bei Erhöhung der
Iterationsanzahl ist noch etwas geringer als bei der Erhöhung der
Fehlervor- und Fehlernachglättungsiterationen. Dieser Parameter
beeinflusst nur das FDRIG- und das DDRAW-Verfahren, da beim
CLG-Verfahren kein nichtlineares Gleichungssystem gelöst werden
muss.
Wie oben beschrieben, ist es im Normalfall ausreichend, einen der
Standardparametersätze für die oben beschriebenen Parameter über
MGParamName = 'default_parameters' und
MGParamValue = 'very_accurate',
'accurate', 'fast_accurate' oder 'fast'
auszuwählen. Dabei können im Bedarfsfall noch einzelne Parameter
nach der Auswahl der Standardparametersätze modifiziert werden,
indem nach dem Wert 'default_parameters' in
MGParamName noch eine Untermenge der obigen Parameter
angegeben wird und in MGParamValue ein entsprechender Wert
übergeben wird (z.B. MGParamName =
['default_parameters','warp_zoom_factor'] und
MGParamValue = ['accurate',0.6]).
Im einzelnen entsprechen die Standardparametersätze folgenden Werten:
'default_parameters' = 'very_accurate': 'warp_zoom_factor' = 0.5, 'warp_levels' = 0, 'warp_last_level' = 1, 'mg_solver' = 'full_multigrid', 'mg_cycle_type' = 'w', 'mg_levels' = 0, 'mg_cycles' = 1, 'mg_pre_relax' = 2, 'mg_post_relax' = 2, 'mg_inner_iter' = 1.
'default_parameters' = 'accurate': 'warp_zoom_factor' = 0.5, 'warp_levels' = 0, 'warp_last_level' = 1, 'mg_solver' = 'multigrid', 'mg_cycle_type' = 'v', 'mg_levels' = 0, 'mg_cycles' = 1, 'mg_pre_relax' = 1, 'mg_post_relax' = 1, 'mg_inner_iter' = 1.
'default_parameters' = 'fast_accurate': 'warp_zoom_factor' = 0.5, 'warp_levels' = 0, 'warp_last_level' = 2, 'mg_solver' = 'full_multigrid', 'mg_cycle_type' = 'w', 'mg_levels' = 0, 'mg_cycles' = 1, 'mg_pre_relax' = 2, 'mg_post_relax' = 2, 'mg_inner_iter' = 1.
'default_parameters' = 'fast': 'warp_zoom_factor' = 0.5, 'warp_levels' = 0, 'warp_last_level' = 2, 'mg_solver' = 'multigrid', 'mg_cycle_type' = 'v', 'mg_levels' = 0, 'mg_cycles' = 1, 'mg_pre_relax' = 1, 'mg_post_relax' = 1, 'mg_inner_iter' = 1.
Es ist zu beachten, dass die beiden Modi 'fast_accurate' und 'fast' für das CLG-Verfahren identisch zu den Modi 'very_accurate' und 'accurate' sind, da das CLG-Verfahren keine Coarse-to-Fine-Warping-Strategie verwendet.
ImageT1 (input_object) singlechannelimage(-array) → object (byte / uint2 / real)
Eingabebild 1.
ImageT2 (input_object) singlechannelimage(-array) → object (byte / uint2 / real)
Eingabebild 2.
VectorField (output_object) singlechannelimage(-array) → object (vector_field)
Optischer Fluss.
Algorithm (input_control) string → (string)
Algorithmus zur Bestimmung des optischen Flusses.
Defaultwert: 'fdrig'
Werteliste: 'clg', 'ddraw', 'fdrig'
SmoothingSigma (input_control) real → (real)
Standardabweichung für initiale Gaußsche Glättung.
Defaultwert: 0.8
Wertevorschläge: 0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0
Restriktion: SmoothingSigma >= 0.0
IntegrationSigma (input_control) real → (real)
Standardabweichung des Integrationsfilters.
Defaultwert: 1.0
Wertevorschläge: 0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0, 2.2, 2.4, 2.6, 2.8, 3.0
Restriktion: IntegrationSigma >= 0.0
FlowSmoothness (input_control) real → (real)
Gewicht des Glattheitsterms gegenüber dem Datenterm.
Defaultwert: 20.0
Wertevorschläge: 10.0, 20.0, 30.0, 50.0, 70.0, 100.0, 200.0, 300.0, 500.0, 700.0, 1000.0, 1500.0, 2000.0
Restriktion: FlowSmoothness >= 0.0
GradientConstancy (input_control) real → (real)
Gewicht der Gradientenkonstanz gegenüber der Grauwertkonstanz.
Defaultwert: 5.0
Wertevorschläge: 0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 15.0, 20.0, 30.0, 40.0, 50.0, 70.0, 100.0
Restriktion: GradientConstancy >= 0.0
MGParamName (input_control) attribute.name(-array) → (string)
Parametername(n) für das Mehrgitterverfahren.
Defaultwert: 'default_parameters'
Werteliste: 'default_parameters', 'mg_cycle_type', 'mg_cycles', 'mg_inner_iter', 'mg_levels', 'mg_post_relax', 'mg_pre_relax', 'mg_solver', 'warp_last_level', 'warp_levels', 'warp_zoom_factor'
MGParamValue (input_control) attribute.value(-array) → (string / real / integer)
Parameterwert(e) für das Mehrgitterverfahren.
Defaultwert: 'accurate'
Wertevorschläge: 'very_accurate', 'accurate', 'fast_accurate', 'fast', 'multigrid', 'full_multigrid', 'v', 'w', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9
grab_image (ImageT1, AcqHandle)
while (true)
grab_image (ImageT2, AcqHandle)
optical_flow_mg (ImageT1, ImageT2, VectorField, 'fdrig', 0.8, 1, 10, \
5, 'default_parameters', 'accurate')
threshold (VectorField, Region, 1, 10000)
copy_obj (ImageT2, ImageT1, 1, 1)
endwhile
Sind die Parameterwerte korrekt, dann liefert
optical_flow_mg den Wert 2 (H_MSG_TRUE). Das Verhalten bei leerer
Eingabe (keine Eingabebilder vorhanden) lässt sich mittels
set_system('no_object_result',<Result>) festlegen.
Gegebenenfalls wird eine Fehlerbehandlung durchgeführt.
threshold,
vector_field_length
T. Brox, A. Bruhn, N. Papenberg, and J. Weickert: High accuracy
optical flow estimation based on a theory for warping. In T. Pajdla
and J. Matas, editors, Computer Vision - ECCV 2004, volume 3024 of
Lecture Notes in Computer Science, pages 25--36. Springer, Berlin,
2004.
A. Bruhn, J. Weickert, C. Feddern, T. Kohlberger, and C. Schnörr:
Variational optical flow computation in real-time. IEEE
Transactions on Image Processing, 14(5):608-615, May 2005.
H.-H. Nagel and W. Enkelmann: An investigation of smoothness
constraints for the estimation of displacement vector fields from
image sequences. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 8(5):565-593, September 1986.
Ulrich Trottenberg, Cornelis Oosterlee, Anton Schüller: Multigrid.
Academic Press, Inc., San Diego, 2000.
Foundation