The urban environment

has to be displayed, the computation of the path
and the integration with the outdoor navigation service has to be transparent to
the user.
Objective and contribution
This project, titled ”Seamless indoor outdoor navigation service”, falls under the
theme of indoor navigation. It is carried out in the ITZ building. In this master thesis
project, we have proposed a modification of the odd-even numbering algorithm for
room identification, as the navigation is based on room numbers. The first part of
our contribution is the building multi-floor graph generation algorithm. Therefore,
it is interesting and useful for indoor navigation to integrate this graph to employ
it in different computations of the navigation process. The second and the most important path of our contribution is the seamless navigation algorithm which includes
the seamless multi-floor navigation, the seamless switch between the indoor and the
outdoor maps and the continuous display of the path between the indoor and the
2
1 Introduction
outdoor spaces. These contributions are made to achieve the objective of a seamless
navigation of the user either between rooms or between the building and the outdoor
space.
Master thesis outline
This master thesis report is structured in four main parts:
The first chapter : Represents an overview of the background information and the
state of the art related to the navigation field of research. We have firstly compared
the indoor and the outdoor environments, then, we have introduced the main parts
of a navigation service including optimal path finding algorithms, We have indoor
map types and elements, room numbering patterns, existing indoor graph generation
methods and indoor-outdoor navigation services and their limitations.
Through the second chapter, entitled ”Methods” we have detailed our contribution,
we have described the developed algorithms to meet the requirements of our project
named ITZ Maps.
The third chapter is an illustration of the implementation details of our work which
performs real experimentations and tests. We have also presented screenshots of the
different test cases.
Thereafter, in the fourth chapter, we have evaluated the performance of our application. We have discussed the results, we have checked how pretty have the preidentified objectives been achieved and if the research questions have been answered.
Finally, we have ended up with the conclusion of our work and the perspectives
opened to further upgrades and future work.

