A Method Of Map Matching For Personal Positioning Systems
Principle
We refer to either of two databases, one of which consists of point's data for boundaries of objects and polygons and the other is a network made by nodes and edges. Coordinates and time of each estimated point and each corresponding modified point are separately stored in these databases.
The estimated position at each step is put on the map as it is unless it crosses outlines of objects such as the line of a wall surface. This means we relocate the points not on a network, but on an area of the object. When an intersection is found, the current and previous position is locally modified so that the modified point comes within the correct object. This is based on the frequent modification method. Modified points are used for showing user's position immediately.
Keeping on using this algorithm, if the change of direction (angle) gets bigger than threshold, all of the points included in the trajectory from previous change to that point are globally modified. This algorithm succeeds a judgment of similarity in forms and corrects whole trajectory itself so that the point at which angle changes can fit the corner. The database of network is used in this algorithm.
Local Modification
The estimated position is locally relocated according to the angles made by tracks and an outline when they have an intersection. If the angle is smaller than threshold, we assume that this incorrect positioning is brought by drift errors of gyrocompass and rotate the current point around the former one in proportion to that angle. If the angle is bigger than threshold, the track may hit against outlines because of its error in length (distance). Relocation of the current position is done by adjustment of the length of tracks.
Global Modification
We switch the algorithm for relocation to the global modification when sudden and sharp change of direction occurs between several steps with almost the same direction data. Searching the database of road networks for a crossroads or a curve with similar change in angle around the intersection, the edge on which user most likely locates is chosen. Compared with the shape of corresponding corner, an angle and length of tracks is modified.
Algorithm
The algorithm is shown in flowcharts (Figure 2 , 3)
The main process of Map Matching is as follows.
-
Coordinates and time of the currently estimated and the previous position are obtained from the storage of positional data.(x, y, z, T)
- Tracks expressed by a vector between these two points is calculated
- Errors are modified by coefficients for correction of distance and angle.
- The values of these coefficients are obtained in of the previous Map Matching process.
- Data of the objects near the estimated position is obtained
- Whether the tracks cross the outlines of objects around them is checked. If there is one, we move into process 1. If not, coordinates and time of the estimated position are adopted as those of modified.
- Data of modified current position is obtained and added to the storage of positional data.
Figure 2
Flow chart of Map Matching (Main)
Next, process 1 is as follows.
- Whether intersection point of tracks and outlines is within the object "entrance" is checked. If so, coordinates and time of the estimated position are adopted as those of modified. If not, the whole tracks from the nearest corner are obtained.
- The most recent corner is detected in the tracks by calculating the angle of each step makes and comparing it with threshold. Coordinates and time of the point of the recent corner is obtained.
- Whether there is any entrance object around the intersection or on the same outline is checked. If any, the estimated point is relocated to the most nearest point within entrance area. If not, the angle made by tracks and outlines is measured.
- The whole tracks from the nearest corner are modified so that its end point fit to the point obtained in (9).
- The intersection angle is compared to right angle (90°). If the former is smaller than latter, (12) follows. If not, part of the following process change as annotation * .
- The angle at the intersection is compared to threshold. If the former is smaller than latter, the whole tracks obtained is rotated around the nearest corner point for the cross angle. If not, the estimated point is relocated to the point on the tracks at 30 cm distance from the outline.
* (. If the former is larger than latter, the whole tracks obtained is rotated around the nearest corner point for (180°- the cross angle). If not, the estimated point is relocated to the point on the tracks at 30 cm from the outline. )
- All points on the tracks are modified.
- The ratio of distances of former track and that of after modification and the angle used in (13) are recorded as coefficients for correction of distance and angle.
Figure 3
Flow chart of Map Matching (Process1)
The process of Global matching is as follows.
- Nodes and Edges around the point are obtained from network database.
- The distance between the current and previous position and respectively each node or edge is calculated.
- Select the nearest node if its distance is shorter than threshold, otherwise quit the process.
- Among the edges connected to the nearest node, angle made by each edges and the nearest edge to the previous point.
- Change the shape of tracks from the most recent point with sharp change in angle so that modified point locates on the edge with least difference in angle between the estimated one.
Results and Consideration
With the algorithm explained above, we examined the Map Matching method for tracking human's movement in three-dimensional space. The effectiveness of this series of process was tested by case studies coping with data from the Personal Positioning System and simulations with data consists of ideal value and errors measured in previous research. The results suggested that the combination approach not only be applicable to three dimensional movements but contribute raise accuracy of positioning system for human.
References
- Takeo Miyata, Kazumi Furusawa, Kosuke Thukamoto, 1991. A Method of Map Matching for Automotive Navigation. T.IEE Japan, vol.111-C, No.10, pp.83-89
-
Takeo Miyata, Kazumi Furusawa, Kosuke Thukamoto, 1991. A Method of Error Detection in Map Matching Technique. T.IEE Japan, vol.111-C, No.10, pp.531-532
-
Takeo Miyata, Yoshihiro Kimura, Kosuke Thukamoto, 1994. A Method of Map Matching Using A Low Precision Angular Sensor. Research Report: Faculty of Engineering of Ibaraki University, vol.42, pp.109-115
