A Virtual Differential Map-Matching Algorithm with Improved Accuracy and Computational Efficiency

Hongchao Liu; Hao Xu; H. Scott Norville; Yuanlu Bao

doi:10.1017/S0373463308004700

A Virtual Differential Map-Matching Algorithm with Improved Accuracy and Computational Efficiency

Published online by Cambridge University Press: 26 June 2008

Hongchao Liu ,

Hao Xu ,

H. Scott Norville and

Yuanlu Bao

Show author details

Hongchao Liu*: Affiliation:
(Texas Tech University, Lubbock)
Hao Xu: Affiliation:
(Texas Tech University, Lubbock)
H. Scott Norville: Affiliation:
(Texas Tech University, Lubbock)
Yuanlu Bao: Affiliation:
(University of Technology and Science of China)
*: (Email: hongchao.liu@ttu.edu)

Article contents

Abstract
INTRODUCTION AND LITERATURE REVIEW
ERROR ANALYSIS
MAP-MATCHING
THE PROPOSED ALGORITHM
SELECTED RESULTS FROM A REAL-LIFE APPLICATION
CONCLUDING REMARKS
References

Rights & Permissions

Abstract

This paper presents development and application of a real-time virtual differential map-matching approach which makes use of the slow drifting property of the GPS errors and the continuous and gradual evolving characteristic of map errors to improve the accuracy and computational efficiency. A differential vector is created to approximate the real-time deviation, which is corrected continuously along with the vehicle movement during the map-matching process. Real-life application of the algorithm to the City of Hefei, a metropolis of China, shows that it corrects both GPS errors and digital map errors reasonably well with improved computational efficiency.

Keywords

Map-matching GPS Virtual Differential Correction

Type: Research Article
Information: The Journal of Navigation , Volume 61 , Issue 3 , July 2008 , pp. 421 - 434

DOI: https://doi.org/10.1017/S0373463308004700 [Opens in a new window]
Copyright: Copyright © The Royal Institute of Navigation 2008

1. INTRODUCTION AND LITERATURE REVIEW

Although the market for vehicle navigators has been growing steadily in the past five years, cost remains the primary reason people will stay away from the systems. The aim of this research is to contribute to the development of reliable low price in-vehicle navigation devices by introduction of a novel map-matching algorithm.

A fundamental function of a land vehicle navigation device is to reconcile the user's location with the underlying map, which is known as map-matching. Most existing research has focused on map-matching when both the user's location and the map are known with a high degree of accuracy. However, this is unlikely to be the case in many situations especially when available resources for accurate matching are limited.

Among traditional map-matching algorithms, the most common method is the geometric analysis approach which utilizes the geometric information of the road network (e.g., Kim et al., Reference Kim, Lee, Kang, Lee and Kim1996; Rajashri, Reference Rajashri2001). White et al. (Reference White, Bernstein and Kornhauser2000) conducted a comparison analysis of existing geometric map-matching algorithms including point-to-point, point-to-curve, curve-to-curve approaches and concluded that the accuracy problem cannot be solely resolved by the geometric approach. Another typical method is the topological approach which uses the information of the link's geometry, connectivity, and contiguity in map-matching process (e.g., Greenfeld, Reference Greenfeld2002; Chen et al., Reference Chen, Li, Yu and Chen2005). Quddus et al. (Reference Quddus, Ochieng and Noland2007) made a complete review of the models and pointed out that most of the topological approaches are sensitive to outliers and unreliable at junctions where the bearings of the connecting roads are not similar. Honey et al. (Reference Honey, Zavoli, Milnes, Phillips, White and Loughmiller1989) proposed a probabilistic map-matching algorithm in which an elliptical or rectangular confidence region was defined around a position fix obtained from a navigation sensor.

Advanced map-matching algorithms use Kalman filters (e.g., Jo et al., Reference Jo, Haseyamai and Kitajima1996; Kim et al., Reference Kim and Kim2001; Hide et al., Reference Hide, Moore and Smith2001; Jagadeesh et al., Reference Jagadeesh, Srikanthan and Zhang2004), belief theory (e.g., Yang et al., Reference Yang, Cai and Yuan2003; Najjar and Bonnifait, Reference Najjar and Bonnifait2003), and the Fuzzy logic model (e.g., Kim and Kim, Reference Kim and Kim2001; Syed and Cannon, Reference Syed and Cannon2004) in the map-matching process. Most of the algorithms improve the accuracy significantly in terms of positioning the vehicle on the right road. However, little attention seems to have been paid to enhancing the along-track accuracy. As a result, the vehicle may be matched to the right road but running on different segments, which may cause significant error especially when the vehicle is near an intersection. In addition, most existing map-matching models assume the map is accurate with negligible errors, which is unlikely to be the case. A recent Fuzzy logic based model by Quddus and Ochieng (Reference Quddus, Noland and Ochieng2006) seems promising in terms of the great improvement in horizontal accuracy, along-track accuracy, and cross-track accuracy. However, most Fuzzy logic based approaches are computationally less effective, the performance of their model in this regard is unknown.

Blackwell (Reference Blackwell1986) introduced a differential GPS method in map-matching process. Taylor et al. (Reference Taylor, Blewitt, Steup, Corbett and Car2001) extended the study by proposing a method on the basis of virtual differential GPS correction. A notable merit of this approach lies in its simplicity and reasonable accuracy. However, much useful information (e.g., characteristics of GPS errors and map errors, vehicle speed) were not considered in their model, which may demerit its value in real-world application.

This paper presents a real-time virtual differential map-matching algorithm, which fully considers the historical mapping information, the vehicle velocity, the vehicle direction, and the topological structure of the traffic vector map. Especially, the proposed virtual differential map-matching algorithm makes use of the slowly drifting character of the GPS signal error and the continuously drifting character of the vector map error to enhance the accuracy. A fundamental principle of this approach is to obtain a virtual differential error from previous track points and use it to pre-correct later track points before matching them on the map. The algorithm not only corrects the GPS error along the road direction but also the error in the direction perpendicular to the road. In addition, it provides an efficient way to correct inaccurate outlying digital maps.

The remainder of the paper is structured as follows: Section 2 introduces in brief the GPS errors and the map errors. Section 3 describes the map-matching problem and reviews in brief the main literature in this domain. Section 4 provides the concepts and the modelling approach of the proposed map-matching algorithm. Section 5 demonstrates the features and properties of the new algorithm with an experimental study. Section 6 summarizes the effectiveness as well as drawbacks of the proposed algorithm with directions for future study.

2. ERROR ANALYSIS

The deviation of vehicle GPS tracking from the underlying road network is caused primarily by two error sources: GPS signal error and transportation digital map error. Neither of these errors can be ignored in the map-matching process because they both affect its accuracy.

2.1. GPS Signal Error

Many factors affect a GPS signal when it is transmitted from satellites to GPS receivers. These include satellite ephemeris error, satellite clock error, ionospheric delay error, tropospheric delay error, multi-path error, and GPS receiver error (Bao and Liu, Reference Bao and Liu2006). Since the GPS selective availability (S/A) was turned off in May 2000 (Ochieng et al., Reference Yang, Cai and Yuan2001), the GPS signal error has been less than 20 metres in an ideal environment and possibly higher in urban areas. Due to the complexity of fully addressing GPS signal errors in the map-matching process, the leeway for errors and statistic models are often used with approximate means (Shi and Zhu, Reference Shi and Zhu2002).

Although calculating exact vehicle locations is difficult, one feature of the main GPS signal error caught the authors' attention. The satellite error and atmospheric error of a GPS signal both have a high correlation with time, which indicates that main GPS errors are relatively stable during short intervals and similar environments (Bao et al., Reference Bao, Wang and Liu2004). In normal DGPS applications, the correcting vectors from differential stations can eliminate the common GPS errors, but the uncommon GPS errors, for example the multi-path error, can only be corrected when the GPS receiver is close to the stations. In other words, main GPS errors are relevant in time and location. This property can be used to effectively correct GPS errors, especially the error component in the road direction.

2.2. Digital Map Error

The transportation digital map is a vector road map and a Geographic Information System (GIS), which forms the basic data platform for vehicle navigation systems. A primary property of vector mapping is to use nodes information to form a road network. Figure 1 presents the structure of a digital vector map. Road nodes are denoted by n _i (i=0, 1, 2 …) and numbered by their topological relationship. An arc is composed of nodes and a road is composed of arcs.

Figure 1. Structure of vector map.

A set of map nodes is usually expressed by N _R.

(1)

$N_{R} \equals \lcub n_{i} \vert i \equals 1\comma {\rm \ 2\comma \ } \ldots {\rm \comma \ }N\rcub$

An arc is expressed as S _i, and S _R is a set of n ^s arcs on the map.

(2)

$S_{R} \equals \lcub S_{i} \vert {\rm i \equals 1\comma \ 2\comma \ } \ldots {\rm \comma \ }M\rcub$

