KR101467317B1 - Method for determining the presence of positioning data error - Google Patents

Abstract

A method for determining whether or not the first position data collected from the user device is erroneous is disclosed. The method includes calculating a first velocity (V _c ) using first position data and past one or more position data collected from the user device, and determining a first velocity (V _c ) And judging that the first position data is erroneous when the predetermined expression included in the variable is satisfied.

Description

[0001] The present invention relates to a positioning method,

The present invention relates to a technique for determining whether there is an error in position data collected by a user device.

Location information systems such as GPS, GLONASS, and Galileo are well known. In addition, wireless communication network positioning can be performed using a WIFI location approach of a base station or a crowd source. Therefore, users with smart phones or other portable devices can obtain their current position regardless of the location system type. However, the location information set has data with errors for various reasons. When using Apple's iPhone or Samsung's Galaxy, you can experience a lot of location information with errors, and there is a need to filter out obvious errors.

Recent developments in portable devices, in particular with the introduction of smart phones with GPS or other position sensing devices, have enabled various location based services based on human mobility. However, this location information sometimes has location errors depending on the operating environment. In such cases, many devices require filtering of location information with such errors.

In the present invention, a relatively simple but efficient filtering method is proposed based on a statistical approach.

The present invention provides a relatively simple yet effective filtering method based on a statistical approach. The velocity and acceleration of the user can be calculated from the user's movement position data in the form of <latitude, longitude, time> obtained from the mobile device. Using the idea of a sliding window or a moving window, the statistics of the velocity and acceleration of the user location data can be calculated and the filtering can be performed using the controllable parameters. Since the algorithm according to an embodiment of the present invention is simple, it can be applied to a mobile device having a small computation power.

In one embodiment of the present invention, to improve performance, the focus is on creating a more sophisticated window for enhanced filtering. A backtracking interpolation method can be used to more precisely estimate the moving window and replace the erroneous data with a reasonable estimate.

Recent advances in mobile devices, particularly smart phones with GPS or other location sensing devices, have enabled various location based services based on human mobility. One application of the position detection system may include the education field as shown in [2] below and can be easily found in various mobile devices shown in [1] below. However, such position detection data often has a position error depending on the operating environment. In this case, many applications require filtering of location data with such errors. As experienced in the experiments for the present invention, errors have occurred in more than 12% of the location information collected by smartphone use. This basic experiment is based on the use of smartphone applications via the Samsung Galaxy Tab, which uses the location of cellular base stations internally, and iOS5, which uses a combination of portable GPS devices [3], WIFI location detection by crowd sourcing, The iPhone 3GS is equipped with the [4]. More sophisticated results can be found in studies of the human movement model and in the articles of Kim and Song [5]. According to other research fields, such as complex system physics, people are reluctant to randomly select the next destination instead of choosing a place and route they visit frequently. Thus, it has been shown that up to 93% of human movement can be predicted [6]. The sets of location information can be the basis for constructing the human mobility model as shown in [5]. In the present invention, we will propose a technique for filtering location information with errors along with the use of a moving window approach. We will also show our ideas using a moving window with preliminary experiments for algorithm setting. The filtering algorithm will be described in detail. We will also show you what to consider and the results of our experiments with user controllable variables for experimental design.

⇒ [1]: Nicolae-Iulian Enescu, Dan Mancas, and Ecaterina-Irina Manole, "Locating GPS Coordinates on PDA," 8th WSEAS International Conference on APPLIED INFORMATICS AND COMMUNICATIONS (AIC08), Rhodes, Greece, August 20-22, 2008 , pp.470-474.

⇒ [2]: Ph. Ddondon, T. TSING, and F. Sandoval, &quot; Initiation to GPS Localization and Navigation Using a Small-Scale Model Electric Car, &quot; Proceedings of the 8th WSEAS International Conference on EDUCATION & EDUCATIONAL TECHNOLOGY , 2009, pp. 21-26.

⇒ [3]: Garmin GPSMAP62s, https://buy.garmin.com/shop/shop.do?pID=63801

⇒ [4]: iOS 5: Understanding Location Services, Available: http://support.apple.com/kb/ht4995

⇒ [5]: Hyunuk Kim and Ha Yoon Song, "Daily Life Mobility of A Student: From Position Data to Human Mobility Model Expectation Maximization Clustering," Communications in Computer and Information Science, Volume 263, December 2011, pp. 88-97.

[6]: Marta C. Gonzalez and A. Hidalgo and Albert-Laszlo Barabasi, "Understanding individual human mobility patterns," Nature, vol. 453, pp. 797-782, 5 June 2008.

The user's speed and acceleration can be calculated through the user's portable location information obtained in the form of <latitude, longitude, time> through portable devices. From the idea of a sliding window or a moving window, statistics of the user's acceleration and speed can be calculated, and filtering can be performed using controllable variables. It can be expected that the algorithm according to an embodiment of the present invention is simple and therefore applicable to low-power portable devices.

According to an aspect of the present invention, there is provided a method of determining whether or not an error exists in first position data collected from a user device. The method includes calculating a first velocity (V _c ) using first position data and past one or more position data collected from the user device, and determining a first velocity (V _c ) And judging that the first position data is erroneous when the predetermined expression included in the variable is satisfied.

The present invention provides an efficient filtering method based on a relatively simple but statistical approach.

Figure 1 is a visual representation of the raw-data set for the collected locations.
Figure 2 shows the results of a simple experiment according to an embodiment of the present invention.
FIG. 3 illustrates the effect of the window size according to the calibration method in accordance with an embodiment of the present invention.
Figure 4 shows an advanced filtering algorithm according to an embodiment of the present invention.
Figure 5 shows another advanced filtering algorithm according to an embodiment of the present invention.
6 shows the filtering result when n = 10 and s = 0.34 in one embodiment of the present invention.
Figure 7 shows the filtering results for n = 10 and 88% confidence interval in one embodiment of the invention.
Figure 8 is intended to illustrate [Algorithm 2] according to an embodiment of the present invention.
FIG. 9 shows another example for explaining [Algorithm 2] according to an embodiment of the present invention.
Fig. 10 is for explaining [Algorithm 3] according to an embodiment of the present invention.
11 is a view for explaining a position data error filtering and correction method according to another embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. It should be understood, however, that the invention is not limited to the disclosed embodiments, but may be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, Is provided to fully inform the user.

A user location collected in the form of latitude, longitude, and time may form a set of user movement traces and may represent a user mobility data set by adding identification parameters to the tuple. Referred to herein as a one tuple at a time t P _t, and may refer to the latitude and longitude of P _t as each _t lat, lon _t.

From two successive positional data tuples, the movement distance D _i at time P _i using <lat _i-1 , lon _i-1 > and <lat _i , lon _i > according to Vincenty's formula [7] Can be calculated. Of course, the time from two successive speed movement distance of the P _i V _i can be calculated, and the acceleration a _i at time P _i can be calculated. Thus, the tuple P _t can have a core form such as <t, lat _t , lon _t , D _t , a _t > that contain additional attributes.

[7]: T. Vincenty, "Direct and Inverse Solutions of Geodesics on the ellipsoid with Application of Nested Equations," Survey Review, Volume 23, Number 176, April 1975, pp. 88-93 (6).

Based on the velocity values from the actual location data set, we could find a single error of 600m / s in a series of speeds, which is insignificant in normal everyday environments. Thus, as shown in Table 1, the maximum possible velocity values of normal human mobility were investigated. Table 1 shows the different maximum speeds for vehicles. For an embodiment of the present invention, the maximum speed MAX _speed can be defined as 250 m / s. Such a maximum value can not be reached immediately, that is, the acceleration is not made suddenly. Besides MAX _speed , MAX _acceleration can be defined.

Transportation Method Maximum speed (m / sec) Ambulation
Bicycle
Automobile
Sports-Car
High-Speed Train
Air-plain 3.00
33.33
92.78
244.44
159.67
528.00

For the next step we introduced the idea of a moving average of speed and a moving standard deviation of speed. We can define MA _speed (n), the moving average of speed at the current time t, where n is the set of tuples {P _x : t-n + 1 ≤ x <t} Represents the number of past data. Similarly, we can define the moving standard deviation MSD _speed (n) at time t, where n represents the number of past data. Here, n is referred to by the name of 'window size' by most researchers. Once we get a new tuple P _t , we can determine if V _t is within the normal range of human mobility, and the same process can be applied to a _t . Once V _t is outside of the normal distribution of the mean value MA _speed (n) and the standard deviation MSD _speed (n), we can discard P _t and this tuple can be filtered from a series of human traces . The condition for filtering P _t is expressed by Equation (1).

[Equation 1]

V _t > MA _speed (n) + s * MSD _speed (n)

Where s represents the sensitivity level of filtering and is a user-controllable parameter. If not (ie, if V _t does not satisfy Equation 1), we can include the tuple P _t in a series of valid position data and recalculate MA _speed (n) and MSD _speed (n). This calculation is relatively simple and can be done in real time. In other words, the algorithm can be performed in a low power device such as a smart phone or similar mobile device. Existing research involves similar tasks using more complex statistical theories [8], but such complex methods are difficult to introduce in real-time environments. Examples of other applications based on moving windows can be found in [9] and [10].

⇒ [8]: Woojoong Kim and Ha Yoon Song, "Optimization Conditions of OCSVM for Erroneous GPS Data Filtering," Communications in Computer and Information Science, Volume 263, December 2011, pp. 62-70.

⇒ [9]: Camelia Ucenic and Atsalakis George, "A Neuro-fuzzy Approach to the Electricity Demand," Proceedings of the IASME / WSEAS International Conference on Energy and Environmental Systems, Chalkida, Greece, May 8-10, 2006, pp.299-304.

