Integration

In Chapter 3, partitions of the parameter vector p have been discussed for bundle adjustment with joined intrinsic parameters and for bundle adjustment with a stereo camera model. In the latter case, componentsa₂,a₃, anda₄ have been introduced to

56

4.4 Reparametrization using Euclidean Transformations

accommodate the parameters of the camera model. It may be observed, however, that these parameters obey the same overall structure as the extrinsic camera parameters a0, albeit with two notable differences: First, the individual components do not need full Euclidean transformations for their description. And second, the parameters are not independent. To combine all these subvectors into a₀, one has to be prepared to increase the size of the matrixU, accept entries for off-diagonal blocks, and to eliminate rows and columns not participating in the optimization before Cholesky decomposition.

One may thus treat hierarchies of Euclidean transformations in bundle adjustment by using a parameter vector

p=a^>₀,a^>₁,b^>> , (4.6) with a₀ being the parameters of all Euclidean transformations, a₁ being all intrinsic camera parameters. The matrix J^>Jmay hence be given as

J^>J=

In the presence of distortion, one may introduce an additional elementa2 compris-ing all distortion parameters into p. This introduces additional blocks in the overall structure, but the overall process remains unaffected.

The requirements outlined above are a concession made to complexity and perfor-mance: If all Euclidean transformations are handled the same, regardless of their actual number of degrees of freedom, the description and implementation becomes easier, and the uniformity may be exploited to gain performance increases.

Block Structure For traditional bundle adjustment, the matrixU, which corresponds to the matrix U₀₀ here, was block diagonal (the blocks being of size 6×6 for the number of degrees of freedom of a Euclidean transformation). As mentioned above, this only holds if all Euclidean transformations are independent (implicating that they only describe extrinsic camera parameters and not some sort of constraint). If a more complex camera model or scene constraints are introduced, additional off-diagonal blocks will be created, depending on the structure of the problem. An illustration of this is shown in Figure 4.2.

The structure of the matrixVis largely unaffected. If 3D object points are constrained, however, the appropriate rows and columns have to be eliminated before inversion.

The block structure of all other matrices depends on the particular scene, ranging from small, dense matrices in case of joined intrinsic parameters for image sequences to large sparse matrices for high variety of intrinsic parameters in the input data.

Chapter 4 A Generalized Framework for Constrained Bundle Adjustment

Euclidean J^>J Lagrange J^>J

Figure 4.2: Structure of the matrixJ^>JforEuclideanandLagrangegiven a toy example with three cameras and four 3D object points that are constrained to be coplanar. The corresponding block structure for unconstrained optimization can be found in Figure 2.7. Blue blocks denote values corresponding to the extrinsic camera parameters, gray to the (shared) intrinsic camera parameters, and yellow to the 3D object point parameters. Red blocks arise from the respective type of constraints. ForEuclidean, the 3D object points only have two parameters, whereas the problem size is actually increased forLagrange.

Implementation To accommodate the updated camera matrices from Equation (4.5), which contain a sequence of camera and point transformations instead of only a single transformation for the unconstrained case, the size of the matrixU₀₀is simply increased.

For each Euclidean transformation, an additional row and column of blocks is added.

The matricesU₀₁ and W₀ are treated in the same way.

Although there are essentially 6 parameters added for each Euclidean transforma-tion, not all constraints require as many (see Table 4.1). However, to simplify the implementation, all Euclidean transformations are assumed to require the full range of parameters. To accommodate this situation, the partial derivatives of translation and rotation parameters that are not part of the constraint description are set to 0. Further-more, the corresponding rows are eliminated after the construction of U₀₀−W^>₀V⁻¹W₀, before Cholesky factorization. In addition to being easier to implement, this strategy has the benefit of allowing more opportunities for optimization to modern compilers, since all matrices in the individual blocks are of the same, known size.

58

4.4 Reparametrization using Euclidean Transformations

Consequences Adding the constraints to U₀₀ does not come without consequences.

Since there are dependencies between a single constraint and multiple cameras, and between the constraints themselves, off-diagonal entries are created (see Figure 4.2).

But the sparse structure of U₀₀ breaks down in any case during the application of the Schur complement trick for the solution of the overall system. For applications relying on dense matrix factorization routines, the impact may be entirely negligible; when sparse factorization routines are used, the impact on the performance may depend on the actual structure of the problem examined. Regardless, this only holds if the number of constraints is small in comparison to the number of cameras. If the number of constraints is large, the increase in computation time may be significant. In such a case, it may be beneficial to reorder the constraints in a way that allows the block-wise inversion of U₀₀, much like it is done with V.

Derivative Calculation The calculation of the derivatives with respect to a single constraint (or rather, Euclidean transformation) can be implemented in a generic way.

To this end, for a given sequence of transformations, all transformations preceding the current one are collapsed to a single 3×4 matrix, while the effect of all subsequent transformations is collapsed to a single point. The calculation is then done in an iterative fashion over all transformations associated with the current camera and 3D object point. An example for this is provided in the next section.