next up previous
Next: Further Reading Up: Model Based Object Recognition Previous: Relaxation Labelling Methods

Graph Searching

A graph consists of

 

Fig. gif Picture of a mug and its simple graph representation

Note that some relationships are two-way, such as distance, in that the relation does not depend on the direction of the link.

Other relations, such as adjacency, do depend on the direction.

Recognition:

Let us return to consider how Nevatia and Binford perform their matching strategy. They use a surface model with generalised cylinders as features, arranged in a relational graph. The features are collected into sets called ribbons  which contain groups of three-dimensional edges. Each group is hypothesised to form the boundary of a single generalised cylinder.

A region where several ribbon connect is represented by a joint . The representation of each joint contains a list of connected ribbons. This list is ordered, placing the longest or widest ribbons first. The longest (or widest) ribbon is said to be distinguished.

For each view of the object a relational graph is constructed with joints as nodes, and with links corresponding to associated ribbons. These links store various geometric properties of the ribbons, including axis length, average cross-section width, elongation and class (cone or cylinder).

The graph representing the view is then matched to the model description in two steps:

  1. For each distinguished ribbon three properties are chosen to drive the matching. These are: Initial matches are sought by looking for distinguished features in the image. If more than one match is found then the above properties are used to decide which matches are most likely and hence should be considered first.
  2. The matches are then grown to include other ribbons so long as the consistency of the connectivity relations is retained. A graph formed from a view is, however, allowed to match the model graph if some ribbons in the model graph are not present in the view. This amounts to finding subgraphs and allows for partial occlusion.

next up previous
Next: Further Reading Up: Model Based Object Recognition Previous: Relaxation Labelling Methods

dave@cs.cf.ac.uk