TERZOPOULOS: COMPUTATION
OF
VISIBLE-SURFACE
REPRESENTATIONS
42
I
1)
Reconstruct a tentative
C'
continuous surface on
Q;
i.e., solve
VP1
with
p(x,
y)
=
7(x,
y)
=
1.
2) Introduce significant depth discontinuities into the
resulting surface; i.e., set
p(x,
y)
=
0
at
{
(x,
y)
1
M(x,
y)
=
0
and
G(x,
y)
>
td
}
and continue the reconstruc-
tion by solving
VP1.
3) Introduce significant orientation discontinuities into
the resulting surface; i.e., set
~(x,
y)
=
0
at
{
(x,
y)
1
VM(x,
y)
=
0
and
I
M(x,
y)
1
>
to}
and continue
the reconstruction by solving
VP1.
4)
Repeat steps 2) and
3)
with decreasing
td
and
to.
Step
4)
sets up an iterative
continuation
cycle for solv-
ing VP1, where steps
2)
and 3) continue using the surface
resulting from the immediately preceding step (here,
(4)
becomes a quasilinear equation due to the dependence
of
p
and
7
not only on position but also on partial derivatives
of
U).
It is wasteful
to
compute each approximation to
high accuracy, since it serves only as an initial condition
toward computing a better approximation over the suc-
ceeding cycle.
The local validation procedure is reminiscent of the
common practice
of
detecting intensity edges in image
functions by applying thresholded local difference opera-
tions. Since a local edge operator, such as a Laplacian, is
easily corrupted by noise, a smoothing prefilter is usually
applied to the image to improve the response.
S,,
has an
analogous smoothing effect on scattered, noisy shape con-
straints (standard low-pass filters, such as Gaussians, are
inapplicable to irregular samples). While regularization
based smoothing permits the reliable computation of nu-
merical derivatives in continuous regions [%], the
smoothing property of the tentative surface computed in
step
1)
tends to obscure subtle discontinuities
[56].
This
problem is also typical of smoothing edge detection op-
erators [39].
B.
Discontinuity Identijication
by
Variational Continuity
Con tro
1
The second discontinuity identification approach
embeds
VP1
within an outer variational principle which
estimates the continuity control parameters
p
(x,
y)
and
~(x,
y).
The surface is permitted to crease and fracture in
order to reduce the total energy below the minimum ob-
tainable with a globally
C'
surface. This resolves the con-
flict between discontinuity identification and regulariza-
tion smoothing.
Variational continuity control is formulated in terms of
the following variational problem:
VP2:
Find
U,
p*,
and
7*
such that
€(U,
p*,
T*)
=
inf
€(U,
p,
7),
(9)
P,
7
where
€(U,
P,
7)
=
D(p,
7)
+
infE,,(v);
(10)
(11)
V
q&4
=
S,,(U)
+
@(U).
Assuming suitable continuity,
u(x,
y),
p*(x,
y),
and
T*
(x,
y)
satisfy the coupled, nonlinear Euler-Lagrange
equations
a
ay
-
-
(7pJ
+
6,@(u)
=
0;
-
(U:
+
U,",]
+
6,*D(p*,
7*)
=
0,
(12)
with suitable boundary conditions on
aQ.
The functional
D(
p,
7)
maps
p(x,
y)
and
7(x,
y)
into
a nonnegative energy. Its role in the outer problem is
analogous to that
of
SpT(
U)
in the inner problem
VP1:
it
serves as a stabilizer for estimating the continuity control
functions from the available surface shape constraints.
Locally reducing the smoothness of the surface will re-
duce its resistance to sudden deflections imposed by the
data and hence release potential energy; i.e., from
(5),
S,,(
U) considered as a function of
(U,
p,
7)
decreases as
1
Sn
p(x,
y)
dx
dy
and
1
So
~(x,
y)
dx
dy
decrease. The
introduction of discontinuities must be penalized, how-
ever, because
p(x,
y)
=
0
everywhere would trivially
minimize the energy. The penalty can simply increase
monotonically according to a total discontinuity measure;
e.g.,
7)
=
j
j
Pd[l
-
P(.,Y)]
D
+
Pop
-
.(x,
Y)]
dx
dY,
(13)
where
pd
and
Po
are positive energy scaling parameters
for the depth and orientation discontinuity contributions,
respectively.
More interestingly,
D
(
p,
7)
can express a predisposi-
tion for discontinuities arranged along piecewise contin-
uous
contours in the
x
-
y
plane (making allowances with
regard to the condition in footnote
1).
An appealing for-
mulation is in terms of curvilinear controlled-continuity
constraints; for instance,
the curvilinear analog of
Spr,
where
s
denotes arc length
along contours
c
(s)
=
[x(
s),
y
(s)
] in
C,
a collection of
discontinuity contours. Here, locally zeroing
&,
allows
break points, while locally zeroing
0,
allows tangent dis-
continuity points to form in the contours. Again, these
events require energy penalties. Naturally, +he embedded