| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Accurate and Scalable Surface Representation and Reconstruction from Images
January 2007 (vol. 29 no. 1)
pp. 141-158
We introduce a new surface representation method, called patchwork, to extend three-dimensional surface reconstruction capabilities from multiple images. A patchwork is the combination of several patches that are built one by one. This design potentially allows for the reconstruction of an object with arbitrarily large dimensions while preserving a fine level of detail. We formally demonstrate that this strategy leads to a spatial complexity independent of the dimensions of the reconstructed object and to a time complexity that is linear with respect to the object area. The former property ensures that we never run out of storage and the latter means that reconstructing an object can be done in a reasonable amount of time. In addition, we show that the patchwork representation handles equivalently open and closed surfaces, whereas most of the existing approaches are limited to a specific scenario, an open or closed surface, but not both. The patchwork concept is orthogonal to the method chosen for surface optimization. Most of the existing optimization techniques can be cast into this framework. To illustrate the possibilities offered by this approach, we propose two applications that demonstrate how our method dramatically extends a recent accurate graph technique based on minimal cuts. We first revisit the popular carving techniques. This results in a well-posed reconstruction problem that still enjoys the tractability of voxel space. We also show how we can advantageously combine several image-driven criteria to achieve a finely detailed geometry by surface propagation. These two examples demonstrate the versatility and flexibility of patchwork reconstruction. They underscore other properties inherited from patchwork representation: Although some min-cut methods have difficulty in handling complex shapes (e.g., with complex topologies), they can naturally manipulate any geometry through the patchwork representation while preserving their intrinsic qualities. The above properties of patchwork representation and reconstruction are demonstrated with real image sequences.
[1] A. Laurentini, “The Visual Hull Concept for Silhouette-Based Image Understanding,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 2, pp. 150-162, Feb. 1994.
[2] E. Boyer and J.-S. Franco, “A Hybrid Approach for Computing Visual Hulls of Complex Objects,” Proc. Computer Vision and Pattern Recognition Conf., vol. 1, pp. 695-701, June 2003.
[3] R. Cipolla and K.K. Wong, “Reconstruction of Sculpture From Its Profiles with Unknown Camera Positions,” IEEE Trans. Image Processing, vol. 13, no. 3, pp. 381-389, Mar. 2004.
[4] S. Sullivan and J. Ponce, “Automatic Model Construction and Pose Estimation from Photographs Using Triangular Splines,” IEEE Trans. Pattern Analysis Machine Intelligence, vol. 20, no. 10, pp.1091-1097, Oct. 1998.
[5] W. Matusik, C. Buehler, and L. McMillan, “Polyhedral Visual Hulls for Real-Time Rendering,” Proc. Eurographics Workshop Rendering, 2001.
[6] J. Isidoro and S. Sclaroff, “Stochastic Refinement of the Visual Hull to Satisfy Photometric and Silhouette Consistency Constraints,” Proc. IEEE Int'l Conf. Computer Vision, pp. 1335-1342, 2003.
[7] C.H. Esteban and F. Schmitt, “Silhouette and Stereo Fusion for 3D Object Modeling,” Computer Vision and Image Understanding, vol. 96, no. 3, pp. 367-392, Dec. 2004.
[8] S.M. Seitz and C.R. Dyer, “Photorealistic Scene Reconstruction by Voxel Coloring,” Proc. Computer Vision and Pattern Recognition Conf., pp. 1067-1073, 1997.
[9] K.N. Kutulakos and S.M. Seitz, “A Theory of Shape by Space Carving,” Int'l J. Computer Vision, vol. 38, no. 3, pp. 199-218, 2000.
[10] K.N. Kutulakos, “Approximate N-View Stereo,” Proc. European Conf. Computer Vision, pp. 67-83, 2000.
[11] R. Szeliski and P. Golland, “Stereo Matching with Transparency and Matting,” Int'l J. Computer Vision, vol. 32, no. 1, pp. 45-61, 1999.
[12] J.S. de Bonet and P. Viola, “Poxels: Probabilistic Voxelized Volume Reconstruction,” Proc. Int'l Conf. Computer Vision, 1999.
[13] A. Broadhurst, T. Drummond, and R. Cipolla, “A Probabilistic Framework for Space Carving,” Proc. IEEE Int'l Conf. Computer Vision, pp. 388-393, July 2001.
[14] G.G. Slabaugh, W.B. Culbertson, T. Malzbender, and R.W. Schafer, “A Survey of Methods for Volumetric Scene Reconstruction from Photographs,” Proc. Int'l Workshop Volume Graphics, June 2001.
[15] S. Osher and J.A. Sethian, “Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations,” J. Computational Physics, vol. 79, pp. 12-49, 1988.
[16] O. Faugeras and R. Keriven, “Complete Dense Stereovision Using Level Set Methods,” IEEE Trans. Image Processing, vol. 7, no. 3, 1998.
[17] H. Jin, A.J. Yezzi, and S. Soatto, “Region-Based Segmentation on Evolving Surfaces with Application to 3D Reconstruction of Shape and Piecewise Constant Radiance,” Proc. European Conf. Computer Vision, 2004.
[18] M. Lhuillier and L. Quan, “Surface Reconstruction by Integrating 3D and 2D Data of Multiple Views,” Proc. Int'l Conf. Computer Vision, Oct. 2003.
[19] H. Jin, S. Soatto, and A.J. Yezzi, “Multi-View Stereo beyond Lambert,” Proc. Computer Vision and Pattern Recognition Conf., vol. 1, pp. 171-178, 2003.
[20] D. Adalsteinsson and J.A. Sethian, “A Fast Level Set Method for Propagating Interfaces,” J. Computational Physics, vol. 118, pp. 269-277, 1995.
[21] D. Terzopoulos, A. Witkin, and M. Kass, “Constraints on Deformable Models: Recovering 3D Shape and Nonrigid Motion,” Artificial Intelligence, vol. 36, no. 1, pp. 91-123, 1988.
[22] S. Roy and I.J. Cox, “A Maximum-Flow Formulation of the n-Camera Stereo Correspondence Problem,” Proc. IEEE Int'l Conf. Computer Vision, pp. 492-499, Jan. 1998.
[23] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
[24] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.
[25] S. Paris, F. Sillion, and L. Quan, “A Surface Reconstruction Method Using Global Graph Cut Optimization,” Int'l J. Computer Vision, vol. 66, no. 2, pp. 141-161, Feb. 2006.
[26] D. Kirsanov and S.J. Gortler “A Discrete Global Minimization Algorithm for Continuous Variational Problems,” Technical Report TR-14-04, Harvard Computer Science, July 2004.
[27] C. Buehler, S. Gortler, M. Cohen, and L. McMillan, “Minimal Surfaces for Stereo,” Proc. European Conf. Computer Vision, 2002.
[28] Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, Nov. 2001.
[29] V. Kolmogorov and R. Zabih, “What Energy Functions Can Be Minimized via Graph Cuts,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 2, Feb. 2004.
[30] V. Kolmogorov and R. Zabih, “Multi-Camera Scene Reconstruction via Graph Cuts,” Proc. European Conf. Computer Vision, May 2002.
[31] M. Lin and C. Tomasi, “Surfaces with Occlusions from Layered Stereo,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 710-717, Aug. 2004.
[32] M. Bleyer and M. Gelautz, “Graph-Based Surface Reconstruction from Stereo Pairs Using Image Segmentation,” Proc. SPIE Conf., 2005.
[33] Y. Boykov and V. Kolmogorov, “Computing Geodesics and Minimal Surfaces via Graph Cuts,” Proc. IEEE Int'l Conf. Computer Vision, vol. 1, pp. 26-33, Oct. 2003.
[34] G. Vogiatzis, P. Torr, and R. Cipolla, “Multi-View Stereo via Volumetric Graph-Cuts,” Proc. Computer Vision and Pattern Recognition Conf., 2005.
[35] A. Blake and A. Zisserman, Visual Reconstruction. MIT Press, 1987.
[36] P. Fua, “From Multiple Stereo Views to Multiple 3-D Surfaces,” Int'l J. Computer Vision, vol. 24, no. 1, pp. 19-35, 1997.
[37] P.J. Narayanan, P. Rander, and T. Kanade, “Constructing Virtual Worlds Using Dense Stereo,” Proc. Int'l Conf. Computer Vision, 1998.
[38] W. Hoff and N. Ahuja, “Surfaces from Stereo: Integrating Feature Matching, Disparity Estimation, and Contour Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 121-136, 1989.
[39] R.L. Carceroni and K.N. Kutulakos, “Multi-View Scene Capture by Surfel Sampling: From Video Streams to Non-Rigid 3D Motion, Shape & Reflectance,” Proc. IEEE Int'l Conf. Computer Vision, vol. 2, 2001.
[40] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel, “Multi-Level Partition of Unity Implicits,” ACM Trans. Graphics, vol. 22, no. 3, pp. 463-470, 2003.
[41] B. Curless and M. Levoy, “A Volumetric Method for Building Complex Models from Range Images,” Proc. SIGGRAPH Conf., 1996.
[42] W.E. Lorensen and H.E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Proc. SIGGRAPH Conf., pp. 163-169, 1987.
[43] V. Kolmogorov, R. Zabih, and S. Gortler, “Generalized Multi-Camera Scene Reconstruction Using Graph Cuts,” Proc. Int'l Workshop Energy Minimization Methods in Computer Vision and Pattern Recognition, July 2003.
[44] B.V. Cherkassky and A.V. Goldberg, “On Implementing the Push-Relabel Method for the Maximum Flow Problem,” Algorithmica, vol. 19, no. 4, pp. 390-410, 1997.
[45] S. Roy, “Stereo without Epipolar Lines: A Maximum-Flow Formulation,” Int'l J. Computer Vision, vol. 34, nos. 2/3, pp. 147-162, Aug. 1999.
[46] P. Perona and J. Malik, “Scale-Space and Edge Detection Using Anisotropic Diffusion,” IEEE Trans. Pattern Analysis Machine Intelligence, vol. 12, no. 7, pp. 629-639, July 1990.
[47] C.L. Zitnick, S.B. Kang, M. Uyttendaele, S. Winder, and R. Szeliski, “High-Quality Video View Interpolation Using a Layered Representation,” ACM Trans. Graphics, vol. 23, no. 3, July 2004.
[48] M.J. Black, G. Sapiro, D.H. Marimont, and D. Heeger, “Robust Anisotropic Diffusion,” IEEE Trans. Image Processing, vol. 7, no. 3, pp.421-432, Mar. 1998.
[49] P. Le Tallec, “Domain Decomposition Methods in Computational Mechanics,” Computational Mechanics Advances, vol. 1, no. 2, pp.123-217, 1994.
[50] G. Zeng, S. Paris, L. Quan, and F. Sillion, “Progressive Surface Reconstruction from Images Using a Local Prior,” Proc. Int'l Conf. Computer Vision, 2005.
[51] W.B. Culbertson, T. Malzbender, and G.G. Slabaugh, “Generalized Voxel Coloring,” Proc. Int'l Workshop Vision Algorithms, pp. 100-115, Sept. 1999.
[52] H. Jin, A.J. Yezzi, Y. Tsai, L. Chen, and S. Soatto, “Estimation of 3D Surface Shape and Smooth Radiance from 2D Images: A Level Set Approach,” J. Scientific Computing, vol. 19, no. 1-3, pp. 267-292, 2003.
[53] A. Sharf, M. Alexa, and D. Cohen-Or, “Context-Based Surface Completion,” ACM Trans. Graphics, vol. 23, no. 3, July 2004.
[54] G. Zeng, S. Paris, L. Quan, and M. Lhuillier, “Surface Reconstruction by Propagating 3D Stereo Data in Multiple 2D Images,” Proc. European Conf. Computer Vision, 2004.
[55] M. Lhuillier and L. Quan, “A Quasi-Dense Approach to Surface Reconstruction from Uncalibrated Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 3, pp. 418-433, Mar. 2005.
[56] N. Amenta, S. Choi, and R. Kolluri, “The Power Crust, Unions of Balls, and the Medial Axis Transform,” Computational Geometry: Theory and Applications, vol. 19, nos. 2-3, pp. 127-153, 2001.
[57] H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, and W. Stuetzle, “Piecewise Smooth Surface Reconstruction,” Proc. SIGGRAPH Conf., pp. 295-302, 1994.
[58] M. Lhuillier and L. Quan, “Match Propagation for Image-Based Modeling and Rendering,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 8, pp. 1140-1146, Aug. 2002.
[59] Y. Boykov and V. Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 9, Sept. 2004.
Index Terms:
Computing methodologies, image processing and computer vision, reconstruction and applications, patchwork representation and reconstruction, space carving, graph-cuts, level-sets, patch-wise carving, patch-wise propagation.
Citation:
Gang Zeng, Sylvain Paris, Long Quan, Fran?ois Sillion, "Accurate and Scalable Surface Representation and Reconstruction from Images," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 141-158, Jan. 2007, doi:10.1109/TPAMI.2007.4