An arc's end nodes are called big nodes. For example, big node n _j can be expressed by $\overline{n_{j}}$ . The other arc nodes are small nodes. When a vehicle runs from one arc to another, it must go through a big node.

Nodes are the basic and most important elements of a vector road map because the accuracy of the nodes' position determines the accuracy of the road position. There are two major errors, i.e., translation error and rotation error in vector road maps. In Figure 2 the lines in black represent the actual location of the road links, the grey lines represent their corresponding locations on the vector map with the presence of both translation error and rotation error.

Figure 2. Map error.

3. MAP-MATCHING

The map-matching process is a specific procedure which reconciles the vehicle's location with the underlying map. The problem as well as variables of interest is depicted in the following in conjunction with Figure 3.

• When a vehicle is travelling on S ₁, its position tracked by GPS at time k (k=0, 1, 2, …) is recorded as g(k). Due to the GPS errors and map errors, normally g(k) is not on the road S ₁ on the vector road map.
• p(k) is used to represent a matched point on the map, which is calculated from g(k) by using a map-matching process at time k. It is called the matched road point on map, or matched point. The matched point's position on the arc of the vector map should reflect the vehicle's position on the actual road. To this end, the error component in the direction perpendicular to the road needs to be minimized first, followed by the correction of the error component in the road direction.
• q(k) is known as g(k)'s pedal point (or pedal) on S ₁, which is the intersecting point of the road arc S ₁ and its perpendicular drawn from g(k).
• e(k) denotes the deviation between the position of the GPS track point and its corresponding matched location at time k.
(3)
$e\lpar k\rpar \equals p\lpar k\rpar \minus g\lpar k\rpar$
• e _h(k) is the e(k)'s component in the road direction.
(4)
$e_{h} \lpar k\rpar \equals p\lpar k\rpar \minus q\lpar k\rpar$
• e _v(k) is the e(k)'s component in the direction perpendicular to the road.

(5)

$e_{v} \lpar k\rpar \equals q\lpar k\rpar \minus g\lpar k\rpar$

Therefore,

(6)

$e\lpar k\rpar \equals e_{v} \lpar k\rpar \plus e_{h} \lpar k\rpar$

Figure 3. Map-matching problem.

A dynamic map-matching process involves minimizing the deviation error e(k) and determining the matched point p(k) of the GPS track point g(k) by using road network information and all GPS signals of the moment k. The full process is usually divided into two steps: first to identify the road arc S _i on which the vehicle is running, and then determine the matched point p(k) i.e., the location of g(k) on S _i.

4. THE PROPOSED ALGORITHM

With the map-matching process introduced and variables denoted, attention can now be directed to the proposed map-matching algorithm. Taking into account the information of vehicle's position, velocity, direction, as well as historical track data and the topological structure of the vector map, the proposed algorithm makes use of the slow drifting property of main GPS errors and the continuous and gradual evolution property of map errors in the error correction process. A unique virtual differential error correction algorithm was then developed and applied to the map-matching process for enhanced integrity and accuracy.

First, a differential vector is defined by using the location information of GPS track points and the corresponding road near a turn that the vehicle has just completed. Second, the follow-up track points are pre-corrected with the differential vector which functions similarly as the differential vector in Differential Global Positioning System (DGPS). Finally, the pre-corrected track points are matched to the corresponding locations on the identified roads according to the vehicle's velocity, direction and topological structure of the vector map. Because of the pre-correction process, both the along-track and the cross-track errors are corrected significantly. At the same time, in the course of the correcting and matching process, the differential vector is adjusted dynamically to trace the changes in both GPS and map errors.

4.1. Map-matching Track Points and Initialization of the Virtual Differential Vector

At the beginning of the navigation process, the virtual differential vector e _diff has not been determined. At this stage, the matching result will be used to determine the mapped points of the follow-up track points, thus ensuring the accuracy of road identification is essential. The algorithm identifies the road by using both the shortest distance between the track point and the matched road and the consistency of the identified road direction and the vehicle's destination. A measurable variable is the acute angle of the road direction and the vehicle moving direction. To avoid misjudgement, the algorithm strengthens the matching requirements by confirming the identification only when the number of continuous track points matched onto the same road is larger than a preset threshold.

Another task at this stage is to determine the virtual differential vector e _diff. For a single track point, determining its accurate corresponding location on the matched road with only the information from the independent vehicle GPS receiver and the traffic map is difficult. Consequently, obtaining the deviation vector of the track point and the corresponding matched location is also difficult. Here the authors use multiple track points and their corresponding matched points before and after a turn to get the differential vector. After the vehicle completes the first turn that meets the preset requirements, the differential vector can be determined for correcting later track points.