In this chapter, we are going to present the state of the art for the navigation system with a focus on the process of generating the graph. We are going to give a
definition of the overall service and we will explain some solutions concerning the
different steps to reach our goal: Displaying on a smartphone the path navigation
from a source to a destination inside and outside the building.
To the best of our knowledge, there is not yet a practical and efficient indoor map
graph for the navigation services and even there is no standard for indoor-outdoor
navigation [7]. So, we will give some existing solutions appeared in the literature and
their limitations.
2.1 Indoor and outdoor environments
Indoor environment represents almost buildings that are always composed by several floors. In each floor we always find rooms characterized by numbers (such as
offices, classrooms, etc) and connectors (such as corridors, doors, etc). Floors are connected via stairs and/or lifts, etc.
There are many types of buildings such as : academic institutions, hospitals, museums, shopping malls, hotels, restaurants, airports, public transport stations, etc. Each
one has a different structure. The bigger is the building the easier the pedestrian
gets lost [8]. The main problem with the indoor space is that there is no commonly
used map that ensures a continuous navigation inside the building and that is due
to the fact that the Global Positioning System (GPS) signal is highly attenuated when
penetrating into buildings [9], which makes the indoor navigation very challenging.
4
2 Background
However, in the outdoor environment, streets that are covered with road maps such
as Open Street Map (OSM) and Google Maps, facilitate pedestrian navigation in an
accurate way. The most used navigation tool is Google Maps [N1]. In addition, the
GPS signal is effective and accurate in determining the position with an error up to 5
meters [10]. Which makes OSM and Google Maps standards for outdoor navigation.
2.2 Location-based services (LBS)
LBS is a software-level service that uses location data to control features. As such
LBS is an information service and has a number of uses in social networking today
as information, in entertainment or security, which is accessible with mobile devices
through the mobile network and which uses information on the geographical position
of the mobile device.
LBS include services to identify a location of a person or object, display the path to
help pedestrians to navigate indoors and outdoors and they also keep further useful
information related to the movement of the mobile (like distance and duration, travel
speed, estimated time of arrival, etc) in the guidance process if it is possible [11].
An LBS has three parts:
• Positioning
• Path finding
• Tracking and guidance.
2.2.1 Positioning
Indoor LBS are multiple such as positioning services which take advantage of the
existing technologies and they use measurement techniques to improve the precision
of positioning a mobile device (smartphone, tablet, laptop).
In fact, one of the most important criteria for indoor geolocation is the accurracy .
Indeed, unlike outdoor navigation, geolocation inside a multi-floor building must
integrate the dimension and the size of the space. If there are several small spaces
5
2 Background
(rooms, corridors, etc), the system allowing indoor positioning must allow a fine localization to be able to easily distinguish the different spaces.
The position of a mobile unit is defined by both :
• Spatial location, estimated with respect to a reference point.
• Direction, estimated with respect to a referencing system.
These two parameters are coupled but practically they have relatively distinct statuses. In 2D, to identify an object position, we have to talk about its coordinates
namely the latitude and the longitude.
The latitude
The latitude of a point on the Earth corresponds to the angular distance which separates this point from the equator. Latitude is an angular measure; it varies between
0° at the equator and 90° at the poles.
The longitude
The longitude is a geographic coordinate that allows, when given with latitude, to
determine the position of a point on the globe. Longitude is the angle of the plane
passing through the meridian of the point in question with the plane passing through
the meridian of origin, that is, the meridian of Greenwich (United Kingdom). Longitude therefore defines the east/west position of a point [12].
The figure 2.1 shows the latitude and longitude values.
6
2 Background
Figure 2.1: Latitude and longitude lines [N2] Positioning technologies
Outdoor navigation services can efficiently use the Global Navigation Satellite System (GNSS) to determine the location of the user accurately. GNSS is a set of components based on a constellation of satellites to provide a user, via a small mobile receiver, with his/her 3D position, speed and time. This category of a geo-positioning
system is characterized by a universal coverage. It includes GPS, GLONASS, Galileo,
Beidou, etc. Using this technology, difficulties will appear as soon as there are signal
attenuation, obstacles and multiple reflections. Thus the reason for not considering
only GNSS indoors.
There are two groups of positioning technologies : Radio Frequency (RF) positioning technologies such as GNSS, WiFi, Ultra wideband (UWB) and sensors based positioning technologies (Micro-Electro-Mechanical Systems (MEMS), Inertial Navigation Sensors (INS)).
Most of indoor systems use a combination of infrastructure-based systems and autonomous systems.
Furthemore, autonomous location systems do not rely on pre-existing installations
7
2 Background
Figure 2.2: Sensors in the smartphone [N2].
in the space or the pedestrian movement, but from the equipment that he/she takes
such as the MEMS, the Assisted GPS (AGPS) and the camera (figure 2.2) [13].
For example, we cite the following sensors :
• The Gyroscope : It gives the angular position and it is used to determine the
orientation of the user.
• The Accelerometer : It gives the acceleration and it is used to estimate the velocity.
• The Barometer : It measures the atmospheric pressure and it is used to know
the altitude of the user.
• The Compass : It gets directions i.e. North, East, West and South and it is used
for navigation.
Positioning techniques
The positioning techniques mostly used for detecting and measuring the position of
a mobile are multiple. As examples : The localization by Time of Arrival (ToA), localization by time difference of arrival (TDoA), location by Received Signal Strength
Indicator (RSSI), localization by measure Angle, location by fingerprinting and Pedestrian Dead Reckoning (PDR) [14].
8
2 Background
• RSSI Fingerprinting : This technique is used with the WiFi technology and consists of storing the different RSSI values and estimating the current position by
applying some algorithms.
• PDR : It extracts data from the MEMS sensors and estimates the current position
by calculating the number of steps taken by the user and his/her orientation in
the movement.
The important technological challenge is that pedestrian movements are not predictable like cars in roads. Today, a fusion approach combining WiFi-based, pedestrian dead reckoning (PDR) and INS techniques are drawing more and more attention
of researchers and try to ameliorate the accuracy in the position resolution [14].
2.2.2 Path finding
Path finding is the core process of the navigation service. It is a problem of graph
theory that is more generally related to the field of planning and finding a solution. It
consists in finding how to move inside an environment between a starting point and
a destination point taking into account different constraints. Initially, a path finding
problem can be reduced to a problem of finding the best path between two nodes in
a graph. There is a set of classical algorithms to solve this type of problem. However,
path finding becomes a complex problem when one tries to take into account various
additional constraints (real-time execution, presence of uncertainties, resource constraint, evolutionary environment, etc). So, the first step to resolve the path finding
problem is to provide an accurate graph that contains all kinds of constraints.
Optimal path calculation
Navigation is almost based on graph theory and a route planning algorithm. The
goal is to calculate a path between two vertices of a graph such that the sum of the
weights of its constituent edges is minimized.
The weight is a numerical value, assigned as a label to a vertex or edge of a graph.
It can be distance, time or a combination of more than two parameters. This value
can be calculated depending on the problem to be solved. Also, this value can be
9
2 Background
modified dynamically. The weight in the context of indoor-outdoor navigation can
be distance and/or time.
There are two groups of route planning algorithms : static algorithms (Dijkistra,
Bellman-Ford-Moore, A, etc) and dynamic algorithms (A*, D* and D* Lite, etc).
Static algorithms
The optimal path between a source and a destination is calculated and displayed
before starting the navigation and without monitoring the changing behaviour of the
mobile user. So, also if he/she deviates from the planned path, nothing happening
and the same path still displayed. As examples of static algorithms, we can find
Dijkstra and Bellman-Ford-Moore.
• Dijkstra : It is proposed by Edgser Wybe Dijkstra in 1959 and it is suitable for
cases where there is only one source node and one or more destination nodes.
Each time during the loop, the algorithm selects a node that has the minimum
cost from the source node. This node has been visited by the source and not
yet optimized. This node is then marked as optimized and the costs of all adjacent nodes will be evaluated. The optimal path is deduced when the algorithm
reaches the destination nodes. The complexity of this algorithm in the worstcase is : O( | E | + | V | log | V | ) with | E | is the number of edges and | V |
is the number of vertices [15].
• Bellman-Ford-Moore : The algorithm bears the names of its inventors Richard
Bellman, Lester Randolph Ford Junior (publications in 1956 and 1958) and Edward Forrest Moore who rediscovered it in 1959. Like Dijkstra, It computes the
shortest paths from a source node to all of the other nodes in a weighted graph.
Compared to Dijkstra’s algorithm, it is slower for the same problem, but it is
more versatile, because it is capable of handling graphs in which some of the
edge weights are negative numbers. In our problem, we do not need this functionality. The complexity of this algorithm in the worst-case is : O(| E | | V | )
with | E | is the number of edges and | V | is the number of vertices [16].
One of the objectives of our work, is to use a dynamic routing algorithm.

