Constraints Between Distant Lines in the Labelling of Line Drawings of Polyhedral Scenes

The machine interpretation of line drawings has applications both in vision and geometric modelling. This paper extends the classic technique of assigning semantic labels to lines subject to junction constraints, by introducing new constraints (often between distant lines). These include generic constraints between lines lying on a path in the drawing as well as preference constraints between the labellings of pairs of junctions lying on parallel lines. Such constraints are essential to avoid an exponential number of legal labellings of drawings of objects with non-trihedral vertices. The strength of these constraints is demonstrated by their ability to identify the unique correct labelling of many drawings of polyhedral objects with tetrahedral vertices. These new constraints also allowed us to deduce a general polyhedral junction constraint for the case when there is no limit on the number of faces which can meet at a junction.