Denote C _current the number of track points that are matched to current road arc and C _last the number of track points that are matched to last road. When a current track point is matched to a new road arc, C _last=C _current and C _current is assigned with zero. If the mapped point is not on the end node of the current road arc, increase the value of C _current by 1. α is used to represent the acute angle of the current road arc and its predecessor. C _eff is the preset threshold for the number of track points that are matched to a road track (six in this study). α_eff is the preset threshold for the acute angle of the current road arc and the last road arc (30° in this study). To judge whether a turn is suitable for determining the differential vector e _eff, some test conditions are set:

(7 a)

$C_{current} \equals C_{eff} \quad {\rm and}\quad C_{last} {\rm \gt\! \equals }C_{eff}$

(7 b)

$\alpha \gt \alpha _{eff}$

These conditions are used to ensure the accuracy and reliability of the to-be-determined differential vector and to reduce the impact of random interference. When both conditions are satisfied concurrently, the virtual differential vector e _eff can be obtained by a method illustrated in Figure 4.

Figure 4. Calculation of the virtual differential vector at a turn.

Obtaining the deviation component e _v(k) of e(k) in the direction perpendicular to the road is relatively easy after the matched road arc is identified. Next, the problem of determining the deviation vector e(k) involves obtaining the error component e _h(k) in the road direction. If the authors select two track points near a turn, one denoted by g(k ₁), which is the point before the turn, and the other denoted by g(k ₂), which is the point after the turn, one knows that:

(8)

$e\lpar k_{\setnum{1}} \rpar \approx e\lpar k_{\setnum{2}} \rpar$

Therefore, the e(k ₂)'s component in the direction of e _v(k ₁) can be calculated by:

(9)

$\vert e_{v} \lpar k_{\setnum{2}} \rpar \vert \lowast \cos \alpha \plus \vert e_{h} \lpar k_{\setnum{2}} \rpar \vert \lowast \sin \alpha$

Thus,

(10 a)

$\vert e_{v} \lpar k_{\setnum{1}} \rpar \vert \approx \vert e_{v} \lpar k_{\setnum{2}} \rpar \vert \lowast \cos \alpha \plus \vert e_{h} \lpar k_{\setnum{2}} \rpar \vert \lowast \sin \alpha$

(10 b)

$\vert e_{h} \lpar k_{\setnum{2}} \rpar \vert \approx \lpar \vert e_{v} \lpar k_{\setnum{1}} \rpar \vert \minus \vert e_{v} \lpar k_{\setnum{2}} \rpar \vert \lowast \cos \alpha \rpar \sol\!\sin \alpha$

(10 c)

$e\lpar k_{\setnum{2}} \rpar \equals e_{v} \lpar k_{\setnum{2}} \rpar \plus e_{h} \lpar k_{\setnum{2}} \rpar \approx e_{v} \lpar k_{\setnum{2}} \rpar \plus {{e_{h} \lpar k_{\setnum{2}} \rpar } \over {\left\vert {e_{h} \lpar k_{\setnum{2}} \rpar } \right\vert}} \lowast \lpar \left\vert {e_{v} \lpar k_{\setnum{1}} \rpar } \right\vert \minus \left\vert {e_{v} \lpar k_{\setnum{2}} \rpar } \right\vert \lowast \cos \alpha \rpar \sol\! \sin \alpha$

By now, the authors have obtained a relatively accurate value of e(k ₂) which includes both the component in the road direction and the component in the direction perpendicular to the road. In practice, the errors of g(k ₁) and g(k ₂) include noise which impact the accuracy and reliability of the differential vector. In light of this, the authors replace |e _v(k ₁)| and |e _v(k ₂)| with $\bar{d}_{\setnum{1}}$ , which represents the average distance between the current road arc and the last C _eff track point matched onto this arc, and $\bar{d}_{\setnum{2}}$ , which is the distance between the last road arc and the last C _eff track point matched onto the arc. Then,

(11)

$e\lpar k_{\setnum{2}} \rpar \approx {{e_{v} \lpar k_{\setnum{2}} \rpar } \over {\vert e_{v} \lpar k_{\setnum{2}} \rpar \vert }}\bar{d}_{\setnum{2}} \plus {{e_{h} \lpar k_{\setnum{2}} \rpar } \over {\vert e_{h} \lpar k_{\setnum{2}} \rpar \vert }}{\rm \lowast \lsqb \lpar }\bar{d}_{\setnum{1}} \minus \bar{d}_{\setnum{2}} {\rm \rpar \lowast }\cos \alpha {\rm \rsqb \sol }\!\sin \alpha$

