Interpreting Pictures of Polyhedral Scenes

Introduction

One way to capture the meaning of pictures is to investigate the relationship between two domains : the picture and what ­ ever it is that is depicted - the scene 1 · This paper c l osely examines that relationship for pictures consisting of straight line seg­ ments and scenes made up of opaque polyhedra . A program , POLY, in the same tradition as Guzman ' s SEE 2 and Clowes ' OBSCENE 1 is presented . POLY exploits the relationship between the domains and also coherence rules that entities in the scene domain must satis~. Following a description of POLY some feasible extensions to this scheme are described . Finally , the relevance of this program to other scene analysis programs is discussed .

The work reported here stemmed from con­ sideration of several unsatisfactory aspects of OBSCENE . The 'predicate table' embodied in that program appears to be a rigid and opaque theory of three- surface corners and the picture- taking process . Secondly , OBSC~ has a very weak grip on the consistency of the viewing direction . Finally , it inter­ prets many pictures as polyhedra which ·cannot, in fact , exist . The conceptual framework for POLY was inspired by Huffman 1 s 'dual- graph 3 ' , which was presented as a device for checking an interpretation provided by the Huffman­

Clowes labelling process .

2 .

Scene Coherence

Let us first establish a representation for the geometry of polyhedra and the picture taking process .

Dual Space

In conventional Cartesian space we des­ cribe a point by giving its coordinates (x , y,z) and a plane by a constraint . upon the coordinates of a point : ax x + ay y +a 2 z +1=0 The representation is as it were point oriented . Since planes are of more interest to us than points in the context of planar­ faced polyhedra , it is desirable to use a

by

Alan K. Mackworth

Laboratory of Experimental Psychology , University of Sussex , Brighton, Sussex , England .

r epresentation that is plane oriented . Such a representation is dual space 4 in which a plane is represented as a point - specifically by the coefficients a , a , a of the variables in the equationyof the · real ' plane . It follows that the dual of a point (x,y,z) is a plane such that (a , a , a ) is on the plane i f xa + ya + zax + ~ = 0. X y Z

If ·a line in real space is construed as the intersection of two real planes then its dual is the line passing through the points in dual space which represent those real planes .

Viewpoint

A two- dimensional image of a three­ dimensional body is a projection whose form can be specified in terms of a viewing posit ­ ion and a picture plane .

Fig.l illustrates such a situation whe re the picture plane is the x- y plane and the viewpoint V is on the z axis . I f we consider a particular line such as P1 P 2 then P 1 P 2 , B 1 B 2 (the corresponding edge) andV all lie in a plane . This pl ane we call the Qlane of interpretation(!) of P1 P 2 since given P 1 P 2 in a picture we have only to hypothesise the position of V relative to that picture to achieve a powerful constraint upon the pos­ sible interpretations of P 1 P 2 as an e dge , namely that the edge lies in the plane I beyond P1 P2 · Such an hypothesis about V has global implications for it determines the planes of interpretation for all other picture lines simultaneously because all planes of interpretation must pass through V. This fact is expressed elegantly in the dual space as the assertion that the duals of al l the inter­ pretation planes must l ie on the dual of V name l y on a plane in the dual space D.

I f V is at infinity relative to the picture (an ideal point) the projection is orthographic otherwise it is perspectiv~ .

Bodies

The interpretation of some set of picture lines as edges bounding a plane surface of a body is expressed in dual space as the requi~ ment that the duals of these edges all pass through the dual point representing that surface . Hidden edges of a partially visible surface would of cour se also be subjected to this requirement as would the dual of any line presumed to be u pon the surface .

The inte rpretation of a p icture junction as the corner of a polyhedron can also be use­ fully characterised in dual space . A point in r eal space can be cons t rued as the intersectim

\

of a set of planes so that we can identify the planes with the surfaces of the corner and the point with the corner itself . Each edge of the corne r is then the line of inter­ section of a pair of planes, and has as its dual a line which passes through the dual (point) of each of the pair of planes . This set of dual lines forms a polygon lying in a plane in D, that plane which is the dual of the point in real space that we identified wi th the corner . Thus the dual of an n ­ surface corner of a polyhedron is a plane n - gon .

Assumptions that the objects in the por­ trayed three- dimensional situations are poly­ hedra interface with a model of viewpoint in a particularly simple way . Both the picture line and the edge it depicts lie in the plane of interpretation, I , for that line . Thus the dual of the edge (a line in D) must pass thr­ ough the dual of I . This can be combined with the requirement that the dual of an edge pass through the duals of the surfaces it belongs to , to obtain the requirement that the duals of I and the two surfaces inter­ secting in I lie on the dual of the edge which is that intersection . Thus in Fig .l the duals of the surfaces B 1 B 2 B 3 B 4 , B 1 B 2 B 5 B 6 and the plane of interpretation of P 1 P 2 all lie on the dual line of B1 B2 ·

The Gradient Space .

A particularly interesting 2- D subspace of the dual space D is the gradient space G. A point (ax,a , az) in D corresponds to the point Y

in G. Geometrically , this corresponds to projecting (a , a , a ) into the a = 1 plane with centre oJ p~oj~ction at 0 a~d using (¢,¢ , 1) as the origin, OG ' of G. In Fig . 2 , I in D is projected into I in G. G

Several interesting remarks can be made about G. If the equation of the plane is re­ written as

called the gradient of the plane . In Fig. l, - z is the dist~nce from the point (x , y , z) on a surface of the object such as B 1 B 2 B 3 B 4 to the picture plane , z = 0 . The gradient represents the vector rate of change of this distance with respect to movement in the picture plane , thtt is,

The length of the vector from 0~ to a point , W, in G is the tangent of the angle between the picture plane and the plane corresponding to W; the direction of that vector is the direction of the dip of the plane corres­ ponding to W relative to the picture plane . Since the dual of the picture plane is the ideal point on the az -axis , OG the zero grad ient, corresponds to it . The projection into the gradient space of the dual line representing an edge may be called the gradi­ ent line of that edge . A perpendicular dropped from 0~ to that line is the gradient of that edge in that its direction and mag­ nitude are the direction and tangent of the angle of dip of that edge r elative to the picture plane . A family of mutually parallel planes represented by the coordinates (kax,ka , ka ) in D will have coincident represencatigns(~ a . ~ , _]£_ ) in G. Planes whlch are

steeply inclined to the picture plane will be relatively remote from 0~ in G. Most of the relationships that were shown to hold in D must necessarily hold in G. In particular , the gradients of the interpretat ion plane and the two object surfaces that intersect in an edge must be on the gradient line of that edge.

The orientation of a picture line deter­ mines the direction of the gradient of its interpretation plane 1n G. Thus a picture line which is parallel to the y - axis , say, will have an interpretation plane whose gradient I G lies on the a axis . If we align the x - y (plcture ) axes w!th the a - a axes of G the directionof I~ relative tS 0~ will be perpendicular to the picture line .

The above remarks are all true regardless of the v iewing position, V, and so are true for both orthographic and perspective pictures . We shall now concern ourselves with the gradient space for orthographic p ictures . The duals of all the interpretation planes (which ll)USt lie on the dual of V) will then be on the a = 0 plane of D. Projecting them into G will 2 therefore put all their gradients at infinity (they become ideal points in the gradient space) . Another way of looking at it is to realize that as V goes further from the picture plane the angles between the picture and the interpretation planes all approach 90° and so the lengths of the gradients approach tan 90° ( -->00) .

The distance of IG from OG increases with the (presumed) distance in real space of the viewing point V from the picture plane . The projection onto G of the dual of the edge depicted by the picture line , will be a line passing through IG . For any picture line there is an infinlte family of such lines in G being the projection onto G of duals of the possible edges depicted by the line . As V tends to infinity, the picture tends to an orthographic projection of the scene and IG tends to an ideal point . The family of edge gradient lines in G simultaneously tends toward a set of parallel lines whose orienta­ tion is that of the direction of IG ' that is, perpendicular to the picture line .

