# Tracking Objects Based on Multiple Particle Filters for Multipart Combined Moving Directions Information

Authors: Ngo Duong Ha; Ikuko Shimizu; Pham The Bao
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

Object tracking is an important procedure in the computer vision field as it estimates the position, size, and state of an object along the video’s timeline. Although many algorithms were proposed with high accuracy, object tracking in diverse contexts is still a challenging problem. The paper presents some methods to track the movement of two types of objects: arbitrary objects and humans. Both problems estimate the state density function of an object using particle filters. For the videos of a static or relatively static camera, we adjusted the state transition model by integrating the movement direction of the object. Also, we propose that partitioning the object needs tracking. To track the human, we partitioned the human intoN parts and, then, tracked each part. During tracking, if a part deviated from the object, it was corrected by centering rotation, and the part was, then, combined with other parts.


---

## Body

## 1. Introduction

The object tracking in videos is a technique that has many applications in many fields. For example, in the biomedical field [1, 2], the object-tracking technique is applied to automatically track cells while they are born, duplicated, or as they move and die. Another example is the application of the technique in autopilot systems, where it is used to observe and track the vehicles around the driving car [3, 4] or footballer tracking [5–7]. A highly accurate vehicle-tracking program is an indispensable necessity for safety. Moreover, the tracking technology is usually combined with the identification and recognition systems to create a complete tactic for real-life applications.Tracking objects in video is difficult due to many challenges that all are needed to be considered and solved. The first challenge is that we do not know, in advance, the object that we need to track. There may be no information about that object. In the absence of information, the object description for the program script must be highly general. Another challenge is that the tracked object has heterogeneity in colors, which vary by each part of the object. For example, to track human movement, the head is characterized by the hair color (black and yellow), while the body and legs are described by the color of the shirt and pants that the person is wearing. Because of the challenges and difficulties mentioned above, no comprehensive tracking algorithm can be adopted for all problems.In this paper, we present the method to modify the state model according to the direction of predicting that an object appears in the same direction of motion with a higher probability. In addition, we explore the effectivity to track partially obscured objects by tracking its visible sections. To do this, we divided the object into multiple sections and tracked these sections independently. When some parts obscure the object, our approach should still successfully track the object movement. We also present the experimental particle filter model and present a suggestion for integrating information on the direction of the object’s movement, theN-particle filter model, to track each part then combines.The rest of the paper is organized as follows: The most relevant work that motivated this paper is reviewed in Section2. Section 3 describes, in detail, our method multiple particle filters for multipart combined moving directions information. Section 4 summarizes the results from our method. Section 5 is the discussion of our paper.


## 2. Related Work

The correlation filters approach is a powerful tool in digital signal processing [8, 9]. This algorithm class utilizes the properties of Fourier transform of turning convolution in the spatial domain into function multiplication in the Fourier domain [10–13]. The original idea of the correlation filter was to solve the problem of locating an object in an image. In other words, if the object of interest appears in the image, its position including the axis coordinates is determined. The tool to solve this problem is the average synthetic exact filter [10]. The next, correlation filter, is the Total Minimum Output Error, studied by Bolme et al. [13]. This tracking method is very powerful and can cope with situations such as changing light and changing the size and shape of objects.Aviden et al. [14] at Misubishi Electric Research Labs considered object tracking as the binary classification problem to distinguish background pixels and tracking-object pixels using the AdaBoost technique. The method’s idea was training weak classification functions to classify the background and object and, then, combine them to form a strong classification based on the Adaboost mechanism. But, the author realized that if an object is not in the rectangle form, pixels in the containing object rectangle but not in the object will be labeled as belonging to the object. These pixels are considered alien elements, while AdaBoost is sensitive to alien elements [15]. In addition, some other limitations of the approach are as follows: it has not solved the completely obstructed object’s situation in a long time and the featured space used in the algorithm does not yet utilize the spatial information of the image.The approach based on random process filtering has been studied for a long time in the field of mathematical statistics, and there have been many discovered impressive results [16–18]. Most of the algorithms based on this approach are based on the Bayes optimal solution for the hidden Markov filtering problem [19–21]. That means building a hidden Markov model plays a key role, and the model is more accurate; in fact, more Bayesian solutions accurately estimate the state of the object. The work in [20] uses the featured color histogram to construct a particle filter to track objects. The work in [22] uses gentle AdaBoost to construct an updated observation model over time.Recently, the Siamese network-based trackers have received significant attention for their well-balanced tracking accuracy and efficiency. These trackers formulate visual tracking as a cross-correlation problem and are expected to better leverage the merits of deep networks from end-to-end learning [23–30]. Bhat et al. [31] proposed a gradient-guided method to update the template. Li et al. [32] developed a discriminative model-prediction architecture for tracking.


## 3. Methodology

Problem 1.
Highlight that first frame coordinatesx1,y1,ω1,h1 are given and we need to infer object coordinates xk,yk,ωk,hk in the subsequent frames.
Filtering the statexk,yk,ωk,hk of the object in the next frames, we rely on the hidden Markov model theory with the construction of two models: state transitions and observations. The state transitions model in the studies is quite similar and are all Gaussian motion, and the main difference in the algorithms depends on the observed model. Using particle filters allows us to better handle color clutter in the background, as well as tracking completely obstructed objects.
The principle of the particle filter according to the Figure1, including 3 steps:Measurement: calculating the samples’ weights based on the observation at timenResampling: resampling or fine tuning (based on the threshold of the return weights) the samples to remove or adjust the samples in which the object positions are overmismatched at the current timePrediction: predicting the object status at timen + 1 based on the likelihoods from time n to the previous states
Based on the particle filter operating mechanism in Figure1, we present the approximate results of posterior density function pxk|y1:k at time k.
From the posterior distribution at timek – 1, pxk|y1:k−1, we calculate the prior distribution for the time k (without observing yk) by using Chapman–Kolmogorov equality [16], pxk|y1:k−1=∫pxk|xk−1.pxk−1|y1:k−1dxk−1, where pxk|xk−1 already exists in the state transition model and pxk−1|y1:k−1 is the posterior root of step k − 1.
After observingyk, we update the prior density function at the predicted step at the level k: pxk|y1:k=pyk|xk∗pxk|y1:k−1/pyk|y1:k−1, where pyk|xk already exists in the observation model and pxk|y1:k−1 is an a priori at the time k calculated in the previous step.
As a result, we obtain a weighted pattern representing the posterior density function at the timek: pxk|y1:k∼xkl,1/Zωk−1l∗pyk|xkll=1L.
When an object is in motion, it usually moves in a specific trajectory. Therefore, to predict the object’s location, we propose integrating the direction of motion, which will be discussed in detail in Section3.1. In addition, different parts of an object carry their distinctive characteristics of shape, color, light absorption, and reflection capacity. If we use a particle filter, it can yield false tracking results. Besides, if a part of the object has the same color and brightness level as any other object in the frame, the tracking may be distorted. To fix this problem, we propose to divide the object into many parts, each of which will have the same properties. We, then, track the movement of each part with the constraints that these parts move in the same direction and maintain similar area and shape.Figure 1
Demonstrate the operating mechanism of a particle filter.


### 3.1. Moving Direction Information

With the videos filtered out from the dataset in which the camera was relatively stable, we modified the state transition model in the hidden Markov model by integrating the direction of the object movement. This means that instead of using the Gaussian motion state model, we projected these Gauss functions into several different directions with different ratios before we made a new pattern. Because each object moves in a specific trajectory, the direction of the object's motion will remain constant for a certain period of time. Specifically, we consider the direction of motion as a separate component. At each assessment, we will update the direction of motion. We use this direction of motion to impact the particle filter at the prediction step, with the purpose that the particle filter will predict the object appearing in the same direction with higher probability.v⟶ is rotated an angle θ by multiplying the rotation matrix by v⟶ as follows:(1)vθ⟶=cosθ−sinθsinθcosθ.v⟶,where θ=0,π/4,−π/4,π/2,−π/2,3π/4,−3π/4,π.Figure2 depicts the probability distribution in the direction of the object's appearance, in which the red direction (in the direction of a1) is the predicted movement direction of the object, a1,a2,a3,a4,a5,a6,a7,a8 are real numbers in [0, 1], and ∑i=18ai=1. In the prediction step, we translate Ns⋅a1 particle by v⟶, Ns⋅a2 particle by vπ/4⟶,Ns⋅a3 particle by v−π/4⟶, Ns⋅a4 particle by vπ/2⟶, Ns⋅a5 particle by v−π/2⟶, Ns⋅a6 particle by v3π/4⟶, Ns⋅a7 particle by v−3π/4⟶, and Ns⋅a8 particle by vπ⟶.Figure 2
Distribute probabilities for moving directions.We propose the particle filter algorithm to integrate the direction of motion in Algorithm1.Algorithm 1:Particle filter integrated motion direction.
Input: Particles pf, Observation image, motion direction v⟶Output: New particles represent px,y,ω,h|observed image, estimating the state of the object in the observed image.Step 1:TranslateNs⋅a1 particles in pf by v⟶TranslateNs⋅a2 particles in pf by vπ/4⟶TranslateNs⋅a3 particles in pf by v−π/4⟶TranslateNs⋅a4 particles in pf by vπ/2⟶TranslateNs⋅a5 particles in pf by v−π/2⟶TranslateNs⋅a6 particles in pf by v3π/4⟶TranslateNs⋅a7 particles in pf by v−3π/4⟶TranslateNs⋅a8 particles in pf by vπ⟶Step 2:fori = 1 to Ns doBeginfor/∗ (withxi,yi,ωi,hi is i th particle) ∗/Getxnew∼xi+N0,σx2Getynew∼yi+N0,σy2Getωnew∼ωi+N0,σω2Calculatehnew=η∗ωnewCalculatelikelihood=pobservated image|xnew,ynew,ωnew,hnew by Algorithm 8Update weight ofi th particle: weighti=weighti∗likelihoodEndforStep 3:Calculate the totalsw=∑j=1Nsweighti+εfori = 1 to Ns doBeginforStandardize weightweighti=weighti+ε/swEndforStep 4: CalculateNeff=1/∑j=1Nsweightj2Step 5:ifNeff<Ns/2 thenxi,yi,ωi,hi,weightii=1Ns=RESAMPLExi,yi,ωi,hi,weightii=1NsEndifStep 6: Estimate the state of the object in thekth image by calculating the average of the new set of particles EstimatedStatus=∑i=1Nsweighti∗particlei


### 3.2. Multiple Particle Filters Model

#### 3.2.1. Multiparts of an Object

While considering the problem where the object shapes are less changing, if the object includes many parts with dissimilarity about the colors and contrast, using 1 particle filter for tracking will lead to incorrect tracking. Therefore, an object needs to separate each area with similar color, grayscale, and contrast inton parts, each part being tracked separately. In this way, the parts which affected by the environment and other object artifacts will cause incorrect position identification which will need to be adjusted. For example, a human object can be normally represented by a 3-partition structure as illustrated in Figure 3. This structure divides the human object based on the gray color changes among the black head, the white shirt body, and the black pants legs. The resulting human object will be divided into 3 parts with a border represented by a different gray level, each part using a particle filter to track and combine based on the best feature matching part.Figure 3
Some structure II partition objects.


#### 3.2.2. Build Model

The adjustment of deviated areas should take two steps:(i)
The center of the similar areas changed, which allowed the incorrect position of the similar areas to be adjusted accordingly to the correct position of the object(ii)
Size ratio of similar area allowed similar areas to scale the height to the height of the original objectThus, when one part of the object is obscured or similar to another, we can restore and track enough.


#### 3.2.3. Fine Tuning Parts

