ClassesClassesClassesClasses | | | | Operators

filter_kalmanT_filter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman (Operator)

Name

filter_kalmanT_filter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman — Estimate the current state of a system with the help of the Kalman filtering.

Warning

filter_kalmanfilter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman is obsolete and is only provided for reasons of backward compatibility.

Signature

filter_kalman( : : Dimension, Model, Measurement, PredictionIn : PredictionOut, Estimate)

Herror T_filter_kalman(const Htuple Dimension, const Htuple Model, const Htuple Measurement, const Htuple PredictionIn, Htuple* PredictionOut, Htuple* Estimate)

Herror filter_kalman(const HTuple& Dimension, const HTuple& Model, const HTuple& Measurement, const HTuple& PredictionIn, HTuple* PredictionOut, HTuple* Estimate)

void FilterKalman(const HTuple& Dimension, const HTuple& Model, const HTuple& Measurement, const HTuple& PredictionIn, HTuple* PredictionOut, HTuple* Estimate)

static HTuple HMisc::FilterKalman(const HTuple& Dimension, const HTuple& Model, const HTuple& Measurement, const HTuple& PredictionIn, HTuple* Estimate)

void HOperatorSetX.FilterKalman(
[in] VARIANT Dimension, [in] VARIANT Model, [in] VARIANT Measurement, [in] VARIANT PredictionIn, [out] VARIANT* PredictionOut, [out] VARIANT* Estimate)

VARIANT HMiscX.FilterKalman(
[in] VARIANT Dimension, [in] VARIANT Model, [in] VARIANT Measurement, [in] VARIANT PredictionIn, [out] VARIANT* Estimate)

static void HOperatorSet.FilterKalman(HTuple dimension, HTuple model, HTuple measurement, HTuple predictionIn, out HTuple predictionOut, out HTuple estimate)

static HTuple HMisc.FilterKalman(HTuple dimension, HTuple model, HTuple measurement, HTuple predictionIn, out HTuple estimate)

Description

The operator filter_kalmanfilter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman returns an estimate of the current state (or also a prediction of a future state) of a discrete, stochastically disturbed, linear system. In practice, Kalman filters are used successfully in image processing in the analysis of image sequences (background identification, lane tracking with the help of line tracing or region analysis, etc.). A short introduction concerning the theory of the Kalman filters will be followed by a detailed description of the routine filter_kalmanfilter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman itself.

KALMAN FILTER: A discrete, stochastically disturbed, linear system is characterized by the following markers:

The output function and the transition function are linear. Their application can therefore be written as a multiplication with a matrix.

The transition function is described with the help of the transition matrix A(t) and the parameter matrix G(t), the initial function is described by the measurement matrix C(t). Hereby C(t) characterizes the dependency of the new state on the old, G(t) indicates the dependency on the parameters. In practice it is rarely possible (or at least too time consuming) to describe a real system and its behaviour in a complete and exact way. Normally only a relatively small number of variables will be used to simulate the behaviour of the system. This leads to an error, the so called system error (also called system disturbance) v(t).

The output function, too, is usually not exact. Each measurement is faulty. The measurement errors will be called w(t). Therefore the following system equations arise:

              x(t+1) = A(t)x(t) + G(t)u(t) + v(t)
              y(t)   = c(t)x(t) + w(t)
The system error v(t) and the measurement error w(t) are not known. As far as systems are concerned which are interpreted with the help of the Kalman filter, these two errors are considered as Gaussian distributed random vectors (therefore the expression “stochastically disturbed systems”). Therefore the system can be calculated, if the corresponding expected values for v(t) and w(t) as well as the covariance matrices are known.

The estimation of the state of the system is carried out in the same way as in the Gaussian-Markov-estimation. However, the Kalman filter is a recursive algorithm which is based only on the current measurements y(t) and the latest state x(t). The latter implicitly also includes the knowlegde about earlier measurements.

A suitable estimate value x0, which is interpreted as the expected value of a random variable for x(0), must be indicated for the initial value x(0). This variable should have an expected error value of 0 and the covariance matrix P0 which also has to be indicated. At a certain time t the expected values of both disturbances v(t) and w(t) should be 0 and their covariances should be Q(t) and R(t). x(t), v(t) and w(t) will usually be assumed to be not correlated (any kind of noise-process can be modelled - however the development of the necessary matrices by the user will be considerably more demanding). The following conditions must be met by the searched estimate values :

