Schur Complement for Bundle Adjustment #407
Comments
|
The default configuration uses METIS to compute the ordering used for elimination. The resulting orderings have the same asymptotic complexity as the Schur complement trick (linear in the number of 3D points in the problem), so it should be pretty fast and it'll scale as you expect with the numbers of poses and points, same as if you were explicitly using the Schur complement trick For really big problems there are other tricks you can use and lots of linear solvers to choose from; the linear solver is a template parameter that you can change to any solver that implements the interface SymForce expects for linear solvers; for example, you can use any of Eigen's sparse linear solvers with the wrapper in eigen_sparse_solver.h, or you could plug in a solver from another library by implementing a similar adapter. |
|
Thank you for your answer. Have you been able to compare against g2o in your experiments and is this difference something you have observed? Or on the contrary have you seen that symforce was faster, suggesting an error on my side? Thank you |
|
It would help if you could post more detailed timing for what part of the iteration time is slower; there are very different reasons depending on that. SymForce should print a table on exit of timing for different parts of the optimization problem; I haven't used g2o much so I'm not sure what timing information they have available |
|
Thanks for your answer, here are the detailed timings for symforce on my BA graph with the following cost changes: Sadly g2o does not provide detailed timings like symforce, only time per iteration: Symforce converges to an error of 23290 while g2o converges to 46572, because g2o reports the sum of the squared residuals without multiplying by 1/2 so they both converge to very close points. I've also run experiments on datasets from bundle adjustment in the large using the example code provided here for symforce and here for g2o. I deactivated the outlier camera filtering in the example of symforce and used only small problems to ensure good initialisation of camera poses. G2o: On problem 39-18060-pre.txt: G2o: On problem 21 g2o converges to 60758 in 2.12s while symforce converges to 30380 in 2.27s, the convergence is similar and the speed is similar. However contrary to symforce g2o does not implement the analytic computation of Jacobians and they rely on numerical differentiation (see their edge definition), I would expect a speed up from the implementation. |
|
So afaict the difference is that g2o has a specialized schur complement implementation, see here: https://github.com/RainerKuemmerle/g2o/blob/eec325a1da1273e87bc97887d49e70570f28570c/g2o/core/block_solver.hpp Best I can tell, their use of CHOLMOD is just for doing sparse cholesky, and CHOLMOD's sparse cholesky should have very similar performance to SymForce's (CHOLMOD also has other solvers, but I believe sparse cholesky is the one we're talking about). In this case though, they're forming the schur complement with a specialized implementation, which will have essentially the same asymptotic complexity as SymForce using METIS and our sparse cholesky, but will be some amount faster in practice (I'm not sure how much exactly). They also support doing this in parallel with OpenMP, not sure if that's enabled in your tests, but that'll also make things faster. It might be interesting to add an explicit schur complement solver to SymForce - we actually have one already in |
Hi, first of all thanks for your amazing work!
I'm using symforce to solve classical bundle adjustment with 6 DoF poses, 3D points and projection factors. The optimization works as expected, however is the Schur Complement trick used automatically or do I need to do something to enable it to speed up the optimisation?
Thank you
The text was updated successfully, but these errors were encountered: