Indoor Navigation with SVG

Keywords: SVG, positioning technologies, mobility, navigation, guiding system

Christian Schmitt
Researcher
Fraunhofer FIT
Schloss Birlinghoven
Sankt-Augustin

Germany
christian.schmitt@fit.fraunhofer.de

Oliver Kaufmann
Fraunhofer FIT
Schloss Birlinghoven
Sankt-Augustin

Germany
oliver.kaufmann@fit.fraunhofer.de


Abstract


This paper describes a mobile guide providing office building visitors with indoor navigation aid. The guide is implementing using a combination of several indoor positioning systems and a SVG-based map viewer for an interactive map visualisation. A combination of several positioning systems is necessary because there is no single technology that can satisfy the system requirements with regard to accuracy and costs. The SVG map viewer is implemented using the BitFlash SVG SDK, allowing us to gain full control over the processing and rendering of the SVG maps as well as to obtain notifications for the user interactions with the map. To enable efficient reuse in follow-up projects, we have developed several helper tools. The toolset includes components like an SVG map generator and a path-finding module.


Table of Contents


1. Introduction
2. Indoor Navigation Overview
     2.1 Infrared Technology
     2.2 Radio frequency technologies (RF)
          2.2.1 Wireless LAN by Ekahau
          2.2.2 Ultra Wide Band (UWB)
     2.3 Other technologies
3. Helper tools
     3.1 SVG map generator
     3.2 Pathfinding module
4. Map viewer and navigation
     4.1 The good combination
     4.2 BitFlash player
     4.3 SVG Map and Navigation
     4.4 Integration of positioning technologies
          4.4.1 Infrared
          4.4.2 Ekahau/Ubisense
     4.5 The ICON Guide
5. Conclusion and future work
Bibliography

1. Introduction

FIT has a long history in developing mobile guides for museums, fairs, symposiums. In the HIPS project ([1]) we developed a mobile guide for the castle situated in our campus. Infrared emitters attached to pictures exhibited in the castle were used to locate the user and generate personalized tours or navigation hints. In 2003 we developed a mobile guide for our Open Day. The visitors were mostly impressed by the user tracking and the new opportunities offered by indoor localization and visualisation of objects of interest. In the SAiMotion project we developed a mobile guide for the CeBIT fair, using a combination of infrared and radio-frequency positioning system. From this experience, we began to make a first prototype of a mobile guide for our institute ([18]) and to lay down the foundation of this work

Our mobile guide was developed with the aim to be used for demo purposes by visitors to our institute, for demonstrating our expertise in mobile computing, positioning technologies and human-computer interface. Other related projects include the NAVIO Project ([19]) and the Niccimon platform ([20]). The requirements for our prototype were:

Presenting information can be easily achieved by integrating functionalities from the Pocket Internet Explorer in the application and having the content available as HTML pages. Indoor navigation implies following components to be available:

In this paper we will present different positioning technologies and describe why and how they were integrated into our mobile navigation system. We will also present helper tools that were developed with the aim to speed up the development of large projects. Then we will have a close look to the map viewer and however the indoor navigations features were implemented in SVG

2. Indoor Navigation Overview

Without a reliable existing positioning system, navigation is not possible. Therefore a careful investigation about the existing technologies, their advantages and limitations, is needed. There are numerous technologies available for user tracking

2.1 Infrared Technology

The infrared technology is inexpensive and available on a broad palette of mobile devices ranging from PDAs, mobile phones to notebooks. Therefore, many IR-based guiding systems have been designed ([1], [6], [7] and [13]). To properly work, there must be a line of sight between the IR emitter and receiver (directed communication) and no strong lighting. Since the range of an emitter is about a few meters, depending of the battery power and number of embedded LED, it is a relatively precise technology

Unfortunately, it is very hard to setup and maintain such a positioning system on a large scale, because many emitters have to be installed and batteries changed from time to time. Rather, it is possible to use IR in specific places, like points of interest or areas where other technologies are not working adequately

We are experimenting with hardware from two vendors: Eyeled GmbH and GuideID. The Eyeled IR emitters have a range of 2 meters but are bigger than the emitter from GuideID with a range of 80-100cm

2.2 Radio frequency technologies (RF)

Radio Frequency based systems ([2], [3], [4], [5] and [14]) are also widely used because they overcome many of the disadvantages of IR. The signals are able to pass through walls and obstacles, thus having a better coverage and therefore requiring less RF receivers to setup a whole building. Drawbacks are higher power consumption and no directed communication. In addition, the frequency ranges are usually licensed. Systems with high precision (~10-30 cm) use Time Difference of Arrival (TDOA) or Angle of Arrival (AOA) but require a synchronization of the receivers (base stations). The disadvantage of those systems is their price. Systems relying on the signal strength measurements (fingerprints) are less complicate and therefore cheaper, but also less accurate (~1-3 m)

A good practice is to use a combination of RF-based technologies having different accuracies. In our case, we opted for WLAN and Ultra Wide Band (UWB) positioning. With the WLAN solution by Ekahau ([8]), we could cover the whole floor at not extra cost, just by using the existing infrastructure. The average accuracy of 3 meters is sufficient in many cases. UWB was chosen because it is a promising and very precise technology. Since it is more costly and requires dedicated hardware, we selected a demonstration room where we installed the UWB solution from Ubisense ([9]) In the following two sections we will describe in more details both solutions.

2.2.1 Wireless LAN by Ekahau

WLAN Positioning uses the signal strength of the access points in the neighbourhood to calculate the position. There are two main approaches to determine the position. The empirical model is based on comparing the current signal strength readings to a database of pre-recorded measurements. A calibration phase creating a radio map has to be performed, before the system can be used. The second approach is called the propagation model and is based on mathematical equations describing the degradation of the signal strength of a radio wave in space. Using these propagation equations an approximate distance from the WLAN card to the access point can be computed and through triangulation an absolute position. The Ekahau solution is based on the empirical model

The Finnish company Ekahau has developed a 100% software based positioning system that can use the existing WLAN infrastructure for positioning, making this solution very cheap and flexible. To be tracked, a device has to run a small application (Ekahau Client) that reads and forwards the signal strength measurements to the Ekahau Positioning Engine (EPE), responsible for gathering the fingerprints from the mobile devices and computing their position. The company offers also WiFi tags to track devices or persons that do not have a build-in WLAN card

The position information (X-Y coordinates, heading and speed) about any connected device can be queried from the EPE using either the Ekahau SDK (requires Java 1.4 support) or using a socket-based proprietary protocol called Yax (for devices without 1.4 support, like most PDAs and mobile phones). In the phase of development of our prototype, Yax was not yet available, therefore a similar protocol had to be designed to let the PDA access its position. Mobile devices use this protocol to interact with a middleware server written in Java and connected to the Positioning Engine through the SDK. A location thread running on the PDA connects to the middleware server via sockets and gets notified of new position information

2.2.2 Ultra Wide Band (UWB)

Multipath distortion caused by radio signals being reflected from walls or people is a big issue in RF positioning and a source of inaccuracy. Thanks to the short duration of UWB pulses, it is possible to filter the reflected signals from the original signal, thus resulting in higher accuracy, about 15 cm. To be tracked, the user must wear a registered UWB tag. The installation of the Ubisense system for a single room (also called a cell) consists of four sensor units mounted at the corners and a control unit. The sensor units timestamp the signals from all tags present in the cell and forward them to the control unit that computes the position of the tags using TDOA and AOA. The 3D position of the devices can be retrieved via a C++/COM API. Using a Java-COM-Bridge, the Ubisense positioning can be integrated into the WLAN middleware server (see S 2.2.1).

2.3 Other technologies

There is also a range of optic systems based on image processing. The idea of those systems is to mimic the capabilities of the human eye and brain. Through edge detection or object identification from the raw image and comparison with an image-database it is possible to compute the distance to well-known objects and hence the absolute position of the camera. But image processing is a very CPU-intensive task and requires a very precise camera, making those systems very expensive (with high-precision cameras and dedicated server for image processing) or not precise enough (with low-budget cameras and mobile image processing.

In the recent years, indoor GPS got increased interest but there are still technical obstacles. Also, RFID-based positioning is starting replacing IR. ([15])

3. Helper tools

3.1 SVG map generator

It is difficult to create SVG maps that can be viewed on any kind of device. There are many SVG-viewers available and there is no guarantee that all of these viewers can interpret and display every SVG element in your SVG file. The same map may have a totally different look on another device/viewer configuration. Maintaining different versions of the same map is not a satisfying solution. Of course it is possible to use a complete GIS database, together with a server delivering maps adapted to the configuration of the mobile device. We rather needed a simple, easy to use solution, since we were interested in the design of room plans, not complex cartographic data. For this purpose, we wrote a special DTD modelling common concepts like rooms of different shape and function (offices, kitchen, etc), doors, entrances, special objects like fire drenchers, among others. The DTD can be easily extended with access rights and path-finding related properties. To ease the creation of a new room plan, we made a custom editor in java. This editor allows to define new room plan objects and to preview the outcome in SVG (using Batik as renderer). XSLT stylesheets, available for the different configurations, are used to convert the XML file of a room plane in the desired SVG version. To support a new configuration, only a new XSLT file has to be written. However, XSLT scripting functionalities are limited. For a greater control over the generation of the map it is advisory to use Batik.

Below is a screenshot of the application

roomPlaner1.gif

Figure 1: The SVG map generator

3.2 Pathfinding module

Navigation software should offer the possibility to generate a route from the current position (or any other point) to any destination. Web-based GIS applications are computing the route on the server while also generating the map

We wanted the pathfinding algorithm to be available on the client, in case there is no network connection. The pathfinding algorithm is based on the well-known A* algorithm, already used in computer games. It was implemented using the STL library, made available to C++ developers with the release of Windows CE .NET. Hence, it is not working with devices running Pocket PC 2002. A* is a graph search algorithm that finds a path from a given start node to a given goal node. Using a certain heuristic function it is possible to find, in reasonably short time, the shortest path between the start and goal nodes. The A* algorithm can be used for pathfinding by introducing the concept of travelling cost via an edge of the graph, defined by the euclidien distance between the two extremities of an edge

To ease the creation of such a graph, a custom editor has been implemented that allows the drawing of the graph "over" the corresponding map. The nodes can be moved around and should be placed at typical waypoints or destinations like doors, entrances, in the middle of offices. The graph can be saved as a text file and copied to the mobile device where it will be processed by the mobile guide

overlayEditor.gif

Figure 2: The tool used to create the graph for the pathfinding module

In the current version of the pathfinding module, a node is defined by a unique name, the coordinates on the map (in pixels), the list of neighbouring nodes and a user-friendly name. The user-friendly name is used for interactions with the user, e.g. to present the list of available destinations. It is also used to identify artificial nodes, whose solely purpose is to provide a realistic and smooth painting of the optimal path

An extension of the pathfinding module is in progress, in order to support the generation of routes adapted to the user preferences. The user acceptance will be greatly improved, as for example wheelchair-bound users will get routes giving the preference to lifts rather than stairs. To do so, the graph will incorporate metadata about nodes and edges, like physical properties (lift or stairs) or security aspects (access rights to open a door). Only the accessible part of the graph will be used for the pathfinding

4. Map viewer and navigation

It is not sufficient to be able to track down the position of the user - it is also important to display it on the mobile device in an understandable, appealing way. In addition to the position, it is also very helpful to be able to visualize the optimal route to a destination

The map viewer should provide the following functionalities:

4.1 The good combination

Our first implementation was a personal java application rendering a raster bitmap and supporting zoom in/out, manual or automatic scrolling on the current position. This solution suffered from several drawbacks. First, raster bitmaps do not render nicely when zooming in/out. Second they use a lot of space in memory in the already resources limited PDAs. Furthermore, Java applications do not have rich user interfaces and are not make optimal use of the limited resources of PDAs. Finally, it is hard to access hardware resources in Java, among others the IR port or the WLAN card

Using these lessons we moved onto a more ambitious project relying on SVG and Visual C++ for Pocket PC 2003. By using the C++ we could improve the overall performance while getting more control over the device (support for hardware buttons, Internet Explorer and Media Player ActiveX controls). The user interface could be designed more user-friendly because operating system widgets could be used, making sure that the user can interact in a familiar interface. SVG is the perfect match for mobile navigation. SVG maps have a smaller footprint than bitmaps and will render a map at any scale without any loss of detail. Support for animation, symbols, linking to other web pages and last but not least scripting functionality makes it possible to write powerful cartographic applications ([16], [17])

There are only two native C++ viewers implementing SVG Basic under windows CE, BitFlash [11] and eSVG [12]. We wanted the C++ application to be notified of user interaction with the SVG map (clicks, zooming, etc) in order to start the Pocket Internet Explorer in case of a POI being clicked, for example. In April 2003, only the eSVG player offered such a functionality, via the use of callback functions (16 such user-defined methods can be defined). It was necessary to append the text onclick="number between 1 and 16" on every SVG element we were interested in knowing the user clicked on it. The eSVG player (version 1.4) was somewhat slow to render the SVG map, especially when the map was panned. This was a great source of complain from users. Also, the limitation to 16 such callback events would have become an issue in the future

During Spring 2004 we acquired a license for the newly released BitFlash SDK that allowed us to have much more control over the SVG viewer and the DOM document than by using an ActiveX control. Moreover, the BitFlash player is pretty fast and has not refresh issue when panning the map. In the next sections we will show how the BitFlash Player, the SVG map of the floor and the positioning technologies were put together to provide indoor navigation support

4.2 BitFlash player

The BitFlash SDK provides a set of header files and some DLLs that contain the interface and implementation for the player functionalities and the DOM model. For the C++ application, the entry point of the SDK is an object of the BFPlayer class. Through this object, it is possible to send commands to the player (reload, repaint, pane, zoom, etc) as well as getting notification about user interactions (clicks, links activated, etc). It is also possible to have access to the underlying DOM object model and to register listeners for DOM events, for the case the application should support animations

For example, to change the zoom factor of the map the following code can be applied:

zoomCode.gif

Figure 3:

It is important to notice that the DOM document cannot be accessed by more than one thread at the same time. There are several cases where this can happen. For example, when the user is interacting with the map (by zooming or panning) while the positioning component is trying to update the position of the user on the map after new position is available, or when the application wants to trigger an animation after the user came in front of an IR emitter. By using a semaphore for the DOM document it is possible to synchronize the several threads

The SVG player has been embedded into a dialog window, so the C++ application can catch the pen clicks and forward the events to the SVG player, and also test if the user is interested in some information about an object on the map. This has been realized in SVG by defining the clickable object into a surrounding a tag, where the href attribute is a custom URL beginning with application, for the c++ application to know it should not interpret the link as an HTML link but as an task. For example, with the following extract from the SVG map, the user can click on an employee name and the application will open a new dialog window (not another SVG or HTML document) containing contact data of the employee

employeeTag.gif

Figure 4:

4.3 SVG Map and Navigation

In order to create the final map of the floor, we started to create a semantic description of the floor with the SVG map generator tool. The generated map was then used as a template for fine-tuning the visual appeal and the interaction with the c++ application

The map starts with the definition of several symbols: a flag for displaying the goal of a route (to be turned visible or not, at the right position, depending if a route is displayed or not), a buddy that represents the current position of the user, blinking infrared points, etc. Then, the ground level with the offices, doors, kitchen, and names for the employees. Finally, the symbols are instantiated with non visible status

The IR symbol is a nice animation built in a very simple way. It simply consists of two SVG-Circle-Elements and four triangles. The first circle is filled in red. The second circle only has a red outline. By using the SVG animate tag the attribute "r" of the second circle is animated so that the radius of this circle grows from value 6 to 33 in 0.5 sec. This animation is repeated permanently while the symbol is shown. Above these two circles four white triangles are placed. These triangles cover parts of the growing circle so that it looks like the first circle is emitting rays

The navigation support is pretty basic. The current position of the user is regularly updated on the map, as soon as new position is available on the positioning server. If the user wants to meet with someone or go to a specific place, he can click on navigation button located in the map viewer toolbar and will be offered a new dialog window where he can select a destination (by selecting the label of one of the graph's nodes). Then, the pathfinding module will find the graph node which is the closest to the current position and return the shortest route to the desired destination as a sequence of nodes. A blue SVG polyline representing the recommended route will be made visible and the points attribute set to the nodes coordinates. A thread recomputes the shortest route again and again, until the user arrives in the vicinity of his destination or stops the navigation by pressing again the navigation button

bluePath2.gif

Figure 5: The current position of the user (in green) and the shortest path to my office (in blue)

Of course, in a mobile situation it is not enough to provide only visual output, because a user should be able to get directions without looking at the map. Therefore, it will be part of future work to provide some basic directions, both as text sentences and audio output.

4.4 Integration of positioning technologies

4.4.1 Infrared

The IR port of the PDA is able to read the signals from the IR beacons. This is usually done by opening a serial communication port (COM-port). It is necessary to know the communication specification of the beacons (baud, parity bit, etc) in order to properly setup the communication port. At startup, a thread is created to open the port and wait for incoming data. Once the thread recognizes an ID stored in this database, it will start the animation of the corresponding IR symbol on the map and update the current position of the user

4.4.2 Ekahau/Ubisense

In the case of Ekahau and Ubisense, the current position of the users is computed and centralized on the server. Clients need to connect to the server via TCP/IP. Therefore, a location thread is created at startup to open a socket connection to the middleware server described in (see S 2.2.1). This server is configured to work with Ekahau and Ubisense, but not with both of them at the same time (no sensor fusion). The server forwards position information (as X-Y coordinates) to the thread as soon as new data is available and the thread updates the x-y attributes of the buddy on the map. Since the same floor map is used on the PDA for both Ekahau and Ubisense and the Ubisense installation is only available in one room, some additional conversion is needed on the PDA to get the absolute coordinates

A key factor in the success of the WLAN positioning is the rate at which new measurements of the signal strengths can be made. This is dependent to a great extend from the type of WLAN card and the driver. WLAN was not designed to be used for positioning purposes, therefore many cards are not built to allow a fast access to the signal strengths (some drivers even don’t allow you to access to all signal strengths).In particular, many PDA internal WLAN cards have a very bad scan speed, which means that an additional CF/SDIO WLAN card is usually needed to get a viable tracking of the device. A list of supported WLAN cards and their features can be found at http://www.ekahau.com/products/client/devices.html

4.5 The ICON Guide

iconguide.gif

Figure 6: The ICON Guide start page (left) and the details of an employee (right)

The ICON Guide can also be used for a conference like SVG Open. Information about employees (resp. projects and events) would be replaced by attendants (resp. papers/posters and the program of the conference). Most content is static HTML, which means that the information from the SVGOpen.net website could be converted without two much effort into a HTML layout suitable for the small screen of the PDA. Only the information about employees is stored as XML, so a new DTD would have to be created and the parsing to be updated on the PDA. Of course, a new SVG map would have to be written to match the floorplan of conference centre. Ekahau could be demonstrated if there is WLAN infrastructure on the floor. An access to the network is not needed because Ekahau is only listening to the signal strengths, not connecting to the access points. A peer-to-peer network between the server (notebook) and a PDA would be sufficient. Setting-up a demo would only require spending a few hours calibrating the area

5. Conclusion and future work

There are a lot of indoor positioning technologies available. None of them is suitable for every purpose. Rather, a smart combination of several technologies is required in order to get a reliable, precise and cost-effective tracking solution. WLAN, a per-square-meter cheap but of average accuracy positioning technology can be used for covering the whole area, while a more costly technology like UWB can be used for such smaller areas requiring higher accuracy. In addition, some IR beacons are perfect in such places where a directed communication is needed, typically points of interest or where other technologies are not properly working

It took some time for SVG to takeoff in the mobile world but now it is being supported by many mobile vendors, and the SVG viewers are being continuously improved, so there are good chances for SVG to be a key component in the expanding sector of mobile cartography.

Future work will focus on the improvement of the indoor navigation support, especially by offering audio-based directions and personalized routes. Another challenging issue is the seamless integration of Ubisense and Ekahau, the system being able to recognize the best positioning technology at any time. We also strive for setting up a server servicing personalized content to the mobile devices, like maps, routes and up-to-date informative data, instead of having the data stored locally on the device

Bibliography

[1]
R. Oppermann and M. Specht, A Context-sensitive Nomadic Information System as an Exhibition Guide, in Proceedings of the Handheld and Ubiquitous Computing Second International Symposium, HUC 2000, Bristol, UK, September 25-27, 2000, pp. 127 - 142
[2]
P. Bahl and V.N. Padmanabhan, RADAR: An in-building RF-based user location and tracking system, in Proceedings of IEEE Infocom 2000, March 2000, volume 2, pp. 775-784
[3]
R. Want et al., The Active Badge Location System, ACM Transactions on Information Systems, January 1992, pp. 91-92.
[4]
A.Ward, A. Jones, A. Hopper. A New Location Technique for the Active Office, in Proceedings of Mobicom '97, September 1997
[5]
N. Priyanatha, A. Chakraborty, and H. Balakrishnan, The Cricket location support system", in Proceedings of MOBICOM, Aug. 2000, pp. 32-43.
[6]
A. Butz, J. Baus, and A. Krüger, Augmenting buildings with infrared information, in Proceedings of the International Symposium on Augmented Reality, 2000
[7]
Eyeled GmbH, http://www.eyeled.de
[8]
Ekahau, http://www.ekahau.com
[9]
Ubisense, http://www.ubisense.net
[10]
S.D. Feller and al, Tracking and imaging humans on heterogeneous infrared sensor array for tactical applications, SPIE Aerosense 2002
[11]
BitFlash, http://www.bitflash.com
[12]
eSVG, http://www.embedding.net/eSVG/
[13]
guideID http://www.guideid.com
[14]
Sennheiser GuidePort, http://www.guideport.com
[15]
P. Tomberge and M. Raubal, Navigation mittels RFID - Untersuchung der Navigationsmöglichkeiten durch RFID-Eintrittskarten bei der Fussball-WM 2006, AGIT 2005 - Symposium und Fachmesse für angewandte Geoinformatik, Salzburg, Austria
[16]
T. Reichenbacher, SVG for adaptive visualisations in mobile situations. Proceedings of the SVG Open 2002
[17]
T. Reichenbacher, The World In Your Pocket - Towards A Mobile Cartography, in Proceedings of the 20th International Cartographic Conference, Beijing, China, August, 6 - 10, 2001
[18]
C. Schmitt, "Mobile guide for the enterprise", WPNC 2004
[19]
G. Gartner, A. Frank and G. Retscher, "Pedestrian Navigation System in Mixed Indoor/Outdoor Environment - The Navio Project", CORP 2004
[20]
J. Baldzer, S. Boll, P. Klante, J. Krösche, J. Meyer, N. Rump, A. Scherp, and H.J. Appelrath, Location-Aware Mobile Multimedia Applications on the Niccimon platform

XHTML rendition made possible by SchemaSoft's Document Interpreter™ technology.