Dynamic algorithms
The calculation of the optimal path from the source to the destination uses a controlling mechanism through the navigation process; if the traveled path differs from
the displayed one, then a new path from the current position of the user to the final
destination will be calculated and displayed.
• A* : This algorithm was first proposed by Peter E. Hart, Nils John Nilsson and
Bertram Raphael in 1968. It is a path searching algorithm on a graph between
an initial and an end node. It uses a heuristic evaluation on each node to estimate the best path passing through it, and then visits the nodes in order of
this heuristic evaluation. In each node n, the algorithm selects the path that
minimizesf(n) = g(n) + h(n) with g(n) is the cost from the source node to n
and h(n) is the heuristic that estimates the cost from n to the destination node.
Thus, The algorithm A* was created so that the first solution found is one of the
optimal solutions. The best application of this algorithm is video games [17].
• D* : The algorithm, proposed by Anthony Stentz, makes assumptions about the
unknown part of the space and finds a shortest path from the current coordinates of the user to the coordinates of the goal according to these assumptions.
When observing a new map information (such as obstacles), this information
should be added to the map and, if necessary, a new shortest path from the current coordinates of the user to the coordinates of the given goal rescheduled.
This process must be repeated until it reaches the coordinates of the goal or
determines that the coordinates of the goal have not been reached. The best
application of the algorithm is robot navigation in an unfamiliar terrain [18].
• D* Lite : It is among the most used routing algorithms by the actual navigation
services. It is a heuristic incremental search algorithm proposed by Sven Koenig
and Maxim Likhachev in 2002. It is a modified version of A* and it is suitable for
cases where there is only one known source node, one known destination node
and an unknown space in which a robot can navigate. The space is modeled by a
grid composed of nodes where the initial cost is one and the position of the robot
is surrounded by eight boxes. The initial hypothesis is that all nodes are free. As
the robot moves towards the destination, it discovers the presence of obstacles,
it updates its map and the shortest path is recomputed from the current position
to the destination (replanning). D* Lite algorithm implements the same route
11
2 Background
Figure 2.3: Example of how D* Lite works.
planning approach as D*, but the algorithm is shorter and it is simpler than D*
with fast replanning and more memory efficient than A* and unlike A*, it can be
used in a partially known and dynamic map [18]. The figure 2.4 represents an
optimized version the algorithm where Sstart is the current node in the grid,
Sgoal is the destination node. Two estimates of costs for nodes : g is the objective function value and rhs is the one step lookahead estimate of the objective function value.
In figure 2.3, we give an operational example of the D* Lite algorithm.
2.2.3 Tracking and guidance
Tracking
It is the process used for controlling the movement of the user, it also calculates the
changes in his/her position.
A tracking system has three principal sub-sections:
1. Input : The position of the user and the route to travel.
2. The processing section : It integrates the data taken as input, compares the current position with the planned path and makes a decision if it is necessary to
12
2 Background
Figure 2.4: An optimized version of D* Lite algorithm [18].
13
2 Background
recalculate the rest of the path. If the user takes a wrong path, a new path has
to be recalculated.
3. The output : The new path showed on the map.
In each instance, we have to loop around these three sections to keep the user
up-to-date about the best route to reach his destination [19].
Guidance
It is used to guide the user along the pre-defined route. It is a matter of comparing
the route actually traveled with the pre-calculated itinerary. It is the set of navigation
instructions to identify the path to travel. For example, to turn left or right, the room
number, and how much distance to the turn. These indications can be in the form of
image, text or speech along the rest of the path. To monitor the position of the moving
object with respect to the calculated trajectory, map matching is used [19].
2.3 Cartography
A map is often required for navigation to display the path and the Points of Interest
(POI) inside the building.
The International Cartographic Association defines cartography as the discipline dealing with the design, construction, dissemination of maps. This means that cartography is the whole process of mapping. This process includes everything from the
gathering, evaluation and processing of source data, through the graphical design of
the map, to the drawing and reproduction of the final map. This is a major step in the
design of most indoor navigation services [20].
2.3.1 Ubiquitous cartography
Ubiquity is a latin word.
ubi = where
14
2 Background
Que = any, also, every
ubique = everywhere
We can define ubiquitous cartography as the research field of how maps can be created
and used anywhere and at any time. Ubiquitous maps can be accessed anywhere
through the information network. ubiquitous cartography is a part of the technological
cartography dealing with exchange and transmission processes and visualization of
diverse spatial information on hand held displays. It does not only include map making but also includes map use and map communication considering the interaction
between map, spatial image, and the real world.
There are many types of indoor maps. We can find 2D, 2.5-D maps as well as 3D
maps.
2D maps
There are already many mapping applications and services : In 2D (Google Maps,
Live Maps, Mappy, Via Michelin, etc). Those maps have only x and y directions and
no z direction.
2.5-D maps
Refers to imaging technologies that are between 2D and 3D. A model where for each
point of the ground defined by a pair of coordinates (x, y) and only one z coordinate.
The term 2.5D refers to the fact that for positioning with the (x,y) plane, a continuous
value domain is used, whereas for the z-axis only discrete values are used [21].
3D maps
It is a 2D model with vertical visual connections. 3D representations are much more
suitable to simulate rich indoor content (e.g., furniture, textures, etc) and building assets (e.g., fire hydrant, Mechanical and Electrical (ME) systems, etc). Indoor maps can
have 3D view by different methods like 3D visual simulation or by using tools such
15
2 Background
as eeGeo (a dynamic 3D mapping platform). Currently, various indoor navigation solutions are introduced (Deep Map, Mally, NavVis, Indoor3D, etc). Some navigate 3D
space using various camera perspectives, some use Augmented Reality (AR), while
others navigate usingg 3D game environments [22].
2.3.2 Points of interest (POI)
They can be defined as services inside the building. Those POI are different from a
building to another. We assumed to define a POI service such as classrooms, WCs,
laboratories, professor offices, administration offices and kitchens. These rooms are
interesting especially for users who are not familiar with the building.
Special points of interest
Landmarks are remarkable objects that facilitate positioning and navigation indoors.
They are generally unique at least in one floor. We have chosen the elevators in the
three floors and coffee, beverage and food distributors in the ground floor.
2.3.3 Computer-aided design (CAD) maps
Computer-aided design is the use of computer programs to create two- or threedimensional (2D or 3D) graphical representations of physical objects. CAD software
may be specialized for specific applications. The use of CAD generated vector plans
showed limitations in terms of the data model : These plans are complex and present
unnecessary information for positioning and navigation. Also, the conversion of this
format to a georeferenced data used by the outdoor navigation service is limited and
complex. Which is not beneficial because the purpose of indoor mapping is to facilitate navigation and to present a simple and rich data model.