L1 rotation averaging using the Weiszfeld algorithm
Richard I. Hartley, Khurrum Aftab, Jochen Trumpf · 2011
We consider the problem of rotation averaging under the L1norm. This problem is related to the classic Fermat-Weber problem for finding the geometric median of a set of points in IRn. We apply the classical Weiszfeld algorithm to this problem, adapting it iteratively in tangent spaces of SO(3) to obtain a provably convergent algorithm for finding the L1mean. This results in an extremely simple and rapid averaging algorithm, without the need for line search. The choice of L1mean (also called geometric median) is motivated by its greater robustness compared with rotation averaging under the L2norm (the usual averaging process). We apply this problem to both single-rotation averaging (under which the algorithm provably finds the global L1optimum) and multiple rotation averaging (for which no such proof exists). The algorithm is demonstrated to give markedly improved results, compared with L2averaging. We achieve a median rotation error of 0.82 degrees on the 595 images of the Notre Dame image set.