filter_kalman
— Schätzung des aktuellen Zustands eines Systems mittels Kalman-Filterung.
filter_kalman
ist veraltet und wird nur aus Gründen
der Rückwärtskompatibilität zur Verfügung gestellt.
filter_kalman( : : Dimension, Model, Measurement, PredictionIn : PredictionOut, Estimate)
filter_kalman
liefert eine Schätzung des aktuellen Zustands
(oder auch eine Prädiktion des künftigen Zustandes) eines diskreten,
stochastisch gestörten, linearen Systems. Kalman-Filter werden im
Bereich der Bildverarbeitung insbesondere erfolgreich bei der
Bildfolgenanalyse eingesetzt (Hintergrund-Erkennung, Fahrbahnverfolgung
mittels Linienverfolgung oder mittels Regionen-Analyse etc.).
Im folgenden wird zunächst eine kurze Einführung in die Theorie
der Kalman-Filter gegeben. Im Anschluss daran wird dann die Routine
filter_kalman
selbst beschrieben.
KALMAN-FILTER: Ein diskretes, stochastisch gestörtes, lineares System wird durch folgende Kenngrößen charakterisiert:
Status x(t): Beschreibt den momentanen Zustand des Systems (Geschwindigkeiten, Temperaturen,...)
Stellgröße u(t): Eingaben von außen in das System
Messwerte y(t): Messwerte, die durch Beobachtung des Systems gewonnen werden. Sie spiegeln den Systemzustand (oder zumindest Teile davon) wider.
Eine Ausgabefunktion, die die Abhängigkeit der Messwerte vom Status beschreibt.
Eine Übergangsfunktion, die angibt, wie sich der Status in Abhängigkeit von der Zeit, seinem momentanen Wert und den Stellgrößen verändert.
Die Ausgabefunktion und die Übergangsfunktion sind linear. Ihre Anwendung kann daher als Matrix-Multiplikation geschrieben werden.
Die Übergangsfunktion wird durch die Übergangsmatrix A(t) und die Stellmatrix G(t) beschrieben, die Ausgangsfunktion durch die Messmatrix C(t). A(t) charakerisiert dabei die Abhängigkeit des neuen vom alten Systemstatus, G(t) die Abhängigkeit von den Stellgrößen. In der Praxis ist es selten möglich (oder zumindest zu aufwendig), ein reales System und sein Verhalten in sich geschlossen exakt zu beschreiben. Insbesondere beschränkt man sich in der Regel auf eine relativ kleine Zahl von Variablen zur Darstellung des Systemverhaltens. Daraus resultiert ein Fehler, der sogenannte Systemfehler (der auch Systemstörung genannt wird) v(t). Auch die Ausgabefunktion ist im allgemeinen nicht exakt. Jede Messung ist fehlerbehaftet. Die Messfehler seien mit w(t) bezeichnet. Damit ergeben sich folgende Systemgleichungen: x(t+1) = A(t)x(t) + G(t)u(t) + v(t) y(t) = c(t)x(t) + w(t) Die System- und Messfehler v(t) und w(t) sind unbekannt. Sie werden bei den im Zusammenhang mit Kalman-Filterung betrachteten Systemen als gaußverteilte Zufallsvektoren betrachtet (daher die Bezeichnung „stochastisch gestörte Systeme“). Somit wird das System berechenbar, wenn die zu v(t) und w(t) gehörigen Erwartungswerte und Kovarianzmatrizen bekannt sind.
Die Schätzung des Systemzustandes erfolgt wie in der Gauß-Markov- Schätzung. Der Kalman-Filter ist jedoch ein rekursiver Algorithmus, der sich nur auf die aktuellen Messwerte y(t) und den letzten Status x(t) stützt. Letzterer enthält implizit das Wissen um früher bereits angefallenen Messwerte.
Für den Startwert x(0) ist ein geeigneter Schätzwert x0 anzugeben, der als Erwartungswert einer Zufallsvariable für x(0) aufgefasst wird. Deren Fehler habe die Erwartung 0 und die Kovarianzmatrix P0, die ebenfalls anzugeben ist. Zum Zeitpunkt t sei der Erwartungswert der Störungen v(t) und w(t) jeweils 0 und ihre Kovarianzmatrizen seien Q(t) und R(t). x(t), v(t) und w(t) werden meist als unkorreliert angenommen (es sind auch beliebige Rauschprozesse modellierbar - die Erstellung der benötigten Matrizen durch den Anwender ist dann allerdings deutlich aufwendiger). An die gesuchten Schätzwerte werden folgende Bedingungen gestellt:
Die Schätzwerte hängen linear vom tatsächlichen Wert x(t) und der Messwertfolge y(0), y(1), ... , y(t) ab.
{ sei erwartungstreu, d.h. .}
Als Gütekriterium erfülle x^t das Kriterium der minimalen Varianz, d.h. die Varianz des Schätzfehlers, definiert als x(t) - x^t, sei minimal.
Der Kalman-Filter führt nach der Initialisierung zu jedem Zeitpunkt t folgende Berechnungsschritte aus: Dabei ist die Kovarianzmatrix des Schätzfehlers, der Extrapolations- bzw. Prädiktionswert des Zustands, die Kovarianzen des Prädiktionsfehlers die Verstärkungsmatrix (das sogenannte Kalman-gain) und X' die Transponierte einer Matrix X. Hingewiesen sei an dieser Stelle auch auf die Möglichkeit der Vorhersage (Prädiktion) des Folgezustandes durch Gleichung (K-I). Dies ist z.B. in der Bildverarbeitung mitunter sehr nützlich, um „regions of interest“ im Folgebild zu bestimmen.
Wie oben erwähnt, ist die Modellierung beliebiger Rauschprozesse mitunter sehr aufwendig. Ist beispielsweise das System- und das Messrauschen korelliert mit entsprechender Kovarianzmatrix L, sind die Gleichungen für das Kalman-gain und die Fehler-Kovarianzmatrix zu modifizieren: Es ist nun Aufgabe des Benutzers, die linearen Systemgleichungen (K-I) bis (K-V) - in Abhängigkeit vom konkreten Problem - aufzustellen. Er muss also ein der Problemlösung zugrundeliegendes mathematisches Modell entwickeln. Statistische Größen, die die Ungenauigkeiten seines Systems und die die zu erwartenden Messfehler beschreiben, müssen dabei geschätzt werden, wenn sie sich nicht exakt berechnen lassen. Im einzelnen sind also folgende Schritte nötig:
Aufstellen eines mathematischen Modells
Auswahl charakteristischer Zustandsvariablen
Aufstellen der Gleichungen, die die Aenderung dieser Zustandsvariablen beschreiben und Linearisierung derselben (Matrizen A und G)
Aufstellung der Gleichungen, die die Abhängigkeit der Messwerte des Systems von den Zustandsvariablen beschreiben und Linearisierung derselben (Matrix C)
Aufstellung oder Schätzung statistischer Abhängigkeiten zwischen den Systemstörungen (Matrix Q)
Aufstellung oder Schätzung statistischer Abhängigkeiten zwischen den Messfehlern (Matrix R)
Initialisierung des Anfangszustandes
Die Initialisierung des Systems (Punkt 7) verlangt dabei, wie oben erwähnt, die Angabe einer Schätzung des Systemzustandes zum Zeitpunkt 0 und der zugehörigen Kovarianzmatrix . Ist der exakte Anfangszustand nicht bekannt, empfiehlt es sich, die Komponenten des Vektors auf die Mittelwerte der jeweiligen Wertebereiche zu setzen und hohe Werte in einzutragen (in der Größenordnung der Quadrate der Wertebereiche). Nach einigen Iterationen (wenn die Zahl der insgesamt akkumulierten Messwerte größer geworden ist als die Zahl der Systemgrößen), erhält man auch hier brauchbare Werte. Ist umgekehrt der Anfangszustand exakt bekannt, sind alle Einträge von auf Null zu setzen - beschreibt ja die Kovarianzen des Fehlers zwischen dem Schätzwert und dem tatsächlichen Wert x(0).
DIE FILTER-ROUTINE:
Eine Kalman-Filterung hängt von einer Reihe von Daten ab, die sich in vier Gruppen gliedern lassen:
Übergangsmatrix A, Steuermatrix G mit der Stellgröße u und Messmatrix C)
Systemfehler-Kovarianzmatrix Q, Systemfehler-Messfehler- Kovarianzmatrix L und Messfehler-Kovarianzmatrix R)
y
Extrapolationsvektor und Extrapolationsfehler-Kovarianzmatrix
Viele Systeme kommen dabei ohne Eingaben „von außen“ und damit ohne G und u aus. Außerdem sind im Normalfall System- und Messfehler unkorreliert (L entfällt).
Konkret werden die benötigten Daten der Routine durch folgende Parameter übergeben:
Dimension
:
Dieser Parameter enthält die Dimensionen von Status-, Mess- und
Stellvektor. Dimension
ist somit ein Vektor [n,m,p],
wobei n die Anzahl der Zustandsvariablen, m die Anzahl der
Messwerte und p die Anzahl der Stellglieder ist.
Für ein System ohne deterministische Steuerung (d.h. ohne Einfluss
„von außen“) ist folglich [n,m,0] zu übergeben.
Model
:
Dieser Parameter enthält hintereinandergehängt die zeilenweise
linearisierten Matrizen (Vektoren) A, C, Q, G, u und (gegebenenfalls)
L. Model
ist also ein Vektor der Länge n*n + n*m + n*n + n*p + p [+ n*m].
Der letzte Summand entfällt, falls System- und Messfehler unkorreliert sind,
d.h. kein L anzugeben ist.
Measurement
:
Dieser Parameter enthält hintereinandergehängt die zeilenweise
linearisierte Matrix R und den Messvektor y.
Measurement
ist also ein Vektor der Dimension m*m + m.
PredictionIn
/ PredictionOut
:
Diese Parameter enthalten hintereinandergehängt die zeilenweise
linearisierte Matrix (die Extrapolationsfehler-Kovarianzmatrix) und
den Extrapolationsvektor , sind also Vektoren der Länge
n*n + n. PredictionIn
ist ein Eingabeparameter, der
und zum aktuellen Zeitpunkt t
enthalten muss.
In PredictionOut
liefert die Routine dann die entsprechenden
Vorhersagen und .
Estimate
:
In Diesem Parameter liefert die Routine hintereinandergehängt die
zeilenweise linearisierte Matrix (die
Schätzfehler-Kovarianzmatrix) und den geschätzten Zustand .
Estimate
ist daher ein Vektor der Länge n*n + n.
Zu beachten ist dabei, dass Kovarianzmatrizen naturgemäß symmetrisch sein müssen.
Dimension
(input_control) integer-array →
(integer)
Die Dimensionen von Status-, Mess- und Stellvektor.
Defaultwert: [3,1,0]
Typischer Wertebereich: 0
≤
Dimension
≤
30
Model
(input_control) real-array →
(real)
Hintereinandergehängt die zeilenweise linearisierten Matrizen A,C,Q, eventuell G und u und gegebenenfalls L.
Defaultwert: [1.0,1.0,0.5,0.0,1.0,1.0,0.0,0.0,1.0,1.0,0.0,0.0,54.3,37.9,48.0,37.9,34.3,42.5,48.0,42.5,43.7]
Typischer Wertebereich: 0.0
≤
Model
≤
10000.0
Measurement
(input_control) real-array →
(real)
Hintereinandergehängt die zeilenweise linearisierte Matrix R und der Messvektor y.
Defaultwert: [1.2,1.0]
Typischer Wertebereich: 0.0
≤
Measurement
≤
10000.0
PredictionIn
(input_control) real-array →
(real)
Hintereinandergehängt die zeilenweise linearisierte Matrix (die Extrapolationsfehler- kovarianzen) und der Extrapolationsvektor .
Defaultwert: [0.0,0.0,0.0,0.0,180.5,0.0,0.0,0.0,100.0,0.0,100.0,0.0]
Typischer Wertebereich: 0.0
≤
PredictionIn
≤
10000.0
PredictionOut
(output_control) real-array →
(real)
Hintereinandergehängt die zeilenweise linearisierte Matrix P* (die Extrapolationsfehler- kovarianzen) und der Extrapolationsvektor
Estimate
(output_control) real-array →
(real)
Hintereinandergehängt die zeilenweise linearisierte Matrix (die Schätzfehlerkovarianzen) und der geschätzte Zustand .
* Typical procedure: * To initialize the variables, which describe the model, e.g., with read_kalman('kalman.init',Dim,Mod,Meas,Pred) * Generation of the first measurements (typical of the first image of an * image series) with an appropriate problem-specific procedure (there is a * fictitious procedure extract_features in example): * extract_features(Image1,Meas,Meas1) * first Kalman-Filtering: filter_kalman(Dim,Mod,Meas1,Pred,Pred1,Est1) * To use the estimate value (if need be the prediction too) * with a problem-specific procedure (here use_est): * use_est(Est1) * To get the next measurements (e.g. from the next image): * extract_next_features(Image2,Meas1,Meas2) * if need be Update of the model parameter (a constant model) * second Kalman-Filtering: filter_kalman(Dim,Mod,Meas2,Pred1,Pred2,Est2) * use_est(Est2) * extract_next_features(Image3,Meas2,Meas3) * etc.
Sind die Parameterwerte korrekt, dann liefert filter_kalman
den Wert 2 (H_MSG_TRUE).
Andernfalls wird eine Fehlerbehandlung durchgeführt.
W.Hartinger: „Entwurf eines anwendungsunabhängigen Kalman-Filters mit
Untersuchungen im Bereich der Bildfolgenanalyse“; Diplomarbeit;
Technische Universität München, Institut für Informatik, Lehrstuhl
Prof. Radig; 1991.
R.E.Kalman: „A New Approach to Linear Filtering and Prediction Problems“;
Transactions ASME, Ser.D: Journal of Basic Engineering; Vol. 82, S.34-45;
1960.
R.E.Kalman, P.l.Falb, M.A.Arbib: „Topics in Mathematical System Theory“;
McGraw-Hill Book Company, New York; 1969.
K-P. Karmann, A.von Brandt: „Moving Object Recognition Using an Adaptive
Background Memory“; Time-Varying Image Processing and Moving Object
Recognition 2 (ed.: V. Cappellini), Proc. of the 3rd Interantional
Workshop, Florence, Italy, May, 29th - 31st, 1989; Elsevier, Amsterdam;
1990.
Foundation