Accurate and Scalable Surface Representation and Reconstruction from Images

• Published in: IEEE transactions on pattern analysis and machine intelligence 2007-01, Vol.29 (1), p.141-158
• Main Authors: Gang Zeng, Paris, S., Long Quan, Sillion, F.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Artificial Intelligence; Cameras; Complexity; Computer science; control theory; systems; Computing methodologies; Exact sciences and technology; Geometry; graph-cuts; Image Enhancement - methods; Image Interpretation, Computer-Assisted - methods; image processing and computer vision; Image reconstruction; Image sequences; Imaging, Three-Dimensional - methods; Information Storage and Retrieval - methods; Intelligence; Layout; Level set; level-sets; Materials handling; Optimization; Optimization methods; Optimization techniques; patch-wise carving; patch-wise propagation; patchwork representation and reconstruction; Pattern Recognition, Automated - methods; Pattern recognition. Digital image processing. Computational geometry; Preserving; Reconstruction; reconstruction and applications; Representations; Reproducibility of Results; Sensitivity and Specificity; Shape; space carving; Studies; Surface reconstruction; Topology
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2007.250605

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