Abstract
Surface reconstruction from multiple calibrated images has been mainly approached using local methods, either as a continuous optimization problem driven by level sets, or by discrete volumetric methods such as space carving. We propose a direct surface reconstruction approach which starts from a continuous geometric functional that is minimized up to a discretization by a global graph-cut algorithm operating on a 3D embedded graph. The method is related to the stereo disparity computation based on graph-cut formulation, but fundamentally different in two aspects. First, existing stereo disparity methods are only interested in obtaining layers of constant disparity, while we focus on high resolution surface geometry. Second, most of the existing graph-cut algorithms only reach approximate solutions, while we guarantee a global minimum. The whole procedure is consistently incorporated into a voxel representation that handles both occlusions and discontinuities. We demonstrate our algorithm on real sequences, yielding remarkably detailed surface geometry up to 1/10th of a pixel.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
Aubert, G. and Kornprobst, P. 2002. Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations, sen Applied Mathematical Sciences. Springer-Verlag, Vol. 147.
Black, M.J., Sapiro, G., Marimont, D., and Heeger, D. 1998. Robust anisotropic diffusion. IEEE Transactions on Image Processing.
Blake, A. and Zisserman, A. 1987. Visual reconstruction, sen Artificial Intelligence. MIT Press: Cambridge.
Boykov, Y. and Kolmogorov, V. 2003. Computing geodesies and minimal surfaces via graph cuts. In International Conference on Computer Vision.
Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI).
Boykov, Y. and Kolmogorov, V. 2004. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI).
Buehler, C., Gortler, S., Cohen, M., and McMillan, L. 2002. Minimal surfaces for stereo. In European Conference on Computer Vision (ECCV 02).
Caselles, V.R. Sapiro, G. 1997. Geodesic active contours. International Journal of Computer Vision.
Catté, F., Lions, P.-L., Morel, J.-M., and Coll, T. 1992. Image selective smoothing and edge detection by nonlinear diffusion. SIAM Journal on Numerical Analysis.
Cherkassky, B.V. and Goldberg, A.V. 1997. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19, 4, pp. 390–410.
Faugeras, O. and Keriven, R. 1998. Variational principles, surface evolution, PDE's, level set methods and the stereo problem. Transactions on Image Processing.
Ford, L. and Fulkerson, D. 1962. Flows in Networks. Princeton University Press.
Ishikawa, H. 2003. Exact optimization for markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI).
Ishikawa, H. and Geiger, D. 1998. Occlusions, discontinuities, and epipolar lines in stereo. In European Conference on Computer Vision (ECCV 98).
Ishikawa, H. 2000. Global optimization using embedded graphs. Ph.D. dissertation, New York University.
Isidoro, J. and Sclaroff, S. 2003. Stochastic refinement of the visual hull to satisfy photometric and silhouette consistency constraints. In Proc. Int. Conf. on Computer Vision. IEEE. pp. 1335–1342.
Kim, J., Kolmogorov, V., and Zabih, R. 2003. Visual correspondence using energy minimization and mutual information. In International Conference on Computer Vision.
Kolmogorov, V. and Zabih, R. 2002. Multi-camera scene reconstruction via graph cuts. In European Conference on Computer Vision.
Kolmogorov, V. and Zabih, R. 2001. Computing visual correspondence with occlusions using graph cuts. In International Conference on Computer Vision.
Kolmogorov, V. and Zabih R. 2002. What energy functions can be minimized via graph cuts? In European Conference on Computer Vision.
Kutulakos, K.N. 2000. Approximate n-view stereo. In European Conference on Computer Vision (ECCV 00).
Kutulakos, K. and Seitz, S. 1999. A theory of shape by space carving. In Proceedings of the 7th IEEE International Conference on Computer Vision (ICCV-99), pp. 307–314.
Lhuillier, M. and Quan, L. 2002. Quasi-dense reconstruction from image sequence. In European Conference on Computer Vision (ECCV 02).
Lhuillier M. and Quan, L. 2003. Surface reconstruction by integrating 3d and 2d data of multiple views. In Proc. of Int. Conf. on Computer Vision. IEEE.
Museth, K., Breen, D., Whitaker, R., and Barr, A. 2002. Level set surface editing operators. ACM Transactions on Graphics (Siggraph 02), 21(3):330–338.
Osher, S. and Sethian, J. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on hamilton-jacobi formulations. Journal of Computational Physics.
Paris, S. and Sillion, F. 2003. Robust acquisition of 3d informations from short image sequences. Graphical Models, 65, 4. pp. 222–238.
Roy, S. 1999. Stereo without epipolar lines: A maximum-flow formulation. Int. Journal of Computer Vision, 34(2/3) 147–162.
Roy, S. and Cox, I. 1998. A maximum-flow formulation of the n-camera stereo correspondence problem. In IEEE International Conference on Computer Vision.
Saito, H. and Kanade, T. 1999. Shape reconstruction in projective grid space from large number of images. In Computer Vision and Pattern Recognition (CVPR-99) pp. 49–54.
Seitz, S.M. and Dyer, C.R. 1999. Photorealistic scene reconstruction by voxel coloring. IJCV.
Sethian, J. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.
Slabaugh, G., Culbertson, B., Malzbender, T., and Schafer, R. 2001. A survey of methods for volumetric scene reconstruction from photographs. In VolumeGraphics 01.
Slabaugh, G., Malzbender, T., and Culbertson, W.B. 2000. Volumetric warping for voxel coloring on an infinite domain. In 3D Structure from Images---SMILE 2000.
Szeliski, R. Golland, P. 1998. Stereo matching with transparency and matting. In International Conference on Computer Vision (ICCV 98).
Terzopoulos, D., Witkin, A., and Kass, M. 1988. Constraints on deformable models: Recovering 3d shape and nonrigid motions. Artificial Intelligence.
Ulvklo, M., Knutsson, H., and Granlund, G.H. 1998. Depth segmentation and occluded scene reconstruction using ego-motion. SPIE Visual Information Processing.
Veksler, O. 1999. Efficient graph-based energy minimization methods in computer vision. Ph.D. dissertation, Cornell University.
Author information
Authors and Affiliations
Corresponding author
Additional information
Author has worked on this project during his Ph. D. at ARTIS
Rights and permissions
About this article
Cite this article
Paris, S., Sillion, F.X. & Quan, L. A Surface Reconstruction Method Using Global Graph Cut Optimization. Int J Comput Vision 66, 141–161 (2006). https://doi.org/10.1007/s11263-005-3953-x
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s11263-005-3953-x