Is BFL the right thing to use for my problem?

Dear BFL experts,

I found out about BFL when I searched for a library that implements a Kalman filter. So far, everything works well: The BFL examples compile and work. I also read the documentation regarding the examples.

I think that BFL could do what I want but before I start implementing the whole thing I need opinions if BFL is really the right tool for my needs. I want to avoid doing things in vain :-)

I have a parameter estimation problem which is given as a nonlinear Kalman filter problem. The system model is treated with an EKF and the measurement model part uses an IEKF as it has stronger nonlinearities. I have derived the necessary jacobian matrices analytically for measurement (H) and system model (F). All noise terms are additive Gaussian.

Now the questions:
- Is BFL able to do what I need and is BFL intended for that?

- Which parts do I have to add to BFL and from what classes do I inherit? In the example there is inheritance from AnalyticConditionalGaussianAdditiveNoise but how do I know to which cases that applies? Is there some basic guidance what classes to use for each type of kalman filter (linear/EKF/IEKF/...)?

I know that Kalman filtering is basically predicting states modelled using gaussian pdfs but I don't feel very comfortable with the fact that BFL describes everything with pdfs. I'm not used to it yet. Kalman filter in matrix form what I read most often.

Hopefully anyone can shed some light to all this. Am I on the right path?
Best regards,
weaker

Is BFL the right thing to use for my problem?

On Mon, Jun 23, 2008 at 5:02 PM, weaker <weaker [..] ...> wrote:
> I found out about BFL when I searched for a library that implements a Kalman
> filter. So far, everything works well: The BFL examples compile and work. I
> also read the documentation regarding the examples.
>
> I think that BFL could do what I want but before I start implementing the
> whole thing I need opinions if BFL is really the right tool for my needs. I
> want to avoid doing things in vain :-)
>
> I have a parameter estimation problem which is given as a nonlinear Kalman
> filter problem. The system model is treated with an EKF and the measurement
> model part uses an IEKF as it has stronger nonlinearities. I have derived
> the necessary jacobian matrices analytically for measurement (H) and system
> model (F). All noise terms are additive Gaussian.
>
> Now the questions:
> - Is BFL able to do what I need and is BFL intended for that?

Yes and yes.

> - Which parts do I have to add to BFL and from what classes do I inherit? In
> the example there is inheritance from
> AnalyticConditionalGaussianAdditiveNoise but how do I know to which cases
> that applies? Is there some basic guidance what classes to use for each type
> of kalman filter (linear/EKF/IEKF/...)?

In the linear case, you can just *use* linear classes, see

For non-linear variants, you have to either
- provide the derivative functions yourself, by heriting from
AnalyticConditionalGaussianAdditiveNoise
- use Ginac (provides symbolic derivation, but is costly in terms of
performance) via

A long time ago, the dfGet functions in
AnalyticConditionalGaussianAdditiveNoise were pure virtual and that
could be seen in the doxygen documentation. That was more logic from
a conceptual point of view, however, we changed it in r14837 to avoid
that you would have to implement virtual functions that you didn't use
(different filters use different PDF operations).

> I know that Kalman filtering is basically predicting states modelled using gaussian pdfs but I don't feel very comfortable with the fact that BFL describes everything with pdfs. I'm not used to it yet. Kalman filter in matrix form what I read most often.

That's because KF is only a special case, and BFL is more general.

> Hopefully anyone can shed some light to all this. Am I on the right path?

You definitely are :-)

Klaas
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Dear Klaas, thank you for

Dear Klaas,

thank you for your kind answers.

So when I calculated the jacobian matrices in advance analytically using a CAS (computer algebra system) then heriting from AnalyticConditionalGaussianAdditiveNoise is what I need.

What I still have problems with is the term "number of conditional arguments". I know that the conditional arguments are those after the | in p(a|b,c,d,...). Where can I read about the kalman filter in that notation? I know about Bayes' rule and heard about it in some lectures but my problem is the transfer of Kalman filter from matrix notation to probability density notation. I need to understand how to rewrite the matrix equations into the pdf framework.
Any reading material tips anyone?

