The Interpretation of Three-Dimensional Structure from Image Curves

Introduction

An image can loosely be thought of as a two-dimensional projection of the light reflected from three-dimensional physical objects. Since most physical objects in our world have sharp physical boundaries (as a condition for maintaining their physi­ cal integrity), it is common for the visible edges of objects to appear as sharp intensity discontinuities in an image. Because these discontinuities are sharp, it is possible to locate the posi­ tion aud orient.atiou of thcsr curves accurately in the image. For this and other reasons, we believe that intensity discontinuities (also known as image curves or lines) arc a particularly valu­ able indicator in an image of an object's shape and geometric structure. Current work in neurophysiology 141 indicates that the mammalian visual system also places considerable emphasis on the detection of intensity discontinuities. This paper is concerned with the use of these two-dimensional curves to derive the three­ dimensional geometric structure of the objects in an image.

Previous work on the interpretation of image curvea, such as that by lluffman IS] , Clowes 13], Waltz IS], and Kanade 16], has usually concentrated on the constraints imposed on boundary junctionH by certain classes of geometric objects. We believe that there arc more general constraints on the interpretation of image curves, and that the usc of thesl' constraints is of great importance for the interpretation of real data and general classes or images. Most previous attempts at boundary interpretation have used connectivity as the main source of information, whereas we ha-.·e placed .·at least as much emphasis on location, shape, size and orientation. Unlike most previous work, our implementation or these constraints is designed so that no single constraint ia taken to be absolute, and the system can therefore tolerate some errors and incompleteness in its initial data.

The constraints we use are based on coincidence (genericity) assumptions, which require no prior knowledge about the specific objects in the image. Many types of alignments in an image are unlikely to arise by coincidence, given that we can reasonably a&­ sume a general camera position and general position or the sources of illumination. For example, when three or more curves con­ verge to the same vertex in the image, it is either a coincidence in which the camera is restrictively placed to produce the alignment, or the three curves meet at a common vertex in three-apace. It is reasonable to base our interpretation on the non-coincidental case, until there is other evidence that a coincidence has in fact occured.

By applying constraints such as these, we can categorise image curves into three distinct classes: those caused by discon­ tinuities in the geometry of an object (edges), in the reflectance of an object (markings), and in the illumination (shadows). This categorization in turn leads to other constramts on the geometry and surface structure of the objects, their occlusion by other sur­ faces, and to a layered ordering of the surfaces in terms of their distance from the camera. Where geometric edges cast shadows, it is usually possible to match the edge to the shadow and make precise measurements of the relative separation or surfaces.

The constraints described in this paper are meant to inter­ face with both higher and lower levels of visual interpretation. This work is being done in the context of the AcRONYM vi­ sion system 12], and is expected to interface closely with the higher levels of AcnoNYM, which apply constraints derived from generic object models. The strength of the coincidence assump­ tions described here depend strongly on the accuracy or the low­ level curve descriptions, and in turn, many of the constraints can lead to better descriptions or the shape and intersections or the curves. Although the only examples shown in this paper are baaed on hand-derived curve data, work is currently under way to inter­ face these constraints with new curve detection techniques being developed as part of ACRONYM 11, 7].

Constraints on the interpretation or image curves

This section describes a series of general constraint& on the three-space interpretation of image lines. In each case we attempt to describe the specific coincidences which would lead to alternate interpretations. Many of these constraints are are also described in 11].

In a certain trivialliense, any of the image features described in the following constraints could be the result entirely or reflectance discontinuities rather than geometric or illumination disrontinuiti·~s. sinr.l' the image could be a picture of a picture. llow<·vrr, wr prcfrr intrrprrtations which arc ronsistrnt with solid K··o11wtry, and and assume coincidentally similar surface markings only in the fac!' of further evidence.

