Comparative Analysis Of Kalman And Extended Kalman Filters In Improving GPS Accuracy

Comparative Analysis Of Kalman And Extended Kalman Filters In Improving GPS Accuracy

Swapna Raghunatp, Dr. Lakshmi Malleswari Barooru 2, Sridhar Karnam 3

1. G.Narayanamma Institute of Technology and Science, Hyderabad, India

2. G.Narayanamma Institute of Technology and Science, Hyderabad, India

3. Tata Consultancy Services, Hyderabad, India

ABSTRACT

The reference coordinate system being used by the GPS is the World Geodetic System 1984 (WGS- 84), which is a geocentric standard spheroidal reference surface with angular coordinates. To provide a constant distance relationship anywhere on a map, we perform coordinate conversion from WGS-84 to Universal Transverse Mercator (UTM) system using a set of conversion equations. The UTM datum can also be obtained from its WGS-84 counterpart by the Franson CoordTrans software. The conversion from one global coordinate system to another introduces error in the receivers position. This paper discusses the reduction in the datum conversion errors by the use of Kalman and Extended Kalman filters (EKF) using MATLAB (version 7.6) software and some of the plots have been plotted using Microsoft Office Excel 2007. A total of 120 samples of data have been collected at the same location, from the heavy traffic area of Ameerpet, Hyderabad, during three different time intervals, i.e. morning, afternoon and evening using SiRF star receiver. The inconsistencies in the received data have been reduced using a Kalman filter but as the data has a non-linear nature to it, the use of an EKF resulted in further reduction in the coordinate conversion errors. This paper proves that the EKF demonstrates a superior performance over a Kalman filter.

Keywords: Extended Kalman filter , GPS, Kalman filter, UTM, WGS-84, Eastings

1. INTRODUCTION

Global Positioning System (GPS) has improved the navigation, surveying and mapping techniques more profoundly than any other technology [11]. A GPS receiver calculates the coordinates of a point on earth from the data acquired from at least 4 of the GPS satellites which are in line of sight with the receiver. A Hand held GPS receiver can provide data up to a certain accuracy which is sufficient to be used in the preparation of small scale maps [6]. The positional coordinates provided directly by the satellites and the corresponding coordinates obtained from the GPS receiver are extremely accurate but there are many factors that can make the errors in the data non-trivial. Geodetic datum is

a set of constants specifying the coordinate system for a collection of points on the Earth surface. GPS satellite navigation system uses WGS-84 as the universal global datum [4]. It is a three dimensional orthogonal coordinate system employed to specify the position of a receiver. WGS-84 is an angular coordinate system which gives the location of a point in latitude and longitude in degrees-minutes- seconds.

The drawback of WGS-84 is that the distance covered by a degree of longitude differs as you move towards the poles. In order to reduce the complexity of mathematical computations involved in working with WGS-84 system, a map projection

is used which transforms a 3-D spheroid to a 2-D flat surface. This causes the necessity to convert datum from WGS-84 system to the UTM system [4, 14]. The UTM system allows the coordinate numbering system to be combined directly with a distance measuring system. UTM is a two dimensional worldwide flat grid system which allows easy computation of the users position in eastings and northings. The datum conversion from WGS-84 to UTM is done by applying standard conversion formulae. Datum conversion leads to positional errors. Knowledge of the exact position of the GPS receiver is very vital for navigation, surveying and mapping applications. When the erroneous datum is applied to a Kalman filter, there is a marked improvement in the positional accuracy [15]. The Kalman filter has been applied extensively in geomatics both in research and industry for navigation, kinematic positioning and image and data processing. In this paper, an EKF and a Kalman filter have been used independently to decrease the positional errors introduced by the datum conversion in the GPS receiver and their performances have been compared.

1. DATUM CONVERSION ERRORS

The WGS-84 datum, which is an angular coordinate system, introduces some positional error when it is projected on a two dimensional map. To reduce this error, the WGS-84 system is transformed to the 2-D UTM system. The UTM system gives datum in the Northings and Eastings format. Transverse mercator projection orients the equator, north-south, through the poles, providing a north-south oriented swath of little distortion. By slightly changing the orientation of the cylinder onto which the map is projected, successive swaths of relatively undistorted regions can be created. Each swath, 6 degrees wide, is called a UTM zone.

In this paper, Franson CoordTrans software has been used to convert from WGS-84 to UTM format. A set of equations proposed by Steven Dutch [1], with a slight modification from Army (1973), convert latitude and longitude to UTM within less than a meter error. GPS data in the WGS-84 format

was collected from the second floor of an apartment building in the region of Ameerpet using the SiRF star receiver. Assuming the UTM datum from the Franson CoordTrans software to be accurate, the error between the UTM values obtained from the equations and Franson CoordTrans is computed for the collected WGS-84 samples.

The values of Eastings obtained from Franson Coordinates are plotted in figure 1, for 30 samples in the region of Ameerpet. The values of Northings obtained from Franson Coordinates are plotted in figure 2 for the same 30 samples. From the plots in figures 3 and 4, it is apparent that the eastings and northings values are not constant with time. The variation in the values is due to the GPS errors like multipath propagation effects, ionospheric errors, clock inaccuracies, satellite geometry, atmospheric effects, etc.

Fig. 1: Eastings from Franson Coordinates Vs

No. of Samples

Fig. 2: Northings from Franson Coordinates vs

No. of Samples

The Eastings and Northings from equations are shown in figure 3 and figure 4 respectively for 120

samples taken from morning to evening in the region of Ameerpet.

Fig. 3: Eastings from Equations vs No.of Samples

Fig. 4: Northings from Equations vs No. of Samples

The error between the Easting values obtained from Franson CoordTrans software (sw) and the equations (prgn) for the first 30 samples is shown in figure 5. The error in Northings between software and program for the first 30 samples is as shown in figure 6.

Fig. 5: Eastings error between software and program vs No. of Samples

Fig. 6: Northings error between software and program vs No. of Samples

The output obtained from the conversion algorithm is applied to the Kalman Filter algorithm which reduces the error and the variations in the data.

1. KALMAN FILTER

   A Kalman filter is a mathematical toolbox which computes the state estimate of a process with high efficiency in the presence of noise by minimizing the linear mean square error. It employs a Predictor- corrector type estimation to achieve an optimum result. The Kalman filter is an adaptive filter following a recursive algorithm which refines the estimate in a series of passes. The estimation

   probleblems for various applications can be modeled using a Kalman filter. In this paper a alman filter is used to reduce the errors introduced during coordinate conversion, thus improving the overall range measurement accuracy.

   The best estimate of the position with a Kalman filter can be obtained if the system is linear with Gaussian errors. The most distinctive feature of Kalman filter is the use of a recursive data processing algorithm to compute the solution. Each update estimate is computed from the previous estimate and the input data. This only requires the storage of the previous estimate.

   The filter processes measurements to deduce a minimum error estimate of the system by utilizing the knowledge of the system, measurement dynamics and statistics of the system, noise measurement errors and initial condition information. The Kalman filtered datum has less variance and mean error when compared to the datum obtained from direct conversion algorithm

   .

   The Kalman filter estimates the state x Rn, at time step k, of a discrete-time controlled process that is governed by the linear stochastic difference equation is as shown in Equation (1), with a measurement z Rm as shown in Equation (2).

   + (1)

   (2)

   The random variables Wk and Vk represent the process and measurement noise (respectively). They are assumed to be independent (of each other), white, and with normal probability distributions.

   The process noise covariance, Q and measurement noise covariance, R matrices as in Equations (3) &

   (4) might change with each time step or measurement, however here we assume they are constant.

   (3)

   (4)

   The n×n matrix A in the difference Equation (1) relates the state at the previous time step k-1 to the

   state at the current step k, in the absence of either a driving function or process noise. The n×1 matrix B relates the optional control input u R to the state x. The m×n matrix H in the measurement Equation (2) relates the state to the measurement zk. In practice H and A might change with each time step or measurement, but here we assume them to be constant. The Kalman filter estimates a process by using a form of feedback control in which the filter estimates the process state at some time and then obtains feedback in the form of (noisy) measurements. As such, the equations for the Kalman filter fall into two groups: time update equations and measurement update equations as shown in figure 1. Discrete Kalman filter time update Equations (1) & (5) are given as

   (5)

   Time update equations project the state and covariance estimates forward from time step k-1 to step k. A and B are from Equation (1), while Q is from is from equation (3). Discrete Kalman filter measurement update Equations (6) (8) are given below.

   (6)

   (7)

   (8)

   The time update equations are responsible for projecting forward (in time) the current state and error covariance estimates to obtain the a priori estimates for the next time step. The measurement update equations are responsible for the feedback

   i.e. for incorporating a new measurement into the a priori estimate to obtain an improved a posteriori estimate. The time update equations can also be considered of as predictor equations, while the measurement update equations can be corrector equations.

   The first task during the measurement update is to compute the Kalman gain or Blending factor, Kk, which reduces the a posteriori error covariance [2]. The next step is to actually measure the process to obtain zk and then to generate an a posteriori state estimate by incorporating the measurement as in

   Equation (7). The final step is to obtain an a posteriori error covariance estimate via Equation (8). After each time and measurement update pair, the process is repeated with the previous a posteriori estimates used to project or predict the new a priori estimates. The Kalman filter has been proven to reduce the inconsistency in the received GPS coordinates [7]. The plot of Eastings obtained by applying Kalman filter to the data in figure 3 is shown in figure 7. The error between the Kalman filtered easting values and the values obtained from Franson CoordTrans for the first 30 samples is as shown in figure 8.

   Fig. 7: Eastings obtained by Kalman filtering the data from equations

   Fig. 8: Eastings error between software and Kalman filter vs No. of Samples

   The error, as seen in figure 8, is less when compared to the error obtained without using Kalman filter as shown in figure 5.

   The plot of the Northings when Kalman filter is applied to the data in figure 4 is shown in figure 9.

   Fig. 9: Northings obtained by Kalman filtering the data from equations

   The error in northings between the Franson CoordTrans northings data and the Kalman filtered data is plotted in figure 10 for the first 30 samples. This error when compared to the one before applying Kalman filter as shown in figure 6 is less.

   Fig. 10: Northings error between software and Kalman filter vs No. of Samples

   Although a reduction of the positional error in the UTM eastings and nothings is noticed by the use of Kalman filter, there is still a considerable difference between the software UTM and the filtered UTM. This is primarily due to the reason that in a Kalman filter, the state estimate is based on a linear stochastic difference equation and the process to be estimated in this problem is a non linear one. For many applications linear models are adequate, but most real-time systems are nonlinear [12].

   Therefore they have to be linearized about a nominal point, as in case of an EKF which linearizes any nonlinear model around the previous estimate, such that the linear Kalman filter can be applied to it [3]. EKF is the extension of linear Kalman filter to non-linear systems [9].

2. EXTENDED KALMAN FILTER

Estimation of the GPS coordinates is a non-linear problem and Kalman filter falls short in this area as it is a linear filter. The EKF is the most popularly used estimator for nonlinear systems, in which, the state distribution is approximated by a Gaussian random variable, which is then propagated analytically through the first order linearization (approximation) of the non-linear system [10]. The state transition and observation state space models in an EKF are non-linear functions.

The predicted state, xk¯ for an EKF, is a function of the previous state xk 1 as shown in Equation 9 and the predicted estimate covariance, Pk¯, is shown in Equation 10.

derivatives or Jacobians of the functions, f and h have to be computed as they cannot be applied to the covariance directly. Jacobians are partial derivatives of measurement with respect to state. If measurement is a vector of length M and state has a length N, Jacobian of measurement function will be (MxN) matrix of numbers [13]. For every time step, the Jacobian is computed using the predicted state at that time step. The matrix of Jacobians can be substituted in the Kalman filter equations. Thus the non-linear function is linearized by this method.

(12)

The update equation of the estimate covariance, Pk is given by Equation 13.

(13)

When all the 120 samples of the UTM Eastings and Northings from the conversion algorithm are applied to the EKF, the resulting estimated values are as plotted in figures 11 and 12 respectively. When the plots in figures 11 and 12, depicting the extended kalman filtered UTM values, are compared with the plots in figures 7 and 8, showing the corresponding kalman filtered UTM values.

f( ) (9)

(10)

The near-optimal Kalman gain, Kk is shown in the measurement update Equation 11.

(11)

Equation 12 makes use of the function h to compute the updated state estimate, xk from the predicted state. The EKF linearizes the non-linear functions f and h by calculating their Jacobians [5]. The partial

Fig. 11: Eastings obtained by EKF

Fig.12 Northings obtained from EKF

The error between the first 30 samples of UTM Eastings and Northigs obtained from the Franson CoordTrans software and those obtained after applying EKF to the UTM coordinates from equations are as shown in figures 13 and 14 respectively. The plots are very similar to the ones on figures

Fig. 13: Eastings error between software and

EKF vs No. of Samples

Fig. 14: Northings error between software and EKF vs No. of Samples

