A Scalable Projective Bundle Adjustment Algorithm using the L infinity Norm

The traditional bundle adjustment algorithm for structure from motion problem has a computational complexity of O((m+n)³) per iteration and memory requirement of O(mn(m+n)), where m is the number of cameras and n is the number of structure points. The sparse version of bundle adjustment has a computational complexity of O(m³+mn) per iteration and memory requirement of O(mn). Here we propose an algorithm that has a computational complexity of O(mn(radicm+radicn)) per iteration and memory requirement of O(max(m,n)). The proposed algorithm is based on minimizing the L_infin norm of reprojection error. It alternately estimates the camera and structure parameters, thus reducing the potentially large scale optimization problem to many small scale subproblems each of which is a quasi-convex optimization problem and hence can be solved globally. Experiments using synthetic and real data show that the proposed algorithm gives good performance in terms of minimizing the reprojection error and also has a good convergence rate.