# LUP Student Papers

## LUND UNIVERSITY LIBRARIES

### Map change detection using GPS position data

and Andersson, Fanny LU (2018) In Master's Theses in Mathematical Sciences FMAM05 20181
Mathematics (Faculty of Engineering)
Abstract
Technology advancement in autonomous driving is accelerating. For the technology to be safe it is crucial for the vehicles to have an updated map, meaning all vehicles should have a correct and identical representation of the current road network. This makes change detection in the maps of great importance, in order to continuously understand and recognize the features that need to be updated.

This thesis aims to develop and evaluate methods to continuously and automatically update maps using only crowd-sourced Global Positioning System (GPS) data. The approach was to create inferred maps using a method based on an approximate Kernel Density Estimation (KDE). The road network is represented using a mathematical graph. A Hidden Markov... (More)
Technology advancement in autonomous driving is accelerating. For the technology to be safe it is crucial for the vehicles to have an updated map, meaning all vehicles should have a correct and identical representation of the current road network. This makes change detection in the maps of great importance, in order to continuously understand and recognize the features that need to be updated.

This thesis aims to develop and evaluate methods to continuously and automatically update maps using only crowd-sourced Global Positioning System (GPS) data. The approach was to create inferred maps using a method based on an approximate Kernel Density Estimation (KDE). The road network is represented using a mathematical graph. A Hidden Markov Model (HMM) and the Viterbi algorithm are used to map match GPS data to the road network.

In the updating routine, new roads are added and old ones are removed. Furthermore, temporary changes are flagged. Three evaluation methods, two set-based and one path-based, are proposed which complement one another by taking different aspects into account—both geometric and topologic.

The proposed map-inference method is robust to noise compared to many other map-generation algorithms, however, it is computationally heavy. Therefore, we propose creating geographically smaller maps and fusing multiple maps together. One of the main challenges was the parameter tuning of various thresholds, since the implemented algorithms are sensitive with respect to the accuracy of the data. The path-based evaluation is the only method where parameter tuning is not needed.

Evaluation results show successful map updates on road level, where the accuracy was further increased when using an OpenStreetMap (OSM) as base map. However, results show that the methodology is not appropriate to obtain lane-level accuracy. (Less)
Popular Abstract (Swedish)
Självkörande bilar är ett hett forskningsområde och utvecklingen går snabbt framåt. För att teknologin ska vara säker krävs det att alla bilar har en uppdaterad karta över hur vägnätverket ser ut. Om bilen ska kunna använda kartan för navigering behöver den innehålla information om mer än bara var man kan svänga. Information ner på centimeterprecision om vägskyltar, trafikljus, vägmarkeringar och vägräcken är livsnödvändigt för att bilen ska kunna köra själv.

De flesta nyare bilar samlar hela tiden in information om sin omgivning med hjälp av ett antal sensorer såsom kameror, RADAR och GPS. Med denna information kan förändringar i vägnätverket upptäckas. Dessa förändringar kan vara både temporära såsom vägarbeten eller permanenta såsom... (More)
Självkörande bilar är ett hett forskningsområde och utvecklingen går snabbt framåt. För att teknologin ska vara säker krävs det att alla bilar har en uppdaterad karta över hur vägnätverket ser ut. Om bilen ska kunna använda kartan för navigering behöver den innehålla information om mer än bara var man kan svänga. Information ner på centimeterprecision om vägskyltar, trafikljus, vägmarkeringar och vägräcken är livsnödvändigt för att bilen ska kunna köra själv.

De flesta nyare bilar samlar hela tiden in information om sin omgivning med hjälp av ett antal sensorer såsom kameror, RADAR och GPS. Med denna information kan förändringar i vägnätverket upptäckas. Dessa förändringar kan vara både temporära såsom vägarbeten eller permanenta såsom nya vägar. Att manuellt hitta och korrigera dessa ändringar i motsvarande karta är kostsamt och tidskrävande.

I detta arbete utforskas metoder för automatisk kartuppdatering. Idén är att utnyttja en stor mängd GPS-data som samlas in från många bilar. Med hjälp av denna data kan en karta skapas över hur vägnätverket ser ut. Denna används sedan för att hitta förändringar i en äldre existerade karta. Detta kan vara antingen en högkvalitativ manuellt verifierad karta, exempelvis Google Maps, eller en karta skapad med data insamlad under en tidigare period. När förändringarna har identifierats uppdateras den äldre kartan med hjälp av den nya kartan. Genom att kontinuerligt samla in ny data kan vi se till att kartan de autonoma bilarna kör efter är uppdaterad så att de kan köra säkert. (Less)
author
supervisor
organization
alternative title
Utilising inferred maps to continuously and automatically detect changes in road networks for autonomous vehicles
course
FMAM05 20181
year
type
H2 - Master's Degree (Two Years)
subject
keywords
autonomous driving, change detection, map inference, GPS, road network, HMM, Viterbi algorithm, OSM, map matching, crowd-sourced data, update maps
publication/series
Master's Theses in Mathematical Sciences
report number
LUTFMA-3353-2018
ISSN
1404-6342
other publication id
2018:E35
language
English
id
8948007
2018-06-12 16:47:46
date last changed
2018-06-12 16:47:46
```@misc{8948007,
abstract     = {Technology advancement in autonomous driving is accelerating. For the technology to be safe it is crucial for the vehicles to have an updated map, meaning all vehicles should have a correct and identical representation of the current road network. This makes change detection in the maps of great importance, in order to continuously understand and recognize the features that need to be updated.

This thesis aims to develop and evaluate methods to continuously and automatically update maps using only crowd-sourced Global Positioning System (GPS) data. The approach was to create inferred maps using a method based on an approximate Kernel Density Estimation (KDE). The road network is represented using a mathematical graph. A Hidden Markov Model (HMM) and the Viterbi algorithm are used to map match GPS data to the road network.

In the updating routine, new roads are added and old ones are removed. Furthermore, temporary changes are flagged. Three evaluation methods, two set-based and one path-based, are proposed which complement one another by taking different aspects into account—both geometric and topologic.

The proposed map-inference method is robust to noise compared to many other map-generation algorithms, however, it is computationally heavy. Therefore, we propose creating geographically smaller maps and fusing multiple maps together. One of the main challenges was the parameter tuning of various thresholds, since the implemented algorithms are sensitive with respect to the accuracy of the data. The path-based evaluation is the only method where parameter tuning is not needed.

Evaluation results show successful map updates on road level, where the accuracy was further increased when using an OpenStreetMap (OSM) as base map. However, results show that the methodology is not appropriate to obtain lane-level accuracy.},
author       = {Sjöstrand, Lina and Andersson, Fanny},
issn         = {1404-6342},
keyword      = {autonomous driving,change detection,map inference,GPS,road network,HMM,Viterbi algorithm,OSM,map matching,crowd-sourced data,update maps},
language     = {eng},
note         = {Student Paper},
series       = {Master's Theses in Mathematical Sciences},
title        = {Map change detection using GPS position data},
year         = {2018},
}

```