In this paper we describe a relative approach to simultaneous localization and mapping, based on the insight that a continuous relative representation can make the problem tractable at large scales. First, it is well known that bundle adjustment is the optimal non-linear least-squares formulation for this problem, in that its maximum-likelihood form matches the definition of the Cramer—Rao lower bound. Unfortunately, computing the maximum-likelihood solution is often prohibitively expensive: this is especially true during loop closures, which often necessitate adjusting all parameters in a loop. In this paper we note that it is precisely the choice of a single privileged coordinate frame that makes bundle adjustment costly, and that this expense can be avoided by adopting a completely relative approach. We derive a new relative bundle adjustment which, instead of optimizing in a single Euclidean space, works in a metric space defined by a manifold. Using an adaptive optimization strategy, we show experimentally that it is possible to solve for the full maximum-likelihood solution incrementally in constant time, even at loop closure. Our approach is, by definition, everywhere locally Euclidean, and we show that the local Euclidean estimate matches that of traditional bundle adjustment. Our system operates online in realtime using stereo data, with fast appearance-based loop closure detection. We show results on over 850,000 images that indicate the accuracy and scalability of the approach, and process over 330 GB of image data into a relative map covering 142 km of Southern England. To demonstrate a baseline sufficiency for navigation, we show that it is possible to find shortest paths in the relative maps we build, in terms of both time and distance. Query images from the web of popular landmarks around London, such as the London Eye or Trafalgar Square, are matched to the relative map to provide route planning goals.
Agarwal, S., Snavely, N., Simon, I., Seitz, S.M. and Szeliski, R. ( 2009). Building Rome in a day. IEEE International Conference on Computer Vision.
2.
Bosse, M.C., Newman, P.M., Leonard, J.J. and Teller., S. ( 2004). SLAM in large-scale cyclic environments using the Atlas framework. The International Journal of Robotics Research , 23(12): 1113-1139.
3.
Brooks, R. ( 1985). Visual map making for a mobile robot. IEEE International Conference on Robotics and Automation.
4.
Brown, D. ( 1958). A Solution to the General Problem of Multiple Station Analytical Stereotriangulation. Technical Report, RCP-MTP Data Reduction Technical Report No. 43, Patrick Air Force Base, Florida (also designated as AFMTC 58-8) .
5.
Choset, H. and Nagatani, K. ( 2001). Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 17: 125-137.
6.
Cummins, M. ( 2009). Probabilistic Localization and Mapping in Appearance Space. PhD thesis, University of Oxford.
7.
Cummins, M. and Newman, P. ( 2007). Probabilistic appearance based navigation and loop closing . IEEE Conference on Robotics and Automation.
8.
Cummins, M. and Newman, P. ( 2008). FAB-MAP: probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research, 27(6): 647-665.
9.
Davison, A., Reid, I., Molton, N. and Stasse, O. ( 2007). MonoSLAM: Realtime single camera SLAM. IEEE Transactions Pattern Analysis and Machine Intelligence, 29(6): 1113-1139.
10.
Deans, M.C. ( 2005). Bearings-Only Localization and Mapping. PhD thesis, School of Computer Science, Carnegie Mellon University.
11.
Dellaert, F. ( 2005). Square root SAM. Proceedings of Robotics: Science and Systems, pp. 1181-1203.
12.
Eade, E. and Drummond, T. ( 2008). Unified loop closing and recovery for real time monocular SLAM. Proceedings of the British Machine Vision Conference.
13.
Engels, C., Stewenius, H. and Nister, D. ( 2006). Bundle adjustment rules. Photogrammetric Computer Vision.
14.
Eustice, R., Singh, H., Leonard, J., Walter, M., and Ballard, R. ( 2005). Visually navigating the RMS Titanic with SLAM information filters. Proceedings of Robotics: Science and Systems , pp. 57-64.
15.
Fischler, M.A. and Bolles, R.C. ( 1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24: 381-395.
16.
Fitzgibbon, A.W. and Zisserman, A. ( 2004). Automatic Camera Recovery for Closed or Open Image Sequences . Berlin, Springer.
17.
Fraundorfer, F., Engels, C. and Nister, D. ( 2007). Topological mapping, localization and navigation using image collections. IEEE/RSJ International Conference on Intelligent Robots and Systems.
18.
Goedem’e, T., Nuttin, M., Tuytelaars, T. and Gool, L.V. ( 2007). Omnidirectional vision based topological navigation. International Journal of Computer Vision, 74(3): 219- 236.
19.
Grisetti, G., Stachniss, C., Grzonka, S. and Burgard, W. ( 2007). A tree parameterization for efficiently computing maximum likelihood maps using gradient descent. Proceedings of Robotics: Science and Systems.
20.
Guivant, J. and Nebot, E. ( 2001). Optimization of the simultaneous localization and map-building algorithm for realtime implementation. IEEE Transactions on Robotics and Automation, 17(3): 242-257.
21.
Harris, C. and Stephens, M. ( 1988). A combined corner and edge detector. Proceedings of The Fourth Alvey Vision Conference, Manchester , pp. 147-151.
22.
Hartley, R. and Zisserman, A. ( 2000). Multiple View Geometry in Computer Vision. Cambridge, Cambridge University Press.
23.
Holmes, S.A., Sibley, G., Klein, G., and Murray, D.W. ( 2009). A relative frame representation for fixed-time bundle adjustment in monocular SFM. Proceedings IEEE International Conference on Robotics and Automation.
24.
Howard, A. ( 2008). Real-time stereo visual odometry for autonomous ground vehicles. IEEE Conference on Robots and Systems (IROS).
25.
Howard, A., Sukhatme, G.S. and Mataric, M.J. ( 2006). Multirobot simultaneous localization and mapping using manifold representations. Proceedings of the IEEE, 94(7): 1360- 1369.
26.
Huber, P.J. ( 1964). Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(2): 73- 101.
27.
Kaess, M. ( 2008). Incremental Smoothing and Mapping. PhD Thesis, Georgia Institute of Technology.
28.
Kaess, M., Ranganathan, A. and Dellaert, F. ( 2008). iSAM: Incremental smoothing and mapping. IEEE Transactions on Robotics and Automation, 244(6): 1365-1378.
29.
Klein, G. and Murray, D. ( 2008). Improving the agility of keyframe-based SLAM. European Conference on Computer Vision.
30.
Konolige, K. and Agrawal, M. ( 2008). FrameSLAM: From Bundle Adjustment to Real-Time Visual Mapping. IEEE Transactions on Robotics and Automation, IEEE Journal of Robotics and Automation, International Journal of Robotics Research , 24(5): 1066-1077.
31.
Krauthausen, P., Dellaert, F. and Kipp, A. ( 2006). Exploiting locality by nested dissection for square root smoothing and mapping. Proceedings of Robotics: Science and Systems.
32.
Kuipers, B. and Byun, Y. ( 1988). A robust qualitative method for spatial learning in unknown environments. Proceedings of the National Conference on Artificial Intelligence.
33.
Lowe, D. ( 2004). Distinctive image features from scale-invariant keypoints . International Journal of Computer Vision, 60(2): 91-110.
34.
Martinelli, A., Nguyen, V., Tomatis, N. and Siegwart, R. ( 2007). A relative map approach to SLAM based on shift and rotation invariants. Robotics and Autonomous Systems, 55(1): 50-61.
35.
McLauchlan, P.F. ( 1999). The Variable State Dimension Filter Applied to Surface-based Structure from Motion. Technical Report, University of Surrey.
36.
Mei, C., Benhimane, S., Malis, E. and Rives, P. ( 2008). Efficient homography-based tracking and 3-d reconstruction for single-viewpoint sensors. IEEE Transactions on Robotics and Automation, 24(6): 1352-1364.
37.
Mei, C., Sibley, G., Cummins, M., Reid, I. and Newman, P. ( 2009). A constant-time efficient stereo SLAM system. Proceedings of the British Machine Vision Conference.
38.
Mikhail, E.M. ( 1983). Observations and Least Squares. Row-man & Littlefield.
39.
Mouragnon, E., Lhuillier, M., Dhome, M., Dekeyse, F. and Sayd, P. ( 2006). Real time localization and 3d reconstruction. Proceedings of Computer Vision and Pattern Recognition.
40.
Newman, P., Sibley, G., Smith, M., Cummins, M., Harrison, A., Mei, C., Posner, I., Shade, R., Schroeter, D., Murphy, L., Churchill, W., Cole, D. and Reid, I. ( 2009). Navigating, recognizing and describing urban spaces with vision and lasers. The International Journal of Robotics Research , 1: 1-28.
41.
Nister, D., Naroditsky, O. and Bergen, J. ( 2004). Visual odometry. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington, DC, pp. 652- 659.
42.
Olson, E., Leonard, J. and Teller, S. ( 2006). Fast iterative alignment of pose graphs with poor initial estimates. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 2262-2269.
43.
Pinies, P. and Tardos, J.D. ( 2007). Scalable SLAM building conditionally independent local maps. IEEE Conference on Intelligent Robots and Systems.
44.
Ranganathan, A. ( 2008). Probabilistic Topological Maps. PhD Thesis, Georgia Institute of Technology.
45.
Ranganathan, A., Kaess, M. and Dellaert, F. ( 2007). Loopy SAM. International Joint Conferences on Artificial Intelligence, pp. 2191-2196.
46.
Ranganathan, A., Menegatti, E., and Dellaert, F. ( 2006). Bayesian inference in the space of topological maps. IEEE Transactions on Robotics and Automation, 22(1): 92- 107.
47.
Rosten, E. and Drummond, T. ( 2006). Machine learning for high-speed corner detection. European Conference on Computer Vision.
48.
Sciavicco, L. and Siciliano, B. ( 1996). Modelling and Control of Robot Manipulators. Berlin: Springer.
49.
Sibley, G. ( 2006). Sliding Window Filters for SLAM. Technical report CRES-06-004, University of Southern California, Center for Robotics and Embedded Systems.
50.
Sibley, G. ( 2007). Long Range Stereo Data-fusion from Moving Platforms. PhD Thesis, University of Southern California.
51.
Sibley, G., Matthies, L. and Sukhatme, G. ( 2007). A Sliding Window Filter for Incremental SLAM, chapter 7, (Lecture Notes in Electrical Engineering). Berlin, Springer, Volume 8. pp. 103-112.
52.
Sivic, J. and Zisserman, A. ( 2006). Video Google: efficient visual search of videos. Toward Category-Level Object Recognition, Berlin, Springer: pp. 127-144.
53.
Smith, M., Baldwin, I., Churchill, W., Paul, R. and Newman, P. ( 2009). The New College vision and laser data set. The International Journal of Robotics Research, 28(5): 595- 599.
54.
Sorenson, H.W. ( 1980). Parameter Estimation: Principles and Problems. New York, Marcel Dekker, Inc.
55.
Steder, B., Grisetti, G., Grzonka, S., Stachniss, C., Rottmann, A. and Burgard, W. ( 2007). Learning maps in 3D using attitude and noisy vision sensors . IEEE/RSJ International Conference on Intelligent Robots and Systems.
56.
Steedly, D. and Essa, I. ( 2001). Propagation of innovative information in non-linear least-squares structure from motion. Proceedings of ICCV01, pp. 223-229.
57.
Steedly, D., Essa, I. and Dellaert, F. ( 2003). Spectral partitioning for structure from motion. IEEE International Conference on Computer Vision.
58.
Thrun, S., Burgard, W. and Fox, D. ( 2005). Probabilistic Robotics. Cambridge, MA, MIT Press.
59.
Thrun, S., Koller, D., Ghahmarani, Z. and Durrant-Whyte, H. ( 2002a). Simultaneous mapping and localization with sparse extended information filters: theory and initial results. Workshop on Algorithmic Foundations of Robotics.
60.
Thrun, S., Koller, D., Ghahmarani, Z. and Durrant-Whyte., H. ( 2002b). SLAM updates require constant time. Workshop on the Algorithmic Foundations of Robotics.
61.
Triggs, B., McLauchlan, P.F., Hartley, R.I. and Fitzgibbon, A.W. ( 2000). Bundle Adjustment-A Modern Synthesis. ICCV ’99: Proceedings of the International Workshop on Vision Algorithms. Berlin, Springer, pp. 298-375.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
