A Study of Error Minimization Techniques in Localization and Motion Tracking Systems

A Study of Error Minimization Techniques in Localization and Motion Tracking Systems

Richa Singh (M.Tech.), Sumit Sharma (Professor), Ravi Mohan (HOD, Professor)

Department of Electronics & Communication Engineering, Shri Ram Institute of Scinece & Technology, Jabalpur (M.P.), India

Abstract

Position estimation, motion tracking and processing increasingly finds applications in many fields including healthcare and defense. In general, most of the outdoor localization systems operate in a noisy environment that often yeilds imprecise and inaccurate measurements. In many cases, it is almost impossible to achieve the precise position of targets and eastimation of their motions. Overprovisioning has adverse effect on the cost of overall system. Thus it becomes paramount to recognize the various sources of errors and minimize their impact through cost-effective techniques at system level.

In this paper, we present a comparative study of various sources of errors that can affect the preciseness in a location tracking system. We also study the impact and magnitude of the error in the final position estimation. Finally, we breifly discuss few cost-effective error minimization techniques that can be incorporated in the localization system to make them more robust. Wherever possible we also present simulation results to show the quantitative robustness of the techniques and the error-correcting capabilities.

Keywords Localization, Motion processing, Error minimization, Filtering

1. Introduction

   Human-body tracking and localization is receiving worldwide attention from researchers of different fields [1-3, 20-22]. The interest is primerily due to the emergence of wide range of applications from various disciplines i.e. healthcare, surveillance, security, human-computer interaction. Most of the human-body motion tracking systems are based on vision sensors. Recently, there has been a significant exploration in tracking people trajectory across multiple image views. Some of these proposed approaches also incorporate systems that are capable of segmenting, detecting and

   tracking people using multiple synchronized surveillance cameras located far from each other. However, such systems try to hand-off image-based tracking from camera-to-camera without recovering real-world coordinates.

   One of the biggest issue that arise in location and motion tracking systems is the accuracy of the target locations. It is always possible to overprovision the system with more hardware such as sensors and processing elements. However, doing so makes the overall system cost-ineffective. As an alternative to overprovisioning, there have been numerous proposal to minimize the error in localization systems. In this paper we study the error minimization techniques that are effectively employed in numerous systems.

   The rest of the paper is organized as following. Before we discuss the basic principles of localization system in the Section 3, we present a brief discussion in the Section 2. In the Section 4 we point out the sources of error and in the Section 5 we discuss the underlying workings of error minimization techniques. We qualitatively compare the techniques in the Section 6 and discuss the future work in the Section 7. Finally, we conclude the study in the Section 8.

2. Background and Related Work

   There has been substantial work in estimating location and motion tracking of various objects, ranging from warehouse goods to human movement, and correcting the related measurement errors. Related work in the area of location and motion tracking system falls into these following four broad categories: (1) IR- based systems (2) indoor RF-based systems (3) wide- area cellular-based systems, and (4) everything- else,

   e.g. ultrasound, magnetic fields, etc. Some of well known localization techniques and systems are presented in the Table 1 along with their attributes that are of common concern for designers and end users.

   TABLE I

   OPERATING RANGES OF LOCALIZATION TECHNIQUES

   System	Protocol	Range	Scalability	Cost
   RADAR	WLAN, RSS	3-5m	Good / 2D, 3D	Low
   EKAHAU	WLAN, RSSI	1m	Good / 2D	Low
   COMPAS S	WLAN	1.65m	Good / 2D	Low
   Snap Track	Assisted GPS, TDOA	5-30m	Good / 2D, 3D	Medium
   Sappire Dart	Unidirectional UWB, TDOA	< 0.3m	Good / 2D, 3D	Medium to high

   In a generic scheme of indoor localization, location of target can be determined by proximity or distance measuring sensors mounted on ceiling at known coordinates. Over time these distances and their differences can be used to pinpoint the exact locations and movements of the target. Because each sensor is only meant to determine the distances, it can be very simple and designed in a power efficiencient manner. All the distances are send to a centralized trilateration system (CTS). Many of the error minimization techniques can be applied once the noisy data has been captured from the low-cost sensors. In general, post processing to minimize the error is more cost effective than using precise sensor and motion capturing cameras as a replacement of sensors.

3. Localization Systems

   There are three main components of localization and position estimation: (1) distance estimation, (2) position computation, and (3) localization algorithm. Most of the position computation techniques are either based on lateration (distance measurement) or angulation (angle measurement). Lateration techniques are based on the precise measurements to three non- collinear anchors. Lateration with more than three anchors are called multi-lateration. Angulation or triangulation is based on information about angles instead of distance.

   3.1 Trilateration: Matehmatical Founction

   Trilateration is commonly used method to determine the position of a target point/object based on simultaneous distance measurement from three other known points/stations (also known as references) located at known sites. This operation is common in

   kinematics, aeronautics, crystallography, computer vision, robot localization and many other.

   Here is the basic principle upon which trilateration works. Assume we know the coordinates of three reference points/sensors S1, S2 and S3 known which are (x1,y1,z1), (x2,y2,z2) and (x3,y3,z3) as shown in the Table below. A fourth sensor S4 is added for better reliability and robustness.

   Figure 2: Trilateration to estimate the position of a target

   Lets assume the 4 sensors which are denoted by Si and position of each sensor is (xi, yi, zi). For notational convenience we use Si(xi,yi,zi) where i=1, n. The approximate distance from the point P(x,y,z) is di from Si. Exact distance is Di as oppose to di. Assume room is a m long, b m wide and c m high. The approximate distance can be computed by following formula.

   After substituting the values of sensors coordinates we have these following set of equations that represent the approximate distances of the target point P from various sensors.

   The solution of target coordinate can be achieved by solving these non-liner equations

   These coordinates hve some uncertainity in them because of numerous errors.

4. Sources of Errors

   In this section we discuss some of the common error that are either introduced in the distance measurement of in the final estimation of target.

   1. Round-off Errors

      Round off error is due the limited number of bits to represent the distances and intermediate computations. In many embedded system, people use fixed-point representation as oppose to computationally expensive floating point representation. The primary reason to use fixed-point as oppose to floating point is to minimize the hardware requirement which would save overall power. We determine the worst case error due to round off and show that it is negligible. For this analysis we assume dimensions are in the order of few meters to 10s of meters. From the Figure 3, it is evident that if we use 12-bits for fixed point representation we encounter the worst case error of 3 mm in distance measurement. For a typical dimension of 5 meters it is less than 0.06%.

   2. Measurement Uncertaintity

      Another major source of error is due to uncertainty of measurement. The uncertainty in range can be from thermal noise, measurement error in TOA or error in receiver. For simplicity we lump all sources of error together and combine them with the uncertainty with the range measurement. When we accommodate the error term in every dimension we now search the intersection of hollow spheres and get a region where the target maybe as opposed to a precise location of the target.

      Figure 3: Worst case round off error in fixed-point representation for 10s of meters dimension.

   3. Other Sources of Error

      Even with the improved signal detection algorithm, individual range estimates may still be erroneous, albeit less frequently, due to a threshold setting that is too low, hardware malfunction, or some other causes, such as another nearby node chirping out of turn. Assuming that the errors are not correlated, we make multiple distance measurements for a pair of nodes and apply statistical filtering to yield a more stable and accurate estimate of the actual distance. Depending on the number of measurements, we take the median or mode value of the measurements, which limits the effect of outliers. The mode operation is more resistant to the effects of uncorrelated outliers than the median, but it needs more measurements to be effective. The statistical filtering is quite effective at discounting uncorrelated errors caused by random, one-time events.

5. Error Minimization Techniques

   The distance measurements available are frequently only approximations. Fairly accurate positions can be calculated with these approximate distances by using various iterative procedures and error minimizing algorithms. Also placing the sensors are right angle from the target object reduces the uncertainty. The two worst case scenarios are when the target object is either 0 or 180 degree from the sensors.

   1. Least Square Method

      The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in the results of every single equation.

   2. Kalman Filter Based Correction

      The Kalman filter, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, containing noise (random variations) and other inaccuracies, and produces estimates of unknown variables that tend to be more precise than those based on a single measurement alone. The algorithm works in a two-step process. In the prediction step, the Kalman filter produces estimates of the current state variables, along with their uncertainties. Once the outcome of the next measurement is observed, these estimates are updated using a weighted average, with more weight being given to estimates with higher certainty. More formally, the Kalman filter operates recursively on streams of noisy input data to produce a statistically optimal estimate of the underlying system state.

      Extensions and generalizations to the method have also been developed, such as the extended Kalman filter and the unscented Kalman filter which work on nonlinear systems. The underlying model is a Bayesian model similar to a hidden Markov model but where the state space of the latent variables is continuous and where all latent and observed variables have Gaussian distributions. The accuracy of positioning sensors such as GPS is often limited to indoor environments.

      Sigma point kalman smoother (SPKS) fuses a predictive model of human walking with a number of low cost sensors to track 2D position and velocity. A number of commercial and research prototype systems currently exist for indoor localization system typically use infra red (IR), radio frequency (RF), or ultra sound sensors.

   3. Genetic Algorithm Based Correction

      Genetic algorithm is very effective in searching a solution space and can be modeled for the localization problem in Wireless Sensor Network (WSN). In a typical GA based correction system, the first phase uses a traditional range free localization algorithm based on Mobile anchor to estimate the location of a sensor node roughly. The second phase is a post optimization phase that uses Genetic algorithm which increases the accuracy of localization. The proposed localization approach, called Localization with Mobile Anchors and Genetic Algorithm (LMA-GA). LMA-GA gives very high localization accuracy as well as does not require extensive searching as in traditional Genetic algorithm.

      From the average error of MAP and LMA-GA methods obtained from the experimentation, it is observed that the percentage of localization error has decreased by 84%. LMA-GA also does not require expensive hardware as in range based methods and it does not require flooding of messages as in traditional range free algorithms. LMA-GA is an inexpensive and an efficient strategy that gives good localization accuracy.

   4. Baycentric Corrdinate Technique

      It has been shown that barycentric coordinates using the closed-points (BCCP) algorithm can be used to minimize the positioning error values [24]. The analysis results of the BCCP algorithm are compared with those of the LS method for performance analysis of the BCCP algorithms. BCCP methodology may provide more precise location detection when used with GPS and wireless communications either outdoors or indoors. The least-square simulation results shows an average of 3.5m and a standard deviation of 1.5m over 500 simulations for ranging errors of 0.3m, 3.6m, and

      0. 6m with a triangular AP arrangement. The BCCP algorithm simulation results show an average of 3.3m and a standard deviation of 1.29m.

   5. Filtering/Smoothing

      Filtering approaches estimate the unknown true state x(t) from some noisy observations y(t). In general, the estimation is called prediction, filtering, or smoothing if observations before frame t, including t, or also after t are taken into account. The filtering problem is typically solved by Kalman filtering or particle filtering where it is assumed that the underlying stochastic processes.

      xt+1 = ft (xt)+vt (1) yt =ht(xt)+wt (2)

      For 3D human motion capture, particle filters were combined with Markov chains, called Hybrid Monte Carlo filter, and graphical models, called nonparametric belief propagation. Even though filtering approaches exploit temporal coherence, handle noise and are able to recover from errors, they are usually too imprecise for motion analysis in high dimensional spaces.

   6. Cooperative Localization

      Few proposals employed techniques to achieve cooperative localization of a team of robots while jointly tracking moving targets. They model the

      problem as graph-based optimization, where the poses of the robots, of the moving targets and of the static landmarks are jointly estimated in a least squares minimization framework. The results show that their approach leads to increased accuracy in the estimation and to an improved scalability in scenarios in which a higher number of robots is required.

      Figure 4: Absolute error in meters in a cooperative localization at different time step

      Figure 5: Error in target position estimation; 10 robots with PFs, 5000 particles each

6. Comparison of Techniques

   In order to evaluate and compare various localizations systems here are few metrics that should be considered. While we should optimize the specific metrics we should also ensure that none of these are compromised beyond a certain threshold.

   1. Cost and Overhead

      There are different types of cost associated with an indoor positioning system (IPS). The main components of cost include cost of infrastructure, positioning devices, system installation, and maintenance over time. Outdoor positioning system, such as GPS, have a large infrastructure to support the location measurement which is expensive and complex. Time and space cost are also factors indicating the efforts for the operation of the IPS. Time cost involves the time requirement of system installation and the time length of the positioning system.

   2. Performance

      Accuracy and precision are two main performance parameters. Accuracy means the average error distance. Precision is defined as the success probability of position estimations with respect to the predefined accuracy. Accuracy only considers the value of mean distance errors. Location precisions consider how consistently the system works. Generally Cumulative Distribution Function (CDF) for distance error is used for measuring the precision of a system. When two positioning techniques are compared, if there accuracies are the same, we prefer the system with the CDF graph, which reaches high probability values faster, because its distance error is concentrated in small values. CDF is described in percentile format.

   3. Scalability

      Scalability is defined as the number of objects that an IPS can locate within a certain amount of infrastructure devices and within a given time period. A stable IPS that can simultaneously locate a large number of objects is predefined. For example, the orientation calculation of an object is required in a motion tracking application, which needs at least three, non-collinear located targets mounted on the object to perform orientation calculation. Thus the deployed IPS needs to simultaneously locate at least three targets and offers higher scalability for the location sensing and location based application.

   4. Robustness and Quality-of-Service

      A robust IPS should be able to function even in some catastrophic cases such as some devices in the system are malfunctioned or a mobile devices runs out of battery energy. For example the IR positioning technique needs line of sight signal transmission between the emitters and the tags. In the Active Badge system a user wears an active Badge. If the badge is covered by his /her thick clothes, It cannot get location information from the system. Since the line of sight communication are not possible the active Badge and the emitters. Thus for those serious situations and faults in the system, the positioning system should offer at least reduced positioning services.

   5. Compelxity

      An aspect of the complexity of IPS is about the human intervention/efforts during the deployment and maintenance of the IPS. For example, the WLAN based

      IPS reuse the existing access point of WLAN as reference locations are positioning measuring units that do not need much infrastructure installation. Another aspect of the complexity indicates the required computing time of the device carried by the user to determine his /her position. Because of the limited CPU processing and battery power of the mobile devices, an IPS uses positioning methodology with lower calculation complexity are desired.

7. Future Work

   There are several aspects of complete system, which are still under exploration, and current investigation would try to address those. Understanding the choices of sensors that can be used for position determination and their power, energy and performance analysis is part of future exploration.

8. Conclusion

   We studied the impact of various communication protocols and the error introduced due to various sources. We also studied various error minimization techniques and their effectivenss. Our analysis shows that a simple fixed-point based computation introduces only few millimetres of error in a room-size setting. This can be helpful in avoiding the use of compute intensive hardware such as CPUs and complete tracking algorithm can be implemented in low-power embedded devices at sensor-end itself. Cooperatie localization based techniques minimize the overall uncertaintity and are the very effective.

9. References

1. D. Zhang, F. Xia, Z. Yang, L. Yao, W. Zhao, Localization Technologies for Indoor Human Tracking, in The Fifth ICFIT (FutureTech), Busan,

   Korea, 2010. pp. 16

2. R. Want, A. Hopper, V. Falcao, J. Gibbons. The Active Badge Location System, ACM Transactions on Information Systems, Vol. 10, No. 1, January 1992, pp 91-102. (ORL Technical Report 92.1)

3. R. Azuma, Tracking Requirements for Augmented Reality, Communications of the ACM, Vol. 36, No. 7, pp: 50-51, July 1993

4. N. Adams, R. Gold, B. N. Schilit, M. Tso, and R. Want, An Infrared Network for Mobile Computers, In Proceedings of the USENIX Symposium on Mobile and Location-independent Computing, pages 41-52, Cambridge, MA, August 1993.

5. F. Bennett and A. Harter. Low Bandwidth Infra-Red Networks and Protocols for Mobile Communicating

   Devices, Oracle Research Lab (ORL) Technical Report 93.5.

