GPS World

Tag: pedestrian navigation

  • Innovation: Checking the accuracy of an inertial-based pedestrian navigation system with a drone

    Innovation: Checking the accuracy of an inertial-based pedestrian navigation system with a drone

    I’m Walking Here!

    INNOVATION INSIGHTS with Richard Langley

    OVER THE YEARS, many philosophers tried to describe the phenomenon of inertia but it was Newton, in his Philosophiæ Naturalis Principia Mathematica, who unified the states of rest and movement in his First Law of Motion. One rendering of this law states: Every body continues in its state of rest, or of uniform motion in a straight line, unless it is compelled to change that state by forces impressed upon it. Newton didn’t actually use the word inertia in describing the phenomenon, but that is how we now refer to it.

    In his other two laws of motion, Newton describes how a force (including that of gravity) can accelerate a body. And as we all know, acceleration is the rate of change of velocity, and velocity is the rate of change of position. So, if the acceleration vector of a body can be precisely measured, then a double integration of it can provide an estimate of the body’s position. That sounds quite straightforward, but the devil is in the details. Not only do we have to worry about the constants of integration (or the initial conditions of velocity and position), but also the direction of the acceleration vector and its orthogonal components. Nevertheless, the first attempts at mechanizing the equations of motion to produce what we call an inertial measurement unit or IMU were made before and during World War II to guide rockets.

    Nowadays, IMUs typically consist of three orthogonal accelerometers and three orthogonal rate-gyroscopes to provide the position and orientation of the body to which it is attached. And ever since the first units were developed, scientists and engineers have worked to miniaturize them. We now have micro-electro-mechanical systems (or MEMS) versions of them so small that they can be housed in small packages with dimensions of a few centimeters or embedded in other devices.

    One problem with IMUs, and with the less-costly MEMS IMUs in particular, is that they have biases that grow with time. One way to limit these biases is to periodically use another technique, such as GNSS, to ameliorate their effects. But what if GNSS is unavailable? Well, in this month’s column we take a look at an ingenious technique that makes use of how the human body works to develop an accurate pedestrian navigation system — one whose accuracy has been checked using drone imagery. As they might say in New York, “Hey, I’m walking (with accuracy) here!”

    Satellite navigation systems have achieved great success in personal positioning applications.

    Nowadays, GNSS is an essential tool for outdoor navigation, but locating a user’s position in degraded and denied indoor environments is still a challenging task. During the past decade, methodologies have been proposed based on inertial sensors for determining a person’s location to solve this problem.

    One such solution is a personal pedestrian dead-reckoning (PDR) system, which helps in obtaining a seamless indoor/outdoor position. Built-in sensors measure the acceleration to determine pace count and estimate the pace length to predict position with heading information coming from angular sensors such as magnetometers or gyroscopes. PDR positioning solutions find many applications in security monitoring, personal services, navigation in shopping centers and hospitals and for guiding blind pedestrians.

    Several dead-reckoning navigation algorithms for use with inertial measurement units (IMUs) have been proposed. However, these solutions are very sensitive to the alignment of the sensor units, the inherent instrumental errors, and disturbances from the ambient environment — problems that cause accuracy to decrease over time. In such situations, additional sensors are often used together with an IMU, such as ZigBee radio beacons with position estimated from received signal strength.

    In this article, we present a PDR indoor positioning system we designed, tested and analyzed. It is based on the pace detection of a foot-mounted IMU, with the use of extended Kalman filter (EKF) algorithms to estimate the errors accumulated by the sensors.

    PDR DESIGN AND POSITIONING METHOD

    Our plan in designing a pedestrian positioning system was to use a high-rate IMU device strapped onto the pedestrian’s shoe together with an EKF-based framework. The main idea of this project was to use filtering algorithms to estimate the errors (biases) accumulated by the IMU sensors. The EKF is updated with velocity and angular rate measurements by zero-velocity updates (ZUPTs) and zero-angular-rate updates (ZARUs) separately detected when the pedestrian’s foot is on the ground. Then, the sensor biases are compensated with the estimated errors.

    Therefore, the frequent use of ZUPT and ZARU measurements consistently bounds many of the errors and, as a result, even relatively low-cost sensors can provide useful navigation performance. The PDR framework, developed in a Matlab environment, consists of five algorithms:

    • Initial alignment that calculates the initial attitude with the static data of accelerometers and magnetometers during the first few minutes.
    • IMU mechanization algorithm to compute the navigation parameters (position, velocity and attitude).
    • Pace detection algorithm to determine when the foot is on the ground; that is, when the velocity and angular rates of the IMU are zero.
    • ZUPT and ZARU, which feed the EKF with the measured errors when pacing is detected.
    • EFK estimation of the errors, providing feedback to the IMU mechanization algorithm.

    INITIAL ALIGNMENT OF IMU SENSOR

    The initial alignment of an IMU sensor is accomplished in two steps: leveling and gyroscope compassing. Leveling refers to getting the roll and pitch using the acceleration, and gyroscope compassing refers to obtaining heading using the angular rate.

    However, the bias and noise of gyroscopes are larger than the value of the Earth’s rotation rate for the micro-electro-mechanical system (MEMS) IMU, so the heading has a significant error. In our work, the initial alignment of the MEMS IMU is completed using the static data of accelerometers and magnetometers during the first few minutes, and a method for heading was developed using the magnetometers.

    PACE-DETECTION PROCESS

    When a person walks, the movement of a foot-mounted IMU can be divided into two phases. The first one is the swing phase, which means the IMU is on the move. The second one is the stance phase, which means the IMU is on the ground. The angular and linear velocity of the foot-mounted IMU must be very close to zero in the stance phase. Therefore, the angular and linear velocity of the IMU can be nulled and provided to the EKF. This is the main idea of the ZUPT and ZARU method.

    There are a few algorithms in the literature for step detection based on acceleration and angular rate. In our work, we use a multi-condition algorithm to complete the pace detection by using the outputs of accelerometers and gyroscopes.

    As the acceleration of gravity, the magnitude of the acceleration ( |αk|  ) for epoch k must be between two thresholds. If

    Source: GPS World

    (1)

    then, condition 1 is

      (2)

    with units of meters per second squared. The acceleration variance must also be above a given threshold. With

      (3)

    where   is a mean acceleration value at time k, and s is the size of the averaging window (typically, s = 15 epochs), the variance is computed by:

    .  (4)

    The second condition, based on the standard deviation of the acceleration, is computed by:

    .  (5)

    The magnitude of the angular rate ( ) given by:

      (6)

    must be below a given threshold:

      .  (7)

    The three logical conditions must be satisfied at the same time, which means logical ANDs are used to combine the conditions:

    C = C1 & C2 & C3.  (8)

    The final logical result is obtained using a median filter with a neighboring window of 11 samples. A logical 1 denotes the stance phase, which means the instrumented-foot is on the ground.

    EXPERIMENTAL RESULTS

    The presented method for PDR navigation was tested in both indoor and outdoor environments. For the outdoor experiment (the indoor test is not reported here), three separate tests of normal, fast and slow walking speeds with the IMU attached to a person’s foot (see FIGURE 1) were conducted on the roof of the Institute of Space Science and Technology building at Nanchang University (see FIGURE 2). The IMU was configured to output data at a sampling rate of 100 Hz for each test.

    FIGURE 1. IMU sensor and setup. (Image: Authors)
    FIGURE 1. IMU sensor and setup. (Image: Authors)
    FIGURE 2. Experimental environment. (Image: Authors)
    FIGURE 2. Experimental environment. (Image: Authors)

    For experimental purposes, the user interface was prepared in a Matlab environment. After collection, the data was processed according to our developed indoor pedestrian dead-reckoning system. The processing steps were as follows: Setting the sampling rate to 100 Hz; setting initial alignment time to 120 seconds; downloading the IMU data and importing the collected data at the same time; selecting the error compensation mode (ZARU + ZUPT as the measured value of the EKF); downloading the actual path with a real measured trajectory with which to compare the results (in the indoor-environment case).

    For comparison of the IMU results in an outdoor environment, a professional drone was used (see FIGURE 3) to take a vertical image of the test area (see FIGURE 4). Precise raster rectification of the image was carried out using Softline’s C-GEO v.8 geodetic software. This operation is usually done by loading a raster-image file and entering a minimum of two control points (for a Helmert transformation) or a minimum of three control points (for an affine transformation) on the raster image for which object space coordinates are known. These points are entered into a table. After specifying a point number, appropriate coordinates are fetched from the working set. Next, the points in the raster image corresponding to the entered control points are indicated with a mouse.

    FIGURE 3. Professional drone. (Photo: DJI)
    FIGURE 3. Professional drone. (Photo: DJI)

    For our test, we measured four ground points using a GNSS receiver (marked in black in Figure 4), to be easily recognized on the raster image (when zoomed in). A pre-existing base station on the roof was also used. To compute precise static GPS/GLONASS/BeiDou positions of the four ground points, we used post-processing software. During the GNSS measurements, 16 satellites were visible. After post-processing of the GNSS data, the estimated horizontal standard deviation for all points did not exceed 0.01 meters. The results were transformed to the UTM (zone 50) grid system. For raster rectification, we used the four measured terrain points as control points. After the Helmert transformation process, the final coordinate fitting error was close to 0.02 meters.

    FIGURE 4. IMU PDR (ZUPT + ZARU) results on rectified raster image. (Image: Authors)
    FIGURE 4. IMU PDR (ZUPT + ZARU) results on rectified raster image. (Image: Authors)

    For comparing the results of the three different walking-speed experiments, IMU stepping points (floor lamps) were chosen as predetermined route points with known UTM coordinates, which were obtained after raster image rectification in the geodetic software (marked in red in Figure 4).

    After synchronization of the IMU (with ZUPT and ZARU) and precise image rectification, positions were determined and are plotted in Figure 4. The trajectory reference distance was 15.1 meters.

    PDR positioning results of the slow-walking test with ZARU and ZUPT corrections were compared to the rectified raster-image coordinates. The coordinate differences are presented in FIGURE 5 and TABLE 1.

    FIGURE 5. Differences in the coordinates between the IMU slow-walking positioning results and the rectified raster-image results. (Chart: Authors)
    FIGURE 5. Differences in the coordinates between the IMU slow-walking positioning results and the rectified raster-image results. (Chart: Authors)

     

    Table 1. Summary of coordinate differences between the IMU slow-walking positioning results and the rectified raster-image results. (Data: Authors)
    Table 1. Summary of coordinate differences between the IMU slow-walking positioning results and the rectified raster-image results. (Data: Authors)

    The last two parts of the experiment were carried out to test normal and fast walking speeds. The comparisons of the IMU positioning results to the “true” positions extracted from the calibrated raster image are presented in FIGURES 6 and 7 and TABLES 2 and 3.

    FIGURE 6. Differences in the coordinates between the IMU normal-walking positioning results and the rectified raster-image results. (Chart: Authors)
    FIGURE 6. Differences in the coordinates between the IMU normal-walking positioning results and the rectified raster-image results. (Chart: Authors)
    FIGURE 7. Differences in the coordinates between the IMU fast-walking positioning results and the rectified raster-image results. (Chart: Authors)
    FIGURE 7. Differences in the coordinates between the IMU fast-walking positioning results and the rectified raster-image results. (Chart: Authors)
    Table 2. Summary of coordinate differences between the IMU normal-walking positioning results and the rectified raster-image results. (Data: Authors)
    Table 2. Summary of coordinate differences between the IMU normal-walking positioning results and the rectified raster-image results. (Data: Authors)
    Table 3. Summary of coordinate differences between the IMU fast-walking positioning results and the rectified raster-image results. (Data: Authors)
    Table 3. Summary of coordinate differences between the IMU fast-walking positioning results and the rectified raster-image results. (Data: Authors)

    From the presented results, we can observe that the processed data of the 100-Hz IMU device provides a decimeter-level of accuracy for all cases. The best results were achieved with a normal walking speed, where the positioning error did not exceed 0.16 meters (standard deviation). It appears that the sampling rate of 100 Hz makes the system more responsive to the authenticity of the gait.

    However, we are aware that the test trajectory was short, and that, due to the inherent drift errors of accelerometers and gyroscopes, the velocity and positions obtained by these sensors may be reliable only for a short period of time. To solve this problem, we are considering additional IMU position updating methods, especially for indoor environments.

    CONCLUSIONS

    We have presented results of our inertial-based pedestrian navigation system (or PDR) using an IMU sensor strapped onto a person’s foot. An EKF was applied and updated with velocity and angular rate measurements from ZUPT and ZARU solutions.

    After comparing the ZUPT and ZARU combined final results to the coordinates obtained after raster-image rectification using a four-control-point Helmert transformation, the PDR positioning results showed that the accuracy error of normal walking did not exceed 0.16 meters (at the one-standard-deviation level). In the case of fast and slow walking, the errors did not exceed 0.20 meters and 0.32 meters (both at the one-standard-deviation level), respectively (see Table 4 for combined results).

    Table 4. Summary of coordinate differences between the IMU slow-, normal- and fast-walking positioning results and the rectified raster-image results. (Data: Authors)
    Table 4. Summary of coordinate differences between the IMU slow-, normal- and fast-walking positioning results and the rectified raster-image results. (Data: Authors)

    The three sets of experimental results showed that the proposed ZUPT and ZARU combination is suitable for pace detection; this approach helps to calculate precise position and distance traveled, and estimate accumulated sensor error.

    It is evident that the inherent drift errors of accelerometers and gyroscopes, and the velocity and position obtained by these sensors, may only be reliable for a short period of time. To solve this problem, we are considering additional IMU position-updating methods, especially in indoor environments. Our work is now focused on obtaining absolute positioning updates with other methods, such as ZigBee, radio-frequency identification, Wi-Fi and image-based systems.

    ACKNOWLEDGMENTS

    The work reported in this article was supported by the National Key Technologies R&D Program and the National Natural Science Foundation of China. Thanks to NovAtel for providing the latest test version of its post-processing software for the purposes of this experiment. Special thanks also to students from the Navigation Group of the Institute of Space Science and Technology at Nanchang University and to Yuhao Wang for his support of drone surveying.

    MANUFACTURERS

    The high-rate IMU used in our work was an Xsense MTi miniature MEMS-based Attitude Heading Reference System. We also used NovAtel’s Waypoint GrafNav v. 8.60 post-processing software and a DJI Phantom 3 drone.

    MARCIN URADZIŃSKI received his Ph.D. from the Faculty of Geodesy, Geospatial and Civil Engineering of the University of Warmia and Mazury (UWM), Olsztyn, Poland, with emphasis on satellite positioning and navigation. He is an assistant professor at UWM and presently is a visiting professor at Nanchang University, China. His interests include satellite positioning, multi-sensor integrated navigation and indoor radio navigation systems.

    HANG GUO received his Ph.D. in geomatics and geodesy from Wuhan University, China, with emphasis on navigation. He is a professor of the Academy of Space Technology at Nanchang University. His interests include indoor positioning, multi-sensor integrated navigation systems and GNSS meteorology. As the corresponding author for this article, he may be reached at [email protected].

    CLIFFORD MUGNIER received his B.A. in geography and mathematics from Northwestern State University, Natchitoches, Louisiana, in 1967. He is a fellow of the American Society for Photogrammetry and Remote Sensing and is past national director of the Photogrammetric Applications Division. He is the chief of geodesy in the Department of Civil and Environmental Engineering at Louisiana State University, Baton Rouge. His research is primarily on the geodesy of subsidence in Louisiana and the grids and datums of the world.

    FURTHER READING

    • Authors’ Work on Indoor Pedestrian Navigation

    “Indoor Positioning Based on Foot-mounted IMU” by H. Guo, M. Uradziński, H. Yin and M. Yu in Bulletin of the Polish Academy of Sciences: Technical Sciences, Vol. 63, No. 3, Sept. 2015, pp. 629–634, doi: 10.1515/bpasts-2015-0074.

    “Usefulness of Nonlinear Interpolation and Particle Filter in Zigbee Indoor Positioning” by X. Zhang, H. Guo, H. Wu and M. Uradziński in Geodesy and Cartography, Vol. 63, No. 2, 2014, pp. 219–233, doi: 10.2478/geocart-2014-0016.

    • IMU Pedestrian Navigation

    “Pedestrian Tracking Using Inertial Sensors” by R. Feliz Alonso, E. Zalama Casanova and J.G. Gómez Garcia-Bermejo in Journal of Physical Agents, Vol. 3, No. 1, Jan. 2009, pp. 35–43, doi: 10.14198/JoPha.2009.3.1.05.

    “Pedestrian Tracking with Shoe-Mounted Inertial Sensors” by E. Foxlin in IEEE Computer Graphics and Applications, Vol. 25, No. 6, Nov./Dec. 2005, pp. 38–46, doi: 10.1109/MCG.2005.140.

    • Pedestrian Navigation with IMUs and Other Sensors

    “Foot Pose Estimation Using an Inertial Sensor Unit and Two Distance Sensors” by P.D. Duong, and Y.S. Suh in Sensors, Vol. 15, No. 7, 2015, pp. 15888–15902, doi: 10.3390/s150715888.

    “Getting Closer to Everywhere: Accurately Tracking Smartphones Indoors” by R. Faragher and R. Harle in GPS World, Vol. 24, No. 10, Oct. 2013, pp. 43–49.

    “Enhancing Indoor Inertial Pedestrian Navigation Using a Shoe-Worn Marker” by M. Placer and S. Kovačič in Sensors, Vol. 13, No. 8, 2013, pp. 9836–9859, doi: 10.3390/s130809836.

    “Use of High Sensitivity GNSS Receiver Doppler Measurements for Indoor Pedestrian Dead Reckoning” by Z. He, V. Renaudin, M.G. Petovello and G. Lachapelle in Sensors, Vol. 13, No. 4, 2013, pp. 4303–4326, doi: 10.3390/s130404303.

    “Accurate Pedestrian Indoor Navigation by Tightly Coupling Foot-Mounted IMU and RFID Measurements” by A. Ramón Jiménez Ruiz, F. Seco Granja, J. Carlos Prieto Honorato and J. I. Guevara Rosas in IEEE Transactions on Instrumentation and Measurement, Vol. 61, No. 1, Jan. 2012, pp. 178–189, doi: 10.1109/TIM.2011.2159317.

    • Pedestrian Navigation with Kalman Filter Framework

    “Indoor Pedestrian Navigation Using an INS/EKF Framework for Yaw Drift Reduction and a Foot-mounted IMU” by A.R. Jiménez, F. Seco, J.C. Prieto and J. Guevara in Proceedings of WPNC’10, the 7th Workshop on Positioning, Navigation and Communication held in Dresden, Germany, March 11–12, 2010, doi: 10.1109/WPNC.2010.5649300.

    • Navigation with Particle Filtering

    “Street Smart: 3D City Mapping and Modeling for Positioning with Multi-GNSS” by L.-T. Hsu, S. Miura and S. Kamijo in GPS World, Vol. 26, No. 7, July 2015, pp. 36–43.

    • Zero Velocity Detection

    “A Robust Method to Detect Zero Velocity for Improved 3D Personal Navigation Using Inertial Sensors” by Z. Xu, J. Wei, B. Zhang and W. Yang in Sensors Vol. 15, No. 4, 2015, pp. 7708–7727, doi: 10.3390/s150407708.

  • Street Smart: 3D City Mapping and Modeling for Positioning with Multi-GNSS

    Street Smart: 3D City Mapping and Modeling for Positioning with Multi-GNSS

    Figure 1. Example of the GNSS signal propagation using ray-tracing and a 3D building map.
    Figure 1. Example of the GNSS signal propagation using ray-tracing and a 3D building map.

    A particle-filter-based positioning method using a 3D map to rectify the errors created by multipath and non-line-of-sight signals on the positioning result delivered by a low-cost single-frequency GPS receiver takes a multi-GNSS approach, using the combined signals of GPS, GLONASS and QZSS. The method outperforms conventional positioning in availability and positioning accuracy. It will likely be fused with other sensors in a future pedestrian navigation application.

    By Li-Ta Hsu, Shunsuke Miura and Shunsuke Kamijo

    GPS provides an accurate and reliable positioning/timing service for pedestrian application in open field environments. Unfortunately, its positioning performance in urban areas still has a lot of room for  improvement, due to signal blockages and reflections caused by tall buildings. The signal reflections can be divided into multipath and non-line-of-sight (NLOS) effects. Recently, use of 3D building models as aiding information to mitigate or exclude multipath and NLOS effects has become a promising area of study.

    At first, researchers used the 3D map model to simulate multipath effects to assess the single-reflection environment of a city. Subsequently, the metric of NLOS signal exclusion using an elevation-enhanced map, extracted from a 3D map, was developed and tested using real vehicular data. An extended idea of identifying NLOS signals using an infrared camera onboard a vehicle has been suggested. The potential of using a dynamic 3D map to design a multipath-exclusion filter for a vehicle-based tightly coupled GPS/INS integration system has also been studied. A forecast satellite visibility based on a 3D urban model to exclude NLOS signals in urban areas was developed.

    The research approaches outlined above seek to exclude the NLOS signal; however, the exclusion is very likely to cause a horizontal dilution of precision distortion scenario, due to the blockage of buildings along the two sides of streets. In other words, the lateral (cross direction) positioning error would be much larger than that of the along-track direction.

    Therefore, approaches applying multipath and NLOS signals as measurements become essential. One of the most common methods, the shadow-matching method, uses 3D building models to predict satellite visibility and compare it with measured satellite visibility to improve the cross street positioning accuracy. A multipath and NLOS delay estimation based on software-defined radio and a 3D surface model based on a particle filter was proposed and tested in a static experiment in the Shinjuku area of Tokyo.The research team of The University of Tokyo developed a particle-filter-based positioning method using a 3D map to rectify the positioning result of commercial GPS single-frequency receiver for pedestrian applications.

    An evaluation of the QZSS L1-submeter-class augmentation with integrity function (L1-SAIF) correction to the proposed pedestrian positioning method was also discussed in an earlier paper by the authors of this article. However, satellite visibility in the urban canyon using only GPS and QZSS would not be enough for this proposed method. The use of emerging multi-GNSS, encompassing GLONASS, Galileo and BeiDou, could furnish a potential solution to the lack of visible satellites for this method. This article assess the performance of the proposed pedestrian positioning method using GPS, GLONASS and QZSS.

    Building Models Construction

    Our work established a 3D building model by a 2D map that contained building location and height information of buildings from 3D point-clouds data. The Fundamental Geospatial Data (FGD) of Japan, which provided by Japan geospatial information authority, is open to the Japanese public. This FGD data is employed as 2D geographic information system (GIS) data. Thus, the layouts and positions of every building on the map could be obtained from the 2D GIS data. In this article, the 3D digital surface model (DSM) data is provided by Aero Asahi Corporation. Figure 2 shows the process of constructing the 3D building model used here. This process first extracts the coordinates of every building corner from FGD as shown in the left of Figure 2. Then, the 2D map is integrated with the height data from DSM. The right of Figure 2 illustrates an example of a 3D building model established in this way. The 3D building map contains a  very small amount of data for each building in comparison to that of the 3D graphic application. For our purposes, the file only contains the frame data of each building instead of the detail polygons data. This basic 3D building map is utilized in the simulation of ray-tracing.

    Figure 2. The construction of the 3D building map from a 2D map and DSM.
    Figure 2. The construction of the 3D building map from a 2D map and DSM.

    Our version of the ray-tracing method does not consider diffractions or multiple reflections because these signals occurred under unfavorable conditions. Here, we utilize only the direct path and a single reflected path. The developed ray-tracing simulation can be used to distinguish reflected rays and to estimate the reflection delay distance. Our research work assumes that the surfaces of buildings are reflective smooth planes, that is, mirrors. Therefore, the rays in the simulation obey the laws of reflection. In the real world, the roughness and the absorption of the reflective surface might create a mismatch between the ray-tracing simulation and the real propagation. Here we ignore this effect, as the roughness of the building surface is much smaller than the propagation distance.

    The opening figure (Figure 1) shows an example of the GNSS signal propagation using ray-tracing and a 3D building map. Red, green and white lines denote the LOS path, reflected paths and the NLOS paths, respectively. In this environment, a conventional positioning method such as weighted least squares (WLS) usually estimates the position on the wrong side of street as shown in the red balloon. With the aid of 3D building model and ray-tracing, the map-based positioning method is able to provide a result close to the ground truth.

    Map-Based Pedestrian Positioning

    The flowchart of the 3D city building model-based particle filter is shown in Figure 3. This method first implements a particle filter to distribute position candidates (particles) around the ground-truth position. In Step 2, when a candidate position is given, the method can evaluate whether each satellite is in LOS, multipath or NLOS by applying the ray-tracing procedure with a 3D building model. According to the signal strength, namely carrier-to-noise ratio (C/N0), the satellite could be roughly classified into LOS, NLOS and multipath scenarios. If the type of signal is consistent between C/N0 and ray-tracing classification, the simulated pseudorange of the satellite for the candidate will be calculated. In the LOS case, simulated pseudoranges can be estimated as the distance of the direct path between the satellite and the assumed position. In the multipath and NLOS cases, simulated pseudoranges can be estimated as the distance of the reflected path between the satellite and the candidate position via the building surface.

    Figure 3. Flowchart of the particle filter using 3D city building models.
    Figure 3. Flowchart of the particle filter using 3D city building models.

    Ideally, if the position of a candidate is located at the true position, the difference between the simulated and measured pseudoranges should be zero. In other words, the simulated and measured pseudoranges should be identical. Therefore, the likelihood of each valid candidate is evaluated based on the pseudorange difference between the pseudorange measurement and simulated pseudorange of the candidate, which is simulated by 3D building models and ray-tracing.

    Finally, the expectation of all the candidates is the rectified positioning of the proposed map method. This method can therefore find the optimum position through a dedicated optimization algorithm of these assumptions and evaluations. The positioning principle of the proposed method is very different from the conventional GPS positioning method, that is, WLS. As a result, the calculation of the positioning accuracy of the 3D map method should be also different.

    We define two positioning performance measures for the 3D map method: user range accuracy of the 3D map method (URA3Dmap) and positioning accuracy.

    The value of URA3Dmap is to indicate its level of positioning service, which is similar to the user range accuracy (URA) of conventional GPS. The URA3Dmap is defined based on the percentage of the valid candidates from all candidates outside the building. The higher percentage of the valid candidate implies a higher confidence of the estimated position. Ideally, if the center of the candidate distribution is not far from the ground truth, the simulated pseudorange of the candidates located at the center of distribution would be very similar to the measurement pseudorange. We define the URA3Dmap as shown in Table 1.

    Table 1. The definition of URA and URA3Dmap used in this article.
    Table 1. The definition of URA and URA3Dmap used in this article.

    Experiments and Discussion

    We selected the Hitotsubashi and Shinjuku areas in Tokyo to construct a 3D building model because of the density of the tall buildings. In this area, multipath and NLOS effect are frequently observed. We tested pedestrian navigation in a typical path that included walking both sides of street and passing through/waiting at a road intersection. The cut-off angle is 20 degrees. The data were collected in November and December 2014.

    We compare here two single point positioning methods: single-point positioning solutions provided by open source RTKLIB software (RTKLIB SPP), and the proposed 3D map method. RAIM FDE of the RTKLIB SPP is used here as a conventional NLOS detection algorithm. The test used a geodetic-grade GNSS receiver and a commercial grade receiver. The geodetic receiver was only used to collect the QZSS L1-SAIF correction signal. The antenna of the commercial receiver was attached in the strap of the backpack as shown in Figure 4. The receiver is connected to a tablet to record the GNSS measurements and is set to output pseudorange measurements and positioning results every second.

    Figure 4. Equipment set-up.
    Figure 4. Equipment set-up.

    We generated a quasi-ground truth using a topographical method.Video cameras were set in the ninth and18th floors of a building near the Hitotsubashi and Shinjuku areas, respectively, to record the traveled path. The video data output by the cameras are used in combination with one purchased high-resolution aerial photo to get the ground truth data. The aerial photo is 25 cm/pixel and therefore the error distance for each estimate can be calculated. The synchronization between video camera and commercial GNSS receiver is difficult to get as accurate as in the topographical method. As a result, we used point to “points” positioning error to evaluate the performance of the dynamic experiment. The synchronization error is limited to 1 second. Hence, for each estimated position x(t), the ground truth points used to calculate the positioning error is xGT (t-1), xGT (t) and xGT (t+1). The point to “points” positioning error is calculated as:

    Streetsmart-Eq1

    Three performance metrics are used here: mean, standard deviation of the point to points error, and the availability of positioning solution. The availability defined here means the percentage of given solutions in a fixed period. For example, if a method outputs 80 epochs in 100 seconds, the availability of the method is 80 percent.

    This research demonstrates two dynamic data. The skyplot of the data are shown in Figure 5. The satellites are tracked by the commercial receiver. The grey areas indicate the obstruction of the surrounding buildings. The two dynamic data are typical signal receptions at Hitotsubashi (middle urban canyon) and Shinjuku (deep urban canyon) areas.

    Hitotsubashi Mid-Canyon. To study the benefit of using different GNSS constellations in the 3D map method, Figure 6 shows the trajectory estimated by the proposed method under different satellite constellations. The different colors indicate different values of URA3Dmap of each point. This walking trajectory is divided into five sections (identified as A, B, C, D and E in the right-most of the three plots). In the GPS-only case (left), results in A and B sections have much better performance than sections D and E, because more than half of the GPS satellites are blocked at D and E, as shown in the left of Figure 5.

    Figure 5. The left and right are the skyplot of the dynamic experiment at the Hitotsubashi and Shinjuku areas, respectively, in Tokyo.
    Figure 5. The left and right are the skyplot of the dynamic experiment at the Hitotsubashi and Shinjuku areas, respectively, in Tokyo.

    The middle plot in Figure 6 shows the trajectory using GLONASS. It is obvious that the positioning results located at the right side of street are greatly increased, derived from the greater number of satellites in view. However, the quality of the GLONASS signal is not as good as GPS because multipath has a double effect on GLONASS.

    Figure 6. Positioning results of the proposed 3D map method using different combinations of satellite constellations in a middle urban canyon.
    Figure 6. Positioning results of the proposed 3D map method using different combinations of satellite constellations in a middle urban canyon.

    In summary, the positioning error of applying GLONASS maintains a similar level, and availability increases about 12 percent compared to using GPS only. The right plot of Figure 6 shows the result after adding QZSS L1 C/A and L1-SAIF. This increases the results of C, D and E sections, because QZSS provides a high-elevation-angle satellite to the 3D map method. As a result, the number of valid candidate points in C, D and E sections increases dramatically. The reliability in C, D and E sections is also much higher than that of GPS+GLONASS. In addition, the trajectory became smoother than before.

    Table 2 compares the positioning results of both RTKLIB SPP and the 3D map method, showing the 3D map method using GPS, GLONASS and QZSS to have the best performance among three scenarios. The positioning error mean and availability are 3.89 meters and 96.72 percent, respectively. The positioning error mean could be further improved to 3.23 meters if selecting the position point with URA3Dmap ≤ 3 (yellow, orange and red points in Figure 6). This selection will lose about 17 percent of availability.

    Table 2. Positioning results of the 3D map method using different combinations of satellite constellations in a middle urban canyon.
    Table 2. Positioning results of the 3D map method using different combinations of satellite constellations in a middle urban canyon.

    Shinjuku Deep Canyon. We conducted a similar experiment in the Shinjuku area of Tokyo, the most urbanized area in Japan (Figure 7). The positioning results and skyplot are shown in Figure 8 and the right of Figure 5, respectively. Table 3 compares the results of the two methods using the three constellation configurations.

    Figure 7. Deep urban canyon environment, Shinjuku, Tokyo. (Courtesy Google Earth)
    Figure 7. Deep urban canyon environment, Shinjuku, Tokyo. (Courtesy Google Earth)
    Figure 8. Positioning results of the proposed 3D map method using different combinations of satellite constellations in a deep urban canyon.
    Figure 8. Positioning results of the proposed 3D map method using different combinations of satellite constellations in a deep urban canyon.
    Table 3. Performance comparison of RTKLIB SPP and the proposed 3D map method using different combinations of satellite constellations in a deep urban canyon.
    Table 3. Performance comparison of RTKLIB SPP and the proposed 3D map method using different combinations of satellite constellations in a deep urban canyon.

    As shown in the left of Figure 8, only half of the GPS-only solutions are on the correct side of the street. A few points are incorrect due to the insufficient number of satellites. Adding GLONASS measurements greatly increases the availability, and most of the GPS-only outliers are corrected. The positioning error mean improves from 12.7 to 10.3 meters, and the availability improves from 53.2 to 75.9 percent. GLONASS measurements provide such a significant improvement because the distribution of GPS and GLONASS satellites are complementary.

    After adding the QZSS measurements, availability further increases to 88.6 percent, and positioning error mean is reduced to 5.7 meters. The positioning error mean could be further improved to 4.2 meters if selecting the position points with URA3Dmap ≤ 3: the red, orange and yellow points in Figure 8. Although this selection will lose about 12 percent of availability, it could be easily compensated by a simple filtering technique.

    Comparing Table 2 and Table 3, we find the positioning error of the proposed method in the middle urban canyon is about 1 meter worse than that in the deep urban canyon. This is because of the increase of multiple reflected signals.

    The target application of this 3D map method is consumer-based pedestrian navigation. Most of these applications benefit from an integrated system of multiple sensors. The 3D map method could serve as one sensor for such an integrated system. The calculation of positioning accuracy is required to indicate the quality of the point solution estimated by this method. Figure 9 shows the relationship between the calculated accuracy and positioning error. We can find that the calculated accuracy is able to describe the performance of the proposed method.

    Figure 9. Positioning error of the 3D map method using GPS+GLONASS+QZSS. The purple line denotes the calculated 68 percent accuracy of the proposed method.
    Figure 9. Positioning error of the 3D map method using GPS+GLONASS+QZSS. The purple line denotes the calculated 68 percent accuracy of the proposed method.

    The performance of the conventional method is very inaccurate in this deep urban canyon. Its positioning error is larger than 40 meters. Figure 10 shows the number of satellites in this data. Note the number of LOS satellites is determined by the ray-tracing simulation according to the ground truth trajectory.

    Figure 10. Number of LOS satellites, the number of satellites used in the 3D map method, and the total number of satellites tracked by the commercial-grade receiver.
    Figure 10. Number of LOS satellites, the number of satellites used in the 3D map method, and the total number of satellites tracked by the commercial-grade receiver.

    The number of LOS satellites means the light-of-sight path of satellite is not blocked by buildings. Note that the LOS signal also contains the multipath effect. In this deep urban canyon, the number of LOS signals is much less than that of all received satellites. This implies a lot of NLOS is received, which deteriorates the performance of the conventional method. The map-based method is able to correct most of the NLOS signals.

    The number of satellites used in the map-based method is close to the number of all the satellites received. Therefore the map-based method can achieve better performance than the conventional method. Figure 11 demonstrates the comparison between the map-based method and the commercial GNSS receiver. The map-based method is simply smoothed by a moving average filter with 3 seconds data. It is difficult to understand the pedestrian trajectory by the commercial-grade receiver result. In some cases, the commercial receiver will estimate the pedestrian to be on the wrong side of the streets. The proposed method, instead, is capable of estimating the result at the correct side of the street.

    Figure 11. Positioning results of the proposed 3D map method and commercial-grade receiver using GPS+GLONASS+QZSS in the deep urban canyon.
    Figure 11. Positioning results of the proposed 3D map method and commercial-grade receiver using GPS+GLONASS+QZSS in the deep urban canyon.

    Li-Ta Hsu is a post-doctoral researcher at the Institute of Industrial Science of the University of Tokyo. He received his Ph.D. degree in aeronautics and astronautics from National Cheng Kung University, Taiwan.

    Shunsuke Miura received an M.S. degree in information science from the University of Tokyo in 2013.

    Shunsuke Kamijo received a Ph.D. in information engineering from the University of Tokyo, where he is now an associate professor.