Abstract
Estimating uncertainty of an estimated 3D point from a set of images is an essential problem for many applications such as Simultaneous Localization and Mapping, image mosaicking, and Structure from Motion. In this paper, we present a novel method to identify the uncertainty of a triangulated point from a set of views. For each image measurement of a 3D point, we model the measurement uncertainty as a cone originating from the camera center. The triangulation uncertainty is, therefore, the intersection of cones. Since the true location is assumed to only contain within the uncertainty cone, the 3D point does not necessarily lie on the bisectors of the cones. Therefore, we also provide a worst-case analysis of the triangulation error represented as the diameter of the intersections among cones and show that two good views can obtain a near-optimal triangulation error comparing to all possible views from an entire viewing plane. The novelty of our approach is two folds. First, we represent the uncertainty region of a 3D point as the intersections of cones with only bounded pixel error. Thus, there are no additional assumptions imposed on the image noise such as modeling the pixel noise as a Gaussian distribution. Second, our worst-case analysis provides a strong performance bound (near-optimal) on the possible deviations from the ground truth. We also extend our uncertainty analysis to view selection and propose a coarse-to-fine view selection algorithm to reduce the number of views required for high-quality reconstruction of non-planar scenes. We validate our view selection algorithm in 5 different scenes and show a significant reduction in processing time without sacrificing the qualities for both image mosaicking and Structure from Motion.