As a result, the virtual difference is:

(12)

$e_{diff} \equals e\lpar k_{\setnum{2}} \rpar \approx {{e_{v} \lpar k_{\setnum{2}} \rpar } \over {\vert e_{v} \lpar k_{\setnum{2}} \rpar \vert }}\bar{d}_{\setnum{2}} \plus {{e_{h} \lpar k_{\setnum{2}} \rpar } \over {\vert e_{h} \lpar k_{\setnum{2}} \rpar \vert }}\lowast \lpar \bar{d}_{\setnum{1}} \minus \bar{d}_{\setnum{2}} \lowast \cos \alpha \rpar \sol\! \sin \alpha$

4.2. Map-matching of GPS Track Points with e_diff

Once the virtual differential vector is determined, it can be used to correct and map match the track points. First, the authors correct the track point g(k) with e _diff by utilizing the slow drifting property of the GPS main error. As illustrated by Figure 5, $\hat{p}\lpar k\rpar$ is obtained by:

(13)

$\hat{p}\lpar k\rpar \equals g\lpar k\rpar \minus e_{diff}$

Figure 5. Map-matching a track point with the differential vector.

After the correction by e _diff, the accuracy of $\hat{p}\lpar k\rpar$ is improved in both the road direction and the direction perpendicular to the road. However, since the GPS main errors drift slowly, the GPS uncommon errors are random variables and the map errors change along with the movement of the vehicle, $\hat{p}\lpar k\rpar$ is still not the accurate corresponding location of the vehicle on the road. Next, the authors identify the corresponding road arc of $\hat{p}\lpar k\rpar$ with other information, especially the historical matching result, the vehicle's velocity and direction, and the topological structure of the map. Then, $\hat{p}\lpar k\rpar$ is mapped onto $\hat{p}\lpar k\rpar$ 's pedal on the identified road arc to get the matched point p(k).

Although it is relatively easy to identify the corresponding road when the vehicle is away from a junction, the process is not trivial when the vehicle is near a junction. These two conditions need to be considered separately. The distance between $\hat{p}\lpar k\rpar$ and the nearest intersection (big node) is used to judge what situation the current track point belongs to. The authors first obtain two big nodes $\bar{n}_{j} \lpar x_{j} \comma y_{j} \rpar$ and $\bar{n}_{i} \lpar x_{i} \comma y_{i} \rpar$ on the last matched road arc S _i, and then calculate two distances d _ik and d _jk between the currently pre-corrected location $\hat{p}\lpar k\rpar \lpar x_{pk} \comma y_{pk} \rpar$ and $\bar{n}_{j} \lpar x_{j} \comma y_{j} \rpar$ , $\bar{n}_{i} \lpar x_{i} \comma y_{i} \rpar$ .

(14 a)

$d_{ik} \equals \sqrt {\lpar x_{pk} \minus x_{i} \rpar ^{\setnum{2}} \plus \lpar y_{pk} \minus y_{i} \rpar ^{\setnum{2}}}$

(14 b)

$d_{jk} \equals \sqrt {\lpar x_{pk} \minus x_{j} \rpar ^{\setnum{2}} \plus \lpar y_{pk} \minus y_{j} \rpar ^{\setnum{2}}}$

Denote d _effect the threshold indicating $\hat{p}\lpar k\rpar$ is near an intersection (30 m in this study). The bigger the d _effect is, the lower the possibility of false identification. When d _ik⩾d _jk and d _jk<d _effect, $\hat{p}\lpar k\rpar$ is judged to be near the big node $\bar{n}_{j}$ (intersection). When d _jk⩾d _ik and d _ik<d _effect, $\hat{p}\lpar k\rpar$ is judged to be near the big node $\bar{n}_{i}$ (intersection). Otherwise, $\hat{p}\lpar k\rpar$ is judged to be away from any intersections.

When the pre-corrected vehicle position is far away from any intersection and the last matched road arc is S _i, the matched road of $\hat{p}\lpar k\rpar$ is identified as S _i according to the continuity of the vehicle's movement. Accordingly, the matched location p(k) on S _i can be obtained by vertically mapping $\hat{p}\lpar k\rpar$ on S _i.

