Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-11T06:49:38.046Z Has data issue: false hasContentIssue false
  • English
  • Français

A Hidden Markov Model-Based Map-Matching Algorithm for Wheelchair Navigation

Published online by Cambridge University Press:  15 June 2009

Ming Ren  and
Hassan A. Karimi
Ming Ren*
Affiliation:
(University of Pittsburgh)
Hassan A. Karimi
Affiliation:
(University of Pittsburgh)
*
(Email: mren@sis.pitt.edu)
Rights & Permissions [Opens in a new window]

Abstract

Application of map-matching techniques to GPS positions can provide accurate vehicle location information in challenging situations. The Hidden Markov Model (HMM) is a statistical model that is well known for providing solutions to temporal recognition applications such as text and speech recognition. This paper introduces a novel map-matching algorithm based on HMM for GPS-based wheelchair navigation. Given GPS positions, a hidden Markov chain model is established by using both geometric data and the topology of sidewalk segments. The map-matching algorithm employs the Viterbi algorithm to estimate correct sidewalk segments as hidden states in a HMM in order to match GPS trajectory on the corresponding segment sequence. The HMM-based map-matching algorithm was validated on a campus sidewalk network for wheelchair navigation. The results show an improvement in tracking a wheelchair in dense urban conditions both in accuracy and in computational time.

Keywords

Hidden Markov ModelMap-matchingWheelchair navigation
Type
Research Article
Information
The Journal of Navigation , Volume 62 , Issue 3 , July 2009 , pp. 383 - 395
Copyright
Copyright © The Royal Institute of Navigation 2009

1. INTRODUCTION

GPS-based wheelchair navigation systems use geo-positioning and map-matching to compute the location of a wheelchair on a sidewalk (Ming and Karimi Reference Ren and Karimi2008). Wheelchair navigation systems deal with more challenging problems than do those for car navigation. Since wheelchair users outdoors usually take sidewalks that are close to buildings, their navigation systems are more susceptible to GPS signal loss or degradation than navigation systems used in cars. A further characteristic of wheelchair navigation, unlike car navigation, is that typically there are no other sensors to help replace or augment GPS data.

Two main error sources make this work challenging. First, the accuracy of GPS is always an issue in dense urban areas, where high buildings, among other obstacles, block satellite signals. Second, wheelchair navigation takes place on a sidewalk network instead of the road network used for car navigation, and this brings more difficulties in map-matching. The quality of a sidewalk network map database is affected by data collection techniques and the operating skill of a map maker. In addition, since most roads have sidewalks on both sides, a sidewalk network is much denser than its corresponding road network, so a challenge in wheelchair navigation using GPS-based geo-positioning technique is determining on which side of the road the wheelchair is moving. This also makes a simple map-matching algorithm, like nearest road matching, unlikely to succeed. Additionally, wheelchair users sometimes move on a random path rather than follow the sidewalk. This further compounds the map-matching algorithm for wheelchair navigation. Examples of these cases are illustrated in Figure 1. Figure 1a shows how inaccurate the GPS signal is in some places where there are high buildings. Figure 1b shows the trajectory of a user who travelled along a route for which there was no corresponding sidewalk in the area's map database. Figure 1c provides a comparison of the density of a sidewalk network with that of its corresponding road network.

Figure 1. Sources of inaccuracy in wheelchair navigation.

In general, map-matching algorithms integrate estimated locations from any kind of positioning sensors, not only GPS but also other positioning and orientation data, with spatial network data on a digital map to identify the correct link on which a vehicle is travelling and to determine the location of a vehicle on that link (Karimi et al Reference Karimi, Conahan and Roongpiboonsopit2006; Quddus Reference Quddus2006; Ochieng et al Reference Ochieng, Quddus and Noland2004). In this paper, we present an HMM-based map-matching algorithm for wheelchair navigation that will determine the sidewalk segment on which a wheelchair is located based on available GPS data projected onto an identified sidewalk segment. Although we concentrate only on GPS data in this paper, our algorithm is applicable to other positioning sensors, including odometer, compass readings, triangulation from Wi-Fi base stations or cell towers, and all such combinations.