Consider an orthographi c picture of a scene with a visible edge joining t wo visible surfaces, A and B . (We call such an edge , a 'connect' edge) . The gradient space configu­ ration corresponding to that consists of the two gradients (GA and GB) joined by a line which is the proJection of the dual of the edge . That line is perpendicular to the picture line if the gradient space is super­ imposed on the picture space as described above . Moreover , it can easily be shown that if the gradients are ordered on the dual line in the same direction as the corresponding surfaces appear at the edgethen that edge is convex but if they are ordered in the reverse direction then it is concave . (Intuitively , imagine a convex edge then rotate one of the surfaces until the edge becomes concave . When the edge is flat , the gradients must coincide) . This crucial fact allows the exploitation of the gradient space for convex/ concave interpretations .

As a simple example of the u se of this consider a FORK junction (Fig . 3) where it is known that all the edges are connect . The configuration of the gradients of surfaces, A, B and C, (�~, GB and Gc) can only take on one of the two rorms of Fig.4if they are to satisfy the requirement that the mutual vector difference be perpendicular to the line depicting the edge that connects the two surfaces . These configurations can , of course , be translated and expanded in the gradient space and still satisfy the requirement . Com­ paring the relative positions of the gradients in Fig.4(a) with the ordering of the regions in the picture shows that all the edges must be convex for that interpretation while for the interpretation given by Fig.4(b) all the edges must be concave . That switch of inter­ pretations which can be achieved by mapping eve ry gradient G into its negation, - G, is known in the literature of psychology as the Necker reversal .

3 .

The task for POLY can be specified as follows : using these constraints on the coherent interpretation of polyhedra subjected to this picture- taking process what informa­ tion can be derived from the picture? In particular , the p r ogram must provide easily accessible answers to questions , such as ,

Which edges are connect edges?

Which of those are convex, which

concave?

Which edges are occluding?

If an edge is occluding which surface is in front?

How much of the hidden structure of the scene can be recovered?

What is the orientation of each surface and each edge?

and so on .

A progra~ POLY, will now be described which recovers these attributes and relationships of the scene . POLY is an existence proof that such questions can be answered . It does not purport to be a stand alone scene analysis program but it can be thought of as a useful embodiment of most of the knowledge specific to these picture and scene domains and their·· interrelationship that a scene- based problem solver would need to have available . The overall structure of POLY is shown in Fig . 5 . The program is written in ALGOL 60 extended to allow for the representation and manipulation of data objects, attributes and binary relationships . The input is obtained by drawing a picture on the graphical displ~ t he input phase passes to the parsing phase the end po i nts of the lines . The parsing phase recovers the picture structure by examining the lines for join relationships , and establishing the junctions and closures and the regions made up of closures . The picture structure is that given in Fig . 6(a) . Then the scene correspondents of this data structure are created following the relation of r epresentat ion 1 as shown in Fig . 6(b) .

The CONNECT part of the program uses the rules of coherence sketched earlier to establish which edges are connect and which are not . This part of the program searches over a binary tree with each l evel represent­ ing a different edge in the scene, the left branches being connect(edge) = true and the right branches connect(edge) = false . This tree is not searched in either of the conven­ tional depth- first or breadth- first ways . To achieve the most connected interpretation first , the top l evel goal requires all edges to be connected and then , when that fails , all edges but one and so on. The tree search is effected by the usual backtracking method with state saving which in this case is achieved by a recursive procedure . The edges are not searched in random order; starting from the background region each region i s interpreted in turn : the next region chosen is that uninterpr eted region with the most lines adjacent to the interpreted r egions . In this context, to interpret a region means to fix the position of the corresponding surface in gradient space . Because the region selected by that criterion will correspond to the most constrained surface , this strategy results in the most efficient search. So , in fact, the order of the search is given in advance by the parser but there is no reason why the program could not modify the order of search dynamically if it were embedded in a larger system that could supply advice or hypotheses about the orientation of particular surfaces or the status of various edges .

