The Role of Constraints and Discontinuities in Visible-Surface Reconstruction

1. INTRODUCTION

Surface perception is comprised of several stages of visual analysis beginning with the retinal images and progressing to the construction of visib/e-swj(Jce reprrsentations. These representations arc explicit descriptions or the visible surl':lces in a scene in terms of their geometrical properties (local depths and orientations of surfaces with respect to the viewer) and of their rcllcctance properties (colors, textures, etc.). The concept of a visible-surface representation may be envisaged as Marr's [1982] 2~-D sketch, or, almost equivalently, as Barrow and Tenenbaum's [1978] intrinsic images.

Numerous specialized visual processes contribute raw infonna· tion about visible surfaces. According to current theories, early visual processing is based on sparsely scattered evcms made explicit in early representations that Marr named primal sketches (sec. e.g., [Marr, 1982]). Consequently, must of the raw information generated takes the form of scallered constraints on surface shape; however, surfaces arc nmmally perceived as being dense and coherent. This suggests the existence of a visible-surjace reconst111ction process that computes from the raw constrnints visible-surface representations containing explicit shape in !ormation almost everywhere. Moreover, dense surface shape in formation. including depth or orientation or both, is desirable in that it greatly facilitates subsrqucnt surface analysis tasks.

Whether the intention is to model human vision, or to guide practical applications, it seems that the visible-surface reconstruction process must solve at least four problems.

• (i) The constraint integration problem: Each specialized visual process may be thought of as an approximately independent source of partial information about visible surfaces. Processes such as stereopsis [Marr and Poggio, 1979] and analysis of mo­ tion [Ullman, 1979] naturally generate local information about the distances of surfaces from the viewer, while processes that

This report describes research done at the Artificial Intelligence Laboratory of the MassadtusetLS Insti tute of Technology. Support for the laboratory's Artilirial Intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Rescar· ch contmct N000l4-75-C·OG43. the Office of Naval Research under contract number N0014-80-C-0505, and the System Development Foundation. The author is supported by postgraduate scholarships from the Natural Sciences and Engiucering Research Council of Canada and from Fonds F.C.A.C. pour !'aide et le soutien a Ia recherche, Quebec, Canada.

uniqueness shows that we may choose a = 0 [l'crwpoulos, 1982) to obtain the simplified functional

and this choice can be shown to be valid for the generalized devel­ opment in this paper (sec [Tcrzopoulos, l983b) for details).

The admissible function space V turns out to be the second­ order Sobolcv space )/ 2 (rl) [l'crzopoulos, 1982[. Member functions of )1 2 (rl) which arc physically meaningful plate configurations possess at least the necessary smoothness (C 1 continuity) required to interpolate between depth constraints [Tcrzopoulos. 1983a), as dictated by the psychophysics of surface perception [Grimson, 1981).

Depth constraints were modeled as rigidly-fixed ve1tical pins, located at a scattered set D of points in n. with heights (i .e., known depth values) given by real scalars d(.,,y;) for all (x;, y;) E D. '!be pins constrain the plate by way of (zero natural length) ideal springs connecting the plate surface to the pin tips. The influence of each constraint may be controlled by assigning positive spring constants (stifTncsscs) fl( x, ,y;)· As the springs deform, they contribute a total potential energy to the system which is given by

This expression is as an additive penally funclional which penalizes local mismatches between admissible surfaces v(x, y) and constraints.

In addition to explicit depth constraints, information about the local orientation of surfaces may be available at scattered locations within rl. The normal vector [vx,vy, - 1] to the surface v(x,y), is specified completely at any point on the surface by the values of the partial derivatives p = v, and q = vy at that point. Orientation constraints can be handled analogously to depth constraints by locally coercing the surface into aligning as consistently as possible with known p-constraints, P(x, ,y;J . (x;, y,) E P, and q-constraints, q(.,,y,)· (:,;;, y,) E Q. The quadratic penalty functional

is suggested, where v, (x;, y;) and vy(x;, y;) are the values of the first partial derivatives of the surface v at points in P and Q respectively, and where CIP(x,,y;) and a,,,,,,y;) are associated constants analogous to the spring constants for the case of depth constraints.

In summary, the extended variational principle for visible surface rcconstmction integrating both depth and orientation constraints, in the case of a single visible-surface patch without discontinuities, is posed as a variational principle involving the minimization of the functional c(v) = cp(v) + c<~ (v) + C'a(v). Hence, the reconstructed surface is given by a deflection function u(x, y) defined over rl that represents the plate's surface in equilibrium. The reconstructed surface is the "best" possible given all avai lable constraints from early visual processing. Given suflicient constraints, there will exist a unique surface u(x, y) which solves the variational principle and which depends continuously on the constraints. It can be shown that the minimal conditions for existence and uniqueness are not restrictive, considering the wealth of information generally provided by early visual processing [Tcrzopoulos, 1983b]. Hence our formulation of the surface rcconstmction problem is well posed in general.

3. DISCONTINUITIES

Deplh disconlinuilies typically occur along occluding contours; that is, loci along which one surface occludes part of itself or another surface from the viewer. Occluding contours delimit ,·biblc-surtace p:1tches and provide much usr: f1il in fonnation about the shapes of ccnain classes of surfaces. Because there can in general be no predictable relationship between properties of surfaces on either side of an occluding contour_ the presence of occluding contours imposes strong restrictions on interpolation. Constraints on one side of the co mom must not influence the surface reconstructed on the other side, and conversely. In terms of the plate model for surface reconstruction, this can be accomplished by "breaking" the plate along occluding boundaries, thereby inhibiting the interpolation process across them. This yields a piecewise continuous reconstructed surface.

Surface crcnscs usually give rise to orienlalion disconlinuilies­ loci along which depth remains continuous, but surface orienta­ tion changes abruptly. The smoothness afforded by the thin plate must be relaxed at known orientation discontinuities so that the reconstructed surface remnins continuous but oflers no resistance to bending. Physically, the rcconstnicted surface should behave as a membrane surface in the immediate vicinity of orientation discon­ tinuities; elsewhere within visible-surface patches it should behave as a thin plate. Now, the dej/eclion af a membrane a/ equilibrium is I hal June/ion u from a set V of admissible functions v for which lhe lola/ palenlial energy C'm(v) for lhe membrane is minimal. Here, the energy c, (v) is proportional to change in area of the membrane. Assuming small deflections [Courant and Hilbert, 1953],

The admissible function space V is the first-order Sobolev space )I 1 (rl). Member functions of )I 1 (rl) which arc physically meaningful membrane configurations must be continuous (but, unlike the plate, need not be C 1 ).

