research-article

Automated view and path planning for scalable multi-object 3D scanning

Authors:

Linguang Zhang,

Benedict Brown,

Szymon RusinkiewiczAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 35, Issue 6

Article No.: 239, Pages 1 - 13

https://doi.org/10.1145/2980179.2980225

Published: 05 December 2016 Publication History

Abstract

Demand for high-volume 3D scanning of real objects is rapidly growing in a wide range of applications, including online retailing, quality-control for manufacturing, stop motion capture for 3D animation, and archaeological documentation and reconstruction. Although mature technologies exist for high-fidelity 3D model acquisition, deploying them at scale continues to require non-trivial manual labor. We describe a system that allows non-expert users to scan large numbers of physical objects within a reasonable amount of time, and with greater ease. Our system uses novel view- and path-planning algorithms to control a structured-light scanner mounted on a calibrated motorized positioning system. We demonstrate the ability of our prototype to safely, robustly, and automatically acquire 3D models for large collections of small objects.

Supplementary Material

ZIP File (a239-fan.zip)

Supplemental file.

Download
190.69 MB

References

[1]

Berkiten, S., Fan, X., and Rusinkiewicz, S. 2014. Merge2-3D: Combining multiple normal maps with 3D surfaces. Proc. Int. Conf. 3D Vision (3DV) (Dec.), 440--447.

Digital Library

[2]

Bernardini, F., and Rushmeier, H. 2002. The 3D model acquisition pipeline. Computer Graphics Forum 21, 2, 149--172.

[3]

Bernardini, F., Rushmeier, H., Martin, I. M., Mittleman, J., and Taubin, G. 2002. Building a digital model of Michelangelo's Florentine Pietà. IEEE Computer Graphics and Applications 22, 59--67.

Digital Library

[4]

Bowyer, K. W., and Dyer, C. R. 1990. Aspect graphs: An introduction and survey of recent results. In Proc. SPIE: Close-Range Photogrammetry Meets Machine Vision, vol. 1395, 200 -- 208.

[5]

Brown, B. J., Toler-Franklin, C., Nehab, D., Burns, M., Dobkin, D., Vlachopoulos, A., Doumas, C., Rusinkiewicz, S., and Weyrich, T. 2008. A system for high-volume acquisition and matching of fresco fragments: Reassembling Theran wall paintings. ACM Trans. Graphics (Proc. SIGGRAPH) 27, 3.

Digital Library

[6]

Chen, S., Li, Y., and Kwok, N. M. 2011. Active vision in robotic systems: A survey of recent developments. Int. J. Robotics Research 30, 11, 1343--1377.

Digital Library

[7]

Cheng, P., Keller, J. F., and Kumar, V. 2008. Time-optimal UAV trajectory planning for 3D urban structure coverage. In Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (IROS), 2750--2757.

[8]

Christofides, N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University.

[9]

Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In Proc. ACM SIGGRAPH, 303--312.

Digital Library

[10]

Englot, B., and Hover, F. 2010. Inspection planning for sensor coverage of 3D marine structures. In Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (IROS), 4412--4417.

[11]

Feige, U. 1998. A threshold of Ln N for approximating set cover. J. ACM 45, 4, 634--652.

Digital Library

[12]

Gonzalez-Barbosa, J.-J., García-Ramírez, T., Salas, J., Hurtado-Ramos, J.-B., and Rico-Jiménez, J.-d.-J. 2009. Optimal camera placement for total coverage. In Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 3672--3676.

Digital Library

[13]

Gurobi Optimization, I., 2015. Gurobi optimizer reference manual. http://www.gurobi.com.

[14]

Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum, 85--103.

[15]

Kazhdan, M., and Hoppe, H. 2013. Screened Poisson surface reconstruction. ACM Trans. Graph. 32, 3, 29:1--29:13.

Digital Library

[16]

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 671--680.

[17]

Kriegel, S., Brucker, M., Marton, Z. C., Bodenmller, T., and Suppa, M. 2013. Combining object modeling and recognition for active scene exploration. In Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (IROS), 2384--2391.

