B3. Istanbul 2004
be simplified by
rectly connect its
h of concepts for
aph for the sketch
several different
find an algorithm
reference graph.
dealing with sub
erties are shown
in this section. In
'oncepts is given.
ally a sub graph
ween the pattern
must satisfy all
the nodes. This is
this task is NP-
ithm is growing
graph except for
raph matching is
ant methods and
his case the NP-
omplexity is of a
approaches have
istical analysis of
exploitation of
ive tree search to
) each other. With
's at the nodes the
le a quick search
ithm described by
1s.
he pattern, which
ie most promising
1g for every node
and name: Îterate
raph with a depth
pattern node with
iterate through all
he next connected
e this assignment
connected to the
Jon't match or no
st saved state. Do
nodes are left. A
xtted) is growing,
aluated (dashed).
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
In Figure 5 the assignment of edges is shown in green and the
actually evaluated assignments are coloured red.
This is easy to implement when using recursion for each step of
the depth first search. Each recursion represents one state and
backtracking simply needs to recover all changes made in the
actual recursion step (this is a small number) and leaving the
actual recursion step.
This algorithm is useful if all possible solutions are needed. If
the algorithm cannot find an exact matching solution it can at
least find a largest common sub graph.
One drawback is the missing fault tolerance of this algorithm. It
is theoretically possible to introduce fault tolerance by allowing
the assignment of non matching nodes, pruning of pattern graph
branches and insertion of dummy nodes into the pattern graph.
Each of this actions will cause the accumulation of error points
and backtracking is done if a maximum number of error points
is reached. But unfortunately this increases the search space
enormously because the strong restriction of the existing classes
and names don't apply any more and some heuristic must be
found to prevent this large growing of the search space.
Other possible algorithms can be build on top of this algorithm
by using the largest common sub graph as a starting point.
Another approach is to exploit the assumption that a sketch
contains a lot of geometric information although the graph
constructed from the sketch consists of topological properties.
Some of the nodes in the graph are direct representations for
geometric objects and can be used to produce a unique
projection of the graph. If some of the assignments between
pattern and reference are known the sketch can be transformed
into the reference frame of the reference graph, producing more
tight constraints especially for the case of inexact matching.
This approach is strongly related to the method of elastic graph
matching (Lee, 2002). Vital for the success is a sufficient
similarity between sketch geometry and reference geometry and
up to now it is not clear if this premise is true.
4. ASET OF SKETCH CONCEPTS
The last section was dealing with the matching process of sub
graphs which is common for a large range of applications. But
now some specialization to the matching of sketches is needed.
The basic premises were already outlined in the context of the
definition of a sketch.
This section will propose a set of classes which has the ability
to describe a road network with its important properties and
leaves enough space for topological invariant operations on the
data. Geometry is explicitly not part of the description and does
only play a role for generating the description graph. However,
geometry can be stored as identifiers of objects that were the
source of the generated graph representation instances of the
objects, which is useful for some heuristics. The principal
geometric constraints applicable for sketches are the following:
* Nouniform scale across the whole sketch, but locally
similar scale.
=» Locally, the relations are true, e.g. a small building
next to a big one should reflect that this relation is
also true in reality, although the actual sizes of the
objects cannot be used.
* The directions drawn in the sketch, e.g. the directions
of the roads at a junction should be approx. true.
" The relative orientation of the objects should be
locally true.
Roads are used to explain the concepts first, at the end of this
section an extension to other objects than roads is suggested.
4.1 Objects
The objects in the sketch need a representation in the
description graph and form the skeleton for the relations
between the objects. In a road network two main classes for
objects can be identified if the road type is not modelled
explicitly: roads and intersections. This choice is clear when the
road network itself is seen as a graph where the edges are the
roads and the nodes are the intersections.
Here at first the nodes are considered because as 0-dimensional
elements they are the basis for the edges. The class is called
INTERSECTION or ISEC here. They can be easily derived
from the geometric data. The cardinality of a node is the
number of outgoing edges. All the points which are part of
more than two road segments (i.e. the cardinality is greater than
2) are intersections in the stronger sense, but points with only
one incident road segment can also be considered as an
intersection. They appear at the ends of roads. The cardinality
of two should only sometimes lead to the introduction of an
INTERSECTION because two road segments may meet at
points where nothing special is visible and only is an artefact of
the measurement process. Only if the direction of the road
segments does exceed a certain limit an instance of this class
must be modelled.
Roads are 1-dimensional elements of the road graph and are
always links between two intersections. Here the model class is
called ROAD. Elements of this class are always linked with
two terminating ISEC nodes. For reducing the number of
classes and nodes in the graphs this is indeed a mixture between
a relation and an object and usually should be used like in
Figure 6.
ISEC---ROAD---ISEC
Figure 6: Road Object.
It would be possible to introduce another relation LINK to
separate objects and relations like shown in Figure 7 but in
practice this is not necessary.
ISEC---LINK---ROAD---LINK---ISEC
Figure 7: Alternative construction of road objects.
4.2 Relations
Relations are connecting the objects of a given sketch or
reference data set but are modelled in the same way as the
latter. They are nodes of the description graph and define links
to other nodes, representing objects or other relations.
Some of the relations are connecting other nodes and provide a
certain meaning to this connection but some are only linked
with one node which has the meaning of adding information to
the target node.
The ISEC objects are the result of incident road segments at an
intersection. But after introduction of an ISEC instance the
information about the cardinality information is discarded. The
cardinality information can be reintroduced by using the classes
C1, C2, C3, C4, C5, ..., CN where CN means there are exactly
n or more than n road segments (Figure 8).