[[10]: Wiphada Wettayaprasit, Nasith Laosen, and Salinla Chevakidagarn, "Data Filtering Techniques for Neural Networks Forecasting," Proceedings of the 7th WSEAS International Conference on Modeling and Optimization, Beijing, China, September 15-17, pp.225-230.

We performed an experiment to determine the effect of window size. For this experiment, a set of location data collected in the Seoul area of Korea for more than 20 days was used. This data was collected using the iPhone 3GS with location-aware applications. Hereinafter, this information will be referred to as an &quot; iPhone data set &quot;. Every time the iPhone detects a change in position, or when the iPhone is idle, the application can record location information every user defined interval (3 to 60 seconds). A variety of techniques have been used to represent this set of location data on a geographical map. Among various techniques, Google Map [11] was chosen for the visualization of location data sets.

⇒ [11]: Google Maps API, Available: https://developers.google. com / maps /

In Figure 1, a raw-data set is shown visually, which contains erroneous data. One notable phenomenon is that iOS5 occasionally reports location data obtained in three different ways. That is, the location of the cellular base station, the crowd source WIFI location detection, and the GPS sometimes report different location data at the same time. When we get multiple position values at the same time, the position information with the smallest velocity value was empirically correct. Therefore, in the first step of filtering, it is possible to simply select the position data having the smallest distance to the previous position among the plurality of position information at the same time. The data sets may also be composed of several discontinuous data sets. For example, location data collection is not available on the subway, and there is no need to collect data from the bed in the house. It is only possible to collect location data while traveling to a subway train station.

The value of n is carefully determined. Various experiments were performed while changing the size of n in the algorithm for the data set. If the window size is large, it can be expected that it will not respond to the situation of rapid change of speed, while it can cope with successive errors in stable non-moving state. While a small value of n will show a rapid response to a sudden change in velocity to a moving state that is considered to include successive error tuples. For example, in the presence of m consecutive errors, if m> n, then such errors can not be filtered. To understand our guesses, we experimented with window size for the iPhone data set. In this experiment, moving average and moving standard deviation for various window sizes such as n = 5, 10, 25, 50, and 100 were calculated.

Figure 2 shows the results of a simple experiment for an embodiment of the present invention. It is clear that a larger window is dull. Once we meet a very large velocity value, the large window size keeps the large error rate effect for a long time, resulting in under filtering of the erroneous data. In the case of a window size of 100 or 50, we can clearly see the tailing effect in FIG. On the other hand, the small window size over-filters the correct data, especially at the beginning of the speed change, while being responsive and sensitive to the speed change. When the window size is 5 or 10, you can see that two or more correctly visible tuples that look like the correct velocity data are discarded by the small window size. This phenomenon implies that an adjustment mechanism for the moving window must be introduced to avoid the windowing tailing effect.

Hereinafter, pre-experiments on position detection data errors according to an embodiment of the present invention will be described.

We conducted a basic experiment to check the accuracy of position data. That is, the position detecting devices were fixed both in the outdoors and in the building, and the position data was collected for several hours without moving to any device. The first position detection device was used for GPS data collection purely as the Garmin GPSMAP62s [3]. The second position detection device is a Samsung Galaxy Tab and was used to obtain position detection data from a 3G base station (3GBS) connected to this device. We assumed that the Galaxy Tab would show more errors in both situations, and assumed that both the GPS and the data sets from 3GBS would indicate position detection errors. Especially, it is assumed that the location detection error will be shown in the building. The results of this basic experiment are shown in Table 2. Table 2 shows the errors that occur when acquiring the position detection data, and the notation unit is a meter.

The error distance is calculated from the position data, and the variance and the average of the error distance can be calculated. As we guessed, 3GBS exhibited a larger error rate, larger error size, larger maximum error size, and larger standard deviation of error size. The producer's policy of producing the Garmin GPSMAP62s is to calculate the user's position based on the speed of the past, even if the GPS signal is lost, which caused a very large error in the building. Therefore, GPS data in a building can be considered as not meaningful data. GPS data outdoors is of sufficient accuracy for sophisticated position detection, and the maximum error size is within a reasonable range of 52 meters.

Hereinafter, a filtering algorithm according to an embodiment of the present invention will be described.

Based on the considerations in the above pre-experiment, we created an algorithm for error location data filtering as in [Algorithm 1] in Table 3. When the new position data P _t is newly obtained, this algorithm can determine whether or not P _t is to be filtered. In actual situations, we can consider several situations.

* Initial configuration of a moving window: If there are fewer than n tuples, we can not construct a complete moving average and a moving standard deviation. Instead, we can construct an incomplete window using a small amount of information. : Line 2 ~ 5 of [Algorithm 1].

* Acceleration and velocity have different points in the filtering detail, but both can be considered as throttling parameters. Position information tuples that are out of velocity range or have excessive acceleration will be filtered. : Line 6 to 8 in [Algorithm 1].

* If the speed of one tuple is too large, it will affect the MA and MSD values and will result in filtering errors such as an extension of the confidence interval. As a result, the tuple to be filtered must be filtered-in . Thus, if the speed of one tuple is too large, you can modify the speed value using MA _speed (n) + 2.57 * MSD _speed to avoid possible extended error of the confidence interval, including as fast as possible. : Line 9 to 11 in [Algorithm 1]. s = 2.57 represents the confidence interval of 99.5% of the normal distribution. This is a throttle that reduces the effect of the errored speed on the moving window. : In line 9 to 10 of [Algorithm 1] s _99.5

Window configuration: Even if a single tuple must be filtered out, it can contain the velocity of this tuple if the velocity of this tuple is outside the 99.5% confidence interval of the normal distribution. It is intended to update the moving window to cope with rapid changes in speed. That is, even a tuple without errors can be filtered out with a sudden change in speed. In such a case, even if the tuple is filtered, the moving window may reflect the change in velocity for the next arriving tuple. : [Algorithm 1], line 10

* Less than 2.77 m / s (10 Km / h) will not be filtered because human walking is possible within a speed less than 2.77 m / s (10 Km / h) and also due to the GPS error range. : In [Algorithm 1], the 9th line MIN _velocity

Tuples with unrealistic acceleration must be filtered. As described in [12], 10.8 m / s ² is the largest existing value for sports cars. : In [Algorithm 1], the 12th line MAX _acceleration

⇒ [12]: List of fastest production cars by acceleration, Available: http://en.wikipedia.org/wiki/LisP_of_fastesP_cars_by_acceleration

Once the tuple to be filtered due to excessive acceleration must be filtered, the acceleration value of this tuple is forced to be set to MAX _acceleration , and the velocity value is set to MA _speed (n) to nullify the effect of the unrealistic velocity value . : In [Algorithm 1], lines 12 to 16

* Since it is always possible for a vehicle to quickly stop with a large negative acceleration, positional information tuples with negative acceleration values will not be considered as errors, whereas tuples with a positive acceleration value greater than MAX _acceleration Will be considered.

For [Algorithm 1], we did not specify two variables. n is the number of tuples in the window, and s is the sensitivity level of filtering. These two parameters can be specified by the user of [Algorithm 1]. The user sensitivity level s can be determined relatively simply. From the properties of the normal distribution we can get s with the appropriate confidence interval. We can set s = 1.64 for a 95% confidence interval and s = 2.33 for a 99% confidence interval, since we will only use positive regions of normal distribution for filtering. Users can determine s according to their own goals. For example, we can choose sensitivity level s as follows. Table 2 shows the normal error rate for position data collection when the instrument is not moving. For the case of GPS, there was an error in the data of 12.3% and an error in the data of 36.75% for the 3GBS cellular position detection system. Therefore, in this experiment, it was possible to set s = 1.16 for GPS data and s = 0.34 for cellular position detection data.

We have already discussed the effect of window size. Due to the trailing effect of the large window, a smaller window can be selected. However, [Algorithm 1] calibrates inaccurate velocity values. In addition, the abnormal acceleration value is limited and the velocity value can be replaced by the average velocity of the moving window. The effect of window size on this calibration mechanism can be seen once again.

FIG. 3 illustrates the effect of the window size according to the calibration method in accordance with an embodiment of the present invention. The x-axis represents the time of November 11, 2011. In this example, window size n = 5, 10, 25, 50, 100 is selected and sensitivity level s = 1.16 is selected and 88% of the position data is assumed to be correct data and filtering is performed. Despite the limited trailing effect, the smaller window size exhibits a more flexible reaction with varying speeds. Thus, a window size of 5 or 10 is a better choice.

The effect of continuous error can also be considered further. Despite adopting a throttling mechanism for speed, successive errors will affect the moving average and the moving standard deviation, and thus may cause confusion in the filtering algorithm according to an embodiment of the present invention . We have experienced up to four consecutive errors in the actual position detection data set and have therefore concluded that n = 5 for our experimental environment is insufficient and can respond to successive errors if n = 10, The tailing effect by size can be reduced. Therefore, the window size in this experiment was finally determined to be 10. Of course, if you experience a greater number of consecutive errors, you can choose the appropriate window size, or dynamically increase the size of the window as described below.

Figure 4 shows an advanced filtering algorithm. The same position detection data sets as those in Fig. 3 were selected and compared in a fair manner. The x-axis represents the time of November 11, 2011. In Fig. 4, the window size n = 10 and the sensitivity level s = 1.16, indicating that 88% of the position data was considered to be correct. The thin black solid line represents the change in actual speed in m / s and the thin gray dashed line represents the speed calibrated by the filtering algorithm according to one embodiment of the present invention. The calibrated speed usually overlaps with the speed, which indicates the calibration value when the tuple is filtered by the filtering algorithm. The dotted line represents the acceleration value.

Bold black solid lines indicate the coverage (range of acceptance of speed) of a moving window with n = 10. It should be noted that the moving window shown in Figure 4 is based on the calibrated velocity value. Thanks to the calibrated velocity value, the moving window reacts quickly to changes in velocity and successfully filters the errored tuples. A double dotted line represents the coverage (raw coverage) of a moving window without velocity correction. Comparing calibrated coverage with low-coverage, the effect or limit of velocity correction becomes clear. Speed correction according to our algorithm successfully suppresses the effect of very large velocity error on the moving window. Thus, a moving window constructed at a calibrated rate successfully removes the effect of the velocity error and can maintain an appropriate estimate of the position detection tuple values.

FIG. 5 shows an advanced filtering algorithm similar to FIG. In Figure 5, the sensitivity level s = 0.34 and all other conditions are the same.

<Result of filtering>

Finally, the results of the filtering experiment according to an embodiment of the present invention are shown in two ways.

First, in one embodiment of the present invention, filtering is performed on the entire position detection data set, and the result is displayed on an actual map. This visualization was performed using Google Maps [11].

Figure 6 shows the filtering results when n = 10 and s = 0.34.

Figure 7 shows the filtering results for n = 10 and 88% confidence interval. Although the error of the position detection data set can not be found in Fig. 7, it includes more position detection data than the result shown in Fig. Therefore, it can be concluded that proper filtering of the window size and sensitivity level can be achieved.

Second, filtering can be performed on all position detection data sets according to various combinations of window size and sensitivity level. Table 4 shows the percentage of filtered-out tuples for each combination of parameters. Users of the algorithm according to an embodiment of the present invention can select the window size and sensitivity level according to Table 4 according to their environment.

In the study for the present invention, we have created an error-prone position data filtering algorithm and experienced the effects of various combinations of window size and sensitivity levels. In practice, the collected location data sets were used for algorithm verification and found successful filtering results. Various parameters of the algorithm such as window size, sensitivity level, maximum speed and maximum acceleration can be defined by the user. It is also possible for the user to change the constant of the algorithm such as MAX _accelerance , s _99.5 (maximum sensitivity level) and MIN _velocity (minimum threshold for speed for filtering).

While examining the filtering process one by one, we found some fine loopholes in the algorithm. The first is that the above algorithm can not work at the beginning of information gathering because there was not enough tuples to fill the entire window at the initial window construction stage. All approaches based on moving windows can have this compulsory demerit.

The second problem is over-filtering and under-filtering. If a new tuple is collected that shows a rapid increase in speed, this tuple can be filtered regardless of the accuracy of this tuple. This tendency becomes apparent when the size of a window is large, because a large window can not respond fast enough to catch a change in speed. As a reward for this, the velocity of the filtered tuple may be included to preserve the window width corresponding to the change in velocity, unless the velocity change is outside the 99% confidence interval range of the normal distribution. If the velocity is outside the 99% confidence interval, the velocity can be calibrated for later construction of the moving window. As described in connection with FIG. 3, the tendency of under-filtering is evident when there is a larger window size.

If the number of consecutive errors is greater than the window size, it can not be filtered by a smaller window. For example, as we have experienced four consecutive errors included in the experimental data, we can conclude that n = 10 is a better choice than n = 5. Another advantage of small window sizes is that the computation time is small and the memory space for moving window configuration is small, so that this algorithm can operate in real time on low power portable devices.

There are several kinds of additional considerations. The first is about the window size. Instead of defining the size of the window as the number of tuples in a window, you can define it as the time interval that the window contains. Since speed is a function of time, this approach will be both effective and accurate when regularly collecting position data. Further consideration can be given to dynamic calibration of the window size. In another embodiment of the present invention, the window size can be dynamically increased or decreased depending on the number of consecutive errors. Once you find that there are a large number of consecutive errors, you can increase the window size to minimize the effect of successive errors on moving average and moving standard deviation. If the number of consecutive errors is small, by reducing the window size, an appropriate response to the abrupt rate change can be shown and the amount of computation for filtering can be reduced.

번째 튜플의 필터링을 결정할 수 있다. 실시간으로 사용될 수 없을지라도 이 접근법은 언더 필터링과 오버 필터링의 경향을 줄일 수 있다. 필터링의 정확성 대(vs.) 필터링의 실시간의 트레이드 오프(tradeoff)를 확인할 수 있다. The second is a pseudo-real-time algorithm, not a real-time algorithm such as [Algorithm 1]. For a window size of n, instead of filtering the (n + 1) -th tuple

Th tuple can be determined. Although it can not be used in real time, this approach can reduce the tendency of under-filtering and over-filtering. You can see the real-time tradeoff of filtering versus accuracy (vs.) filtering.

번째 튜플을 윈도우 내의 n 튜플들로 인터폴레이션 하는 것이다. 더 좋은 추정(estimation)을 위하여 n 튜플들로부터 추정된 점근 곡선(asymptotic curve)을 이용하여 윈도우 내의 중앙 튜플(middle tuple)을 인터폴레이션하여 더 정밀한 인터폴레이션을 가능하게 할 수 있다. 그러나 이 때문에 계산 오버헤드(computational overhead)가 생기게되어, 이 알고리듬을 이동 기기에 적용하는 것이 어려울 수 있다. 속도 인터폴레이션이 필터링 정확도에 미치는 영향을 살펴볼 수 있다.
Another idea for improving the algorithm is the introduction of interpolation. Algorithm 2 presented in Table 5 below includes additional operations for interpolation as compared to [Algorithm 1] (see lines 17 to 20 of [Algorithm 2]). In [Algorithm 2], an additional step is added to [Algorithm 1] to better approximate the moving window statistics. When a new tuple arrives, the last tuple in the existing window can be marked, and the speed of the last tuple in the current window can be replaced with a linearly interpolated value. This interpolation can provide a more precise approximation of the moving window for filtering purposes (see [Algorithm 2], lines 17-20). In other words, the last part of [Algorithm 2] allows you to interpolate the last tuple marked in the window whenever you get a new tuple. Yet another variation for a moving window configuration for a more precise approximation,

Th tuple into n tuples in the window. It is possible to interpolate the middle tuple in the window using an asymptotic curve estimated from the n-tuples for better estimation to enable more accurate interpolation. However, this leads to computational overhead, which may be difficult to apply to mobile devices. The effect of velocity interpolation on filtering accuracy can be seen.

Algorithm 2 Moving Window construction with Interpolation Require : P ₀ ▷ At least one initial tuple is required
Require : window size n
Require : user sensitivity level s
Ensure : Check validity of new position tuple
Ensure : Calibrated series of tuple {P _i : t ≥ i> 0} for t inputs
Require : i = 0
1: repeat Get P _{i + 1} ▷ Acquisition of new tuple, if exist
_{2: Construct MA speed (n)} with {P x: max (i-n + 1, 0) ≤ x ≤ i}
_{3: Construct MSD speed (n)} with {P x: max (i-n + 1, 0) ≤ x ≤ i}
4: Set MA _speed = MA _speed (n)
5: Set MSD _speed = MSD _speed (n) ▷ Moving Window Construction
6: if (V _{i + 1} > MA _speed + s × MSD _speed ) OR (a _{i + 1} ≥ MAX _acceleration ) then ▷ Filtering
7: Mark P _{i + 1} as filtered.
8: end if
9: if (V _{i + 1} ≥ MA _speed + s _99.5 × MSD _speed ) AND (V _{i + 1} > MIN _velocity ) then ▷ Calibration of Speed
10: Set V _{i + 1} = MA _speed + s _99.5 x MSD _speed
11: end if
12: if a _{i + 1} ≥ MAX _acceleration then Restriction by Maximum Acceleration
13: Mark P _{i + 1} as filtered
14: Set V _{i + 1} = MA _speed
15: Set a _{i + 1} = MAX _acceleration
16: end if
17: if (P _i marked as filtered) then ▷ Linear Interpolation
_{18: Set V i = ((} V i + 1 - V i-1) × (t i - t i-1)) / (t i + 1 - t i-1) + V i-1
19: Mark P _i as interpolated
20: end if
21: Set i = i + 1
22: until Exist no more input of positioning tuple

Figure 8 is intended to illustrate [Algorithm 2] according to an embodiment of the present invention.

The horizontal axis of FIG. 8 represents the index of the continuously obtained moving data tuple, and the vertical axis represents the raw-data relating to the speed obtained from each moving data tuple. In FIG. 8, the size n of the moving window is 10. MA _speed and MA _speed + s _99.5 x MSD _speed can be calculated from the speed values present in the moving window, and an example of this value is shown in FIG. In Fig. 8, it is assumed that the movement data tuple P _i for index [i] is marked as already filtered according to [Algorithm 2]. Thus [Algorithm 2] a, the mobile data tuple P _i speed V _i is the mobile data tuple speed V _{i + 1} of the speed V _i-1 and the mobile data tuple P _{i + 1} of the P _i-1 according to claim 18 rows Is replaced by a linear interpolated value.

FIG. 9 shows another example for explaining [Algorithm 2] according to an embodiment of the present invention.

In FIG. 9, the acceleration a _{i + 1} at the index [i + 1] is assumed to be larger than MAX _acceleration . Therefore, the speed V _{i + 1} at the index [i + 1] was corrected to the MA _speed . And, the mobile data tuple P _i speeds V _i is 8 and, like mobile data tuple P _i-1 velocity V _i-1 and the mobile data tuples, P _{i +} velocity V _{i + 1} using a linear interpolation of the value of _one of the .

In [Algorithm 2], the newly obtained moving data tuple (P _{i + 1} ) and the latest moving data tuple (P _i ) existing in the moving window are processed. Alternatively, in another embodiment of the present invention, the processing of the mobile data tuple (P _m ) existing at a certain point in the moving window can be performed, which will be described in [Algorithm 3] shown in Table 6.

Algorithm 3 Filtering Any Point Inside Moving Window Require : P ₀ At least one initial tuple is required
Require : window size n
Require : user sensitivity level s
Ensure : Check validity of new position tuple
Ensure : Calibrated series of tuples P _i : ti> 0 for t inputs
Require : i = 1
1: repeat Get P _i Acquisition of new tuple, if exist
2: Construct MA _speed (n) with P _x : max (i-n + 1, 0) xi
3: Construct MSD _speed (n) with P _x : max (i-n + 1, 0) xi
4: Set MA _speed = MA _speed (n)
5: Set MSD _speed = MSD _speed (n) Moving Window Construction
_{6: if (V m> MA} speed + s MSD speed) OR (a m MAX acceleration) then ▷ Filtering
7: Mark P _m as filtered.
8: end if
9: if (V _m MA _speed + s _99.5 MSD _speed ) AND (V _m > MIN _velocity ) then ▷ Calibration of Speed
10: Set V _m = MA _speed + s _99.5 MSD _speed
11: end if
12: if a _m MAX _acceleration then Restriction by Maximum Acceleration
13: Mark P _m as filtered
14: Set V _m = MA _speed
15: Set a _m = MAX _acceleration
16: end if
17: if (P _m marked as filtered) then ▷ Linear Interpolation
_{18: Set V m = ((} V m + 1 - V m-1) (t m - t m-1)) / (t m + 1 - t m-1) + V m-1
19: Mark P _m as interpolated
20: end if
21: Set i = i + 1
22: until Exist no more input of positioning tuple

Where m = ik and k is a user adjustable parameter satisfying two-n0. That is, m means a point set by the user in a window having a size n.

Fig. 10 is for explaining [Algorithm 3] according to an embodiment of the present invention.

In FIG. 10, the size of the moving window is set to 10. Also, the subject of filtering and / or velocity value correction is illustrated as being a moving data tuple with index [i-4] = ([m]). In Fig. 10, it is assumed that the mobile data tuple with index [i-4] has already been filtered according to [Algorithm 3]. Thus, in accordance with claim 18 rows of [Algorithm 3], the mobile data tuple P rate of the _i-4 V _i-4 are mobile data tuple P _i-5 speed V _i-5 and the mobile data tuple P _{i + 5} the speed of the V _{i + 5} is substituted for the linear interpolated value.

11 is a view for explaining a position data error filtering and correction method according to another embodiment of the present invention.

11 shows the result of using the modified interpolation method from the interpolation method according to lines 17 to 20 of [Algorithm 3]. In Fig. 11, a nonlinear interpolation method using a plurality of data in a moving window is used. For example, the moving data tuple having the index [i-4] can be corrected using a plurality of data included in the moving window and a value corresponding to an asymptote approximated by using the least squares method.

8 to 11 show examples for explaining the principles of various algorithms according to the embodiment of the present invention, and it is apparent that these examples are not intended to limit the present invention. It is to be understood that [Algorithm 1], [Algorithm 2], and [Algorithm 3] are described in detail so as to be clearly understood without reference to FIGS. 8 to 11, It is understandable that this is an executable code derived from the demonstration results shown.

Finally, we need to examine the effect of the probability distribution on filtering. In general, a normal distribution is a distribution usually used to describe various errors and filtering. However, advanced studies point out that the human mobility pattern follows a heavy tailed distribution like Levy Walk [6]. Therefore, since the distribution of location information can follow the Levy Walk format, the effect of applying the Levy Walk distribution to the filtering can be seen.

<Examples>

Hereinafter, a method for determining whether or not the position data is erroneous according to an embodiment of the present invention will be described. This method will be described with reference to [Algorithm 1], [Algorithm 2], or [Algorithm 3] described above.

The method of determining whether or not the position data is erroneous is a method of determining whether or not the first position data (P _c ) collected from the user equipment is erroneous, wherein the first position data (P _c ) And calculating a first velocity (V _c ) using at least one position data (SlO). Here, c may be, for example, i of [Algorithm 1] / [Algorithm 2] or m of [Algorithm 3]. The method further includes determining (S20) that the first position data (P _c ) is erroneous if the first velocity (V _c ) satisfies Equation (2).

&Quot; (2) &quot;

V _c > f (P),

Where P is at least one parameter that determines the shape of a probability distribution that is used to fit one or more other position data collected by the user equipment. At this time, the one or more other position data may be position data contained in a window used for calculating the parameter. For example, f (P) may be MA _speed + s x MSD _speed of [Algorithm 1], where parameter P may be MA _speed and MSD _speed .

The above probability distribution can be normal distribution, heavy tailed distribution, gamma distribution, etc. The parameters that determine the shape of the normal distribution are expected values and standard deviations, the parameter that determines the shape of the heavy tailed distribution is lamda1, and the parameters that determine the shape of the gamma distribution are any positive numbers lamda2 and alpha. The standard deviation is a value calculated to fit the past n collected position information to the normal distribution. lambda1 is the root of the equation obtained when the past n collected position information is pitched to the heavy tailed distribution. lamda2 and alpha are the roots of the equation obtained when the past n collected positional information is fitted to the gamma distribution.

The reason why the parameter for determining the shape of any one of the above distributions is used in the equation (2) is that, as a criterion for determining whether there is an error in the velocity with respect to the collected position data, It is decided whether or not to go beyond the range.

The above-described step S20 may be implemented by, for example, the sixth row and the seventh row of [Algorithm 1] or [Algorithm 2], or the twelfth row and the fourteenth row.

Here, the probability distribution is a normal distribution and the P may be at least one parameter that determines the shape of the normal distribution. Alternatively, the probability distribution may be a heavy tailed distribution and the P may be at least one parameter that determines the shape of the heavy tailed distribution. Alternatively, the probability distribution may be a gamma distribution, and the P may be at least one parameter that determines the shape of the gamma distribution.

In this case, the probability distribution is a normal distribution, equation 2 above is V _c> MA _speed + s1 * and MSD _speed, MA _speed is the shift of the speed calculated from the one or more other location data average, MSD _speed is Is an average value of the standard deviations calculated from the one or more other positional data, and s1 may be a predetermined constant (see line 6 of [Algorithm 1], [Algorithm 2], and [Algorithm 3].

At this time, in the calculating step S10, the first velocity V _c and the first acceleration a (a) are calculated using the first position data P _c and the past one or more position data collected from the user equipment _c ) can be calculated.

If the first speed V _c satisfies the equation (1) or the first acceleration a _c is equal to or greater than the predetermined maximum acceleration MAX _acceleration , Algorithm 6] or [algorithm 6]), it can be determined that there is an error in the first position data P _c .

