Semantic segmentation of trajectories with agent models
Daisuke Ogawa Toru Tamaki Bisser Raytchev Kazufumi Kaneda


















































Semantic segmentation of trajectories with agent models
    
Daisuke Ogawa, Toru Tamaki, Bisser Raytchev, Kazufumi Kaneda

Hiroshima University

Higashi-Hiroshima, Hiroshima 739-8527 Japan

















    December 30, 2023
=====================================================================================================================================================









In many cases, such as trajectories clustering and classification, we often divide a trajectory into segments as  preprocessing.
In this paper, we propose a trajectory semantic segmentation method based on learned behavior models.
In the proposed method, we learn some behavior models from video sequences.
Next, using learned behavior models and a hidden Markov model, we segment a trajectory into semantic segments.
Comparing with the Ramer-Douglas-Peucker algorithm, we show the effectiveness of the proposed method.























§ INTRODUCTION


Analyzing behavior and trajectories of pedestrians captured by video cameras are
one of important topics in computer vision, which has been widely studied over the decades.
In such studies, segmentation of trajectories often is performed for reducing computation cost
and extracting local information. There are three typical approaches <cit.>:

 
  * Temporal segmentation: splitting a trajectory at points where two observed locations are temporally away from each other .
 
  * Shape-based segmentation: splitting at points of larger curvature indicating that the target may change its direction at that point. This is used for simplifying the shape of trajectories, and the Ramer-Douglas-Peucker algorithm <cit.> is a famous approach.
 
  * Semantic segmentation: dividing a whole trajectory into semantically meaningful segments, and many methods have been proposed for different tasks <cit.>.

In this paper we focus on the third type, semantic segmentation, of trajectories based on models of human behavior (or agents). 
It would be very beneficial if we could have segments related to behavior, however no segmentation methods of trajectories have been proposed for the task of human behavior analysis.
Our proposed method first estimates agent models by Mixture model of Dynamic pedestrian Agents (MDA) <cit.>, then segment trajectories with the learned agent models by using Hidden Markov Models (HMM) <cit.>.




§ RELATED WORK


The Ramer-Douglas-Peucker algorithm <cit.> is often used for
trajectory simplification. It segments a trajectory while preserving important points in order to
keep the trajectory shape as much as possible. First the start and end points of a trajectory are kept.
Next it finds the most far point away from the line between two kept points,
and keep it if the distance is larger than threshold ϵ.
This process iterates recursively until no further points are kept.
Finally, all of the kept points are used to segment the trajectory.
This method is simple and preserve the rough shape of the trajectory,
while an appropriate value of ϵ has to be specified.


Task oriented methods are also proposed.
Yuan et al. <cit.> propose a system called T-Finder, which recommends
to taxi drivers places where as many potential customers exist as possible,
and to end users places where taxis are expected to be find.
To this end, they estimate taxi locations based on taxi driving trajectories
and segments the trajectories as pre-processing.
Lee et al. <cit.> proposes TRAOD, an algorithm for finding outliers in trajectories
based on segmentation by using the Minimum Description Length (MDL) principle.
Zheng et al. estimates Transportation Mode <cit.>
such as walk, car, bus, and bike used for semantic segmentation in terms of a mode of transportation.

In contrast, our proposed method uses semantic human behavior models, called agent models,
learned from pedestrian trajectories in videos.





§ MIXTURE MODEL OF DYNAMIC PEDESTRIAN AGENTS



In this section, we briefly describe 
Mixture model of Dynamic pedestrian Agents (MDA) <cit.> proposed by Zhou et al.
for learning behavior models, or agents.
MDA is a hierarchical Bayesian model that represents
pedestrian trajectories by a mixture model of dynamics and belief.
By a modified Kalman filter handling missing observations in trajectories,
and an iterative EM algorithm, parameters of dynamics and belief of each agents
are estimated.
Finally, trajectories are clustered based on the estimated agents.
In our proposed method, we use the estimated agents for segmentation of trajectories, instead of clustering.

y
x
ḇ
μμ



 §.§ Formulation


