Tm n = i zii 
  
REPRESENTATION OF SKETCH DATA FOR 
LOCALISATION IN LARGE DATA SETS 
M. Kopezynski, M. Sester 
Institute of Cartography and Geoinformatics, University of Hannover, AppelstraBe 9a, 
30167 Hannover, Germany —Matthias.Kopezynski@ikg.uni-hannover.de 
KEY WORDS: Analysis, Interpretation, Matching, Recognition, Query, Data Structures, Pattern, Reference Data 
ABSTRACT: 
Sketches are often used by humans to quickly give information about places or illustrate how to find a.way from A to B. Thus, 
sketches are an interesting technique of generating queries with the goal of finding unknown places matching the sketched 
constraints. This article proposes a graph based structure for the representation of the knowledge in the sketch and shows how this 
structure supports the matching process. A set of relation and object classes is developed to represent the sketch in an appropriate 
way, which implies preserving the topology in the sketch but neglects most of the exact geometric information. Some examples are 
shown and analyzed. 
1. INTRODUCTION 
Not a long time ago internet search engines were simple 
programs, dealing with masses of text input, regardless of the 
contents in the text. The search engine simply looked for a 
word, typed in by the user. But people are always interested in 
the contents and the search engine companies were forced to 
produce better results. One way to achieve this is to rank the 
results of the query by guessing what the user is interested in 
and what the page contents is about. 
A lot of the queries turn out to be either implicitly or explicitly 
related to space. Websites of shops are interesting when the 
shop is near the own location or tourist attractions should be on 
the same island where someone spends his holidays. Some 
search engine companies realized this and offered to restrict the 
query to an area, given by a country or by zip codes (e.g. 
Mirago: www.mirago.com and Google: www.google.com/dirhp 
or local.google.com). This can improve query results but is only 
a small part of what is possible. 
Much more than zip codes can be used to specify spatial 
queries. Examples are place names with a radius, a region 
name, any set theoretical combination of regions and so on. 
New ranking technologies are capable of presenting the most 
suitable results to the user. An ontology of places and regions 
can help while dealing with ambiguous names for the queries 
and can be extended to special domains, like tourism, to support 
combination with other context sensitive information. 
The SPIRIT project (Jones, 2002) is doing research on this 
techniques to design a powerful spatially aware search engine 
that really can answer spatially related queries in the internet. 
Conventional search engines are using simple text interfaces 
but there are better ways to create a query. An obvious 
approach for spatial queries is the use of maps where one can 
choose the region of interest, which is similar to the zip code 
approach but is easier to use because who knows the zip code 
of a holiday resort? This way of choosing a region is very 
simple but is restricted to single regions near a known place. 
A way to abandon this restrictions is to draw a sketch. If 
someone asks for the way, an explanation only using words can 
get very complicate and time consuming. Much more easy is to 
get some piece of paper and draw some lines representing 
important objects in space. This principle can be transferred to 
the search engine interface. Simply draw a sketch of the region 
you want to know something about. This is the way we are 
thinking about space and the advantage is that questions of an 
abstract level can be formulated. 
A sketching input tool is developed as part of the graphical user 
interface of the SPIRIT search engine. This article shows how 
sketches produced with it can answer the question for a 
sketched area. 
The paper is organized as follows: after an introduction into the 
nature of sketches and a prototype of a sketching tool, the 
representation of a sketch in terms of a graph is introduced, as 
well as matching techniques as means to match a sketch and a 
given representation. In section .4 the concepts needed for 
describing sketches are presented. The use of this structure is 
firstly applied to matching two road data sets. Finally, there is a 
conclusion and an outlook on further work. 
2. SKETCHES 
2.1 The structure of a sketch 
At first an overview about the anatomy of a sketch is given, 
because the term “sketch” can be used with several different 
meanings. Figure 1 is showing an example sketch. 
A 
Vectra fi 
A / be f, » 
i ^ pd 
) \ In sels v 
  
Figure 1: Sketch of a location in Hannover. 
Mainly a sketch is produced very quickly and uses only as few 
elements as possible to communicate the intended information. 
A line may become a representative of a road, and a rectangle 
  
   
  
   
  
  
   
   
   
  
  
  
  
  
  
   
   
  
   
   
   
  
  
   
  
   
    
    
   
   
     
   
     
    
    
   
   
  
  
   
   
  
   
   
   
   
  
  
   
   
   
  
   
  
  
  
    
   
   
   
   
    
  
Interna 
may re 
of a rai 
The lir 
represe 
people 
too gx 
Annota 
specific 
class. 
family” 
family” 
Using : 
meanin 
where . 
generic 
only tl 
type “1 
“churcl 
C 
As skel 
and in: 
think 
general 
and 
incomp 
a sketc 
certain 
à speci: 
Cc 
As me 
sketche 
space. 
map he 
for the 
frame i 
are no 
princip 
arbitrar 
We are 
becaus: 
names 
tracks) 
typical 
22 Sl 
Usually 
of drav 
suitable 
In the ¢ 
for gen 
piece o 
bean 
Tablet 
and a : 
needed