When the vehicle is near an intersection, the authors need to identify the matched road in conjunction with the information of vehicle movement and the traffic map. They use the vehicle's heading information h(k), the pre-corrected location $\hat{p}\lpar k\rpar$ , and the topological structure of the vector map in the mapping process. When the vehicle's velocity v(k) is smaller than the threshold v _effect (11 km/h in this study), the error of the vehicle's moving direction is significant and its credibility is low. Therefore, whether v(k) is bigger than v _effect needs to be evaluated before using v(k) in calculation. The process is described below.

If v(k)>v _effect, the authors calculate the distances between $\hat{p}\lpar k\rpar$ and every road arc connected with $\bar{n}_{i}$ . Then they identify the nearest arc S _i. If the acute angle β_k of h(k) and the direction of S _i is smaller than the preset threshold β_effect, the mapped road of $\hat{p}\lpar k\rpar$ is identified as S _i and the mapped point p(k) is obtained by vertically mapping $\hat{p}\lpar k\rpar$ onto S _i. If β_k<=β_effect, the nearest arc and the arc judged by the vehicle's moving direction are inconsistent, thus the matched road cannot be identified with certainty. In this case, the authors map $\hat{p}\lpar k\rpar$ onto the big node $\bar{n}_{i}$ . This is a standard method commonly used to deal with the situation when the matched road cannot be identified near an intersection.

4.3. Correcting and Resetting of the Virtual Differential Vector e_diff

In Section 4.1, the authors have introduced the virtual differential vector e _diff. In order to have e _diff keep tracking the changes of GPS errors and road map errors, e _diff needs to be corrected and reset along with the vehicle's movement. As shown in Figure 5, the deviation vector s(k) of the pre-corrected location $\hat{p}\lpar k\rpar$ and its matched point p(k) on the road is mainly caused by two GPS errors, i.e., the drift and random error. Indeed, s(k) is the component of the error change in the direction perpendicular to the road. It can be used to correct the virtual differential vector e _diff to ensure the correction accuracy in the direction perpendicular to the road.

(15)

$e_{diff} \equals e_{diff} \plus \varepsilon \lpar k\rpar \equals e_{diff} \plus \lsqb p\lpar k\rpar \minus \hat{p}\lpar k\rpar \rsqb \equals p\lpar k\rpar \minus g\lpar k\rpar$

Since random GPS error develops along with the vehicle's movement, the authors use the average of the last three distances between GPS track points and the matched point as the smoothed corrector for e _diff. To avoid the disturbance caused by random GPS errors, calculation of e _diff becomes:

(16)

$e_{diff} \equals \sum\limits_{m \equals \setnum{0}}^{\setnum{2}} {\lsqb p\lpar k \minus m\rpar \minus g\lpar k \minus m\rpar \rsqb \sol 3}$

It is worthy of note that e _diff cannot be corrected in such a way at the initial stage when it is assigned. In the cases where the vehicle's matched point cannot be obtained accurately near an intersection, we do not correct e _diff to avoid bringing more error to it.

For the track points obtained along the road segments which are far away from intersections, it is difficult to determine their exact error components in the road direction. Therefore, it is impossible to correct the e _diff component in the road direction in each point matching process. Considering that the vehicle makes turns frequently during the course of movement, we use the same method when assigning e _diff at the initial stage (as introduced in Section 4.1) to reset e _diff at each turn that meets the requirements (7a) and (7b). In this way, the authors can keep the error of e _diff in an acceptable range, especially when the vehicle runs in an urban area.

4.4. Excluding Invalid Track Points

GPS location may be invalid sometimes due to signal impairment or reception problems of the receivers. In this situation, the position data from GPS receivers cannot be used for mapping because they can cause problems in valid GPS track points. These outliers need to be filtered because they would undermine the accuracy and reliability of the map-matching algorithm. The method to filter outliers depends on the locations of the pre-corrected points. After correcting the track point with e _diff, the authors calculate the distance, say, d _c2l between the current pre-corrected point $\hat{p}\lpar k\rpar$ and the last pre-corrected point $\hat{p}\lpar k \minus 1\rpar$ . When the distance is more than the preset threshold d _odd, i.e.,

(17)

$d_{c\setnum{2}l} \gt d_{odd}$

the track point is judged to be invalid and discarded. The threshold was set as 30 metres in this experiment.

4.5. Summary of The New Algorithm

The significance of the proposed algorithm lies most in its simplicity, computational efficiency, and reasonable accuracy. It can be easily programmed for instant application. The algorithm can be implemented step by step as follows:

Step 1: Receive new GPS track information. If e _diff hasn't been initialized, go to Step 2. Otherwise, go to Step 4.
Step 2: Identify the matched road arc with the method introduced in Section 4.1 for the initial stage and map the track point onto the matched road by vertical mapping.
Step 3: Judge whether the requirements (7a) and (7b) are met. If positive, then e _diff is initially assigned by the formula (12) and the processing flow goes to Step 1. Otherwise, go to Step 1 directly.
Step 4: Pre-correct the track point g(k) to obtain $\hat{p}\lpar k\rpar$ . Judge whether the track point is an outlier. If it is an outlier, proceed to Step 1. Otherwise, go to Step 5. If the requirements provided in Section 4.2 for judging whether the track point is near an intersection are met, then go to Step 5. Otherwise, go to Step 6.
Step 5: If v(k)>v _effect then go to Step 7. Otherwise match the track point onto the last mapped point and go to Step 3.
Step 6: Identify the matched road arc as the last matched road arc. Get the mapped point on the matched road by vertical mapping and go to Step 3.
Step 7: If the nearest road arc has the same direction as that of the vehicle, i.e., β_k>β_effect, then identify the nearest road as the matched road, get the mapped point by vertical mapping and go to Step 3. Otherwise, go to Step 8.
Step 8: Map the current track point onto the nearest big node $\bar{n}_{i}$ and go to Step 1.

5. SELECTED RESULTS FROM A REAL-LIFE APPLICATION

The new algorithm, as part of a comprehensive land vehicle navigation project, was examined in Hefei, the capital city of Anhui province of China. The results related to the map-matching algorithm are presented in this section. Table 1 shows a comparison between the new algorithm and the algorithm without the virtual differential pre-correction process but utilizing the information of the vehicle's direction, the vehicle speed, the historical information of the matched road and the topological structure of the map. It is obvious that traditional approach without pre-processing is less effective.

Table 1. Comparison of the Algorithms.

In the test, the authors recorded the pre-corrected locations of raw track data and compared the distances of raw track points to their correct positions and the distances of pre-corrected locations to the corresponding correct positions, the result is shown in Figure 6. The curve on top represents the distances between the raw track points and their corresponding correct locations, and the curve at the bottom represents the distances between the pre-corrected locations and their corresponding correct locations. The horizontal axis is the index of the track points and the vertical axis is the distance to the corresponding correct locations. Approximately 97% of pre-corrected locations are less than 10 metres away from the correct locations, and the other pre-corrected locations are about 20 metres away from the correct locations.

Figure 6. Comparison of errors.

In order to examine the algorithm's capability in correcting map errors, the authors moved the accurate roads to inaccurate positions and map matched the GPS track points onto the map, this is shown in Figure 7. The test results show that the new algorithm works well in correcting the translation map error. For the rotation map error, the new algorithm can partially handle it but the number of inaccurate identifications was found to have increased when the rotation error became larger.

Figure 7. Correction of translation map error and rotation map error.

Figures 8, 9, 10 show the results of another application of the proposed map-matching algorithm in a vehicle navigator with an independent GPS receiver and a less precise traffic map. As the purpose of the sample application is to demonstrate the properties and features of the proposed approach, we use a section of the road network to present the result. Figure 8 shows the raw track points on a section of the road network of Hefei City; Figure 9 shows the pre-corrected result (by the correcting differential e(k)) and final matched points on the map; and Figure 10 shows the same result obtained from a large portion of the city's network.

Figure 8. Raw GPS signals from a section of the test network.

Figure 9. Pre-corrected (left) and corrected result (right).

Figure 10. Pre-corrected (left) and corrected result (right) for a large network.

6. CONCLUDING REMARKS

In this paper, the authors presented a novel virtual differential map-matching algorithm which makes use of the slowly drifting property of the GPS signal error and the continuously drifting character of the vector map error for error correction and map-matching. The core principle of this approach is to develop a virtual differential error from the previous track point matching process and use it to pre-correct later track points before matching them. The algorithm can not only correct GPS signal error in the direction of road but also the component in the direction perpendicular to the road. In addition, it also corrects the potential digital map errors during the map-matching process, which is a neglected problem in existing GPS systems. The property of the algorithm was examined by a real-world application and the result is satisfactory. Several preset parameters were used in this study, for examples, the threshold for the number of track points matched to a road track was six, and the angle threshold of the current road arc and the last road arc was 30°. These parameters were selected based on some published literature; sensitivity analysis should be performed in later studies. In addition, future studies will focus on enhancing the model's capability in correcting digital map errors, especially the rotation error.

ACKNOWLEDGEMENT

This research was supported in part by the National Science Foundation of China, grant number 60272040.