The paper is organized as follows. Section 2 briefly overviews current methods for map-matching. Section 3 describes the proposed HMM-based map-matching algorithm. Section 4 presents the results of evaluating the HMM-based map-matching algorithm using the University of Pittsburgh campus sidewalk network. Conclusions and plans for future research are given in Section 5.

2. BACKGROUND

Main approaches to map-matching include point-to-point, point-to-curve, curve-to-curve and topological map-matching (Karimi et al., Reference Karimi, Conahan and Roongpiboonsopit2006; Quddus Reference Quddus2006; Ochieng et al., Reference Ochieng, Quddus and Noland2004). The simplest way to match GPS data is to find the nearest point on the map based on point-to-point distances. Another technique to match GPS data to sidewalk segments is simply to select the nearest segment by computing perpendicular distance from each GPS point to all candidate segments on a map. Curve-to-curve map-matching algorithms use the similarity between the vehicle's trajectory and the curves as matching criteria. The most similar curve is selected as the correct segment. Topological map-matching (Meng et al., Reference Meng2006; Quddus et al., Reference Quddus, Ochieng, Zhao and Noland2003) considers both geometrical data and topological relationships of GPS positioning trajectory and candidate segments as the decision factors for map-matching. The candidate which earns the highest score from topological and geometric based calculations is considered as the vehicle's true location. In order to further enhance the matching accuracy, many advanced mathematical methods have been introduced in this field, such as a fuzzy logic approach and Kalman filters. Results show that these advanced approaches perform better than basic map-matching algorithms (Quddus et al Reference Quddus, Ochieng and Noland2007). However, all these map-matching techniques are developed and tested for car navigation where centreline road networks are used. The only map-matching algorithm for wheelchair navigation is the chain-code-based map-matching algorithm developed by Ming and Karimi (Reference Ren and Karimi2008).

3. HIDDEN MARKOV MODEL MAP-MATCHING

The Hidden Markov Model is a statistical model in which the system being modelled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden (unknown) parameters from the observable parameters (Wikipedia, Ephraim and Merhav Reference Ephraim and Merhav2002). The HMM has been used in temporal recognition applications such as text and speech recognition. We argue that map-matching is also a temporal recognition application susceptible to a Markov process where the aim is to find actual paths and actual locations, i.e., the hidden information, using GPS data as observed measurements. Map-matching, as a time-series problem, resembles temporal pattern recognition applications, such as speech, handwriting, gesture recognition and bioinformatics, where the hidden Markov model is applied. With these characteristics, a map-matching algorithm based on HMM, where finding the correct sidewalk segment amongst all candidate sidewalk segments given a GPS trajectory, is set forth in this research.

The Viterbi Algorithm (Forney Reference Forney1973) is a recursive optimal solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process. Many problems can be cast in this form. We applied the Viterbi algorithm to estimate the sidewalk segments based on observed GPS positions. The key innovation using HMM in this algorithm for wheelchair navigation is matching sidewalk segments based not only on the geometry of the location readings, but additionally on the topology of the segments.

3.1. Hidden Markov Model

The HMM is represented by a finite set of states, each of which is associated with a probability distribution. Transitions among the states are governed by a set of probabilities called transition probabilities. In a particular state an outcome or observation can be generated according to the associated probability distribution. It is only the outcome, not the state, that is visible to an external observer and therefore states are ‘hidden’ to the outside; hence the name Hidden Markov Model (Rabiner Reference Rabiner1989). The general architecture of a hidden Markov model is shown as Figure 2.

Figure 2. Architecture of an HMM.

The architecture has two layers: {o t} represents the observable layer and o t corresponds to an observation value at time t. {q t} represents the hidden layer, and q t, at time t, comes from one state in a state space. In order to model a hidden Markov process, the following elements are needed:

  • • The number of states in the model, n.

  • • The number of observations, m. If the observations are continuous then m is infinite.

  • • A set of state transition probabilities. A={a ij}

    (1)
    a_{ij} \equals p_{r} \lcub q_{t \plus \setnum{1}} \equals j \vert q_{t} \equals i \rcub \comma 1 \les i \comma j \les n
    where q t denotes the state at time t.

  • • An observation probability distribution in each of the states, B={b j(k)}.

    (2)
    b_{j} \lpar k\rpar \equals p_{r} \lcub o_{t} \equals o_{k} \vert q_{t} \equals j\rcub \comma \, 1\les\, j\les n\comma \, 1 \les k \les m
    where o t is the observation at time t and o k denotes the k th observation.

  • • The initial state distribution, π={πi}, where,

    (3)
    \pi \equals p_{r} \lcub q_{\setnum{1}} \equals i\rcub \comma 1 \les i \les n
    With these, λ=(π, A, B) can be used to denote an HMM with probability distributions.

