We propose a novel method to solve online SLAM problems with many loop-closures on the basis of two state-of-the-art SLAM methods, iSAM and SPCG. We first use iSAM to solve a sparse sub-problem to obtain an approximate solution. When the error grows larger than a threshold or the optimal solution is requested, we use subgraph-preconditioned conjugate gradient method to solve the original problem where the subgraph preconditioner and initial estimate are provided by iSAM. Finally we use the optimal solution from SPCG to regularize iSAM in the next steps. The proposed method is consistent, efficient and can find the optimal solution. We apply this method to solve large simulated and real SLAM problems, and obtain promising results.

We present a simultaneous localization and mapping (SLAM) algorithm for a hand-held 3D sensor that uses both points and planes as primitives. We show that it is possible to register 3D data in two different coordinate systems using any combination of three point/plane primitives (3 planes, 2 planes and 1 point, 1 plane and 2 points, and 3 points). Our algorithm uses the minimal set of primitives in a RANSAC framework to robustly compute correspondences and estimate the sensor pose. As the number of planes is significantly smaller than the number of points in typical 3D data, our RANSAC algorithm prefers primitive combinations involving more planes than points. In contrast to existing approaches that mainly use points for registration, our algorithm has the following advantages: (1) it enables faster correspondence search and registration due to the smaller number of plane primitives; (2) it produces plane-based 3D models that are more compact than point-based ones; and (3) being a global registration algorithm, our approach does not suffer from local minima or any initialization problems. Our experiments demonstrate real-time, interactive 3D reconstruction of indoor spaces using a hand-held Kinect sensor.

Efficiently solving large-scale sparse linear systems is important for robot mapping and navigation. Recently, the subgraph-preconditioned conjugate gradient method has been proposed to combine the advantages of two reigning paradigms, direct and iterative methods, to improve the efficiency of the solver. Yet the question of how to pick a good subgraph is still an open problem. In this paper, we propose a new metric to measure the quality of a spanning tree preconditioner based on support theory. We use this metric to develop an algorithm to find good subgraph preconditioners and apply them to solve the SLAM problem. The results show that although the proposed algorithm is not fast enough, the new metric is effective and resulting subgraph preconditioners significantly improve the efficiency of the state-of-the-art solver.

We present a simultaneous localization and mapping (SLAM) algorithm for a hand-held 3D sensor that uses both points and planes as primitives. Our algorithm uses any combination of three point/plane primitives (3 planes, 2 planes and 1 point, 1 plane and 2 points, and 3 points) in a RANSAC framework to efficiently compute the sensor pose. As the number of planes is significantly smaller than the number of points in typical 3D scenes, our RANSAC algorithm prefers primitive combinations involving more planes than points. In contrast to existing approaches that mainly use points for registration, our algorithm has the following advantages: (1) it enables faster correspondence search and registration due to the smaller number of plane primitives; (2) it produces plane-based 3D models that are more compact than point-based ones; and (3) being a global registration algorithm, our approach does not suffer from local minima or any initialization problems. Our experiments demonstrate real-time, interactive 3D reconstruction of office spaces using a hand-held Kinect sensor.

We present a generalized subgraph preconditioning (GSP) technique to solve large-scale bundle adjustment problems efficiently. In contrast with previous work which uses either direct or iterative methods as the linear solver, GSP combines their advantages and is significantly faster on large datasets. Similar to [11], the main idea is to identify a sub-problem (subgraph) that can be solved efficiently by sparse factorization methods and use it to build a preconditioner for the conjugate gradient method. The difference is that GSP is more general and leads to much more effective preconditioners. We design a greedy algorithm to build subgraphs which have bounded maximum clique size in the factorization phase, and also result in smaller condition numbers than standard preconditioning techniques. When applying the proposed method to the “bal” datasets [1], GSP displays promising performance.

In this paper, we propose a new approach, appearance-guided particle filtering (AGPF), for high degree-of-freedom visual tracking from an image sequence. This method adopts some known attractors in the state space and integrates both appearance and motion-transition information for visual tracking. A probability propagation model based on these two types of information is derived from a Bayesian formulation, and a particle filtering framework is developed to realize it. Experimental results demonstrate that the proposed method is effective for high degree-of-freedom visual tracking problems, such as articulated hand tracking and lip-contour tracking.

This paper presents a novel motion segmentation algorithm on the basis of mixture of Dirichlet process (MDP) models, a kind of nonparametric Bayesian framework. In contrast to previous approaches, our method consider motion segmentation and its model selection regarding to the number of motion models as an indivisible problem. The proposed algorithm can simultaneously infer the number of motion models, estimate the cluster memberships of correspondence points, and identify the outliers of input data. The key idea is to use MDP models to fully exploit the epipolar constraints before making premature decisions about the number motion models. To handle outliers efficiently, we then incorporate RANSAC within the inference process of MDP models and make them take the advantages of each other. In the experiments, we compare the proposed algorithm with naive RANSAC, GPCA and Schindler's method on both synthetic data and real image data. The experimental results show that we can handle more motions and still have satisfactory performance in the presence of various levels of noise and outlier.

Belief propagation (BP) has been successfully used to solve many computer vision problems, such as stereo matching, object detection and low-level vision. Although the BP algorithm provides an efficient computation framework for general graph inference, the capability of BP is limited by the fact that it only considers the first-order constraints which can simply model the distance relation between two nodes. But in many computer vision problems, this limitation will bring on serious results when the differential or the angular constraints are inherent in the problems. To resolve this limitation, we generalize the BP algorithm to consider the second-order constraints, and integrate it into the particle filtering framework to speed up the computation. In addition, we apply the proposed method to develop a face localization algorithm to demonstrate its effectiveness.