pi
P2
P3
DN-1 qT
2/1 4
DN 96 à 92 & 98
Figure 2: Search tree representation of a correspondence problem
trying all possible combinations between the primitive sets. Sev-
eral search algorithms have been developed, performing a more
efficient scanning of the tree [Nilsson 1982].
A tree search always starts at the root node of the tree. At
this point no assignments have been made. The root node is
expanded by generating the successor nodes. These nodes rep-
resent the possible assignments between the first unit primitive
and admissible label primitives. A label is admissible if it has not
been used before and if the mutual information between the unit
and that label is not minus infinite. One of the generated suc-
cessor nodes is inspected and expanded afterwards. The search
space (defined by the search tree) is examined by visiting and
expanding the nodes of the tree until a solution has been found.
A simple method to determine the order of visiting the nodes
in the tree is called the depth first method. The depth first
method tries to move to the bottom of the tree as fast as possible
by always expanding the node on the deepest level of the tree.
Scanning the tree of figure 2 in a depth first manner one would
start by selecting the first successor node of the root node. This
node represents the assignment of label g; to unit p;. Because
this node now is the deepest one, the next step is to add the node
which e.g. represents the assignment of go to p? to this branch.
If there is no admissible label primitive q; left, a node can not be
expanded any further. The search then moves up to the parent
node and moves down again along one of the other branches of
that node. This procedure is called backtracking.
The depth first method has some serious disadvantages. An as-
signment, leading the search into a part of the tree where no
solution will be found, may appear at a very high level. Never-
theless, all nodes below this assignment will be inspected until
a new assignment at that level is tried. E.g., if the depth first
search expands the node, which assigns label q, to unit p; in
figure 2 all nodes in the sub-tree below this node will be visited
until the search reaches this level again. Beside that, one also has
to search the complete tree, because one does not know whether
the first path to a leaf node that has been found represents the
best solution. A more intelligent strategy has to be used.
Always expanding the most promising node would immediately
lead to the optimal solution. To this purpose the function f(n)
is defined representing the mutual information of the best path
through node n [Pearl 1984]. The merit f(n) depends on the
merit g(n), collected on the branch from the root node to node n
and the future merit h(n), which will be collected if this branch
is continued to a leaf node. Of course, it is impossible to com-
pute the future merit h(n) exactly. However, it can be estimated
roughly by calculating the mutual information of all unit to label
assignments which are left, without checking these assignments
for consistency. This value h*(n) is used to calculate an estimate
of the possible mutual information f*(n) = g(n) + h*(n) at every
node n. Leaving out the consistency check will always cause an
overestimation of the future merit and therefore f*(n) is always
greater than the true value f(n). During the so-called A* search
the estimated possible merit is used to decide which node is ex-
panded next. If the possible merit f (n) is always underestimated,
the A* strategy will always find the best solution first (see e.g.
[Nilsson 1982]).
4.3 Heuristics
Several heuristics can be used to reduce the number of nodes
which have to be visited in the tree. Because the future merit is
always overestimated, the A* algorithm tends to focus the search
on the nodes at the higher levels of the tree. If we use a lower
estimate of the total merit, calculated with the formula f*(n) —
g(n)-- (1 — e) h* (n), the search algorithm will reach the leaf nodes
faster. There is, however, a risk of loosing the optimal solution,
but the loss of optimality is limited to 7— Percent of the best
solution [Pearl 1984].
The number of nodes visited during a search depends on the total
number of image and landmark primitives. Another important
factor influencing the size of the search tree is the number of pos-
sible assignments between label and unit primitives determined
by possible correspondences of attribute values. It can be shown,
that the size of a search tree is reduced significantly, if units with
only few corresponding labels are used at the very first levels of
the tree [Haralick and Elliott 1980].
The search time can be further reduced, if branches of the tree
which do not lead to a solution are identified as early as possi-
ble. Since a correspondence of three points determines the trans-
formation parameters, wrong branches can be found by trans-
forming the landmark model into the image description after the
assignment of three points. The coordinate differences of image
and landmark points after the transformation are a good indica-
tor whether or not the assumed correspondence is possible. The
search at a wrong branch often can be terminated after the as-
signment of three points.
In section 3.2 we mentioned the necessity of using wildcard as-
signments, if primitives can not be matched. For this reason, a
consistent result can always be achieved by just adding wildcards
to a path. Of course, this is not desired. Therefore, the num-
ber of possible wildcard assignments is limited and the search
algorithm will not expand a node, if this number is exceeded.
5 RESULTS
Figure 3 right shows the landmark model projected into the hue
image using the parameters which were calculated by the match-
ing algorithm. The algorithm had to find a match between 25
label or model primitives (6 points, 12 lines, 7 regions) and 67
image or unit primitives (19 points, 33 lines, 15 regions). In all
examples we calculated, the scale between the landmark model
and the image was assumed to be within a range of +15% of a
given value. In example streetl, a match was found after exam-
ining 52 nodes of the search tree (figure 3 middle). As mentioned
in section 3.2, the algorithm projects the model into the image
after three image points have been mapped to model points. Six
972
The
tha
nee
inf
mal
mat
stro
exp