3.2. A Hidden Markov Model for Map-Matching

In a hidden Markov model, the state is not directly visible, but variables influenced by the state are visible. Each state has a probability distribution over the possible observations. Therefore, the sequence of observations provides some information about the sequence of states by means of a HMM (Cappé et al., Reference Cappé, Moulines and Rydén2005). Given the parameters of the model, the Viterbi algorithm can solve the problem of how to find the most likely sequence of hidden states that could have been generated by using a given observed sequence. The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states, called the Viterbi path. In map-matching for wheelchair navigation, observed GPS points are the visible observation layer and correct sidewalk segments are the invisible state layer.

Let Pt∊{p 1, p 2, …, p m} denote the observation (i.e., a GPS data point) obtained every second t for 1⩽t⩽m.

Let Rt∊{r 1, r 2, …, r n} denote the actual location (i.e., the correct sidewalk segment) at time t.

Suppose we obtain a series of GPS observations within the time period m, so we could obtain m GPS points as an observation sequence from time t 1 to time t m. In the state space, there are n states, which represent n candidate segments. The transition probability from any time i to the next time j represents the probability of a user moving from one segment to another segment. The model could be structured as shown in Figure 3. The goal is to find the sidewalk segment sequence that has maximum probability given the observations. That is, finding a sequence of actual locations, R 1…R t, such that Pr(R 1R 2 … Rt|P 1P 2 … P t) is maximized.

Figure 3. The hidden Markov model for map-matching.

Based on conditional probabilities from basic probability theory, for any sequence R 1...R t of actual locations we have:

(4)
\Pr \lpar {R_{\setnum{1}} R_{\setnum{2}}\ldots R_{t} \vert {P_{\setnum{1}} P_{\setnum{2}}\ldots P_{t} } } \rpar \equals {{\Pr \lpar {R_{\setnum{1}} R_{\setnum{2}} \uscore R_{\setnum{t}} P_{\setnum{1}} P_{\setnum{2}} \uscore P_{t} } \rpar} \over {\Pr \lpar {P_{\setnum{1}} P_{\setnum{2}} \uscore P_{t} } \rpar}}

Given the observations, the denominator of this expression is determined (the exact value is unknown, but that value only depends on the observations, not on the path R 1 … R t.). So the problem is equivalent to finding R 1 … R t such that Pr(R 1R 2 … R tP 1P 2 … P t) is maximized.

From the basic identities of probability theory, for any events A, B, C we have, Pr(ABC)=Pr(A)Pr(B|A)Pr(C|AB). We use this to decompose the complicated event:

