Reconstruction of Curved-Surface Bodies from a Set of Imperfect Projections
Proceedings of the Fifth International Joint Conference on Artificial Intelligence. Vision. Pages 628-633.
© 1977 International Joint Conferences on Artificial Intelligence
Abstract
A procedure is described for obtaining the description of solid bodies from a set of pictures taken from different vantage points. The bodies are assumed to be bounded by faces which are planar or quadric, and to have vertices formed by exactly three faces. The line and junction information provided to the program by the preprocessor is assumed to contain defects such as missing lines or wrongly classified junction types. The procedure is able to build a description of the bodies in spite of a moderate number of such imperfections. Use is made of a set of new grammar rules for line-drawing projections of curved and planar bodies.
- R. T. Chien, Y. H. Chang, "Recognition of Curved Objects and Objects Assembly", Proc. of the Second International Joint Conference on Pattern Recognition, IEEE Publication No. 74 CH0885-4C, Copenhagen, pp. 465-510, August 1974 .
- M. B. Clowes, "On Seeing Things", Artificial I nte 11 i gence, .£, ( 1 ) , 1970, pp . 79-116.
- G. Falk, "Computer Interpretation of Imperfect Line Data as a Three-Dimensional Scene", doctoral dissertation, Computer Science Department, Stanford University, Stanford, CA, August 1970. (AD 715 665).
- S. Ganapathy, "Reconstruction of Scenes Con- taining Polyhedra for Stereo Pair of Views", AI Memo 272, Stanford University, Dec. 1975.
- A. Guzman, "Computer Recognition of Three- Dimensional Objects in a Visual Scene", doctoral dissertation, M.I.T., Cambridge, Mass., December 1968. (AD 692 200). •
- D. A. Huffman, "Impossible Objects as Nonsense Sentences", Machine Intelligence, 6, ed.
- B. Meltzer and B. Michie, American Elsevier, 1971' pp. 295-323.
- L. G. Roberts, "Machine Perception of Three- Dimensional Solids", Optical and Electro- optical Information Processing, ed.
- J. T. Tippet et. al., M.I.T. Press, Cambridge, Mass., pp. 159-197, 1965.
- R. Shapira, "Computer Reconstruction of Bodies Bounded by Quadric Surfaces from a Set of Im- perfect Projections", doctoral dissertation, ~ew York University, Sept.l976. (AD A035 563).
- R. Shapira and H. Freeman, "A Cyclic-Order Property of Bodies with Three-Face Vertices", accepted for publication in IEEE Transactions on Computers.
- S. A. Underwood and C. L. Coates Jr., "Visual Learning from Multiple Views", IEEE Transac- tions on Computers, C-24, (6), June 1975.
- D. A. Waltz, "Generating Semantic Description from Drawings of Scenes with Shadows", doc- toral dissertation, Artificial Intelligence Lab., M.I.T., Cambridge, Mass., November 1972. (AD 754 080).
- P. Wood and H. Freeman, "A Procedure for Generating Visible-Line Projections of Solids Bounded by Quadric Surfaces", Information Processing 71, ed. bu C. Freiman, North-Holland Publ. Co . , Amsterdam, 1972, pp. 1120-1125.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
In computer scene analysis a picture of a three-dimensional scene is converted into an array of pixels, with each assigned a number correspond ing to the average grey value in that local area of the picture. A common scheme for preprocess ing the array for scene interpretation is to ex tract lines that are believed to correspond to the bodies' edges. To interpret a perfect line description of a scene, a picture grammar must be supplied that is based on the common general prop erties of the scene's bodies. When the line des cription contains errors (as a result of prepro cessor limitations), its parsing and interpreta tion becomes difficult if not impossible. In such a case, understanding of the scene can be gained by using a set of line structures (each possibly defective), extracted from pictures describing the scene from different vantage points, a scheme which is also useful for obtain ing three-dimensional information about the bodies.
The scene interpretation given in terms of edges (grouped first according to faces and then according to bodies), is most suitable for poly hedra, but can also be applied to curved bodies. This paper is restricted to the analysis of bodies with planar or quadric faces. The tech nique, however, could easily be modified to handle also bodies whose curved faces are close to quadric surfaces, and this includes a large sub set of man-made bodies .
Many papers were published in recent years dealing with polyhedral scene analysis, of which the papers by Roberts (7], Guzman [5], Falk [3], Huffman [6], Clowes [2], Waltz [11] and Ganapathy [4] are representative of the line of research that has been pursued. Some researchers contributed to the understanding of the process of perception by analyzing perfect (but unfeas ible) line drawings. Others used real data (slightly edited) with its imperfections, but re stricted themselves to a set of known bodies. Nearly all limited themselves to a single picture of the scene. (A restriction that led to many unnecessary difficulties) . The work by Underwood and Coates [lD] does utilize multiple pictures in the analysis of scenes of a single convex poly hedron - not to overcome data and analysis prob lems but merely to "have a look" at all sides of the body.
* This work was supported by the Directorate of l~athematical and Information Sciences, Air Force Office of Scientific Research, under grant AFOSR 76-2937.
Attempting to extend the work from polyhedra to even a restricted family of curved bodies increases the difficulties to an extent which may not be apparent at first glance. Such an effort has been described by Chien and Chang [1]. They analyzed perfect line drawings representing bodies with planar, conic, or cylindric faces, where no intersection of two curved faces was a 11 owed.
In this paper we shall show how a program can be made to "understand" a set of bodies with planar or quadric faces, utilizing defective data extracted from a set of multiple photographs.. No pre-knowledge of the bodies is assumed, but cer tain general properties of the scene - such as the existence of precisely three faces in every vertex - are stipulated.
2. Basic Assumptions
The terminology used has been adapted from that employed by Woon and Freeman [12] and Clowes [2].
We impose the following restrictions: 1) Every vertex in the scene is formed by exactly three surfaces and belongs to exactly three edges; 2) Smooth transition between two different faces is not allowed (i.e., the derivative must be discontinuous across the edge); 3) The camera position is assumed to be "general". (For exam ple, the projections of different vertices may not coincide in any picture); 4) No limb passes through a vertex .
In accordance with the foregoing, junctions can have no more than three lines. They can be classified into the types W, Y, V, T, A, and S. An example of each type is given in Fig. l(a). Types Y and W must be the projections of vertices.
Type T results from the covering of part of an edge or a limb by a face. ~ypes ~and A a~e the projections of virtual vert1ces (~ntersect~on~ of edges and limbs). In a perfect l1ne descr1pt1on V is also a projection of a vertex.
The scene data is assumed to be extracted visually from a set of real photographs. The data includes line information (as a set of points) and junction information consisting of c?ordin~t~s and types. The data is expected to be (1n add1t1on to the geometric inaccuracies) defective in the sense that (1) visible lines or parts of visible lines may be missing, (2) visible junction~ may be missing, (3) junctions may be reported 1ncor rectly (V instead of Y, W, TorS junctions).
We call a junction valid when it is a pro jection of a vertex. Thus-aTT Y and W junctions are valid, all A, S, and T junctions are not valid, and the nature of the V junctions cannot be decided until more evidence is collected (as will be explained later). In those cases in which a preprocessor has difficulty in distin~uish~ng between a T junction and a flat Y or W Junct1on, they can be included in the group of the undecided junctions.
3. Cyclic Order Property
As already stated, every vertex belongs to exactly three edges. We define for these edges.a cyclic order in the vertex [8,9], as ~he order 1n duced by "walking around" the vertex 1n a clock wise manner, and numbering the edges in the order 1<2<3<1. If we trace out the edges of a boundary, we consistently change edges at the vertices, either always in a decreasing cyclic order or always in an increasing cyclic order. Let us always choose to trace edges in an increasing order. Then we shall traverse every edge in two different directions as we walk around the two faces that share it, as illustrated in Fig. l(b) . When a vertex's projection has three lines, their cyclic order is determined by the arra~gement of the lines in the picture. (The clockw1se sense of the cyclic order is preserved in a projection when the three edges are visible). However, when one line is invisible or missing, the cyclic order is not known. Let us define the notation AB<AC to mean that in junction A the line AC follows the line AB immediately in the cyclic order. Then if A is a two-line valid junction, we have either the relation AB<AC or the relation AC<AB.
Knowledge of the cyclic order at a junction is crucial to the assembly of the lines belonging to a single region. Therefore it is important to have means for determining the cyclic order in a junction when the order is not given naturally.
We define a line assembly (LA) as the direc ted path followed in tracing out the lines ~orre~ spending to a single boundary - or any cont1nuous part of it - in increasing cyclic order. We de note an LA in picture i by the ordered set of junctions A. 1 ..... A. visited in the course of 1, 1 ,n the trace. Now it follows from the definition that for every l <k<n we have Ai,kAk,{k-l) < Ai,kAi,(k+l)" Two LA's are said to be distinct if they trace out lines corresponding to two dis tinct boundaries. Two LA's, A;, 1 ... A; ,n and A. 1 ... A. , are distinct if J' J ,m
- A. 1 ~A . . and there is at least one AJ. 1 , 1 , n different from every A;, or
- There are two successive junctions in the
- two LA's such that Ai,k ~ Aj,h and Ai,(k-l) ~ Aj,(h+l)' or
- A. ~A. 1 and the relation A. 1 A. 2 < 1,n J, J, J, A. ( l)A. exists. 1, n- 1,n
Two rules forcing a cyclic order in a junction can be stated now:
For example in Fig. 2(a) we have the LA B,C,D,A, B. (The LA is shown as an arrowed line). The lines in Bare thus forced to have the relation
BA<BC
Rule 2: If we have two distinct LA's, A. . .. A. r.nd A. 1 ... A. such that 1,1 1,n J, J,m A. ~A. 1 and A. ( I) t A. 2 then we must J ,m 1 , J , m1 , have in Ai,l the relation Ai,lAi, 2 < A. A. ( l) . J,m J, m-
For example in Fig. 2(b) we have the two distinct LA's: E,F,C,B and B,A,G,E. They are distinct because of the cyclic order already established in junction B by Rule 1. Now by Rule 2 the rela tion EF<EG must hold in E. (This in turn estab lishes the LA M,F,E,G,N,O) .
A more complicated strategy may be adopted to force the correct order at a junction when these two rules cannot be applied directly. One assumes a cyclic order in the junction and .tries to reach a contradiction by a sequence of 1nduc tive steps. If a contradiction is reached~ the cyclic order opposite to the one selected 1s forced on the junction. For example, in _ Fig. 2(c) we assume an order in junction R such that RQ<RN. Then we can establish the LA's P,Q,R,N,G,A,D and D,C,F,M,P. They are.distinct because of the existing natural order 1n D, and hence by Ru 1 e 2 force in P the re 1 at ion PQ<Pt·1. At the same time we have the two LA's R,Q,O and 0 N R which are distinct due to the assumed order i~ R. By Rule 2 the relation ON<OQ is forced in 0. This in turn establishes the LA M,F,E,G,N,O, Q,P,M. Now by Rule 1 we must have in M the relation MP<MF, which contradicts the natural order in M. This sequence of deductions was based on the assumption that the relation RQ<RN exists in R. The contradiction reached lets us conclude that the opposite relation, namely RN<RQ, must exist in R. This establishes the LA O,N,R,Q,O and, by Rule 1, the relation OQ<ON in 0. We have thus been able to find the cyclic order in 4 of the original 5 unordered junctions. Junction P remains unordered. The final ordering of the junctions is given in Fig. 2(d).
A by-product of the foregoing is a new class of impossible objects, in addition to those des cribed by Huffman [6]. The objects can be identi fied as being impossible if their structure is such as to lead to contradictory cyclic order at their junctions [8,9].
4. Junction Matching
To utilize the data from all pictures, we must know the parameters that relate each picture's coordinates to those of the other pictures and also to the universal coordinate system in which the final description should be given. These parameters are difficult to measure. Some of them are measured indirectly and some are calculated by minimizing the sum-of-squares differences between the measured and calculated projections of a set of predetermined points. A detailed description of the parameter determination is given in [8].
In order to arrive at a true description of the 3D scene in spite of the data imperfections, we compare the line structures from the given pic tures (three in our case) against each other and use the information found in one picture to verify the information found in another.
Let us start with junctions. We have two goals. One is to determine those V junctions for which there is enough evidence to assume that they are valid junctions. The second is to group, from the different pictures, junctions that are the projections of the same vertex . From here on in this section, whenever we use the term "junction", we shall mean a V, Y, or W junction.
If two junctions in two different pictures are projections of the same vertex, they must obey certain geometric rules . Let P., C. and A. J be 1 1 1 ' the picture plane, the center of projection, and the projection of vertex J, respectively, for picture i. Then for two pictures, i and j, C., 1 Cj' J, Ai,J' and Aj,J are coplanar, and the lines CiCj, CiAi,J' and CjAj,J intersect any plane pq in three colinear points: C .. , J . and J., 1Jq 1q Jq respectively (Fig. 3). We shall call the line formed by these points a match line. Thus if we re-project into the plane P junvyion A. from C 1 ., . . q 1 ,J Junct1on A. J from c., and C. from c., we can J, J 1 J check whether this condition is satisfied. Two junctions from different pictures that satisfy this condition are said to be matchable.
Obviously, if a vertex I is in the plane of C. ,C . , and J, then A. I and A. J are matchable, 1 J 1 ' J' and so are A. JandA. I" To resolve such 1 ' J' ambiguities, we refer to the third picture, picture k. We require that Ci' Cj, Ck be not colinear. Then if A. J' A. J' and Ak J are the 1 ' J ' ' three projections of vertex J, the three different match lines on plane Pq form a triangle whose vertices are Jiq' Jjq' and Jkq (Fig. 4). We call the set of three junctions, from different pic tures, that are matchable in pairs, a triple. By forming triples we can eliminate many pairs that are matchable but are not projections of the same vertex. However, even in the pure geometric case we may have three projections of three dif ferent vertices that form a triple [8].
We are dealing here with data extracted from actual photographs; thus we must accept Ai,J and A. J as matchable even ff J. is distant from J . 1 q the match line CijqJjq by an amount less than some threshold. Relaxing the colinearity require ment on the match lines increases the ambiguity of matching. The larger the threshold distance, the greater the number of ambiguous cases.
Two matchable junctions that are the projec tions of the same vertex are said to match each other. A triple in which the junctions match each other is called a match triple. To establish matches, we find for every junction all matchable junctions in the two other pictures. Then we form all the triples. To find the match triples in the set of all triples, we must use some pic ture context. The kind of context we shall use is line connections between junctions. If we have three lines -each in a different picture whose ends form two triples, the two triples are each considered to be a match triple. (The chance of naming a wrong triple as a match triple still exists but is now greatly reduced).
Since it is possible that a vertex's pro jection will be missing in one or more pictures, it is desirable to establish matches between matchable pairs. Naturally, more context must be used to establish a match on the basis of only a two-picture comparison. The pair match is done in two passes and only after the triple match phase is camp 1 eted. (It reduces the number of free candidates and, therefore, the chance of error). We select a set of three junctions for which one of them - call it the middle - is con nected by lines to the other two that are match able to a set of three junctions connected (in the same way) in another picture. In the first pass we require that the middle junction be of type Y or Wand that the two lines have the same cyclic precedence in the two junctions. The three junc tions are then assumed to match the three junc tions in the other picture. In the second pass we allow one or both of the middle junctions to be of type V and do not check the cyclic preced ence (it may be unknown for the V junction). The second pass is a little more hazardous since we are unable to use cyclic precedence, but since it is carried out after most junctions are already matched, there is only a small chance of making an error. If one junction in a triple is matched to the other two by two applications of a pair wise match, we consider the triple to be a match triple; that is, we consider the remaining two as matching also.
Every V junction that is matched to a junc tion in another picture is marked as valid. The match supplies additional evidence that the junc tion is a projection of a vertex. The validated V junctions are assigned a cyclic order, when possible, by applying the cyclic order rules.
5. Line Matching
The matching of lines in different pictures poses difficulties because of data imperfections and because the number of lines between two junc tions can vary from zero to three. Matching is done for two pictures at a time for the lines terminating at matched junctions. There are three cases to be considered: (1) The two matched junctions are both 3-line junctions, (2) one is a 3-line and the other a 2-line junction, and (3) both junctions are 2-line junctions. For a detailed discussion of this the reader is referred to reference [8].
When two junctions around which a match of lines is attempted are both cyclically ordered, a match of one pair of lines yields in turn the corresponding match of the successors in the cyclic order. Also two lines in two pictures found to match to the same line in a third pic ture are declared to match each other.
When two lines of a cyclically ordered junction are matched to two lines of an unordered junction, the second junction can be ordered because its cyclic order must agree with that of the junction to which it is matched.
The line matching procedure makes it possible to detect missing connections between junctions. The lines around the junctions are assigned indices that agree with the cyclic order in ordered junctions, or re-assigned to agree if the cycJic order is determined at a later stage.
6. Object Formation
The collection of lines from all pictures that correspond to the boundaries of a single face will be referred to as a face group. Clearly, every line that is not a limb belongs to two face groups. We build a face group by selecting a line, in any picture, that does not yet belong to two face g\oups. We then follow the LA in a direction not previously followed, adding to the group every line traced and its matches in the other pictures. If the trace returns us back to the line from which we started, the trace is terminated - and this face-group generation is complete, assuming that the face has only one boundary. Otherwise when we reach a line for which no next line in the LA is available, we check whether an LA trace can be continued from the line's match in another picture. The face group generation may thus proceed by "jumping" from one picture to another. If the process is blocked in all pictures, we return to the start ing point and try to follow the LA in the oppo site direction, again "jumping" from one picture to another, if necessary, until the process is blocked again in all pictures. All Sand A junctions encountered in the trace are remembered. When the process terminates, the limbs at these junctions are checked and if a limb's other end junction belongs to a line not yet in the face group (implying that another boundary of the same face has been detected), the trace resumes there. The limb lines are also added to the face group.
When all lines have been traced twice, further data recovery action is called for. This second-level data recovery can be carried out for the following three configurations, illustrated in Fig. 5.
- Two lines t and kin the same picture, with a valid junction in only one end of each, have been assembled into two face-groups M and N, k, t E M and k, t E N
Action: Combine t and k into one line.
- A line t with one valid end junction has been assembled into two face-groups M and N, and there is in the same pic ture a 2-line valid junction J with lines m and n, mE M and n EN.
Action : Extend the line t to junction J .
- There are two 2-line valid junctions and J in the same picture with lines k, t and h, g, respectively, where k and h have been assembled into face group M, and t and g have been assem bled into face-group N.
Action : Create an "empty" line between the two junctions I and J. (An "empty" 1 ine is a 1 ine whose only known points are its end junctions and whose form has not yet been determined.)
The data recovery actions utilize the prop erty that two components assembled simultaneously into two face-groups must correspond to the inter section of the associated faces. There is, of course, the possibility that the intersection is sectioned into several separate edges and that the two lines correspond to two different sections; but at this stage of the recognition phase, with no evidence to the contrary, we assume that they belong to the same section.
Each face group corresponds to a face of one of the bodies in the scene. After the face group assembly and second-level data recovery is completed, we are ready for the description of the objects. Each object is a set of face-groups, with no common elements between two sets. Every face group must belong to some set. A new object is formed by taking a face group that is as yet unassigned and recursively adding to it every unassigned face group that has a line in common with any of the face groups already in the set.
We also wish to determine those face groups that correspond to curved faces. Clearly, every curved face must manifest itself somehow, or we have no way for recogniziing it as curved . We know that whenever two face groups share, in at least one picture, a curved line, at least one of them must correspond to a curved face. It is also obvious that every face group that contains a limb must correspond to a curved face. Thus to determine the curved face, we build, by means of a tree search, a minimal set of faces containing initially all those faces whose face groups have a limb, such that at least one partner (actually its corresponding face), from each pair sharing a curved line, is present in it. A procedure for extracting information about the nature of the faces and for getting the faces' equations is described in [8].
7. Experimental Results
A scene that is typical of the kind con sidered for analysis is shown in Fig. 6. Three views are shown, each from a different vantage point. Schematic descriptions of the three pic tures are given in Fig. 7. In the input data, the two non-limb lines of an S junction, which are actually parts of the same line, have dis tinct labels; however, later on one of these can be deleted.
The procedure was able to validate 28 of the 34 V junctions in the junction-matching phase . After the line-matching process, all the junctions shown circled in Fig. 7 had been cyclically ordered. Data recovery action caused the "empty" lines (shown dashed in Fig. 7) to be generated, as well as the line extensions marked by arrows.
The final scene description reported by the program was given in the form of face groups (consisting of sets of triples of matched lines) for each of the 5 bodies in the scene. Detailed results, as well as other scenes processed, are described in [8].
8. Conclusion
The objective of the research described here was to investigate techniques for the com puter understanding of pictures of scenes. Three principles guided the research: (a) No complete preknowledge of the scene's bodies should be assumed since that would limit the repertoire of bodies. (b) The number of bodies should be un restricted and merely some properties of the bodies should be prespecified which are suffi ciently general to permit inclusion of all bodies likely to be encountered. (c) Since the input is to be gotten from photographs, the presence of a limited amount of data imperfections such as missing lines, wrong junctions, and geometric inaccuracies should be permitted.
To achieve the objective, a set of multiple pictures of the scene was assumed to serve as the input data . New grammar rules needed for the analysis of these pictures were formalized. A procedure for establishing matches between fea tures in the different pictures and for verifying doubtful features were devised, as well as pro cedures for eliminating wrong data and for re covering missing data. Finally a procedure for assembling the analyzed data into sets, each des cribing a single body of the scene, was construc ted, including the determination of the bodies' faces and their nature. A computer program based on this approach was written. The program was able, given real input data, to "understand" the photographed scene, and to yield a plausible description.
@inproceedings{ijcai1977p147,
title = {Reconstruction of Curved-Surface Bodies from a Set of Imperfect Projections},
author = {Shapira, Ruth and Freeman, Herbert},
booktitle = {Proceedings of the Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-77}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Raj Reddy},
pages = {628--633},
year = {1977},
note = {Vision},
url = {https://ijcai.org/proceedings/1977/147},
}
TY - CPAPER TI - Reconstruction of Curved-Surface Bodies from a Set of Imperfect Projections AU - Shapira, Ruth AU - Freeman, Herbert T2 - Proceedings of the Fifth International Joint Conference on Artificial Intelligence, IJCAI-77 PB - International Joint Conferences on Artificial Intelligence PY - 1977 SP - 628 EP - 633 UR - https://ijcai.org/proceedings/1977/147 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: