Tag: 3D mapping

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.

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/N₀), the satellite could be roughly classified into LOS, NLOS and multipath scenarios. If the type of signal is consistent between C/N₀ 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.

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.

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.

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 x_GT (t-1), x_GT (t) and x_GT (t+1). The point to “points” positioning error is calculated as:

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.

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.

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.

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.

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.

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.

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.

---

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.