33. Istanbul 2004
is,
al angle between
STR and ORTH
| acute angles the
d all four have a
segments.
f real objects this
matching process
imit of errors is
here with exactly
ot reflect reality.
ecause they are a
re of course more
)epending on the
fined. The most
ch is connecting
1 the reference it
the sketch. The
cen analyzed yet
good foundation
tion of reference
The sketch must
search engine but
ere is no need to
is impossible on
small enough for
files where it is
for every feature
1 can be selected
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
and a triangulation is performed on the geometry. Here the
constrained delaunay triangulation is a good choice because
lines of the data become edges of the triangulation.
The triangulation produces a topological representation of the
data projected to one single plane and if a topological data
structure is used it supports the efficient extraction. of
topological constraints.
For the case of the road network simple edge tracing can
answer most of the questions directly or with some additional
geometric calculations on local elements of the triangulation.
Neighbourhood is an inherent part of the definition of the
delaunay triangulations and voronoi diagrams. It can be
extracted from the edges by checking the features on the edge
itself or at the connected nodes of the edge.
The sketch data needs a reconstruction of the contained objects
before the conversion to the graph representation can be started,
which involves another pattern matching process. This process
is not subject of this article.
6. TESTING
The recognition of a sketched position was tested with some
simple sketches and for the case of exact matching it performed
very well. If the exact solution existed it was found
immediately within a second. For bigger patterns it is likely to
have no exact matching location in the reference and error
tolerant matching algorithms must be applied.
Another tested application of the matching algorithm was the
matching of two road networks from the same area but different
data providers. Here the geometry is not very distorted but the
size of the pattern has the same size like the reference and at
some points there are missing roads, missing inflection points
or another shape of the road. The area shown in Figure 13
produced two graphs with the size of approx. 570 nodes. An
interesting test was the matching of the road network to itself.
The correct solution was found immediately. When using both
target and destination, no solution could be found but the
largest common sub graph has 55 Nodes of correctly assigned
nodes.
i
)
/ b
N RA
[Li
Je Lo
en
J
t
E
/
Figure 13: Test area for matching of two road graphs.
7. CONCLUSIONS AND FUTURE WORK
This article showed how the location of a spatial situation can
be solved with a sketch as a pattern. This offers the possibility
of producing abstract queries where only relations of the
objects are defined but not the objects themselves.
The sketch is compared to a reference data set by transforming
it to graph structure which is a an explicit representation of the
implicit knowledge important for the matching process. A set of
classes which are needed for this representation is developed.
The matching process does implement exact graph matching at
this time and is very quick if no errors are in the data. Inexact
graph matching is still under development and needs further
investigations on the exploitable information to find suitable
heuristics which are fast enough. The literature shows some
example in other applications comparable with the complexity
of the problem discussed here. The success of their solutions
should be transferable to the sketch matching problem. The
future work will also concentrate on investigating to which
degree the geometric constraints can be introduced into the
search procedure.
8. REFERENCES
Bengoetxea, E., 2002. Inexact Graph
Estimation of Distribution Algorithms.
France.
Matching Using
Dissertation, Paris,
Blaser, A., 1998, Geo-Spatial Sketches. Technical Report,
National Center of Geographic Information and Analysis,
University of Maine, Orono, Maine, USA.
Blaser, A., 2000. Sketching Spatial Queries. Dissertation, The
Graduate School, University of Maine, Orono, Maine, USA.
Cordella, L.P., Foggia, P., Sansone, C., Vento, M., 2001. An
Improved Algorithm for Matching Large Graphs. Proc. of the
3" JAPR TC-15 Workshop on Graph-based Representations in
Pattern Recognition, Ischia, May 2001, p. 149-159.
Cortadella, J., Valiente, G., 2000. A Relational View of
Subgraph Isomorphism. Proc. Fifth International Seminar on
Relational Methods in Computer Science, 2000, pp.45-54.
1991. Point-Set Topological
Journal of Geographical
Egenhofer, M.J., Franzosa, R.D.,
Spatial Relations. International
Information Systems 5, pp. 161-174.
Jones, C.B. et al, 2002. Spatial Information Retrieval and
Geographical Ontologies : An Overview of the SPIRIT project.
SIGIR 2002: Proceedings of the 25% Annual International ACM
SIGIR Conference on Research and Development in
Information Retrieval, 2002, pp. 387-388.
Lee, R.S.T., Liu, J.N.K., 2002. An Automatic Tropical Cyclone
Pattern Recognition and Classification System using Composite
Neural Oscillatory-based EGDLM. International Journal of
Fuzzy Systems, Vol. 4, No. 1, 2002.
Lipschutz, S., 1976. Discrete Mathematics. McGraw-Hill, New
York, pp. 89-90.
Sowa, F., 2001. Conceptual Graphs, ISO standard, Reference:
ISO/JJTCI/SC 32/WG2 N 000.
Ullmann, J.R., 1976. An Algorithm for Subgraph Isomorphism.
Journal of the ACM (JACM), Vol. 23, Issue 1, pp. 31-42.
9. ACKNOWLEDGEMENTS
This work is part of the project SPIRIT (Spatially-Aware
Retrieval on the Internet) IST-2001-35047 which is funded by
the EU.
