CSE486, Penn StateRobert CollinsLecture 29: Video Tracking: Mean-ShiftCSE486, Penn StateRobert CollinsAppearance-Based Trackingcurrent frame +previous locationMode-Seeking(e.g. mean-shift; Lucas-Kanade; particle filtering)likelihood overobject locationcurrent locationappearance model(e.g. image template, orcolor; intensity; edge histograms)CSE486, Penn StateRobert CollinsHistogram Appearance Models • Motivation – to track non-rigid objects, (like a walking person), it is hard to specifyan explicit 2D parametric motion model.• Appearances of non-rigid objects can sometimes be modeled with color distributionsCSE486, Penn StateRobert CollinsAppearance via Color HistogramsColor distribution (1D histogram normalized to have unit weight)R’G’B’discretizeR’ = R << (8 - nbits)G’ = G << (8 - nbits)B’ = B << (8-nbits)Total histogram size is (2^(8-nbits))^3example, 4-bit encoding of R,G and B channelsyields a histogram of size 16*16*16 = 4096.CSE486, Penn StateRobert CollinsSmaller Color HistogramsR’G’B’discretizeR’ = R << (8 - nbits)G’ = G << (8 - nbits)B’ = B << (8-nbits)Total histogram size is 3*(2^(8-nbits))example, 4-bit encoding of R,G and B channelsyields a histogram of size 3*16 = 48.Histogram information can be much much smaller if we are willing to accept a loss in color resolvability.Marginal R distributionMarginal G distributionMarginal B distributionCSE486, Penn StateRobert CollinsColor Histogram Examplered green blueCSE486, Penn StateRobert CollinsNormalized Color(r,g,b) (r’,g’,b’) = (r,g,b) / (r+g+b)Normalized color divides out pixel luminance (brightness), leaving behind only chromaticity (color) information. The result is less sensitive to variations due to illumination/shading.CSE486, Penn StateRobert CollinsMean-ShiftThe mean-shift algorithm is an efficient approach to tracking objects whose appearance is defined by color.(not limited to only color, however. Could also use edge orientations, texture, motion)CSE486, Penn StateRobert CollinsWhat is Mean Shift ?Non-parametricDensity EstimationNon-parametricDensity GRADIENT Estimation (Mean Shift)DataDiscrete PDF RepresentationPDF AnalysisA tool for:Finding modes in a set of data samples, manifesting an underlying probability density function (PDF) in RNUkrainitz&Sarel, WeizmannPDF in feature space• Color space• Scale space• Actually any feature space you can conceive• …CSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassMean ShiftvectorObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsIntuitive DescriptionDistribution of identical billiard ballsRegion ofinterestCenter ofmassObjective : Find the densest regionUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert CollinsUsing Mean-Shift on Color ModelsTwo approaches:1) Create a color “likelihood” image, with pixelsweighted by similarity to the desired color (bestfor unicolored objects)2) Represent color distribution with a histogram. Usemean-shift to find region that has most similardistribution of colors.CSE486, Penn StateRobert CollinsMean-shift on Weight ImagesIdeally, we want an indicator function that returns 1 for pixels on the object we are tracking, and 0 for all other pixelsInstead, we compute likelihood maps where the value at a pixel is proportional to the likelihood that the pixel comes from the object we are tracking.Computation of likelihood can be based on• color• texture• shape (boundary)• predicted locationCSE486, Penn StateRobert CollinsMean-Shift TrackingLet pixels form a uniform grid of data points, each with a weight (pixel value) proportional to the “likelihood” that the pixel is on the object we want to track. Perform standard mean-shift algorithm using this weighted set of points.x = aK(a-x) w(a) (a-x)aK(a-x) w(a)CSE486, Penn StateRobert CollinsNice PropertyRunning mean-shift with kernel K on weight image w is equivalent to performing gradient ascent in a (virtual) image formed by convolving w with some “shadow” kernel H.Note: mode we are looking for is mode of location (x,y)likelihood, NOT mode of the color distribution!CSE486, Penn StateRobert CollinsExample: Face Tracking using Mean -ShiftGray Bradski, “Computer Vision Face Tracking for use in a Perceptual User Interface,”IEEE Workshop On Applications of Computer Vision, Princeton, NJ, 1998, pp.214-219.CSE486, Penn StateRobert CollinsBradski’s CamShiftX,Y location of mode found by mean-shift.Z, Roll angle determined by fitting an ellipseto the mode found by mean-shift algorithm.CSE486, Penn StateRobert CollinsCamShift ResultsFast motion DistractorsFrom Gary BradskiCSE486, Penn StateRobert CollinsCamShift ApplicationsQuake interfaceFlight simulatorCSE486, Penn StateRobert CollinsUsing Mean-Shift on Color ModelsTwo approaches:1) Create a color “likelihood” image, with pixelsweighted by similarity to the desired color (bestfor unicolored objects)2) Represent color distribution with a histogram. Usemean-shift to find region that has most similardistribution of colors.CSE486, Penn StateRobert CollinsMean-Shift Object TrackingTarget RepresentationChoose a reference target modelQuantized Color SpaceChoose a feature spaceRepresent the model by its PDF in the feature space00.050.10.150.20.250.30.351 2 3 . . . mcolorProbabilityKernel Based Object Tracking, by Comaniniu, Ramesh, MeerUkrainitz&Sarel, WeizmannCSE486, Penn StateRobert