Another thing: In the "Getting started" tutorial you write "for a measurement model of a particle filter we only need to implement one of these functions: ProbabilityGet(meas)". How do I know which of the virtual functions I have to provide necessarily?

Best regards,
weaker

PS: Are you interested that people report typos within the "Getting started tutorial"?

Dear Klaas,

> So when I calculated the jacobian matrices in advance analytically using a
> CAS (computer algebra system) then heriting from
> AnalyticConditionalGaussianAdditiveNoise is what I need.

Exactly.

> What I still have problems with is the term "number of conditional
> arguments". I know that the conditional arguments are those after the | in
> p(a|b,c,d,...). Where can I read about the kalman filter in that notation?

A Kalman filter is an estimator for dynamic systems, so the above
equations then become
p(x_k+1|x_k, u_k) where u_k represents an input at timestep k, and
p(z_k|x_k, s_k) respectively

In your KF, the first PDF could be described as x_k+1 = A \times x_k +
B\times u_k + N(\mu, \sigma) etc.

So systems for which you use a KF are just a special case.
See e.g.

In BFL, the model directory is specific to such dynamic systems and
hence contains the checks if NumConditionalArguments is 2

However, the pdf classes in BFL are more general.

> I
> know about Bayes' rule and heard about it in some lectures but my problem is
> the transfer of Kalman filter from matrix notation to probability density
> notation. I need to understand how to rewrite the matrix equations into the
> pdf framework.
> Any reading material tips anyone?

Does this become more clear from what I said above?
So if you have a model like
x_k+1 = A \times x_k + B \times u_k + N(mu,sigma)

You would create a PDF in BFL like

Matrix A; Matrix B;
vector ratio; ratio[0] = A; ratio[1] = B;
Gaussian additiveNoise (mu,sigma);
LinearAnalyticConditionalGaussian::LinearAnalyticConditionalGaussian(ratio,
additiveNoise);

> Another thing: In the "Getting started" tutorial you write "for a
> measurement model of a particle filter we only need to implement one of
> these functions: ProbabilityGet(meas)". How do I know which of the virtual
> functions I have to provide necessarily?

If you know how your filter works (from a pdf point of view), then you
will know which functions you have to provide. If you don't, I would
suggest a 'don't fix it if it ain't broke' scenario. Wait till BFL
tells you you should implement a certain function :-)

> PS: Are you interested that people report typos within the "Getting started
> tutorial"?

Ofcourse. And not only typos. If you think we could describe certain
things more clearly, let us know too. Patches are preferred ;-)

Klaas
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Thank you!

Dear Klaas,

thank you for helping me so kindly. I really appreciate that.

My KF has a system model without inputs (no u_k) and with a relatively simple transition matrix. (As a first step I can even use the identity matrix here.) Where it is getting more complicated is with the measurement model.

For the background:
I'm reimplementing a PhD thesis about camera calibration where the author has an implicit Gauss-Helmert model and expresses that as a Gauss-Markov model which can be translated into a Kalman filter notation. The implicit function h(z,x) = 0 turns out to be the measurement matrix H. The h(z,x) is either the epipolar constraint, the trilinear constraint or a bundle adjustment constraint. And that's the reason why H is a very ugly matrix.

Your explanations made that formulation much clearer to me. As I understood it now, BFL treats the Kalman filter basically only as pdfs and all the transition matrices that tell how to change those pdfs over time are hidden inside the model e.g. the LinearAnalyticMeasurementModel in the linear case. The additive gaussian noise is a non-conditional argument.
That means, when I have no inputs there is only one conditional argument.

Regarding the typos, I will send you a mail with that. Also about possible improvements but at the moment I could not yet tell what to improve. When I will have mastered my Kalman filter with BFL I hopefully can. For creating patches I'm a too bad programmer at the moment :-)

I hope that I will make progress now but probably I might come back here with another question...

