Show simple item record

dc.contributor.advisorEidsvik, Jo
dc.contributor.authorKlåpbakken, Øyvind
dc.date.accessioned2020-06-04T16:02:23Z
dc.date.available2020-06-04T16:02:23Z
dc.date.issued2020
dc.identifier.urihttps://hdl.handle.net/11250/2656712
dc.description.abstractKartmatching refererer til prosessen der en sekvens med posisjonsmålinger brukes til å estimere en sammenhengende rute på et veinettverk. Posisjonsmålinger som brukes til kartmatching er typisk innhentet ved hjelp av en GPS-enhet som befinner seg i et kjøretøy som beveger seg gjennom veinettverket. Formålet med denne avhandlingen er å utforske og evaluere flere forskjellige "skjult Markov modell"-formuleringer (SMM-formuleringer) som muliggjør kartmatching. Disse metodene krever kjennskap til det underliggende veinettverket. Dette veinettverket blir brukt til å konstruere et tilstandsrom hvor hver tilstand representerer et veisegment. Det sørges for at de SMM-baserte kartmatching-metodene overholder antagelsene i en SMM. Tilstandsestimatet man får fra Viterbi-algoritmen kan derfor anses som "den mest sannsynlige sekvensen av veisegmenter". Ett av bidragene i denne avhandlingen er kombineringen av idéer fra tidligere verker på en måte som tilfredsstiller antagelsene i en SMM. Et annet bidrag kommer gjennom introduksjonen av et tilstandsrom som, så vidt forfatteren vet, ikke har blitt brukt før. Denne utvidede tilstandsrom-formuleringen forstørrer tilstandsrommet ved å inkorporere tilleggselementer som blant annet inneholder informasjon om bevegelsesretningen. Bruken av Baum-Welch-algoritmen er også trolig et betydelig bidrag, siden den ikke har blitt brukt til dette spesifikke problemet tidligere. Eksperimentene som presenteres i denne avhandlingen er utført ved bruk av data fra simulert bevegelse på reelle veinettverk. Hovedformålet er å evaluere ytelsen til fire distinkte SMM-baserte metoder. En naiv sammenligningsmetode er også inkludert for å tilføre kontekst. Eksperimentene er delt inn i tre deler: et parametersøk som brukes til å identifisere gode parametervalg for overgangs- og emisjonssannsynlighetene, en del dedikert til estimering av overgangssannsynligheter og en del dedikert til prestasjonsevaluering. Kvaliteten på ruteestimatene blir vurdert ved hjelp av Hausdorff-avstanden på grunn av dens evne til å kvantifisere ruteestimatets grad av korrekthet. Resultatene fra eksperimentene viser at man oppnår en betydelig økning i prestasjon ved å gå fra det enkle til det utvidede tilstandsrommet. Dette er spesielt tydelig i situasjonen med høy samplingsfrekvens og lav varians, hvor man oppnår 90.7% reduksjon i Hausdorff-avstand når SMM-tilnærmelsen med utvidet tilstandsrom sammenlignes med tilnærmelsen hvor det enkle tilstandsrommet brukes.
dc.description.abstractMap matching refers to the process of using a sequence of position measurements to estimate a connected route on a road network. Position measurements used for map matching are typically obtained from a GPS device located in a vehicle moving through the road network. The purpose of this thesis is to explore and evaluate several different hidden Markov model (HMM) formulations that enable map matching. These methods all require knowledge about the underlying road network. This road network is used to create a state space where each state represents a road segment. It is ensured that the HMM-based map matching methods are consistent with the assumptions of an HMM. The state estimate obtained from the Viterbi algorithm can, therefore, be regarded as the "most probable road segment sequence." One of the contributions of this thesis is to combine ideas from earlier works in a way that is consistent with the assumptions of an HMM. Another contribution comes through the introduction of a state space that, to the author's knowledge, has not been used before. This augmented state space formulation extends the state space by incorporating additional elements that, among other things, include information about the direction of travel. The use of the Baum-Welch algorithm is also believed to be a significant contribution, seeing as it has not been applied to this specific problem before. The experiments presented in this thesis are conducted using data from simulated traversal on real road networks. The primary goal is to assess the performance of four distinct HMM-based methods. A simple benchmark method is also included to provide context. The experiments are divided into three parts: a parameter search used to identify good parameter choices for the transition probability and emission probability, a part dedicated to the estimation of transition probabilities, and a part dedicated to performance evaluation. The quality of the route estimates is assessed using the Hausdorff distance because of its ability to quantify the degree of correctness for the route estimates. The results of the experiments show that one achieves substantial performance gains by moving from the simple to the augmented state space. This is especially evident in the case with high sampling frequency and low variance, where we observe a 90.7% decrease in Hausdorff distance for the new augmented state space HMM approach when compared to the approach with a simple state space.
dc.languageeng
dc.publisherNTNU
dc.titleMap matching using hidden Markov models
dc.typeMaster thesis


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record