In this case, the method according to this embodiment includes the steps of replacing the first speed (V _c) that if any of the equations (3) and (4) to the first speed (V _c) to a value calculated by Equation (5) (S30).

&Quot; (3) &quot;

V _c > = MA _speed + s2 * MSD _speed

However, s2 is a predetermined value,

&Quot; (4) &quot;

V _c > MIN _velocity

However, the MIN _velocity is a predetermined minimum velocity

&Quot; (5) &quot;

MA _speed + s2 * MSD _speed

At this time, the step S30 may be implemented by the ninth through eleventh rows of [Algorithm 1], [Algorithm 2], or [Algorithm 3], for example.

The method according to this embodiment is characterized in that when the first acceleration a _c is equal to or greater than a predetermined maximum acceleration MAX _acceleration (see the twelfth row of [Algorithm 1], [Algorithm 2], or [Algorithm 3] , determination is made that the error in said first position data (P _c) and wherein the ([algorithm 1] and [algorithm 2], or see the 13th line of the [algorithm 3]), the first speed (V _c) (See column 14 of [Algorithm 1], [Algorithm 2], or [Algorithm 3]) with the value of the MA _speed calculated from one or more other position data, (see the 15th row of [Algorithm 1], [Algorithm 2], or [Algorithm 3]) that replaces the predetermined maximum acceleration ( _c ) with the predetermined maximum acceleration (MAX _acceleration ).

Also, the method according to this embodiment may be such that the MA _speed of the velocity is updated to reflect the first velocity (V _c ) or the substituted first velocity.

In addition, the method according to this embodiment, when it is determined to be in error in said first position data (P _c) (see the line 17 in the [algorithm 2] or [Algorithm 3]), the speed (V _c) (See [Algorithm 2] or [Algorithm 3], line 18), the current position data P _c is replaced with a value interpolated using a plurality of velocity values adjacent to the velocity V _c (See [Algorithm 2] or [Algorithm 3], line 19) to record that they have been interpolated.

Above, for example, if c represents i + 1 of [Algorithm 2], then the interpolation may be done according to Equation (6).

&Quot; (6) &quot;

(V _{i + 1} - V _i-1 ) x t _i - t _{i -1} ) / (t _{i + 1} - t _{i -1} ) + V _{i -1,}

