6.891SyllabusTracking ApplicationsThings to consider in trackingDensity propogationOutlineTracking and Recursive estimationRecursive estimationTrackingThree main issues in trackingSimplifying AssumptionsTracking as inductionBase caseInduction stepInduction stepLinear dynamic modelsExamplesConstant velocityConstant accelerationPeriodic motionPeriodic motionHigher order modelsThe Kalman FilterRecall the three main issues in trackingThe Kalman FilterThe Kalman Filter in 1DThe Kalman FilterPrediction for 1D Kalman filterThe Kalman FilterCorrection for 1D Kalman filterSmoothingn-Dn-Dn-D Predictionn-D Correctionn-D correctionKalman Gain Matrix2-D constant velocity example from Kevin Murphy’s Matlab toolboxData AssociationData AssociationAbrupt changesMultiple model filtersMM estimateP likelihoodNo lagSmooth when stillResources(KF) Distribution propogationDistribution propogationEKFRepresenting non-linear DistributionsRepresenting non-linear DistributionsRepresenting non-linear DistributionsRepresenting Distributions using Weighted SamplesRepresenting Distributions using Weighted SamplesOutline16.891Computer Vision and ApplicationsProf. Trevor. DarrellLecture 16: Tracking– Density propagation– Linear Dynamic models / Kalman filter – Data association– Multiple modelsReadings: F&P Ch 172Syllabus3Tracking Applications• Motion capture• Recognition from motion• Surveillance• Targeting4Things to consider in trackingWhat are the• Real world dynamics• Approximate / assumed model• Observation / measurement process5Density propogation• Tracking == Inference over time• Much simplification is possible with linear dynamics and Gaussian probability models6Outline• Recursive filters• State abstraction• Density propagation• Linear Dynamic models / Kalman filter • Data association• Multiple models7Tracking and Recursive estimation• Real-time / interactive imperative.• Task: At each time point, re-compute estimate of position or pose.– At time n, fit model to data using time 0…n– At time n+1, fit model to data using time 0…n+1• Repeat batch fit every time?8Recursive estimation• Decompose estimation problem– part that depends on new observation– part that can be computed from previous history• E.g., running average:at= α at-1+ (1-α) yt• Linear Gaussian models: Kalman Filter• First, general framework…9Tracking• Very general model: – We assume there are moving objects, which have an underlying state X– There are measurements Y, some of which are functions of this state– There is a clock• at each tick, the state changes• at each tick, we get a new observation• Examples– object is ball, state is 3D position+velocity, measurements are stereo pairs– object is person, state is body configuration, measurements are frames, clock is in camera (30 fps)10Three main issues in tracking11Simplifying Assumptions12Tracking as induction• Assume data association is done– we’ll talk about this later; a dangerous assumption• Do correction for the 0’th frame• Assume we have corrected estimate for i’th frame– show we can do prediction for i+1, correction for i+113Base case14Induction stepgiven15Induction stepgiven16Linear dynamic models• A linear dynamic model has the form• This is much, much more general than it looks, and extremely powerfulxi= N Di−1xi−1;Σdi()yi= N Mixi;Σmi()17xi= N Di−1xi−1;Σdi()Examples• Drifting points– assume that the new position of the point is the old one, plus noiseD = Idyi= N Mixi;Σmi()cic.nist.gov/lipman/sciviz/images/random3.gif http://www.grunch.net/synergetics/images/random3.jpg18Constant velocity yi= N Mixi;Σmi()xi= N Di−1xi−1;Σdi()• We have– (the Greek letters denote noise terms)• Stack (u, v) into a single state vector– which is the form we had aboveui=ui−1+∆tvi−1+εivi= vi−1+ςiuv      i=1∆t01      uv      i−1+ noise19positionpositionConstantVelocityModelvelocitytimemeasurement,positiontime20xi= N Di−1xi−1;Σdi()Constant acceleration• We have– (the Greek letters denote noise terms)• Stack (u, v) into a single state vector– which is the form we had aboveui=ui−1+∆tvi−1+εivi= vi−1+∆tai−1+ςiai= ai−1+ξiuva        i=1∆t001∆t00 1        uva        i−1+ noiseyi= N Mixi;Σmi()21timepositionpositionvelocityConstantAccelerationModel22Assume we have a point, moving on a line with a periodic movement defined with a differential eq: can be defined as with state defined as stacked position and velocity u=(p, v)Periodic motionyi= N Mixi;Σmi()xi= N Di−1xi−1;Σdi()23xi= N Di−1xi−1;Σdi()Periodic motionyi= N Mixi;Σmi()Take discrete approximation….(e.g., forward Euler integration with ∆t stepsize.)24Higher order models• Independence assumption• Velocity and/or acceleration augmented position• Constant velocity model equivalent to–velocity ==– acceleration ==– could also use , etc.25The Kalman Filter• Key ideas: – Linear models interact uniquely well with Gaussian noise - make the prior Gaussian, everything else Gaussian and the calculations are easy– Gaussians are really easy to represent --- once you know the mean and covariance, you’re done26Recall the three main issues in tracking(Ignore data association for now)27The Kalman Filter[figure from http://www.cs.unc.edu/~welch/kalman/kalmanIntro.html]28The Kalman Filter in 1D• Dynamic Model•NotationPredicted meanCorrected mean29The Kalman Filter30Prediction for 1D Kalman filter• The new state is obtained by– multiplying old state by known constant– adding zero-mean noise• Therefore, predicted mean for new state is– constant times mean for old state• Old variance is normal random variable– variance is multiplied by square of constant– and variance of noise is added.3132The Kalman Filter33Correction for 1D Kalman filterNotice:– if measurement noise is small, we rely mainly on the measurement,– if it’s large, mainly on the prediction– σ does not depend on y3435positionpositionvelocitytimeConstantVelocityModel36position andmeasurementtime3738The o-s give state, x-s measurement.39The o-s give state, x-s measurement.40Smoothing•Idea– We don’t have the best estimate of state - what about the future?– Run two filters, one moving forward, the other backward in time.– Now combine