A simple example wi ll make the workings of CONNECT clearer . Consider the picture in Fig . ? . CONNECT fails to find any interpreta­ tion with five or with four connect edges for reasons that will become obvious . So with the goal of establishing three connect edges , CONNECT starts with the background A, and for convenience sets GA at the origin in gradient space . It then examines the lines on the inner closure of A (1 , 2 , 4 and 5) and finds that none of the r egions on the other sides of those lines have been i nterpreted so it can say nothing yet about these lines . It then chooses the uninterpreted region that has the most adjacencies to the interpreted regions as the next region to interpret . The ordering of the edges as a tree is determined by this strategy of addressing the picture . Both B and C have two adjacencies so the choice is arbitrary , say , B . Now it examines lines on the outer closure of B in sequence trying to establish connect edges . Say it looks at l first . It establishes it as a connect edge which means that G must lie on a line perpendicular to l throu~h GA =(¢,¢).

In general the position of a gradient is defined by the i ntersection of two or more li­ nes in the gradient space arising from edges assigned connect stat~s ; however , for the first two gradients (GA and GB, here) there is no loss of generality if we do not use that requirement to locate them s i nce the origin and scale of the gradient space can be subse­ quently altered . So we put GB at unit distance from G on that line . The next picture line to~e considered is 2, which CONNECT also tries to establish as a connect edge but this would require G to lie on a line perpendicular to 2 throu~h G which is incompatible with the current int!rpretation of GB . Thus the interpretation in which both 1 ana 2 are connect edges is said to be incoherent . This makes it clear why CONNEC'r failed in its original goal of establishing all the edges as connect edges . 2 is established as an occluding edge and CONNECT looks next at 3 . Since the region on the other side , C, is not yet interpreted, it says nothing about 3. The r emaining region C is then interpreted . 3 is estab lished as a connect edge requiring G to lie on a line perpendicular to 3 passihg through GB . The actual position of G is established by defining its relatiohship to GA by making 4 or 5 (but not both) connect edges . The inte~ pretation in which 1, 3 and 5 are connect and 2 and 4 are occluding edges is rejected by the single rule that three non-collinear points in space (the corners a, b and c) cannot simultaneously lie on two planes (A ffiU B). So one legal connect interpretation is that 1 , 3 and 4 are connect edges while 2 and 5 are not . Continued search of the tree will only yield one moreinterpretation with 3 connect edges, viz . 2 , 3 and 5 connect, 1 and 4occluding . For 1, 3 and 4 connect the final gradient space configuration will be as shown in Fig . S, in which the gradient line of connect edge 1 is labelled as 1' etc .

Then VEXCAVE takes over and decides which of the connect edges are convex and which concave . VEXCAVE starts by partit­ ioning the gradient space graph into 2- con­ nected subgraphsg using the g radient lines of connect edges as arcs . For each subgraph VEXCAVE then determines its t wo possible interpretations using the ordering rule for gradients . In the example , VEXCAVE will decide in the interpretation for which 1, 3 and 4 are connect edges that the whol e graph is 2~connected and that either 1 and 4 are concave edges whi l e 3 is convex or 1 and 4 are convex whi l e 3 is concave. Note that, for the latter interpretation, junction b is assigned an ·accidental ' status.

Finally, OCCLUDE looks at the non-conn­ ect edges and uses two inference rules to achieve a compl ete interpretation . The first rule expresses the fact that if two surfaces intersect in a connect edgethat is known to be, say , convex then at any position in the picture it will be apparent which surface is in front . Using this rule it becomes clear , for many occluding edges , which surface (of the two that it apparently bounds) the edge actually belongs to . The rule also adds a hidden surface attached to that edge . The fact that such a surface is both turned away from the viewing direction and obscured by the visible surface means that it obeys the same constraint as it would if the edge were concave and connect . This rule is used in the example to decide for the case where 1 and 4 are concave and 3 is convex that occluding edges 2 and 5 belong to surfaces B and C

respectively. The second rule for occlusion completes the polygon of gradients corres­ ponding to the visible and hidden surfaces meeting at each corner . It does this by allowing for the hidden surfaces created by the first rule and introducing the minimum number of extra hidden surfaces required . The minimum number is achieved by allowing two occluding edges to share the same hidden surface wherever possible . In the example the second rule confirms that the polygon of gradients is complete for corner c since the surfaces at that corner, A, B and C are all visible and there are no occluding edges . For corner d it completes the polygon by introducing a hidden edge between the hidden surface at edge 5 and the background . Similarly for corner a and the hidden surface at edge 2 . Then at corner b it decides that those two hidden surfaces could be the same surface , D, and still obey the con·straints . So the final gradient space configuration is F ig.9 which looks like a picture of a wire­ frame tetrahedron because the tetrahedron is ·only self-dual polyhedron4 .

