nips nips2002 nips2002-137 nips2002-137-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ali Rahimi, Trevor Darrell
Abstract: Given a set of hidden variables with an a-priori Markov structure, we derive an online algorithm which approximately updates the posterior as pairwise measurements between the hidden variables become available. The update is performed using Assumed Density Filtering: to incorporate each pairwise measurement, we compute the optimal Markov structure which represents the true posterior and use it as a prior for incorporating the next measurement. We demonstrate the resulting algorithm by calculating globally consistent trajectories of a robot as it navigates along a 2D trajectory. To update a trajectory of length t, the update takes O(t). When all conditional distributions are linear-Gaussian, the algorithm can be thought of as a Kalman Filter which simplifies the state covariance matrix after incorporating each measurement.
[1] A. Stoddart and A. Hilton. Registration of multiple point sets. In IJCV, pages B40–44, 1996. (a) (b) Figure 3: Left, naive accumulation (green) and projecting trajectory to diagonal covariance (red). Loops are not closed well, and trajectory is not smooth. The zoomed areas show that in both naive approaches, there are large jumps in the trajectory, and the pose estimate is incorrect at revisited locations. Right, Differential Update Network (blue) and exact solution (black). Like the batch solution, our solution generates smooth and consistent trajectories.
[2] Y. Chen and G. Medioni. Object modelling by registration of multiple range images. In Porceedings of the IEEE Internation Conference on Robotics and Authomation, pages 2724–2728, 1991.
[3] F. Lu and E. Milios. Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4:333–349, 1997.
[4] J. Gutmann and K. Konolige. Incremental mapping of large cyclic environments. In IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), 2000.
[5] Harpreet S. Sawhney, Steve Hsu, and Rakesh Kumar. Robust video mosaicing through topology inference and local to global alignment. In Proc ECCV 2, pages 103–119, 1998.
[6] H.-Y. Shum and R. Szeliski. Construction of panoramic mosaics with global and local alignment. In IJCV, pages 101–130, February 2000.
[7] A. Shashua. Trilinearity in visual recognition by alignment. In ECCV, pages 479–484, 1994.
[8] C. Tomasi and T. Kanade. Shape and motion from image streams under orthography: A factorization approach. International Journal of Computer Vision, 9(2):137–154, 1992.
[9] Olivier Faugeras. Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press, Cambridge, Massachusetts, 1993.
[10] M. Harville, A. Rahimi, T. Darrell, G.G. Gordon, and J. Woodfill. 3d pose tracking with linear depth and brightness constraints. In ICCV99, pages 206–213, 1999.
[11] Feng Lu and E. Milios. Robot pose estimation in unknown environments by matching 2d range scans. Robotics and Autonomous Systems, 22(2):159–178, 1997.
[12] P. J. Besl and N. D. McKay. A method for registration of 3-d shapes. IEEE Trans. Patt. Anal. Machine Intell., 14(2):239–256, February 1992.
[13] N. Ayache and O. Faugeras. Maintaining representations of the environment of a mobile robot. IEEE Tran. Robot. Automat., 5(6):804–819, 1989.
[14] Y. Liu, R. Emery, D. Chakrabarti, W. Burgard, and S. Thrun. Using EM to learn 3D models of indoor environments with mobile robots. In IEEE International Conference on Machine Learning (ICML), 2001.
[15] R. Smith, M. Self, and P. Cheeseman. Estimating uncertain spatial relationships in robotics. In Uncertainity in Artificial Intelligence, 1988.
[16] T.P. Minka. Expectation propagation for approximate bayesian inference. In UAI, 2001.
[17] X. Boyen and D. Koller. Tractable inference for complex stochastic processes. In Uncertainty in Artificial Intelligence, 1998.
[18] T.P. Minka. Independence diagrams. Technical http://www.stat.cmu.edu/˜minka/papers/diagrams.html, 1998. report, Media Lab,
[19] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1997.
[20] A. Rahimi, L-P. Morency, and T. Darrell. Reducing drift in parametric motion tracking. In ICCV, volume 1, pages 315–322, June 2001.
[21] T. Kailath, A. H. Sayed, and B. Hassibi. Linear Estimation. Prentice Hall, 2000.
[22] E. Sudderth. Embedded trees: Estimation of gaussian processes on graphs with cycles. Master’s thesis, MIT, 2002.
[23] Philip F. McLauchlan. A batch/recursive algorithm for 3d scene reconstruction. Conf. Computer Vision and Pattern Recognition, 2:738–743, 2000.
[24] B. D. Lucas and Takeo Kanade. An iterative image registration technique with an application to stereo vision. In International Joint Conference on Artificial Intelligence, pages 674–679, 1981.
[25] Andrew W. Fitzgibbon and Andrew Zisserman. Automatic camera recovery for closed or open image sequences. In ECCV, pages 311–326, 1998.