“Uncertainty quantification for multi-scan registration” by Huang, Liang and Huang
Conference:
Type:
Title:
- Uncertainty quantification for multi-scan registration
Session/Category Title: Motion and Matching
Presenter(s)/Author(s):
Abstract:
A fundamental problem in scan-based 3D reconstruction is to align the depth scans under different camera poses into the same coordinate system. While there are abundant algorithms on aligning depth scans, few methods have focused on assessing the quality of a solution. This quality checking problem is vital, as we need to determine whether the current scans are sufficient or not and where to install additional scans to improve the reconstruction. On the other hand, this problem is fundamentally challenging because the underlying ground-truth is generally unavailable, and it is challenging to predict alignment errors such as global drifts manually. In this paper, we introduce a local uncertainty framework for geometric alignment algorithms. Our approach enjoys several appealing properties, such as it does not require re-sampling the input, no need for the underlying ground-truth, informative, and high computational efficiency. We apply this framework to two multi-scan alignment formulations, one minimizes geometric distances between pairs of scans, and another simultaneously aligns the input scans with a deforming model. The output of our approach can be seamlessly integrated with view selection, enabling uncertainty-aware view planning. Experimental results and user studies justify the effectiveness of our approach on both synthetic and real datasets.
References:
1. Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello. 2016a. Global Registration of 3D Point Sets via LRS Decomposition. In Computer Vision – ECCV 2016 – 14th European Conference, Proceedings, Part IV. Springer Verlag, Amsterdam, The Netherlands, 489–504. Google ScholarCross Ref
2. Federica Arrigoni, Beatrice Rossi, and Andrea Fusiello. 2016b. Spectral Synchronization of Multiple Views in SE(3). SIAM J. Imaging Sciences 9, 4 (2016), 1963–1990. Google ScholarCross Ref
3. Ola Bengtsson and Albert-Jan Baerveldt. 2003. Robot localization based on scan-matching – estimating the covariance matrix for the IDC algorithm. Robotics Auton. Syst. 44, 1 (2003), 29–40. Google ScholarCross Ref
4. Raouf Benjemaa and Francis Schmitt. 1998. A Solution for the Registration of Multiple 3D Point Sets Using Unit Quaternions. In Proceedings of the 5th European Conference on Computer Vision-Volume II – Volume II (ECCV ’98). Springer-Verlag, Berlin, Heidelberg, 34–50.Google ScholarCross Ref
5. Matthew Berger, Andrea Tagliasacchi, Lee M. Seversky, Pierre Alliez, Joshua A. Levine, Andrei Sharf, and Cláudio T. Silva. 2014. State of the Art in Surface Reconstruction from Point Clouds. In Eurographics 2014 – State of the Art Reports. The Eurographics Association, Strasbourg, France, 161–185. Google ScholarCross Ref
6. Paul J. Besl and Neil D. McKay. 1992. A Method for Registration of 3-D Shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14, 2 (Feb. 1992), 239–256. Google ScholarDigital Library
7. Peter Biber and Wolfgang Straßer. 2003. The normal distributions transform: a new approach to laser scan matching. In 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE/RSJ, Las Vegas, Nevada, USA, 2743–2748. Google ScholarCross Ref
8. Michael Bosse and Robert Zlot. 2008. Map Matching and Data Association for Large-Scale Two-dimensional Laser Scan-based SLAM. I. J. Robotics Res. 27, 6 (2008), 667–691. Google ScholarDigital Library
9. Benedict J. Brown and Szymon Rusinkiewicz. 2007. Global Non-Rigid Alignment of 3-D Scans. ACM Trans. Graph. 26, 3 (July 2007), 21–es. Google ScholarDigital Library
10. Andrea Censi. 2007. An accurate closed-form estimate of ICP’s covariance. In 2007 IEEE International Conference on Robotics and Automation, ICRA 2007. IEEE, Roma, Italy, 3167–3172. Google ScholarCross Ref
11. Jiawen Chen, Dennis Bautembach, and Shahram Izadi. 2013. Scalable Real-Time Volumetric Surface Reconstruction. ACM Trans. Graph. 32, 4, Article 113 (July 2013), 16 pages. Google ScholarDigital Library
12. Yang Chen and Gérard Medioni. 1992a. Object Modelling by Registration of Multiple Range Images. Image Vision Comput. 10, 3 (April 1992), 145–155. Google ScholarDigital Library
13. Yang Chen and Gérard G. Medioni. 1992b. Object modelling by registration of multiple range images. Image Vision Comput. 10, 3 (1992), 145–155. Google ScholarDigital Library
14. Nicos Christofides. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388. Graduate School of Industrial Administration, Carnegie Mellon University.Google Scholar
15. Angela Dai, Angel X. Chang, Manolis Savva, Maciej Halber, Thomas A. Funkhouser, and Matthias Nießner. 2017a. ScanNet: Richly-Annotated 3D Reconstructions of Indoor Scenes. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017. IEEE, Honolulu, HI, USA, 2432–2443. Google ScholarCross Ref
16. Angela Dai, Matthias Nieundefinedner, Michael Zollhöfer, Shahram Izadi, and Christian Theobalt. 2017b. BundleFusion: Real-Time Globally Consistent 3D Reconstruction Using On-the-Fly Surface Reintegration. ACM Trans. Graph. 36, 3, Article 24 (May 2017), 18 pages. Google ScholarDigital Library
17. Chandler Davis and W. M. Kahan. 1970. The Rotation of Eigenvectors by a Perturbation. III. SIAM J. Numer. Anal. 7, 1 (1970), 1–46.Google ScholarCross Ref
18. Xinyi Fan, Linguang Zhang, Benedict Brown, and Szymon Rusinkiewicz. 2016. Automated View and Path Planning for Scalable Multi-Object 3D Scanning. ACM Trans. Graph. 35, 6, Article 239 (Nov. 2016), 13 pages. Google ScholarDigital Library
19. Natasha Gelfand and Leonidas J. Guibas. 2004. Shape Segmentation Using Local Slippage Analysis. In Second Eurographics Symposium on Geometry Processing, July 8-10, 2004. The Eurographics Association, Nice, France, 214–223. Google ScholarCross Ref
20. Natasha Gelfand, Szymon Rusinkiewicz, Leslie Ikemoto, and Marc Levoy. 2003. Geometrically Stable Sampling for the ICP Algorithm. In 4th International Conference on 3D Digital Imaging and Modeling (3DIM 2003), 6-10 October 2003, Banff, Canada. IEEE Computer Society, Banff, Canada, 260–267. Google ScholarCross Ref
21. Venu Madhav Govindu and A. Pooja. 2014. On Averaging Multiview Relations for 3D Scan Registration. IEEE Trans. Image Processing 23, 3 (2014), 1289–1302.Google ScholarDigital Library
22. Peter Henry, Michael Krainin, Evan Herbst, Xiaofeng Ren, and Dieter Fox. 2012. RGB-D mapping: Using Kinect-style depth cameras for dense 3D modeling of indoor environments. I. J. Robotics Res. 31, 5 (2012), 647–663. Google ScholarDigital Library
23. Benjamin Hepp, Matthias Nieundefinedner, and Otmar Hilliges. 2018. Plan3D: Viewpoint and Trajectory Optimization for Aerial Multi-View Stereo Reconstruction. ACM Trans. Graph. 38, 1, Article 4 (Dec. 2018), 17 pages. Google ScholarDigital Library
24. Qixing Huang, Bart Adams, and Michael Wand. 2007a. Bayesian surface reconstruction via iterative scan alignment to an optimized prototype. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing, 2007. The Eurographics Association, Barcelona, Spain, 213–223. Google ScholarCross Ref
25. Qixing Huang, Bart Adams, and Michael Wand. 2007b. Bayesian Surface Reconstruction via Iterative Scan Alignment to an Optimized Prototype. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (Barcelona, Spain) (SGP ’07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 213–223. http://dl.acm.org/citation.cfm?id=1281991.1282021Google ScholarDigital Library
26. Qi-Xing Huang and Dragomir Anguelov. 2010. High quality pose estimation by aligning multiple scans to a latent map. In IEEE International Conference on Robotics and Automation, ICRA 2010. IEEE, Anchorage, Alaska, USA, 1353–1360.Google Scholar
27. Qi-Xing Huang and Leonidas Guibas. 2013. Consistent Shape Maps via Semidefinite Programming. In Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing (Genova, Italy) (SGP ’13). Eurographics Association, Goslar, DEU, 177–186.Google ScholarDigital Library
28. Xiangru Huang, Zhenxiao Liang, Chandrajit Bajaj, and Qixing Huang. 2017. Translation Synchronization via Truncated Least Squares. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017. Curran Associates, Long Beach, CA, USA, 1459–1468. http://papers.nips.cc/paper/6744-translation-synchronization-via-truncated-least-squaresGoogle Scholar
29. Xiangru Huang, Zhenxiao Liang, Xiaowei Zhou, Yao Xie, Leonidas J. Guibas, and Qixing Huang. 2019. Learning Transformation Synchronization. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019. IEEE, New York City, NY, USA, 8082–8091. Google ScholarCross Ref
30. Daniel Huber. 2002. Automatic Three-dimensional Modeling from Reality. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh, PA.Google ScholarDigital Library
31. Thorbjørn Mosekjær Iversen, Anders Glent Buch, and Dirk Kraft. 2017. Prediction of ICP pose uncertainties using Monte Carlo simulation with synthetic depth images. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, September 24-28, 2017. IEEE/RSJ, Vancouver, BC, Canada, 4640–4647. Google ScholarCross Ref
32. Shahram Izadi, David Kim, Otmar Hilliges, David Molyneaux, Richard Newcombe, Pushmeet Kohli, Jamie Shotton, Steve Hodges, Dustin Freeman, Andrew Davison, and Andrew Fitzgibbon. 2011. KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera. In Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology (Santa Barbara, California, USA) (UIST ’11). ACM, New York, NY, USA, 559–568. Google ScholarDigital Library
33. Hubert Jin, Thomas Duchamp, Hugues Hoppe, John Alan McDonald, Kari Pulli, and Werner Stuetzle. 1995. Surface reconstruction from misregistered data. In Vision Geometry IV, Robert A. Melter, Angela Y. Wu, Fred L. Bookstein, and William D. K. Green (Eds.), Vol. 2573. International Society for Optics and Photonics, SPIE, San Diego, CA, United States, 324–328. Google ScholarCross Ref
34. Olaf Kähler, Victor Adrian Prisacariu, Carl Yuheng Ren, Xin Sun, Philip H. S. Torr, and David William Murray. 2015. Very High Frame Rate Volumetric Integration of Depth Images on Mobile Devices. IEEE Trans. Vis. Comput. Graph. 21, 11 (2015), 1241–1250. Google ScholarDigital Library
35. K. Kanatani and D. D. Morris. 2006. Gauges and Gauge Transformations for Uncertainty Description of Geometric Structure with Indeterminacy. IEEE Trans. Inf. Theor. 47, 5 (Sept. 2006), 2017–2028. Google ScholarDigital Library
36. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson Surface Reconstruction. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (Cagliari, Sardinia, Italy) (SGP ’06). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 61–70. http://dl.acm.org/citation.cfm?id=1281957.1281965Google ScholarDigital Library
37. Maik Keller, Damien Lefloch, Martin Lambers, Shahram Izadi, Tim Weyrich, and Andreas Kolb. 2013. Real-Time 3D Reconstruction in Dynamic Scenes Using Point-Based Fusion. In Proceedings of the 2013 International Conference on 3D Vision (3DV ’13). IEEE Computer Society, USA, 1–8. Google ScholarDigital Library
38. Steven G. G. Krantz and Harold R. Parks. 2013. The Implicit Function Theorem: History, Theory, and Applications. Springer, New York City.Google Scholar
39. Shankar Krishnan, Pei Yean Lee, John B. Moore, and Suresh Venkatasubramanian. 2005. Global Registration of Multiple 3D Point Sets via Optimization-on-a-Manifold. In Proceedings of the Third Eurographics Symposium on Geometry Processing (Vienna, Austria) (SGP ’05). Eurographics Association, Goslar, DEU, 187–es.Google ScholarDigital Library
40. David Landry, François Pomerleau, and Philippe Giguère. 2019. CELLO-3D: Estimating the Covariance of ICP in the Real World. In International Conference on Robotics and Automation, ICRA 2019. IEEE, Montreal, QC, Canada, 8190–8196. Google ScholarCross Ref
41. Maxime Lhuillier and Mathieu Perriollat. 2006. Uncertainty Ellipsoids Calculations for Complex 3D Reconstructions. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation. IEEE, Orlando, Florida, USA, 3062–3069. Google ScholarCross Ref
42. Yangyan Li, Xiaochen Fan, Niloy J. Mitra, Daniel Chamovitz, Daniel Cohen-Or, and Baoquan Chen. 2013. Analyzing Growing Plants from 4D Point Cloud Data. ACM Trans. Graph. 32, 6, Article 157 (Nov. 2013), 10 pages. Google ScholarDigital Library
43. Yang Liu, Helmut Pottmann, and Wenping Wang. 2006. Constrained 3D shape reconstruction using a combination of surface fitting and registration. Computer-Aided Design 38, 6 (2006), 572–583. Google ScholarDigital Library
44. Prakhya Sai Manoj, Bingbing Liu, Yan Rui, and Weisi Lin. 2015. A closed-form estimate of 3D ICP covariance. In 14th IAPR International Conference on Machine Vision Applications, MVA 2015. IAPR, Miraikan, Tokyo, Japan, 526–529. Google ScholarCross Ref
45. Juan I. Nieto, Tim Bailey, and Eduardo Mario Nebot. 2005. Scan-SLAM: Combining EKF-SLAM and Scan Correlation. In Field and Service Robotics, Results of the 5th International Conference, FSR 2005. Springer, Port Douglas, QLD, Australia, 167–178. Google ScholarCross Ref
46. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (second ed.). Springer, New York, NY, USA.Google Scholar
47. Mark Pauly, Niloy J. Mitra, and Leonidas J. Guibas. 2004. Uncertainty and Variability in Point Cloud Surface Data. In Proceedings of the First Eurographics Conference on Point-Based Graphics (Switzerland) (SPBG’04). Eurographics Association, Goslar, DEU, 77–84.Google Scholar
48. Michal Polic, Wolfgang Förstner, and Tomás Pajdla. 2018. Fast and Accurate Camera Covariance Computation for Large 3D Reconstruction. In Computer Vision – ECCV 2018 – 15th European Conference, September 8-14, 2018, Proceedings, Part II. Springer Verlag, Munich, Germany, 697–712. Google ScholarCross Ref
49. Kai Pöthkow, Britta Weber, and Hans-Christian Hege. 2011. Probabilistic Marching Cubes. Comput. Graph. Forum 30, 3 (2011), 931–940. Google ScholarDigital Library
50. Helmut Pottmann and Michael Hofer. 2002. Geometry of the Squared Distance Function to Curves and Surfaces. In Third International Workshop “Visualization and Mathematics”, VisMath 2002. Springer Verlag, Berlin, Germany, 221–242. Google ScholarCross Ref
51. Helmut Pottmann, Qi-Xing Huang, Yong-Liang Yang, and Shi-Min Hu. 2006. Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes. International Journal of Computer Vision 67, 3 (2006), 277–296. Google ScholarDigital Library
52. Helmut Pottmann, Stefan Leopoldseder, and Michael Hofer. 2004. Registration without ICP. Computer Vision and Image Understanding 95, 1 (2004), 54–71. Google ScholarDigital Library
53. Anil C. Raghuramu. 2015. Robust Multiview Registration of 3D Surfaces via ∈1-norm Minimization. In Proceedings of the British Machine Vision Conference (BMVC), Xianghua Xie, Mark W. Jones, and Gary K. L. Tam (Eds.). BMVA Press, Swansea, UK, Article 62, 11 pages. Google ScholarCross Ref
54. Szymon Rusinkiewicz, Olaf Hall-Holt, and Marc Levoy. 2002. Real-time 3D Model Acquisition. ACM Trans. Graph. 21, 3 (July 2002), 438–446. Google ScholarDigital Library
55. William R. Scott. 2009. Model-Based View Planning. Mach. Vision Appl. 20, 1 (Jan. 2009), 47–69.Google ScholarCross Ref
56. William R. Scott, Gerhard Roth, and Jean-François Rivest. 2003. View Planning for Automated Three-Dimensional Object Reconstruction and Inspection. ACM Comput. Surv. 35, 1 (March 2003), 64–96. Google ScholarDigital Library
57. Pei Sun, Henrik Kretzschmar, Xerxes Dotiwalla, Aurelien Chouard, Vijaysai Patnaik, Paul Tsui, James Guo, Yin Zhou, Yuning Chai, Benjamin Caine, Vijay Vasudevan, Wei Han, Jiquan Ngiam, Hang Zhao, Aleksei Timofeev, Scott Ettinger, Maxim Krivokon, Amy Gao, Aditya Joshi, Yu Zhang, Jonathon Shlens, Zhifeng Chen, and Dragomir Anguelov. 2019. Scalability in Perception for Autonomous Driving: Waymo Open Dataset. arXiv:1912.04838 [cs.CV]Google Scholar
58. Richard Szeliski. 1990. Bayesian modeling of uncertainty in low-level vision. Int. J. Comput. Vis. 5, 3 (1990), 271–301. Google ScholarDigital Library
59. Richard Szeliski and Sing Bing Kang. 1997. Shape Ambiguities in Structure From Motion. IEEE Trans. Pattern Anal. Mach. Intell. 19, 5 (1997), 506–512. Google ScholarDigital Library
60. Gary K. Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank Langbein, Yonghuai Liu, A. David Marshall, Ralph Martin, Xianfang Sun, and Paul Rosin. 2013. Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid. IEEE Transactions on Visualization and Computer Graphics 19, 7 (July 2013), 1199–1217. Google ScholarDigital Library
61. Andrea Torsello, Emanuele Rodolà, and Andrea Albarelli. 2011. Multiview registration via graph diffusion of dual quaternions. In The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011. IEEE, Colorado Springs, CO, USA, 2441–2448. Google ScholarDigital Library
62. Bill Triggs, Philip F. McLauchlan, Richard I. Hartley, and Andrew W. Fitzgibbon. 1999. Bundle Adjustment – A Modern Synthesis. In Vision Algorithms: Theory and Practice, International Workshop on Vision Algorithms, held during ICCV ’99. IEEE, Corfu, Greece, 298–372. Google ScholarCross Ref
63. Dragan Tubic, Patrick Hébert, and Denis Laurendeau. 2003. A volumetric approach for interactive 3D modeling. Comput. Vis. Image Underst. 92, 1 (2003), 56–77. Google ScholarDigital Library
64. A.W. Van Der Vaart. 1998. Asymptotic Statistics. Cambridge University Press, One Liberty Plaza, New York, NY 10006. https://books.google.com/books?id=udhfQgAACAAJGoogle Scholar
65. Grace Wahba. 1983. Bayesian “Confidence Intervals” for the Cross-Validated Smoothing Spline. Journal of the Royal Statistical Society. Series B 45 (1983), 133–150. Issue 1.Google Scholar
66. Lanhui Wang and Amit Singer. 2013. Exact and Stable Recovery of Rotations for Robust Synchronization. Information and Inference: A Journal of the IMA 2 (December 2013), 145–193. Issue 2.Google Scholar
67. Thomas Whelan, Michael Kaess, Hordur Johannsson, Maurice F. Fallon, John J. Leonard, and John McDonald. 2015. Real-time large-scale dense RGB-D SLAM with volumetric fusion. I. J. Robotics Res. 34, 4-5 (2015), 598–626. Google ScholarDigital Library
68. Thomas Whelan, Renato F Salas-Moreno, Ben Glocker, Andrew J Davison, and Stefan Leutenegger. 2016. ElasticFusion. Int. J. Rob. Res. 35, 14 (Dec. 2016), 1697–1716. Google ScholarDigital Library
69. Hong-Tzong Yau, Tsan-Jui Yang, and Yi-Chen Chen. 2014. Tooth model reconstruction based upon data fusion for orthodontic treatment simulation. Comp. in Bio. and Med. 48 (2014), 8–16. http://dblp.uni-trier.de/db/journals/cbm/cbm48.html#YauYC14Google ScholarCross Ref
70. Fuzhen Zhang. 2005. The Schur Complement and its Applications. Numerical Methods and Algorithms, Vol. 4. Springer, New York. Google ScholarCross Ref
71. Zhengyou Zhang. 1998. Determining the Epipolar Geometry and its Uncertainty: A Review. Int. J. Comput. Vis. 27, 2 (1998), 161–195. Google ScholarDigital Library
72. Zaiwei Zhang, Zhenxiao Liang, Lemeng Wu, Xiaowei Zhou, and Qixing Huang. 2019. Path-Invariant Map Networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019. IEEE, New York City, NY, USA, 11084–11094. Google ScholarCross Ref
73. Michael Zollhöfer, Patrick Stotko, Andreas Görlitz, Christian Theobalt, Matthias Nießner, Reinhard Klein, and Andreas Kolb. 2018. State of the Art on 3D Reconstruction with RGB-D Cameras. Comput. Graph. Forum 37, 2 (2018), 625–652. Google ScholarCross Ref