After the initialization

at each point in time t the Kalman filter executes the following calculation steps:
Hereby is the covariance matrix of the estimation error, is the extrapolation value respective the prediction value of the state, are the covariances of the prediction error is the amplifier matrix (the so called Kalman gain), and X' is the transposed of a matrix X.

Please note that the prediction of the future state is also possible with the equation (K-I). Somtimes this is very useful in image processing in order to determine “regions of interest” in the next image.

As mentioned above, it is much more demanding to model any kind of noise processes. If for example the system noise and the measurement noise are correlated with the corresponding covariance matrix L, the equations for the Kalman gain and the error covariance matrix have to be modified:

This means that the user himself has to establish the linear system equations from (K-I) up to (K-V) with respect to the actual problem. The user must therefore develop a mathematical model upon which the solution to the problem can be based. Statistical characteristics describing the inaccuracies of the system as well as the measurement errors, which are to be expected, thereby have to be estimated if they cannot be calculated exactly. Therefore the following individual steps are necessary:

  1. Developing a mathematical model

  2. Selecting characteristic state variables

  3. Establishing the equations describing the changes of these state variables and their linearization (matrices A and G)

  4. Establishing the equations describing the dependency of the measurement values of the system on the state variables and their linearization (matrix C)

  5. Developing or estimating of statistical dependencies between the system disturbances (matrix Q)

  6. Developing or estimating of statistical dependencies between the measurement errors (matrix R)

  7. Initialization of the initial state

As mentioned above, the initialization of the system (point 7) hereby necessitates to indicate an estimate of the state of the system at the time 0 and the corresponding covariance matrix . If the exact initial state is not known, it is recommendable to set the components of the vector to the average values of the corresponding range, and to set high values for (about the size of the squares of the range). After a few iterations (when the number of the accumulated measurement values in total has exceeded the number of the system values), the values which have been determined in this way are also useable.

If on the other hand the initial state is known exactly, all entries for have to be set to 0, because describes the covariances of the error between the estimated value and the actual value x(0).

THE FILTER ROUTINE:

A Kalman filter is dependent on a range of data which can be organized in four groups:

Model parameter:

transition matrix A, control matrix G including the parameter u and the measurement matrix C

Model stochastic:

system-error covariance matrix Q, system-error - measurement-error covariance matrix L, and measurement-error covariance matrix R

Measurement vector:

y

History of the system:

extrapolation vector and extrapolation-error covariance matrix

Thereby many systems can work without input “from outside”, i.e. without G and u. Further, system errors and measurement errors are normally not correlated (L is dropped).

Actually the data necessary for the routine will be set by the following parameters:

DimensionDimensionDimensionDimensionDimensiondimension:

This parameter includes the dimensions of the status vector, the measurement vector and the controller vector. DimensionDimensionDimensionDimensionDimensiondimension thereby is a vector [n,m,p], whereby n indicates the number of the state variables, m the number of the measurement values and p the number of the controller members. For a system without determining control (i.e. without influence “from outside”) therefore [n,m,0] has to be passed.

ModelModelModelModelModelmodel:

This parameter includes the lined up matrices (vectors) A, C, Q, G, u and (if necessary) L having been stored in row-major order. ModelModelModelModelModelmodel therefore is a vector of the length n*n + n*m + n*n + n*p + p [+ n*m]. The last summand is dropped, in case the system errors and measurement errors are not correlated, i.e. there is no value for L.

MeasurementMeasurementMeasurementMeasurementMeasurementmeasurement:

This parameter includes the matrix R which has been stored in row-major order, and the measurement vector y lined up. MeasurementMeasurementMeasurementMeasurementMeasurementmeasurement therefore is a vector of the dimension m*m + m.

PredictionInPredictionInPredictionInPredictionInPredictionInpredictionIn / PredictionOutPredictionOutPredictionOutPredictionOutPredictionOutpredictionOut:

These two parameters include the matrix (the extrapolation-error covariance matrix) which has been stored in row-major order and the extrapolation vector lined up. This means, they are vectors of the length n*n + n. PredictionInPredictionInPredictionInPredictionInPredictionInpredictionIn therefore is an input parameter, which must contain and at the current time t. With PredictionOutPredictionOutPredictionOutPredictionOutPredictionOutpredictionOut the routine returns the corresponding predictions and .