References

REFERENCES

Bao, Y., Liu, Z. (2006). GPS, traffic monitoring and digital map. China National Defense Industry Press.Google Scholar

Bao, Y., Wang, S.-G., Liu, Y. (2004). GIS-based real-time correction of deviation on vehicle tracks. Proceedings of International Conference on Dynamics, Instrumentation and Control, Nanjing, China, pp. 336–344.CrossRef Google Scholar

Blackwell, E. G. (1986). Overview of differential GPS methods. Global Positioning Systems, the Institute of Navigation, 3, pp. 89–100.Google Scholar

Chen, W., Li, Z., Yu, M., and Chen, Y. (2005) Effects of sensor errors on the performance of map-matching. The Journal of Navigation, 58, pp. 273–282.CrossRef Google Scholar

Greenfeld, J. S. (2002). Matching GPS observations to locations on a digital map. 81st Transportation Research Board Annual Meeting, Washington, D.C.Google Scholar

Hide, C., Moore, T., and Smith, M. (2001). Adaptive Kalman filtering algorithms for Low-cost INS/GPS. The Journal of Navigation, 56, pp. 143–152.CrossRef Google Scholar

Honey, S. K., Zavoli, W. B., Milnes, K. A., Phillips, A. C., White, M. S., Loughmiller, G. E. (1989). Vehicle navigational system and method, United States Patent No., 4796191.Google Scholar

Jagadeesh, G. R., Srikanthan, T., and Zhang, X. (2004). A map-matching method for GPS based real-time vehicle location. The Journal of Navigation, 57, pp. 429–440.CrossRef Google Scholar

Jo, T., Haseyamai, M., Kitajima, H. (1996). A map-matching method with the innovation of the Kalman filtering. IEICE Trans. Fund. Electron. Comm. Comput. Sci. E79-A, pp. 1853–1855.Google Scholar

Kim, J. S., Lee, J. H., Kang, T. H., Lee, W. Y., Kim, Y. G. (1996). Node based map-matching algorithm for car navigation system: Proceedings of the 29th International Symposium on Automotive Technology and Automation, Florence, Italy, 10, pp. 121–126.Google Scholar

Kim, S., Kim, J. (2001). Adaptive fuzzy-network based C-measure map-matching algorithm for car navigation system, IEEE Transactions on industrial electronics, 48 (2), 432–440.Google Scholar

Najjar, M. E., Bonnifait, P. (2003). A roadmap-matching method for precise vehicle Localization using belief theory and Kalman filtering. The 11th International Conference in Advanced Robotics, Coimbra, Portugal, June 30–July 3.Google Scholar

Quddus, M. A., Noland, R. B., and Ochieng, W. Y. (2006). A high accuracy fuzzy logic based map-matching algorithm for road transport. Journal of Intelligent Transportation Systems, 10(3), pp. 103–115.CrossRef 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. Proceedings of Transportation Research Board Annual Meeting, Washington, D.C.CrossRef Google Scholar

Ochieng, W. Y., Sauer, K. (2001). Urban road transport navigation requirements: performance of the Global Positioning System after selective availability. Transportation Research Part C, 10, pp. 171–187.CrossRef Google Scholar

Rajashri, R. Joshi. (2001). A new approach to map-matching for in-vehicle navigation systems: the rotational variation metric. Proceedings of IEEE Intelligent Transportation System Conference, Oakland, USA, pp. 33–38.Google Scholar

Shi, W. and Zhu, C. (2002). The line segment match method for extracting road network from high-resolution satellite images. IEEE Trans. Geoscience and Remote Sensing, 40, pp. 511–514.Google Scholar

Syed, S., Cannon, M. E. (2004). Fuzzy logic-based map-matching algorithm for vehicle navigation system in urban canyons. Proceedings of the Institute of Navigation (ION) national technical meeting, January 26–28, California, USA.Google Scholar

Taylor, G., Blewitt, G., Steup, D., Corbett, S., Car, A. (2001). Road reduction filtering for GPS-GIS navigation, Transactions in GIS, 5(3), pp. 193–207.CrossRef Google Scholar

White, C. E., Bernstein, D., Kornhauser, A. L. (2000). Some map-matching algorithms for personal navigation assistants. Transportation Research Part C, 8, pp. 91–108.CrossRef Google Scholar

Yang, D., Cai, B., Yuan, Y. (2003). An improved map-matching algorithm used in vehicle navigation system. IEEE Proceedings on Intelligent Transportation Systems, 2, 1246–1250.Google Scholar