Patent Publication Number: US-2015087333-A1

Title: Method for correcting position information

Description:
TECHNICAL FIELD 
     The present disclosure relates to a method of determining whether there is an error in positional data collected by a user device, and a technology to correct the value of a position where there is an error. 
     BACKGROUND ART 
     People are apt to avoid selecting, as a destination, a place where they rarely visit. Regarding this matter, there are various research results for predicting a destination that people visit. In order to predict the movement of people, accurate positional data on them should be obtained. To this end, it is possible to use a well-known positional data system such as a GPS, a GLONASS or Galileo. Alternatively, it is possible to use wireless communication network positioning using a WiFi position approach as a mobile communication base station or a crowd source. Such methods may be implemented in a mobile user device. However, there may be an error in raw position data that is actually measured. There are many errors in position data in position data measured by a mobile user device that a specific manufacture manufactures. There is a need for filtering glaring errors and correcting a position determined as an error. 
     DISCLOSURE OF THE INVENTION 
     Technical Problem 
     According to an experiment, 12% or more of actually measured position data that is collected from an available smart phone, a cellular GPS device, a WiFi position detector for crowd sourcing, and a cellular network device has an error. Thus, there is a need to filter out erroneous position data. Furthermore, there is a need to simply correct erroneous position data. 
     The present disclosure provides a method of solving such problems. Also, the present disclosure provides a method of implementing the method of solving such problems in real time so that the latter may be well performed by a user device having a limited capacity. 
     Technical Solution 
     In order to determine whether position data actually measured by a user device has an error, a method according to an aspect of the present disclosure may use a statistical mechanism that uses a calculated mean or expectation and a standard deviation for an actually measured speed. Also, it is possible to use a mechanism of using an actually measured acceleration value. 
     In addition, a method of correcting a position value determined as erroneous according to an aspect of the present disclosure may use a statistical mechanism that is based on a difference calculated on an actually measured position value. 
     The wording “actually measured” in the present disclosure may mean acquiring information on a position, a speed and acceleration directly from a user device that does not use a method of filtering position data and a method of correcting position data according to the present disclosure. 
     It is possible to obtain the actually measured values of a speed and acceleration from moving position data that has the form &lt;latitude, longitude, time&gt; actually measured from a user device. In the following, moving position data having the form &lt;latitude, longitude, time&gt; may be referred to as “tuple” or “position data tuple”. 
     In the present disclosure, it is possible to calculate the statistics of a position and a speed by using data selected by a moving window (or a sliding window) and it is possible to repetitively update these values. In addition, it is possible to perform a filtering operation on actually measured position data by using a controllable parameter. Since an algorithm according to an embodiment of the present disclosure is simple, the present disclosure may also be applied to a mobile user device that has little computing power. 
     In an embodiment of the present disclosure, it is possible to optimize the size of a moving window for the enhancement of performance. Also, a backtracking interpolation method may be used to replace a speed value and/or position value determined as erroneous with an appropriate estimation value. 
     It may be considered that a speed does not sharply increase to a certain level, and this when it is possible to know the mean and standard deviation of a speed at a time interval, it is possible to set a significant interval conforming to e.g., a normal distribution and determine a speed exceeding the significant interval as an error value. 
     A method of processing position information according to an aspect of the present disclosure processes information on a tuple including latitude, longitude, and a timestamp collected from a position information collection device. In this case, the method includes determining that there is an error in tuple [i] in a timestamp [i] when the current speed Vi in the timestamp [i] is larger than a statistic value calculated from past speeds included in a window including a timestamp [i−1]; and replacing information on the tuple [i] with an estimation value when it is determined that there is the error. In this case, the replacing may be performed at the timestamp directly after the timestamp at which the determining is performed. 
     In this case, the statistic may be a moving confidence interval obtained from past speeds. In particular, the moving confidence interval may be a value obtained by adding the mean MA speed  of past speeds to a first value s×MSD speed  proportional to the standard deviation of the past speeds. 
     In this case, the processing method may further include, before calculating the estimation value, determining that there is an error in a speed [i+1] when the speed [i+1] at a timestamp [i+1] is larger than a second statistic calculated from past speeds included in a window including a timestamp [i−n+1] to a timestamp [i]; and, before the estimating, pre-replacing the speed [i+1] with the second statistic when it is determined that there is an error in the speed [i+1]. In this case, the second statistic may be MA speed +s 99.5 ×MSD speed . In this case, s 99.5  means a confidence interval but other parameters meaning a confidence interval having a range different therefrom, such as s 99.9  meaning a confidence interval of 99.9% may also be used. 
     Also, the processing method may further include determining whether there is an error in a tuple [i−] at the timestamp [i−1]; calculating the above-described statistic when there is no error in acceleration in the tuple [i−1] and there is an error in speed in the tuple [i−1] and determining whether a speed value actually measured at the timestamp [i−1] is smaller than the above-described statistic; and replacing a speed, a latitude, and a longitude at the timestamp [i−1] with values actually measured at the time stamp [i−1] when the actually measured speed value is smaller than the above-described statistic. In this case, n above is the size of a window. 
     Advantageous Effects 
     According to the present invention, a position data having an error can be filtered out in real time, a technology can be provided that the position data with error is substituted with a newly corrected position data, not by simply discarding the position data with error. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  explains a speed calibration algorithm according to an embodiment of the present disclosure; 
         FIG. 2  explains a speed calibration method in which a speed value is interpolated by using a least square method according to another embodiment of the present invention; 
         FIGS. 3 to 5  explain a method of filtering a position tuple, a method of estimating a speed using interpolation, and a method of calibrating a speed error according to embodiments of the present disclosure; 
         FIG. 6  explains a speed error detected without correcting a speed according to an embodiment of the present invention; 
         FIG. 7  explains a detected speed error by applying a speed calibration according to an interpolation mechanism according to an embodiment of the present invention; 
         FIG. 8  represents a speed actually measured by using an available position detector; 
         FIGS. 9 and 10  are graphs derived by applying the concepts of a moving significant interval, acceleration error detection and a calibrated speed according to the present disclosure; and 
     
    
    
     MODE FOR CARRYING OUT THE INVENTION 
     Embodiments of the present disclosure are described below with reference to the accompanying drawings. However, the present disclosure is not limited to embodiments described herein and may be implemented in different various forms. 
     It is possible to use a set of tuple (i.e., a moving data tuple) actually measured and collected in the form of &lt;latitude, longitude, time&gt; to represent a user&#39;s moving trajectory (trace). It is possible to obtain a set of data representing user&#39;s mobility by combining an identification parameter capable of identifying each tuple with the tuple. In the present disclosure, it is possible to refer to a tuple obtained at a time t as P t , and latitude and longitude provided by P t  as lat t  and lon t , respectively. 
     By using the contents disclosed in reference [I] cited below, it is possible to calculate a moving distance Di and a speed Vi and acceleration a i  at a time t i  by using two consecutive tuples &lt;lat i−1 , lon i−1 &gt; and &lt;lat i , lon i &gt;. Therefore, the tuple P t  may have a core form such as &lt;t, lat t , lon t , D t , V t , a t &gt; including additional attributes. The attributes t, lat t , lon t , a t  may be referred to as actually measured values in the present disclosure.
         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 represents, through a research, general maximum speeds that may be represented depending on a transportation method. For example, the maximum speed MAX speed  to be applied to an embodiment of the present disclosure may be defined as 250 m/s. Also, the maximum value of acceleration considered to be available in a usual environment is defined and may be indicated by MAX acceleration . When an actually measured speed or acceleration is larger than the MAX speed   MAX acceleration , it may be determined that there is an error. 
     
       
         
           
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                   
                 Transportation Method 
                 Maximum speed (m/sec) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 Ambulation 
                 3.00 
               
               
                   
                 Bicycle 
                 33.33 
               
               
                   
                 Automobile 
                 92.78 
               
               
                   
                 Sports-Car 
                 244.44 
               
               
                   
                 High-Speed Train 
                 159.67 
               
               
                   
                 Air-plain 
                 528.00 
               
               
                   
               
            
           
         
       
     
     Then, it is possible to calculate a moving average of speed actually measured or stored and it is possible to calculate a moving standard deviation of speed. 
     The moving average of speed and the moving standard deviation of speed at any time t may be indicated by MA speed (n) and MSD speed (n), respectively. In this example, n represents the number of past data of {P x : t−n+1≦x&lt;t} that is a set of tuples. In this case, past n data may be obtained by applying a window having a size of “n”. 
     Once a new tuple P t  is obtained, it may be checked whether V t  and at calculated from the tuple P t  may be accepted in a usual environment. When a calculated V t  is out of a normal distribution conforming to the moving average of speed MA speed  (n) and the moving standard deviation of speed MSD speed (n), the tuple P t  may be filtered out (i.e., removed) from a series of traces. A condition for removing the P t  may be given by Equation 1: 
         V   t   &gt;MA   speed ( n )+ s*MSD   speed ( n ).  &lt;Equation 1&gt;
 
     In Equation 1, “s” represents the sensitivity of filtering and is a parameter that may be controlled by a user. 
     If V t  does not satisfy Equation 1, it may be determined that a new tuple P t  has an effective value and it is possible to update the values of MA speed (n)  MSD speed (n) by using the new value. Since the calculation is relatively simple, it may be performed in real time by a low power device such as a mobile user device. 
     Depending on the size n of the above-described window, a filtering characteristic may vary. Thus, it is possible to collect a value actually measured by an available mobile user device in order to perform an experiment for examining an effect depending on the size of a window. A user device may store and output position data whenever sensing a change in position. Alternatively, when the user device is in a static state, it is possible to store and output position data at a user-defined interval such as every three seconds to sixty seconds. It is possible to represent position data acquired by using the method above on a map by using various mechanisms. 
     According to an experiment for the present disclosure, an available user device often provides position data obtained by using three different techniques, together. That is, a position using a cellular base station, a position using a WiFi device for a crowd source and a position using a GPS are provided together. In some cases, the values of three types of position data provided at the same time represent different values. When a plurality of position data is obtained together, there is a high possibility according to an experience that position data having the minimum speed value is effective. Therefore, at a first step of filtering position data, a technique of selecting position data having the shortest moving distance from the previous position among a plurality of position data provided by different techniques at the same time may be selected. 
     In order to determine the optimal value of the size n of a window applied to an algorithm used for filtering position data, various experiments are performed changing the size n. 
     When the size of the window is large, it may be expected that the algorithm may successfully cope with continuous errors in a static state but will fail to respond to them when a speed quickly changes. 
     On the contrary, when the size of the window is small, the algorithm will show a quick response with respect to a sudden change in speed in a moving state considered as including continuous error tuples. However, when there are m continuous errors, it is impossible to filter the errors when m&gt;n, i.e., the size of the window is small. 
     To confirm such a matter, various experiments are performed on a set of data actually measured, changing the size n of the window. In each experiment, n is set to 5, 10, 25, 50 or 100 and the moving average of speed and the moving standard deviation of speed are calculated for each case. 
     As the size of the window increases, the effect of an error is maintained for a longer time when data having a big error in an actually measured speed value is input. As a result, under filtering on erroneous data occurs. When the size of the window is 100 or 50, it is confirmed that there is a tailing effect. 
     On the contrary, when the size of the window is small, a reaction is performed quickly and sensitively on a change in speed, especially at the step that the speed starts changing. However, there is a tendency of over-filtering and removal of accurate data. When the size of the window is small such as 5 or 10, there are cases where two or more tuples appearing to be accurate speed data are removed. 
     Through the above matter, it may be seen that there is a need to introduce a throttling mechanism for a moving window in order to avoid a tailing effect depending on the size of the window. 
     A pre-experiment for examining an error in actually measured position data is described below. 
     In the pre-experiment, position data is collected for several hours while position detectors are fixed indoors and outdoors. A first position detector is an available Garmin GPSMAP62s and only used for GPS data collection. A second position detector is an available Samsung Galaxy Tab and used for obtaining position detection data from a 3G base station (3GBS) connected to the device. It is estimated that position data obtained by using the 3GBS has more errors and that position data obtained from the GPS and the 3GBS all has errors. Especially, it is estimated that there is also a position detection error indoors. The result of the pre-experiment is represented in Table 2. Table 2 represents errors that are represented when actually measuring position data, and is m in unit. 
     
       
         
           
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 Building 
                 3G Base Station 
                 GPS 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 Inside 
                 n(Data Point) 
                 893 
                 n(Data Point) 
                 2186 
               
               
                   
                 n(Error Point) 
                 434 
                 n(Error Point) 
                  939 
               
               
                   
                 Error Rate 
                 48.6% 
                 Error Rate 
                 43.0% 
               
               
                   
                 E[Error Dist] 
                 52.5530 m 
                 E[Error Dist] 
                  43.5506 m 
               
               
                   
                 Max(Error Dist) 
                 156.7578 m  
                 Max(Error Dist) 
                 10769.72 m 
               
               
                   
                 O ErrorDist   
                 32.6859 m 
                 O ErrorDist   
                 370.6034 m 
               
               
                 Outside 
                 n(Data Point) 
                 331 
                 n(Data Point) 
                 1690 
               
               
                   
                 n(Error Point) 
                 122 
                 n(Error Point) 
                  208 
               
               
                   
                 Error Rate 
                 36.9% 
                 Error Rate 
                 12.3% 
               
               
                   
                 E[Error Dist] 
                 52.6618 m 
                 E[Error Dist] 
                  4.4498 m 
               
               
                   
                 Max(Error Dist) 
                 206.3526 m  
                 Max(Error Dist) 
                  51.7789 m  
               
               
                   
                 O ErrorDist   
                 23.5953 m 
                 O ErrorDist   
                  7.1696 m 
               
               
                   
               
            
           
         
       
     
     Error distances are calculated from position data and it is possible to calculate the variance and mean of the error distances. As estimated, the 3GBS represents a larger error rate and a larger error, the maximum its error size is also larger and the standard deviation of its error size is also larger. Garmin GPSMAP62s should calculate a user&#39;s position based on past speeds even if a GPS signal is lost, and thus a very large error is also represented indoors. Thus, it may be considered that indoor GPS data is not meaningful. Outdoor GPS data represents accuracy sufficient to obtain accurate position data and its maximum error size also is within a reasonable range of 52 m. 
     A filtering algorithm according to an embodiment of the present disclosure is described below. [Algorithm 1] in Table 3 is used to determine whether there is an error in actually measured position data and filter erroneous position data. When new position data P i+1  is acquired, [Algorithm 1] may determine whether to filter P i−1 . 
     
       
         
           
               
             
               
                 TABLE 3 
               
               
                   
               
               
                 Algorithm 1: Position Error Detection by Moving Window 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: P c  // At least one initial tuple is required 
               
               
                 Require: window size n 
               
               
                 Require: user sensitivity level s 
               
               
                 Ensure: Check validness of new position tuple 
               
               
                 Ensure: Calibrated series of tuple (P i  : t≧i&gt;0 ) for t inputs 
               
               
                 Require: i=0 
               
               
                 1: repeat 
               
            
           
           
               
               
            
               
                 2: 
                 Get P i+1  // Acquisition of new tuple, if exist 
               
               
                 3: 
                 Construct MA speed (n) with (P s  : max(i−n+1, 0)≦x≦i) 
               
               
                 4: 
                 Construct MSD speed (n) with (P x  : max(i−n+1, 0)≦x≦i) 
               
               
                 5: 
                 Set MA speed  = MA speed (n) 
               
               
                 6: 
                 Set MSD speed  = MSD speed (n) // Moving Window Construction 
               
               
                 7: 
                 Set V i+1  = (dist(P i+1 ,P 1 ))/(t i+1 −t 1 ) 
               
               
                 8: 
                 If ((V i+1  &gt; MA speed  + s × MSD speed ) or (a i+1 ≧MAX acceleration )) 
               
               
                   
                 and (V i+1 &gt; MIN speed ) then 
               
               
                 9: 
                  Mark P i+1  as filtered. // Filtering 
               
               
                 10: 
                 end if 
               
               
                 11: 
                 if (V i+1  ≧ MA speed  + s 99.5  × MSD speed ) and (V i+1  &gt; MIN speed ) then 
               
               
                 12: 
                  Set V i+1  = MA speed  + s 99.5  × MSD speed  // Calibration of Speed 
               
               
                 13: 
                 end if 
               
               
                 14: 
                 if a i+1  ≧ MAX acceleration  then 
               
               
                 15: 
                  Mark P i+1  as filtered 
               
               
                 16: 
                  Set V i+1  = MA speed   
               
               
                 17: 
                  Set a i+1  = MAX acceleration  // Restriction by Maximum Acceleration 
               
               
                 18: 
                 end if 
               
               
                 19: 
                 Set i = i + 1 
               
            
           
           
               
            
               
                 20: until Exist no more input of positioning tuple 
               
               
                   
               
            
           
         
       
     
     The functions of each part of [Algorithm 1] in Table 3 are described below.
         Third to Sixth Lines of [Algorithm 1]: When there are less than n tuples, it is impossible to provide data sufficient to fill a window having a size n. Instead, it is possible to configure an incomplete window by using little information.   Eighth to Tenth Lines of [Algorithm 1]: Acceleration and a speed may be used as parameters for filtering and used by using different techniques but may all be considered as throttling parameters. Tuples that are out of a range of a so-called moving significant interval expressed by MA speed +s*MSD speed  that represents velocity V i+1  or have too high acceleration are filtered. In this example, s represents the significant level of a normal distribution.   Eleventh to Thirteenth Lines of [Algorithm 1]: When the velocity of a tuple is too high, it affects values MA speed  and MSD speed  and thus a filtering error such as an expansion of a confidence interval occurs. As a result, tuples that are needed to be filtered out are filtered in. As such, when the velocity of a tuple is too high, it is possible to modify a velocity value by using MA speed (n)+s 99.5 *MSD speed =MA speed (n)+2.57*MSD speed , in order to include a quick change in speed as possible and avoid the expansion error of a confidence interval.   s 99.5  on Eleventh to Thirteenth Lines of [Algorithm 1]: s 99.5 =2.57 represents a confidence interval of 99.5% in a normal distribution. This is a throttling parameter that reduces the effect of an erroneous speed on a moving window.   Twelfth Line of [Algorithm 1]: Even if any tuple is needed to be filtered out by Equation 1, it is possible to include the speed of this tuple through restriction or calibration to be within a confidence interval of 99.5% in a normal distribution in order to reflect the speed of this tuple to a moving window. The reason is so that a moving window is updated including a quick speed value in order to cope with a quick change in speed. That is, an error-less tuple may also be filtered out if having a sharp change in speed. In such a case, even if the tuple is filtered, a moving window may reflect a maximum change in speed that may be allowed for the tuple.   MIN velocity  on Twelfth Line of [Algorithm 1]: Since a human being may walk at 2.77 m/s (10 Km/h) or lower speed and is within a GPS error range, 2.77 m/s (10 Km/h) or lower speed is not filtered out.   MAX acceleration  on Fourteenth Line of [Algorithm 1]: Tuples having impractical acceleration are filtered out.   Twelfth to Sixteenth Lines of [Algorithm 1]: Tuples having excessive acceleration are filtered out, the acceleration values of the tuples are calibrated to MAX acceleration , their speed values are calibrated to MA speed (n) in order to nullify the effect of impractical speed values.       

     Since a vehicle may always stop quickly with great negative acceleration, tuples having negative acceleration values are considered as being effective without errors. On the contrary, tuples having positive acceleration values greater than MAX acceleration  are considered as being erroneous. 
     Two variables n and s in [Algorithm] may be set by a user. The variable n is the number of tuples in a window, i.e., a window size, and the variable s is the sensitivity level of filtering (i.e., a significant level of a normal distribution). The user sensitivity level s may be relatively simply determined. It is possible to obtain s having an appropriate confidence interval from the characteristic of a normal distribution. Since only the positive area of a normal distribution is used for filtering, s may be set to 1.64 for a 95% confidence interval, and s may be set to 2.33 for a 99% confidence interval. Users may determine s according to their purposes. For example, the sensitivity level s may be selected as follows. Table 2 shows a normal error rate for position data collection when a device does not move. In the case of GPS, 12.3% of position data has errors, and in the case of a 3GBS cellular position detection system, 36.75% of position data has errors. Thus, in this case, s may be set to 1.16 for GPS data and s may be set to 0.34 for cellular position detection data. 
     As described above, when the size of a window is large, a trailing effect occurs and thus it is possible to decrease the size of the window in order to avoid the effect. An inaccurate speed value may be calibrated by [Algorithm 1], an abnormal acceleration value may be limited, and a speed value may be replaced with an average speed calculated by a moving window. Several experiments are performed in order to examine the effect of a window size depending on such a calibration mechanism. In a first experiment, a window size n is selected as 5, 10, 25, 50 and 100, the sensitivity level s is selected as 1.16, and filtering is performed on the assumption that 88% of actually measured position data is accurate data. When the window size is small, a trailing effect is limited but a result representing a more flexible reaction according to a change in speed is obtained. In the first experiment, when the size of the window is 5 or 10, a good result is obtained. 
     In a second experiment, the effect of continuous errors is considered. The continuous errors may affect a moving average and a moving standard deviation used in the present algorithm. There are up to four continuous errors in a set of position detection data used in an actual experiment. Thus, in the second experiment, it is concluded that n=5 is not sufficient for correcting consecutive errors, and that the consecutive errors can be properly corrected when the window size n is set equal to 10 (n=10), and that, with window size n=10, tailing effect which occurs with a window size n larger than 10 can be reduced. Thus, in the experiment, the window size is eventually determined as 10. When experiencing more continuous errors, it is possible to select a window size suitable therefor or dynamically increase the window size. 
     As a result of various experiments using [Algorithm 1] according to the present invention, it is possible to obtain two conclusions. Firstly, when the window size and the sensitivity level are appropriately selected, it is possible to obtain an appropriate filtering result. Secondly, according to many combinations of the window size and the sensitivity level, it is possible to perform filtering on all sets of position detection data. 
     Table 4 represents the percentage of filtered-out tuples for combinations of parameters. A user of an algorithm according to an embodiment of the present invention may select a window size and a sensitivity level according to Table 4 according to his or her environment. In [Algorithm 1], various parameters of the algorithm such as a window size, a sensitivity level, a maximum speed and maximum acceleration may be defined by a user. The user may also change the constants of the algorithm such as MAX acceleration , a maximum sensitivity level s 99.5 , and minimum threshold value of speed for filtering MIN velocity . 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE 4 
               
               
                   
               
               
                 Size of Sliding Window 
                 s = 0.34 
                 s = 1.16 
                 s = 1.64 
                 s = 2.33 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 5 
                 42.20 
                 29.07 
                 24.06 
                 19.31 
               
               
                 10 
                 38.67 
                 24.10 
                 18.81 
                 14.31 
               
               
                 25 
                 37.37 
                 21.43 
                 16.07 
                 11.85 
               
               
                 50 
                 37.71 
                 20.54 
                 15.23 
                 11.07 
               
               
                 100 
                 37.05 
                 20.03 
                 14.90 
                 10.65 
               
               
                   
               
            
           
         
       
     
     [Algorithm 1] may vary in consideration of the flowing matters. 
     Firstly, it is possible to define the size of a window as a time interval including the window instead of defining the window size as the number of tuples in a window. When considering that a speed is a function of a time, it may be seen that a varied technique is effective and accurate when regularly collecting position data. 
     Secondly, it is possible to dynamically calibrate the window size. In another embodiment that is a variation to [Algorithm 1], it is possible to dynamically increase or decrease the window size according to the number of continuous errors. Once it is found that the number of continuous errors is large, it is possible to increase the window size in order to minimize an effect on a moving average and a moving standard deviation by continuous errors. When the number of continuous errors is small, it is possible to show an appropriate reaction to a rapid change in speed and to decrease calculation for filtering by decreasing the window size. 
     Thirdly, it is possible to change [Algorithm 1] to a pseudo real-time algorithm, not a real-time algorithm. For the window size n, it is possible to filter a 
     
       
         
           
             
               [ 
               
                 n 
                 2 
               
               ] 
             
             th 
           
         
       
     
     tuple that is approximately in the middle of a window instead of filtering a (n+1)th tuple. This method may decrease under filtering and over filtering tendencies even though it may not be implemented completely in real time. 
     Fourthly, it is possible to an interpolation mechanism to [Algorithm 1]. [Algorithm 2] presented in Table 5 below is obtained by adding an interpolation step to [Algorithm 1] (see lines 18 to 21 of [Algorithm 2]). When a new tuple (index i+1) is acquired, it is possible to replace the speed of the last tuple with an interpolated value when it is confirmed that the last tuple (index i) in the currently existing window is filtered out. When such interpolation is used, it is possible to more precisely provide a moving window introduced for the filtering of a tuple (see lines 18 to 21 of [Algorithm 2]). That is, by the last part of [Algorithm 2], it is possible to interpolate the last tuple marked as filtered out in a window whenever a new tuple is acquired. In another variation for configuring a moving window for more precise approximation, a 
     
       
         
           
             
               [ 
               
                 n 
                 2 
               
               ] 
             
             th 
           
         
       
     
     tuple approximately in the middle of a window is interpolated by using n tuples in the window. For more precise estimation, more precise interpolation may be enabled by interpolating the middle tuple in a window by using an asymptotic curve estimated from n tuples. However, since computational overhead may occur due to that, it may be difficult to apply it to a mobile user device. 
     
       
         
           
               
             
               
                 TABLE 5 
               
               
                   
               
               
                 Algorithm 2 Estimation of Speed for Stabilization of Moving Window 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 Require: P c  // At least one initial tuple is required 
                   
               
               
                 Require: window size n 
                   
               
               
                 Require: user sensitivity level s 
                   
               
               
                 Ensure: Check validness of new position tuple 
                   
               
               
                 Ensure: Calibrated series of tuple (P i  : t ≧ i &gt; 0 ) for t inputs 
                   
               
               
                 Require: i=0 
                   
               
            
           
           
               
            
               
                 1: repeat 
               
            
           
           
               
               
            
               
                 2: 
                 Get P i+1  // Acquisition of new tuple, if exist 
               
               
                 3: 
                 Construct MA speed (n) with (P x  : max(i−n+1, 0) ≦ × ≦ i) 
               
               
                 4: 
                 Construct MSD speed (n) with (P x  : max(i−n+1, 0) ≦ × ≦ i) 
               
               
                 5: 
                 Set MA speed  = MA speed (n) 
               
               
                 6: 
                 Set MSD speed  = MSD speed (n) // Moving Window Construction 
               
               
                 7: 
                  if ((V i+1 &gt;MA speed +s×MSD speed )  or  (a i+1 ≧MAX acceleration )) and 
               
            
           
           
               
            
               
                 (V i+1 &gt;MIN speed ) then 
               
            
           
           
               
               
            
               
                 8: 
                  Mark P i+1  as filtered, // Filtering 
               
               
                 9: 
                 end if 
               
               
                 10: 
                 if (V i−1 ≧MA speed +s 99.5 × MSD speed ) AND (V i+1 &gt;MIN speed ) than 
               
               
                 11: 
                   Set V i+1  = MA speed  + s 99.5  × MSD speed  // Calibration of Speed 
               
               
                 12: 
                 end if 
               
               
                 13: 
                 if a i+1  ≧ MAX acceleration  then 
               
               
                 14: 
                  Mark P i+1  as filtered 
               
               
                 15: 
                   Set V i+1  = MA speed   
               
               
                 16: 
                   Set a i+1  = MAX acceleration   //  Restriction by Maximum 
               
            
           
           
               
            
               
                 Acceleration 
               
            
           
           
               
               
            
               
                 17: 
                  end if 
               
               
                 18: 
                  if (F i  marked as filtered) then 
               
               
                 19: 
                  Set V i  ((V i+1  − V i−1 ) × (t i  − t i−1 ))/(t i+1  − t i−1 ) +V i−1   
               
               
                 20: 
                  Mark P i  as interpolated // Linear interpolation 
               
               
                 21: 
                  end if 
               
               
                 22: 
                  Set i = i + 1 
               
            
           
           
               
            
               
                 23: until Exist no more input of positioning tuple 
               
               
                   
               
            
           
         
       
     
       FIG. 1  explains a speed correction algorithm according to an embodiment of the present invention. 
     The horizontal axis of  FIG. 1  represents the indexes (i.e., timestamps) of tuples continuously obtained and the vertical axis of  FIG. 1  is the speed of each tuple stored in a memory.  FIG. 1  illustrates that the size n of a moving window is 10. It is possible to calculate “MA speed ” and “MA speed +s 99.5 ×MSD speed ” from 10 speeds present in a moving window and examples of the values are shown in  FIG. 1 . In FIG.  1 , it is assumed that the acceleration at an index [i+1] is higher than MAX acceleration . Thus, the speed V i+1  at the index [i+1] is corrected to MA speed  (see line 15 of [Algorithm 2]). In  FIG. 1 , it is assumed that a moving data tuple P i  for an index [i] is marked as filtered already out according to [Algorithm 2] (see line 18 of [Algorithm 2]). The filtering out of any tuple means that a determination that there is an error where the tuple has is made, but a speed or acceleration calculated from the tuple may still be stored. Thus, according to line 19 of [Algorithm 2], the speed V i  of a moving data tuple P i  is replaced with a value linearly interpolated by using the speed V −1  of a moving data tuple and speed of a moving data tuple P i+1 . As such, according to [Algorithm 2], the speed of a newly acquired tuple may be first calibrated by lines 10 to 17 of [Algorithm 2], and then a calibrated speed may be further calibrated by lines 18 to 21 of [Algorithm 2] when another new tuple is acquired. It may be understood that both the first calibration and the further calibration as described above may be performed on the speed of any tuple, or only one of both calibrations or no calibrations may be performed thereon. 
     A value obtained by interpolating and calibrating the speed V i  of the above-described tuple P i  is usually smaller than a value “MA speed +s 99.5 ×MSD speed ” calibrated by the line 11 of [Algorithm 2] but may also be larger depending on a calibrated value or moving significance interval at the next timestamp. 
     Processing on a newly acquired moving data tuple P i+1  and the latest moving data tuple P i  present in a moving window are performed through [Algorithm 2]. Alternatively, in another embodiment of the present disclosure, processing on a moving data tuple P m  at any timestamp in a moving window may be performed. To this end, lines 18 to 21 of [Algorithm 2] may vary as represented in Table 6. 
     
       
         
           
               
               
               
             
               
                 TABLE 6 
               
               
                   
               
             
            
               
                 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 
               
               
                   
               
               
                 Where m = i − k and k is a parameter that may be throttled by a user. 
               
            
           
         
       
     
       FIG. 2  explains a speed correction method in which a speed value is interpolated by using a least square method according to another embodiment of the present invention. 
       FIG. 2  represents a result of using an interpolation method varied from an interpolation method by lines 18 to 21 of [Algorithm 2].  FIG. 2  uses a non-linear interpolation method using a plurality of data in a moving window. For example, it is possible to correct a moving data tuple having an index [i−4] by using a value corresponding to an asymptotic curve approximated by using a least square method and a plurality of data included in a moving window. 
       FIGS. 3 to 5  explain a method of filtering a position tuple, a method of estimating a speed using interpolation, and a method of calibrating a speed error according to other embodiments of the present disclosure. 
     The horizontal axes of  FIGS. 3 to 5  represent the indexes of a timestamp and the vertical axes of  FIGS. 3 to 5  represent a speed. Reference numeral  100  represents a speed actually measured at a corresponding timestamp and a reference numeral  101  represents a speed actually measured from a filtered-out tuple by using one of algorithms disclosed in the present disclosure.  FIGS. 3 to 5  represent an example where a window size is 10. Reference numeral  103  represents the average value of speed in a window and reference numeral  102  represents the value  102  of the above-described moving significance interval. The position tuple of reference numeral  101  represented in  FIG. 3  is filtered out because its speed is higher than the value  102  of the moving significance interval. 
     The reference numeral  101  (index i) of  FIG. 4  represents a speed actually measured from a position tuple filtered-out according to the algorithm of the present disclosure. The reference numeral  200  of  FIG. 4  represents an estimated value of a speed provided by linearly interpolating the speed value of an index i by the speed values of an index i−1 and an index i+1 that precede and follow it. 
       FIG. 5  represents a case where the tuples of the index i and the index i+1 are all filtered-out. In this case, since the actually measured speed of the index i (see reference numeral  101  of the index i) is higher than the value of a moving significance interval, it is already calibrated to a certain size (see reference numeral  300  of the index i). Next, since the actually measured speed of the index i+1 (see reference numeral  101  of the index i+1) is also higher than the value of a moving significance interval, it is calibrated to a certain size (see reference numeral  300  of the index i+1). Next, since the tuple of the index i is filtered out, the speed of the index i is interpolated by using the speeds of the index i+1 and the index i−1. In other words, in an embodiment of the present disclosure, the calibration of a speed may also be used as a pre-step for accurately estimating the speed. 
     It is possible to estimate the speed of a filtered-out one of actually measured tuples by using [Algorithm 2] but the position value of the filtered-out tuple is in a simply removed state. When using [Algorithm 3] represented in Tables 7 and 8 below, it is possible to estimate the position value of the filtered-out tuple. The speed estimation of [Algorithm 2] needs to consider only a positive (+) speed value, but since latitude and longitude have directionality, negative (−) differences at latitude and longitude may not be ignored for position estimation added to [Algorithm 3]. 
     
       
         
           
               
             
               
                 TABLE 7 
               
               
                   
               
               
                 Algorithm 3: Position Estimation Using Moving Window (1/2) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: P c  // At least one initial tuple is required 
               
               
                 Require: window size n 
               
               
                 Require: user sensitivity level s 
               
               
                 Require: error tolerance of distance ETa 
               
               
                 Ensure: Check validness of new position tuple 
               
               
                 Ensure: Calibrated series of tuple (P i  : t ≧ i &gt; 0 ) for t inputs 
               
               
                 Require: i=0 // V i  is speed calculated from: P i−1  to P i   
               
               
                 1: repeat 
               
            
           
           
               
               
            
               
                 2: 
                 Get P i+1   // Acquisition of new tuple, if exist 
               
               
                 3: 
                 Set V i+1  = dist(P i+1 , P i )/t i+1  − t i ) 
               
            
           
           
               
            
               
                  // dist( ): distance between two geographic coordinate system points 
               
            
           
           
               
               
            
               
                 4: 
                 Set MiN speed  = ETa/(t t−1  − t i ) 
               
               
                 5: 
                 Construct MA speed (n) with (P x  : max(i−n+1, 0) ≦ × ≦i) 
               
               
                 6: 
                 Construct MSD speed (n) with (P x  : max(i−n+1, 0) ≦ × ≦i) 
               
               
                 7: 
                 Set MA speed  = MA speed (n) 
               
               
                 8: 
                 Set MSD speed  = (MSD speed (n) &gt; MIN speed  ? MSD speed (n) : MIN speed   
               
               
                   
                  // Allow minimum room for moving significant interval 
               
               
                 9: 
                 Set Vlat i+1  = ||lat i+1 , lat i ||/(t i+1  − t i ) 
               
               
                 10: 
                 Construct MA Vlatitude (n) with (P x  : max(1−n+1; 0) ≦ × ≦ i) 
               
               
                 11: 
                 Set MA Vlatitude = MA Vlatitude (n) 
               
               
                 12: 
                 Set Vion i+1  = ||lon i+1 , lon i ||/(t i+1  − t i ) 
               
               
                 13: 
                 Construct MA Vlongitude (n) with (P x  : max(1−n+1; 0) ≦ × ≦ i) 
               
               
                 14: 
                 Set MA Vlongitude  = MA Vlongitude (n) 
               
               
                 15: 
                 if ((V i−1  &gt; MA speed  + s × MSD speed ) or (a i+1 ≧MAX acceleration )) 
               
               
                   
                   and (V i+1  &gt; MIN speed ) then 
               
               
                 16: 
                  Mark P i+t  as filtered, // Filtering 
               
               
                 17: 
                 end if 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 8 
               
               
                   
               
               
                 Algorithm 3 - continued (2/2) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 18: 
                 if (V i+1  ≧ MA speed  + s 89.5  × MSD speed ) and (V i+1  &gt; MIN speed ) then 
               
               
                 19: 
                  Set V i+1  = MA speed  + s 99.5  × MSD speed  // Calibration of Speed 
               
               
                 20: 
                 end if 
               
               
                 21: 
                 if a i+1  ≧ MAX acceleration  then 
               
               
                 22: 
                  Mark P i+1  as filtered 
               
               
                 23: 
                  Set V i+1  = MA speed   
               
               
                 24: 
                  Set a i+1  = MAX acceleration   
               
               
                 25: 
                  Set lat i+1  = lat i  + sign(lat i+1 −lat i ) × MA Vlatitude  × (t i+1 −t i−1 ) 
               
               
                 26: 
                  Set lon i+1  = lon i  + sign(lon i+1 −lon i ) × MA Vlongitude  × (t i+1 −t i−1 ) 
               
               
                   
                  // Restriction by Maximum Acceleration 
               
               
                 27: 
                 end if 
               
               
                 28: 
                 if (P i  marked as filtered) then 
               
               
                 29: 
                  Set V i  = ((V i+1  − V i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + V i−1   
               
               
                 30: 
                  Mark P i  as interpolated // Linear Interpolation of speed 
               
               
                 31: 
                  Set lat i  = ((lat i+1  − lat i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + lat i−1   
               
               
                 32: 
                  Set lon i  = ((lon i+1  − lon i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + lon i−1   
               
               
                   
                  // Estimation of Position by interpolation 
               
               
                 33: 
                 end if 
               
               
                 34: 
                 Set i = i + 1 
               
               
                 35: 
                 until Exist no more input of positioning tuple 
               
               
                   
               
            
           
         
       
     
     A position calibrating method according to an embodiment of the present invention is described by using [Algorithm 3] above. 
     [Algorithm 3] introduces a parameter ET D  for allowing a usual distance error (see line 4 of [Algorithm 3]). The parameter ET D  may be set to e.g., 15 m for a GPS system in which SA is activated, from the circular error probable (CEP) concept a usual positioning system. It is also possible to change the value of the parameter ET D  depending on the accuracy of the positioning system. The minimum speed and the minimum difference of latitude and longitude may be determined by the parameter ET D , a moving standard deviation may be affected, and as a result, a moving significance interval may have a value other than zero. That is, by using the parameter ET D , it is possible to introduce the CEP concept of the positioning system into [Algorithm 3] according to an embodiment of the present disclosure, and it is possible to avoid overfiltering tuples due to a small feasible speed error within the accuracy of the positioning system. 
     According to [Algorithm 3], it is possible to introduce a position estimation process into a filtered tuple, similar to the speed estimation process of [Algorithm 2]. The main difference of the position estimation process included in [Algorithm 3] is in the directionalities of latitude and longitude. That is, a speed value needs to consider only a positive value but in order to estimate a position, the negative difference of latitude and longitude may not be ignored. [Algorithm 3] represents the whole process for position estimation and corresponds to the whole process for the speed estimation of [Algorithm 2]. 
     The parameters V lat  and V lon  refer to differences in latitude and longitude, respectively. [Algorithm 3] calculates the moving averages of the parameters V lat  and V lon . When one tuple is filtered by an excessive speed, it represents that a difference in position is excessive. Once there is such a situation, there is a need to estimate an accurate position. When acceleration error occurs, position data is corrected to the moving average MA of difference, similar to speed estimation (see lines 25 and 26 of [Algorithm 3]). Lastly, similar to speed estimation, interpolation is performed on latitude and longitude at the end of a moving window (see lines 31 and 32 of [Algorithm 3]). In addition, the directionality of a difference is also preserved (see lines 25, 26, 31 and 32 of [Algorithm 3]). 
     In line 4 of [Algorithm 3], when the time interval of a position tuple increases, there are cases where the value MIN speed  by the parameter ET D  becomes very small. In this case, in order to ensure the certain lower bound of the value MIN speed , it is possible to change codes in line 4 of [Algorithm 3] to “Set MIN speed =(ET D /(t i+1 −t i )&gt;MIN SPEED )?ET D /(t i+1 −t i ): MINSPEED”. In this example, MINSPEED is the minimum speed that is defined by a user of the present disclosure. 
       FIG. 6  explains a speed error obtained from actually measured data, and  FIG. 7  explains a speed error detected by applying a speed correction according to an interpolation mechanism according to an embodiment of the present disclosure. Each figure includes information on an origin speed, acceleration, a moving significant interval, a calibrated speed, an estimated speed, and a detected acceleration error. The acceleration error is shown in an inverted triangular shape. However,  FIG. 6  does not include information on an interpolated speed. An empty rectangle represents a speed limited according to a calibration mechanism according to an embodiment of the present disclosure, and a dark rectangle represents an estimated speed by an interpolation mechanism. The speed on the y-axis has an m/s unit and the x-axis represents the time of the day. Even though an error that an origin speed is placed outside a moving significant interval near 13:33:06 is found, an algorithm according to an embodiment of the present invention properly estimates a feasible speed value. An apparent error by an acceleration limit occurs at the time of 13:32:59 on Dec. 18, 2012, but a speed error is limited to within an appropriate range by the calibration technique of the present disclosure and then, a speed is corrected by a speed estimation technique. Rather than a method of calibrating an error speed, a method of estimating a speed by an interpolation technique may further decrease an effect applied to a moving window. Thus, a moving significant interval following interpolation in  FIG. 7  represents a difference, which is because the statistical value of a moving window varies by an interpolated speed value. The difference at the time of 13:33:04 is considerably great. 
     Tables 9 to 11 explain a fourth algorithm for position estimation according to another embodiment of the present disclosure. 
     
       
         
           
               
             
               
                 TABLE 9 
               
               
                   
               
               
                 Algorithm 4: Moving Window Based Position Estimation Method Using 
               
               
                 Backtracking (1/3) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: P c  // At least one initial tuple is required 
               
               
                 Require: IWS, MWS, // IWS ≦ MWS 
               
               
                 Require: window size n = IWS 
               
               
                 Require: user sensitivity level s 
               
               
                 Require: error tolerance of distance ET D   
               
            
           
           
               
               
            
               
                 1: 
                 i=0 
               
               
                 2: 
                 NCE=0 
               
               
                 3: 
                 repeat 
               
               
                 4: 
                  Get P i+1  // Acquisition of new tuple, if exist 
               
               
                 5: 
                  Set V i+1, original  = V i+1  = dist(P i+1 , P 1 )/(t i+1  − t i ) 
               
               
                   
                   // dist( ): distance between two geographic coordinate system 
               
               
                   
                   points. 
               
               
                 6: 
                  Set MIN speed  = (ET D /(t i+1  − t i )&gt;MINSPEED) ? ED D /(t i+1 −t i ) : 
               
               
                   
                  MINSPEED 
               
               
                 7: 
                  Construct MA speed (n) with (P i  : max(i−n+1, 0) ≦ x ≦ A 
               
               
                 8: 
                  Construct MSD speed (n) with (P i  : max(i−n+1, 0) ≦ x ≦ A 
               
               
                 9: 
                  Set MA speed  = MA speed (n) 
               
               
                 10: 
                  Set MSD speed  = (MSD speed (n) &gt; MIN speed ) ? MSD speed (n) : 
               
               
                   
                  MIN speed   
               
               
                   
                   // Allow minimum room for moving significant interval 
               
               
                 11: 
                  Set Vlat i+1  = ||lat i+1 , lat i ||/(t i+1  − t i ) 
               
               
                 12: 
                  Construct MA Vlatitude (n) with (P x  : max(i−n+1, 0) ≦ x ≦ i) 
               
               
                 13: 
                  Set MA Vlatitude  = MA Vlatitude (n) 
               
               
                 14: 
                  Set Vlon i+1  = ||lon i+1 , lon i ||/(t i+1  − t i ) 
               
               
                 15: 
                  Construct MA Vlongitude (n) with (P x  : max(i−n+1, 0) ≦ x ≦ i) 
               
               
                 16: 
                  Set MA Vlongitude = MA Vlongitude (n) 
               
               
                 17: 
                  Set lat i+1, original =lat i+1   
               
               
                 18: 
                  Set lon i+1, original =lon i+1   
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 10 
               
               
                   
               
               
                 Algorithm 4 - Continued (2/3) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                 19: 
                 if (P i+1  marked as filtered or interpolated) 
               
               
                   
                  and ((P i+1 marked as accel..filtered) 
               
               
                   
                  and ( V i 1, original  ≦ MA speed  + s × MSD speed ) then 
               
               
                 20: 
                  V i+1  = V i+1, original   
               
               
                 21: 
                  lat i+1 =lat i+1, original   
               
               
                 22: 
                  lon i+1 =lon i+1, origina   
               
            
           
           
               
            
               
                  // Backtracking: Look back one step and Resotre with orginal 
               
            
           
           
               
               
            
               
                 values 
                   
               
            
           
           
               
               
            
               
                 23: 
                  Set NCE = 0 
               
               
                 24: 
                  n = (n−1 ≦ TWS) ? IWS : n //Window Size Adjustment- 
               
               
                   
                  Decrease 
               
               
                 25: 
                 end if 
               
               
                 26: 
                 if ((V i+1  &gt; MA speed  + s × MSD speed ) or (a i−1  ≧ MAX acceleration )) 
               
               
                   
                   and (V i+1  &gt; MIN speed ) then 
               
               
                 27: 
                  Mark P i+1  as filtered, // Filtering 
               
               
                 28: 
                  NCE ++ 
               
               
                 29: 
                  IF(n+ 1 &gt; MWS) ? MWS : n++ //Window Size Adjustment-Increase 
               
               
                 30: 
                 else 
               
               
                 31: 
                  Set NCE = 0 
               
               
                 32: 
                  n=(n−1 &gt; IWS) ? IWS : n − −//Window Size Adjustment-Decrease 
               
               
                 33: 
                 end if 
               
               
                 34: 
                 if (V i+1  ≧ MA speed  + s 99.5  × MSD speed ) and (V i+1  &gt; MIN speed ) then 
               
               
                 35: 
                  Set V i+1  = MA speed  + s 99.5  × MSD speed  // Calibration of Speed 
               
               
                 36: 
                 end if 
               
               
                   
               
            
           
         
       
     
     
       
         
           
               
             
               
                 TABLE 11 
               
               
                   
               
               
                 Algorithm 4 - Continued (3/3) 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 37: 
                 if a i+1  ≧ MAX acceleration  then 
               
               
                   
                 38: 
                  Mark P i+1  as filtered 
               
               
                   
                 39: 
                  Set V i+1  = MA speed   
               
               
                   
                 40: 
                  Set a i+1  = MAX acceleration   
               
               
                   
                 41: 
                  Set lat i+1  = lat i  + sign(lat i+1 −lat i ) × MA Vlatitude × (t i+1 −t i−1 ) 
               
               
                   
                 42: 
                  Set lon i+1  = lon i  + sign(lon i+1 −lon i ) × MA Vlongitude  × (t i+1 −t i−1 ) 
               
               
                   
                   
                   // Restriction by Maximum Acceleration 
               
               
                   
                 43: 
                 end if 
               
               
                   
                 44: 
                 if (P i  marked as filtered) then 
               
               
                   
                 45: 
                  Set V i  = ((V i+1  − V i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + V i−1   
               
               
                   
                 46: 
                  Mark P i  as interpolated // Linear Interpolation of speed 
               
               
                   
                 47: 
                  Set lat i  = ((lat i+1  − lat i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + lat i−1   
               
               
                   
                 48: 
                  Set lon i  = ((lon i+1  − lon i−1 ) × (t i  − t i−1 )) / (t i+1  − t i−1 ) + lon i−1   
               
               
                   
                   
                   // Estimation of Position by interpolation 
               
               
                   
                 49: 
                 end if 
               
               
                   
                 50: 
                 Set i = i + 1 
               
            
           
           
               
               
            
               
                   
                 51: until Exist no more input of positioning tuple 
               
               
                   
               
            
           
         
       
     
     [Algorithm 4] is the same as [Algorithm 3] excluding lines 2, 5, 6, 17 to 25, 28 to 32 and 38 of [Algorithm 4]. In the following, lines 2, 5, 6, 17 to 25, 28 to 32 and 38 of [Algorithm 4] are described.
         Line 2 of [Algorithm 4]: In order to count the number of continuous errors, a parameter NCE is introduced and its value is initialized to zero.   Line 5 of [Algorithm 4]: V may be changed to another value by another part of [Algorithm 4]. For example, V may be replaced with another calibrated value or estimated value in lines 35, 39 and 45 of [Algorithm 4]. However, in line 20 of [Algorithm 4], the estimated value provided through a replacement may be replaced back with an original value (calculated from an actually measured value and then stored), and in order to perform such an operation, the original value of V is separately stored in line 5.   Line 6 of [Algorithm 4]: MIN speed  for the minimum speed is set to a smaller one of ET D /(t i+1 −t i ) and a predetermined minimum value MINSPEED. That is, the minimum value of a moving standard deviation is determined   Lines 17 and 18 of [Algorithm 4]: lat and lon may be changed to other values by other parts of [Algorithm 4]. For example, lat and lon may be replaced with other calibrated values or estimated values in lines 41, 42, 47 and 48 of [Algorithm 4]. However, in lines 21 and 22 of [Algorithm 4], values provided through a replacement may be replaced back with original values, and in order to perform such an operation, the original values of lat and lon are separately stored in lines 17 and 18.   Line 19 of [Algorithm 4]: Line 19 of [Algorithm 4] represents a condition for performing backtracking represented in lines 20 to 22 of [Algorithm 4]. In this case, three conditions are discussed which should be satisfied. Firstly, a tuple P i−1  at a backtracking discussion target timestamp (i−1) should be filtered or interpolated, secondly, the tuple P i−1  at a backtracking discussion target timestamp (i−1) should not be accel_filtered by an acceleration error, and thirdly, the original speed V i−1,original  of the tuple of the backtracking discussion target timestamp (i−1) should belong to a moving significant interval “MA speed +s×MSD speed ” determined by a window defined as timestamps [i−n+1, . . . i].   Lines 20 to 24 of [Algorithm 4]: When the condition of line 19 of [Algorithm 4] is satisfied, V, lon, and lat values are replaced back with their original values in lines 20 to 22 of [Algorithm 4]. That is, it is determined that the original V, fan and lat values are more accurate than V, lon and lat values calibrated or estimated by other parts of [Algorithm 4], and a return to actually measured data is performed (backtracking). When the backtracking occurs, the NCE is initialized to zero in line 23 and a window size n decreases in line 24. However, the window size n may not be smaller than the minimum value IWS.   Lines 28 and 29 of [Algorithm 4]: When a tuple P i+1  is filtered, NCE increases in line 28. That is, the number of continuous errors increases. In addition, the window size n increases in line 29. However, the window size n may not be larger than the maximum value MWS.   Lines 31 and 32 of [Algorithm 4]: When the tuple P i+1  is not filtered, NCE is initialized to zero in line 31. In addition, the window size n decreases in line 32. However, the window size n may not be smaller than the minimum value IWS.   Line 38 of [Algorithm 4]: When newly measured acceleration is higher than the maximum acceleration, a newly actually measured tuple is filtered and a mark is made as accel_filtered by an acceleration error.       

       FIG. 8  represents a speed actually measured by using position detectors iPhone and Garmin. In this experiment, a speed varies with a continuous value over time but it may be seen that the actually measured data of iPhone and Garmin sometimes has a sudden increase or decrease in speed, which corresponds to an error. 
       FIGS. 9 and 10  are graphs derived by applying the concepts of a moving significant interval, acceleration error detection and a calibrated speed that are described in embodiments of the present disclosure. In  FIG. 9 , a window size is set to 5, and in  FIG. 10 , the windows size is set to 100.  FIGS. 9 and 10  use 287 raw position data acquired on Feb. 27, 2012. 
     When the window size is small (n=5) as shown in  FIG. 9 , a moving significant interval and a calibrated speed sensitively reflect a change in speed. However, when the window size is large (n=100) as shown in  FIG. 10 , it may be seen that the moving significant interval and the calibrated speed do not sensitively reflect a change in speed. 
       FIG. 11  represents an example of data processed according to [Algorithm 4]. The graph is crated by using 9 position data actually measured on Aug. 8, 2012 and includes information on a filtered original speed, a moving significant interval, acceleration, a detected acceleration error, an interpolated speed, a calibrated speed, a speed revived by backtracking. At the time of 08:49:54, since the filtered original speed is out of a range of the moving significant interval and an acceleration error is already detected, the interpolated speed is maintained as is. On the other hand, at the times of 08:49:56 and 08:49:59, the original speed is within the range of the moving significant interval and the acceleration error is not detected, it may be seen that the interpolated speed is replaced by [Algorithm 4] and revived. 
     In the following, a position calibration method according to another embodiment of the present disclosure is described with reference to [Algorithm 4]. 
     It is possible to perform the following steps in order to process information on a tuple including latitude, longitude and a timestamp collected from a position information collection device. 
     In step S 11 , it is possible to determine whether a speed [i+1] V i+1  at a timestamp [i+1] has an error (see line 34). 
     In step S 12 , when it is determined that the speed [i+1] has an error (V i+1 ≧MA speed +s 99.5 ×MSD speed ) in step S 11 , the speed [i+1] is pre-calibrated or restricted (see line 35). In this case, when the speed [i+1] is lower than or equal to a predetermined minimum speed MIN speed , it is determined that the speed [i+1] has no error (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 S 13 , it is determined that acceleration [i+1] a i+1  at a timestamp [i+1] has an error (see line 37). In this case, when the acceleration [i+1] is equal to or higher than predetermined maximum acceleration MAX acceleration , it may be determined that the acceleration has an error (see line 37). 
     In step S 14 , when it is determined that the acceleration [i+1] a i+1  has an error in step S 13 , latitude [i+1] and longitude [i+1] are calibrated (see lines 41 and 42). In this case, it is possible to calibrate the longitude [i+1] by using an average longitude difference MA Vlongitude  until a timestamp [i] and the longitude [i] lon i  at the timestamp [i], and it is possible to calibrate the latitude [i+1] by using an average latitude difference MA Vlatitude  until the timestamp [i] and the latitude [i] lat i  at the timestamp [i] (see lines 41 and 42). In this case, the average longitude difference MA Vlongitude  set in line 16 of Algorithm 4 means a value obtained by averaging, over time, a longitude difference at each timestamp set in line 14, and the average latitude difference MA Vlatiude  set in line 13 means a value obtained by averaging, over time, a latitude difference at each timestamp set in line 11. 
     In step S 21 , it is checked whether a tuple [i] P i  at the timestamp [i] t i  has an error (see line 44). In this case, the presence of the error means that the tuple [i] Pi is filtered by a speed error as described above. 
     In step S 22 , when it is confirmed that there is an error, the latitude [i] lat i  at the timestamp [i] is estimated by interpolating the latitude [i+1] lat i+1  at the timestamp [i+1] t i+1  and one or more latitudes acquired before the timestamp [i], and the longitude [i] lon i  at the timestamp [i] is estimated by interpolating the longitude [i+1] lon i+1  at the timestamp [i+1] t i+1  and one or more longitudes acquired before the timestamp [i] (see lines 47 and 48). In this case, “acquired” may mean being processed by [Algorithm 4] and stored in a memory. 
     In this case, when it is confirmed that there is an error in step S 21 , a position calibration method according to the embodiment may further include step S 23 . 
     In step S 23 , it is possible to estimate a speed [i] V i  at the timestamp by interpolating a speed [i+1] V i+1  at the timestamp [i+1] and one or more speeds acquired before the timestamp (sec line 45). 
     In step S 31 , when the error at the timestamp [i−1] occurs by a speed error and not by an acceleration error, it is possible to determine whether a speed value actually measured at the timestamp [i−1] is smaller than a statistical value, by calculating the statistical value using the average MA speed  and standard deviation MSD speed  of speeds stored at the timestamps [i−n+1] to [i] (see line 19). In this example, the “speed stored” means a value that is processed by [Algorithm 4] and stored in a memory. 
     In step S 32 , when it is determined that the actually measured speed value is smaller than the statistical value in step S 31 , a speed, latitude, and longitude at the timestamp may be replaced with actually measured original values (see lines 20 to 22). In this case, n above is the size of a window. 
     In step S 33 , it is determined that the actually measured speed value is smaller than the statistical value in step S 31 , it is possible to decrease n (see line 24). 
     In step S 34 , when it is confirmed that there is an error at the timestamp [i], it is possible to increase the size of the window (see line 29), and when it is confirmed that there is no error at the timestamp [i], it is possible to decrease the size of the window (see line 32). In this example, the presence of the error may include both when there is a speed error and when there is an acceleration error. 
     A user device according to another embodiment of the present disclosure may include a position information collection unit that collects information on a tuple including latitude, longitude and a timestamp; and a processing unit that processes information on 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 step as described above may be performed every timestamp. Algorithm 4 is described based on the timestamp [i+1] at which a new tuple is acquired, and it is possible to describe Algorithm 4 based the timestamp [i+2]. In this case, in the description of e.g., step S 31  above, in the index of the timestamp increases by +1. 
     Each of the above-described steps may be performed by a user device that includes a position information collection unit collecting information on a tuple including latitude, longitude and a timestamp; and a processing unit processing information on the tuple. 
     Although the present invention is explained in reference with the embodiments depicted in the enclosed set of drawings, it should be noted that this is only exemplary description, and various equivalent other embodiments can be derived from this by an ordinary skilled one in this technical field. Thus, the scope of the present invention should be determined by the claims of the present invention.