Once the anterior root of the object is defined, the object is defined inton parts in a structure H, as shown in Figure 3. We, then, used one particle filter to track each part S1,S2,…,Sn. At each time data point, each particle filter in the tracking area can diverge from each other. Therefore, a modification model is needed to correct this issue. We used the collected assessment data of each part to evaluate which tracked part behaves the best. We kept this best-tracked part fixed and applied the rotation algorithm to n − 1 other parts using the fixed part as the origin. The adjustment of N-particle filters when tracking an object in the frame time k is described below.Step 1: we calculate the rotation from the center of each section with the remainingn − 1 based on frame 0.(2)θij0=Si0,Sj0,wherei,j=1,n¯.For example, the angle of rotation from the center ofS20 compared to the rest of S10,S30 is the angle θ120,θ320 according to Figure 4(a).Step 2
: we suppose thatS1k,S2k,…,Snk are estimates and S10,S20,…,Sn0 are parts of the object in the original image. The distance is calculated as distancei=HOGSik−HOGSi02,i=1,n¯.However, because the division of parts may not be equal, to determine which is best, we multiply the coefficient by each distance and, then, compareK1∗distance1,K2∗distance2,…,Kn∗distancen. The smallest value is considered the best estimate. The best estimate is placed at the kth frame as Smink.Step 3
: when the best partSmink was selected, we performed the center rotation of the remaining n − 1 relative to the best part Smink with the rotation angle defined. The result is the new center coordinates of the n − 1 part.find the new center coordinates of the partSik with i=1,n−1¯ by calculating the center rotation of the section Sik compared to the center of the part Smink with the angle of rotation θimink−θimin0 as follows:(3)vSi′k⟶=cosθimink−θimin0−sinθimink−θimin0sinθimink−θimin0cosθimink−θimin0.v⟶Sik,wherev⟶Sik is the center coordinate of the part Sik and vSi′k⟶ is the new center coordinate of the part Sik after performing the rotation.For example, according to Figure4(b), the new center coordinates of S1k,S3k parts are found compared to S2k centers with the rotation angle θ12k−θ120 and θ32k−θ320 as(4)vS1′k⟶=cosθ12k−θ120−sinθ12k−θ120sinθ12k−θ120cosθ12k−θ120.v⟶S1k,vS3′k⟶=cosθ32k−θ320−sinθ32k−θ320sinθ32k−θ320cosθ32k−θ320.v⟶S3k.Step 4
: translating the particles progress of partSik with i=1,n−1¯ which differs from the best part Smink to the position of n-1 new part Si′k is created out through Step 3.Step 5: the sizes ofS1k,S2k,…,Snk parts are scaled according to the ratio of S10,S20,…,Sn0. That is, we will calculate hik and wik with i=1,n−1¯ of the sections S1k,S2k,…,Snk.First, we find the horizontal dimensions of eachSik part as follows: wik=∑i=1nwik/n with i=1,n−1¯.Next, we find the height dimensions of eachSik part as follows: hik=wik∗hi0/wi0.Step 6
: translating the particles progress of partSik with i=1,n−1¯ compared to the best part S2k with distance dimink.Figure 4
(a) The angleθ120,θ320 is the angle between the center S20 and the center S10,S30 based on Frame 0, and h10,h20,h30 are the heights of S10,S20,S30. (b) In the kth frame, the parts S1k,S3k have been skewed from S2k with angle θ12k,θ32k, and h1k,h2k,h3k are the heights of S1k,S2k,S3k.
(a)(b)For example, as shown in Figure4(b), the particles of S1k are translated towards the best part S2k with about d12k.We propose the multiparticle filter algorithm in Algorithms2 and 3.Algorithm 2:Particle filter for random processes xn,yn,ωn,hn.
Input:pf particles sample set (based on Algorithm 4), k th image (where k starts from the second image)Output: The new set of particles represents px,y,ω,h|imagek, estimate the state of the object in the k th image.Step 1:fori = 1 to Ns doBeginfor/∗(withxi,yi,ωi,hi is the i th particle)∗/Getxnew∼xi+N0,σx2Getynew∼yi+N0,σy2Getωnew∼ωi+N0,σω2Calculatehnew=η∗ωnewCalculatelikelihood=pimage2|xnew,ynew,ωnew,hnew by Algorithm 8Update weight fori th particle: weighti=weighti∗likelihoodEndforStep 2:Calculate sumsw=∑j=1Nsweighti+εfori = 1 to Ns doBeginforStandardize weight:weighti=weighti+ε/swEndforStep 3: CalculateNeff=1/∑j=1Nsweightj2Step 4:ifNeff<Ns/2 thenxi,yi,ωi,hi,weightii=1Ns=RESAMPLExi,yi,ωi,hi,weightii=1Ns use boostrapEndifStep 5: Estimate the state of the object in thek th image by calculating the average of the new set of particles EstimatedStatus=∑i=1Nsweighti∗particleiAlgorithm 3:(MultiPart).
Step 1: InitializeN-particles set pf1,pf2,…,pfnStep 2:fori = 1 to n doBeginforTakeDi patern for part i according to Algorithm 4.Train strong classificationFi=gentleAdaboostDi according to Algorithm 5.EndforStep 3:while The video is not over doBeginwhileGet observation photos obsfori = 1 to n doBeginforUse particle filter to estimate theith state according to Algorithm 1 or Algorithm 2Si∗=xiest,xiest,xiest,xiest=particlefilterobs,pfiMeasure the distance:distancei=HOGSi∗−HOGSi02EndforChoose the best parti0=argminK1∗distance1,K2∗distance2,…,Kn∗distancenUsing centeri0 part and structure H perform rotation of the remaining n − 1 centers.Tranlaten − 1 other particle set i0 to n − 1 has just been centered on i0.Scale the particle sets according to the structure ratioH.Translatingn − 1 set of other particles i0 toward the part i0.fori = 1 to n doBeginforTake a new sampleDi∗ based on the new section rotated from i0.Update strong classificationFi according to Algorithm 6EndforEndwhile


## 3.1. Moving Direction Information