Let _t ∈ R^2 be two-dimensional coordinates of a pedestrian at time t,
and _t ∈ R^2 be the corresponding state
of the following linear dynamic system;

    _t    ∼ P(_t | _t-1) = N(_t | A _t-1 + ,̱ Q) 
    _t    ∼ P(_t | _t) = N(_t | _t, R) ,

where 
N(·) represents a normal distribution with covariance matrices Q, R ∈ R^2× 2,
and A ∈ R^2× 2 is state transition matrix and ∈̱R^2 is translation vector,
assuming the state transition be a similar transformation.
In this paper we use explicitly use the translation vector for similar transformation,
while Zhou et la. <cit.> used homogeneous coordinates for their formulation.


MDA represents pedestrian trajectories by a mixture of 
dynamics D and belief B.
Here, dynamics D = (A, ,̱ Q, R) describes dynamics of human movement in the two-dimensional scene.
Belief B describes the starting point _s and end point _e of the trajectory,
each represented by normal distributions as follows;

    _s    ∼ p(_s) = N(_s | μ_s, Φ_s)
    
    _e    ∼ p(_e) = N(_e | μ_e, Φ_e).

That is, belief is represented as B = (μ_s, Φ_s, μ_e, Φ_e),
describing where it starts and to where it is going.
The mixture weights are written as π_m = p(z = m)
where hidden variable z represents that the trajectory is generated by agent m.


Furthermore, observation = {_1, _2, …, _τ} of length τ
is assumed not to start and end at the exact start and end points 
_s and _e of the agent, that is, stats of the trajectory exists
before and after the observed points of the trajectory;

    = {   _s = _-t_s, _-t_s + 1, …, _0, 
       _1, _2, …, _τ, 
       _τ + 1, …, _τ + t_e = _e
    }.

Hereafter, _1:T denotes the sequence of states  except _s and _e.
Figure <ref> shows the state space model of MDA.







 §.§ Learning



Given K trajectories Y = {^k }
MDA estimates M agents Θ = { (D_m, B_m, π_m)}
by maximizing the following log likelihood;

    L = ∑_k log p(^k | ^k, z^k, t_s^k, t_e^k,Θ)

This can be rewritten by replacing 
hidden variables Z = { z^k }, T = { (t_s^k, t_e^k) }
with H = {Z, T}, h^k = { z^k, t_s^k, t_e^k }
as follows;

    L = ∑_k log p(^k | ^k, h^k, Θ)

The EM algorithm estimates iteratively as H is not observed.



  §.§.§ E step



    Q(Θ, Θ̂)
       = E_X, H | Y, Θ̂ [L]
    
       = E_H | X̂, Y, Θ̂ [ E_X | Y, H, Θ̂ [L] ]
    
       = ∑_k ∑_h^kγ^k E_^k | ^k, h^k [L]

Hereafter, 
E_^k | ^k, h^k [^k] = ^k is denoted as ^k,
which is computed by the modified Kalman filter <cit.>.

Weights are given as follows;

    γ^k
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
       =
    p( h^k | _1:T^k, Θ̂) 
          p( ^k| h^k, _1:T^k, Θ̂)
          p( _s^k, _e^k | Θ̂)/p( ^k | _1:T^k, Θ̂)
           p( _s^k, _e^k | Θ̂)

Note that we assume the conditional independence between ^k and _s^k, _e^k,
and between _s^k, _e^k and h^k, _1:T^k.

By further assuming the independence among hidden variables z, t_s, t_e
and the conditional independence between^k and Θ̂,
we have 

    p(h^k | ^k, Θ̂) = p(h^k) = p(z^k, t_s^k, t_e^k) = p(z^k) p(t_s^k) p(t_e^k)

By removing t_s, t_e by assuming those be uniform,
we have

    γ^k
       = p(z^k) p( ^k | h^k, _1:T^k, Θ̂)
             p(_s^k)
             p(_e^k)/∑_h^k p(z^k) p( ^k | h^k, _1:T^k, Θ̂)
                       p(_s^k)
                       p(_e^k)

