Well-Posed by Design - Spectral Clustering for Rotation Averaging

We present a two-stage pipeline for rotation averaging that leverages spectral clustering to partition the camera graph into well-connected subgraphs. We develop and apply a spectral-clustering algorithm to group cameras enforcing high algebraic connectivity within and across subgraphs, and thus promote well-posed rotation averaging problems. After solving rotation averaging independently within each cluster, we aggregate the inter-cluster relative rotations into a compact supergraph and solve a final rotation averaging problem on this supergraph to recover globally consistent camera orientations. Experiments on two real-world datasets demonstrate that our clustering algorithm is able to identify spatial properties as well as more nuanced features in the data. Moreover, the full pipeline is able to almost halve total computation time on a medium-sized dataset while incurring only a modest error increase.