1Accurate and Scalable Surface Representationand Reconstruction from ImagesGang ZENG1Sylvain PARIS2Long QUAN1Franc¸ois SILLION31Dep. of Computer Science, HKUST, Clear Water Bay, Kowloon, Hong Kong{zenggang,quan}@cs.ust.hk2CSAIL - MIT, 32 Vassar Street, Cambridge, MA 02139, [email protected] / GRAVIR-IMAG, INRIA Rhˆone-Alpes, 38334 Saint Ismier, [email protected] submitted to PAMI on Sep. 08, 2005.September 14, 2005 DRAFT2AbstractWe introduce a new surface representation, the patchwork, to extend the problem of surfacereconstruction from multiple images. A patchwork is the combination of several patches that arebuilt one by one. This design potentially allows the reconstruction of an object of arbitrarily largedimensions while preserving a fine level of detail. We formally demonstrate that this strategy leads to aspatial complexity independent of the dimensions of the reconstructed object, and to a time complexitylinear with respect to the object area. The former property ensures that we never run out of storage(memory) and the latter means that reconstructing an object can be done in a reasonable amount oftime. In addition, we show that the patchwork representation handles equivalently open and closedsurfaces whereas most of the existing approaches are limited to a specific scenario (open or closedsurface but not both).Most of the existing optimization techniques can be cast into this framework. To illustrate thepossibilities offered by this approach, we propose two applications that expose how it dramaticallyextends a recent accurate graph-cut technique. We first revisit the popular carving techniques. Thisresults in a well-posed reconstruction problem that still enjoys the tractability of voxel space. We alsoshow how we can advantageously combine several image-driven criteria to achieve a finely detailedgeometry by surface propagation. These two examples demonstrate the versatility and flexibility of thepatchwork reconstruction. The above properties of the patchwork representation and reconstructionare extensively demonstrated on real image sequences.Index Terms(I. Computing Methodologies).(4 Image Processing and Computer Vision).(5 Reconstruction &9 Applications): patchwork representation and reconstruction, space carving, graph-cuts, level-sets,patch-wise carving, patch-wise propagation.September 14, 2005 DRAFT3I. INTRODUCTIONThree-dimensional reconstruction from multiple images is a natural extension to stereoscopicreconstruction. Combining the information from several images make the process more robustand precise. It is also possible to handle larger scenes since more viewpoints and view directionsare available. A wealth of quality work has been produced to address the resulting challengesto propose usable applications in the domains of virtual reality, movie making, entertainment,etc. In particular, great progress has been made in terms of camera calibration and surfaceoptimization. The former retrieves the parameters of the cameras such as their positions andfocal lengths, while the latter produces the actual geometry of the scene. In this paper, we focuson the geometry reconstruction part.Two major issues remain largely unaddressed: scalability and flexibility. First, even in afavorable situation, one cannot recover an arbitrarily large geometry due to resource lim-itations. Most of the existing techniques handle the entire scene at once. Therefore, for agiven resolution, the size of the reconstructed scene is bounded by the available memory ofthe machine that executes the program. In addition to this storage issue, since the temporalcomplexity of the optimization algorithms is high (i.e. more than linear), increasing the scenesize inherently leads to an explosion in the processing time. Thus, large scenes are limitedto large scale reconstructions that ignore the fine details. Second, existing methods representthe object surface either with a single-value explicit depthfield z(x, y) (or d(x, y) for disparitymaps) or with a voxel space or an implicit function φ(x, y, z) = 0 (a.k.a. level set). Thesetwo options address different configurations. Depthfields and disparity maps perform well withcameras that lie only on one side of the scene but they are hard to extend to arbitrary camerapositions. Level sets provide effective solutions when numerous cameras are available but theybreak down with limited view directions. As a consequence, these techniques cannot cope withan arbitrary camera layout, and the user has to select the algorithm according to the scenario.In order to overcome these limitations, in this paper we present the patchwork surface repre-sentation. It consists of a collection of small surface pieces, the patches, that are progressivelyreconstructed and stitched together. Despite its apparent simplicity, it implies a fundamentalassumption that the reconstruction problem is a local issue. Let us consider the example ofacquiring the geometry of a head. It seems reasonable and even desirable that, whatever processwe use, the shape of one ear does not depend on the shape of the other. Another behavior wouldmean for instance that adding an earring on one side changes the geometry of the other ear. ItSeptember 14, 2005 DRAFT4would be incoherent. This assumption is formally defined and assessed. We show that exceptthe visibility all the other components involved in the existing optimization techniques are local.Independent of the selected optimization technique, the patchwork representation inducesseveral interesting gains. The first advantage is that dealing with patches makes the amountof handled data fixed and the processing time proportional to the number of patches. Theseproperties are formally stated and proven. Second, the patch parameterization can be adjustedfor each patch. For instance, this allows the representation of complex surfaces with methodsthat usually handle only depthfields or disparity maps. Third, the formulation is independent ofthe surface topology, the same algorithm deals seamlessly with both open and closed surfacesdepending on the setup. If the cameras provide enough information, the whole scene is built; ifnot, only a partial reconstruction is achieved.We also address the practical issues that make this representation fully usable. All the patchesare registered into a distance field to build a coherent structure. We define a proper shapefor the patches in order to preserve the continuity at their