The interpretation pursued in the exampl e above is one of the first produced by POLY but the program will continue to generate less connected interpretations . For example, the tetrahedron separate from the background surface has only one connect edge, 3' , but its gradient space configuration has the same structure as Fig. 9 with the exception that G in that figure is replaced by the gradient o~ a second hidden surface, GE and GA is now an isolated point in gradient space . Interpre­ tations such as this with complete bodies separate from the background can be easily generated first by giving CONNECT the advice that all the lines on the inner closure of the frame represent non-connect edges .

When OCCLUDE has finished then the interpretation process is compl ete . Each edae in the scene data structure is related to other scene entities such as the surfaces it bounds and the corners which bound it. An edge node also contains attributes such as connect, convex, concave or occluding and its slope relative to the picture plane . Nodes for the original visible surfaces and the hidden surfaces introduced by OCCLUDE contain the gradient vectors which are relative to the gradient of some other surface, usually the background . These gradients may be uniformly scaled by a positive number before being added to the gradient of that other surface to obtain the true gradient . The scal e factor must be positive because the work done by OCCLUDE on the hidden surfaces wi ll not survive the Necker transformation that a negative scale factor would involve. This transformation was allowed for earlier, in VEXCAVE, when two versions of the configura­ tion were generated .

Two further points about the program should be made . First, POLY has no difficulty in making sense of cracks as in Fig . lO . Cracks are simply connect edges where the two adjacent surfaces have identical gradients. Finally, the processing time required to produce the first interpretation is proportional to the number of picture lines if that interpretation is completely connected but that tends towards an exponential relationship if the first interpretation is less connected .

4. Possible Extensions of POLY

There are many possible elaborations of this scheme . Since surfaces are represented by their gradients we learn only the orientation of each surface and not its position in space. It is clear , however , that one could take the results of POLY and by fixing the actual position of one surface propagate the positions of the other surfaces through the connect edges . Alternatively one could use the dual space itself as a represe ­ ntati?n and build a program that directly explolted the constraints outlined above . S~ch ~ ~rogram would not have the conceptual slmpllclty of the implemented scheme .

In theory , POLY only considers ortho­ graphic projections but this is not in practice , a significant li~itation ~n a scene analysis program . Howeve r , one could reform­ ula~e t~e program to deal with perspective proJectlon . In outline , this means that the interpretation plane is now represented as a :eal point in gradient space since it is not , ln general , pe r pendicular to the picture plane . The vector from the origin of the gradient space to that point will still be perpendicular to the picture line but the gradient line of the edge is only required to pass through that point and also contain the gradients of the two object planes . Since the gradients of the planes of interpretation of all the picture lines are determined by the geometry of the picture and the pos ition of the viewpoint relative to the picture plane_these constraints can be systematically explolted to construct a perspective interpretation of the line drawing .

If the scene is lit by one or more discrete l ight sources the boundaries of the shadows cast are depicted as straight lines . Consider a shadow plane formed by the light source, a shadow- casting edge and the corres­ ponding shadow boundary . The gradient of such a plane must lie on the gradient line of the edge (which is perpendicular to the picture line and contains the gradients of the two object surfaces meeting at the edge) . T~e sha~ow boundary will also have a gradient llne Whlch contains the gradients of the shadow- r e c eiving surface and the shadow plane . Moreover , for a source producing a parallel beam t~e gradients of all the shadow planes must ~le on a straight line in gradient space ~hat 7s p~rpendicular to the direction of lll umlnatlon in the picture . Such constraints allow the extension of the scheme to include shadow interpretation .

5.

POLY has particularly interesting relationships with f our other· vision program~ namely, Guzman's SEE 2 , Clowes · OBSCENE1 , Waltz ' s program 5 and Falk ' s I NTERPRETs .

