Abstract

Rotation search is a fundamental problem which has significant importance in geometric computer vision. In many practical settings, data or measurements for rotation search are usually contaminated with large errors, leading to the existence of outliers in the data. As a consequence, traditional least-squares rotation estimation methods are not suitable in many practical applications. A more appropriate approach is to search for the rotation based on a robust criterion. However, optimisation problems involving robust criteria are hard to solve since the objective functions are usually non-differentiable and non-convex. This thesis makes several fundamental contributions in robust rotation search. In contrast to approximations or local methods that are typically used by current practitioners, the presented methods in this thesis guarantee global optimality. The main challenge for robust rotation search algorithms is to find an optimal result in reasonable time (to be practical in out-of-lab applications). The work in this thesis is a contribution in this direction. To efficiently solve robust rotation search, several strategies are presented based on new insights into the geometry of rotations, from the perspective of global optimisation. Firstly, for point set registration on horizontally levelled data, the presented algorithms make it possible to globally find the best rotation in real-time. Secondly, for the fully unconstrained 3D rotation search problem, the presented algorithms outperform previous methods by an order of magnitude. The final contribution of this thesis is an algorithm to safely remove true outliers when rotation is computed on outlier contaminated point correspondences. Substantial speed-up can be obtained when the proposed outlier removal is used as a preprocessor to globally optimal algorithms. Since no inliers are discarded, global optimality is guaranteed. The contributions in this thesis can impact on computer vision problems where rotation search is invoked as a subroutine. This thesis presents examples from 3D point cloud registration and image stitching.