# sba

1,255 downloads

sba is a generic sparse bundle adjustment C/C++ package based on the levenberg-marquardt algorithm.

sba is a generic sparse bundle adjustment C/C++ package based on the levenberg-marquardt algorithm.

This page 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 this 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 placed in the public domain in source form.

As an indication of its efficiency, it is noted here that one of the 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 9 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 offers the following user-callable functions:

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.

More details can be found in ICS/FORTH Technical Report No. 340.

sba has been implemented with special emphasis on flexibility and performance efficiency. It relies on LAPACK for solving the augmented normal equations arising in the course of the LM algorithm. If LAPACK (or an equivalent vendor optimized library such as Sun's performance library, IBM's ESSL, Intel's MKL, SGI's SCSL, NAG, ...), is not available at your site, it is suggested to install CLAPACK, the f2c'ed version of LAPACK. Under MSWin, there is the additional option of downloading precompiled LAPACK/BLAS libraries from here. If performance is a concern, ATLAS or GotoBLAS, respectively the automatically tuned BLAS implementation and K. Goto's high-performance BLAS should be useful. Apart from LAPACK 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.

· Support was added for including the covariance matrices of the image projections in the optimization.

· This feature provides the option of weighting the reprojection errors with the inverses of the point covariances.

· The memory requirements of sba_motstr_levmar_x() were reduced further by using the same memory to store the matrices V* and V*-1. Any working memory retained between invocations of the linear solvers is now ensured to be released upon the termination of all sba routines.

This page 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 this 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 placed in the public domain in source form.

As an indication of its efficiency, it is noted here that one of the 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 9 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 offers the following user-callable functions:

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.

More details can be found in ICS/FORTH Technical Report No. 340.

sba has been implemented with special emphasis on flexibility and performance efficiency. It relies on LAPACK for solving the augmented normal equations arising in the course of the LM algorithm. If LAPACK (or an equivalent vendor optimized library such as Sun's performance library, IBM's ESSL, Intel's MKL, SGI's SCSL, NAG, ...), is not available at your site, it is suggested to install CLAPACK, the f2c'ed version of LAPACK. Under MSWin, there is the additional option of downloading precompiled LAPACK/BLAS libraries from here. If performance is a concern, ATLAS or GotoBLAS, respectively the automatically tuned BLAS implementation and K. Goto's high-performance BLAS should be useful. Apart from LAPACK 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.

**What's New**in This Release:· Support was added for including the covariance matrices of the image projections in the optimization.

· This feature provides the option of weighting the reprojection errors with the inverses of the point covariances.

· The memory requirements of sba_motstr_levmar_x() were reduced further by using the same memory to store the matrices V* and V*-1. Any working memory retained between invocations of the linear solvers is now ensured to be released upon the termination of all sba routines.

Last updated on September 1st, 2009

## 0 User reviews so far.

SUBMIT