Segmentation and GroupingLast weekToday’s classEMGestalt groupingSlide Number 8Slide Number 9ExplanationSlide Number 11Slide Number 12Slide Number 13Slide Number 14Slide Number 15Gestaltists do not believe in coincidenceSlide Number 17Gestalt cuesMoving on to image segmentation …Segmentation for feature supportSegmentation for efficiencySegmentation as a resultTypes of segmentationsMajor processes for segmentationSegmentation using clusteringFeature SpaceSlide Number 27K-Means pros and consMean shift segmentationKernel density estimationMean shift algorithmMean shiftMean shiftMean shiftMean shiftMean shiftMean shiftMean shiftReal Modality AnalysisAttraction basinAttraction basinMean shift clusteringSegmentation by Mean ShiftMean shift segmentation resultsSlide Number 46Mean-shift: other issuesMean shift pros and consWatershed algorithmWatershed segmentationMeyer’s watershed segmentationSimple trickWatershed usageWatershed pros and consThings to rememberFurther readingNext classSegmentation and GroupingComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem02/23/10Last week• Clustering• EMToday ’s class• More on EM• Segmentation and grouping– Gestalt cues– By boundaries (watershed)– By clustering (mean‐shift)EMGestalt groupingGerman: Gestalt - "form" or "whole”Berlin School, early 20th centuryKurt Koffka, Max Wertheimer, and Wolfgang Köhler View of brain: • whole is more than the sum of its parts • holistic• parallel • analog • self-organizing tendencies Slide from S. SavereseGestalt psychology or gestaltismThe Muller-Lyer illusionGestaltismExplanationPrinciples of perceptual organizationFrom Steve Lehar: The Constructive Aspect of Visual PerceptionPrinciples of perceptual organizationFrom Steve Lehar: The Constructive Aspect of Visual PerceptionGrouping by invisible completionFrom Steve Lehar: The Constructive Aspect of Visual PerceptionGrouping involves global interpretationGrouping involves global interpretationFrom Steve Lehar: The Constructive Aspect of Visual PerceptionGestaltists do not believe in coincidenceEmergenceGestalt cues• Good intuition and basic principles for grouping• Difficult to implement in practice• Sometimes used for occlusion reasoningMoving on to image segmentation …Goal: Break up the image into meaningful or perceptually similar regionsSegmentation for feature support50x50 Patch50x50 PatchSegmentation for efficiency[Felzenszwalb and Huttenlocher 2004][Hoiem et al. 2005, Mori 2005][Shi and Malik 2001]Segmentation as a resultRother et al. 2004Types of segmentationsOversegmentation UndersegmentationMultiple SegmentationsMajor processes for segmentation• Bottom‐up: group tokens with similar features• Top‐down: group tokens that likely belong to the same object[Levin and Weiss 2006]Segmentation using clustering• Kmeans• Mean‐shiftSource: K. GraumanFeature SpaceImageClusters on intensity Clusters on colorK-means clustering using intensity alone and color aloneK‐Means pros and cons• Pros– Simple and fast– Easy to implement• Cons– Need to choose K– Sensitive to outliers• Usage– Rarely used for pixel segmentation• Versatile technique for clustering‐based segmentationD. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, PAMI 2002. Mean shift segmentationKernel density estimationKernel density estimation functionGaussian kernelMean shift algorithm• Try to find modes of this non‐parametric densityRegion ofinterestCenter ofmassMean ShiftvectorSlide by Y. Ukrainitz & B. SarelMean shiftRegion ofinterestCenter ofmassMean ShiftvectorSlide by Y. Ukrainitz & B. SarelMean shiftRegion ofinterestCenter ofmassMean ShiftvectorSlide by Y. Ukrainitz & B. SarelMean shiftRegion ofinterestCenter ofmassMean ShiftvectorMean shiftSlide by Y. Ukrainitz & B. SarelRegion ofinterestCenter ofmassMean ShiftvectorSlide by Y. Ukrainitz & B. SarelMean shiftRegion ofinterestCenter ofmassMean ShiftvectorSlide by Y. Ukrainitz & B. SarelMean shiftRegion ofinterestCenter ofmassSlide by Y. Ukrainitz & B. SarelMean shiftReal Modality Analysis• Attraction basin: the region for which all trajectories lead to the same mode• Cluster: all data points in the attraction basin of a modeSlide by Y. Ukrainitz & B. SarelAttraction basinAttraction basinMean shift clustering• The mean shift algorithm seeks modes of the given set of points1. Choose kernel and bandwidth2. For each point:a) Center a window on that pointb) Compute the mean of the data in the search windowc) Center the search window at the new mean locationd) Repeat (b,c) until convergence3. Assign points that lead to nearby modes to the same cluster• Find features (color, gradients, texture, etc)• Set kernel size for features Kf and position Ks• Initialize windows at individual pixel locations• Perform mean shift for each window until convergence• Merge windows that are within width of Kf and KsSegmentation by Mean Shifthttp://www.caip.rutgers.edu/~comanici/MSPAMI/msPamiResults.htmlMean shift segmentation resultshttp://www.caip.rutgers.edu/~comanici/MSPAMI/msPamiResults.htmlMean‐shift: other issues• Speedups– Uniform kernel (much faster but not as good)– Binning or hierarchical methods– Approximate nearest neighbor search• Methods to adapt kernel size depending on data density• Lots of theoretical supportD. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, PAMI 2002. Mean shift pros and cons• Pros– Good general‐practice segmentation– Finds variable number of regions– Robust to outliers• Cons– Have to choose kernel size in advance– Original algorithm doesn’t deal well with high dimensions• When to use it– Oversegmentatoin– Multiple segmentations– Other tracking and clustering applicationsWatershed algorithmWatershed segmentationImage GradientWatershed boundariesMeyer’s watershed segmentation1. Choose local minima as region seeds2. Add neighbors to priority queue, sorted by value3. Take top priority pixel from queue1. If all labeled neighbors have same label, assign to pixel2. Add all non‐marked neighbors4. Repeat step 3 until finishedMeyer 1991Matlab: seg = watershed(bnd_im)Simple trick• Use median filter to reduce number of regionsWatershed usage• Use as a starting point for hierarchical segmentation– Ultrametric contour map (Arbelaez 2006)• Works with any soft boundaries– Pb– Canny– Etc.Watershed pros and