[18]

Laurentini, A. 1994. The visual hull concept for silhouette-based image understanding. IEEE Trans. PAMI 16, 2, 150--162.

Digital Library

[19]

Lawler, E. L., Lenstra, J. K., Kan, A. R., and Shmoys, D. B. 1985. The traveling salesman problem: a guided tour of combinatorial optimization, vol. 3. Wiley.

[20]

Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The Digital Michelangelo Project: 3D scanning of large statues. In Proc. ACM SIGGRAPH, 131--144.

Digital Library

[21]

Olson, E. 2011. AprilTag: A robust and flexible visual fiducial system. In Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 3400--3407.

[22]

Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In Proc. 3D Digital Imaging and Modeling (3DIM), 145--152.

[23]

Rusinkiewicz, S., Hall-Holt, O., and Levoy, M. 2002. Real-time 3D model acquisition. ACM Trans. Graph. 21, 3, 438--446.

Digital Library

[24]

Salvi, J., Pagès, J., and Batlle, J. 2004. Pattern codification strategies in structured light systems. Pattern Recognition 37, 827--849.

[25]

Scott, W. R., Yz, W. R. S., Roth, G., and Rivest, J.-F. 2001. View planning as a set covering problem. Tech. Rep. 44892, NRC Canada.

[26]

Scott, W. R., Roth, G., and Rivest, J.-F. 2003. View planning for automated three-dimensional object reconstruction and inspection. ACM Computing Surveys 35, 1, 64--96.

Digital Library

[27]

Tarbox, G. H., and Gottschlich, S. N. 1995. Planning for complete sensor coverage in inspection. Computer Vision and Image Understanding 61, 1, 84--111.

Digital Library

[28]

Taylor, C. 2012. Implementing high resolution structured light by exploiting projector blur. In Proc. IEEE Workshop on Applications of Computer Vision (WACV), 9--16.

Digital Library

[29]

Urrutia, J. 2000. Art gallery and illumination problems. In Handbook of Computational Geometry, J. Sack and J. Urrutia, Eds. Elsevier.

[30]

Vázquez, P.-P., Feixas, M., Sbert, M., and Heidrich, W. 2001. Viewpoint selection using viewpoint entropy. In Proc. Vision Modeling and Visualization (VMV), 273--280.

Digital Library

[31]

Wang, P., Krishnamurti, R., and Gupta, K. 2007. View planning problem with combined view and traveling cost. In Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 711--716.

[32]

Weise, T., Wismer, T., Leibe, B., and Gool, L. V. 2009. In-hand scanning with online loop closure. In Proc. 3D Digital Imaging and Modeling (3DIM).

[33]

Wu, S., Sun, W., Long, P., Huang, H., Cohen-Or, D., Gong, M., Deussen, O., and Chen, B. 2014. Quality-driven Poisson-guided autoscanning. ACM Trans. Graph. 33, 6, 203:1--203:12.

Digital Library

[34]

Xu, K., Huang, H., Shi, Y., Li, H., Long, P., Caichen, J., Sun, W., and Chen, B. 2015. Autoscanning for coupled scene reconstruction and proactive object analysis. ACM Trans. Graph. 34, 6, 177:1--177:14.

Digital Library

[35]

Yan, F., Sharf, A., Lin, W., Huang, H., and Chen, B. 2014. Proactive 3D scanning of inaccessible parts. ACM Trans. Graph. 33, 4, 157:1--157:8.

Digital Library

[36]

Zhao, J., Yoshida, R., ching Samson Cheung, S., and Haws, D. 2013. Approximate techniques in solving optimal camera placement problems. Int. J. Distributed Sensor Networks, Article ID 241913.

Cited By