6. A. Ward, A. Jones, and A. Hopper. A New Location Technique for the Active Office, IEEE Personal Communications, Vol. 4, No. 5, October 1997, pp 42-47. (ORL Technical Report 97.10)

7. Z. Yang and Y. Liu, Quality of Trilateration: Confidence Based Iterative Localization, In the Proceedings of the 2008 the 28th ICDCS – vol 00 (June 17-20,2008). IEEE Computer Society, Washington, DC, 446-454

8. A. Bahr, J. Leonard, Minimizing Trilateration Errors in the Presence of Uncertain Landmark Positions, In Proceedings of the 3rd ECMR, Germany, Sept 2007

9. B. Wellenhoff, H. Lichtenegger and J. Collins, Global Positions Systems: Theory and Practice, 4th Edition, Springer Verlag 1997.

10. A. Kelly, Precision dilution in mobile robot position estimation, in Intelligent Autonomous Systems, Amsterdam, Holland, 2003.

11. K. Al Nuaimi, H. Kamel, A survey of indoor positioning systems and algorithms, Innovations in Information Technology (IIT), 2011 International Conference on, vol., no., pp.185-190, 25-27 April 2011

12. M. Depsey, Indoors positioning Systems in Healthcare, Radianse Inc. White paper, 2003.

13. S. Gezici, A survey on wireless position estimation, Wireless Personal Communications, vol. 44, no. 3, pp.263-282, Feb.2008.

14. Jason W.P.Ng, Ubiquitous Healthcare Localization Schemes , 7th International Workshop on Enterprise networking and computing in Healthcare Industry, HEALTHCOM, June 2005, Page(s): 156-161.

15. P. Prasithsangaree, P. Krishnamurthi, and P. K. Chrysanthis, On indoors position with wireless LANs in Proc. IEEE Int. Symp. Pers. Indoor, Mobile Radio Commun, Sep. 2002, Vol.2, pp. 720-724.

16. C. Savarese, J. M. Rabaey, and J.Beutel, Locationing in distributed ad-hoc wireless sensor networks in Proc.

    IEEEICASSP, May 2001

17. J. Hightower and G. Borriello, Location systems for ubiquitous computing Computer, vol. 34, no. 8, Ag. 2001.

18. K. Pahlavan, X. Li, and J. Makela, Indoor geo-location science and technology, IEEE Com. Mag., vol.40, no. 2, pp. 112-118,Feb. 2002.

19. M. Vossiek, L. Wiebking, P. Gulden, J. Wiehardt, C. Hoffmann, and P. Heide, Wireless Local Positioning, IEEE Microwave Mag., vol. 4, Issue 4, December 2003, pp. 77-86.

20. C. Flora, M. Ficco, S. Russo, and V. Veccio, Indoor and outdoor location based services for portable wireless devices, Proc. 25th IEEE ICDCS Workshop, 2005.

21. L. M. Ni and Y. Liu, LANDMARC: Indoor Location Sensing Using Active RFID, Proc. IEEE International

    Conference on Pervasive Computing and Communications, 2003, pp. 407-416.

22. Y. Wang, X. Jia, and H. K. Lee, An Indoor wireless positioning system based on wireless local area network infrastructure, Proc. 6th International Symposium on Satellite Navigation Technology Including Mobile Positioning and Location Services, 2003.

23. P. Prasithsangaree, P. Krishnamurthi, and P. K. Chrysanthis, On indoor position location with wireless LANs, Proc. 13th IEEE Intl Symposium on Personal, Indoor and Mobile Radio Communications, September 2002.

24. Joonseong Gim, Jong-Kyun Hong, Sang-Sun Lee, Error Minimization Algorithm Using Barycentric Coordinates for Wireless Positioning Systems Appl. Math. Inf. Sci. 7, No. 5, 1783-1788

25. S. Kawakubo, A. Chansavang, S. Tanaka, T. Iwasaki, K. Sasaki, T. Hirota, H. Hosaka, and H. Ando, Wireless Network System for Indoor Human Positioning, Proc. 1st Intl Symposium on Wireless Pervasive Computing, 2006, pp. 1-6.