0% found this document useful (0 votes)

104 views138 pages

Rob2 19 Tracking

Target Tracking Overview   Applications   Types of Problems and Errors   Algorithms   Linear Discrete Systems (LDS)   Kalman Filter (KF)

Uploaded by

jackabraham

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

104 views138 pages

Rob2 19 Tracking

Target Tracking Overview   Applications   Types of Problems and Errors   Algorithms   Linear Discrete Systems (LDS)   Kalman Filter (KF)

Uploaded by

jackabraham

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 138

Robotics 2

Target Tracking
Kai Arras, Cyrill Stachniss,
Maren Bennewitz, Wolfram Burgard

Slides by Kai Arras, Gian Diego Tipaldi, v.1.1, Jan 2012

Chapter Contents
  Target Tracking Overview
  Applications
  Types of Problems and Errors
  Algorithms
  Linear Discrete Systems (LDS)
  Kalman Filter (KF)
  Overview
  Error Propagation
  Esimation Cycle
  Limitations
  Extended Kalman Filter (EKF)
  Overview
  First-Order Error Propagation
  Tracking Example
Target Tracking Overview

Tracking is the estimation of the state of a moving

object based on remote measurements. [Bar-Shalom]

  Detection is knowing the presence of an object

(possibly with some attribute information)

  Tracking is maintaining the state and identity of

an object over time despite detection errors (false
negatives, false alarms), occlusions, and the
presence of other objects
Target Tracking Applications

Fleet Management
Surveillance

Air Traffic Control

Motion Capture Military

Applications

Robotics, HRI
Tracking: Problem Types
  Track stage   Target behavior
  Track formation   Nonmaneuvering
(initialization)   Maneuvering
  Track maintenance
(continuation)
  Number of targets
  Single target
  Number of sensors   Multiple targets
  Single sensor
  Multiple sensors
  Target size
  Point-like target
  Sensor characteristics   Extended target
  Detection probability (PD)
  False alarm rate (PF)
Tracking: Error Types
1. Uncertainty in the values of measurements:
Called “noise”
➔ Solution: Filtering (State estimation theory)

2. Uncertainty in the origin of measurements:

measurement might originate from sources different
from the target of interest. Reasons :
  False alarms
  Decoys and countermeasures
  Multiple targets

➔ Solution: Data Association

(Statistical decision theory)
Tracking: Problem Statement
  Given
  Model of the system dynamics (process or plant model).
Decribes the evolution of the state
  Model of the sensor with which the target is observed
  Probabilistic models of the random factors (noise
sources) and the prior information

  Wanted
  System state estimate such as kinematic (e.g. position),
feature (e.g. target class) or parameters components

  In a way that...
  Accuracy and/or reliability is higher than the raw
measurements
  Contains information not available in the measurements
Tracking Algorithms
  Single non-maneuvering target, no origin uncert.
  Kalman filter (KF)/Extended Kalman filter (EKF)

  Single maneuvering target, no origin uncertainty

  KF/EKF with variable process noise
  Muliple model approaches (MM)

  Single non-maneuvering target, origin uncertainty

  KF/EKF with Nearest/Strongest Neighbor Data Association
  Probabilistic Data Association filter (PDAF)

  Single maneuvering target, origin uncertainty

  Multiple model-PDAF
Tracking Algorithms
  Multiple non-maneuvering targets
  Joint Probabilistic Data Association filter (JPDAF)
  Multiple Hypothesis Tracker (MHT)

  Multiple maneuvering targets

  MM-variants of MHT (e.g. IMMMHT)

  Other Bayesian filtering schemes such as Particle

filters have also been sucessfully applied to the
tracking problem
Linear Dynamic System (LDS)
  A continuous-time Linear Dynamic System (LDS)
can be described by a state equation of the form

Called process or plant model

  The system can be observed remotely through

Called observation or measurement model

  This is the State-Space Representation, omni-

present in physics, control or estimation theory

  Provides the mathematical formulation for our

estimation task
Linear Dynamic System (LDS)
  Stochastic process governed by

  is the state vector

  is the input vector
  is the process noise
  is the system matrix
  is the input gain

  The system can be observed through

  is the measurement vector

  is the measurement noise
  is the measurement matrix
Discrete-Time LDS
  Continuous model are difficult to realize
  Algorithms work at discrete time steps
  Measurements are acquired with certain rates

  In practice, discrete models are employed

  Discrete-time LDS are governed by

  is the state transition matrix

  is the discrete-time input gain

  Same observation function of continuous models

