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
}
@cs.umd.edu
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 ﬁeld.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 ﬁrst and the second phase of thealgorithm. We also introduce a method for dealing with silhouette uncertainties arising from background subtraction on real data. We test theapproach on synthetic data with diﬀerent 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 shapefromsilhouette 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 diﬀerent 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 diﬀerent views. Stereo techniques ﬁnd 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 IIS0325715 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
SpringerVerlag 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 oﬀ. We overcome thislimitation with a twophase procedure. In the ﬁrst 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])
reﬁne the shape and texture map with an EMlike 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 diﬀerent 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 identiﬁcation of these surface points is typically based on the silhouettesand color/photo consistency. A frontier point in [7] is the point with lowesttexture backprojection 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 noselfocclusion. 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 interconnectedsubgraphs 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 ﬁrst 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 ﬁeld 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 diﬀerent 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 diﬀerence 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 ﬁeld, 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, ﬁnding
S
∗
can be formulated as anenergy minimization problem, where the energy is deﬁned 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 6neighbor systemfor edges. The weight for the edge between voxel (node)
v
i
and
v
j
is deﬁned 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 ﬁnd
S
∗
.
3 Graph Cut with Surface Point Constraints
As mentioned in [8], the above procedure suﬀers from the limitation that thegraph cut algorithm prefers shorter cuts. This produces inaccurate surfaces atprotrusions,which are often cut oﬀ ([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 certainty. 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, additionally, 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 ﬁndthe 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 consistency score
ρ
or zero color variance. Practically, they are voxelswhose projectionshave the lowest
ρ
within a search region. Figure 2.b shows an example of the constraintpoints,
P
,forthesyntheticfacethatisusedintheexperimentsinsection5.Note that their distribution is quite general and they do not obviously form rims.This creates diﬃculties for approaches that assume exact silhouette informationsuch as [9] and [13] . By marking which subregionsof
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 diﬃcult 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 corresponding 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 diﬀerence image.