Labelling an Image

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.

Constraint satisfaction is common implementation method for line labelling.