Discrete-Time LDS
  Continuous model are difficult to realize
  Algorithms work at discrete time steps
  Measurements are acquired with certain rates

  In practice, discrete models are employed In ta

rg
track et
the i ing,
np
  Discrete-time LDS are governed by unkn ut is
own!

  is the state transition matrix

  is the discrete-time input gain

  Same observation function of continuous models

LDS Example – Throwing ball
  We want to throw a ball and compute
its trajectory
  This can be easily done with a LDS
  No uncertainties, no tracking, just physics
  The ball‘s state shall be represented as

  We ignore winds but consider the gravity force g

  No floor constraints
  We observe the ball with a noise-free position sensor
LDS Example – Throwing ball
  Throwing a ball from s
with initial velocity v y
  Consider only the gravity v
force, g, of the ball
s
o x

  State vector   Process matrices

  Initial state

  Input vector (scalar)

  Measurement vector   Measurement matrix

LDS Example – Throwing ball

  Initial State

LDS Example – Throwing ball

  The initial state is generally unknown and modeled

as a Gaussian random variable
State estimate
Covariance estimate
Kalman Filter
  State Prediction

  Measurement Prediction

  Update
EKF: Error Propagation
  Error Propagation is everywhere in Kalman filtering
  From the uncertain previous state to the next state over
the system dynamics

  From the uncertain inputs to the state over the input gain
relationship

  From the uncertain predicted state to the predicted

measurements over the measurement model
Error Propagation Law
Given
  A linear system Y = FX⋅X
X, Y assumed to be Gaussian
  Input covariance matrix CX
  System matrix FX

the Error Propagation Law

computes the output covariance matrix CY

46
Error Propagation Law
  Derivation in Matrix Notation

Blackboard...

47
Error Propagation Law
  Derivation in Matrix Notation

48
Kalman Filter Cycle
Kalman Filter Cycle

posterior
motion state
model
predicted innovation from
state matched landmarks

observation
model
predicted
measurements in
sensor coordinates targets

raw sensory data

KF Cycle 1/4: State prediction
  State prediction

  In target tracking, no a priori knowledge of the

dynamic equation is generally available
  Instead, different motion models (MM) are used
  Brownian MM
  Constant velocity MM
  Constant acceleration MM
  Constant turn MM
  Specialized models (problem-related, e.g. ship models)
Motion Models: Brownian
No-motion assumption
  Useful to describe stop-and-go motion behavior
Ball example
  State representation

  Initial state

  Transition matrix
Motion Models: Brownian
No-motion assumption
  Useful to describe stop-and-go motion behavior
Ball example
  State representation

  Initial state

  Transition matrix

State prediction:
  Uncertainty grows
Motion Models: Brownian
No-motion assumption
  Useful to describe stop-and-go motion behavior
Ball example
  State representation

  Initial state

  Transition matrix

State prediction:
  Uncertainty grows
Motion Models: Brownian
No-motion assumption
  Useful to describe stop-and-go motion behavior
Ball example
  State representation

  Initial state

  Transition matrix

State prediction:
  Uncertainty grows
Motion Models: Brownian
No-motion assumption
  Useful to describe stop-and-go motion behavior
Ball example
  State representation

  Initial state

  Transition matrix

State prediction:
  Uncertainty grows
MMs: Constant Velocity
Constant target velocity assumption
  Useful to model smooth target motion
Ball example
  State representation

  Initial state

  Transition matrix
MMs: Constant Velocity
Constant target velocity assumption
  Useful to model smooth target motion
Ball example
  State representation

  Initial state

  Transition matrix

State prediction:
  Linear target motion
  Uncertainty grows
MMs: Constant Velocity
Constant target velocity assumption
  Useful to model smooth target motion
Ball example
  State representation

  Initial state

  Transition matrix

  Initial state

  Transition matrix

  Initial state

  Transition matrix

State prediction:
  Linear target motion
  Uncertainty grows
MMs: Constant Acceleration
Constant target acceleration assumed
  Useful to model target motion that is smooth in position
and velocity changes
Ball example

  State representation

  Initial state

  Transition matrix
MMs: Constant Acceleration
Constant target acceleration assumed
  Useful to model target motion that is smooth in position
and velocity changes
Ball example

  State representation

  Initial state

  Transition matrix

State prediction:
  Non-linear motion
  Uncertainty grows
MMs: Constant Acceleration
Constant target acceleration assumed
  Useful to model target motion that is smooth in position
and velocity changes
Ball example

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix
MMs: Constant Acceleration
Constant target acceleration assumed
  Useful to model target motion that is smooth in position
and velocity changes
Ball example

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix

  State representation

  Initial state

  Transition matrix

