WO2013147560A1 - Method for correcting position information - Google Patents

Description

Position information correction method

The present invention relates to a method for determining whether there is an error in position data collected by a user device and a technique for correcting a position value in which an error exists.

People tend to be reluctant to choose places they don't visit often as destinations. In this regard, various studies exist for predicting a person's visit destination. In order to predict a person's movement, we must first obtain accurate location data about that person. To this end, well-known location data systems such as GPS, GLONASS and Galileo can be used. Alternatively, wireless network positioning using a WIFI location approach as a mobile base station or crowd source may be used. These methods may be implemented in a mobile user device. However, there may be an error in the raw position data actually measured. There are many errors in the location data measured by mobile user equipment manufactured by a specific company. It is necessary to filter the obvious errors and further correct the position determined to be an error.

Experiments have shown that more than 12% of actual location data collected from commercial smartphones, portable GPS devices, WIFI location sensors for crowd sourcing, cellular network devices, and the like appear. Therefore, it is necessary to filter out the location data in error. Furthermore, it is necessary to simply correct the erroneous position data. The present invention seeks to provide a method for solving this problem. In addition, a method for solving such a problem is to provide a method for real-time implementation so that it can be performed in a user device with limited computing ability.

A method according to an aspect of the present invention for determining whether there is an error in position data measured by a user device is a statistical technique using mean, expectation, and standard deviation calculated for the measured speed. Can be used. Also, a technique using the measured value of acceleration can be used.

The method according to an aspect of the present invention for correcting a position value determined to be an error may use a statistical technique based on a calculated difference with respect to the measured position value.

In the present specification, 'measurement' may mean directly acquiring information about a position, a speed, and an acceleration from a user device that does not use the position data filtering method and the position data correction method according to the present invention.

The measured values of the speed and acceleration of the user can be obtained from the movement position data having the format of <latitude, longitude, time> measured from the user equipment. Hereinafter, the moving position data having a format of <latitude, longitude, time> may be referred to as a 'tuple' or 'location data tuple'.

In the present invention, using the data selected by the moving window (or sliding window), it is possible to calculate the statistics of position and velocity and to update the calculated values repeatedly. The measured position data may be filtered using the controllable parameter. Since the algorithm according to the embodiment of the present invention is simple, the present invention can be applied to a mobile user equipment having a small computing power.

In an embodiment of the present invention, the size of the moving window may be optimized to improve performance. Also, a backtracking interpolation method can be used to replace the speed value and / or position value determined to be an error with an appropriate estimate.

Since the velocity does not increase rapidly above a certain level, if the mean value and standard deviation of the velocity at a certain time interval are known, for example, a significant interval following a normal distribution can be set and this interval can be set. The passing speed can be determined as an error value.

The location information processing method according to an aspect of the present invention processes information on a tuple including latitude, longitude, and time stamp collected from the location information collecting device. At this time, the current speed at the time stamp [i] (V _i) is, the time stamp [i -1] in the case of an exchange included in the window that includes greater than a statistical value calculated from the speed, the time stamp [i A first step of determining that there is an error in the tuple [ i ] at; And a second step of replacing the information about the tuple [ i ] with an estimated value when it is determined that the error exists. In this case, the second step may be performed at a time stamp immediately after the time stamp on which the first step is performed.

In this case, the statistical value may be a mobile confidence interval obtained from the past speeds. Specifically, the mobile confidence interval may be a value obtained by adding an average value MA _speed of the past speeds to a first value s × MSD _speed that is proportional to the standard deviation of the past speeds.

At this time, this processing method includes a speed [ i + 1] at timestamp [i + 1] including timestamp [ i − n + 1] to timestamp [ i ] before calculating the estimated value. Determining that an error exists in the speed [ i + 1] if it is greater than a second statistical value calculated from past speeds included in the window; And if it is determined that the velocity error in [i +1] is present, can be prior to the step of the estimated the speed comprising [i +1] replace previously in the second statistics more. Here, the second statistical value may be MA _speed + s _99.5 × MSD _speed . Here, s _99.5 means a confidence interval of 99.5%, but another parameter indicating a different range of confidence intervals, for example, s _99.9 which means a confidence interval of 99.9% may be used.

The processing method may further include determining whether an error has occurred for the tuple [ i -1] in the time stamp [i-1]; If the acceleration error for the tuple [i -1] is not generated speed error for the tuple [i -1] occurs, by calculating the statistical values described above, measured in the time stamp [i -1] Determining whether the determined speed value is smaller than the aforementioned statistical value; And is smaller than the actual speed value above which the statistics case, the step of replacing the speed, latitude, and longitude for the time stamp [i -1] to the values measured in the time stamp [i -1] It may further include. In this case, n is the size of the window.

According to the present invention, it is possible to filter out the location data in error in real time, and provide a technique for replacing in real time using the corrected new location data instead of discarding the location data determined to be in error.

1 is for explaining a speed calibration algorithm according to an embodiment of the present invention.

2 is a view for explaining a speed calibration method of interpolating a speed value by a least square method according to another embodiment of the present invention.

3 to 5 illustrate a position tuple filtering method, a speed estimation method using interpolation, and a speed error correction method according to an embodiment of the present invention.

6 is for explaining a speed error detected without speed correction according to an embodiment of the present invention.

7 illustrates a speed error detected by applying a speed correction according to an interpolation technique according to an embodiment of the present invention.

Fig. 8 shows the speed measured using a commercially available position detection device.

9 and 10 are graphs derived by applying the concept of a moving intention interval, acceleration error detection, and correction speed according to the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be implemented in various forms.

The movement trajectory (trace) of the user may be represented using a set of tuples (ie, a moving data tuple) measured and collected in the form of <latitude, longitude, time>. By combining this tuple with an identification parameter identifying each tuple, a data set representing user mobility can be obtained. One tuple obtained for the time t is herein referred to as P _t, and can be referred to as _t, respectively lat, lon _t latitude and longitude provided by the P _t.

Using the contents disclosed in Ref. [1] shown below, two consecutive tuples, <lat_i-1, lon_i-1> And <lat_i, lon_iTime t using>_iTravel distance from_iAnd speed V_i, And acceleration a_iCan be calculated. Therefore tuple P_t<T, lat contains additional attributes_t, lon_t, D_t, V_t a_tIt can have a core form such as>. T, lat mentioned above_t, lon_t, D_t, V_t, a_t May be referred to herein as an actual value.

* Reference [1]: 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).