With the videos filtered out from the dataset in which the camera was relatively stable, we modified the state transition model in the hidden Markov model by integrating the direction of the object movement. This means that instead of using the Gaussian motion state model, we projected these Gauss functions into several different directions with different ratios before we made a new pattern. Because each object moves in a specific trajectory, the direction of the object's motion will remain constant for a certain period of time. Specifically, we consider the direction of motion as a separate component. At each assessment, we will update the direction of motion. We use this direction of motion to impact the particle filter at the prediction step, with the purpose that the particle filter will predict the object appearing in the same direction with higher probability.v⟶ is rotated an angle θ by multiplying the rotation matrix by v⟶ as follows:(1)vθ⟶=cosθ−sinθsinθcosθ.v⟶,where θ=0,π/4,−π/4,π/2,−π/2,3π/4,−3π/4,π.Figure2 depicts the probability distribution in the direction of the object's appearance, in which the red direction (in the direction of a1) is the predicted movement direction of the object, a1,a2,a3,a4,a5,a6,a7,a8 are real numbers in [0, 1], and ∑i=18ai=1. In the prediction step, we translate Ns⋅a1 particle by v⟶, Ns⋅a2 particle by vπ/4⟶,Ns⋅a3 particle by v−π/4⟶, Ns⋅a4 particle by vπ/2⟶, Ns⋅a5 particle by v−π/2⟶, Ns⋅a6 particle by v3π/4⟶, Ns⋅a7 particle by v−3π/4⟶, and Ns⋅a8 particle by vπ⟶.Figure 2
Distribute probabilities for moving directions.We propose the particle filter algorithm to integrate the direction of motion in Algorithm1.Algorithm 1:Particle filter integrated motion direction.
Input: Particles pf, Observation image, motion direction v⟶Output: New particles represent px,y,ω,h|observed image, estimating the state of the object in the observed image.Step 1:TranslateNs⋅a1 particles in pf by v⟶TranslateNs⋅a2 particles in pf by vπ/4⟶TranslateNs⋅a3 particles in pf by v−π/4⟶TranslateNs⋅a4 particles in pf by vπ/2⟶TranslateNs⋅a5 particles in pf by v−π/2⟶TranslateNs⋅a6 particles in pf by v3π/4⟶TranslateNs⋅a7 particles in pf by v−3π/4⟶TranslateNs⋅a8 particles in pf by vπ⟶Step 2:fori = 1 to Ns doBeginfor/∗ (withxi,yi,ωi,hi is i th particle) ∗/Getxnew∼xi+N0,σx2Getynew∼yi+N0,σy2Getωnew∼ωi+N0,σω2Calculatehnew=η∗ωnewCalculatelikelihood=pobservated image|xnew,ynew,ωnew,hnew by Algorithm 8Update weight ofi th particle: weighti=weighti∗likelihoodEndforStep 3:Calculate the totalsw=∑j=1Nsweighti+εfori = 1 to Ns doBeginforStandardize weightweighti=weighti+ε/swEndforStep 4: CalculateNeff=1/∑j=1Nsweightj2Step 5:ifNeff<Ns/2 thenxi,yi,ωi,hi,weightii=1Ns=RESAMPLExi,yi,ωi,hi,weightii=1NsEndifStep 6: Estimate the state of the object in thekth image by calculating the average of the new set of particles EstimatedStatus=∑i=1Nsweighti∗particlei


## 3.2. Multiple Particle Filters Model

### 3.2.1. Multiparts of an Object

While considering the problem where the object shapes are less changing, if the object includes many parts with dissimilarity about the colors and contrast, using 1 particle filter for tracking will lead to incorrect tracking. Therefore, an object needs to separate each area with similar color, grayscale, and contrast inton parts, each part being tracked separately. In this way, the parts which affected by the environment and other object artifacts will cause incorrect position identification which will need to be adjusted. For example, a human object can be normally represented by a 3-partition structure as illustrated in Figure 3. This structure divides the human object based on the gray color changes among the black head, the white shirt body, and the black pants legs. The resulting human object will be divided into 3 parts with a border represented by a different gray level, each part using a particle filter to track and combine based on the best feature matching part.Figure 3
Some structure II partition objects.


### 3.2.2. Build Model

The adjustment of deviated areas should take two steps:(i)
The center of the similar areas changed, which allowed the incorrect position of the similar areas to be adjusted accordingly to the correct position of the object(ii)
Size ratio of similar area allowed similar areas to scale the height to the height of the original objectThus, when one part of the object is obscured or similar to another, we can restore and track enough.


### 3.2.3. Fine Tuning Parts

