International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
information for the recognition task. The data can be seen as
implicitly represented knowledge which has to be made
explicit.
A well known representation for knowledge is the use of a
graph structure. Here the special case of a conceptual graph
applies (Sowa, 2001). The information is represented in the
nodes and edges. The nodes are labelled with the concepts and
the edges determine the relations between the concepts. In this
representation the task of identifying a sketch is identical with
the task of finding a sub graph isomorphism between the graph
representation of the sketch data and the graph representation of
the reference data.
A sub graph isomorphism (Cortadella, 2000; Lipschutz, 1976)
is given if for every node in the pattern another node in the
reference can be found with the same Type and when the edges
of the pattern graph have corresponding edges in the reference
graph.
When organizing the knowledge about the sketch and the
reference data in graphs, a semantic component is needed. How
this can be provided is shown here, following (Sowa, 2000)
At first the problem is dealing with objects of the real world
where the objects are defined by the human understanding of
the world. Objects in this sense can be roads, buildings,
junctions, railroads, etc. The given terms are already a
classification of the individual objects and can be called
classes. The individual objects themselves are then called
instances of a class. Each instance can be given a unique name
which allows the identification of this particular instance. The
classification should be unambiguous.
Each object is now considered to be one node of the graph and
labelled with its class and the name of the object. This step
doesn't produce connections between the nodes and the graph is
totally disconnected.
The next step is dealing with relations between the given
objects, making the graph unique if it describes a unique
situation in reality. For the description of the graph structure it
is not important which kind of relations are used. A relation can
be modelled between an arbitrary number of objects. Usually
two objects are involved but there can be more than two objects
or only one object which relates to itself in some particular
way. One example is the neighbourhood relation which is
dealing with two objects. A set of useful relations is given later
in this article. If we had only binary relations it would be easy
to introduce them as labelled connections between the objects.
But here it makes more sense to introduce new nodes into the
graph which are treated the same way like the nodes introduced
for the objects. They are labelled with a class and a name,
where the name does not refer to something real but is needed
to identify this relation in a unique way. The difference to
ordinary objects is that edges are introduced into the graph
which connect the relation node with all the object nodes which
are subject of the relation. for an example see Figure 4.
Et
"a ~
OBJ OBJ OBJ
NN pa x /
E REL
F4
OBJ
Figure 4: Conceptual Graph.
In some cases the border between objects and relations
disappears and an object is also a relation. An example are road
segments. A road segment is a real object but it always has the
connection to a node of the road graph like a junction or a sharp
bend which would require an explicit relation between the road
segment and the road graph node. This can be simplified by
treating the road segment like a relation and directly connect its
node to the junction object node.
As a result we have one single connected graph of concepts for
the reference data and one single connected graph for the sketch
data. This representation is very basic and several different
algorithms can use it for certain tasks.
3.2 Matching algorithms
With the graph representation it is possible to find an algorithm
that identified the pattern graph inside the reference graph.
There is a lot of literature about algorithms dealing with sub
graph isomorphism, but some essential properties are shown
here. An algorithm is detailed more in depth in this section. In
(Bengoetxea, 2002) an overview of matching concepts is given.
Two cases have to be considered. Traditionally a sub graph
isomorphism implicates the exact match between the pattern
and a subset of the reference. Every node must satisfy all
constraints including all connections between the nodes. This is
simple to describe but it was proved that this task is NP-
complete and the complexity of any algorithm is growing
exponential with the number of nodes in the graph except for
some special cases. One example for exact graph matching is
the algorithm of (Ullmann, 1976).
The second case is dealing with error tolerant methods and
mostly called inexact graph matching. For this case the NP-
completeness has been proven too and its complexity is of a
greater order than in the exact case.
Nonetheless or because of this fact a lot of approaches have
been developed to solve this problem, like statistical analysis of
the structure, evolutionary algorithms or exploitation of
geometric distribution of graph parts.
The simplest approach is to apply an exhaustive tree search to
the possible assignments of the graph nodes to each other. With
the additional information of classes and names at the nodes the
search space remains small enough to provide a quick search
for identical sub graphs. This is the VF-Algorithm described by
(Cordella, 2001) with some slight modifications.
The algorithms starts with a given node of the pattern, which
should be a very unique one, in order to test the most promising
matching pairs first. Then it tries the following for every node
in the reference graph with the same class and name: Îterate
through all nodes and edges of the pattern graph with a depth
first search. For every node try to match the pattern node with
the actual reference node or for every edge iterate through all
open edges of the reference graph and make the next connected
node the actual node. If the nodes match, save this assignment
and push all unassigned edges in the reference connected to the
node to the list of open edges. If the nodes don't match or no
open edge can be found, backtrack to the last saved state. Do
the backtracking too when no open edges or nodes are left. A
solution is found when all nodes are assigned.
i beh 4 - |
Figure 5: The region of assigned nodes (dotted) is growing,
while potential assignments are evaluated (dashed).
Interna
In Fig
actuall
This is
the dej
backtre
actual
actual i
This al
the alg
least fi
One dr
is theo
the ass
branch
Each o
and ba
is reac
enorme
and na
found i
Other |
by usir
Anothe
contair
constrt
Some
geome
project
pattern
into thi
tight c
This aj
matchi
similar
up ton
The la:
graphs
NOW SC
The ba
definiti
This se
to des:
leaves
data. C
only pl
geome
source
objects
geome