Best regards,
weaker

Thank you!

Hi weaker,

> thank you for helping me so kindly. I really appreciate that.
>
> My KF has a system model without inputs (no u_k) and with a relatively
> simple transition matrix. (As a first step I can even use the identity
> matrix here.) Where it is getting more complicated is with the measurement
> model.
A simple linear system model will just do for you.
So simply follow the instructions in:
http://people.mech.kuleuven.be/~tdelaet/bfl_doc/getting_started_guide/node9.html

> For the background:
> I'm reimplementing a PhD thesis about camera calibration where the author
> has an implicit Gauss-Helmert model and expresses that as a Gauss-Markov
> model which can be translated into a Kalman filter notation. The implicit
> function h(z,x) = 0 turns out to be the measurement matrix H. The h(z,x) is
> either the epipolar constraint, the trilinear constraint or a bundle
> adjustment constraint. And that's the reason why H is a very ugly matrix.

You sure need a nonlinear measurement model.
As I understand from your explanation you have an implicit measurement model
so you might have a look at:
LinearAnalyticMeasurementModelGaussianUncertainty_Implicit (API at:
http://people.mech.kuleuven.be/~tdelaet/bfl_doc/doc/html/classBFL_1_1LinearAnalyticMeasurementModelGaussianUncertainty__Implicit.html)

> Regarding the typos, I will send you a mail with that. Also about possible
> improvements but at the moment I could not yet tell what to improve. When I
> will have mastered my Kalman filter with BFL I hopefully can. For creating
> patches I'm a too bad programmer at the moment :-)
Please mail the list of typos/suggestions/corrections to the mailinglist such
that the correct person can apply them.
Any typo/suggestion is greatly appreciated!

> I hope that I will make progress now but probably I might come back here
> with another question...
That's what the ML is for.

Good luck.

Tinne
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

For the beginning a linear

For the beginning a linear system model will do, but in the end it may also be nonlinear. I think I start with a linear one and will progress to an EKF later.

The measurement model is given first as an implicit form, but the PhD thesis describes how to change from that (highly nonlinear) implicit formulation to explicit Kalman filter (IEKF) formulas. Therefore I (hopefully) don't need to use the implicit formulation. Further I'm unsure because LinearAnalyticMeasurementModelGaussianUncertainty__Implicit starts with "linear" while my implicit function is very nonlinear.

Another question that comes to my mind is: Can BFL deal with variably sized measurements? For example in one image pair I find 50 correspondences and in the other one only 40. Matrix sizes would change then. Does that pose a problem?

For the typos I'm going to open another thread for not to clutter that one.

Best regards,
weaker

For the beginning a linear

On Thursday 26 June 2008 16:48:45 weaker wrote:
> For the beginning a linear system model will do, but in the end it may also
> be nonlinear. I think I start with a linear one and will progress to an EKF
> later.
Good idea.

> The measurement model is given first as an implicit form, but the PhD
> thesis describes how to change from that (highly nonlinear) implicit
> formulation to explicit Kalman filter (IEKF) formulas. Therefore I
> (hopefully) don't need to use the implicit formulation. Further I'm unsure
> because LinearAnalyticMeasurementModelGaussianUncertainty__Implicit starts
> with "linear" while my implicit function is very nonlinear.
Nice, just use a nonlinear measurement model then as described in
http://people.mech.kuleuven.be/~tdelaet/bfl_doc/getting_started_guide/node28.html.

> Another question that comes to my mind is: Can BFL deal with variably sized
> measurements? For example in one image pair I find 50 correspondences and
> in the other one only 40. Matrix sizes would change then. Does that pose a
> problem?
BFL can deal with variable size measurements.
But so far I only considered the case where you have a seperate measurement
model for each measurement-type (i.e. a measurement model for each size).
Of course you could consider to use the maximum size you will encounter and
only partially use the vectors/matrices when your number of correspondences
is lower.

> For the typos I'm going to open another thread for not to clutter that one.
Great,

Tinne
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Variably-sized measurements

If I choose to use a fixed maximum size, does that influence the covariance of the KF? E.g. if I have a maximum of 100 correspondences and can only populate it with 30 measurements leaving 70 zero, does the KF "think" that the 70 zeroes are perfect measurements and therefore decrease its covariance on these entries? Or does leaving these entries zero the covariances unaffected?

If I choose to go the route of dynamically changing sizes, would I have to basically create a new measurement model for each measurement? Wouldn't that affect speed dramatically?

Best regards,
weaker

Variably-sized measurements

On Mon, 30 Jun 2008, weaker wrote:

> If I choose to use a fixed maximum size, does that influence the covariance
> of the KF? E.g. if I have a maximum of 100 correspondences and can only
> populate it with 30 measurements leaving 70 zero, does the KF "think" that
> the 70 zeroes are perfect measurements and therefore decrease its covariance
> on these entries? Or does leaving these entries zero the covariances
> unaffected?
>
> If I choose to go the route of dynamically changing sizes, would I have to
> basically create a new measurement model for each measurement? Wouldn't that
> affect speed dramatically?
>
I think Tinne mentioned another approach in her answer last time: you
could _allocate memory_ for the worst case dimension, such that you can
use exactly the memory you need in each case. I don't think she meant to
always run a KF on full dimension, leaving most of the states 'empty'...

Herman

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Variably-sized measurements

On Monday 30 June 2008 15:31:50 Herman Bruyninckx wrote:
> On Mon, 30 Jun 2008, weaker wrote:
> > If I choose to use a fixed maximum size, does that influence the
> > covariance of the KF? E.g. if I have a maximum of 100 correspondences and
> > can only populate it with 30 measurements leaving 70 zero, does the KF
> > "think" that the 70 zeroes are perfect measurements and therefore
> > decrease its covariance on these entries? Or does leaving these entries
> > zero the covariances unaffected?
> >
> > If I choose to go the route of dynamically changing sizes, would I have
> > to basically create a new measurement model for each measurement?
> > Wouldn't that affect speed dramatically?
>
> I think Tinne mentioned another approach in her answer last time: you
> could _allocate memory_ for the worst case dimension, such that you can
> use exactly the memory you need in each case. I don't think she meant to
> always run a KF on full dimension, leaving most of the states 'empty'...
Indeed.
As weaker correctly analyzed, it is not good to introduce dummy measurement
since this will indeed affect the covariances.
That's why I said in my previous email "Of course you could consider to use
the maximum size you will encounter and
only partially use the vectors/matrices when your number of correspondences
is lower." (where I want to put the emphasis on partially use).

Tinne
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Small steps forward :-)