SEE accepts input in the same form as POLY does and produces groupings of the picture regions on the basis of the putative body membership of the surfaces depicted . The program starts by classifying each junction into one of a small number of junction cate­ gories. It then uses this classification to place links between regions if certain local junction configurations exist . The resultant graph (with surfaces as nodes and links as arcs) is then examined for well connect ed subgraphs which are declared to r epresent bodies . In the language of POLY, Guzman ' s links can be thought of as good guesses at connect edges and, indeed SEE·s graph structure is a weaker version of POLY ' s gradient space rep resentation . But SEE fails to exploit fully our knowledge of three dimensional situations; for example , there is no representation in the program for the fact that if two edges between two surfaces are ncl collinear they cannot both be connect edges . SEE ' s tendency to see holes in objects as separate objects 7 is only one consequence of the fact that the program i gnores inherent ambiguities in the interpretation process that are exposed by the next program to be considered here , OBSCENE .

OBSCENE (and Huffman's labelling algorithm3 ) gives each edge in the scene one of four interpretations , namely , convex , concave and the two occluding possibilities . OBSCENE works by mapping junctions into corners using some of the junction categories described by Guzman . Each junction type (ELL , FORK , ARROW and TEE) has a small numbe r of pre- determined corner interpretations . Tre program then pursues the l egal combinat ions of these using the coherence rule that an edge must have the same interpretation at each end. OBSCENE can be seen as a theory of why SEE works , in that it makes explicit what is impl icit in SEE . POLY , in turn, is a theory of why OBSCENE works, in that it shows how to derive the junction categories of OBSCENE .

POLY can be seen as a descendant of OBSCENE in several ways . The coherence rules for OBSCENE are at the edge level whe r eas POLY requires each surface to have a unique orientation in space . This higher level of coherence means, for example , that POLY rejects as ill- formed , skewed objects , such as Fig . ll , that OBSCENE will accept .

The mapping rules for OBSCENE are at the corner level while those for POLY are at the level of edges . For OBSCENE , thi s resul ts in the rathe r unsatisfactory predicate table in which are listed all the various 3- surface corners which could be depicted by each junction type . All the entries are wo rked out in advance by the programmer whe reas drawing each junction type as input to POLY would result in interpretations that are the OBSCENE predicate table entries . OBSC~~N"E · s edge mapping is :

but POLY uses the fact that those four categories are really hiding two boolean predicates . POLY ' s mapping is :

and the combinatorial search is done on this p r edicate alone with the other predicate de termined by non- search procedures .

Waltz 5 considerably extended the Huffman- Clowes labelling procedure by sub­ dividing the four categories of edge types and adding cracks and shadow boundaries; furthermore , he i~geniously modified the search mechanism to avoid the combinatorial explosion of a straightforward breadth- first procedure . Nevertheless , most of the remarks made here about the Huffman- Clowes procedure seen in terms of POLY apply equally to Waltz's extension . Waltz also assigns to each surface an illumination status : illuminated , turned away from the light or shaded by another surface . Such hypotheses would be better justified if the surface orientations were explicitly represented as in the g radient space . Similarly his treatment of shadows does not include the global consis­ tencies outlined in Section 4 above . Finall~ Waltz suggested a scheme to check a labelled picture by using quantized versions of line , edge and surface orientations related through tabulations of possible values . POLY exploits directly a more concise and trans­ parent representation of those relationships to construct rich scene interpretations thereby dispensing with possible corner lists.

Falk ' s INTERPRET 6 is a well documented account of a complete scene analysis system that interprets line drawings and so it is instructive to see hovr POLY could r e late to that program . But first , consider Falk ' s 1 faceadj acency graph 1 · This concept , al thougj:l not used in the program, is outlined in his paper because it 'would be valuable for a scene analysis system which operated in a universe of planar faced solids more compli­ cated' (6 , p . ll2) than the nine simple objects his program recognizes . Falk suggests doing a Huffoan- Clowes analysis of the picture to determine which edges are connect and then constructing a graph with surfaces as nodes and connect edges as arcs . It is then shown that a property of this graph , 'mergeability ' , gives the number of independent points that need to be located in three dimensions in order to specify the scene completely . In particular , if the graph is l - mergeable ( 2 - connected in graph- theoretic terms) then 4 points must be located . These 4 scalars correspond to setting the orig in and scale of the gradient space and the distance of the obj ect from the picture plane . Falk ' s result applies direct]y to the gradient space configuration produced by POLY, which is not confined to isolated , degree - 3 polyhedra .

With respect to INTERPRET itself , Falk mentions seve ral times that a Huffman- Clowe s labe lling would have helped the program . Those remarks apply , a fortiori , to POLY . In addition, the surface orientations available in POLY would help in support determination and in recognition; also , the inclination of edges relative to the picture plane give the foreshortening factor necessary to calculate true edge length. Finally, consider the seven somewhat opaque heuristics that Falk uses to determine possible base edges . He is forced to use these because at that stage the program is functioning entirely in the picture domain . The analysis offe red by POLY, which const~Qcts a scene interpretation without 're cognizing ' tLe objects , provides a structure in which one could find t he lowest hidden surface and simply ask which visible edges are attached to it .

The caveat should be entered that , as they stand , both OBSC.~~NE and POLY re quire comple te line drawings while Falk interprets pictures in which lines can be missing . How­ ever , examination o:r the manner o:r :failure of POLY on a particular picture will suggest whe re lines may be missing or extraneous by showing, at the ve ry least , which subpictures can be sensibly interpr eted . Furthermore , hypotheses concerning line s to be added or removed can be confirmed by successful analysis by POLY .

6.

Although POLY is restricted to the interpretation of compl e te line drawings showing an orthographic view of a shadow- free polyhedral scene , the extensions in Section 4 and the discussion in Section 5 suggest that all of these restrictions except the over­ riding commitment to polyhedra can be over­ come . Be that as it may , the program does demonstrate just how much structural information can be inferred from the pic ture using knowledge of the picture- taking process and the gene ral nature of polyhedra but with­ out using specific polyhedral prototypes .

Dr . ·M. B. Clowes provided much welcome advice and criticism. The author a l so acknowledges facili t .ies provided by Professor N. S . Sutherland , the financial support of the National Research Council of Canada and computing r esources made available by the Science Research Council of Great Britain .

Referenq_e_~

• l . Clowe s , M. B. On seeing things . Artificial Intelligence 2 ,No 1 . (1971) , 79- 116 .
• 2 . Guzman , A . Decomposition of a visual scene into three- dimensional bodies . AFIPS Proc . Fall Joint Comp . Conf . Vol . 33 (1968) , 291- 304 .
• Huffman , D. A. Impossible objects as nonsense sentences . Machine Inte lligence 6 , Meltzer , B, and Michie D. (Eds . ) , Edinburgh University Press , Edinburgh, 1971 , pp . 295- 323 .
• 4 . Hilbert, D., and Cohn-Vossen , S . Geome try and the Imagination, Chelsea , New York , 1952 .
• 5 . Waltz , D. L . Generating semantic descriptions from drawings of scenes with shadows . AI TR- 271 (Thesis) , M. I . T ., Cambridge , Mass ., 1972 .
• 6 . Falk , G. Interpr e tation of imperfect line data as a three dimensional seen~ Artificial Intell igence 3, No . 2(1972) , 101- 141+ .

• 7 , Winston , P .H. Holes . AI Memo No . 163 , M. I . T., Cambridge , Mass ., 1970 .
• 8 . Harary, F . Graph Theory Addison Wesley , Reading , Mass ., 1969 .

a =1

z

Plane

I

Or---------------~

Fig . 2 Projection of a dual point , I, into gradient space .

A

B

F ig . 3 A FORK Junc t ion .

Fig . 4 Two gradient space configurations derived from Fig . 3 .

Fig . 5 The organization of the program.

~----PICTURE (

----'-RE�ION~eRE�ION )

OUTER CLOSURE d.-

INNER CLOSURE~····INNER

LINE ~······LINE

LEFT END~RI�HT END )

POINT)

(X · y)

( 0)

SCENE t-< ------~

,suRFACE J

OUTER BOUNDARY) ~~---------..,

NER BOUNDARY:JuiNNER BOUNDARY J

E-._.ueEDGE

1 --1 END 2 J

(b)

E L suRFACE , CLOSURE J

Fig . 6 The picture and scene data structures.