189 Modified Exponential Smoothing Method to Improve Course Estimation of a Moving Object © Volodymyr Yuzefovych[0000-0002-6336-9548], © Yevheniia Tsybulska Institute for Information Recording of NAS of Ukraine, Kyiv, Ukraine uzefv71@gmail.com Abstract. This paper proposes a modified exponential smoothing method with variable coefficient to smooth the estimated course of slowly moving objects, calculated using measurements (estimates) of equal or unequal accuracy of the coordinates of these objects. Presented method takes on average 5-6 iterations to converge on object's true heading, while also providing additional reduction of the mean-square error of path estimation. Keywords: tracking moving objects, course of movement, exponential smooth- ing, measurements of equal accuracy, measurements of unequal accuracy, filter- ing. 1 Introduction In the modern age most integrated security and surveillance solutions contain a range of tools for monitoring moving objects. This capability is an essential part of military C4ISR (Command, Control, Communications, Computers, Intelligence, Surveillance and Reconnaissance) systems, traffic control and management, critical infrastructure protection, et cetera. These monitoring systems collect reconnaissance data, often coming from multiple sources with vastly different characteristics, and analyze the combined dataset using advanced computational methods. Their typical function is monitoring aerial, ground and/or waterborne objects within an area of responsibility and providing a clear, con- cise view to the users, allowing quick detection of any abnormal activity in that area. Thus computational problems that have to be solved by such systems include object detection and tracking, motion characterization, trajectory estimation, future path prediction and generating user representation. 2 Related works General requirements for the tracking algorithms are that they should be accurate, fast, robust to different types of motion, and simple to implement and understand [1, 2, 11, 12]. Most studies focus on research and enhancement tracking algorithms based on Kalman filter and extended Kalman filter [2-5]. Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 190 There are simpler alternatives, such as α-β-γ-filter [6, 7] and variations of exponen- tial filter tracking algorithms [8, 9], which use derivative-free measurement model. The works mention ad above show that under certain conditions these algorithms provide tracking and trajectory prediction as accuracy as the algorithms based on Kalman filtering. At the same time they are easier in implement and have greater computational efficiency. 3 Background and a problem formulation In some cases properly solving the problems of trajectory analysis and prediction requires an additional step of smoothing the course estimate generated by the algo- rithm of trajectory processing (secondary processing) on the base of the coordinates obtained from sensor input. In particular, this happens when the speed of the object is such that its linear displacement during observation interval (period between discrete measurements taken by the surveillance tool(s)) is smaller than linear error in the object's measured coordinates. Within this paper, objects that satisfy this condition are referred to as slowly moving. This is common for ground and waterborne targets, and in certain circumstances (large distance to the target, low accuracy of measurements) can apply to aerial objects as well. For example, Figure 1 shows a fragment of a screenshot from the System for pro- cessing information (SPI) about aerial, ground and waterborne objects, developed at the Institute for information recording of NAS of Ukraine [10]. It displays a group of ships moving in formation, as it is first detected by SPI. From this snapshot alone, it is difficult to determine that the targets move on the same course. The situation remains uncertain during the initial stage of target following, as the objects are detected and the software begins tracking their trajectories. The group of ships moving on common course Long-range radar surveillance aircraft Fig. 1. The result of the tracking waterborne objects moving on common course (using SPI) 191 Figure 2 presents simulated tracking results for an aerial object that moves with con- stant speed and heading. The algorithm is based on the first-order Kalman filter in Cartesian coordinates, which is optimal for this type of motion. As the results show, the condition of “slowly moving” for the object leads to an almost chaotic change in the estimates of its current planar course by the tracking algorithm for quite some time. Note that in this simulation the target's course is calculated directly from the output of the Kalman filter. This situation complicates attempts to analyze the behavior of the target and pre- dict its future movements. In addition, it can create difficulties for traffic control, making it hard to ensure traffic safety in highly congested area. Thus, improving ac- curacy of current course estimates for “slowly moving” objects is an important prob- lem. True trajectory of an object Estimation of object coordinates by a sensor Calculated values of an object course Smoothed trajectory of an object by tracking al- gorithm Fig. 2. The results of simulating movement of an aerial object with the parameters: object speed - 40 m/c; distance from the sensor – 20 km, observation period – 2,5 c, MSE (mean squared error) in distance – 300 m, MSE in azimuth and elevation angle – 20’. Simulation was carried out for 100 observation intervals (250 c). Generally, smoothing is defined as a task of reducing the variance of the estimation error of some parameter. As it is important to avoid introducing any systematic errors, in the remaining part of the paper the terms "filter" and "filtering" will be used inter- changeably with the term "smoothing". Movement of any object can be classified as either maneuvering or non- maneuvering motion. We will start by considering a simpler case of an object that moves in straight line, i.e. without maneuvering. Let (xk, yk) – measured Cartesian coordinates of an object, obtained from a sensor, at the k-th step of observation. Then the course is calculated by the formula: 192   π , if (Δx = 0) ∧ (Δy ≥ 0); 2 k k 3  π , if (Δxk = 0) ∧ (Δy k < 0); 2  Δy Qk = arctan k , if (Δxk > 0) ∧ (Δy k ≥ 0); , (1)  Δxk  Δy π + arctan k , if (Δxk < 0);  Δxk  Δy 2π + arctan k , if (Δxk > 0) ∧ (Δy k < 0),  Δxk where Δxk, Δyk – change in the coordinates (xk, yk) at the step k. In [11] it is proposed to apply exponential smoothing to the estimate of the object's course. This is a relatively simple and effective way of smoothing time-invariant pa- rameters [1, 12, 13] and, unlike moving average method and least square method, it begins to “smooth” the parameter starting from the second iteration: Q̂k = (1 − ξ )Qk + ξQ̂k −1 , (2) where Q̂k – is the estimate of the course at step k, obtained by exponential smoothing ˆ ( Q 0 = 0 ); Qk – a course value, calculated based on the estimates of the motion parame- ters at the k-th step of data processing by tracking algorithm (expr. (1)); ξ – exponential smoothing coefficient (ξ varies from 0 to 1). It is well known that when ξ → 1, quality of the smoothing improves, as does the accuracy of the estimate of the parameter after the initial transition. However, the filter takes longer to converge to true value of the parameter. When a coefficient ξ decreases, the situation is reversed. For example, Figure 3 shows the results of the simulated tracking of the non-maneuvering target, where the course estimate was smoothed by the exponential filter with the coefficients ξ = 0,9 and ξ = 0,7 (solid and dashed curves respectively, marked by rectangular marker). Therefore when using exponential smoothing, it is necessary to find a compromise between filter convergence speed and the accuracy of the resulting estimate of the parameter. In addition, it should be taken into account that if the filter is slow to con- verge (ξ → 1), this will cause poor tracking quality if the target is performing a grad- ual maneuver, and for some time after the maneuver is complete. A logical solution to this problem is to use different coefficient ξ values at the different stages of exponen- tial filter convergence. Thus, the purpose of this work is to develop modified exponential filter, which al- lows to converge quickly to real course values of “slowly moving” objects based on the measurements (estimates) of its coordinates and to provide high accuracy of the course estimation after transition process is finished. 193 4 Modified exponential filter for measurements of equal accuracy To provide high-quality smoothing and simultaneously reduce the filter inertia we propose to use a variable smoothing coefficient ξ. The value of the coefficient can be determined unambiguously by the duration of the smoothing run, that is ξ = f(k) for discrete observations of an object. Consider the optimal dependency f(k) for the case where the statistical error of cal- culated course is a constant and does not depend on k (all course estimates are equally accurate), and the object does not change its course over the tracking period. Then the weight coefficient ξ can be determined using the equation for a statistical estimate of the mathematical expectation of a random variable:  1 K Q =  Qk K k =1 , (3) where K – number of observations (course estimates). Thus, based on the above expression, the weight of current k-th course estimate 1k (k − 1) k (K = k) is equal to , and the total weight of all previous estimates is . Then the coefficient ξ at the k-th smoothing step is equal: ξk= (k − 1) k . (4) Substitute the expression (4) to the expression (2): Q̂k = (1 − ξ k )Qk + ξ k Q̂k −1 = (1 − (k − 1) / k )Qk + (k − 1) k ⋅ Q̂k −1 and finally get the expression: Q̂k = (1 / k )Qk + (k − 1) k ⋅ Q̂k −1 . (5) In fact, the expression (5) is the known formula for iteration (recurrent) calculation of the mathematical expectation of a random value. As for k → ∞ we get that ξ → 1, the filter will lose sensitivity to new course values at large values of k. To provide the possibility to track slight course maneuvers by this filter, it is advisable to limit the weight coefficient ξ by certain value kmax: (k − 1) k , if k < k max ; ξk =  (k max − 1) k max , if k ≥ k max . (6) Figure 3 shows the result of the course smoothing with kmax=10 (solid line, marked by stars) There it can be seen that the inertia of smoothing is significantly decreased using the expressions (5)-(6) and this smoothing quality in stationary mode roughly corre- sponds to the case for ξ = 0,9. 194 dg Input data - The number of cycles of data updating – 45; - Observation period of a sensor – 10 c; - Sensor measurement errors of the coordinates: in distance – 300 m; in azimuth – 20’; in elevation angle – 20’; - Average distance from the sensor to an object – about 200 km. real course values; object course estimation by tracking algorithm; smoothed course values for ξ=0,7; smoothed course values for ξ=0,9; smoothed course values for ξ=variable; Fig. 3. Results of the simulation of course estimation and smoothing for an object that moves without maneuvering. The filter given by the expression (5) also performs better (in the average statistical sense) than the standard exponential filter when the target is performing gentle ma- neuver. This is shown in the Figure 4, see the first 10 iterations. The behavior of the filter (5) beyond that time is generally similar to the filter (2) and it allows tracking minor and short time maneuvers of the object. dg Real course Course estimation with measurement errors Smoothed course values for ξ=0,7; Smoothed course values for ξ=0,9; Smoothed course values for ξ=variable Fig. 4. Results of the simulation of course estimation and smoothing for an object that is per- forming slight maneuvers. 195 Experiments have shown that when using proposed modified exponential filter, con- verging to real course values is reduced to 5-6 iterations. In addition, while converg- ing it provides reduction in the mean square error of a course estimate in about 1,5 times. When the object is maneuvering considerably, it is required to perform a "reduc- tion" in the filter history, and continue its "accumulation after the maneuver is com- plete. During the maneuvering only 2-3 last estimates should be used to smooth the motion parameters [1,12,13]. So, during active maneuvering it is advisable to use the expression (6) with kmax = 3 or 4 (ξ ≈ 0,7 - 0,75) to smooth the course. After the maneuver is complete, the varia- ble kmax is limited by the values 10-15. Figure 5 shows the results of simulation course estimation and smoothing for the target that performs a considerable maneuver. There it is shown that dynamical ad- justment of the coefficient ξ according to the expression (5) with the limiting k as described above allows tracking the real course values for the given type of motion with greater accuracy than the exponential filters with the coefficients ξ = 0,7 and ξ = 0,9. Thus, modified exponential filter can be effectively used for smoothing of the es- timated course of the object. Use of the variable smoothing coefficient allows to re- duce the time needed for filter convergence, including after completion of a substan- tial maneuver. dg Real course Course with measurement errors Smoothed course for ξ=0,7; Smoothed course for ξ=0,9; Smoothed course for ξ=variable Fig. 5. The results of the simulation of course estimation and smoothing for an object that is performing a considerable maneuver 5 Modified exponential filter for measurements of unequal accuracy Consider a more general case, when the course is estimated using coordinate meas- urements of unequal accuracy. This case is typical for so-called tertiary or multi-radar data processing in monitoring systems, where the object is monitored simultaneously 196 by multiple sensors with different characteristics [1]. Then the smoothing coefficient ξ can be calculated using the expression for the statistical estimation of the mathemat- ical expectation of a random variable with unequally accurate measurements. According to expression (2) for exponential smoothing and by analogy to expres- sion (5), it is easy to show that current estimation of the course for unequally accurate data is calculated as: Q̂k = pk 1 Pk ⋅ Qk + Pk −1 Pk Q̂k −1 ; (7) Pk = Pk − + pk , pk = 1 σQk 2 where – the weight of the k-th course estimate, obtained from the track- ing algorithm; 2 σQk - mean-squared error of the k-th course estimate from a single data source; Pk – total weight of all course estimates, obtained until the k-th iteration inclu- sive (P1 = p1). So, MSE of the course estimate (σ) at each step of object tracking can be calculat- ed based on the mean squared errors of the estimates of Cartesian coordinates (σx and σy), used to calculate the course of the object (expression (1)). Thus, σ is a function of several random arguments. In this study it is used to calcu- late only a relative weight of the k-th course estimate (expression (6)). Therefore it is possible to determine σ by approximate ratios, for example, using the linearization method, described in detail in [14]. According to this method (it is assumed that the arguments are independent): σQ2 = (dQ/dx)2σΔx2 + (dQ/dy)2σΔy2, (8) 2 2 2 2 σ 2 =σ 2 2 + σ ≈ 2σ 2 σ Δy =σ y −1 + σ ≈ 2σ y y where Δx x −1 x x and . 2 σ : 2 Ultimately, according 2 to expression (8), for  Δx  2  Δy  2 Δx 2 σ Δ2 y Δy 2 σ Δ2 x σ Q =  2 2  σ +  −  σ + 2 , 2   Δx + Δy  Δy  Δx 2 + Δy 2    Δx = Δx + Δy 2 2 2 ( Δx 2 + Δy 2 ) ( ) or finally with the index k: 2 2Δxk2σ 2yk + 2Δyk2 σ 2xk σQk = . (Δx + Δy ) 2 k 2 2 k (9) Expressions (7) and (9) reflect the functional dependence of the smoothing coefficient for modified exponential filter for object course. This, in contrast to expression (5), takes into account unequal accuracy of the current estimates of the course. Figure 6 shows the results of a course smoothing using exponential filter with the coefficient ξ=0,9 and modified exponential filters for equally accurate and unequally accurate estimates of the motion parameters obtained from multiple reconnaissance 197 sensors. In this simulation it was assumed that the data about the motion parameters of the target is received consecutively from three unequally accurate data sources. Real course values Values of unequal-accuracy measurement Smoothed course values for ξ=0,9 Smoothed course values for ξ=variable (equal-accuracy) Smoothed course values for ξ=variable (unequal accuracy) Fig. 6. The results of the simulation of course estimation and smoothing for an object that does not maneuver. As it is shown, modified exponential filter that takes into account unequal accuracy of the estimates of smoothed parameter shows better results than other exponential fil- ters. On average, this filter can further reduce convergence time by several iterations of data update and further decrease the mean squares error of the estimate. Note that specific characteristics of modified filters are directly proportional to the number of data sources and their accuracies. 6 Conclusions This work proposes a modification of a well-known method of exponential smoothing of dynamical data for the smoothing of course estimate when tracking “slowly mov- ing” objects. Modified exponential smoothing method uses variable value of the smoothing coefficient, in contrast to the constant coefficient in the regular exponential filters. The variable value of smoothing coefficient is calculated based on the equa- tions of the statistical estimate of the mathematical expectation of a random value. The problem of determining the value of the smoothing coefficient for modified exponential filter is solved for a special case of equally accurate estimates of a smoothed parameter, and then for a more general case of unequally accurate data. As a result, convergence time of modified filter to real course values is decreased on average by 5-8 iterations. In addition, it provides the reduction of the mean squared error in 1.5-2 times. It allows to obtain more accurate course estimates for 198 slowly moving objects at the initial stage of their tracking when the uncertainly about their actions is the greatest. Therefore, proposed modified method of exponential smoothing can be used to smooth consecutive series of equally accurate and unequally accurate measurements (estimates) of any values, which are constant over time or changing slowly, to reduce the number of iterations required to converge to real parameter values. References 1. Farina A., Studer F. Radar Data Processing: Introduction and Tracking. John Wiley, new York, USA (1985). 2. Kaawaase K.S., Chi F., Shuhong J., Bo Ji Q. A Review on Selected Target Tracking Algo- rithms. Information Technology Journal 10, 691-702 (2011) https://scialert.net/abstract/?doi=itj.2011.691.702. 3. Sarkka S., Tolvanen V., Kannala J., Rahtu E. Adaptive Kalman Filtering and Smoothing for Gravitation Tracking in Mobile Systems. In: International Conference on Indoor Posi- tioning and Indoor Navigation (IPIN), Banff, Alberta, Canada (2015). 4. Aravkin A., Burke J. V., Ljung L.,Lozano A. Generalized Kalman Smoothing: Modeling and Algorithms //arXiv:1609.06369v2 [math.OC] (2016). 5. Dehghannasiri R., Esfahani M.S., Dougherty E.R. Intrinsically Bayesian robust Kalman filter: an innovation process approach. IEEE Trans. Signal Process. 65(10), 2531–2546 (2017). 6. Kenshi Saho and Masao Masugi. α–β–γ tracking filters using acceleration measurements. Springerplus (2016) https://springerplus.springeropen.com/articles/10.1186/s40064-016- 1960-8 7. Jeong T.G., Njonjo A.W., Pan B.F. A Study on the Performance Comparison of Three Op- timal Alpha-Beta-Gamma Filters and Alpha-Beta-Gamma-Eta Filter for a High Dynamic Target. The International Journal on Marine Navigation and Safety of Sea Transportation 11(1), 55-61 (2017). 8. Joseph J., La Viola Jr. Double Exponential Smoothing: An Alternative to Kalman Filter- Based Predictive Tracking. Eurographics Workshop on Virtual Environments (2003). http://cs.brown.edu/people/jlaviola/pubs/kfvsexp_final_laviola.pdf. 9. Karmaker C.L. Determination of Optimum Smoothing Constant of Single Exponential Smoothing Method: A Case Study. International Journal of Research in Industrial Engi- neering. 6(3), 184–192 (2017). 10. Петров В.В., Кожешкурт В.И., Буточнов А.Н., Науменко Е.М., Осташевский В.Б. Основные направления создания автоматизированных систем мониторинга воздуш- ного, наземного и надводного пространства в реальном времени. Реєстрація, зберігання і обробка даних 12(2), 151-164 (2010). 11. Кожешкурт В.И., Юзефович В.В. Дослідження схем фільтрації алгоритмів трасової обробки інформації в системах моніторингу динамічних об’єктів. Реєстрація, збері- гання і обробка даних 12(4), 3–12 (2010). 12. Кузьмин С.З. Основы теории цифровой обработки радиолокационной информации. Сов. радио, Москва (1974). 13. Кузьмин С.З. Цифровая радиолокация. Введение в теорию. КВіЦ, Київ (2000). 14. Вентцель Е.К. Теория вероятностей. Наука, Москва (1969).