The general problem addressed by the method of the present invention is the interpretation of two-dimensional images of three-dimensional scenes. The problem, in a form addressed by prior art methods, is directed to image interpretation where the three-dimensional scene is comprised of plane faced objects. The two-dimensional image of such a scene is composed of the faces, edges and vertices of the three-dimensional objects. By techniques known in the art, that are not the subject of the present invention, e.g. edge detection or image segmentation, such a two-dimensional image can be initially processed by a computer to generally distinguish the object edges as lines and the vertices as points at which those lines intersect. Each face, then, is simply a connected region enclosed by the lines. Where the three-dimensional scene includes shadows caused by a light source directed onto the scene, the shadow regions will also be delineated by the image processing. For convenience, the features of the two-dimensional image are referred to herein as vertices, edges and faces. The interpretation of the two-dimensional image commences with this initial image data, generated by initial computer processing, about the three-dimensional scene.
A variety of methods are known in the art for interpreting the initial image data characterizing the two-dimensional image as edges, vertices, and faces. One particular method that is relevant to the practice of the present invention is an image intrepretation method formulated by David Waltz. That method is described in the book "The Psychology of Computer Vision" Chapter 2 of which (pages 19-91) is authored by David Waltz, the book being edited by P. H. Winston and published by McGraw-Hill, 1975. Chapter 2 of that book is incorporated in its entirety herein by reference. Basic aspects of two-dimensional image interpretation including D. Waltz's method are described in the book "Artificial Intelligence" by P. H. Winston, Addison-Wesley Publishing Company, 1984, at pages 43-72, those pages being incorporated in their entirely herein by reference. Common to such image interpretation methods is a cataloguing, by symbolic labels, of the possible edge and vertex configurations that may be encountered. Such configuration labels, many of which being illustrated in the above incorporated text pages and some of which being described and illustrated hereinbelow, serve to characterize the vertices and each image edge that extends between a pair of vertices. Commencing with the initial image data, it is at best possible to assign a plurality of possible ones of such labels to each vertex in the image. Waltz describes a method of "filtering" these labels, i.e. eliminating from consideration labels that cannot correctly characterize a particular vertex and an edge extending from that vertex to another vertex. That filtering method proceeds by using the labels at one vertex to constrain the possible labels at each other adjacent vertex joined thereto by an edge. In this manner, the constraints are propagated throughout the two-dimensional image and the number of labels remaining at each vertex is minimized. This basic aspect of the filtering method is referred to herein as contraint satisfaction and propagation. Descriptions of theoretical aspects of constraint satisfaction and propagation, as applied to a network of nodes, are disclosed in "Consistency in Networks of Relations" by A. K. Mackworth, Artificial Intelligence, Vol. 8, pp. 99-118 (1977); "The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems" by A. K. Mackworth et al., Artificial Intelligence, Vol. 25, pp, 65-74, (1985); and "Network of Constaints: Fundamental Properties and Applications to Picture processing" by V. Montanari, Information Science, Vol. 7, pp. 95-132, (1976).
One deficiency with the Waltz filtering method is the relatively long computing time required to execute it upon a complex image. It would therefore be desirable to provide an image interpretation method that constrains the image labelling to characterize a two-dimensional image in a relatively short computing time.
The Waltz filtering method by concentrating on satisfying the constraints existing between adjacent vertices achieves what is referred to as local consistency between those vertices. That is, since the labels at each vertex are constrained by and used to constain the labels at each adjacent vertex connected thereto by an edge, a local consistency is achieved between such adjacent vertices. The filtering method does not by its nature achieve global consistency over the entire image being interpreted. Global consistency means that the label(s) remaining, after a process such as Waltz's filtering method, for each image element is consistent with all other element labels remaining in the image. With respect to Waltz's filtering method, it is suggested that the art that global consistency among image element labels can be achieved following filtering by performing an additional depth first search with respect to each label. In such a depth first search, each label would be considered in turn with respect to its consistency not only with labels of adjacent elements but also with labels of all other elements in the image. As a result, for an image having m elements being labelled and an average of n labels remaining per element, after filtering, the size of the remaining search space within which to perform the depth first search is on the order of n.sup.m possible label combinations. For a fairly complex image where m is on the order of 100 or more, it is readily apparent that the remaining computing task to achieve global consistency can be prohibitively large. Aside from this disadvantage associated with attempting to achieve global consistency, problems can arise if the image being interpreted contains extraneous elements or is missing one or more elements (e.g. extra or missing lines). In such a case, the depth first search to achieve global consistency may find no consistency at all and the entire interpretation process will fail. It is therefore additionally desirable to provide an image interpretation method that does not suffer these disadvantages associated with achieving global consistency.