EstimateEstimateEstimateEstimateEstimateestimate:

With this parameter the routine returns the matrix (the estimation-error covariance matrix) which has been stored in row-major order and the estimated state lined up. EstimateEstimateEstimateEstimateEstimateestimate therefore is a vector of the length n*n + n.

Please note that the covariance matrices

must of course be symmetric.

Parallelization

Parameters

DimensionDimensionDimensionDimensionDimensiondimension (input_control)  integer-array HTupleHTupleHTupleVARIANTHtuple (integer) (int / long) (Hlong) (Hlong) (Hlong) (Hlong)

The dimensions of the state vector, the measurement and the controller vector.

Default value: [3,1,0]

Typical range of values: 0 ≤ Dimension Dimension Dimension Dimension Dimension dimension ≤ 30

ModelModelModelModelModelmodel (input_control)  real-array HTupleHTupleHTupleVARIANTHtuple (real) (double) (double) (double) (double) (double)

The lined up matrices A,C,Q, possibly G and u, and if necessary L which have been stored in row-major order.

Default value: [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]

Typical range of values: 0.0 ≤ Model Model Model Model Model model ≤ 10000.0

MeasurementMeasurementMeasurementMeasurementMeasurementmeasurement (input_control)  real-array HTupleHTupleHTupleVARIANTHtuple (real) (double) (double) (double) (double) (double)

The matrix R stored in row-major order and the measurement vector y lined up.

Default value: [1.2,1.0]

Typical range of values: 0.0 ≤ Measurement Measurement Measurement Measurement Measurement measurement ≤ 10000.0

PredictionInPredictionInPredictionInPredictionInPredictionInpredictionIn (input_control)  real-array HTupleHTupleHTupleVARIANTHtuple (real) (double) (double) (double) (double) (double)

The matrix (the extrapolation-error covariances) stored in row-major order and the extrapolation vector lined up.

Default value: [0.0,0.0,0.0,0.0,180.5,0.0,0.0,0.0,100.0,0.0,100.0,0.0]

Typical range of values: 0.0 ≤ PredictionIn PredictionIn PredictionIn PredictionIn PredictionIn predictionIn ≤ 10000.0

PredictionOutPredictionOutPredictionOutPredictionOutPredictionOutpredictionOut (output_control)  real-array HTupleHTupleHTupleVARIANTHtuple (real) (double) (double) (double) (double) (double)

The matrix P* (the extrapolation-error covariances)stored in row-major order and the extrapolation vector lined up.

EstimateEstimateEstimateEstimateEstimateestimate (output_control)  real-array HTupleHTupleHTupleVARIANTHtuple (real) (double) (double) (double) (double) (double)

The matrix (the estimation-error covariances) stored in row-major order and the estimated state lined up.

Example (HDevelop)

* 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.

Example (C)

/* Typical procedure: */
/* 1. To initialize the variables
      which describe the model, e.g. with */

read_kalman("kalman.init",Dim,Mod,Meas,Pred) ;

/* Generation of the first measurements (typically of the
   first image of an image series) with an appropriate
   problem-specific routine (there is a fictitious routine
   extract_features in this 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 routine (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. */

Example (HDevelop)

* 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.

Example (HDevelop)

* 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.

Example (HDevelop)

* 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.

Example (HDevelop)

* 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.

Result

If the parameter values are correct, the operator filter_kalmanfilter_kalmanFilterKalmanfilter_kalmanFilterKalmanFilterKalman returns the value 2 (H_MSG_TRUE). Otherwise an exception is raised.

Possible Predecessors

read_kalmanread_kalmanReadKalmanread_kalmanReadKalmanReadKalman

Possible Successors

update_kalmanupdate_kalmanUpdateKalmanupdate_kalmanUpdateKalmanUpdateKalman

See also

read_kalmanread_kalmanReadKalmanread_kalmanReadKalmanReadKalman, update_kalmanupdate_kalmanUpdateKalmanupdate_kalmanUpdateKalmanUpdateKalman

References

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.

Module

Foundation


ClassesClassesClassesClasses | | | | Operators