If you reached this page while looking for a general-purpose Levenberg-Marquardt C/C++ implementation, please have a look at sparseLM and levmar, which are respectively aimed at problems with sparse and dense Jacobians.

# Introduction

This site concerns `sba`, a C/C++ package for generic sparse bundle adjustment that is distributed
under the GNU General Public License (GPL).
Bundle Adjustment (BA) is almost invariably
used as the last step of every feature-based multiple view
reconstruction vision algorithm to obtain optimal 3D structure and motion (i.e. camera matrix)
parameter estimates. Provided with initial estimates, BA simultaneously refines motion and structure
by minimizing the reprojection error between the observed and predicted image points. The minimization
is typically carried out with the aid of the Levenberg-Marquardt
(LM) algorithm. However, due to the large number of unknowns contributing to the minimized reprojection error,
a general purpose implementation of the LM algorithm (such as MINPACK's
`lmder`) incurs high computational costs when applied to the minimization problem defined in the context of BA.

Fortunately, the lack of interaction among parameters for different 3D points and cameras results in the underlying
normal equations exhibiting a sparse block structure (click here for an example).
`sba` exploits this sparseness by employing a tailored sparse variant of the LM algorithm that leads to
considerable computational gains. `sba` is generic in the sense that it grants the user full control over
the definition of the parameters describing cameras and 3D structure. Therefore, it can support virtually any
manifestation/parameterization of the multiple view reconstruction problem such as arbitrary projective cameras,
partially or fully intrinsically calibrated cameras, exterior orientation (i.e. pose) estimation from fixed 3D
points, refinement of intrinsic parameters, etc. All the user has to do to adapt `sba` to any such problem
is to supply it with appropriate routines for computing the estimated image projections and their Jacobian for the
problem and parameterization at hand. Routines for computing analytic Jacobians can be either coded by hand, generated
with a tool supporting symbolic differentiation (e.g. maple), or obtained
using automatic differentiation techniques. There is also the alternative
of approximating Jacobians with the aid of finite differences. Additionally, `sba` includes routines for
checking the consistency of user-supplied Jacobians. To the best of our knowledge, `sba` is the first
and currently the only software package of its kind to be released as free software.

# Overview

`sba` has been implemented with special emphasis on flexibility and performance efficiency.
It is, in essence, a specialized LM variant that is tailored to fit the “arrowhead”
type of sparseness commonly encountered in SfM problems. To achieve this, `sba` employs a
scheme that partitions the normal matrix into distinct camera and structure blocks and solves the (sparse)
normal equations by employing the sparse Schur
complement of the points submatrix. By adopting this scheme, `sba` can effectively deal with very
large reconstruction problems. Further details regarding the theory behind `sba` can be found
in the documentation.

As an indication of its efficiency, it is noted here that one of the moderately-sized test problems to
which `sba` has been applied involved **54** cameras and **5207** 3D points that gave rise
to **24609** image projections. The corresponding minimization problem depended on **15999** variables
and was solved by `sba` in about 7 sec using unoptimized BLAS on an Intel P4@1.8 GHz running Linux.
Without a sparse implementation of BA, a problem of this size would simply be intractable.

`sba` relies on LAPACK for all linear algebra operations
arising in the course of the LM algorithm. If LAPACK (or an equivalent vendor optimized library such as
Intel's MKL, AMD's AMCL, Sun's performance library, IBM's ESSL, SGI's SCSL, NAG, ...), is not available,
it is suggested to install CLAPACK, the f2c'ed version of LAPACK.
Under MSWin, there is the additional option of downloading precompiled 32 bit LAPACK/BLAS libraries from
here. For better performance,
ATLAS or
GotoBLAS, respectively the
automatically tuned BLAS implementation and K. Goto's high-performance BLAS, are recommended.
Apart from LAPACK & BLAS though, `sba` requires no other third party libraries.
A MEX-file interface for using `sba` from within
matlab is also available. It will probably work
with GNU octave as well but this has not been tested.

# Documentation

Detailed descriptions of the theory behind `sba` can be found in the correspondind ACM TOMS
paper (bibtex entry)
or the (somewhat outdated) 2004 ICS/FORTH Technical Report #340 entitled *The Design and Implementation of
a Generic Sparse Bundle Adjustment Software Package Based on the Levenberg-Marquardt Algorithm*.
An overview presentation of `sba` and BA can be found in these
slides.

Sparse BA is also discussed in Appendix 6 of Hartley & Zisserman's book.

# Available Functions

User-callable functions offered by `sba` obey the following naming convention: All functions are prefixed
by `sba_`; the string following this prefix specifies whether the function implements full or partial (i.e.,
motion or structure only) BA. To cater for different user needs, expert and simple drivers to sparse bundle adjustment
have been developed; expert drivers are distinguished by the existence of the `_x` suffix in a function's name.
More specifically, `sba` includes the functions below:

`sba_motstr_levmar()`,`sba_motstr_levmar_x()`:- Resp. simple and expert driver for full motion and structure BA.

`sba_mot_levmar()`,`sba_mot_levmar_x()`:- Resp. simple and expert driver for motion only BA. Strictly speaking, this is not BA since structure is kept unmodified. However, this function is very useful when dealing with problems involving camera resectioning, i.e. pose estimation from known 3D-2D correspondences.

`sba_str_levmar()`,`sba_str_levmar_x()`:- Resp. simple and expert driver for structure only BA. Again, this is not real BA since motion is kept unmodified. This function can, for example, be useful when dealing with intersection problems, i.e. reconstructing 3D points seen in a set of extrinsically calibrated images.

The exact prototype of `sba_motstr_levmar_x()` is given next for reference, along with a description of
each of its arguments. I and O in these descriptions denote input and output arguments, respectively.
Motion and structure only BA routines have very similar arguments. Consult Madsen
et al's lecture notes
for details on the roles of `opts` and `info` arguments. Argument `adata` is
intended to help avoid direct use of globals in the routines computing the image projection function
and its Jacobian. A structure containing pointers to appropriate data structures can be set
up and a pointer to it can be passed to the BA function which then passes it uninterpreted to each
call of the user-supplied routines. More accurate argument descriptions can be found in the
documentation, whereas Madsen et al's
lecture notes
provide more details on the LM algorithm implemented by `sba`.
Also included in `sba`'s distribution is a sample program (i.e., `eucsbademo.c`),
that provides an example of using `sba` for various flavors of Euclidean BA.

`sba_motstr_levmar_x()`

```
.:: toggle display ::.
```

Examples of practical uses of `sba` are included in the demo pages on
camera tracking
and
localization of unordered panoramic images.

# Contact Address

If you find `sba` useful in your research or have any comments/questions/suggestions, please contact
me at

Be warned that although I try to reply to most messages, I might take long to do so.

In case that you use `sba` in your published work, please include a reference to this paper:
[ bibtex entry ].

hits since Thu Nov 10 15:23:31 EET 2005