Tree Search Methods

Next: Relaxation Labelling Methods Up: Model Based Recognition Previous: Model Based Recognition

Basic approach:

Nodes of the tree represent a scene to model primitive (e.g. edge, surface) match.
Let Tree have m branches at each node that correspond to model primitives.
Let level of tree represent a model primitive.
The level and node position specify a match pair.
Use a depth first tree search to find a match.
One traversal through tree gives a match list -- a possible match of scene to model features.
Representation called a search or interpretation tree.

Fig. 51 Interpretation tree

How do we perform matching?

At each level of the tree, one of the edges from the scene is matched with each of the m possible edges in the model.
Each node has m children representing taking the match proposed so far together with all possible matches for the current scene edge.
A transformation representing the match so far can be maintained.
Search tree in depth first manner and pruned by rejecting interpretations that fail to satisfy current match.
The search space is large -- possible combinations for n scene primitives.
A lot of computations?

We can reduce the computational overheads by employing some local geometric constraints to prune the tree further.

These are:

For Edges we could employ:

Distance Constraint: -- The length of the sensed edge must be less than or equal to the length of the model edge under consideration.
Angle Constraint: -- The angle between two adjacent sensed edges must agree with that between the two corresponding matched model edges.
Direction Constraint: -- Let represent the range of vectors from any point on sensed edge a to any point on sensed edge b. In an interpretation which respectively pairs sensed edges a and b with model edges i and j, this range of vectors must be compatible with the range of vectors produced by i and j.

For Surface we could employ:

Next: Relaxation Labelling Methods Up: Model Based Recognition Previous: Model Based Recognition