=Paper=
{{Paper
|id=Vol-2498/short2
|storemode=property
|title=Pixel-based map matching algorithm for pedestrian dead reckoning system
|pdfUrl=https://ceur-ws.org/Vol-2498/short2.pdf
|volume=Vol-2498
|authors=Yew Fei Tang
|dblpUrl=https://dblp.org/rec/conf/ipin/Tang19
}}
==Pixel-based map matching algorithm for pedestrian dead reckoning system==
https://ceur-ws.org/Vol-2498/short2.pdf
Pixel-based Map Matching Algorithm for Pedestrian
Dead Reckoning System
Y.F. Tang1, Y.X. Zhang, S.W. Hing, S.L. Kan
1 School of Engineering, Nanyang Polytechnic, Singapore
tang_yew_fei@nyp.edu.sg
Abstract. City dwellers spend most of their time indoor. Therefore, indoor
location-based services would have much more potential than outdoor. However,
the width of a typical indoor pathway is 1.3 meter, making the indoor localization
system accuracy a challenge. Moreover, the indoor clutters will scatter signal-
based localization system accuracy unpredictable. Pedestrian dead reckoning
system would be an ideal system. It uses motion sensing involves fusing data
generated by inertial measuring units (IMUs) to compute the user trajectory
relative to the initial position. It is an accurate and a simple system but the drift
in the system make it unreliable for most practical use.
In this paper, we proposed a pixel-based map matching algorithm to minimize
the drift error in a dead reckoning system. The practical results would be
presented in this paper.
Keywords: Indoor Localization, Dead Reckoning System, Multi-sensor, Sensor
Networking, Error Minimization, Internet of Things.
1 Introduction
Pedestrian dead reckoning (PDR) is the process of calculating one's current position the
velocity provide by the system and previously known position. This relative positioning
does not require any site survey or an intensive deployment of infrastructure, making
PDR a very promising cost-effective technology for indoor localization. However, the
relativity will allow error margin in the sensors’ reading to accumulated over time, this
error term as drift. The previously known position had an error, the current position
calculated will include the error and this error will be magnify over time. The error
accumulation over time is random. This make PDR unreliable for practical use.
Map-matching is the process of matching raw positioning data output from a
positioning system to a map or two-dimensional (2D) navigation model depicting the
surrounding physical environment [1-3]. It is first, and commonly used GPS navigation
used outdoor and Geographic Information System (GIS) provide the standard format for
the GPS navigation application [4-6]. However, no standard representation of indoor
environments for indoor map-matching navigation is available [7]. Although indoor
2
architecture floor plan is available, the drawing is using associate with information not
required for indoor map matching navigation.
In this paper, a map matching algorithm is proposed in minimizing the drift in a PDR.
In leveraging on indoor floor plan, pre-determine path could be determined to minimize
the drift in a PDR system.
2 Obtaining Map Information
This is a light weight manual method to obtain map information in assigning pixels to
the corresponding coordinate (long, lat) for the use in indoor navigation with map
matching algorithm. Although, there are automated map generation for navigation
models from building information models [7]. The automated solution would require
extensive for a single floor testing and is usually target whole building map generation.
2.1 Layering
The floor plan must be drawn to scale and converted into softcopy. The floor plan will
go through layering to separate the essential information from non-essential information.
The floor plan was layered into indoor/structural floor plan and the information layer.
Only the indoor/structural floor plan is used in determining the pre-determine path.
An example of a typical floor plan layering is shown in Fig. 1.
Fig. 1. Layering out a typical floor plan
2.2 Pixelization
The digitalized indoor/structural floor plan will have each pixel presents a coordinate
(latitude, longitude). The solid pixels or black pixels will represent walls or obstacles
that will prevent the localization system to make its location on it or cross it. Thereby,
creating allowable and non-allowable pixels for the localization system to navigate
within these pixels. The continuity of the allowable pixels will be the pre-determine
path containing the navigation of a PDR system. This will enhance accuracy and
prevent localization system from navigate into the walls or over the walls.
3
2.3 Coordinate Assignment
The outline of the indoor floor plan is overlay onto the building outline in a Google
map as shown in Fig. 2 Once outline of the indoor floor plan is aligned onto the Google
map building outline. The indoor floor plan circumference coordinate could be
obtained, and each pixel’s coordinate could be determined. The resolution could be
reduced to minimize the system resources.
Fig. 2. Mapping the outline of the indoor floor plan onto Google Map to obtain the
coordinates for each pixels in the indoor floor plan
3 Map Matching Algorithm
A pre-defined path will be defined to contain the PDR value within a certain range.
The PDR reading will be moved to the pre-defined path pixels with k nearest algorithm.
Since the biggest problem from PDR is it is not calibratable when error accumulated
along with the time, we have used map matching algorithm applied on every raw point
from PDR and iteratively compared distance to the nearest path and nearest pixels.
After calibrated to the nearest pixel in the predefined path, the accumulated error will
be significantly limited to an acceptable range.
Fig. 3a shows the process flow. At the beginning of the tracking, an initial tracking
location together with the initial direction obtained from magnetometer is required for
the system. The start point does not need to be accurate because the map matching
system will assign it to the nearest pixel on the nearest path. There are two steps to
determine the nearest pixel. The graphical explanation is shown in Fig. 3b. The initial
direction of the moving direction as in Fig. 3b(i) is obtained from the magnetometer
and subsequent direction is determined by the gyroscope. The predefined paths
directions with the initial direction determined by the magnetometer or the gyroscope
will filter out all predefined path pixel located in the irrelevant direction as shown in
Fig. 3b(ii). To determine the nearest pixel along the remaining paths. The existing
location coordinates will compute the distances between its coordinates with the pixels
coordinates along the pre-determine path as shown in Fig. 3b(iii). The existing location
coordinates will be replaced with the nearest coordinates in the pre-defined path as
shown in Fig. 3b(iv). Iteratively, with movement sensed by IMU unit, previous
assigned point together with step length and direction changed will be used to calculate
the next predicted location and the final location will be assigned on the nearest pixel
using the same strategy.
4
Fig. 3. (a) Map matching algorithm flowchart (b) Map matching algorithm example
Since, the algorithm will restrict the tracking within the pre-defined path, error will
be significant at the turning of the cross junction where the PDR error accumulated could
be overshoot or undershoot. This error will disallow the turning since the predicted
location will be either after the cross junction or before the cross junction depending on
the error is overshoot or undershoot. This drift error is random. In different situations
it may mislead the next path decision in making turns.
Based on PDR practical result and typical steps sizes, in a straight-line pre-define
path, the error accumulation does not exceed 4 meters. This indicate the system
localization error with map matching is 4 meters and below or the misstep error is limited
to slightly more 2 steps size. In factoring the system localization error in the system
decision to determine if a turning is genuine. The allowable turn area is set to the current
point to the nearest turn is ± 4 meters. The diagrams showing the errors undershoot (A)
and overshoot (B) at the cross junction is shown in Fig. 4. If the predicted location is
within ± 4 meters of the entrant point of the junction and a change of direction in the
system, the previous direction will be disregarded, the calibrated position will be the
entrant point of the nearest cross junction.
However, if a change of direction not within ± 4 meters of the entrant point of the
junction, the previous direction will be considered as the factor. The next path of
pedestrian will be the previous nearest facing path of the previous direction. This auto-
calibrate the PDR direction error from the gyroscope or the magnetometer.
5
Fig. 4. Map matching algorithm for turning corners for undershoot situation (A), overshoot
situation (B)
4 Experimental Results and Discussion
A PDR localization system based on accelerometer, gyroscope and magnetometer is
developed on Android platform. The device used here is Samsung Note 4+. One device
is with PDR localization system while another is using the same localization system
with map matching algorithm mentioned in Section 3. The laboratory indoor map
coordinates are extracted as discussed in Section 2.
An initial starting point is pre-defined and the coordinated is marked out together
with a set of check points. The purpose of having the check points are mapped out is
to the tester to record the reading at the same location for over 50 cycle of testing. This
would provide consistency in having the test repeated for 50 cycles and reading taken
in the exact same location. The test is carried with 34 pre-defined measurement points
and test setup with two phones (same model). The test path is designed to have a
reasonable number of turns and distance. One mobile phone will have a PDR with map
matching algorithm while the other without on a notepad board to ensure both systems
are subject to the same physical movement and conditions during each test cycle.
Fig. 5 show how the distance error is measured with the predicated position by system
with reference to the pre-defined path. The distance error from the pre-defined path
for system with map matching is termed as ∆ . ∆ is the distance after the predicted
point is move to the nearest neighbor on the pre-defined path. The distance error ∆ is
measured directly from the predicted point by the system without map matching with
respect to the pre-defined path.
6
Fig. 5. Map matching algorithm in assigning the reading out value to the nearest neighbor in pre-
defined path pixel with k nearest neighbor algorithm
The mean distance error at each check points for system with and without map matching
algorithm for 50 cycles is shown in Fig. 6. The result shows the mean distance error at
each check point for the system with map matching algorithm is constantly below the
system without map matching. The average mean distance error is 2.07 meter and 6.13
meter for system with map matching and without map matching respectively. This
suggest a drastic improvement in the distance error in using map matching algorithm.
Fig. 6. Mean error value for each cycle
In Fig. 7 shows the variance and standard deviation at each checkpoint over 50
cycles. The variance and standard deviation are constantly lower in the system with map
matching algorithm over the system without. This indicate the data produced by system
with map matching is more consistent and closer to the mean value of the predicted
value.
In Fig.8 show the improvement factors for each test cycle. The improvement factor per
cycle, is calculated using the equation Γ=(∆2-∆1)/∆1 , where Γ is the improvement factor
per sample. A linear trend line shows an approximate 55% improvement could be
achieved using the map matching algorithm.
7
Fig. 7. Variance (y-axis on the left) and Standard Deviation (y-axis on the right) at each
checkpoints (x-axis) over 50 cycles for system with and without map matching algorithm
Common techniques used in error correction in PDR uses estimating the step length
and orientation change of each stride observing the characteristics of the IMU reading
during steps [8,9] or if the IMU is located at the pedestrian’s feet, an inertial navigation
system (INS) [10] is used to correct the zero velocity UPdaTes (ZUPT) during the stance
phases of step. Estimating the step length and orientation offers a flexible method but
an increase in error after each step persist. INS offer better positioning at the cost of
limiting the possible positions of the IMU (at the shoe).
However, our lightweight solution allows indoor map information transfer for our map
matching algorithm to minimize error in the PDR navigation system. In confining the
navigation space of each steps and allow every turn to perform system calibration to
auto-correct the errors accumulated. The system drift could be contained within a finite
time of each cornering.
Fig. 8. Average improvement factor
The results had showed a drastic improvement in the system using map matching
algorithm in term of accuracy and more consistently closer to the mean predicted value.
8
5 Conclusion
In this paper, we had proven a lightweight map matching algorithm through an
experiment could drastically improve the system error. This map matching algorithm
uses each cornering to auto-correct the drift. It also restricts the PDR predicted value
from drifting away too far from the pre-define path or over across the wall, which is
not possible logically. In pre-define the space of movement and calibrating at each
cornering, the errors had reduced significantly to a mean system error of 2.07 meters.
The value is also closer to the mean system error, smaller error deviation, which make
it less noise. The average improvement factor over each had reduced by approximately
by 55%. This map matching algorithm is not restricted for PDR use and could be
extended to other indoor navigation platform to improve the accuracy.
Acknowledgement
The authors acknowledge the support of the Translational and Innovation Fund
(MOE2017-TIF-1-G-028) provided by Ministry of Education, Singapore. The work is
carried out wholly in Nanyang Polytechnic premise.
References
1. G. Ta ylor, G. Blewitt, Intelligent Positioning: GIS–GPS Unification, John Wiley & Sons
Ltd, 2006.
2. X. Zhang, Q. Wang, W. Wan, The relationship among vehicle positioning performance, Map
Quality and Sensitivities and Feasibilities of Map-Matching Algorithms. IEEE Proc
Intelligent Vehicles Symposium 2003, pp. 468–473.
3. M.A. Quddus, R.B. Noland, W.Y. Ochieng, The effects of navigation sensors and spatial
road network data quality on the performance of map matching algorithms, GeoInformatica
13 (1) (2009) 85–108.
4. H.A. Karimi, T. Conahan, D. Roongpiboonsopit, A methodology for predicting
performances of map-matching algorithms, in: J.D. Carswell, T. Tezuka (Eds.), The 6th
International Symposium on Web and Wireless Geographical Information Systems, Lecture
Notes in Computer Science, Springer, Berlin 2006, pp. 202–213.
5. S. Taneja, B. Akinci, J. H. Garrett, and L. Soibelman, “Algorithms for automated generation
of navigation models from building information models to support indoor map-matching,”
Automation in Construction, vol. 61, 2016, pp. 24–41.
6. Q. Ladetto, J. V. Seeters, S. Sokolowski, Z. Sagan, and B. Merminod, “Digital Magnetic
Compass and Gyroscope for Dismounted Soldier
Position and Navigation,” Sensors & Electronics Technology Panel, NATO Research and
Technology Agency Sensors, pp. 1–15, 2002.
7. R. Stirling, “Development of a Pedestrian Navigation System Using Shoe Mounted
Sensors,” Master’s thesis, University of Alberta, 2004.
8. D. Titterton and J. Weston, Strapdown Inertial Navigation Technology. The American
Institute of Aeronautics and Astronautics, second ed.,
2004.