Globally Optimal Line Clustering and Vanishing Point Estimation in Manhattan World

The projections of world parallel lines in an image inter-sect at a single point called the vanishing point (VP). VPs are a key ingredient for various vision tasks including rota-tion estimation and 3D reconstruction. Urban environments generally exhibit some dominant orthogonal VPs. Given a set of lines extracted from a calibrated image, this paper aims to (1) determine the line clustering, i.e. find which line belongs to which VP, and (2) estimate the associated orthogonal VPs. None of the existing methods is fully sat-isfactory because of the inherent difficulties of the problem, such as the local minima and the chicken-and-egg aspect. In this paper, we present a new algorithm that solves the problem in a mathematically guaranteed globally optimal manner and can inherently enforce the VP orthogonality. Specifically, we formulate the task as a consensus set max-imization problem over the rotation search space, and fur-ther solve it efficiently by a branch-and-bound procedure based on the Interval Analysis theory. Our algorithm has been validated successfully on sets of challenging real im-ages as well as synthetic data sets. 1