Table 1 shows the typical maximum speeds that can occur depending on the mode of transport. For example, the maximum speed MAX _speed for applying to an embodiment of the present invention may be defined as 250 m / s. In addition, MAX _acceleration can be expressed by defining the maximum value of acceleration considered to be possible in everyday environment. If the measured speed or acceleration is greater than MAX _speed or MAX _acceleration , it can be determined that an error has occurred.

Table 1

Then, the moving average of speed can be calculated and the moving standard deviation of speed can be calculated.

At any time t, the moving average value of the speed and the moving standard deviation value can be expressed as MA _speed (n) and MSD _speed (n), respectively. N represents the number of past data of {P _x : t-n + 1 ≦ x <t}, which is a set of tuples. At this time, the past n data can be obtained by applying a window of size 'n'.

Once a new tuple P _t is obtained, it can be ascertained whether V _t and a _t calculated from the tuple P _t are acceptable values in the everyday environment. If the calculated V _t is outside the range of normal distribution according to the moving average value MA _speed (n) and the moving standard deviation of _speed MSD _speed (n), the tuple P _t is filtered out from a series of traces. (Ie, removed). The condition for removing P _t may be given by Equation 1 below.

[Equation 1]

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

In Math 1, 's' represents the sensitivity of filtering and is a user controllable parameter.

If V _t does not satisfy Equation 1, it is determined that the new tuple P _t has a valid value, and the new values can be used to update the values of MA _speed (n) and MSD _speed (n). This calculation is relatively simple and can be performed in real time on a low power device such as a mobile user equipment.

The filtering characteristic may vary depending on the size n of the window described above. Therefore, in order to perform an experiment to determine the influence of the window size, it is possible to collect the value measured by a commercial mobile user equipment. The user device may store and output location data whenever it detects a change in location. Alternatively, if the user device is in the stopped state, the location data may be stored and output every user defined interval, for example, every 3 to 60 seconds. The location data thus obtained may be displayed on a map using various techniques.

According to an experiment for the present invention, commercial user equipment sometimes provided the location data obtained in three different ways at the same time. That is, a location using a cellular base station, a location using a WiFi device for a crowd source, and a location using a GPS were simultaneously provided. At this time, the values of the three types of location data provided at the same time indicate different values. When multiple position values are obtained at the same time, experience has shown that position data with the smallest velocity value is likely to be valid data. Therefore, in the first step of filtering the position data, it is possible to select a method of selecting the position data that has moved the least from the previous position among the plurality of position data provided by different methods at the same time.

Various experiments were performed by varying the size of n to determine the optimal value of the size n of the window applied to the algorithm used for the location data filtering.

If the window size is large, the algorithm can successfully cope with successive errors in the absence of movement, but it can be expected that it will not respond to situations where the speed changes rapidly.

On the other hand, if the window is small, it will show a quick response to sudden speed changes to the moving state, which is believed to contain consecutive error tuples. However, if there are m consecutive errors, m> n, i.e. if the window size is small, the errors cannot be filtered out.

In order to confirm this, various experiments were performed while changing the window size n of the measured dataset. In each experiment, n = 5, 10, 25, 50, and 100 were set. For each case, the moving average of the speed and the moving standard deviation of the speed were calculated.

The larger the window size, the longer the effect of the error will be maintained if data with very large errors are entered into the measured speed value. As a result, an under filtering phenomenon occurs on the data in error. When the window size is 100 or 50, it is confirmed that there is a tailing effect (tailing effect).

On the other hand, when the window size is small, especially at the beginning of the speed change, it reacts quickly and sensitively to the speed change. However, they tend to overfilter out the right data. When the window size is as small as 5 or 10, there are cases where two or more tuples that appear to be correct velocity data are removed.

From the above phenomenon, it can be seen that in order to avoid the tailing effect according to the window size, the adjustment mechanism for the moving window must be introduced.

Hereinafter, pre-experiments for identifying errors in the measured position data will be described.

In this preliminary experiment, the position data was collected for several hours while the position detection devices were fixed in the outdoor and the indoor. The first position detection device is a commercial Garmin GPSMAP62s, used purely for GPS data collection. The second location detector is a commercial Samsung Galaxy Tab, used to obtain location data from a 3G base station (3GBS) connected to the device. It was assumed that more error would be shown in the position data obtained using 3GBS, and both position data obtained from GPS and 3GBS would indicate an error. In particular, it was assumed that the position detection error would be shown indoors. The results of this preliminary experiment are shown in Table 2. Table 2 shows the errors that occur when measuring location data. The unit of measurement is meters.

TABLE 2

The error distance is calculated from the position data, and the variance and average of the error distance can be calculated. As expected, 3GBS showed a larger error rate, larger error size, larger maximum error size, and larger standard deviation of error size. In the Garmin GPSMAP62s, even if the GPS signal is lost, the user's position is calculated based on past speeds, resulting in very large errors indoors. Therefore, indoor GPS data can be thought of as not meaningful data. GPS data in the open air has a sufficient level of accuracy to obtain sophisticated location data, 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. [Algorithm 1] of Table 3 is for determining whether there is an error in the measured position data and filtering the position data having an error. Upon acquiring new position data P _{i + 1} , this [Algorithm 1] can determine whether to filter P _{i + 1} .

TABLE 3

The function of each part of [Algorithm 1] of Table 3 is demonstrated below.

* In the 3rd to 6th of [Algorithm 1]: If there are less than n tuples, complete data can be prepared to fill a window of size n. Instead, a small amount of information can be used to construct an incomplete window.

Lines 8-10 in Algorithm 1: Acceleration and velocity can be used as parameters for filtering and can be used in different ways, but they can all be considered as throttling parameters. Tuples with out-of-range or over-acceleration are filtered out of the so-called 'moving significant interval' values, where velocity V _{i + 1} is expressed as MA _speed + s × MSD _speed . s represents the significant level of the normal distribution.

_* Line 11 ~ 13 in Algorithm 1: If the speed of one tuple is too big, MA_speedAnd MSD_speed This affects the value and results in filtering errors, such as extending the confidence interval, resulting in the filter-in tuples to be filtered out. As such, if the speed of one tuple is too large, to include the change in speed as fast as possible and to avoid errors in extending the confidence interval, MA_speed(n) + s_99.5 * MSD_speed= MA_speed(n) + 2.57 * MSD_speedYou can modify the speed using.

* S in line 11-13 of Algorithm 1_99.5: s_99.5= 2.57 represents a 99.5% confidence interval of the normal distribution. This is an adjustment parameter that reduces the effect of erroneous speed on the moving window.

Line 12 in Algorithm 1: 99.5% confidence interval of the normal distribution to reflect the speed of this tuple in the moving window, even if a tuple needs to be filtered out by Equation 1: It may be limited or calibrated to be within, to include the speed of this tuple. This is intended to update the mobile window with fast speed values to cope with rapid changes in speed. That is, even if there is an error-free tuple, a sudden speed change may be filtered out. In such a case, even if the tuple is filtered, the moving window may reflect the speed change of the maximum allowable for this tuple.

* Line 11 MIN in [Algorithm 1]_velocity: Since human walking is usually possible at speeds less than 2.77 m / s (10 km / h) and is in the GPS error range, speeds less than 2.77 m / s (10 km / h) are not filtered out.

* MAX 14th line in [Algorithm 1]_acceleration: Tuples with unrealistic acceleration are filtered out.

Lines 12-16 in Algorithm 1: Once a tuple with excessive acceleration is filtered out, the acceleration value of this tuple is calibrated with MAX _acceleration , and the velocity value negates the effect of unrealistic velocity values. nullify) to correct for MA _speed (n).

Because it is always possible for a vehicle to stop quickly with a large negative acceleration, tuples with negative acceleration values are considered valid without errors. On the other hand, tuples with positive acceleration values greater than MAX _acceleration are considered to be in error.

In Algorithm 1, the two variables n and s can be set by the user. n is the number of tuples in the window, that is, the size of the window, and s is the sensitivity level of the filtering (ie, the significance level of the normal distribution). The user sensitivity level s can be determined relatively simply. From the characteristics of the normal distribution, s with an appropriate confidence interval can be obtained. Since we will use only positive regions of the normal distribution for filtering, we can set s = 1.64 for 95% confidence intervals and s = 2.33 for 99% confidence intervals. Users can determine s according to their own purpose. For example, the sensitivity level s can be selected as follows. Table 2 shows typical error rates for position data collection when the device is not moving. In the case of GPS, there was an error in 12.3% of the position data, and in the 3GBS cellular position detection system there was an error in 36.75% of the position data. In this case, therefore, s = 1.16 may be set for GPS data and s = 0.34 for cellular position detection data.

As described above, since the trailing effect occurs when the size of the window is large, the size of the window may be made smaller. By [Algorithm 1], the incorrect speed value is calibrated, the abnormal acceleration value is limited, and the speed value can be replaced by the average speed calculated by the moving window. Several experiments were conducted to investigate the effect of window size on the calibration mechanism. In the first experiment, the window size was selected as n = 5, 10, 25, 50, 100, and the sensitivity level was selected as s = 1.16, and it was assumed that 88% of the measured position data were accurate data. The smaller window size limits the trailing effect, but results in a more flexible response to speed changes. In the first experiment, we found good results when the window size was 5 or 10.

In the second experiment, we consider the effects of continuous errors. Successive errors can affect the moving average and moving standard deviation used in this algorithm. There were up to four consecutive errors in the location data set used in the actual experiment. Therefore, for the second experiment, we concluded that n = 5 is not sufficient, and we conclude that n = 10 can cope with continuous errors and reduce the tailing effect due to the larger window size. Thus, in this experiment, the window size was finally determined to be 10. If you are experiencing a greater number of consecutive errors, you can choose a window size that is suitable for this or dynamically increase the size of the window.

Two conclusions can be obtained from various experiments using [Algorithm 1] according to the present invention. First, proper window size and sensitivity levels can provide adequate filtering results. Second, filtering can be performed on all of the location data sets according to various combinations of window sizes and sensitivity levels. Table 4 shows the percentage of filtered-out tuples for each combination of parameters. The user 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 [Algorithm 1], 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 constants of the algorithm, such as MAX _accelertaion , s _99.5 (= maximum sensitivity level), and MIN _velocity (= minimum threshold of speed for filtering).

Table 4

Algorithm 1 can be modified in consideration of the following.

First, instead of defining the size of the window as the number of tuples in one window, it can be defined by the time interval included in the window. Considering that speed is a function of time, it can be seen that this modified approach will be effective and accurate when collecting location data regularly.

Second, it is possible to dynamically calibrate the window size. In another embodiment modified from Algorithm 1, the window size may be dynamically increased or decreased according to the number of consecutive errors. Once we find that the number of consecutive errors is large, we can increase the window size to minimize the effect of the continuous errors on the moving average and the moving standard deviation. If the number of consecutive errors is small, the window size can be reduced to respond appropriately to rapid speed changes and to reduce the amount of computation for filtering.

번째 튜플을 필터링할 수 있다. 이 방법은 완벽하게 실시간으로 구현될 수 없을지라도 언더 필터링과 오버 필터링의 경향을 줄일 수 있다. Third, [Algorithm 1] can be transformed into a pseudo real time algorithm rather than a real time algorithm. For window size n, we're going to be in the middle of the window instead of filtering the (n + 1) th tuple

The first tuple can be filtered. This method can reduce the tendency of underfiltering and overfiltering even though it cannot be implemented in full real time.

번째 튜플을 윈도우 내의 n개의 튜플들을 이용하여 인터폴레이션 하는 것이다. 더 정밀하게 추정(estimation)하기 위하여 n개의 튜플들로부터 추정된 점근 곡선(asymptotic curve)을 이용하여 윈도우 내의 중앙 튜플(middle tuple)을 인터폴레이션하여 더 정밀한 인터폴레이션을 가능하게 할 수 있다. 그러나 이 때문에 계산 오버헤드(computational overhead)가 발생할 수 있기 때문에 이동형 사용자기기에 적용하기 어려울 수 있다.Fourth, an interpolation technique can be added to [Algorithm 1]. Algorithm 2, shown in Table 5 below, adds the steps for interpolation to Algorithm 1 (see lines 18 to 21 of Algorithm 2). When a new tuple (index i + 1) is obtained, if the last tuple (index i) in the currently existing window is found to be filtered out, the speed of this last tuple can be replaced with the interpolated value. Using such interpolation, it is possible to provide a more precise movement window introduced for filtering tuples (see line 18 to 21 of [Algorithm 2]). That is, according to the last part of [Algorithm 2], each time a new tuple is obtained, the last tuple marked as filtered out in the window can be interpolated. Another variation for the construction of moving windows for more precise approximation is that the approximate midpoint of the window

The first tuple is interpolated using n tuples in the window. In order to more accurately estimate, an asymptotic curve estimated from n tuples can be used to interpolate the middle tuple in the window to enable more precise interpolation. However, this may result in computational overhead and may be difficult to apply to mobile user equipment.

Table 5

1 is for explaining a speed correction algorithm according to an embodiment of the present invention.

The horizontal axis of FIG. 1 represents an index (ie, a timestamp) of tuples obtained continuously, and the vertical axis is a speed according to each tuple stored in a memory. In FIG. 1, the size n of the moving window is illustrated as 10. The MA _speed and MA _speed + s _99.5 × MSD _speed can be calculated from the 10 speeds present in the moving window, an example of which is shown in FIG. In FIG. 1, it is assumed that acceleration a _{i +} 1 at index [i + 1] is greater than MAX _acceleration . Therefore, the speed V _{i + 1} at the index [i + 1] was corrected to MA _speed (row 15 of [Algorithm 2]). In FIG. 1, it is assumed that the moving data tuple P _i for the index [i] is marked as already filtered out according to [Algorithm 2] (row 18 of [Algorithm 2]). If a tuple is filtered out, it means that it has determined that there is an error in the location indicated by the tuple, but the velocity or acceleration values calculated from that tuple may still be stored. Thus [Algorithm 2] 19 to 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, depending on the line of Replaced with a linear interpolated value. Thus, according to Algorithm 2, the newly acquired tuple is first calibrated by lines 10 to 17 of Algorithm 2. Then, when another new tuple is acquired, the calibrated rate is [algorithm]. Can be calibrated secondaryly by lines 18 to 21 of 2]. It can be appreciated that the primary and secondary corrections described above for the speed of any tuple may occur, only one of them, or none at all.

Speed V _i is the interpolation with the calibration value of the aforementioned tuple P _i in [Algorithm 2], but little is usually less than the value _{(MA speed + s 99.5 × MSD} speed) corrected by the second line 11, in the next time stamp It may be larger depending on the interval of movement or the corrected value of.

In Algorithm 2, the newly acquired mobile data tuple P _{i + 1} and the latest mobile data tuple P _i present in the mobile window are processed. Alternatively, in another embodiment of the present invention, it can be modified to perform processing for the moving data tuple P _m for any time stamp in the moving window. To this end, rows 18 to 21 of Algorithm 2 may be modified as shown in Table 6.

Table 6

2 is a view for explaining a speed correction method of interpolating a speed value by a least square method according to another embodiment of the present invention.

2 shows the results of using the modified interpolation method from the interpolation method according to the 18th to 21st lines of [Algorithm 2]. In FIG. 2, a nonlinear interpolation method using a plurality of data in a moving window is used. For example, a moving data tuple having an index [i-4] may be corrected using a plurality of data included in the moving window and a value corresponding to an asymptote approximated using a least square method.

3 to 5 illustrate a position tuple filtering method, a speed estimation method using interpolation, and a speed error correction method according to another embodiment of the present invention.

3 to 5 represent the index of the time stamp and the vertical axis represents the speed. Reference numeral 100 denotes the measured velocity in the corresponding timestamp, and reference numeral 101 denotes the measured velocity obtained from the tuple filtered out using one of the algorithms disclosed herein. 3 to 5 show an example in which the window size is 10. Reference numeral 103 denotes an average value of the speed in the window and reference numeral 102 denotes a value 102 of the moving significant value described above. The position tuple of reference numeral 101 shown in Fig. 3 is filtered out because its speed is larger than the value 102 of the movement significance section.

Reference numeral 101 (index i) of FIG. 4 represents an actual velocity obtained from the filtered position tuple according to the algorithm of the present invention. Reference numeral 200 in FIG. 4 denotes an estimated value of the speed provided by the speed value of index i being linearly interpolated by the speed values of index i-1 and index i + 1 before and after it.

In FIG. 5, the tuples of the index i and the index i + 1 are both filtered out. At this time, since the measured speed of the index i (see reference numeral 101 of the index i) is larger than the value of the movement intention interval, it has already been calibrated to a predetermined size (see reference numeral 300 of the index i). Then, the measured speed of index i + 1 (see reference numeral 101 of index i + 1) is also calibrated to a predetermined size because it is larger than the value of the movement intention interval (see reference numeral 300 of index i + 1). . Then, since the tuple of index i is filtered out, the speed of index i is interpolated using the speeds of index i + 1 and index i-1. In other words, in one embodiment of the present invention, a calibration of speed may be used as a pre-step for accurate estimation of speed.

Using Algorithm 2, we can estimate the velocity of the filtered out tuple of the measured tuples, but the position value of the filtered out tuple is simply removed. By using [Algorithm 3] shown in Tables 7 and 8 below, the position values for the filtered out tuples can be estimated. In the velocity estimation of Algorithm 2, only the positive velocity value was considered. However, since the directionality exists in latitude and longitude, in the position estimation added to Algorithm 3, the negative The difference is that you can't ignore the difference.

TABLE 7

Table 8

Hereinafter, a position correction method according to an embodiment of the present invention will be described using the contents of Algorithm 3.

In Algorithm 3, the parameter ET _D for introducing a normal distance error is introduced (line 4). From the Circular Error Probable (CEP) concept of a conventional positioning system, for example, ET _D can be set to 15 m for a GPS system with SA enabled. Of course, it is possible to change the value of ET _D depending on the accuracy of the positioning system. ET _D may determine the minimum speed, minimum difference between latitude and longitude, and affect the moving standard deviation, resulting in a non-zero moving significance interval. That is, by using ET _D , the concept of CEP of the positioning system can be introduced in Algorithm 3 according to one embodiment of the present invention, which overfilters tuples because of small possible speed error within the accuracy of the positioning system. Can be avoided.

According to [Algorithm 3], similar to the velocity estimation process of [Algorithm 2], a position estimation process can be introduced for the filtered tuple. The main difference in the location estimation process included in Algorithm 3 lies in the direction of latitude and longitude. In other words, only a positive value needs to be considered for the velocity value, but a negative difference between latitude and longitude cannot be ignored to estimate the position. [Algorithm 3] shows the entire process for position estimation, which corresponds to the entire process for velocity estimation of [Algorithm 2].

Vlat and Vlon in [Algorithm 3] refer to the difference between latitude and longitude, respectively. Algorithm 3 calculates the moving average of Vlat and Vlon. If one tuple is filtered by excessive speed, this indicates that the difference in position is excessive. Once this is done, we need to estimate the correct position. When an acceleration error occurs, the position data is corrected to a moving average value of the difference value (rows 25 and 26), similarly to that performed for the speed. Finally, as with the velocity estimation, interpolation is performed for latitude and longitude at the end of the travel window (lines 31 and 32). The direction of the difference is also preserved (lines 25, 26, 31, and 32).

In line 4, when the time interval of the position tuple increases, the MIN _speed value due to ET _D may become very small. In order to ensure a constant lower limit of the MIN _speed value, the four lines of code are set to "Set MIN _speed = (ET _D / (t _{i + 1} -t _i )> MINSPEED)? ET _D / (t _{i + 1} -t _i ): MINSPEED ". MINSPEED is the lowest speed arbitrarily set by the user of the invention.

FIG. 6 illustrates speed errors obtained from measured data, and FIG. 7 illustrates speed errors detected by applying speed correction according to an interpolation technique according to an exemplary embodiment of the present invention. Each figure contains information about the actual speed, the acceleration, the section of motion, the calibrated speed, the estimated speed, and the detected acceleration error. Acceleration errors are shown in inverted triangle shapes. 6 does not include information on the interpolated speed. An empty rectangle represents a limited speed according to a calibration mechanism according to an embodiment of the present invention, and a black rectangle represents an estimated speed by an interpolation technique. The velocity on the y-axis is in m / s, and the x-axis represents time of day. Although an error was found in which the measured speed was located outside the moving significance section near 13:33:06, the algorithm according to an embodiment of the present invention estimated the possible speed value well. On December 18, 2012 13:32:59, a clear error due to the acceleration limitation was issued, but the speed error was limited to an appropriate range by the calibration method of the present invention, and then the speed was corrected by the speed estimation method. . Rather than correcting the error speed, the method of estimating the speed by the interpolation method can further reduce the influence on the moving window. Therefore, in FIG. 7, the moving significance interval following the interpolation shows a difference, since the statistical value of the moving window varies according to the interpolated speed value. The difference at 13:33:04 is quite large.

Tables 9 to 11 are for explaining the fourth algorithm for position estimation according to another embodiment of the present invention.

Table 9

Table 10

Table 11

[Algorithm 4] is the same as [Algorithm 3] except lines 2, 5, 6, 17-25, 28-32, and 38 of [Algorithm 4]. Hereinafter, the lines 5, 6, 17-25, 28-32, 38 of [Algorithm 4] are demonstrated.

* Line 2 of Algorithm 4 to count the number of consecutive errorsNCE(Number of Continuous Error) and initialize its value to zero.

* Line 5: [Algorithm 4] V can be changed to another value by another part of [Algorithm 4]. For example, in lines 35, 39, and 45 of Algorithm 4, V may be replaced by another calibrated or estimated value. However, in line 20 of Algorithm 4, we can replace this replaced estimate with the original value (= value stored after being calculated from the measured value). In order to do this, in line 5, the original value of V Save it.

* Line 6 of Algorithm 4 sets the MIN _speed for the minimum speed to the smaller of ET _D / ( t _{i +1} - t _i ) the predetermined minimum value MINSPEED . That is, it determines the minimum value of the moving standard deviation.

Lines 17 and 18 of [Algorithm 4]: Different parts of [Algorithm 4] can change lat and lon to different values. For example, in lines 41, 42, 47, and 48 of Algorithm 4, lat and lon can be replaced with other calibrated or estimated values. However, in lines 21 and 22 of Algorithm 4, we can replace this replaced value with the original value. To do this, we store the original values of lat and lon separately in lines 17 and 18.

* Line 19 of [Algorithm 4]: Line 19 of [Algorithm 4] represents a condition for performing backtracking shown in lines 20 to 22 of [Algorithm 4]. At this time, three conditions are reviewed: first, the tuple ( P _{i -1} ) at the backtracking review timestamp (= i -1) must be filtered or interpolated, and second, the backtracking review timestamp (= i). The tuple ( P _{i -1} ) at _-1 ) must not be filtered (accel_filtered) by the acceleration error, and third, the original velocity of the tuple at the backtracking review timestamp (= i -1) ( V _{i-1). , original} ) must meet the condition that the movement must be within the movement-interval ( MA _speed + s × MSD _speed ) determined by the window defined by the time stamp [i-n + 1, ..., i].

* Lines 20 to 24 of [Algorithm 4]: Lines 20 to 22 of [Algorithm 4] replace the V, lon, and lat values with the original values when the condition of Line 19 of [Algorithm 4] is satisfied. have. That is, it is determined that the original V, lon and lat values are more accurate than the V, lon and lat values that have been corrected or estimated by other parts of [Algorithm 4], and return to the measured data (backtracking). If backtracking occurs, initialize NCE to 0 on line 23 and reduce window size n on line 24. However, the window size n cannot be smaller than the minimum value IWS .

Lines 28 and 29 of [Algorithm 4]: Increase NCE on line 28 if the tuple P _{i +1} is filtered. That is, to increase the number of consecutive errors. In line 29, we increase the window size n. However, the window size n cannot be larger than the maximum value MWS .

* Lines 31 and 32 of [Algorithm 4]: If tuple P _{i +1} is not filtered, initialize NCE to 0 in line 31. And reduce the window size n in line 32. However, the window size n cannot be smaller than the minimum value IWS .

* Line 38 of [Algorithm 4]: If the newly measured acceleration is greater than the maximum acceleration, filter the newly measured tuple, and record it as accel_filtered.

Figure 8 shows the speed measured using a commercial position detection device iPhone and Garmin. In this experiment, the speed changes with a continuous value over time, but the actual data of iPhone and Garmin show that the sudden increase and decrease of the speed sometimes occurs, which is an error.

9 and 10 are graphs derived by applying the concepts of a moving significant interval, acceleration error detected, and calibrated speed described in the above-described embodiment of the present invention. 9 shows that the window size is set to 5, and FIG. 10 shows the result of setting the window size to 100. FIG. 9 and 10 use 287 measured position data acquired on February 27, 2012.

When the window size is small as shown in FIG. 9 (n = 5), the moving section and the correction speed sensitively reflect the change in speed. However, as shown in FIG. 10, when the window size is large (n = 100), it can be seen that the moving section and the correction speed do not sensitively change the speed due to the tailing effect.

11 shows an example of data processed according to [Algorithm 4]. This graph was created using nine position data measured on August 28, 2012, and it detects filtered original speed, moving significant interval, acceleration, and acceleration error. (acceleration error detected), interpolated speed, calibrated speed, and revived speed by backtracking. At time 08:49:54, the filtered original velocity is not only out of the range of movement mean but acceleration error is detected, thus maintaining the interpolated velocity. On the other hand, at time 08:49:56 and time 08:49:59, since the original speed is in the range of movement significance and acceleration error was not detected, it was confirmed that the playback was replaced by the interpolated speed by [Algorithm 4]. Can be.

Hereinafter, a position correction method according to an embodiment of the present invention will be described with reference to [Algorithm 4].

In order to process information about a tuple including latitude, longitude, and a timestamp collected from the location information collecting device, the following steps may be performed.

In step S11, it may be determined whether there is an error in the speed [i + 1] (V _{i + 1} ) at the time stamp [i + 1] (see line 34).

In step S12, if it is determined in step S11 that there is an error in speed [i + 1] ( V _{i +1} ≥ MA _speed + s _99.5 × MSD _speed ), the speed [i + 1] is corrected in advance. Calibrate or restrict (see line 35). At this time, if the speed [i + 1] is less than or equal to the predetermined minimum speed (MIN _speed ), it is determined that there is no error in the speed [i + 1] (see line 35). In this case, the minimum speed may be determined by an error tolerance of distance (ET _D ) or a predetermined minimum value MINSPEED (see line 6).

In step S13, it is determined whether there is an error in the acceleration [i + 1] (a _{i + 1} ) at the time stamp [i + 1] (see line 37). In this case, when the acceleration [i + 1] is greater than or equal to the preset maximum acceleration (MAX _acceleration ), it may be determined that there is an error in the acceleration [i + 1] (see line 37).

In step S14, when it is determined in step S13 that there is an error in acceleration [i + 1], latitude [i + 1] and longitude [i + 1] are corrected in advance (lines 41 and 42). Reference). At this time, the hardness [i + 1] is corrected using the average hardness difference (MA _Vlongitude ) up to the time stamp [i] and the hardness [i] (lon _i ) in the time stamp [i], and the time stamp [i] Latitude [i + 1] can be corrected using the mean latitude difference (MA _Vlatitude ) and latitude [i] (lat _i ) in time stamp [i] (see lines 41 and 42). Here, the average hardness difference (MA _Vlongitude ) set in the 16th row of Algorithm 4 means the average value of the hardness difference in each timestamp set in the 14th row according to the time, and the average latitude difference set in the 13th row _Vlatitude ) means the average of the latitude difference in each timestamp set in row 11 over time.

In step S21, it is checked whether there is an error in the tuple [ i ] ( P _i ) at the time stamp [ i ] ( t _i ) (see line 44). In this case, an error means that the tuple [ i ] ( P _i ) is filtered by the speed error as described above.

In step (S22), if it is determined that the error is present, the time stamp [i +1] (t _{i +1)} latitude in [i +1] (lat _{i +1)} and the time stamp [i ] the interpolation of one or more previously acquired latitude estimation (estimation) latitude [i] (lat _i) in the time stamp [i], and the hardness at the time stamp [i +1] [i +1 ] ( lon _{i +1} ) and one or more longitudes obtained before the timestamp [ i ] are interpolated to estimate the longitude [ i ] ( lon _i ) at the timestamp [ i ] (see lines 47 and 48). ). In this case, 'acquired' may mean that the algorithm is processed by [Algorithm 4] and stored in the memory.

In this case, when it is determined in step S21 that the error exists, the location calibration method according to the embodiment may further include step S23.

In step S23, the speed [i + 1] (V _{i + 1} ) at timestamp [i + 1] and one or more speeds obtained before timestamp [i] are interpolated to generate the timestamp [i]. The velocity [i] (V _i ) at can be estimated (see line 45).

In step S31, if the error in time stamp [ i -1] is caused by an error due to speed and not due to an error due to acceleration, time stamp [ in +1] to time stamp [ i]. Statistical values using the mean of the stored speeds ( MA _speed ) and the standard deviation ( MSD _speed ) can be calculated to determine whether the measured speed value in the timestamp [ i -1] is less than the statistical value. (See line 19). Here, 'stored speed' refers to a value stored in the memory processed by [Algorithm 4].

In step S32, when it is determined in step S31 that the measured speed value is smaller than the statistical value, the speed, latitude, and longitude for the time stamp [ i ] may be replaced by the original value measured. (See lines 20-22). In this case, n is the size of the window.

In step S33, when it is determined in step S31 that the measured speed value is smaller than the statistical value, the n value can be decreased (see line 24).

In step S34, if the time stamp [ i ] is found to have the above error, increase the size of the window (see line 29), and if it is confirmed that there is no error at the timestamp [ i ], The size can be reduced (see line 32). Here, an error may include both an error in speed and an error in acceleration.

According to another embodiment of the present invention, a user device includes: a location information collecting unit configured to collect information about a tuple including latitude, longitude, and a timestamp; And a processing unit configured to process information about the tuple.

In this case, the processing unit may perform lines 19, 20 to 22, 24, 29, 32, 34, 35, 37, 41, 42, 44, 45, 47, and 48 of [Algorithm 4].

Each of the above steps can be executed at every timestamp. Algorithm 4 is described based on the time point of the time stamp [i + 1] at which the new tuple is obtained. Algorithm 4 may be described as the time stamp [i + 2]. In this case, for example, in the above description of the step S31, the index of the time stamp is increased by +1.

Each of the above steps may be executed in a user device including a location information collecting unit configured to collect information about a tuple including latitude, longitude, and a timestamp, and a processing unit configured to process information about the tuple. have.

Although the present invention has been described with reference to the embodiments shown in the drawings, this is merely exemplary, and those skilled in the art will understand that various modifications and equivalent other embodiments are possible. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

Claims (17)

A method of processing information about a tuple comprising latitude, longitude, and timestamp collected from a location information collection device, The current speed at the time stamp [i], the time stamp [i -1] If included in the window that includes greater than a statistical value calculated from the past velocity, tuple [i in the time stamp [i] Determining that there is an error; And If it is determined that the error exists, replacing the information about the tuple [ i ] with an estimated value Including, Location information processing method. The method according to claim 1, wherein the statistical value is a moving confidence interval obtained from the past speeds. The method according to claim 2, wherein the moving confidence interval is a value obtained by adding an average value of the past speeds to a first value proportional to a standard deviation of the past speeds. The method of claim 1, Substituting the estimated value, Estimating the time stamp [i +1] latitude in [i +1] and the time stamp [i] lat [i] in the time stamp by the interpolation of one or more latitude previously obtained in [i] (estimation) and estimating the hardness [i] in the time stamp [i +1] hardness at [i +1] and the time stamp [i] and the interpolation of one or more hardness to the previously obtained time stamp [i] Steps to Including, Location information processing method. The method of claim 4, wherein Prior to the estimating step, Determining whether there is an error in acceleration [ i + 1] at the timestamp [ i + 1]; And If it is determined that there is an error in the acceleration [ i +1], correcting the latitude [ i +1] and the longitude [ i +1] before the estimating step Further comprising, Location information processing method. The method according to claim 5, wherein in the determining step, when the acceleration [ i + 1] is equal to or greater than a preset maximum acceleration ( MAX _acceleration ), the acceleration [ i + 1] is determined to have an error. . The method of claim 5, In the step of the pre-calibration, using the hardness [i] in the time stamp [i] to the average hardness difference (MA _Vlongitude) and the time stamp [i] and correct the hardness [i +1], the time stamp [i] the average latitude difference (MA _Vlatitude) and the position information processing method that is adapted to correct the latitude [i] the latitude [i +1] by using the above time stamp [i] up. The method of claim 4, wherein The estimating step, If the error is found to exist, a timestamp [iSpeed at +1] [i+1] and the timestamp [iThe timestamp by interpolating one or more previously acquired speedsiSpeed at]iEstimating]. The method of claim 4, wherein Prior to the estimating step, If the time stamp rate [i +1] in the [i +1], is greater than the second statistical value calculated from the past velocity included in the window that includes the time stamp [i], the rate [i + Determining that an error exists at 1]; And Wherein the speed when it is determined that an error exists in the [i +1], in advance prior to the step of replacing the estimated speed to the [i +1] on the second statistics; Further comprising, Location information processing method. The method of claim 9, If the speed [ i +1] is less than or equal to the predetermined minimum speed ( MIN _speed ), it is determined that there is no error in the speed [ i +1], The minimum speed is determined by an error tolerance of distance ( ET _D ) and a preset minimum value ( MINSPEED ), Location information processing method. The method of claim 1, Determining whether an error with respect to the tuple [i-1] in the time stamp [i-1] occurs; When no acceleration error occurs for the tuple [i-1] and a speed error occurs for the tuple [i-1], the measured speed value in the timestamp [ i- 1] is greater than the statistical value. Determining whether it is small; And If the said measured speed is less than the statistical value includes the step of replacing with the actually measured value in the time stamp [i- 1] speed, latitude, and the time stamp for one or more of the hardness [i- 1] for ; More, N is the size of the window, Location information processing method. 12. The method of claim 11, further comprising the step of decreasing the value of n when the measured speed value is smaller than the statistical value. The method of claim 1, wherein if it is determined that that the error exists in the time stamp [i] is to increase the size of the window, it is determined in the time stamp [i] that it does not have the error, the Reducing the size of the window, location information processing method. A location information collection unit configured to collect information about a tuple comprising a latitude, a longitude, and a timestamp; And A processor configured to process information about the tuple Including; The processing unit, If the time stamp rate [i] in a [i], the time stamp [i -1] is greater than a statistical value calculated from the past velocity included in the window comprising a tuple in the time stamp [i] [ i ] is supposed to determine that an error exists, If it is determined that the error exists, the information on the tuple [ i ] is to be replaced with an estimated value, User device. The method of claim 14, If it is determined that the error exists, the processing unit, Estimating the time stamp [i +1] latitude in [i +1] and the time stamp [i] lat [i] in the time stamp by the interpolation of one or more latitude previously obtained in [i] (estimation) and estimating the hardness [i] in the time stamp [i +1] hardness at [i +1] and the time stamp [i] and the interpolation of one or more hardness to the previously obtained time stamp [i] Supposed to User device. The method of claim 15, The processing unit, Before performing the estimation, it is determined whether or not there is an error in the speed [ i +1] at the time stamp [ i +1], That is adapted to the speed when it is determined that there is a [i +1] to the error, before performing the estimating the speed [i +1] a correction (calibration) or advance limit (restriction), User device. 15. The user equipment according to claim 14, wherein the statistical value is a first value that is proportional to the standard deviation of the past speeds plus a mean value of the past speeds.

Images