\eqalign {\tab{R_{\setnum{1}} R_{\setnum{2}} \ldots R_{t} P_{\setnum{1}} P_{\setnum{2}} \ldots P_{t} \ {\rm as \ a \ product \ ABC}. \ {\rm We\ define\ }A \equals R_{\setnum{1}} \ldots R_{t \minus \setnum{1}} P_{\setnum{1}} \ldots P_{t \minus \setnum{1}} \comma }\cr\tab\quad{ B \equals R_{t} \comma C \equals P_{t} \comma

By applying the above formula, we obtain:

\eqalign{Pr \lpar R_{\setnum{1}} R_{\setnum{2}} \ldots R_{t} P_{\setnum{1}} P_{\setnum{2}} \ldots P_{t} \rpar \equals \tab Pr \lpar R_{\setnum{1}} R_{\setnum{2}} \ldots R_{t \minus \setnum{1}} P_{\setnum{1}} P_{\setnum{2}} \ldots P_{t \minus \setnum{1}} \rpar \cr \tab \times Pr \lpar R_{t} \vert R_{\setnum{1}} \ldots R_{t \minus \setnum{1}} P_{\setnum{1}} \ldots P_{t \minus \setnum{1}} \rpar \cr \tab \times Pr \lpar P_{t} \vert R_{\setnum{1}} \ldots R_{t \minus \setnum{1}} P_{\setnum{1}} \ldots P_{t \minus \setnum{1}} R_{t} \rpar .\cr}

Furthermore, we obtain:

(\hskip 53pt(5))
\eqalign{ Pr \lpar R_{\setnum{1}} \ldots R_{t} P_{\setnum{1}} \ldots P_{t} \rpar \equals \tab Pr \lpar R_{\setnum{1}} \ldots R_{t \minus \setnum{1}} P_{\setnum{1}} \ldots P_{t \minus \setnum{1}} \rpar Pr \lpar R_{t \minus \setnum{1}}\! \rightarrow\! R_{t} \rpar \Pr \lpar R_{t}\! \rightarrow\! P_{t} \rpar \cr \tab \equals Pr \lpar R_{\setnum{0}} \rpar \prod\nolimits_{t \equals \setnum{0}}^{\rm T} {\Pr \lpar {\rm R_t} \vert {\rm R_{t \minus 1}\rpar \prod\nolimits_{{\rm t} \equals \setnum{0}}^{\rm T} {\Pr \lpar {\rm Pt}\vert {\rm Rt}\rpar .}}

We assume each probability in the state transition matrix and in the observation probability matrix in the HMM is time independent. Therefore, given prior probability Pr(R 0), observation probability Pr(P t|R t) and state transition probability Pr(R t|R t−1), we can use the Viterbi algorithm to find the path through the states that maximizes the probability of a sequence of sidewalk segments. The Viterbi algorithm uses dynamic programming methods to efficiently accomplish this, so that the actual path consisting of a sequence of sidewalk segments can be identified.

In Equation (5), in order to apply the Viterbi algorithm, we need to know prior probability, observation probability and state transition probability in the HMM. Prior probability Pr(R 0) is Pr(r j), when j=1, …, n, which is simply computed by 1/n as a uniform distribution reflecting the fact that we have no known bias about which is the correct sidewalk segment. Hence, how to compute observation probability and state transition probability becomes the key point.

First, we compute the observation probability, which is the probability of the measured location p i given r j. We can compute this with the Bayesian rule:

(6)
{\rm P}_{\rm r} \lpar {\rm p}_{\rm i} \vert {\rm r}_{\rm j} \rpar \equals {{{\rm P}_{\rm r} \lpar {\rm r}_{\rm j} \vert {\rm p}_{\rm i} \rpar \Pr \lpar {\rm p}_{\rm i} \rpar } \over {\sum\nolimits_{{\rm k} \equals \setnum{1}}^{\rm n} {{\Pr}\lpar {\rm r}_{\rm k} \vert {\rm p}_{\rm i} \rpar \Pr\lpar{\rm p}_{\rm i} \rpar } }}\quad i \equals \it1\comma 2 \ldots \comma m\semi \quad j \equals 1\comma 2 \ldots n

We presume that Pr(pi), a prior probability in Equation (6), follows a uniform distribution. Therefore, Equation (6) could be further simplified as:

(7)
{\rm P}_{\rm r} \lpar {\rm p}_{\rm i} \vert {\rm r}_{\rm j} \rpar \equals {{{\rm P}_{\rm r} \lpar {\rm r}_{\rm j} \vert {\rm p}_{\rm i} \rpar } \over {\sum\nolimits_{{\rm k} \equals \setnum{1}}^{\rm n} {{\rm p}_{\rm r} \lpar {\rm r}_{\rm k} \vert {\rm p}_{\rm i} \rpar } }}\quad i \equals \it1\comma 2 \ldots \comma m\semi \quad j \equals 1\comma 2 \ldots \comma n

Pr(rj|pi) is the probability that r j is the correct sidewalk segment out of the candidate sidewalk segments given that measured location is P i. We computed this by assuming that, for most of the GPS points, the closer a sidewalk segment is to the observed point, the higher the probabilities that it is the correct segment. This is borne out by our informal observations of nearest segment matching. Considering the relationship of distance and observation probability as an inverse proportion, we first compute the probability of the perpendicular distance from GPS point p i to the segment rj over the summation of the distances from p i to all the candidate segments, and then use reciprocal relation of the probability based on distances to approximate observation probability. This leads to:

(8)
\eqalign{ {\rm P}_{\rm r} \lpar {\rm r}_{\rm j} \vert {\rm p}_{\rm i} \rpar \equals \tab {{Expected \ \lcub number \ of \ time \ in \ segment \ {\rm r}_{\rm j} \vert GPS \ measured \ location \ {\rm p}_{\rm i} \rcub } \over {Expected \ \lcub all \ the \ times \ in \ all \ possible \ segments \ {\rm r_{\setnum{1}}} \ldots {\rm r}_{\rm n} \vert GPS \ measured \ location \ {\rm p}_{\rm i} \rcub }} \cr \tab \equals 1\sol {{Distance \ from \ {\rm p}_{\rm i} \ to \ {\rm r}_{\rm j} } \over {\sum\nolimits_{k \equals \setnum{1}}^{n} {Distance \ from \ {\rm p}_{\rm i} \ to \ {\rm r}_{\rm k} } }} \hfill

In wheelchair navigation, wheelchair users either move on the same segment, or they make a turn at a junction such as an intersection, exit, or entrance. Therefore, we need to compute the transition probability a ij, which represents the probability of the wheelchair user moving from one sidewalk segment corresponding to a measured point to another sidewalk segment corresponding to another measured point. For this, in this algorithm we use topological relationship to compute the transition probability. We only consider three topological relationships: same segment, connected segment and unconnected segment. It is impossible for a wheelchair user to move from a segment to an unconnected segment in consecutive time windows. Therefore, the transition probability from time i to the next time j=i+1, a ij would be zero where the two segments are not connected. If two sidewalk segments are connected, this transition probability should be higher than if two sidewalk segments are unconnected, since wheelchair users would travel on the same segment most of the time except at an intersection or junction. Thus, the transition probability of moving on the same segment has the highest value. By setting a ij=e −rij , we create an exponential curve for this probability distribution, where r ij corresponds to the topological relationship between two segments. By normalization, a ij changes between 0 and 1. The next important step is to build a transition matrix {r ij} and set the value for each element in this matrix. The following set of rules must be followed

  1. (1) If two segments are connected, r ij is set to 1;

  2. (2) If they are unconnected, then r ij is set to ∞.

  3. (3) Otherwise, r ij is 0, when two segments are the same, that is i=j.

Take our measured GPS points on campus as an example, shown in Figure 4. First, we model sidewalk segments as a set {r 1,r 2, …, r 12} as Figure 5 shows. Next, we build a matrix {r ij}, based on the topology of the segments in Figure 6. Figure 7 shows the map matching results by applying the Viterbi algorithm to the entire sequence of location measurements shown in Figure 4.

Figure 4. An example of GPS points overlaid on sidewalks on campus.

Figure 5. An abstracted sidewalk network model.

Figure 6. State transition matrix.

Figure 7. Map-matching locations versus GPS positions.

3.3. HMM-based Map-matching Process

For a hidden Markov model, two parameters, n and m, have to be initialized, where m is the size of an observation sequence and n is the state number in a state space. For map-matching, the size of the observation sequence is the number of measured GPS points and the state number is the number of candidate sidewalk segments close to the observed GPS points. In this algorithm, after setting these two values, we take several steps to complete the matching process.

First, a set of nearby candidate sidewalk segments is chosen based on the first GPS data observed in each sequence. Second, the transition matrix on the selected set of nearby candidate sidewalk segments is built (see Figure 6). This matrix not only shows the topology of segments but implies two moving modes, which are changing mode and continuing on same segment mode. In the case of continuing on same segment mode, where r ij is equal to 0, current and previous positions should be matched on the same segment. Conversely, if r ij is 1, then the wheelchair is moving in a changing mode, where current and previous positions are on two connected segments. Consequently, we could compute transition probabilities based on the transition matrix. Third, the perpendicular distance from each GPS point to each segment in the set of candidate sidewalk segments is computed, so that observation probabilities for each measured location are calculated. Last, the Viterbi algorithm to the observation probabilities and transition probabilities to compute the maximum probability sequence of sidewalk segments are applied. Once the most likely sidewalk segment is obtained, GPS points are projected to the segments and the map-matching result is shown on the map. The flowchart of the process is shown in Figure 8.

Figure 8. Flowchart of HMM-based map-matching process.

4. VALIDATION

To validate the HMM-based map-matching algorithm developed in this work for wheelchair navigation, the sidewalk data along with associated parameters on the University of Pittsburgh campus area were digitized and utilized. The sidewalk database, consisting of the sidewalk network, buildings, landmarks, and accessibility information, are built for wheelchair navigation in order to assist wheelchair users travelling outdoors (Kasemsuppakorn and Karimi Reference Kasemsuppakorn and Karimi2008). For the testing, GPS points were collected by walking and using a stand-alone GPS receiver, and map-matched to the established sidewalk network. The computing platform used was a PC machine with Intel Core 2 1.4G HZ CPU. The software for the HMM-based map-matching algorithm was written in JAVA in an open source GIS tool called Geotools (Geotools 2008).

4.1. Analysis of Results

Three groups of data sets, collected on main campus of University of Pittsburgh by GPS receiver, were processed to validate the presented algorithm. Route 1 covered the most main sidewalks on campus; Route 2 included the sidewalks around high buildings; Route 3 included a loop and some small paths. Fully considering the various types of sidewalks on the different areas, we used the three selected routes to test the HMM-based map-matching algorithm. In comparison, three-route GPS raw data with map-matching results were overlapped on campus sidewalk map, shown in Figures 9, 10, and 11.

Figure 9. Route 1 comparing map-matching result with GPS raw data on campus sidewalk map.

Figure 10. Route 2 comparing map-matching result with GPS raw data on campus sidewalk map.

Figure 11. Route 3 comparing map-matching result with GPS raw data on campus sidewalk map.

Model parameters n and m were specified through experiments. Based on the topology extracted from the campus sidewalk data, the size of the state space, i.e., the number of segment candidates in one map-matching process, notated by n, was set as twelve. Experiments using 3- to 8-point sequence were conducted to determine the suitable number of points in one sequence. It was realized that for the real-time requirement of map-matching a 4-point sequence is appropriate for this HMM-based map-matching algorithm. The map-matching performances are presented in Table 1. The average time per four points represents the average time taken for one sequence matching computation. In the offline matching, the total computation time shows the total time to complete the matches of all GPS points in one route. Since correct link identification after applying a map-matching algorithm and average computation time are the most important performance parameters for evaluation, we use statistical data to show that this algorithm performs well and satisfies the requirements of real-time map matching in wheelchair navigation.

Table 1. Performance results.

As with all map-matching algorithms, there are mismatched points due to errors in geo-positioning systems and the digital map quality, and both affect the performance of the map-matching algorithm. We observe that most mismatched points in Route 3 occur when the data collector moved on paths with no corresponding segments on the digital map. Meanwhile, in the case of Routes 1 and 2, we realize that many mismatched points occur on sidewalks of narrow roads due to GPS errors.

5. CONCLUSIONS AND FUTURE RESEARCH

In this paper, we presented a novel map-matching algorithm to estimate wheelchair location in sidewalk networks. The HMM-based map-matching algorithm matches with high accuracy GPS data to segments based on finding an optimal compromise between GPS data and topological structure, implicitly accounting for the topology of the sidewalk network. This trade-off is accomplished with a hidden Markov model. The algorithm was tested in many situations where it successfully ignored complex distractions to find the correct path. However, some GPS points were still mismatched due to failure in differentiating between the two sides of narrow roads. Future work on this algorithm should include a more careful characterization of topological data. Map-matching results may be more accurate if we could account for the fact that transition probability between two candidate sidewalk segments changes with a wheelchair moving. In addition, applying this algorithm to other navigation environments, such as car navigation, will further validate its appropriateness for all navigation applications.

References

REFERENCES

Cappé, O., Moulines, E., Rydén, T. (2005). Inference in Hidden Markov Models, Published by Springer.Google Scholar
Ephraim, Y. and Merhav, N. (2002). Hidden Markov processes, IEEE Trans. Inform. Theory, vol. 48, pp. 1518–1569.CrossRefGoogle Scholar
Forney, G. D. (1973). The Viterbi algorithm. Proceedings of the IEEE 61(3): 268–278.CrossRefGoogle Scholar
Geotools (2008). The java GIS toolkit, http://sourceforge.net/projects/geotools/Google Scholar
Hidden Markov model. Wikipedia, the free encyclopedia, http://en.wikipedia.org/wiki/Hidden_Markov_modelGoogle Scholar
Jagadeesh, G. R., Srikanthan, T. and Zhang, X. D. (2004). A Map Matching Method for GPS Based Real-Time Vehicle Location, Journal Of Navigation, 57, 429–440.Google Scholar
Karimi, H A, Conahan, T. and Roongpiboonsopit, D. (2006). A Methodology for Predicting Performances of Map-Matching Algorithms, W2GIS 202–213.CrossRefGoogle Scholar
Kasemsuppakorn, P. and Karimi, H. A. (2008). Data requirements and spatial database for personalized wheelchair navigation, 2nd International Convention on Rehabilitation Engineering & Assistive Technology.Google Scholar
Krumm, J., Letchner, J. and Horvitz, E. (2007). Map Matching with Travel Time Constraints, SAE 2007 World Congress, April 16–19.CrossRefGoogle Scholar
Meng, Y. (2006). Improved Positioning of Land Vehicle in ITS Using Digital Map and Other Accessory Information, PhD Thesis, Department of Land Surveying and Geoinformatics, Hong Kong Polytechnic University.Google Scholar
Ochieng, W. Y., Quddus, M. A. and Noland, R. B. (2004). Map-matching in complex urban road networks, Brazilian Journal of Cartography (Revista Brasileira de Cartografia) 55 (2), 1–18.Google Scholar
Quddus, M. A., Ochieng, W. Y., Zhao, L., Noland, R B 2003 A general map-matching algorithm for transport telematics applications, GPS Solutions 7 (3), 157–167.CrossRefGoogle Scholar
Quddus, M. A., Noland, R. B., Ochieng, W. Y. (2004). Validation of map-matching algorithm using high precision positioning with GPS, Journal of Navigation 58, 257–271.Google Scholar
Quddus, M. A. (2006). High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications A thesis of the University of London.Google Scholar
Quddus, M. A., Ochieng, W. Y. and Noland, R. B. (2007). Current map-matching algorithms for transport applications: State-of-the art and future research directions, Transportation Research Part C 15, pp. 312–328.Google Scholar
Rabiner, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286.CrossRefGoogle Scholar
Ren, M., Karimi, H. A. (under review, 2008). A Chain-Code-Based Map Matching Algorithm for Wheelchair Navigation. Transactions in GIS.Google Scholar
Taylor, G., Blewitt, G., Steup, D., Corbett, S., Car, A. (2001). Road reduction filtering for GPS-GIS navigation, Transactions in GIS, ISSN 1361–1682, 5(3), 193–207.CrossRefGoogle Scholar
Taylor, G., Brunsdon, C., Li, J., Olden, A., Steup, D., Winter, M. (2006). GPS accuracy estimation using map-matching techniques: Applied to vehicle positioning and odometer calibration, Computers, Environments, and Urban Systems 30, 757–772.Google Scholar
Figure 0

Figure 1. Sources of inaccuracy in wheelchair navigation.

Figure 1

Figure 2. Architecture of an HMM.

Figure 2

Figure 3. The hidden Markov model for map-matching.

Figure 3

Figure 4. An example of GPS points overlaid on sidewalks on campus.

Figure 4

Figure 5. An abstracted sidewalk network model.

Figure 5

Figure 6. State transition matrix.

Figure 6

Figure 7. Map-matching locations versus GPS positions.

Figure 7

Figure 8. Flowchart of HMM-based map-matching process.

Figure 8

Figure 9. Route 1 comparing map-matching result with GPS raw data on campus sidewalk map.

Figure 9

Figure 10. Route 2 comparing map-matching result with GPS raw data on campus sidewalk map.

Figure 10

Figure 11. Route 3 comparing map-matching result with GPS raw data on campus sidewalk map.

Figure 11

Table 1. Performance results.