Sparse Bundle Adjustment (SBA) is the standard method for optimizing a structure-from-motion problem in computer vision. With the success of Photosynth and similar systems for stitching together large collections of images [5] , attention has turned to the problem of making SBA more efficient. There are two typical usage patterns for SBA. In one, a set of images are taken of an object, so most of the images have features in common and the secondary structure is dense. For example, in the Venice dataset of tourist photos 1 , the density of H is 40%, that is, non-zeros account for 40% of the matrix entries. On the other end of the spectrum are datasets from visual mapping, where usually a single camera moves around an area, and the images are registered to produce an extended map. For example, in the Intel Seattle indoor dataset 2 , the camera motion is mostly along corridors, and the density is only 1.4%. The difference in the sparsity pattern is shown in Figure 1 . Note that the mapping pattern consists of a fat diagonal band, with some parallel bands for overlapping trajectories. (Guilbert et al. call these "sparse systems" [2]). In this paper, we are interested in fast SBA methods for the mapping case, where it is possible to exploit the sparse secondary structure (camera to camera relations) of the problem. Nonlinear optimization in SBA typically proceeds by iteration: form a linear subproblem around the current solution, solve it, and repeat until convergence. For large problems, the computational bottleneck is usually the solution of the linear subproblem, which can grow as the cube of the number of cameras. The fill-in of the linear problem is directly tied to the camera-point structure of the problem: if each camera only sees features in a small neighborhood of other cameras, the number of non-zero elements grows only linearly or nearly linearly with the number of cameras. The linear system is formed from the projection of points p onto cameras c. The linear equation can be written as: where J c is the Jacobian with respect to camera variables, and J p with respect to point variables. Because all the error functions involve one camera and one point, the Jacobian products J ⊤ c J c and J ⊤ p J p are blockdiagonal. After some manipulation, the reduced system is where H xy refers to the Jacobian products in Equation 1. Note the matrix inversion is simple because of the block-diagonal structure of H pp . Solving this equation produces an increment ∆c that adjusts the camera variables, and then is used to update the point variables according to In forming the left-hand side of Equation 2, the main computational bottleneck is computing the product H cp H −1 pp H pc . We are interested in large systems, where the number of camera variables ||c|| can be 10k or more (the largest real-world dataset we have used is about 3k poses, but we can generate synthetic datasets of any order). The number of system variables is 6 · ||c||, and the reduced system matrix of Equation 2 has size 36 · ||c|| 2 , or over 10 9 elements. Manipulating such large matrices is expensive. To do it efficiently, we have to take advantage of its sparse structure. The sparsity pattern of the reduced SBA system is referred to as secondary structure. The most compute-intensive part of creating H involves an outer product over the projections in each point track (for details of the whole algorithm, see Engels et al. [1] ). In our version of this algorithm, we create a sparse structure for accessing arbitrary 6x6 blocks i, j of H. We use a C++ std::map container for each column of H. The map is keyed by row
REF introduced Sparse SBA (sSBA) which exploits the sparse secondary structure of sparse camera to camera relations, which increases computational and memory efficiency.
Sparse Sparse Bundle Adjustment
BMVC
Computer Science