where p( ^k | h^k, _1:T^k, Θ̂) is computed 
by the modified Kalman filter <cit.> considering
unobserved states 
{_-t_s, _-t_s + 1, …, _0, _τ + 1, …, _τ + t_e}.





  §.§.§ M step


Next we find 
Θ̂= argmax_Θ Q(Θ, Θ̂)
by solving a system of equations
obtained by differentiating Q with respect to Θ,
resulting in the following analytical solutions;





























































































  §.§.§ Implementation


In summary, the EM algorithm iterates the following two steps;


  * for each trajectory ^k, for all h^k = (z^k, t_s^k, t_e^k) the modified Kalman filter is paplied to estimate {^k } and γ^k.

  * Update Θ.



ρ
ρρ
A
B
X
Y
Z
v̌




 §.§ HMM and Switching Kalman Filter




A Hidden Markov Model (HMM) shown in Figure <ref> has  discrete latent variables z.
By using the Baum-Welch algorithm <cit.>, HMM learns parameters from training data,
then infers unobserved states = {z_n}_n=1^N from observations = {_n}_n=1^N
by using the Viterbi algorithm <cit.>.

A possible extension of MDA to segmentation is shown in Figure <ref>
where z_n is assigned to each state _n by using HMM,
where _n is a state of Kalman filter,
and z_n is a hidden variable indicating which agent the observation is generated.
Both _n and z_n are dependent on previous variables _n-1 and z_n-1
as in Fig. <ref>, which is known as Switching Kalman Filter <cit.>.



Switching Kalman Filter <cit.>
is a dynamic system model having parameters that depend on hidden variables.
State _n and observation _n at time n is given by

    _n    ∼ P(_n | _n-1) = N(_n | A_n _n-1, Q_n)
    
    _n    ∼ P(_n | _n) = N(_n | C_n _n, R_n)

where A_n = A[z_n]，C_n = C[z_n]，Q_n = Q[z_n]，R_n = R[z_n] are parameters
that are switched by the value of hidden variable z_n.

Switching Kalman Filter is a useful model, however
needs state transition probabilities to be given <cit.>,
therefore is not applicable to the task presented here.
We instead propose to separate MDA agent estimation from HMM inference
to make the whole procedure to work.








§ PROPOSED METHOD


Figure <ref> shows the overview of the proposed method.
First we learn multiple agent models of trajectories from videos by using MDA.
Then we segment trajectories by using HMM based on the learned agents.




 §.§ Agent estimation by MDA



Let M agents be D_m = (A_m, _̱m, Q_m, R_m), 
B_m = (μ_s,m, Φ_s,m, μ_e,m, Φ_e,m),
and π_m.
Then all agents are denoted as 

    Θ = { (D_m, B_m, π_m)}_m=1^M = {ω_m}_m=1^M

and these are estimated as shown section <ref>.



 §.§ HMM parameter estimation





Figure <ref> shows the model of the proposed method.
Agents transit from one another according to state transition matrix ,
and state  is generated based on output probability matrix .
We use the Baum-Welch algorithm <cit.>
to estimate initial probability distributions ρ
of learned M agents, as well as matrices  and .




We assume that an agent may switch to other agent at each step,
and observation _t ∈ R^6 of one step consists of successive three coordinates 
_t_1, _t_2, _t_3∈ R^2
in a trajectory, as shown in Fig. <ref>.
State _t is considered to be generated
by an agent specified z_t associated to step t.
Hence a trajectory is represented by 
hidden variables = {z_t}_t=1^n,
states = {_t}_t=1^n,
and observations = {_t}_t=1^n.

Here let ρ be an M-dimensional vector
whose m-th element represents 
the initial distribution _m of agent ω_m,
and  by an M× M matrix
whose (i, j) element is transition probability a(i, j)
from agent ω_i to agent ω_j.
Output distribution of agent ω_m is assumed to be normal N(μ_m, Σ_m),
and let  a vector whose m-th element is
output probability of agent ω_m.
Also we denote probability that agent ω_j outputs state _t by

    b(j, t) ∼ p(_t| ω_j)= N(_t| μ_j, Σ_j)






