Visual Hull with Imprecise Input

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.

Authors:

• Peng He

Keywords:

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

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.