The EKF is very robust as it uses linear approximation over smaller ranges of state space [8]. It is clearly evident from the plots in figures 9 and 13 that there is a noticeable reduction in error in the UTM Eastings and from plots 10 and 14 in the Northings when the EKF is used. Therefore, the positional accuracy improved further by the use of an EKF as compared to a Kalman filter.

1. RESULTS

   The datum is collected from the second floor of a six storey complex, surrounded by tall buildings, in the heavy traffic area of Ameerpet, Hyderabad, 40 samples each, at three different times of a day i.e. during morning, afternoon and evening. An SiRF Star Receiver has been used to collect positional coordinates in the WGS-84 format which is translated to the UTM coordinates using the software Franson CoordTrans and also using a set of coordinate conversion equations as given in [1]. Kalman filter and EKF are applied to the UTM datum obtained from the equations and the minimum and maximum values of Eastings and Northings and the minimum and maximum values of the errors with respect to the Franson CoordTrans UTM are shown in table 1.

   Table 1. Range of Errors Before and After

   Filters

   Error Between UTM from Software and Equations 0	Eastings Values (meters)		Northings Values (meters)
   	Min	Max	Min	Max
   Before Applying Filter	19314	19365	10733	10876
   After Applying Kalman filter	19304	19353	10723	10881
   After Applying EKF	19290	19348	10715	10875

2. DISCUSSIONS

There is a very large error between the UTM coordinates obtained from Franson CoordTrans and the coordinate conversion equations. When the Kalman filter is applied to the UTM coordinates from the equations there is a clear 10m decrease in the Eastings error and 8m decrease in the Northings error as shown in Table 1. When the EKF is used instead of a Kalman filter to the UTM datum from the equations, there is a 20m decrease in the Eastings error and atleast 10m decrease in the Northings error. From these results it can be said that the EKF has outperformed the Kalman filter.

REFERENCES

1. Dutch.S, Converting UTM to Latitude and Longitude (Or Vice Versa), Natural and Applied Sciences, University of Wisconsin – Green Bay, 8th September, 2004.

2. Welch.G and Gary Bishop, An Introduction to the Kalman Filter, Department of Computer Science, University of North Carolina, Chapel Hill, July 24, 2006.

3. Riberio.M.I, Kalman and Extended Kalman Filters:Concept, Derivation and properties, Institute for Systems and Robotics, Instituto Superior T´ecnico Av. Rovisco Pais, 11049-001 Lisboa PORTUGAL, February 2004

4. Ordnance Survey A guide to coordinate systems in Great Britain, August 2010.

5. Orderud.F, Comparison of Kalman filter estimation Approaches for state space models with non-linear measurements, Sem Saelands vei 7-9, NO- 7491, Trondheim

6. Chalam.S.S.V and I.V.Murlikrishna, Assesment of positional accuracy of GPS A case study, Journal of Geomatics, April 2010, Vol. 4, No. 1, Pages 31-36.

7. Malleswari.B.L,Dr.I.V.Muralikrishna,Dr.K.Lal kishore,Dr.M.Seetha,Nagarathna P.Hegde, The Role of Kalman Filter in the Modeling Of GPS Errors, Journal of Theoretical and Applied Information Technology, 2009, Vol.5, No. 1, Pages 95-101.

8. Grewal.M.S, Angus P. Andrews Kalman filtering, Theory and Practice Using MATLAB, Second Edition,

9. D.Simon, Kalman Filtering, Embedded Systems Programming, vol. 14, no. 6, pp 72-79, June, 2001.

10. Wan.E and Rudolph van der Merwe, The Unscented Kalman Filter for non-linear estimation, Proc. of IEEE Symposium,2000 (AS-SPCC), Lake Louise, Alberta, Canada, October 2000.

11. Kaplan.E.D, Editor,Understanding GPS Principles and Applications, Artech House, 1996.

12. P.S.Maybeck, Stochastic models, estimation and control, volume 2, Academic Press,1982.

13. Simani.S, Kalman filtring: Theory and Applications, Advanced Technologies for Neuro-Motor Assessment and Rehabilitation, Summer School, 10th June, 2006, Bologna, Italy.

14. Langley.R.B, The UTM Grid System, GPS World, Vol. 9, No. 2, pp 46-50, February 1998

15. Swapna.R, P.Visalakshmi and Karnam Sridhar, GPS Datum Conversion and Kalman Filtering for Reducing Positional Errors, Asian Journal of Computer Science and Information Technology, 2011, Volume 1, No. 5, Pages 141-145.