  Most man-made environments, such as urban and indoor scenes, consist of a set
of parallel and orthogonal planar structures. These structures are approximated
by the Manhattan world assumption, in which notion can be represented as a
Manhattan frame (MF). Given a set of inputs such as surface normals or
vanishing points, we pose an MF estimation problem as a consensus set
maximization that maximizes the number of inliers over the rotation search
space. Conventionally, this problem can be solved by a branch-and-bound
framework, which mathematically guarantees global optimality. However, the
computational time of the conventional branch-and-bound algorithms is rather
far from real-time. In this paper, we propose a novel bound computation method
on an efficient measurement domain for MF estimation, i.e., the extended
Gaussian image (EGI). By relaxing the original problem, we can compute the
bound with a constant complexity, while preserving global optimality.
Furthermore, we quantitatively and qualitatively demonstrate the performance of
the proposed method for various synthetic and real-world data. We also show the
versatility of our approach through three different applications: extension to
multiple MF estimation, 3D rotation based video stabilization, and vanishing
point estimation (line clustering).
