C280 Computer VisionC280, Computer VisionProf. Trevor [email protected] 19: TrackingTracking scenarios• Follow a pointll l•Follow a template• Follow a changing template• Follow all the elements of a moving person, fit a model to it.2Things to consider in trackingWhat are the dynamics of the thing being tracked?ii b d?How is it observed?3Three main issues in tracking4Simplifying Assumptions5Kalman filter graphical model and corresponding factorized joint probabilitycorresponding factorized joint probabilityx1x2x3y1y2y3),,,,,(321321yyyxxxP)|()|()|()|()|()(),,,,,(33232212111321321xyPxxPxyPxxPxyPxPyyy6Tracking as induction• Make a measurement starting in the 0thframehhihih•Then: assume you have an estimate at the ith frame, after the measurement step.Sh th t d di ti f th i+1th•Show that you can do prediction for the i+1th frame, and measurement for the i+1th frame.7Base case8Prediction stepgiven9Update stepgiven10The Kalman Filter• Key ideas: Li d l i t t i l ll ith G i–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 done11Recall the three main issues in tracking(Ignore data association for now)12(Ignore data association for now)The Kalman Filter13[figure from http://www.cs.unc.edu/~welch/kalman/kalmanIntro.html]The Kalman Filter in 1D• Dynamic Model•NotationPredicted meanCorrected mean14The Kalman Filter15Prediction for 1D Kalman filter• The new state is obtained bylti l i ld t t b k t t–multiplying old state by known constant– adding zero-mean noise• Therefore, predicted mean for new state isconstant times mean for old state–constant times mean for old state• Old variance is normal random variable–variance is multiplied by square of constantvariance is multiplied by square of constant– and variance of noise is added.1617The Kalman Filter18Measurement update for 1D Kalman filterNotice:– if measurement noise is small, we rely mainly on the measurement,– if it’s large, mainly on the predictiondtdd19–does not depend on y20Kalman filter for computing an on-line average•What Kalman filter parameters and initialWhat Kalman filter parameters and initial conditions should we pick so that the optimal estimate for x at each iteration is just the average of all the observations seen so far?211,0,1,1iimdiimdKalman filter model000x,,,iimdiiInitial conditionsIteration 0 1 2000xix00y210yyix0y210yy3210yyyi1121122i12131What happens if the x dynamics are given a non-zero variance?nonzero variance?231,1,1,1iimdiimdKalman filter model000x,,,iimdiiInitial conditionsIteration 0 1 2000xix00y3210yyix0y3210yy852210yyyi23524i13285Linear dynamic models• A linear dynamic model has the formxi N Di1xi1;diyi N Mixi;mi• This is much, much more general than it looks, and extremely powerful25Examples of linear state space modelsxi N Di1xi1;dimodels• Drifting pointsth t th iti f th i t i th ldyi N Mixi;mi–assume that the new position of the point is the old one, plus noiseD=IdentityD Identity26cic.nist.gov/lipman/sciviz/images/random3.gif http://www.grunch.net/synergetics/images/random3.jpgConstant velocity xi N Di1xi1;di• We haveyi N Mixi;miuiui1tvi1ivi vi1i– (the Greek letters denote noise terms)•Stack (u, v) into a single state vectorStack (u, v) into a single state vectoru1tui– which is the form we had abovevi01vi1noiseD27Di-1xi-1xipositionvelocitypositiontimepCtimemeasurement,positionConstantVelocityModelModel28timeConstant accelerationxi N Di1xi1;di• We haveuutvyi N Mixi;miuiui1tvi1ivi vi1tai1iaa– (the Greek letters denote noise terms)•Stack (u, v) into a single state vectoraiai1iStack (u, v) into a single state vectoruv1t001tuvnoise– which is the form we had abovevai01t00 1vai1noise29Di-1xi-1xipositionvelocitytimepositiontimeConstantAcceleration30cce e oModelPeriodic motionNMxi N Di1xi1;diAssume we have a point, moving on a line with a periodic movement defined with ayiNMixi;mia periodic movement defined with a differential eq: can be defined ascan be defined as ih d fi d k d ii d31with state defined as stacked position and velocity u=(p, v)Periodic motionxi N Di1xi1;diyi N Mixi;miTake discrete approximation….(e.g., forward Euler integration with t stepsize.)32Di-1xi-1xin-DGeneralization to n-D is straightforward but more complex.33n-DGeneralization to n-D is straightforward but more complex.34n-D PredictionGeneralization to n-D is straightforward but more complex.Prediction:• Multiply estimate at prior time with forward model:• Propagate covariance through model and add new noise:35n-D CorrectionGeneralization to n-D is straightforward but more complex.Correction:• Update a priori estimate with measurement to form a posteriori36n-D correctionFind linear filter on innovations which minimizes a posteriori error covariance:xxxxETK is the Kalman Gain matrix. A solution is37Kalman Gain MatrixAs measurement becomes more reliable, K weights residual more heavily, 10lim MKimAs prior covariance approaches 0, measurements are ignored:0liK380lim0iKi39tionocitypositvelopositiontimepositiontime40Constant Velocity Modelsitionpos41timeThis is figure 17.3 of Forsyth and Ponce. The notation is a bit involved, but is logical. Weplot the true state as open circles, measurements as x’s, predicted means as *’swith three standard deviation bars, corrected means as +’s with three standard deviation
View Full Document