Patent Document ID: 4888711
Application ID: 07121301
Patent Status: 1

Claim One:
1. A method for intepreting a two dimensional image of a three-dimensional scene on a computer, said two-dimensional image comprising a plurality of vertices, edges and faces, each said vertex being defined by the intersection of at least two said edges in said two-dimensional image, each said face being bound by a closed chain of said edges, each said vertex being associatively linked with its defining intersecting edges and with the faces bounded by the last recited defining edges, each said face being associatively linked with each said edge of the closed edge chain bounding the face, said method comprising the steps of: (a) assigning a vertex label, an edge label and a face label respectively to each said vertex, edge and face of said image, each said vertex, edge and face label respectively being selected from predetermined hierarchies of said vertex, edge and face labels; (b) assuming for each said vertex label a predetermined set of junctions that is consistent with said vertex label, each junction being a possible edge configuration; (c) assigning for each said face all possible junction loops that are consistent with the face labels assigned to said face, each said junction loop being an n-tuple of said junctions and consisting of one said junction from each of n said vertices respectively at each of n said intersections of the edges bounding said face, each pair of vertices of said image being joined by a common image edge and respectively represented in each said junction loop n-tuple by junctions respectively having the same edge label for said common edge; (d) assigning for each said edge all possible junction pairs that are consistent with the edge labels assigned to said edge, each said junction pair being a two-tuple of said junctions and consisting of one of said junctions assigned to each said vertex at each end of said edge, within said junction pair the junctions respectively assigned to the vertices at the ends of said edge having the same edge label for that edge; and (e) performing constraint satisfaction and propagation (CSP) between the linked vertices and edges of said image, between the linked vertices and faces of said image and between the linked edges and faces of said image, the CSP being performed using said junctions, said junction pairs and said junction loops assigned to said vertices, edges and faces of said image, respectively; so that the junctions, junction pairs and junction loops and their respectively corresponding vertex, edge and face labels remaining upon completion of step (e) are descriptive of said three-dimensional scene.