{'fraction_non_alphanumeric': 0.019975579975579975, 'fraction_numerical': 0.0017094017094017094, 'mean_word_length': 4.9783941605839415, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Target Tracking Using Kalman Filter Based Algorithms

Kalman filter and its families have played an important role in information gathering, such as target tracking. Data association techniques have also been developed to allow the Kalman filter to track multiple targets simultaneously. This paper revisits the principle and applications of the Kalman filter for single target tracking and multiple hypothesis tracking (MHT) for multiple target tracking. We present the brief review of the Bayes filter family and introduce a brief derivation of the Kalman filter and MHT. We show examples for both single and multiple targets tracking in simulation to illustrate the efficacy of Kalman filter-based algorithms in target tracking scenarios.


Introduction
Target state estimation, or tracking, is an essential technique over decades that aims to obtain continuous or discrete states of one or more desired objects from sensor measurements and recursively update them over time. Target states may vary from geometric information such as position and orientation to any other information one may interested in, such as color and battery level, resulting in a broad class of applications ranging from robot localization and mapping to surveillance and autonomous driving [1,2]. Probabilistic manners are often applied in target state estimations due to noise and uncertainty in the real world. Such methods represent the uncertain target states via the belief distributions as time steps move forward. The most general algorithm for calculating beliefs is given by the Bayes filter algorithm, which calculates the belief distribution from measurement and control data, with a Markov assumption that the current state includes complete information of the past [3]. However, in practice, the exact belief distributions are often intractable in continuous spaces due to computational complexity, and approximation techniques are required in most robotics problems. In general, two classes of approximation skills have been developed, i.e., the parametric techniques and the non-parametric techniques.
The most important and popular family of parametric state estimators are Gaussian filters, which represent the beliefs by multivariate Gaussian distributions. For a linear Gaussian system, a Kalman filter (KF) can be applied to represent the beliefs by the moment representation, i.e., the mean and the covariance in a way that yields to Gaussian posterior beliefs propagated recursively with closed-form solutions [4]. The extended Kalman filters (EKFs) release the linearity assumptions by expressing the next state probabilities and the measurement probabilities using nonlinear functions and calculates an approximation to true belief represented by a Gaussian [5]. As noted by Wan et al., the EKF allows large errors in the true posterior, which may result in sub-optimal performance and even divergence [6]. The unscented Kalman filter (UKF) was later proposed to overcome the flaws in using EKF by representing the state distributions via sample points [7]. All above mentioned Gaussian filters can track the beliefs in polynomial time. Non-parametric filters approximate beliefs by a finite number of values rather than a fixed functional form. As a result, non-parametric filtcane to track both continuous and discrete states with adaptive computational time depends on the approximation accuracy. One example is the histogram filter, which decomposes the state space into many finite regions and represents the cumulative posterior for each region by a single probability value [3]. Another non-parametric implementation of the Bayes filter named the particle filter represents the posterior by a random scatter of samples drawn from this posterior [8]. The particle filter approximates posterior over a particular region via weighted particles in that region by Monte-Carlo-based statistical signal processing. Compared with the most popular Kalman filter, the particle filter has a lower system requirement, i.e., neither the system model equation is required to be linear, nor the system noise is required to be Gaussian and better scalability and universality. However, many samples may be required to approximate the posterior accurately, which brings a heavier computational burden.
For the state estimators to track multiple discrete targets, data association is often required to match estimated target tracks to true targets. Many multiple target tracking (MTT) techniques have been developed over the years, such as global nearest neighbor (GNN), joint probabilistic data association (JPDA), multiple hypothesis tracking (MHT), and particle filters based method. Each of them solves the data association problem differently [9][10][11][12]. Such multiple target trackers figure out a unique label for each track (target) over time. Another class of multiple target trackers, based on random finite set statistics, does not require explicit data association [13]. For example, the probability hypothesis density (Ph.D.) filter represents the multiple targets posterior via the first-order moment (mean) of target density distribution and propagate it over time. In this way, the environment and measurement noise is incorporated in the form of the intensity of target distribution [14]. It is especially suitable in scenarios where unique target labels are not required, such as rescuing people from fire scenes.
In this paper, our contributions are three-fold. Firstly, we briefly investigate the background of the generic Bayes filter and its mathematic derivation. Secondly, we revisit the Kalman filter and the multiple hypothesis filter in detail under single target tracking and multiple target tracking scenarios, respectively. Thirdly, we show simulation demos and results for single and multiple target tracking using our introduced trackers and analyze the efficacy.

Bayes Filter
In this paper, a Bayes filter is tasked to recursively estimate the position of a set of n targets in a 2-D plane using sensor measurement   . A single target tracking problem will be formulated when 1 n a multiple target tracking problem will be formulated otherwise.
In practice, the measurements can be obtained by either a fixed or a mobile sensor and by either one or more sensors depending on the applications. Typical sensor models that can measure target planet positions include the camera, laser scan, radar, etc.
The Bayes filtering technique only calculates the approximate state posterior of the current moment, which will then be utilized in the next discrete time step for state posterior estimation. This is an iterative process based on the Markov assumption that the current estimated state i x is a complete summary of all past estimations 3 target motion model, which can be obtained before the task using data-driven manners or based on experiences. Based on the Markov assumption given by One-section Markov: One-section Markov: Conditional independence: ( The Bayes filter prediction step is outlined by and the update step is given by

Kalman Filter for Single Target Tracking
The Kalman filter represents the target state posterior in the form of Gaussian distribution and recursively estimates the mean and covariance of it. As a Gaussian implementation of the Bayes filter, the main components of the Kalman filter are to predict the current state using a linear target transaction model and to update the prediction based on the sensor measurement and the linear control input (if any). The one-step prediction of the state vector is given by .
The predicted error covariance matrix is given by .
Using the measured value   The innovation covariance matrix is .
Kalman gain is The state error covariance matrix is updated to are the best one-step predicted value and the covariance matrix of the predicted signal, respectively.   are the best-filtered value and the smoothed estimation covariance matrix, respectively.
Under ideal conditions, the filtered value   is the minimum mean square error matrix. Kalman filter can obtain the state's estimated value when performing filtering processing and perform error analysis on the obtained state error covariance, which is an important advantage of it.

Multiple Hypothesis Tracking for Multiple Target Tracking
The MHT algorithm builds a potential tracking hypothesis tree for each candidate target, calculates the belief of each track, and selects the most likely tracking combination. Since the entire tracking assumption is considered when calculating the probability, MHT is theoretically suitable for higherorder information such as long-term motion and appearance models. The MHT considers miss detections and target birth and death and assumes that the number and initial states of targets are unknown.

Tracking Tree Maintaining and Gain Gating
The first step of MHT is to create and update a tracking tree composed of a sequence of the time frame that holds multiple hypotheses generated by observations of targets. In each frame, a new tracking tree will be generated as a new target being detected. Meanwhile, an existing tracking tree will be updated if an existing target maintains being detected.
A gating step will then follow if the tracking hypothesis is within the observed gating range, meaning that a new observation is close to an existing track (determined by a distance d ) and is very likely to belong to it. The gating step predicts the location where the next observation is likely to appear to reduce the number of data association pairs. Elliptical gating is one of the most common gating techniques. We introduce the rectangular gating in this paper since it is more computationally efficient. The observation corresponding to the increasing branch of the tree is given by where the distance threshold th d determines the size of the gating area and l k x denotes the possible position of the l track at a time k, obtained by the Kalman filter. The rectangular gating uses the Mahalanobis distance to decide whether to use the newly predicted target to update a specific trajectory.

Best Global Hypothesis
Only the best global hypothesis is retained by calculating the tracking score, and the others are not.
The th l track's score at frame k is defined as follows: If   0 l S k  , a tracking hypothesis is more like a true target, while   0 l S k  means that it is more likely to be a false warning. So we can recursively calculate the best global hypothesis by where   l mot S k  and   l app S k  represent the increments of the two types of scores at the time k , respectively, D P and FA P represent the detection probability and false alarm probability, respectively.

Track Tree Cropping
The N -scan pruning method is one of the choices following the previous steps to control the number of hypotheses by limiting the depth of the trajectory tree. The N -scan pruning method forces the uncertainty generated at N the time to be resolved at k N  the time. When the depth of the trajectory tree is greater than N , the N -scan pruning method will search for the leaf node with the highest confidence in the trajectory tree and keep the root node branch of the leaf node with the highest confidence, then delete the remaining branches. We set the threshold th B such that when the number of branches exceeds th B , only the first th B branches are retained based on the tracking score. For each tracking hypothesis, a method of online training appearance model is introduced. The appearance model can be effectively learned by the least squares method of regularization, and only a little extra operation is required for each hypothesis branch. pruning. This can reduce unnecessary pruning and improve efficiency.

5.Examples
We conduct simulation using MATLAB to present examples both for single and multiple target tracking.
For both examples, we track targets from .mp4 videos which show fixed scenes with one or more objects moving within the scenes. We use function kalmanFilterForTracking() for single target tracking and function MotionBasedMultiObjectTrackingExample() for multiple target tracking, both in computer vision toolbox.

Single Target Tracking
We select to use the MATLAB computer vision toolbox video where a small ball moves from left to right on the floor, passing through a carton. Because of the friction on the ground, we choose a constant acceleration motion model. A paper box is set up in the middle of the ball's trajectory to verify whether the Kalman filter is still able to track the trajectory of the ball by the target motion model in the prediction step when the ball is unable to be detected. We set the initial position input to the position where the object was first detected. We also set the initial estimation error vector to a larger value because the initial state can be very noisy. After all, it is derived from a single detection. We select the value of measurement noise according to the accuracy of the camera. Setting the measurement noise to a larger value will result in a less accurate detector. The result is shown in Fig.1a. We can see that the ball is tracked throughout its trajectory correctly, even with the paper box blocking at the halfway. This proves that the Kalman filter can predict the target state using the motion model and recursively correct it over time. The tracking can recover with the prediction step even no detection is received for a while. It embodies the superiority of the Kalman filter algorithm in state estimation and accuracy for linear systems. Fig.1b presents a failed example of tracking a moving ball recorded in a video. The ball is no longer tracked as it's blocked from detected by an obstacle. This is due to the inaccuracy of the motion model and the confusion of extracting objects from the background with a similar color in the video. And shows that while using an inaccurate motion model. The object appears in a completely different position from the predicted position. When the object is released, it undergoes a constant deceleration due to resistance from the ground. Therefore, the constant acceleration model is a better choice. If the optimal motion model is not appropriate, the tracking results will be sub-optimal. Meanwhile, when there is a problem with the initial position we set, the initial center position of the object will deviate. When we give the initial estimation a significant error, the object's trajectory will find a serious deviation from being blocked by the obstacle to the end of the trajectory. This indicates that for the Kalman filter, a suitable parameter configuration plays an important role.
In short，the multi-target tracking we experimented with is mainly divided into two steps: Detect moving target in every frame and associating the detected target with the same target that was being tracked before. And our first step is divided into using the Gaussian mixture model for background subtraction to get the moving target, eliminating the noise in the foreground mask through morphological operations, and detecting the connected domain through blob analysis to obtain the corresponding moving target. Our second step is divided into using Kalman filter to calculate and predict the position of each trajectory in the next frame. Then calculate the Euclidean distance between the predicted trajectory position and each newly detected target, and measure The result is used as the loss function matrix. Then, the Hungarian matching algorithm is used to calculate the assigned/unassigned tracking/detection according to the threshold. And update tracking and detection, update assigned tracking to the assigned detection position of the current frame, delete unassigned tracking that reaches the threshold (continuous disappearance of multiple frames) and add unassigned detection to the track.

Multiple Target Tracking
We test multiple target tracking using an MHT-based algorithm in two scenes. The first one is on a flat road, with few people and simple background. Another scene is on a slope, with a more complicated environment and more people. In the two videos, we aim to track people, and most of them are moving at a constant speed. We make a comparison in this test between simple and complex scenarios. The multi-target tracking includes mainly two steps: detect moving target in every frame and associating the detected target with the same target that was being tracked before. Our first step is divided into using the Gaussian mixture model for background subtraction to get the moving target, eliminating the noise in the foreground mask through morphological operations, and detecting the connected domain through blob analysis to obtain the corresponding moving target. Our second step is divided into using the Kalman filter to calculate and predict the position of each trajectory in the next frame and calculating the Euclidean distance between the predicted trajectory position and each newly detected target. The result is evaluated with the loss function matrix, and then the Hungarian matching algorithm is used to calculate the assigned/unassigned tracking/detection according to the threshold. Finally, we update assigned tracking to the assigned detection position of the current frame, delete unassigned tracking that reaches the threshold (continuous disappearance of multiple frames) and add unassigned detection to the track. Fig.2a and Fig.2b demonstrate the results of tracking multiple people in videos. Most people are successfully tracked in both simple and complex environments even within a short appearance time and been marked with rectangles separately. This reflects that the MHT algorithm can track targets fast and reliably using Kalman filter with correct motion model characterization and match tracked target to new measurements as time moves forward. tracking, and the yellow rectangle is the recognition of the target contour. We also conduct some extra tests where the tracking of people is not very accurate, which will be more obvious in a complex environment compared to a simple environment. Fig.2d shows that two people in front of the street sign in the lower right corner are not detected. This may be because they lose detection as they are relatively small and standing still, which is not described by our selected motion model. In Fig.2c, two people are detected as one merged target. The reason is that the morphological operation and connectivity check are not too detailed. In Fig.2e, the man in white clothes in the lower left corner does not appear on the right edge because it has not reached the threshold of the minimum number of consecutive frames. The person in the far lower left of the picture is not detected because the object is too small, and the movement is very slow.
These examples indicate that the algorithm has limitations as this article is based on dynamic multitarget tracking. Thus, continuous multiple frames of static objects will be automatically classified as background. We also find that moving vehicles may block people from being tracked. To increase the reliability in using MHT in real-world scenarios, the morphological operation and connectivity check should be more detailed to be better divided. Meanwhile, for different objects, different eigenvalues should be given, and some methods should be adopted. It is used to divide different objects in foreground detection and only track the objects we are interested in.

6.Conclusion
This paper introduces the Kalman filter algorithm for single target tracking and the multiple hypothesis tracking (MHT), a Kalman filter-based algorithm incorporated with data association technique for multiple target tracking. Kalman filter predicts the mean and covariance of the Gaussian target state posterior using the target transition model and updates the sensor measurement recursively. MHT uses the Kalman filter to estimate the states of targets at each step and matches measurements to target tracks with a series of data association processes, including maintaining tracking trees, gating, and pruning. Experiments validate the efficacy of single and multiple target tracking using Kalman filter and MHT, respectively. It is also concluded that the morphological operation and connectivity check affect the tracking effect. The different feature values assigned to different objects may lead to various performances in detecting and tracking objects.