State prediction:
  Non-linear motion
  Uncertainty grows
KF Cycle 2/4: Meas. Prediction
  Measurement prediction

  Observation
Typically, only the target position is observed.
The measurement matrix is then

Note: One can also observe

  Velocity (Doppler radar)
  Acceleration (accelerometers)
KF Cycle 3/4: Data Association
  Once measurements are predicted and observed,
we have to associate them with each other
  This is resolving the origin uncertainty
of observations
  Data association is typically done in the
sensor reference frame

  Data association can be a hard problem and

many advanced techniques exist

More on this later in this course

KF Cycle 3/4: Data Association
Step 1: Compute the pairing difference
and its associated uncertainty

  The difference between predicted measurement and

observation is called innovation

  The associated covariance estimate is called the

innovation covariance

  The prediction-observation pair is often called pairing

KF Cycle 3/4: Data Association
Step 2: Check if the pairing is
statistically compatible

  Compute the Mahalanobis distance

  Compare it against the proper threshold from an

cumulative ( chi square ) distribution

Significance level

Degrees of freedom

Compatibility on level α is finally given if this is true

KF Cycle 3/4: Data Association
  Constant velocity model
  Process noise

  Measurement noise

  No false alarm

 No problem
KF Cycle 3/4: Data Association
  Constant velocity model
  Process noise

  Measurement noise

  Uniform false alarm

  False alarm rate = 3

 Ambiguity: several observations in the validation gate

KF Cycle 3/4: Data Association
  Constant velocity model
  Process noise

  Measurement noise

  Uniform false alarm

  False alarm rate = 3

 Wrong association as closest observation is false alarm

KF Cycle 4/4: Update
  Computation of the Kalman gain

  State and state covariance update

KF Cycle 4/4: Update

prediction measurement

correction

It's a weighted mean!

80
Kalman Filter Cycle

posterior
motion state
model
predicted innovation from
state matched landmarks

observation
model
predicted
measurements in
sensor coordinates targets

raw sensory data

Kalman Filter: Limitations
  Non-linear motion models and/or non-linear
measurement models
  Extended Kalman filter

  Unknown inputs into the dynamic process model

(values and modes)
  Enlarged process noise (simple but there are implications)
  Multiple model approaches (accounts for mode changes)

  Uncertain origin of measurements

  Data Association

  How many targets are there?

  Track formation and deletion techniques
  Multiple Hypothesis Tracker (MHT)
Extended Kalman Filter
  The Extended Kalman filter deals with non-linear
process and non-linear measurement models

  Consider a discrete time LDS with dynamic model

where is the process noise (no input assumed)

  The measurement model is

where is the measurement noise

  The same KF-assumptions for the initial state

Kalman Filter
  State Prediction

  Measurement Prediction

  Update
Extended Kalman Filter
  State Prediction
Jacobian

  Measurement Prediction
Jacobian

  Update
First-Order Error Propagation
Given
  A non-linear system Y = f(X)
X,Y assumed to be Gaussian
  Input covariance matrix CX
  Jacobian matrix FX

the Error Propagation Law

computes the output covariance matrix CY

86
First-Order Error Propagation
  Approximating f(X) by a first-order Taylor series
expansion about the point X = µX

87
Jacobian Matrix
  It s a non-square matrix in general

  Suppose you have a vector-valued function

  Let the gradient operator be the vector of (first-order)

partial derivatives

  Then, the Jacobian matrix is defined as

88
Jacobian Matrix
  It’s the orientation of the tangent plane to the vector-
valued function at a given point

  Generalizes the gradient of a scalar valued function

89
Track Management
Formation Occlusion/deletion
  When to create a new track?   When to delete a track?
  What is the initial state?   Is it just occluded?

Heuristics: Heuristics:
  Greedy initialization   Greedy deletion
  Every observation not   Delete if no observation can
associated is a new track be associated
  Initialize only position   No occlusion handling
  Lazy initialization   Lazy deletion
  Accumulate several   Delete if no observation can
unassociated observations be associated for several
  Initialize position & velocity time steps
  Implicit occlusion handling
Example: Tracking the Ball
  Unlike the previous experiment in
which we had a model of the ball s
trajectory and just observed it,
we now want to track the ball

  Comparison: small versus large process noise Q

and the effect of the three different motion models

  For simplicity, we perform no gaiting (i.e. no

Mahalanobis test) but accept the pairing every time
Ball Tracking: Brownian

Small process noise Large process noise

ce!
large differen

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Small process noise Large process noise

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity

Ground truth Observations State estimate

Ball Tracking: Constant Velocity