Spensieri DÅ blad ESalman RCarlson J(2025)A unified sampling method for optimal feature coverage and robot placementRobotics and Computer-Integrated Manufacturing10.1016/j.rcim.2024.10293293(102932)Online publication date: Jun-2025
https://doi.org/10.1016/j.rcim.2024.102932
Tasneem OPieters R(2024)Automatic Robot Path Planning for Active Visual Inspection on Free-Form Surfaces2024 IEEE 20th International Conference on Automation Science and Engineering (CASE)10.1109/CASE59546.2024.10711320(173-180)Online publication date: 28-Aug-2024
https://doi.org/10.1109/CASE59546.2024.10711320
Lee ISeo JYoo B(2024)Autonomous view planning methods for 3D scanningAutomation in Construction10.1016/j.autcon.2024.105291160(105291)Online publication date: Apr-2024
https://doi.org/10.1016/j.autcon.2024.105291
Show More Cited By

Index Terms

Automated view and path planning for scalable multi-object 3D scanning
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics input devices
2. Hardware
  1. Communication hardware, interfaces and storage
    1. Scanners

Recommendations

Robust sequential view planning for object recognition using multiple cameras

While prior relevant research in active object recognition/pose estimation has mostly focused on single-camera systems, we propose two multi-camera solutions to this problem that can enhance object recognition rate, particularly in the presence of ...
Real-time multi-view 3d object tracking in cluttered scenes
ISVC'06: Proceedings of the Second international conference on Advances in Visual Computing - Volume Part II

This paper presents an approach to real-time 3D object tracking in cluttered scenes using multiple synchronized and calibrated cameras. The goal is to accurately track targets over a long period of time in the presence of complete occlusion in some of ...
View Planning for 3D Reconstruction Using Time-of-Flight Camera Data
Proceedings of the 31st DAGM Symposium on Pattern Recognition - Volume 5748

Solving the next best view NBV problem is an important task for automated 3D reconstruction. An NBV algorithm provides sensor positions, from which maximal information gain about the measurement object during the next scan can be expected. With no or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 35, Issue 6

November 2016

1045 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2980179

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 December 2016

Published in TOG Volume 35, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
730
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)9

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Spensieri DÅ blad ESalman RCarlson J(2025)A unified sampling method for optimal feature coverage and robot placementRobotics and Computer-Integrated Manufacturing10.1016/j.rcim.2024.10293293(102932)Online publication date: Jun-2025
https://doi.org/10.1016/j.rcim.2024.102932
Tasneem OPieters R(2024)Automatic Robot Path Planning for Active Visual Inspection on Free-Form Surfaces2024 IEEE 20th International Conference on Automation Science and Engineering (CASE)10.1109/CASE59546.2024.10711320(173-180)Online publication date: 28-Aug-2024
https://doi.org/10.1109/CASE59546.2024.10711320
Lee ISeo JYoo B(2024)Autonomous view planning methods for 3D scanningAutomation in Construction10.1016/j.autcon.2024.105291160(105291)Online publication date: Apr-2024
https://doi.org/10.1016/j.autcon.2024.105291
Peng CWei MIsler V(2023)Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection2023 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48891.2023.10161120(3607-3613)Online publication date: 29-May-2023
https://doi.org/10.1109/ICRA48891.2023.10161120
Wang JZhang CWang PLi XCobb PTheobalt CWang W(2023)Batch-based Model Registration for Fast 3D Sherd Reconstruction2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.01335(14473-14483)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.01335
Wolski KZhong FMyszkowski KMantiuk R(2022)Dark stereoACM Transactions on Graphics10.1145/3528223.353013641:4(1-12)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530136
Sun JWu WLiu LMin WZhang GZheng L(2022)WallPlanACM Transactions on Graphics10.1145/3528223.353013541:4(1-14)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530135
Li GMeka AMueller FBuehler MHilliges OBeeler T(2022)EyeNeRFACM Transactions on Graphics10.1145/3528223.353013041:4(1-16)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530130
Araújo CVining NRosales EGori GSheffer A(2022)As-locally-uniform-as-possible reshaping of vector clip-artACM Transactions on Graphics10.1145/3528223.353009841:4(1-10)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530098
Yin JLiu CLin RVining NRhodin HSheffer A(2022)Detecting viewer-perceived intended vector sketch connectivityACM Transactions on Graphics10.1145/3528223.353009741:4(1-11)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530097
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents