3D Surface Reconstruction Using Graph Cuts with Surface Constraints

We describe a graph cut algorithm to recover the 3D object surface using both silhouette and foreground color information. The graph cut algorithm is used for optimization on a color consistency field. Constraints are added to improve its
of 13
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
  3D Surface Reconstruction Using Graph Cutswith Surface Constraints ⋆ Son Tran and Larry Davis Dept. of Computer Science, University of Maryland,College Park, MD 20742, USA { sontran, lsd } Abstract.  We describe a graph cut algorithm to recover the 3D ob- ject surface using both silhouette and foreground color information. Thegraph cut algorithm is used for optimization on a color consistency field.Constraints are added to improve its performance. These constraints area set of predetermined locations that the true surface of the object islikely to pass through. They are used to preserve protrusions and topursue concavities respectively in the first and the second phase of thealgorithm. We also introduce a method for dealing with silhouette uncer-tainties arising from background subtraction on real data. We test theapproach on synthetic data with different numbers of views (8, 16, 32,64) and on a real image set containing 30 views of a toy squirrel. 1 Introduction We consider the problem of reconstructing the 3D surface of an object froma set of images taken from calibrated viewpoints. The information exploitedincludes the object’s silhouettes and its foreground color or texture. 3D shaperecovery using silhouettes constitutes a major line of research in computer vision,the shape-from-silhouette approach. In methods employing silhouettes only (seee.g. [1]), voxels in a volume are carved away until their projected images areconsistent with the set of silhouettes. The resulting object is the visual hull.In general, the visual hull can be represented in other forms such as boundingedges ([2]), and can be reconstructed in a number of different ways. The maindrawback of visual hulls is that they are unable to capture concavities on theobject surface ([3]).A 3D surface can also be reconstructed using color or texture consistencybetween different views. Stereo techniques find the best pixel matching betweenpairs of views and construct disparity maps which represent (partial) shapes.Combining from multiple stereo maps has been studied, but is quite complicated([4]). Space carving ([5]) and recent surface evolution methods (e.g. [6], [7]) use a more general consistency check among multiple views.The combination of both silhouettes and foreground color to reconstruct anobject’s surface has been studied in a number of recent papers ([7], [8], [9]). ⋆ This work is supported by the NSF grant IIS-0325715 entitled ITR: New Technologyfor the Capture, Analysis and Visualization of Human Movement. A. Leonardis, H. Bischof, and A. Prinz (Eds.): ECCV 2006, Part II, LNCS 3952, pp. 219–231, 2006.c   Springer-Verlag Berlin Heidelberg 2006  220 S. Tran and L. Davis Our work is motivated by [8] and [10] where the graph cut algorithm serves as the underlying 3D discrete optimization tool. The near global optimalityproperties of the graph cut algorithm are discussed in [11]. As noted in [8] and in other works however, the graph cut algorithm usually prefers shorter cuts, whichleads to protrusive parts of the object surface being cut off. We overcome thislimitation with a two-phase procedure. In the first phase (phase I), protrusionsare protected during the optimization by forcing the solution to pass close to a setof predetermined surface points called “constraint points”. In the second phase(phase II), concavities on the object surface are aggressively pursued. Silhouetteuncertainties, which are important in practice but have been ignored in previousresearch ([8], [9], ...) are also taken into account. 1.1 Related Works The application of reliable surface points to constrain the reconstruction of asurface appears in a number of recent papers ([2], [7], [9], ...). Isidoro et al ([7]) refine the shape and texture map with an EM-like procedure; the evolution of the shape at each iteration is anchored around a set of locations called frontierpoints. Cheung et al ([2]) use another set of points called color surface pointsto align multiple visual hulls constructed at different times to obtain a closerapproximation to the object’s true surface. Usually, these points have no specialpatterns on the surface. In some cases, however, they might lie on continuouscurves such as the rims in [9], where each (smooth and closed) rim is a contourgenerator. The mesh of rims can be used to partition the surface into localpatches. Surface estimation is then performed individually for each patch, withsome interaction to ensure certain properties such as smoothness.The identification of these surface points is typically based on the silhouettesand color/photo consistency. A frontier point in [7] is the point with lowesttexture back-projection error among those on the evolving surface that projectonto a single silhouette point. Frontier points are recomputed at each iteration.The rims in [9] are built with a rim mesh algorithm. In order for the meshto exist, certain assumptions have to be made, the most limiting one being noself-occlusion. In [2], the colored surface points are searched for along boundingedges which collectively represent the surface of the object.Surface reconstruction methods that use color or texture such as [2], [8], [7], [9] and most stereo algorithms involve optimization. The srcinal space carvingalgorithm ([5]) used a simple greedy algorithm. Other examples of local methodsinclude stochastic search ([7]) and, recently, surface evolution using level sets orPDEs (e.g. [6]). Local techniques are often sensitive to initialization and localminimum. Here, we use the 3D graph cut algorithm which is more global in scope([11]). It was applied in [3] to solve the occupancy problem and in [10] for 3D image segmentation. The work described in [7] has similar motivation to ours:developing a constrained graph cut solution to object surface recovery. Theirconstraints are based on the rim mesh mentioned above. Multiple interconnectedsub-graphs are built, with one for each rim mesh face. Our constraint points arenot required to form rims and we use only one graph; our formulation is most  3D Surface Reconstruction Using Graph Cuts with Surface Constraints 221 similar to [8], which is the departure point for our research. Section 2 describesthe basic steps of the formulation from [8]. 2 Volumetric Graph Cuts Following [8], we first construct the visual hull  V   from the set of   N   imagesilhouettes, denoted  { Sil i } .  V   is used as the initial approximation to the objectshape. A photo consistency field for all voxels  v ∈ V   is constructed and used asthe graph on which a graph cut optimization is performed. Visibility for a voxel v ∈ V   ,  V is ( v ), is approximated with the visibility of the closest voxel to  v  on thesurface  S  out  of   V   . The consistency score for  v ,  ρ ( v ) is the weighted normalizedcross correlation (NCC) between the pairs of local image patches that  v  projectsto in the different views: ρ ( v ) =  C  i ,C  j ∈ V is ( v ) w (  pos ( C  i ,C  j )) NCC  (  p ( C  i ,v ) ,p ( C  j ,v )) (1)where  w (  pos ( C  i ,C  j ) is a weight depending on the relative position of the twocamera centers  C  i  and  C  j  (small when the difference between the viewing anglesof the  i  -th and  j  -th cameras is large and vice versa);  p ( C  i ,v ) is the local imagepatch around the image of   v  in the  i  -th image  I  i  . Fig.1.  a) a slice of the photo consistency field, yellow line denotes the true surface. b)Nodes and edges in the graph  G . If the surface,  S  out , of the visual hull,  V   , is not far from the actual surface S  ∗ , then with consistency computed this way, voxels that lie on  S  ∗ would havesmallest  ρ  values (Figure 1.a). Therefore, finding  S  ∗ can be formulated as anenergy minimization problem, where the energy is defined as E  ( S  ) =   S  ρ ( x ) dA  (2)A graph cut algorithm can be used to solve this problem in a manner similarto [12] and [10]. Each voxel is a node in the graph,  G , with a 6-neighbor systemfor edges. The weight for the edge between voxel (node)  v i  and  v j  is defined as  222 S. Tran and L. Davis w ( v i ,v j ) = 4 / 3 πh 2 ( ρ ( v i ) + ρ ( v j )) / 2 (Figure 1.b), where  h  is the voxel size.  S  out and  S  in  −  the surface inside  V   at a distance  d  from  S  out  −  form an enclosingvolume in which  S  ∗ is assumed to lie. Similar to [12] and [9], every voxel  v  ∈ S  in ( S  out ) is connected to the  Sink  ( Source ) node through an edge with veryhigh weight. With the graph  G  constructed this way, the graph cut algorithm isthen applied to find  S  ∗ . 3 Graph Cut with Surface Point Constraints As mentioned in [8], the above procedure suffers from the limitation that thegraph cut algorithm prefers shorter cuts. This produces inaccurate surfaces atprotrusions,which are often cut off ([8]). We addressthis problem by constrainingthe solution cut to pass through certain surface points. First we show how toidentify those points. Next, we show how to enforce the solution cut to passthrough or close to them. Finally, methods for dealing with silhouette uncertaintyare included. 3.1 Constraint on Surface Points Assume, to begin with, that the set of silhouettes has absolute locational cer-tainty. Every ray ( C  i ,p ji ) from a camera center  C  i  through a point  p ji  on thesilhouette  Sil i  has to touch the object surface at at least one point  P   ([2],[9]) (Figure 2.a). In [2], the authors search for  P   along this ray. We, addi-tionally, take into account the discretization of the silhouette and make thesearch region not a single ray ( C  i ,p ji ) but a surface patch  s  ⊂  S  out  where s  =  { v  |  v  ∈  S  out  and  v projects to p ji  through C  i } . Since every voxel on S  out  has to project onto some point on some silhouette { Sil i } , the union of all  s is  S  out . Therefore,  S  out  is completely accounted for when we search for all  P  ’s.In [7], the authors also use the projection from object space to silhouettes to findthe search regions for their set of constraint points. However, these regions, andtherefore the resulting constraint points, lie on an evolving surface and have tobe recomputed at each step of their iterative procedure. Here, the determinationof   P   is done only once and is based on  S  out , the surface of the srcinal visual hull. Fig.2.  a) Rays touch  V   ’s surface at  p , b) Example of the set of constraint points,  P  3D Surface Reconstruction Using Graph Cuts with Surface Constraints 223 Let  P  denotes the set of all such  P  ’s. To identify the location of each  P   ∈  P within its corresponding search region, we use color or texture information fromthe image foreground. Ideally, the images of such voxels should have zero consis-tency score  ρ  or zero color variance. Practically, they are voxelswhose projectionshave the lowest  ρ  within a search region. Figure 2.b shows an example of the con-straintpoints, P ,forthesyntheticfacethatisusedintheexperimentsinsection5.Note that their distribution is quite general and they do not obviously form rims.This creates difficulties for approaches that assume exact silhouette informationsuch as [9] and [13] . By marking which sub-regionsof   S  out  are produced by whichcamera,  P  can be constructed in time linear in the number of voxels in  S  out .If the average number of points on a silhouette is  n s , then the number of points in  P  is  N.n s . Many of them lie on protrusive parts of the object surface.In general,  P  provides a large set of constraints for the graph cut optimization. 3.2 Graph Cut with Surface Constraint Points Given the set of surface constraint voxels,  P , we want to construct a cut thatpasses through every voxel  p  ∈  P . Unfortunately, it is difficult to introducesuch constraints directly into the 3D graph cut algorithm. Instead, we adoptan indirect approach by blocking the solution surface from cutting a continuousregion that connects  p  and  S  in . Figure 3.a illustrates the blocking region: it isa curve  bl (  p ) from the surface point  p  ∈  P  to  S  in . More generally, a blockingregion can be represented as a blurred volume around the blocking curves usinga Gaussian blurring function. We next describe how to construct  bl (  p ).Let  D ( S  ) and  ∇ D ( S  ) denote the 3D distance transform of a surface  S   andthe gradient of the distance transform, respectively. For each  p  ∈  P , the cor-responding curve  bl (  p ) is constructed using  ∇ D ( S  out ) and  ∇ D ( S  in ) as follows.First, starting from  p , we move along  ∇ D ( S  out ) for a small distance  l . Second,we follow  −∇ D ( S  in ) until  S  in  is met. Points are added into  bl (  p ) as we move.To avoid redundancy, if a point is met that has been added to some previouslyconstructed  bl (  p ′ ), we stop collecting points for  bl (  p ). This procedure is carriedout for all points in  P . Fig.3.  a) Blocking regions (curves). b) Locational uncertainties (gray areas) of thecontour extracted from a difference image.
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks