Next: Bibliography Up: Bundle adjustment Previous: Levenberg-Marquardt iteration   Contents

The observed points being fixed, a specific residual is only dependent on the point -th point and the -th projection matrix. This results in a very sparse matrix for the Jacobian. This is illustrated in figure A.1 for 3 views and 4 points.

Because of the block structure of the Jacobian solving the normal equations have a structure as seen in figure A.2.
It is possible to write down explicit formulas for each block. Let us first introduce the following notation:
 (A5) (A6) (A7) (A8) (A9)

with and matrices containing the partial derivatives from the coordinates of to the parameters of and respectively. In this case the normal equations can be rewritten as
 (A10)

where the matrices and are composed of the blocks defined previously. Assuming is invertible both sides of equation A.10 multiplied on the left with

to obtain
 (A11)

This can be separated in two groups of equations. The first one is
 (A12)

and can be used to solve for . The solution can be substituted in the other group of equations:
 (A13)

Note that due to the sparse block structure of its inverse can be computed very efficiently.

The only computationally expensive step consist of solving equation A.12. This is however much smaller than the original problem. For 20 views and 2000 points the problem is reduced from solving 6000 unknowns concurrently to more or less 200 unknowns. To simplify the notations the normal equations were used in this presentation. It is however simple to extend this to the augmented normal equations.

Next: Bibliography Up: Bundle adjustment Previous: Levenberg-Marquardt iteration   Contents
Marc Pollefeys 2002-11-22