Computer Reconstruction of Bodies Bounded by Quadric Surfaces from a Set of Imperfect Projections

Candidate: Shapira,Ruth

Abstract

This thesis describes a computer program for constructing a description of solid bodies from a set of n pictures of the bodies. The bodies are assumed to be bounded by faces which are quadric or planar, and they are restricted to have all their vertices formed by exactly three faces. The pictures are taken from different vantage points, with the restriction that a slight shift in vantage point will not alter the topology of the picture. It is assumed that the program receives outline information from a preprocessor which has extracted this information from the pictures. The outline information (set of line structures) may be imperfect in that some junctions may be erroneously reported and some lines may be missing. However, all lines due to shadows are assumed to have been eliminated by the preprocessor. The thesis includes a technique for establishing the validity of the junctions presented by the preprocessor as well as for matching corresponding features in the line structures derived from the different pictures. New grammar rules for line-drawing projections of curved and planar solid bodies are developed. These are useful in parsing the line drawings. They have also led to the definition of a new family of impossible objects. The program works simultaneously with all the available line structures. The parsing of every line structure is supported dynamically by the results gotten thus far from the parsing of the other line structures. Through the parsing of the line structures, the use of picture comparison and the application of the grammar rules, many of the preprocessor errors are detected and partly corrected. The program also can provide feedback to the preprocessor in the form of suggestions as to where to look again for lines in the pictures. The program utilizes the extracted line structures corresponding to the different bodies in all the pictures to determine the set of faces (insofar as possible) for every body. Every face is defined by an ordered set of n-tuples. The n-tuples are the matched lines and junctions in the n different pictures. The three-dimensional coordinates of the vertices and the equations of the faces can then be determined from these n-tuples. The program was written in PL/I and has been tested on several scenes.