Key Takeaways
- Kalman filters can be utilized to smooth noisy human trajectories.
- Trajectories constructed from sensor data have significant deviations from their actual values which require the use of trajectory smoothing and realignment techniques to correct them.
- In real world applications an out-of-order event handler needs to be coupled with the Kalman filter to ensure the event stream consumed by the Kalman filter are time ordered.
- Multiple fluctuations in the end of a trajectory causes a noticeable error in the final estimation.
- Both position information as well as velocity of the person can be used for Kalman filtering algorithm to obtain high accuracy.
Introduction
Extracting useful information from an uncertain data stream (a stream of data items which does not carry precise information) is a significant issue in data stream processing with a wide variety of applications. In this article we will demonstrate one such application which involves the synthesis of useful information from an uncertain data stream in the domain of transportation and logistics. It is essential to filter the sensor data collected from sensor networks since most of such data are inaccurate due to multiple issues such as sensor malfunctions, environmental noise, etc. Specifically we describe the use of Kalman filters on WSO2 CEP (complex event processing) for smoothing human trajectory information gathered from an iBeacon sensor network. We demonstrate the effectiveness of our solution by comparing an example raw human trajectory against the Kalman filtered results. The use case presented in this article is one of the key example applications of the internet of things (IoT) technology. The solution described in this article has been released with WSO2 CEP, a complex event processing middleware that is part of WSO2’s comprehensive enterprise middleware platform.
Problem Description
We will be using the following example scenario throughout the rest of this article: A person carrying an iBeacon sensor (e.g., a smartphone) walks in a field of iBeacons. The signals transmitted by the iBeacons are received by the iBeacon sensor. And an approximation of the location of the person at a particular time is constructed by triangulating the locations of the iBeacons which the iBeacon sensor detected (see figure 1). However, the location P(x,y) obtained from such triangulation is only a rough approximation of the exact location of that person at a particular time. This is due to multiple reasons such as signals emitted by different iBeacons are received by the iBeacon sensor with similar signal strength, at different times, low sampling frequency of the iBeacon sensor, out-of-order arrival of events, etc. If the iBeacon sensors are operating with low sampling frequency sudden changes made to the trajectory of the person are not properly captured.
Figure 1: A person walking with an iBeacon sensor through a field of iBeacons. The signals sent from the iBeacons are received by the sensor and are used to construct an approximation of the location.
If one plots the raw triangulated path of the person it may create a rough trajectory which has significant deviations from the person’s original trajectory. Hence, a trajectory smoothing and realignment technique needs to be used to correct the trajectory of the person.
Solution Overview
To solve the above problem we are using two techniques: First, we use an out-of-order handler component which introduces ordering to the input event stream. Second, we implement a Kalman filter component which predicts the person’s location given the previous states and the current triangulated location. Next, we will describe how the out-of-order event handling and Kalman filtering have been implemented respectively.
Out-of-order Handler
Out-of-order event arrival is present in general data stream processing applications. The disorder (i.e., lack of order) of tuples within a stream is caused by network latency, operator parallelization, merging of asynchronous streams, etc. There are four main techniques for disorder handling (event reordering) called “buffer-based”, “punctuation-based”, “speculation-based”, and “approximation-based” techniques. The reordering solution implemented in this article is based on the k-slack algorithm. The key idea is to use a buffer to sort tuples from the input stream in ascending timestamp order before presenting them to the query operator. It should be noted that even after the use of a buffer to sort events there can still be events which appear out-of-order in the output due to multiple reasons such as significantly delayed events, etc.
The reordered stream is then sent to a location averaging module to get the average location.
Averaging Location
An iBeacon sensor might detect several iBeacons at some points and will stop receiving iBeacon pings when moving away from that particular iBeacon. The averaging solution will consider all those pieces of information available and triangulate the location of the person.
The averaged-location stream is then presented to a Kalman filter to smooth the trajectory. Next, we provide an introduction to Kalman filtering and move on to describe how Kalman filtering has been adapted in our solution.
Kalman Filter-based Trajectory Smoothing
Detection of signals of known form in the presence of random noise has been a widely discussed issue which dates back to 1950s. Kalman filter is an estimator for a linear-quadratic problem. It is a set of mathematical equations which provides an efficient computational (recursive) way of estimating the state of a process in a way that minimizes the mean of the squared error. The filter estimates the instantaneous state of a linear dynamic system perturbed by white noise. It can estimate past, present, and future states even when the precise behavior of the modeled system is unknown. The typical uses of Kalman filters include smoothing noisy data and providing estimates of parameters of interest. There is plethora of applications of Kalman filters in the autonomous and assisted navigation, smoothing output from laptop trackpads, global positioning system (GPS) receivers, etc.
Trajectory smoothing has become an important issue in recent times due to large collections of trajectory data getting popular. Using Kalman filters has become the preferred solution when it comes to tracking and predicting visual motion. It uses very small memory resources since it only saves the previous state. And it is also suitable for solving real time problems since it’s very fast and the calculation is recursive, so new values can be processed as they arrive.
Our Approach
In this section we provide the details of trajectory smoothing using Kalman filters. There are two techniques to estimate the position of a person. First, we can use only the position information of the person’s trajectory if the person does not move. Second, we can use both position information as well as velocity information of the person in the Kalman filtering algorithm if the person is moving. In this article we follow the latter technique because we are interested in smoothing the trajectory of a moving person. Furthermore, the second technique is more precise because it uses the previous velocity of a person as an additional parameter during the position estimation process. But for clarity we explain both these techniques below. Table 1 lists the parameter definitions used in this article. The middle column shows the dimensions of the used matrices while the actual values used in our Kalman filter implementation are shown inside the parenthesis.
Table 1: Parameter definitions used in this article.
Variable |
Dimensions (Exact Value) |
Description |
Zk |
N×1 (2×1) |
Measurement at time k |
Xk |
N×1 (2×1) |
Estimated value for the measurement using the Kalman Filter |
Rk |
M×M (2×2) |
Covariance of this uncertainty (i.e., the sensor noise covariance) Rk, not used in our implementation |
Ak |
N×N (2×2) |
Transition matrix (State gain) |
Pk |
N×N (2×2) |
Covariance of the estimate Xk |
Qk |
N×N (2×2) |
Each point in x̂ k−1 is moved to somewhere inside a Gaussian blob with covariance Qk (not used in our implementation) |
H |
N×N (2×2) |
Units and scale of the reading might not be the same as the units and scale of the state which we are keeping track of. We use this matrix in order to scale it back to the measurement scale. |
K |
N×M (2×2) |
Kalman gain matrix. |
Kalman Filter Static Model
The very basic implementation of the Kalman filter is based on a static model where we use the location as the only variable in the system. In this scenario we assume the measuring variable has a constant value and we estimate the value as such. Measuring a voltage, still object’s location, etc. are similar uses of the static model. As shown in Figure 2, through application of Kalman filtering what we obtain is “probably the real reading” based on an observed reading. What is meant by this is that the output from a Kalman filter is more closer to the actual location of the user yet it’s not guaranteed that the value will exactly be the location where the person is located.
Figure 2: The expected outcome of Kalman filtering. We need to find the probable real reading from an observed reading which has been diluted by sensor noise.
The main equation of the Kalman filter’s static model is depicted in equation (1).
X’^k = X^k-1 + Kk-1 ( Zk - H*X^k-1) (1)
Prediction
The prediction step predicts the next state at time k.
X^k = A*X^k-1 (2)
Pk = A*Pk-1AT (3)
where X^k is the center of the random distribution which represents the most likely state and the uncertainty is represented by variance Pk.
Update
The update step updates the Kalman gain matrix.
S = H*Pk*HT+R (4)
K’k = Pk*HT*S-1 (5)
X’^k = X^k + K’k (Zk - H*X^k) (6)
P’k = Pk - K’k*H*Pk (7)
Where,
A = 1
X = previouslyEstimatedValue. The previously estimated value was assumed as the initially
measured value.
P = [1000 0]
H = 1
R = standardDeviationOfNoise, We used standardDeviationOfNoise = 0.01
K’k shown in equation (5) corresponds to the updated Kalman gain matrix which is calculated using the covariance matrices of the previous estimates. Then we can calculate the best estimate (i.e., probably the real reading) X’^k and its covariance matrix P’k . These values are fed back to the Kalman filter in the next round of predict or update as many times as required. Note that although table 1 lists two matrices Rk (covariance matrix of measurement noise) and Qk (covariance matrix of process noise) we have not used them in our current Kalman filter implementation.
Kalman Filter Dynamic Model
In this scenario we assume the measuring variable changes its value with time. Examples for this scenario includes a moving object’s position. The main equation of Kalman filter’s dynamic model is the same equation as defined in equation (1) above. However, the parameters used in the matrices change as follows.
A = [1 timeDifference; 0 1]
Initially, the time difference is assumed as 0
X = [previouslyEstimatedValue; ChangingRate]
Initially, the previously estimated value was assumed as the initial measured value
P = [1000 0; 0 1000]
H = [1 0; 0 1]
R = [standardDeviationOfNoise 0; 0 standardDeviationOfNoise]
standardDeviationOfNoise = 0.01
4. System Implementation
We implemented the above described human trajectory smoothing methodology completely with WSO2 CEP and tested its application with real world trajectory data sets. Note that the methodology followed in this article can be implemented with many other state-of-the art event processing systems. The high-level system architecture diagram shown in Figure 3 describes how the overall solution has been implemented. The position events read from the iBeacon sensors are received by a WSO2 CEP receiver. WSO2 CEP comprises of an event processing library called Siddhi. While most of the generic event processing functions such as projection, aggregation, windowing, joining, etc. can be implemented directly using Siddhi’s SiddhiQL query language, more specific processing need to be coded in custom extensions. We use an extension called “reorder” which handles the out-of-order present in a data stream. Next, in Figure 3, the reorder Siddhi extension reorders the stream of events.
Figure 3: Overall system architecture
After that, the average location is calculated and then sent to the Kalman filter which smoothes the trajectory information. The smoothed trajectory information is eventually published to an external geo dashboard application. Such trajectory information could be used to calculate the waiting time of a specific area by using geospatial techniques. Waiting time here refers to the time spent in a specific area. The Siddhi queries shown in Listing 1 indicates how this pipeline has been implemented.
--Retrieving events through event receivers
.
.
--Convert beacon ping stream to the generic format
.
.
@info( name = 'reorderPersonLocatorStream')
from beaconPingStream#reorder:kslack(timestamp, 120000l, -1l, true)
select recordLocator, uuid, timestamp, beaconProximity, fenceAirportCode,
fenceIdentifier, locationEventTriggerType, locationEventType,
mileagePlusNumber
insert into sortedEditedPingStream;
.
.
@info( name = 'averagingBeaconLocationsPerPerson')
from sortedEditedPingStream#custom:averageLocationCalculate(recordLocator,
latitude,longitude, beaconProximity, uuid,
floor, false, airport)
select *
insert into totalAveragedPingStream;
.
.
@info( name = 'smoothingLatitudeAndLatitude')
from totalAveragedPingStream#kf:kalmanFilter(averagedLatitude, averagedLongitude,
timestamp, recordLocator, floor)
select kalmonFilteredStream.recordLocator as id,
kalmonFilteredStream.timestamp as timeStamp, kalmanLatitude as latitude,
kalmanLongitude as longitude, "CUSTOMER" as type, floor,
beaconType, mileagePlusNumber, beaconName, airport, terminal
insert into personLocationStream;
.
.
--Publishing customer location to geo dashboard
.
.
@info( name = 'calculateSecurityAreaWaitTime')
from personLocationStream#custom:updateSecurityWaitTime(latitude, longitude,
floor, id, timeStamp, true, airportCode,
terminal)
select id, timeStamp, latitude, longitude, type, speed, heading, floor, geoFence,
averageWaitingTime, mileagePlusNumber, geoFenceLat, geoFenceLong,
airportCode
insert into securityWaitTimeStream;
.
.
--Publishing to updated security wait time to the geo dashboard
.
Listing 1: Sample Siddhi code snippets of our solution which indicate how the trajectory smoothing process has been conducted.
Experiments
We conducted the Kalman filtering on a data set corresponding to a single person’s trajectory obtained from a real world sensor network environment. The sensor network consisted of about 20 iBeacon sensors installed in a public place and spanning 480 meters. The dataset contained around 9300 events. The data set was reordered and Kalman-filtered following the techniques described above. We plotted the original trajectory as well as the Kalman-filtered trajectory as shown in Figure 4. It can be observed that the original sensor readings are less smooth and the path (shown in blue color) has considerable fluctuations whereas the path calculated by Kalman filtering (shown in green color) is much smoother.
Figure 4: An example human trajectory smoothed using Kalman filtering technique. The red color dots indicate the triangulated position of the person. The green color crosses indicate the smoothed and realigned trajectory using Kalman filtering.
Shown below are screenshots taken from the Geo Dashboard which indicates the effectiveness of our trajectory smoothing technique.
Figure 5: An example of the effectiveness of processing streaming data for a human trajectory with our solution. The two trajectories are drawn on the geo dashboard to show a person’s movement in an airport terminal. (a) In the first screenshot, the raw trajectory information is only reordered and triangulated. (b) For the second screenshot, this data is also processed by our Kalman filtering solution.
Multiple fluctuations at the end of a trajectory causes noticeable error in the final estimation. When there are multiple fluctuations at the beginning of a trajectory, the Kalman filter successfully smoothens the path. But when there are fluctuations at the end of the trajectory, even if the final event delivers the correct position information of the trajectory, the filter handles that as noisy data and smoothens the last position causing the error in the estimation.
Summary
There are many real world problems which require estimation of a system state that changes over time using noisy measurements. In this article we described one example where we corrected a noisy human trajectory using a Kalman filter. During this process we first reordered the events which potentially arrive out-of-order. Next, we estimated the real trajectory of the person using a Kalman filter. We experimented with two Kalman filtering approaches called static model and dynamic model and verified the quality of the corrected trajectory by plotting it alongside the raw trajectory information received from the input streams. In our implementation we developed both Kalman filtering and out-of-order handling as WSO2 Siddhi extensions. Those extensions are accessible under Apache 2.0 open source license from [1] and [2] respectively.
About the Authors
Ramindu De Silva is a Software Engineer at WSO2 where he is mainly working on WSO2 Complex Event Processor. He holds a B.Sc. special degree in Computer Science from the Department of Computer Science, University of Sri Jayewardenepura, Sri Lanka and Diploma in ICT from APIIT Malaysia.
Miyuru Dayarathna is a Senior Technical Lead at WSO2. He is a computer scientist with multiple research interests and contributions in stream computing, graph data management and mining, cloud computing, performance engineering, IoT, etc. He is also a consultant at the Department of Computer Science and Engineering, University of Moratuwa, Sri Lanka. He has published technical papers in reputed international journals and conferences.