Suppose we have a line image and wish to automatically label it. At each vertex

- the labelling must
be one of the permissible ones -- one of a relative small number
of possibilities.
- each line segment has two ends, and it must have the same labelling at each end, at least in the case of polyhedral models.

Start by taking the outside lines in the image and label them as occluding the background.

We may now organise our method as a tree search.

- Choose a junction, label
it in a valid way,
- Move along its edges to neighbouring
junctions, labelling them in a consistent manner.
- If this is not
possible, we must backtrack and try another
alternative for a previous choice.
- Continue until we
have successfully labelled the drawing, or we have no
possibilities left.
- In the latter case the line image does not represent a valid physical object.

Note that more than one valid interpretation may exist, so we may wish to make our tree search exhaustive to find other permissible labellings, rather than just stopping after after finding one consistent labelling for the whole image.

David Marshall 1994-1997