Once the anterior root of the object is defined, the object is defined inton parts in a structure H, as shown in Figure 3. We, then, used one particle filter to track each part S1,S2,…,Sn. At each time data point, each particle filter in the tracking area can diverge from each other. Therefore, a modification model is needed to correct this issue. We used the collected assessment data of each part to evaluate which tracked part behaves the best. We kept this best-tracked part fixed and applied the rotation algorithm to n − 1 other parts using the fixed part as the origin. The adjustment of N-particle filters when tracking an object in the frame time k is described below.Step 1: we calculate the rotation from the center of each section with the remainingn − 1 based on frame 0.(2)θij0=Si0,Sj0,wherei,j=1,n¯.For example, the angle of rotation from the center ofS20 compared to the rest of S10,S30 is the angle θ120,θ320 according to Figure 4(a).Step 2
: we suppose thatS1k,S2k,…,Snk are estimates and S10,S20,…,Sn0 are parts of the object in the original image. The distance is calculated as distancei=HOGSik−HOGSi02,i=1,n¯.However, because the division of parts may not be equal, to determine which is best, we multiply the coefficient by each distance and, then, compareK1∗distance1,K2∗distance2,…,Kn∗distancen. The smallest value is considered the best estimate. The best estimate is placed at the kth frame as Smink.Step 3
: when the best partSmink was selected, we performed the center rotation of the remaining n − 1 relative to the best part Smink with the rotation angle defined. The result is the new center coordinates of the n − 1 part.find the new center coordinates of the partSik with i=1,n−1¯ by calculating the center rotation of the section Sik compared to the center of the part Smink with the angle of rotation θimink−θimin0 as follows:(3)vSi′k⟶=cosθimink−θimin0−sinθimink−θimin0sinθimink−θimin0cosθimink−θimin0.v⟶Sik,wherev⟶Sik is the center coordinate of the part Sik and vSi′k⟶ is the new center coordinate of the part Sik after performing the rotation.For example, according to Figure4(b), the new center coordinates of S1k,S3k parts are found compared to S2k centers with the rotation angle θ12k−θ120 and θ32k−θ320 as(4)vS1′k⟶=cosθ12k−θ120−sinθ12k−θ120sinθ12k−θ120cosθ12k−θ120.v⟶S1k,vS3′k⟶=cosθ32k−θ320−sinθ32k−θ320sinθ32k−θ320cosθ32k−θ320.v⟶S3k.Step 4
: translating the particles progress of partSik with i=1,n−1¯ which differs from the best part Smink to the position of n-1 new part Si′k is created out through Step 3.Step 5: the sizes ofS1k,S2k,…,Snk parts are scaled according to the ratio of S10,S20,…,Sn0. That is, we will calculate hik and wik with i=1,n−1¯ of the sections S1k,S2k,…,Snk.First, we find the horizontal dimensions of eachSik part as follows: wik=∑i=1nwik/n with i=1,n−1¯.Next, we find the height dimensions of eachSik part as follows: hik=wik∗hi0/wi0.Step 6
: translating the particles progress of partSik with i=1,n−1¯ compared to the best part S2k with distance dimink.Figure 4
(a) The angleθ120,θ320 is the angle between the center S20 and the center S10,S30 based on Frame 0, and h10,h20,h30 are the heights of S10,S20,S30. (b) In the kth frame, the parts S1k,S3k have been skewed from S2k with angle θ12k,θ32k, and h1k,h2k,h3k are the heights of S1k,S2k,S3k.
(a)(b)For example, as shown in Figure4(b), the particles of S1k are translated towards the best part S2k with about d12k.We propose the multiparticle filter algorithm in Algorithms2 and 3.Algorithm 2:Particle filter for random processes xn,yn,ωn,hn.
Input:pf particles sample set (based on Algorithm 4), k th image (where k starts from the second image)Output: The new set of particles represents px,y,ω,h|imagek, estimate the state of the object in the k th image.Step 1:fori = 1 to Ns doBeginfor/∗(withxi,yi,ωi,hi is the i th particle)∗/Getxnew∼xi+N0,σx2Getynew∼yi+N0,σy2Getωnew∼ωi+N0,σω2Calculatehnew=η∗ωnewCalculatelikelihood=pimage2|xnew,ynew,ωnew,hnew by Algorithm 8Update weight fori th particle: weighti=weighti∗likelihoodEndforStep 2:Calculate sumsw=∑j=1Nsweighti+εfori = 1 to Ns doBeginforStandardize weight:weighti=weighti+ε/swEndforStep 3: CalculateNeff=1/∑j=1Nsweightj2Step 4:ifNeff<Ns/2 thenxi,yi,ωi,hi,weightii=1Ns=RESAMPLExi,yi,ωi,hi,weightii=1Ns use boostrapEndifStep 5: Estimate the state of the object in thek th image by calculating the average of the new set of particles EstimatedStatus=∑i=1Nsweighti∗particleiAlgorithm 3:(MultiPart).
Step 1: InitializeN-particles set pf1,pf2,…,pfnStep 2:fori = 1 to n doBeginforTakeDi patern for part i according to Algorithm 4.Train strong classificationFi=gentleAdaboostDi according to Algorithm 5.EndforStep 3:while The video is not over doBeginwhileGet observation photos obsfori = 1 to n doBeginforUse particle filter to estimate theith state according to Algorithm 1 or Algorithm 2Si∗=xiest,xiest,xiest,xiest=particlefilterobs,pfiMeasure the distance:distancei=HOGSi∗−HOGSi02EndforChoose the best parti0=argminK1∗distance1,K2∗distance2,…,Kn∗distancenUsing centeri0 part and structure H perform rotation of the remaining n − 1 centers.Tranlaten − 1 other particle set i0 to n − 1 has just been centered on i0.Scale the particle sets according to the structure ratioH.Translatingn − 1 set of other particles i0 toward the part i0.fori = 1 to n doBeginforTake a new sampleDi∗ based on the new section rotated from i0.Update strong classificationFi according to Algorithm 6EndforEndwhile


## 3.2.1. Multiparts of an Object

While considering the problem where the object shapes are less changing, if the object includes many parts with dissimilarity about the colors and contrast, using 1 particle filter for tracking will lead to incorrect tracking. Therefore, an object needs to separate each area with similar color, grayscale, and contrast inton parts, each part being tracked separately. In this way, the parts which affected by the environment and other object artifacts will cause incorrect position identification which will need to be adjusted. For example, a human object can be normally represented by a 3-partition structure as illustrated in Figure 3. This structure divides the human object based on the gray color changes among the black head, the white shirt body, and the black pants legs. The resulting human object will be divided into 3 parts with a border represented by a different gray level, each part using a particle filter to track and combine based on the best feature matching part.Figure 3
Some structure II partition objects.


## 3.2.2. Build Model

The adjustment of deviated areas should take two steps:(i)
The center of the similar areas changed, which allowed the incorrect position of the similar areas to be adjusted accordingly to the correct position of the object(ii)
Size ratio of similar area allowed similar areas to scale the height to the height of the original objectThus, when one part of the object is obscured or similar to another, we can restore and track enough.


## 3.2.3. Fine Tuning Parts

