A Method Of Map Matching For Personal Positioning Systems
Kay Kitazawa, Yusuke Konishi, Ryosuke Shibasaki
Ms., Center for Spatial Information Science,
The University of Tokyo
Center for Spatial Information Science,
Institute of Industrial Science
The University of Tokyo
4-6-1 Komaba, Meguro-ku,Tokyo 153-8505
JAPAN
Tel. +81-3-5452-6417 Fax. +81-3-5452-6417
E-mail: kitazawa@iis.u-tokyo.ac.jp
Keywords: Map matching, Positioning, Human, 3D-space, gyro
Abstract
To track human's movements with high accuracy in certain areas, where GPS system is not available, complimentary positioning methods are needed. Personal positioning system using a sensor of acceleration and a gyrocompass together with GPS is now being developed as one of promising methods. Accumulation of positioning errors, however, cannot be avoided. One of the solutions to reduce or modify these errors is "Map matching" technique, which modifies estimated user's position assuming that users are always along road networks.
In this paper, a method of Map Matching for Personal Positioning Systems is proposed. While it has already been in practical use for car navigation systems, its simple algorithm based on distance and direction estimation is not sufficient for tracking of man's complicated movement. In addition, matching should be done for three-dimension maps because human movement consists of both vertical and horizontal motion. The algorithm proposed in this paper combines two of the current algorithms, one of which is based on matching one's shift patterns with shapes of road network, and the other is for a frequent step-by-step adjustment of one's estimated position against outlines of objects around it. Using this integrating algorithm, we propose a new Map Matching method that would give good performance in terms of accuracy of positioning system for human movement in 3D space.
Background
A demand for the accurate positioning technology is increasing. Though several positioning services are already in practical use, there are still some areas left to which radio waves used in such positioning systems cannot reach. Complimentary positioning methods for covering these areas are strongly needed. Though Personal Positioning System using a sensor of acceleration and a gyrocompass together with GPS to trace a person by his/her footsteps and angles is now being developed as one of promising methods, such system calculating one's relative position always accompanies an accumulation of positioning errors. To reduce or prevent these errors to make such system as much accurate as GPS, "Map Matching" technique, which modifies user's estimated position based on the assumption that users are always along road networks on the map is combined with it.
The quite simple algorithm used in current car navigation system is not enough for Personal Positioning System. Data from sensor of acceleration and a gyrocompass such as the number of footsteps and direction is not as accurate as that from sensor of rotation and angle of wheel. In addition, while the assumption used in this algorithm that car runs always on and along roadways allows the system to reconcile the car's estimated position and correspondent point on the center line of road network described by nodes and edges in the database, complicated and various patterns of human's movement cannot be limited to the center line network of roads. For example, it is necessary for a human tracking system to determine on which side of the street or in which floor the user is now walking. (Figure 1.) As a solution of this problem, using three-dimensional database in which roads are represented by polygonal planes, a new map matching method which can cope with unsteadiness of human's movement both for vertical and horizontal direction is proposed in this paper.
Fig. 1 Human can move more freely than cars on road networks
Review:Current Map Mathicng Algorithms
As a beginning, we overview current Map Matching methods and point out their problems to highlight the differences between our approach. Current methods can be classified into two types in large. The first one makes use of distinctive features of both human's shift pattern and road networks to find a corresponding point. In other words, similarity or correlation between the trajectory up to that time (position) and alignment of the road network around is calculated to choose an edge on which user most likely exists when conspicuous change in movements such as turning at corner occurs. The clue for matching is "turn at the corner". Since this is a non-regular event, it often happens that user keeps on going straight without any turn or other distinctive movement and the time interval of matching process is prolonged consequently, which brings accumulation of errors. The other method, on the other hand, just calculates distances between the estimated position and neighboring edges in very short term. Miyata(1991) suggests a methods with frequent calculation that enables relocation of estimated position before it goes too far away from the road networks to find correct point. Though this methods works well to avoid mismatching based on accumulation of errors, the brief algorithm designed for frequent position correction fails to modify the location if once mismatching occurs by selecting wrong edges. It has been shown in recent investigation that the mismatching occurs mainly near crossroads, that is, pros and cons of the second method are complementary to those of the first one. Then the approach we are going to take here uses both algorithms together in the process of map matching.
Main Points of Algorithm
Before we describe the algorithm in detail, we would like to make some remarks on principle and basic structure of it.