Thanks for all your suggestions that help me much (as a total BFL newbie).

I think I understand now: I build the jacobian matrices up to a certain dimensional limit depending on what is the maximum number of correspondences I will have. If I have less measurements I just use a smaller sub-matrix (just as much rows as I have measurements) of that jacobian matrix. That way I avoid introducing dummy measurements. Is that what you mean?

If so, would I always have to create a new measurement model in BFL or would I somehow reuse the same model and just "cutting" the matrix size?

Best regards,
weaker

Small steps forward :-)

On Tuesday 01 July 2008 12:38:36 weaker wrote:
> Thanks for all your suggestions that help me much (as a total BFL newbie).
>
> I think I understand now: I build the jacobian matrices up to a certain
> dimensional limit depending on what is the maximum number of
> correspondences I will have. If I have less measurements I just use a
> smaller sub-matrix (just as much rows as I have measurements) of that
> jacobian matrix. That way I avoid introducing dummy measurements. Is that
> what you mean?
I think it is.

> If so, would I always have to create a new measurement model in BFL or
> would I somehow reuse the same model and just "cutting" the matrix size?
The easiest thing to do is to create a new measurement model for every new
size, but it sure is not the most efficient solution nor the nicest one.
Do you have any idea how your measurement model changes if you get a different
number of measurements?
Do all the measurement have just the same measurement model or (i.e. every row
of the H-matrix is the same) or how does you H matrix look like?