T _i-1 , t _i , and t _{i + 1} represent the absolute time in the position data index i-1, i, i + 1, respectively.

Alternatively, unlike that shown in [Algorithm 2] and [Algorithm 3], the interpolation may be performed using all the data contained in the window, or a nonlinear fit method may be used.

In this method, the at least one parameter is calculated from a plurality of position data included in a window having an adjustable size (n), and when it is determined that all of the M consecutive position data have an error, The size of the window can be increased, and when it is determined that there is no error in all of the L continuous position data, the size of the window can be reduced. Here, M and L are natural numbers that can be set.

While the present invention has been described with reference to exemplary embodiments, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the invention. Accordingly, the true scope of the present invention should be determined by the technical idea of the appended claims.

Claims (13)

A method for determining whether an error of first position data (P _c ) collected from a user device is present,
Calculating a first velocity (V _c ) associated with the first position data (P _c ) using the first position data (P _c ) and the past one or more position data collected from the user device; And
And determining that the first position data (P _c ) is erroneous if the first speed (V _c ) satisfies equation (1).
How to determine if location data is erroneous.
(1): V _c > f (P),
However, P is than collected in time, the first position data (P _c) as at least one parameter that determines the shape of the probability distribution to be used for one or more feet (fit) other location data collected by the user equipment A parameter including a statistical value calculated based on a probability distribution using at least one speed determined in the past,
f () is a function that takes the parameter P as an independent variable and outputs a value that can be compared with the first speed (V _c ). The method according to claim 1,
The probability distribution is a normal distribution and P is at least one parameter that determines the shape of the normal distribution,
Wherein the probability distribution is a heavy tailed distribution and P is at least one parameter determining the shape of the heavy tailed distribution,
Wherein the probability distribution is a gamma distribution, and P is at least one parameter that determines the shape of the gamma distribution,
How to determine if location data is erroneous. The method according to claim 1,
The probability distribution is a normal distribution,
Formula (1) V _c> MA _speed + s1 * MSD _speed and, MA _speed is the speed of movement of the average calculated from the one or more other location data, MSD _speed is a movement calculated from the one or more other location data Standard deviation, s1 is a predetermined constant,
How to determine if location data is corrupted. The method according to claim 1,
The calculating step calculates the first speed (V _c ) and the first acceleration (a _c ) using the first position data (P _c ) and the past one or more position data collected from the user device ,
In the determining, when the first speed V _c satisfies the equation (1) or the first acceleration a _c is equal to or greater than a predetermined maximum acceleration MAX _acceleration , the first position data P _c ) is judged to be in error,
How to determine if location data is corrupted. The method of claim 3,
If any of the first speed (V _c), the formula (2) and (3) further comprises the step of replacing said first speed (V _c) to a value calculated by Equation (4), the position data How to Determine If You Are Errors.
Equation _{(2): V c> =} MA speed + s2 * MSD speed, However, s2 is a predetermined value,
(3): V _c > MIN _velocity , where MIN _velocity is a predetermined minimum velocity,
(4): MA _speed + s2 * MSD _speed 5. The method of claim 4,
The first acceleration (a _c) is a predetermined maximum acceleration (MAX _{acceleration),} the said first position data (P _c) or more in the determination is made that the error, wherein the first speed (V _c) one wherein the not less than (MA _speed ) value of the _speed calculated from the other position data. 6. The method of claim 5,
Wherein the MA _speed is adapted to be updated to reflect the first speed (V _c ) or the replaced first speed. 7. The method according to claim 1 or 6,
If it is determined that there is an error in the first position data (P _c )
The speed (V _c) how the value of the speed (V _c), whether the error location data, comprising a step of replacing one of interpolation values using a plurality of speed values adjacent to the crystal. 9. The method of claim 8, wherein the interpolation is performed according to equation (5).
Equation _{(5): ((V c} + 1 - V c-1) × (t c - t c-1)) / (t c + 1 - t c-1) + V c-1,
T _c-1 , t _c , and t _{c + 1} represent the absolute time in the position data indexes c-1, c, c + 1, respectively. 9. The method of claim 8,
Wherein the at least one parameter is calculated from a plurality of position data included in a window having an adjustable size,
Wherein the interpolation is performed using a plurality of data included in the window.
How to determine if location data is corrupted. The method according to claim 1,
Wherein the at least one parameter is calculated from a plurality of position data included in a window having an adjustable size,
The size of the window may be increased to a first predetermined value if it is determined that all of the M consecutive position data are erroneous,
And if it is determined that there is no error in all of the L consecutive position data, the size of the window can be reduced to a second predetermined value.
How to determine if location data is erroneous. An apparatus for determining whether an error of first position data (P _c ) collected from a user device is present,
A storage unit; And a processing unit,
Wherein the storage unit is configured to store the first position data (P _c ) and past one or more position data collected from the user equipment,
Wherein,
(V _c ) about the first position data (P _c ) using the first position data (P _c ) and the past one or more position data collected from the user device, and
Wherein the first position data (P _c ) is judged to be erroneous when the first speed (V _c ) satisfies the formula (1)
A location data error determination device.
(1): V _c > f (P),
Wherein P is at least one parameter for determining the shape of a probability distribution used to fit one or more other position data collected by the user equipment, A parameter including a statistical value calculated based on a probability distribution using at least one determined speed,
f () is a function that takes the parameter as an independent variable and outputs a value that can be compared with the first speed (V _c ). A computer-readable medium storing a program to be executed by an apparatus for determining whether or not an error of first position data (P _c ) collected from a user device is present,
The program includes:
In the apparatus,
Calculating a first velocity (V _c ) for the first position data (P _c ) using the first position data (P _c ) and the past one or more position data collected from the user device; And
Determining that the first position data (P _c ) is erroneous if the first speed (V _c ) satisfies the formula (1)
A computer-readable medium intended to be executed.
(1): V _c > f (P),
Wherein P is at least one parameter for determining the shape of a probability distribution used to fit one or more other position data collected by the user equipment, A parameter including a statistical value calculated based on a probability distribution using at least one determined speed,
f () is a function that takes the parameter as an independent variable and outputs a value that can be compared with the first speed (V _c ).

Images