Visual Hull with Imprecise Input

Authors: Peng He

Abstract:

Imprecision is a long-standing problem in CAD design and high accuracy image-based reconstruction applications. The visual hull which is the closed silhouette equivalent shape of the objects of interest is an important concept in image-based reconstruction. We extend the domain-theoretic framework, which is a robust and imprecision capturing geometric model, to analyze the imprecision in the output shape when the input vertices are given with imprecision. Under this framework, we show an efficient algorithm to generate the 2D partial visual hull which represents the exact information of the visual hull with only basic imprecision assumptions. We also show how the visual hull from polyhedra problem can be efficiently solved in the context of imprecise input.

Keywords: Geometric Domain, Computer Vision, Computational Geometry, Visual Hull, Image-Based reconstruction, Imprecise Input, CAD object

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062650

References:

[1] Leda. http://www.mpi-sb.mpg.de/LEDA/leda.html.
[2] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 9th printing edition, 1972.
[3] F. Avnaim, J.-D. Boissonnat, O. Devillers, F. P. Preparata, and M. Yvinec. Evaluation of a new method to compute signs of determinants. In SCG -95: Proceedings of the eleventh annual symposium on Computational geometry, pages 416-417, New York, NY, USA, 1995. ACM.
[4] Andrea Bottino and Aldo Laurentini. The visual hull of smooth curved objects. IEEE Trans. Pattern Anal. Mach. Intell., 26(12):1622-1632, 2004.
[5] Andrea Bottino and Aldo Laurentini. The visual hull of piecewise smooth objects. Comput. Vis. Image Underst., 110(1):7-18, 2008.
[6] Herv'e Br¨onnimann, Ioannis Z. Emiris, Victor Y. Pan, and Sylvain Pion. Computing exact geometric predicates using modular arithmetic with single precision. In SCG -97: Proceedings of the thirteenth annual symposium on Computational geometry, pages 174-182, New York, NY, USA, 1997. ACM.
[7] Herv'e Br¨onnimann and Mariette Yvinec. Efficient exact evaluation of signs of determinants. In SCG -97: Proceedings of the thirteenth annual symposium on Computational geometry, pages 166-173, New York, NY, USA, 1997. ACM.
[8] N. J. Cutland. Computability: An Introduction to Recursive Function Theory. Cambridge University Press, 1980.
[9] Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. In SCG -00: Proceedings of the sixteenth annual symposium on Computational geometry, pages 139-147, New York, NY, USA, 2000. ACM.
[10] C. R. Dyer. Volumetric scene reconstruction from multiple views. In Foundations of Image Understanding, pages 469-489. Kluwer, 2001.
[11] A. Edalat, A. A. Khanban, and A. Lieutier. Delaunay triangulation and Voronoi diagram with imprecise input data. Electronic Notes in Theoretical Computer Science, 66(1), July 2002. Proceedings of the 5th CCA Workshop.
[12] A. Edalat, A. A. Khanban, and A. Lieutier. Computability in computational geometry. New Computational Paradigms, 3526:117-127, 2005.
[13] A. Edalat and A. Lieutier. Foundation of a computable solid modeling. In Proceedings of the fifth symposium on Solid modeling and applications, ACM Symposium on Solid Modeling and Applications, pages 278-284, 1999.
[14] A. Edalat and A. Lieutier. Foundation of a computable solid modelling. Theoretical Computer Science, 284(2):319-345, June 2002.
[15] A. Edalat, A. Lieutier, and E. Kashefi. The convex hull in a new model of computation. In Proceedings of the 13th Canadian Conference on Computational Geometry, pages 93-96, University of Waterloo, August 2001.
[16] Philipp Fechteler and Peter Eisert. Adaptive Colour Classification for Structured Light Systems. IET Journal on Computer Vision, 3(2):49-59, June 2009. Special Issue on 3D Face Processing.
[17] Steven Fortune. Polyhedral modelling with multiprecision integer arithmetic. Computer-Aided Design, 29(2):123-133, 1997.
[18] Steven Fortune and Christopher J. Van Wyk. Efficient exact arithmetic for computational geometry. In SCG -93: Proceedings of the ninth annual symposium on Computational geometry, pages 163-172, New York, NY, USA, 1993. ACM.
[19] Ziv Gigus, John Canny, and Raimund Seidel. Efficiently computing and representing aspect graphs of polyhedral objects. IEEE Trans. on Pat. Matching & Mach. Intelligence, 13(6), June 1991.
[20] Ziv Gigus, John F. Canny, and Raimund Seidel. Efficiently computing and representing aspect graphs of polyhedral objects. Technical Report UCB/CSD-88-432, EECS Department, University of California, Berkeley, Aug 1988.
[21] Chun-Yi Hu, Takashi Maekawa, Evan C. Sherbrooke, and Nicholas M. Patrikalakis. Robust interval algorithm for curve intersections. Computer-Aided Design, 28(6-7):495-506, 1996.
[22] Chun-Yi Hu, Nicholas M. Patrikalakis, and Xiuzi Ye. Robust interval solid modelling part ii: boundary evaluation. Computer-Aided Design, 28(10):819-830, 1996.
[23] A. A. Khanban and A. Edalat. Computing Delaunay triangulation with imprecise input data. In Proceedings of the 15th Canadian Computational Geometry Conference, pages 94-97, 2003.
[24] M. Kreveld, M. Loffler, and J. S. Mitchell. Preprocessing imprecise points and splitting triangulations. In ISAAC -08: Proceedings of the 19th International Symposium on Algorithms and Computation, pages 544-555, Berlin, Heidelberg, 2008. Springer-Verlag.
[25] K. N. Kutulakos and S. M. Seitz. A theory of shape by space carving. Computer Vision, IEEE International Conference on, 1:307-314, 1999.
[26] Kiriakos N. Kutulakos. Approximate N-view stereo. In ECCV -00: Proceedings of the 6th European Conference on Computer Vision-Part I, pages 67-83, London, UK, 2000. Springer-Verlag.
[27] A. Laurentini. The visual hull concept for silhouette-based image understanding. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(2):150-162, February 1994.
[28] Aldo Laurentini. Introducing the reduced aspect graph. Pattern Recogn. Lett., 16(1):43-48, 1995.
[29] Aldo Laurentini. Computing the visual hull of solids of revolution. Pattern Recognition, 32(3):377-388, 1999.
[30] M. Loffler and J. Snoeyink. Delaunay triangulations of imprecise pointsin linear time after preprocessing. In SCG -08: Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 298-304, New York, NY, USA, 2008. ACM.
[31] Franco P. Preparata and Michael I. Shamos. Computational Geometry: An Introduction (Monographs in Computer Science). Springer, August 1985.
[32] D. Salesin, J Stolfi, and L. Guibas. Epsilon geometry: building robust algorithms from imprecise computations. In SCG -89: Proceedings of the fifth annual symposium on Computational geometry, pages 208-217, New York, NY, USA, 1989. ACM.
[33] Daniel Scharstein. High-accuracy stereo depth maps using structured light. pages 195-202, 2003.
[34] Thomas W. Sederberg and Rida T. Farouki. Approximation by interval bezier curves. IEEE Comput. Graph. Appl., 12(5):87-95, 1992.
[35] G. G. Slabaugh, T. Malzbender, W. B. Culbertson, and R. W. Schafer. Improved voxel coloring via volumetric optimization. Technical report, 2003. Center for Signal and Image Processing, Georgia Institute of Technology.
[36] Klaus Weihrauch. Computability. Springer-Verlag New York, Inc., New York, NY, USA, 1987.
[37] Chee Yap and Thomas Dub. The exact computation paradigm. 1994.
[38] Li Zhang, Brian Cudess, and Steven M. Seitz. Rapid shape acquisition using color structured lightand multi-pass dynamic programming. In In The 1st IEEE International Symposium on 3D Data Processing, Visualization, and Transmission, pages 24-36, 2002.