Tinne
_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

As far as I understood the

As far as I understood the PhD thesis so far, the calculation is the same in each row of H. H has 13 columns (13 parameters are going to be estimated) and as many rows as there are measurements. It wouldn't be useful to post the formulas as that is several lines of trigonometric expressions per matrix entry.
For the beginning I'm content with any solution, whether it's inefficient or ugly doesn't matter :-)

OK, I'll try how it goes and report back when I accomplished something (or not).

Found out that function dfget is in AnalyticConditionalGaussian and not in AnalyticConditionalGaussianAdditiveNoise. So please forget about the following.

[[[Another question: Klaas suggested that I use AnalyticConditionalGaussianAdditiveNoise but there is no virtual function dfget(). Does he perhaps mean AnalyticMeasurementModelGaussianUncertainty? Because there is a function df_dxget() which deals with the H matrix according to the source comments.

Or do I still have difficulties with the structure of BFL and I should use both? AnalyticConditionalGaussianAdditiveNoise to create the density and AnalyticMeasurementModelGaussianUncertainty to treat the density?]]]

Best regards,
weaker

Feeding measurements one-by-one?

I did further reading and found in the mailing list archive the following post
http://lists.mech.kuleuven.be/pipermail/bfl/2007-January/000448.html
where Herman Bruyninckx suggests to feed the variable measurements sequentially one-by-one. From his post it looks like the only prerequisite for that is that the measurements are assumed independent. Furthermore I'm unsure if I can treat a number of feature correspondences between two images as independent.

Does anyone know a book or paper that contains a proof or further material about what additional requirements must possibly be met in order to go that sequential measurement route?

Best regards,
weaker

Feeding measurements one-by-one?

On Thu, 3 Jul 2008, weaker wrote:

> I did further reading and found in the mailing list archive the following
> post
> http://lists.mech.kuleuven.be/pipermail/bfl/2007-January/000448.html
> where Herman Bruyninckx suggests to feed the variable measurements
> sequentially one-by-one. From his post it looks like the only prerequisite
> for that is that the measurements are assumed independent. Furthermore I'm
> unsure if I can treat a number of feature correspondences between two images
> as independent.

They are not... But this dependency should be represented in your "process
model"; the "measurements" could them be considered independent ("white
noise" difference between the real measurement and the prediction of the
measurement using the process and the measurement model).

> Does anyone know a book or paper that contains a proof or further material
> about what additional requirements must possibly be met in order to go that
> sequential measurement route?

What I mention above is a special case of "whitening": by introducing the
dependencies explicitly in your model, the deviations from the predictions
are "white noise" (if your process model is correct).

It is very difficult for us to follow the context of your threads: _you_
know it when you write the messages, but we don't... So, please define the
context (or reply to a previous message with the same context) so that we
can keep track of your reasoning :-)

Herman

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

_______________________________________________
I hereby promise not to top-post on the
BFL mailing list
BFL [..] ...
http://lists.mech.kuleuven.be/mailman/listinfo/bfl

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

Dear Herman, I understand

Dear Herman,

I understand that it may be very difficult to follow my context. And it is no bog-standard kalman filter what I need to do which makes things even more difficult.

For those who are interested in the topic, here is the PhD thesis I'm working with:
http://www.uvka.de/univerlag/volltexte/2007/232/
(I hope the PDF (at the top of the page) is also viewable from the outside network). On page 78 there is the overview about how his IEKF works (warning: z=state, x=measurement). (I'm not sure but he possibly performs whitening on the measurement noise covariance matrix with that H_x matrix.)

At the moment I feel a little disheartened in spite of all the help and good suggestions from the BFL crew. Perhaps treating that problem being a BFL newbie is a too steep learning curve.

For now it seems best for me to abandon my BFL plans and try to implement the matrix calculations directly.

Best regards,
weaker