Once the anterior root of the object is defined, the object is defined inton parts in a structure H, as shown in Figure 3. We, then, used one particle filter to track each part S1,S2,…,Sn. At each time data point, each particle filter in the tracking area can diverge from each other. Therefore, a modification model is needed to correct this issue. We used the collected assessment data of each part to evaluate which tracked part behaves the best. We kept this best-tracked part fixed and applied the rotation algorithm to n − 1 other parts using the fixed part as the origin. The adjustment of N-particle filters when tracking an object in the frame time k is described below.Step 1: we calculate the rotation from the center of each section with the remainingn − 1 based on frame 0.(2)θij0=Si0,Sj0,wherei,j=1,n¯.For example, the angle of rotation from the center ofS20 compared to the rest of S10,S30 is the angle θ120,θ320 according to Figure 4(a).Step 2
: we suppose thatS1k,S2k,…,Snk are estimates and S10,S20,…,Sn0 are parts of the object in the original image. The distance is calculated as distancei=HOGSik−HOGSi02,i=1,n¯.However, because the division of parts may not be equal, to determine which is best, we multiply the coefficient by each distance and, then, compareK1∗distance1,K2∗distance2,…,Kn∗distancen. The smallest value is considered the best estimate. The best estimate is placed at the kth frame as Smink.Step 3
: when the best partSmink was selected, we performed the center rotation of the remaining n − 1 relative to the best part Smink with the rotation angle defined. The result is the new center coordinates of the n − 1 part.find the new center coordinates of the partSik with i=1,n−1¯ by calculating the center rotation of the section Sik compared to the center of the part Smink with the angle of rotation θimink−θimin0 as follows:(3)vSi′k⟶=cosθimink−θimin0−sinθimink−θimin0sinθimink−θimin0cosθimink−θimin0.v⟶Sik,wherev⟶Sik is the center coordinate of the part Sik and vSi′k⟶ is the new center coordinate of the part Sik after performing the rotation.For example, according to Figure4(b), the new center coordinates of S1k,S3k parts are found compared to S2k centers with the rotation angle θ12k−θ120 and θ32k−θ320 as(4)vS1′k⟶=cosθ12k−θ120−sinθ12k−θ120sinθ12k−θ120cosθ12k−θ120.v⟶S1k,vS3′k⟶=cosθ32k−θ320−sinθ32k−θ320sinθ32k−θ320cosθ32k−θ320.v⟶S3k.Step 4
: translating the particles progress of partSik with i=1,n−1¯ which differs from the best part Smink to the position of n-1 new part Si′k is created out through Step 3.Step 5: the sizes ofS1k,S2k,…,Snk parts are scaled according to the ratio of S10,S20,…,Sn0. That is, we will calculate hik and wik with i=1,n−1¯ of the sections S1k,S2k,…,Snk.First, we find the horizontal dimensions of eachSik part as follows: wik=∑i=1nwik/n with i=1,n−1¯.Next, we find the height dimensions of eachSik part as follows: hik=wik∗hi0/wi0.Step 6
: translating the particles progress of partSik with i=1,n−1¯ compared to the best part S2k with distance dimink.Figure 4
(a) The angleθ120,θ320 is the angle between the center S20 and the center S10,S30 based on Frame 0, and h10,h20,h30 are the heights of S10,S20,S30. (b) In the kth frame, the parts S1k,S3k have been skewed from S2k with angle θ12k,θ32k, and h1k,h2k,h3k are the heights of S1k,S2k,S3k.
(a)(b)For example, as shown in Figure4(b), the particles of S1k are translated towards the best part S2k with about d12k.We propose the multiparticle filter algorithm in Algorithms2 and 3.Algorithm 2:Particle filter for random processes xn,yn,ωn,hn.
Input:pf particles sample set (based on Algorithm 4), k th image (where k starts from the second image)Output: The new set of particles represents px,y,ω,h|imagek, estimate the state of the object in the k th image.Step 1:fori = 1 to Ns doBeginfor/∗(withxi,yi,ωi,hi is the i th particle)∗/Getxnew∼xi+N0,σx2Getynew∼yi+N0,σy2Getωnew∼ωi+N0,σω2Calculatehnew=η∗ωnewCalculatelikelihood=pimage2|xnew,ynew,ωnew,hnew by Algorithm 8Update weight fori th particle: weighti=weighti∗likelihoodEndforStep 2:Calculate sumsw=∑j=1Nsweighti+εfori = 1 to Ns doBeginforStandardize weight:weighti=weighti+ε/swEndforStep 3: CalculateNeff=1/∑j=1Nsweightj2Step 4:ifNeff<Ns/2 thenxi,yi,ωi,hi,weightii=1Ns=RESAMPLExi,yi,ωi,hi,weightii=1Ns use boostrapEndifStep 5: Estimate the state of the object in thek th image by calculating the average of the new set of particles EstimatedStatus=∑i=1Nsweighti∗particleiAlgorithm 3:(MultiPart).
Step 1: InitializeN-particles set pf1,pf2,…,pfnStep 2:fori = 1 to n doBeginforTakeDi patern for part i according to Algorithm 4.Train strong classificationFi=gentleAdaboostDi according to Algorithm 5.EndforStep 3:while The video is not over doBeginwhileGet observation photos obsfori = 1 to n doBeginforUse particle filter to estimate theith state according to Algorithm 1 or Algorithm 2Si∗=xiest,xiest,xiest,xiest=particlefilterobs,pfiMeasure the distance:distancei=HOGSi∗−HOGSi02EndforChoose the best parti0=argminK1∗distance1,K2∗distance2,…,Kn∗distancenUsing centeri0 part and structure H perform rotation of the remaining n − 1 centers.Tranlaten − 1 other particle set i0 to n − 1 has just been centered on i0.Scale the particle sets according to the structure ratioH.Translatingn − 1 set of other particles i0 toward the part i0.fori = 1 to n doBeginforTake a new sampleDi∗ based on the new section rotated from i0.Update strong classificationFi according to Algorithm 6EndforEndwhile


## 4. Experiment

### 4.1. Environment

Installation environment: we experiment on computers using the Windows 10 Pro 64 bit, RAM 8 GB, Chip Intel Core (TM) 5i-3210M CPU @ 2.5GHz; Matlab programming language version R2016a.


### 4.2. Data Set

In 2013, Wu et al. [33] gathered many video sources related to the track and proceeded to create ground truth for these videos to form the TB-100 dataset. Because the TB-100 is a compilation of data from many sources, the context of the videos is also very different and diverse in attributes such as the type of objects to track, color or black-and-white videos, and still or dynamic cameras. The video datasets used to support the findings of this study have been deposited in http://www.visual-tracking.net.Challenges in the dataset include the following:IV- illumination variation: the brightness of the subject varies significantlySV- scale variation: the ratio of the rectangle containing the first image object to the current image is out of range1/ts,ts,ts>1ts=2OCC- occlusion: the object is partially or completely obscuredDEF- deformation: nonsolid objects that change shapeMB- motion blur: the subject is blurry due to camera movementFM- fast motion: groundtruth motion is greater thantm pixels (tm = 20)IPR- in-plane rotation: objects rotate in the image domainOPR- out-of-plane rotation: object out of the image domainOV- out of view: part of the object out of the image domainBC- background clutters: the background near the object has the same color or line as the objectLR- low resolution: the number of pixels in the rectangle that contains the object (considering ground truth) is less thantr (tr = 400)The abovementioned challenges are distributed in the data set, which is shown in Figure5.Figure 5
(a) Distribution of the properties throughout the data set. (b) Distribution of attributes in videos that have OCC attributes.
(a)(b)


### 4.3. Evaluating

We use the evaluation criteria presented at the site [33] to evaluate the tracking algorithm.Method 1 (R1): evaluation based on the Euclid distance (precision plot): we measure the distance Euclid d from the estimated center of the algorithm to the actual center of the object (ground truth), if d is less than or equal to a threshold t0. The view is successful according to Figure 6(a).Method 2 (R2): evaluation based on levels of overlap (success plot): the number of overlapping points is defined as =rt∩ra/rt∪ra, in which rt is the bounding rectangle determined by the algorithm and ra is the ground truth rectangle according to Figure 6(b).Figure 6
(a) Euclid distance measurement. (b) Measure of the level of overlap.
(a)(b)We calculate the ratio ofR1,R2 by (the number of successful images/the total number of images of images).


### 4.4. Result

The results of tracking people with the camera do not fluctuate much, the rotation angle is conserved, and the proportions on the body of people and people are not too small.We namedProgram 1 as MultiPart3 using the MultiPart algorithm by dividing the object into 3 parts in a ratio of 1 : 5 : 3; Program 2 is MultiPart3_direction using the MultiPart algorithm to calculate the direction of moving objects by dividing the object into 3 parts in a ratio of 1 : 5 : 3; Program 3 is MultiPart2 using the MultiPart algorithm by dividing the object into 2 parts in a ratio of 5 : 3; Program 4 is MultiPart2_direction using the MultiPart algorithm to calculate the direction of object movement by dividing the object into 2 parts in a ratio of 5 : 3. The abovementioned five programs compared with DiMP algorithms [31] and GradNet [32] are shown in Table 1 and Figure 7.Table 1
Algorithm results of DiMP, GradNet, MultiPart3, MultiPart3_direction, MultiPart2, and MultiPart2_direction.
VideoDiMP (%)GradNet (%)MultiPart2 (%)MultiPart2_direction (%)MultiPart3 (%)MultiPart3 direction (%)R1R2R1R2R1R2R1R2R1R2R1R2Crossing10010010010010098.310093.3100100100100Dancer93.310092.498.295.188.991.188.483.186.264.974.2Dancer297.399.310010077.359.047.357.310098.796.096.7David390.990.910010073.081.464.367.980.684.592.592.5Human81001008.67.010089.110099.210081.310089.8Walking10099.810099.310098.510098.899.899.010099.3Walking242.239.610010010010010010098.896.010010089.189.985.986.492.287.986.186.494.692.293.393.2Figure 7
Algorithm evaluation chart.The MultiPart2 algorithm uses 2 particle filters in a ratio of 5 : 3 to track, allowing a large portion of the head (head and body) to be more informative, less changing over time, and “denser” than the leg. The average accuracy result (R1 = 92.2%, R2 = 87.9%) is slightly larger than that of the GradNet algorithm (R1 = 85.9%, R2 = 86.3%). With the abovementioned results, we can see that the tracking part has much information for good average results compared with the object tracking. However, for data (Dancer và Dancer2) that have a tracking object who wears a skirt or long skirt covering feet, tracking using 2 particle filters at a ratio of 5 : 3 gives a low result compared to an object trace. By tracking, the object intact in this case is best.For the videos mentioned above, the MultiPart3 algorithm divides 3 parts in a 1 : 5 : 3 ratio, after each image has adjustments of the parts according to the rotation technique based on the structureH to bring the wrong parts to the right area of ground truth. The results of the MultiPart3 algorithm (R1 = 94.6% and R2 = 92.2%) are better than those of DiMP (R1 = 89.1%, R2 = 89.9%) and GradNet (R1 = 85.9%, R2 = 86.3%). In addition, the algorithm MultiPart3_direction is the combination of the object movement direction for average accuracy results (R1 = 93.3%, R2 = 93.2%), and this result is better than DiMP and GradNet algorithm’s result. The MultiPart3_direction algorithm approximates the average accuracy result with the MultiPart3 algorithm because the dancer data have the human object that jumps up and down suddenly and the refined data take a number of frames so that the determination of the motion direction is wrong.


## 4.1. Environment

Installation environment: we experiment on computers using the Windows 10 Pro 64 bit, RAM 8 GB, Chip Intel Core (TM) 5i-3210M CPU @ 2.5GHz; Matlab programming language version R2016a.


## 4.2. Data Set

