COMP9517_24T2W9_Object_Tracking.pdf

COMP9517: Computer Vision Object Tracking Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 1  Motion Tracking Tracking is the problem of generating an inference about the motion of an object given a sequence of images Copyright (C) UNS...

COMP9517: Computer Vision Object Tracking Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 1  Motion Tracking Tracking is the problem of generating an inference about the motion of an object given a sequence of images Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 2  Applications Motion capture – Record motion of people to control cartoon characters in animations – Modify the motion record to obtain slightly different behaviours Recognition from motion – Determine the identity of a moving object – Assess what the object is doing Surveillance – Detect and track objects in a scene for security – Monitor their activities and warn if anything suspicious happens Targeting – Decide which objects to target in scene – Make sure the objects get hit Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 3  Difficulties in Tracking Loss of information caused by projection of the 3D world on a 2D image Noise in images Complex object motion Non-rigid or articulated nature of objects Partial and full object occlusions Complex object shapes Scene illumination changes Real-time processing requirements Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 4  Example Tracking Problem Single moving microscopic particle Imaged with signal-to-noise ratio (SNR) of 1.5 Human visual motion perception Not so accurate and reproducible in quantification Good at integrating spatial and temporal information Powerful in making associations and predictions Computer vision challenges Integration of spatial and temporal information Modeling and incorporation of prior knowledge Probabilistic rather than deterministic approach Bayesian estimation methods… Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 5  Motion Assumptions When moving objects do not have unique texture or colour, the characteristics of the motion itself must be used to connect detected points into trajectories Assumptions about each moving object: – Location changes smoothly over time – Velocity (speed and direction) changes smoothly over time – Can be at only one location in space at any given time – Not in same location as another object at the same time Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 6  Topics Bayesian inference Using probabilistic models to perform tracking Kalman filtering Using linear model assumptions for tracking Particle filtering Using nonlinear models for tracking Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 7  Bayesian Inference Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 8  Problem Definition A moving object has a state which evolves over time Random variable: Xi can contain any quantities of interest (position, velocity, acceleration, Specific value: xi shape, intensity, colour, …) The state is measured at each time point Random variable: Yi in computer vision the measurements are typically Specific value: yi features computed from the images Measurements are combined to estimate the state Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 9  Three Main Steps Prediction: use the measurements ( y0 , y1 ,..., yi −1 ) up to time i − 1 to predict the state at time i P( X i | Y0 = y0 , Y1 = y1 ,..., Yi −1 = yi −1 ) Association: select the measurements at time i that are related to the object state Correction: use the incoming measurement yi to update the state prediction P( X = i | Y0 0 , Y1 y= y1 ,...,= 1 , Yi Yi −1 yi −= yi ) Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 10  Independence Assumptions Current state depends only on the immediate past P( X i | X 0 , X 1 ,..., X i −1 ) = P( X i | X i −1 ) Measurements depend only on the current state P(Yi , Y j ,..., Yk | X i ) = P(Yi | X i ) P(Y j ,..., Yk | X i ) These assumptions imply the tracking problem has Yi-1 Yi Yi+1 the structure of inference on a hidden Markov model Xi-1 Xi Xi+1 Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 11  Tracking by Bayesian Inference Prediction P( X i | y0 , y1 ,..., yi −1 ) = ∫ P( X i , X i −1 | y0 , y1 ,..., yi −1 ) dX i −1 = ∫ P( X i | X i −1 , y0 , y1 ,..., yi −1 ) P( X i −1 | y0 , y1 ,..., yi −1 ) dX i −1 = ∫ P( X i | X i −1 ) P( X i −1 | y0 , y1 ,..., yi −1 ) dX i −1 dynamics posterior of P( X i , X i −1 | y0 , y1 ,..., yi −1 ) = P( X i , X i −1 , y0 , y1 ,..., yi −1 ) P( y0 , y1 ,..., yi −1 ) model previous time = P( X i | X i −1 , y0 , y1 ,..., yi −1 ) P( X i −1 , y0 , y1 ,..., yi −1 ) P( y0 , y1 ,..., yi −1 ) P( X i −1 , y0 , y1 ,..., yi −1 ) = P( X i | X i −1 , y0 , y1 ,..., yi −1 ) P( y0 , y1 ,..., yi −1 ) = P( X i | X i −1 , y0 , y1 ,..., yi −1 ) P( X i −1 | y0 , y1 ,..., yi −1 ) Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 12  Tracking by Bayesian Inference Correction P( X i , y0 , y1 ,..., yi ) P( X i | y0 , y1 ,..., yi ) = P( y0 , y1 ,..., yi ) P( yi | X i , y0 , y1 ,..., yi −1 ) P( X i | y0 , y1 ,..., yi −1 ) P( y0 , y1 ,..., yi −1 ) = P( y0 , y1 ,..., yi ) P( y0 , y1 ,..., yi −1 ) = P( yi | X i ) P( X i | y0 , y1 ,..., yi −1 ) P( y0 , y1 ,..., yi ) ∝ P( yi | X i ) P( X i | y0 , y1 ,..., yi −1 ) constant measurement prediction of model current state Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 13  Tracking by Bayesian Inference In summary, tracking by Bayesian inference is done by iterative prediction and correction: Prediction P( X i | Y0:i −1 ) = ∫ P( X i | X i −1 ) P( X i −1 | Y0:i −1 ) dX i −1 Posterior at time 𝑖𝑖 − 1 Correction P( X i | Y0:i ) ∝ P(Yi | X i ) P( X i | Y0:i −1 ) Posterior at time 𝑖𝑖 Y= 0:k (Y =0 y0 ,= Y1 y1 ,..., Y= k yk ) Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 14  Tracking by Bayesian Inference To make tracking by Bayesian inference work in practice you need to design two models: Dynamics model P ( X i | X i −1 ) Measurement model P (Yi | X i ) The specific design choices are application dependent Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 15  Tracking by Bayesian Inference Final estimates are computed from the posterior: Example 1: expected a posteriori (EAP) =xˆi ∫= x P( X i i xi | Y0:i )dxi Example 2: maximum a posteriori (MAP) =xˆi arg = max xi P( X i xi | Y0:i ) These are the most popular ones but others are possible Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 16  Tracking by Bayesian Inference P( X i = xi | Y0:i ) xi xˆ iEAP xˆ iMAP Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 17  Bayesian Tracking Example Estimating the coordinates of a moving particle: t Posterior computed from the image x y t= i+4 t= i+3 t= i+2 t = i +1 t =i P( X i | Y0:i ) Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 18  Kalman Filtering Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 19  Probability Density Propagation dynamics model noise measurement model Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 20  Linear / Gaussian Assumption If we assume the dynamics (state transition) model and the measurement model to be linear, and the noise to be additive Gaussian, then all the probability densities will be Gaussians: 𝑥𝑥 ∼ 𝑁𝑁(𝜇𝜇, Σ) The state is advanced by multiplying with some known matrix and then adding a zero-mean normal random variable: xi Axi −1 + qi −1 = The measurement is obtained by multiplying the state by some matrix and then adding a zero-mean normal random variable: yi Hxi + ri = Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 21 xi ~ N ( Axi −1 , Q) yi ~ N ( Hxi , R) Kalman Filtering Correction Prediction 1. Compute Kalman gain 1. Predict state =K i Pi − H T ( H Pi − H T + R ) −1 xi− = Axi −1 2. Correct state with measurement 2. Predict covariance xi− + K i ( yi − H xi− ) xi = =Pi − APi −1 AT + Q 3. Correct covariance P= i ( I − K i H ) Pi − i → i +1 Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 22  Particle Filtering Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 23  Probability Density Propagation dynamics model noise measurement model Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 24  Non-Linear / Non-Gaussian Case Represent the conditional state density by a set of samples (particles) with corresponding weights (importance) P( X i | Y0:i ) → {si( n ) , π i( n ) }nN=1 Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 25  Particle Filtering Propagate each sample using the dynamics model and obtain its new weight using the measurement model Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 26  Particle Filtering Algorithm NIPS 1996 Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 27  Example Application Tracking of active contour representations of objects Particle filtering is also known variously as sequential Monte Carlo (SMC) filtering, bootstrap filtering, the condensation algorithm… Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 28  Example Application Tracking of object location in the presence of clutter Walking pedestrian represented by a state vector consisting of a center position and a bounding box: si = ( x, y, w, h)i si( n ) (samples) sˆi (estimated) si (truth/annotated) Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 29  Example Application Tracking of object location in the presence of clutter https://www.youtube.com/watch?v=j-duyzShJ_o Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 30 References and Acknowledgements Chapters 5 and 8 of Szeliski 2010 Chapter 18 of Forsyth and Ponce 2011 Chapter 9 of Shapiro and Stockman 2001 Paper by M. Isard and A. Blake 1998 CONDENSATION: Conditional density propagation for visual tracking Available online via the UNSW Library Some images drawn from the above references Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 31 Example exam question Which one of the following statements about object tracking is incorrect? A. The particle filtering method assumes that the dynamics model and the measurement model can be parameterized. B. The hidden Markov model assumes that the measurements depend only on the current state of the objects. C. The prediction step of Bayesian inference assumes that the current state of the objects depends only on the previous state. D. The Kalman filtering method assumes that the dynamics and measurement noise are additive Gaussian. Copyright (C) UNSW COMP9517 24T2W9 Object Tracking 32