To summarize, the reconstructed surface is modeled as con­ strained thin-plate patches joined by membrane strips along orien­ tation discontinuities; and so: The solulion of Jhe general surface recons/ntclion problem is defined by a configura/ion which minimizes Jhe lola/ polenlial energy [ of Jhe physical syslem comprised of the lhin-~lale patches, membrane slrips, and springs.

4. DISCRETIZATION VIA FINITE ELEMENTS

We need to approximate the solution u in terms of functions that arc convenient representations of visible surfaces. A set of theorems from functional analysis guarantee that, because our problem is well-posed, an optimal (closest in the strain energy norm) discrete approximntion can be obtained within a finite dimensional subspace of the admissible space V [Terzopoulos, 1982, 1983a]. The jinile elemenl method is a systematic procedure for constructing a subspace S", called a .finile elemenl space, of functions v" that are very convenient for numerical computation by virtue of the fact that the basis functions of S" are simple. local support polynomials [Strang and Fix, 1973).

The finite clementE shown in Fig. 1 was defined in [Terz.opoulos, 1982) and shown to be applicable to surface reconstruction because it satisfies certain completeness and consistency conditions. Since the clements impose a uniform tesselation T h over n and the nodes form a uniform square grid, it is convenient to index the nodes by (i,J). The (unknown) displacement at node (i,J) is denoted by the nodal variable v7oJ and all the nodal variables together by a vector v" E !Ji". The plate energy functional can be now be expressed as a sum of integrals 01cr the individual clement domains, wherein the second-order partial derivatives of pr:; arc constnnts. Noting that the area of each clement is h 2 and substituting the expressions for the derivatives into (1) yields

5. PLATE MOLECULES

The energy-minimizing vector of displacements uh satisfies the condition "V [ h(uh) = 0, where "V is the gradient operator. Since the discrete functional is a quadratic form in the v~'- 1 , the minimi7.ing vector is the solution of a system of linear equations. We need the partial derivative of £~(uh) with respect to u~.J· From the above equation, we get

For reasons that will become apparent shortly, the terms on the right hand side of (5) arc best visualized as the set of computational 111olecules shown in Fig. 2. When (i, j) is an interior node- a node in the interior of n, away from both discontinuities and constraints­ the equilibrium condition is expressed by setting to zero the sum of all the terms in {5). This gives a linear, local-support nodal equation (sec Fig. 3).

6. CONSTRAINT MOLECULES

The effects of depth constraints on the reconstructed surface were specified quantitatively in tenns of the penalty functional given by (2). Assume for simplicity that all depth constraints d(z; ,y;) E D coincide with nodes ( i, f) in T h. Henceforth, the constraints will be denoted by d7". The penalty functional becomes [~(~h)= ~ I:(i,J)ED{3;~J(v?,1 -- d7.Jt Now,

which can be represented by the trivial depth constraint molecule and associated constant term shown in Fig. 4.

The treatment of orientation constraints follows analogously from that of depth constraints. Assume for simplicity that all orien­ tation constraints P( z;,y;) E P and q1 ,,y,) E Q coincide with interior nodes (i,J} in T". Hcnccfonh ·denote them by p:·. 1 and q?,J· and denote the partial derivatives of the surface at (i,J) by p~J and q~'. 1 · Then, the orientation consu·aint -~cnalty functional (J} becomes £~(~") = ~ '2:(.,1)Ei' a,~)P:~i - P7,;}' H 'I:ti,1)EQ aq~ , (q~1 - q?.Jt Expressing the panial derivatives in terms of nodal variables via the finite clement gives p~ 1 = p~(O,O} = (v?+t.J- v~_ 1 J/2h, and q~ 1 = p;(o,o) = (v?,J+t- v~,J- 1 )/2h. Substituting, we obtain

which can be represented by the orientation constraint molecules and associated constant terms shown in Fig. 5.

7. DISCONTINUITIES AND MOLECULAR INHIBITION

Discontinuities inhibit the summation of plate and constraint molecules. In the following discussion, assume for simplicity that all depth discontinuities coincide with nodes in the tesselation Th of n.

Depth discontinuities must be handled as free boundaries which can be introduced by removing finite clements, thereby modeling a fractured plate. Missing elcmenL~ can be handled as follows: Depth discontinuity nodes arc special in that (i) the displacement is undefined there, and (ii) they it inhibit plate and constraint molecules. The first property implies that a depth discontinuity node has no nodal variable and, hence. no nodal equation. Consequently, it is meaningless for a depth discontinuity to coincide with a depth constraint. Regarding the second property, consider a boundary node ( i, j) that is ncar enough to a depth discontinuity such that the di scontinuity coincides with any of the atoms of a plate or constraint molecule associated with the node. If this occurs. the depth discontinuity inhibits the summation of the molecules in question (sec Fig. 6).

The situation for orientation discontinuities is somewhat more complicated. The effect of orientation discontinuity nodes on interior nodes is precisely the same as that of depth discontinuity nodes - they too inhibit the summation uf the aforementioned computa­ tional molecules. On the other hand. unlike depth discontinuity nodes, orientation discontinuity nodes do have associated nodal dis· placements; however, these displacement~ arc governed by the varia­ tional principle for the membrane. A discrete approximation for the membrane problem is obtained via the finite element method (see Fig. 7).

Suppose that node ( i, J.) is an interior orientation discontinuity, none of whose neighbors arc depth discontinuities. The patch of membrane surrounding the node contributes potential energy to the total energy functional. We discrctizc the patch by triangulation using the linear clement above. Only the six clements E1, ... , E6 shown in Fig. 8 depend on node (i ,j), and they contribute the energy

whose terms are represented by the membrane molecules shown in Fig. 9. Fig. 10 illustrates the resulting nodal molecule at an interior orientation discontinuity.

Note that depth discontinuities inhibit the summation of mem­ brane molecules (Fig. 11). Orientation discontinuities inhibit orienta­ tion constraint molecules. On the contrary, depth constraint molecules are not inhibited by orientation discontinuities since it is perfectly reasonable to constrain membrane strips in depth.

----------- -

8. CONCLUDING REMARKS

Our computational theory of visible-surface representations has been made more complete. We have formulated the construction of nodal equations under the influence of constraints and discontinuities. The casily-irnplcmcntable wnstructioo was envisaged essentially as the summation of basic computational molecules subject to possible inhibition from nearhy discontinuities. It is important to realize that what we end up with is a large system of linear equations (one for each node. excluding depth discontinuities). This system, however, is sparse and can therefore be solved rapidly by the multilevel algorithms described in [Terzopoulos, 1982, l983a) (sec [l'erwpoulos, 1983b]).

We showed how discontinuities in surface geometry can be represented, anc! characterized their influence on visible-surface reconstruc­ tion, but we have ignored the important problem of detecting them. It is clear that prominent discontinuities can be inferred prior to surface reconstruction by (in general, interactions among) the early visual processes. while subtle discontinuiues must await detection until sur­ face reconstruction, during which full depth maps become available fl'crzopoulos, l983b]. Fig. 12 illu-;tratcs the performance of a surface reconstruction algorithm that incorporates discontinuity detection in depth maps.

Acknowledgements

This paper was improved by comments from Michael Brady, Eric Grimson, and Shimon Ullman.