In 2013, Wu et al. [33] gathered many video sources related to the track and proceeded to create ground truth for these videos to form the TB-100 dataset. Because the TB-100 is a compilation of data from many sources, the context of the videos is also very different and diverse in attributes such as the type of objects to track, color or black-and-white videos, and still or dynamic cameras. The video datasets used to support the findings of this study have been deposited in http://www.visual-tracking.net.Challenges in the dataset include the following:IV- illumination variation: the brightness of the subject varies significantlySV- scale variation: the ratio of the rectangle containing the first image object to the current image is out of range1/ts,ts,ts>1ts=2OCC- occlusion: the object is partially or completely obscuredDEF- deformation: nonsolid objects that change shapeMB- motion blur: the subject is blurry due to camera movementFM- fast motion: groundtruth motion is greater thantm pixels (tm = 20)IPR- in-plane rotation: objects rotate in the image domainOPR- out-of-plane rotation: object out of the image domainOV- out of view: part of the object out of the image domainBC- background clutters: the background near the object has the same color or line as the objectLR- low resolution: the number of pixels in the rectangle that contains the object (considering ground truth) is less thantr (tr = 400)The abovementioned challenges are distributed in the data set, which is shown in Figure5.Figure 5
(a) Distribution of the properties throughout the data set. (b) Distribution of attributes in videos that have OCC attributes.
(a)(b)


## 4.3. Evaluating

We use the evaluation criteria presented at the site [33] to evaluate the tracking algorithm.Method 1 (R1): evaluation based on the Euclid distance (precision plot): we measure the distance Euclid d from the estimated center of the algorithm to the actual center of the object (ground truth), if d is less than or equal to a threshold t0. The view is successful according to Figure 6(a).Method 2 (R2): evaluation based on levels of overlap (success plot): the number of overlapping points is defined as =rt∩ra/rt∪ra, in which rt is the bounding rectangle determined by the algorithm and ra is the ground truth rectangle according to Figure 6(b).Figure 6
(a) Euclid distance measurement. (b) Measure of the level of overlap.
(a)(b)We calculate the ratio ofR1,R2 by (the number of successful images/the total number of images of images).


## 4.4. Result

The results of tracking people with the camera do not fluctuate much, the rotation angle is conserved, and the proportions on the body of people and people are not too small.We namedProgram 1 as MultiPart3 using the MultiPart algorithm by dividing the object into 3 parts in a ratio of 1 : 5 : 3; Program 2 is MultiPart3_direction using the MultiPart algorithm to calculate the direction of moving objects by dividing the object into 3 parts in a ratio of 1 : 5 : 3; Program 3 is MultiPart2 using the MultiPart algorithm by dividing the object into 2 parts in a ratio of 5 : 3; Program 4 is MultiPart2_direction using the MultiPart algorithm to calculate the direction of object movement by dividing the object into 2 parts in a ratio of 5 : 3. The abovementioned five programs compared with DiMP algorithms [31] and GradNet [32] are shown in Table 1 and Figure 7.Table 1
Algorithm results of DiMP, GradNet, MultiPart3, MultiPart3_direction, MultiPart2, and MultiPart2_direction.
VideoDiMP (%)GradNet (%)MultiPart2 (%)MultiPart2_direction (%)MultiPart3 (%)MultiPart3 direction (%)R1R2R1R2R1R2R1R2R1R2R1R2Crossing10010010010010098.310093.3100100100100Dancer93.310092.498.295.188.991.188.483.186.264.974.2Dancer297.399.310010077.359.047.357.310098.796.096.7David390.990.910010073.081.464.367.980.684.592.592.5Human81001008.67.010089.110099.210081.310089.8Walking10099.810099.310098.510098.899.899.010099.3Walking242.239.610010010010010010098.896.010010089.189.985.986.492.287.986.186.494.692.293.393.2Figure 7
Algorithm evaluation chart.The MultiPart2 algorithm uses 2 particle filters in a ratio of 5 : 3 to track, allowing a large portion of the head (head and body) to be more informative, less changing over time, and “denser” than the leg. The average accuracy result (R1 = 92.2%, R2 = 87.9%) is slightly larger than that of the GradNet algorithm (R1 = 85.9%, R2 = 86.3%). With the abovementioned results, we can see that the tracking part has much information for good average results compared with the object tracking. However, for data (Dancer và Dancer2) that have a tracking object who wears a skirt or long skirt covering feet, tracking using 2 particle filters at a ratio of 5 : 3 gives a low result compared to an object trace. By tracking, the object intact in this case is best.For the videos mentioned above, the MultiPart3 algorithm divides 3 parts in a 1 : 5 : 3 ratio, after each image has adjustments of the parts according to the rotation technique based on the structureH to bring the wrong parts to the right area of ground truth. The results of the MultiPart3 algorithm (R1 = 94.6% and R2 = 92.2%) are better than those of DiMP (R1 = 89.1%, R2 = 89.9%) and GradNet (R1 = 85.9%, R2 = 86.3%). In addition, the algorithm MultiPart3_direction is the combination of the object movement direction for average accuracy results (R1 = 93.3%, R2 = 93.2%), and this result is better than DiMP and GradNet algorithm’s result. The MultiPart3_direction algorithm approximates the average accuracy result with the MultiPart3 algorithm because the dancer data have the human object that jumps up and down suddenly and the refined data take a number of frames so that the determination of the motion direction is wrong.


## 5. Conclusions

This paper presented several methods for object tracking in the videos mainly related to particle filters. To solve the general problem, we built a hidden Markov model and applied particle filters. For tracking human videos in normal condition where the human scale is preserved, we used 3 particle filters to track each part of the body or track the part of the body containing the most information, which will, then, infer to the whole body. Experimental results show dividing the object into (n + m) parts, even when n parts of objects are partially obscured and the remaining m parts are tracked normally and do not affect the tracking of the subject in the video.The development direction of this paper is to change the observation model. We found that the gentle Adaboost training process is time consuming. However, the algorithms using correlation filters have the advantage of being fast and highly accurate. For future studies, we suggest integrating the correlation filters into the observation model to shorten the execution time. In addition, we are planning to study parts of the traced objects in parallel to shorten the execution time.



---

*Source: 8839725-2020-12-17.xml*