International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
C
M
C
Ci ©
| | |
ISEC---ROAD---ISEC---ROAD---TSEC
ROAD
ISEC---CÍ
Figure 8: Cardinal relations.
A special case is the C2 relation which includes more
information than the other cardinalities. To reflect the existence
of an inflection point it should be called the INF relation.
If more than two road segments meet at an intersection, it is
interesting to know if any pair of roads is a straight
continuation of each other or if the pair is orthogonal. This
situation is very common in cities and essential for orientation.
Such a relation can be detected by comparing the direction of
road segments. In the real world the conditions must be relaxed
because a straight road remains a straight road if a small error is
present in the angle between the road segments. Both relations
refer to the ROAD concepts for which the property holds true.
The notation of the straight relation is STR while the notation
of the orthogonal relation is ORTH. Their use is shown here
(Figure 9):
ISEC
|
ROAD
|
ISEC---ROAD---ISEC---ROAD---ISEC
| | |
------- STR------
(ORTH)
Figure 9: Straight / Orthogonal relation.
4.3 Sequential relations
In some situations natural sequences are formed by objects and
the sequence is of a special type. In this cases always a
predecessor and a successor object exists which can be marked
by the PRED and SUCC relations. They are used together and
each of them links to the ordered concept OBJ. The type is
determined by another relation REL which is linked between
the PRED and SUCC concepts. The principle is shown in
Figure 10.
OBJ---PRED---REL---SUCC---OBJ
Figure 10: Sequential relations (REL) between two objects
(OBJ).
This kind of construction is needed for junctions where the road
segments are ordered by their direction around the central
intersection. In the graph it would not be possible to reconstruct
the sequence of road segments because the direction
information is lost. But the sequential order of roads is a very
strong constraint for a junction. Here another relation with the
name ORD can be introduced (Figure 11). Then it is not
possible to generate ambiguously directed junctions.
STR
SUGCE-TZORD---—PRED
{ i
ISEC---ROAD---ISEC-TCRORBD---ISEGC
| l
PRED | SUCC
i i
ACC----ORD | ORD---OBT
SOQOT--—-ROADCoTTUPRED
ISEC
Figure 11: Ordered road segments.
This construction does not require any special angle between
the roads. If this restriction is wanted the STR and ORTH
relations can be used and for obtuse angles and acute angles the
relations OBT and ACC will fit. They should all four have a
single link to the ORD node (Figure 12).
Sue —cORD PRED
| | |
LlSECT-CROAD--—LSÉC-rznOAD--ISEC
| | |
PRED | suce
| | |
ORD | ORD
| | |
SUCC-—--ROAD--——PRED
|
ISEC
Figure 12: More restricted ordered road segments.
Because the sketch is not an exact projection of real objects this
will need an error tolerant algorithm for the matching process
where wrong relations are accepted until a limit of errors is
reached. The direction constraints are defined here with exactly
separating angle values but this hard cut does not reflect reality.
4.4 Non-Road objects
This section concentrated on road networks because they are a
vital component in most situations. But there are of course more
objects than roads which are important too. Depending on the
type of the objects new relations can be defined. The most
important is the neighbourhood relation which is connecting
two objects. If the neighbourhood is found in the reference it
can be expected that it is preserved in the sketch. The
consequences of using this relation have not been analyzed yet
but the 9-intersection of (Egenhofer, 1991) is a good foundation
for working out a suitable set of relations.
5. CONVERTING DATA
The matching process requires the transformation of reference
data and sketch data to a graph representation. The sketch must
be processed on the fly in the context of the search engine but
the reference data can be pre-processed. So there is no need to
do all the conversions in real time which is impossible on
available hardware. The sketch data is usually small enough for
online processing.
Actually the data is taken from ESRI shape files where it is
organized as simple features in distinct layers for every feature
type. The layers with the relevant information can be selected
Internati
Je ner
and a tr
constrair
lines of t
The triai
data pro
structure
topologit
For the
answer r
geometri
Neighbo
delaunay
extractec
itself or :
The sket
before th
which in
is not su
The rec
simple sl
very Wi
immedia
have no
tolerant 1
Another
matching
data pro
size of t
some po
or anoth
producec
interestii
The corr
target ai
largest c
nodes.
Fig
This art
be solve
of prod
objects :
The sket
it to gra