Denoting HMM parameters ρ, , to be estimated by Θ = (ρ, , ),
we maximize the following log likelihood to estimate 
Θ given K trajectories;

    Q(Θ, Θ^old) = ∑_K^∑_^ p(| , Θ^old)lnp(, ; Θ)

by using the EM algorithm.




 §.§ Semantic segmentation



A trajectory is segmented by applying Viterbi algorithm <cit.> with the learned HMM parameters 
Θ, that is, sequences of hidden variables ^∗
and agents Ω^∗;

    ^∗ = { i_1, i_2, ⋯, i_n }
       Ω^∗ = {ω_i_1, ω_i_2, ⋯, ω_i_n}






§ EXPERIMENTS


We compare the proposed method, denoted by MDA+HMM in the following, with
the Ramer-Douglas-Peucker (RDP) algorithm <cit.>
in terms of segmentation accuracy.
Trajectories in the Pedestrian Walking Path Dataset <cit.>
are used for this experiments. This dataset has a large number of pedestrian trajectories
in videos of size 1920 × 1080 pixels.
First we evaluate methods with synthetic trajectories generated from the dataset
for performance comparison,
then with real trajectories of the dataset.



 §.§ Metrics



Evaluation metrics used in this experiments 
are Positional error and Step error defined in Algorithm <ref>.
Note that N_est and N_gt are numbers of 
estimated and actual segmentation points in a trajectory.










 §.§ Synthetic data



In order to compare methods with a large number of trajectories,
we generate 20,000 trajectories from MDA agent models learned from the dataset.
By assuming that transition probabilities are uniform,
these trajectories are sampled from the linear system of Eqs. (<ref>) and (<ref>).
In the following, we use 10,000 trajectories for HMM training (parameter estimation),
and the other 10,000 trajectories for HMM inference (segmentation).
Segmentation points are ones where agent models are switched from one another.

For the RDP method, we segment trajectories by changing the parameter values ϵ,
then choose the best one.

In this case, ϵ = 69 and ϵ = 80 minimize each error.





















For the proposed method, we choose different number of agents for segmentation (between 5 and 10)
for HMM parameter estimation and inference. 
Because 10 agents were learned by MDA, we perform the same procedure for 10 times (except the case of using all 10 agents) then report averaged results.


Table <ref> show comparison results.
The proposed method works better when the number of used agents is larger than eight.







 §.§ Real data


For evaluating methods with the real dataset,
we selected and manually annotated 104 trajectories
so that trajectories are segmented at the point where pedestrians turn their walking directions.

For the RDP method, we segment all trajectories by changing the parameter values ϵ,
then choose the best one.

In this case, ϵ = 38 and ϵ = 29 minimize each error.





















For the proposed method, we choose different number of agents for segmentation (between 5 and 10),
as we did in the previous section.
For separating the dataset for HMM parameter estimation and inference,
we perform four-fold cross validation.

Results are shown in table <ref>.
Figures <ref> to <ref> visualize segmentation results
by the proposed method.
RDP errors are smaller then the proposed method, however
it doesn't provide any semantic information of segmentation.
In contrast, the proposed method divides trajectories
into semantically meaningful segments with associated agent models,
which helps to understand the behavior of the pedestrians in the real scene.
































§ CONCLUSIONS


In this paper we have proposed a semantic trajectory segmentation method
by combining MDA and HMM to estimate agent models and segment trajectories
according to the learned agents.
Experimental results with synthetic trajectory dataset show that the 
proposed method works better than the baseline, the Ramer-Douglas-Peucker method.
Errors of the proposed method on the real dataset are relatively large
due to the fact that the HMM tends to infer multiple agents frequently at
turning points of pedestrians. Our future work includes to overcome this issue.







  

§ ACKNOWLEDGMENTS


  

§ ACKNOWLEDGMENT




This work was supported in part by JSPS KAKENHI grant number JP16H06540.






































IEEEtran





