ACVT Logo
 
 

 
Many problems in computer vision are readily formulated as the need to minimise a cost function with respect to some unknown parameters. Such a cost function will often involve (known) covariance matrices characterising uncertainty of the data and will take the form of a sum of quotients of quadratic forms in the parameters. Finding the values of the parameters that minimise such a cost function is often difficult.

One approach to minimising a cost function represented as a sum of fractional expressions is attributed to Sampson. Here, an initial estimate is substituted into the denominators of the cost function, and a minimiser is sought for the now scalar-weighted numerators. This procedure is then repeated using the newly obtained estimate until convergence is obtained. It emerges that this approach is biased. Noting this, Kenichi Kanatani developed a renormalisation method whereby an attempt is made at each iteration to undo the biasing effects. Many examples may be found in the literature of problems benefiting from this approach.

In our work on parameter estimation, we have analysed the renormalisation approach, and placed it in the context of other approaches. As a result of this process we have observed that the renormalisation estimate is not a theoretical minimiser of the cost function. To counter this problem we have developed a fundamental numerical scheme for minimising the appropriate cost functions.

Parameter estimation with FNS

FNS stands for the fundamental numerical scheme. It was given this label because it arose out of efforts to compare Kanatani's renormalisation schemes (see the JMIV paper). It was the fundamental method we used to understand the various renormalisation schemes rather than being fundamental in a broader sense.

There are two parts to FNS, the cost function, and a means by which a minimiser of such a cost function may be found.

  • The cost function
    • The form of the cost function is not unique, it's the same cost function that was used by Sampson, Bookstein and Kanatani amongst others.
    • There are a number of justifications for such a cost function, but one is that it forms a first order approximation of the distance between a point representing an image measurement (like a pair of corresponding points) and a manifold (such as that parameterised by the fundamental matrix)
    • We have given the cost function the label approximated maximum likelihood distance for this reason.
  • The minimisation scheme
    • The minimisation scheme allows the minimisers of such cost functions to be calculated.
    • Sampson, Bookstein and Kanatani (amongst others) have come up with schemes to perform the same function with varying levels of success.
    • The minimiser is unique, however, in that it actually calculates a parameter estimate which minimises the cost function in question, not some other related cost function.

There is a pdf introduction to the justification for the approximated maximum likelihood cost function and how to implement the FNS minimisation scheme in order to help get it going, and there's Matlab code for a number of estimators (including FNS and CFNS) on my code page..

Publications

Constrained Parameter Estimation

We have recently been working on applying the above to the problem of constrained parameter estimation. A number of the problems of the form to which FNS is applicable exhibit a constraint on the values a parameter estimate may take. An example of such a constraint is the rank 2 constraint in fundamental matrix fitting.

We are currently in the process of writing this work up, but there are slides from a talk and a couple of publications available.

Publications

 

Code

The code for these estimators is available on my code page

 
ACVT Logo