1. Alignmtnt ofimagt curvts. When two straight lines are aligned in an image (rven though they may be separated by a gap of a considerable distance), they must also be aligned in space, or else the lines must be parallel and the oi>server must be coincidentally in the plane of the two lines. This constraint allows us, for example, to hypothesize continuity of line segments on both sides of an occluding object. This constraint can be extended to deal with the alignment of r.ircular arcs, smooth splines, symmetries, and any shap"s which arr predictrd from knowledge of the imaged objl'd. It can also be usrd to bridge gaps in curves due to errors in the curve drtection process or insufficient contrast across some part. of a boundary. By combining a model of the errors in thr curve dPtrction process with the separation and support for l111· aligned curves, it is possible to quantify the strength of the constraint in each individual case. This is an area of current rrsrarch while we are integrating these constraints with the curve drtertion and description proceas.
2. Tangent diacontinuitiea in curvta. Tangent breaks in an image curvr (also known as tangent discontinuities or corners) are im­ portant for the same reason that intensity discontinuities are im­ portant in an image: they are features which can be sharply localized, and can therefore lead to more restrictive constraints than more diffuse features. Two-dimensional breaks in an image curve are closely related to breaks in three-dimensional apace curves: in fact, a smooth space curve will never have a break in its image. Likewise, a break in a space curve will result in a break in its image, unless there is a coincidence in which the observer is coplanar with the two tangents. The situation is the same for a cast shadow: there will be a break in the shadow cast by a geomrtric edge which contains a break, unless the source of illumination is coincidentally coplanar with the two tangents of the break.
3. Straight linea. An image line which is straight must be the image of a straight space curve, unless the curve is planar and thr observer is coincidentally aligned with the plane of curvature. Likewise, a straight shadow curve in the image must have been cast by a straight geometric boundary onto a planar aurface, unless the source of illumination is coincidentally in the plane of curvature of the geometric boundary or the observer is in the plane of curvature of the shadow curve.
4. Termination at a continuous curve. When an image curve terminates at a continuous curve (a T junction), the terminating curve cannot be closer to the observer than the continuoua curve; otherwise, it would be a coincidence that the termination hap­ pened to occur on the other line. The T junction could be the result of three different occurrences: occlusion of the terminalr ing edge by a geometric boundary, the termination of a surface marking at the visible edr;e of a geometric object, or a specific set of surface markings. Therefore, if we know that the terminalr ing curve is a geometric boundary, then we can infer that the continuous curve is also a geometric boundary and we know ita direction of occlusion. If we know that the continuous curve is a geometric boundary occluding on the aide of the terminating curve, then we can infer that the terminating curve must be a Aurrar.., marking. If we know that the terminatinr; curve is a shadow, then we can infer that the continuous curve is a non­ rourave geometric boundary (if it was concave we would see a continuation or the shadow from the aarne vertex).
5. Crossing of continuous curv~s. Wlwn two rontinuous curVI>8 cross <lll<' anotlll·r (an X junrl.ion), this is an indirator of either an illumination discontinuity, transparrnry, or an IIIJIJSIIal combina­ tion of surfarc markings, sinr.l' the r.urvc rloscst. to· thr observer docs not ocrludc either side of the othrr (w<' arc ass11ming that "wires" will IH' disting11ished on th<' basis of other local evidence, or else they can be handled as a separate case). If one of the curves is an illumination discontinuity (shadow boundary) this implies that the other curve lies on the samr surface and is not a geometric boundary, since otherwise a break would occur (as will be discussed further below).
6. Contrast across sh11dow edges. Thr contrast across a shadow edgr is equal lo thr ratio of direct to indirrd light, which rcmainA fairly constant across an ima~~:·· for a distant light sourrc. llowrvcr, the situation is complir.at.rrl by the presence of rcHcctions from nrarhy objects, which can considerably increase the amount of indirect illumination. A stronger constraint is that the contrast ratio alonr; the length of a shadow will change only smoothly and independently from th·· surracr on which it falls, so that as the shadow curvr crosses different reflectance boundaries there will be the same contrast ratio on both sides of the bound­ ary. This is a valuable constraint ror identifying shadow linea. In the case of the X junction mentionrd above, the illumination discontinuity will have the same contrast ratio on both sides of the junction, and can therefore be distinguished from the other curve at the X junction, barring coincidence. In color imagery, the ratios of illumination at each wavelength across a shadow boundary should be fairly constant and vary only smoothly along the length of the shadow, and could therefore provide an even stronger constraint (eg. the dark side of a shadow boundary will be bluer than the sunlit side on a clear day).
7. Sh11dow breaks caused by geometric brraka. As mentioned in (2) , barring coincidence, hreaks (tang<'nt discontinuities) in geometric edges arc observable as breaks in irnav;c lines, and geometric edges with breaks cast shadows with breaks. Therefore, given a known direction or illumination, the geometric break caus­ ing any particular shadow break is constrained to lie in a precise direction. This constraint is so strong that the mere existence of a break in thr given direction is support for the hypothesis of a shadow. If the dirrction of illumination is unknown, then sets of matching breaks between hypothesized shadows and other image lines, which converge to a single point (sec next paragraph), provide evidence for the hypothesis of the direction of illumina­ tion.

In perspective imagery there is an illumination convergence point in the image through which the images of all illumination rays rrom a point source pass (this is true even for nearby point sources) . The location of this point can be determined froin any set of two or more matches betwt~en shadow and geometric breaks. If the point source i8 in front of the camera lens plane, then the convergence point is of course the location of the image of the point sourrc. If the light source is behind the camera lena plane, then the illumination convergence point is located at the point of projection of the light source onto the film plane through the projective center of the camera, and the illumination streams towards this point rather than away from it. If the point source is exactly in the lens plane of the camera, then the perspective effect compensates for divergence from the light source to make the illumination con1·crgcnce point infinitely far off, ~o all imagea of illumination rays are exactly paralld (these insig!Jts am due to Sid Liebea).

It ahould be noted that breaks in shadow curves can also be r.aused by the intersection of shadows cast by different objects, so it cannot be assumed that there is a geometric break correspond­ ing to every shadow break. The constraints given here could be extended to cover discontinuities in curvature and other shape properties as well as discontinuities in tangents, although these arc more dillicult to implement computationally.

1. Casting of shadow curves by geomelri~ edges. Given one or mon· rnat.rhcs between shadow breaks and geometric breaks it is easy to dctPrminc which geometric edges arc casting which shadow edges. An important constraint is that each point on the shadow edge must correspond to some point on the geometric edge in the direction toward or away from the illumination vanishing point, although all parts of the geometric edge may not be observ­ able (say, if it is occluded by another object) . Once a match has been hypothesized between a shadow edge and a geometric edge, many important inferenc«"s follow: the casting curve is known to be a geometric edge or limb with the direction of occlusion depending on the direction of contrast across the shadow edge. If the geometric edge is straight then any curvature in the shadow curve is due to curvature in the surface on which it is cast. Likewise, if the shadow surface is known to be planar, the cur­ vature of the shadow can be used to calculate the curvature of the casting edge. The image separation or the casting curve from the shadow can be used to calculate their relative range from the camera. Shadows essentially provide a second projection of the object geometry, in addition to the original image, and can therefore be used in much the same way as stereo information.
2. Jun~tions of two or more discontinuous curves. When two or more curves terminate at the same junction, it would be a coincidence if the observer were aligned so that separated vertices in space landed at the same point in the image. Therefore, for 1., Y, 1<, or higher-order junctions, it is reasonable to hypothesize that coinddencc in the image implies coincidence in space. In other words, knowing constraints on the 3-space location of the cudpoint of any of the terminating curves gives us the same constraints on the 3-spacc locations of the other endpoints at the vcrt(!X. Whl'n a shadow curve terminates at a Y or higher-order junction, we can assume that one of the other terminating curves is a geometric edge casting this shadow onto a surface passing through the junction (otherwise it would be a coincidence that the shadow happened to pass through the junction).
3. Propagation of direction of occlusion. When the direction of occlusion is known for a geometric boundary (ie., we know which of the surfaces on either side the edge belongs to), then any unambiguous continuations of the geometric boundary will have the same direction of occlusion.
4. Surface continuity. We assume smoothness and continuity of surfaces when there is no intensity discontinuity in the image. If an intensity discontinuity on a surface is due to a geometric discontinuity of the surface, then we would expect to see a dis­ continuity in the geometric boundary of the surface where it in­ tersected this intensity discontinuity (unless the observer is in the pla·ne of the two tangents at the boundary). Therefore, a curve which intersects a smooth boundary of the surface on which it lies can be assumed to be a surface marking rather than a tangent break in th.e surface.

Knowing the direction of occlusion (from 4,8,10, etc.) al­ lows us to form surface descriptions by looking at the regions bounded by geometric boundaries. In many cases it is possible to form surface descriptions by merely following the continuations of geometric boundaries around the extent of the surface, until they are possibly occluded by another surface. Another technique is to work away from the occluding side of a geometric boundary, ig­ noring illumination and reflectance discontinuities, until either an opposing geometric boundary is found or an occluding geometric object is found. Note tha~ this is different than the usual region segmentation of images, since we arc doing it in the geometric domain. These can be diflicult constraints to implement com­ putationally, since they deal with properties of entire surfaces rather than just a curve. Our current implementation handles only some of the more common cases of surface description.

1. Predietion of shadow locations. If we have formed hypothese· of the geometry of an object, the surrounding surfaces, and the direction of illumination, then we can predict the locations of illumination discontinuities in the image, and thereby produce new hypotheses for image lines at these locations, as well u confirm or contradict our original hypotheses. Prediction of thia sort can also be used to check consistency of surface occlusion.
2. Parallelism in object apace. In perspective imagery, straight lines which are parallel in object space all converge towards a common vanishing point in the image. Since scenes often contain many lines parallel to a preferred direction (such as vertical with respect to the ground) , once a vanishing point has been identified for some lines, other lines which are aligned with it can be a. sumed to be parallel in object space, barring coincidence. Curves which are parallel and close together in object space (relative to the image size), are almost parallel in the image for most camera orientations (this can be precisely quantified).

Since we are attempting to derive three-dimensional structure from image clues, the constraints above all deal with image fea­ tures which are qua3i-invariant (ie., generically stable, with at most a planar locus of instability) with r<'spect to viewpoint. For example, a curve break in three-space produces an image curve with a break over a wide range of viewing conditions, even though the angle of the break is not invariant. The higher levels of ACRO­ NYM produce predictions of quasi-invariants from specific object models, and these should interface well with the more general quasi-invariants described above.

The list of constraints given above can be extended in many directions, while still maintaining the same level of generality. We are particularly interested in constraints for inferring the crosa sections and volume descriptions of geometric objects in an image.

Reasoning on the basis of coincidence auumptiona

The use of incomplete constraints forces us to use a non­ monotonic reasoning system, in which further evidence can dis­ prove a previously held hypothesis. We have chosen a method of deduction which forms an explicit symbolic representation of each hypothesis, and maintains a record of its support and im­ plications so that it can be reevaluated and undone if new con­ textual evidence indicates that the original hypothesis waa false. Each hypothesis has pointers to all the hypotheses and types of evidence which have given support to it, as well as pointers to the hypotheses which it supports.

When conflicting interpretations are suggested for some part of the image, the evidence for each interpretation is evaluated to see if one interpretation is strong enough to exclude the other. If there is insufficient information to make this decision, then both hypotheses are pursued until there is. When a previously held hypothesis is thought to be false, its implications are undone and any further results propagated. This non-commital style of deduction works well because the constraints are strong and the search space is shallow. The major difficulty is that this requirea that special code be written to evaluate and resolve each type or conflict that could occur. but we are looking at other possible resolution schemes. The explicit maintenance of constraints ia much better than the use of backtracking for testing hypotheaea, since it is not limited to the last-in-first-out order or testing typically enforced by a backtracking stack, and any results apply to the entire problem space.

The coincidence assumptions could sometimes be used to measure the likelihood that a given coincidence will occur, and therefore be used to compute a probabilistic degree of confidence in a hypothesis. However, these probabilistic measures can be extremely context-dependent and may vary widely rrom image to image in ways that can not be known before the image ia interpreted (ie., the probabilities cannot reasonably be assumed to be independent). The combination of probability valuea may be or importance in some cases for speeding up the analysis, by telling ua what to examine first, but we have made no attempt to use them in our current system. When some consistent overall interpretation has been found for an image, there is usually much redundant information available in support of the interpretation and there ia no need to choose between alternatives on the baaia or explicit probabilities.

An Implementation

We have written a preliminary veraion or a computer program which implements the reasoning system and many or the con­ straints described above. This program has been tested on aimu­ lated image curve data derived by hand from a real image, with the encouraging results described below. We are in the proceaa or implementing more constraints, and hope to soon test the pro­ gram on data derived automatically from images by new curve detection techniques being developed here at Stanford. The pro­ gram baa been implemented in MACLISP on a DEC KL-10, uaing the record package and AcRONYM environment created by Rod Brooks [2]. All of the constraints we currently use are computa­ tionally intxpenaive, and the hypothesis formation for the given example took leas than 2 seconds of computer time.

The initial curve data ia translated into a set or "curve hypotheses" in order to initialize the hypothesis generation process. Each curve is represented as a series of points with the tangent of the curve given at each point, and cubic splines are as­ sumed as the method of interpolating for intermediate points. All curves are indexed in a grid array under all grid squares through which they pass, making it economical to search image neighbor­ hoods for curve features. During input, each curve termination is linked to other curves which terminate or pass through the same spot, as well as to curves which are aligned with ita continuation.

A weakness of the current system is ita control structure. Currently, most of the hypothesis generation proceeds in a rairly fixed order, with the evidence which is expected to be the moat reliable being examined first. However, we are in the proceaa of creating a more flexible control structure using a generalised agenda for ordering conatraint propagation.

In spite or the incomplete state of the current system, it ia able to carry out detailed interpretations from simulated curve data as shown in Figures 1 through 8. Figure 1 shows the original picture taken over San Francisco airport rrom which the curve data in Figure 2 was derived by hand. This data also specifies the approximate contrast acrou edges. In deriving this curve data we referred to data derived automatically by curve detection programs, and we believe data of at least this quality will soon be available. We have also input the location or the sun, although .we hope to soon be able to derive the illumination direction(·) automatically from the image. Figure 3 shows the hypothese· regarding curve terminations at a continuous curve (constraint 4).

Figure 4 shows a dotted line at the match between each hypothesized shadow discontinuity and its corresponding edge discontinuity in the sun direction. This makes a small amount of use of the input data regarding the contrast across curves (constraint 6}, but the major support for a shadow hypotheaia is the existence or one or these shadow matches (constraint 7). We expect to be able to use tighter tolerances when using automatically generated data than were used with this simulated data, with correspondingly better results. Figure 6 shows curves which have been hypothesized to be shadows as dotted lines, and also the hypothesized connections between shadow linea and the geometric edges which cast them (constraint 8). These hypothese& were formed from the evidence of Figure 4 in combination with other projective constraints mentioned in the previous section and hypotheses regarding which edges constituted geometric bound­ aries. Figure 5 shows hypotheses which form surface boundaries from other hypothese· regarding geometric edges, the direction of occlusion, and unambiguous boundary continuation&.

From the reaulta of this interpretive proceaa, it is possible to conatruct three-dimensional models of the acene. The shadow to curve matches provide information on the relative distance of each geometric edge and shadow surface from the camera. Even if the aun position is not known, all measurements are correct relative to aome constant factor and can be made absolute by knowing the correct measurement for any one part or the image. Figures 7 and 8 ahow different views of 1uch a model generated automatically from the hypotheses described above. Some of the minor errora in thia model are actually artifacts of the display aystem rather than being pre.ent in the actual hypotheaea. The position of the camera with reapect to the ground waa given to the modeling aystem (so that vertical· would appear vertical), but thia could be deduced from the image if the orientation of any image object with respect to the ground waa known. With our digitized data it waa impossible to aee into ·had.ow· on the ground becau1e of digiti1ing limitation·, even though· this information waa available in the original negative. We believe that interpretation would have been eaaier with more complete data. This example by no means exhausts the information inherent in the given curve data, even without considering the u.e of specific knowledge regarding ,airplanes and airports.

Coneluslon·

The constraints on curve interpretations do not need to rely on restrictive assumptions about the claas of objects in the image. One objective of this reaearch has been to show that image in­ tenaity diacontinuities carry far more information than has often been recognised in the past. The ability to precisely locate rea. ture1 ia of great importance for providing strong constraint. on interpretation. Not only is it valuable to localise intensity discon­ tinuities as accurately as possible, but it is important to locali1e curve terminations, inter.ections, and tangent or curvature dill­ continuities accurately. Much work remains to be done on error analysis with each type of constraint in order to make maximum use or the available information.

More weakly localisable information, such as shading, inten­ sity, and color, while being very important, is usually dependent on other assumptions regarding aurface continuity. We believe that it is valuable to first examine the intensity discontinuities and carry out interpretation similar to that described here as a step towards using these other aources of information.

Shadows are not troubleaome features to be removed frorn an image, but are in fact one of the most reliable aources of low-level information. While aome or our constraint. on shadows depend on properties of the sun and assume a known location of the light aource, we believe that human perception in general makes use or the more qualitative aspects of our constraint. on the interpreta­ tion of illumination. In particular, the behavior of illumination boundaries u they cro11 surface markings and geometric bound­ aries and terminate at geometric vertices provides a great deal or information even under unknown condition· of illumination.

The identification of illumination boundaries can be carried out at a low level by noting the width of boundary transitions, con­ straints on contrast changes along a shadow edge, arid the crosll­ ing of continuous curves where a shadow falls across a reHectance discontinuity.

The reasoning system used for this interpretation task can be summarized as follows: we rea.on forward on the auumption that no coincidences have occurred, but always maintain enough information so that hypotheus can be reevaluated and changes propagated in the face of new contextual evidence. This gives us the ability to use constraints which will sometimes be false, and therefore allows us to use many sources of information which would be unacceptable in a strictly deductive inference or con­ straint system. This method relies on the large amount of redun­ dant information usually available for vision tasks. The further development of tools for reasoning with suggestive evidence is an important goal for many areas of artificial intelligence research.

Acknowledgement.

Our task would have been much more difficult without the extensive systems and graphics features created by Rod Brooks during his work on AcRONYM. Sid Liebes has helped us work out the geometry of perspective imagery and shadow formation. Peter Blicher, Dave Marimont, and Barry Soroka made helpful comments on a first draft of this paper.

This research has been supported by the National Science Foundation under grant DAR78-15914, and by the Defense Advanced Research Projects Agency under contract MDA90380-C-0102. The first author also receives support from a National Science and Engineering Research Council of Canada Postgraduate Scholarship.