Graph-based SegmentationLast classToday’s classImages as graphsSimilarity matrixSegmentation by Graph CutsCuts in a graphBut min cut is not always the best cut...Slide 9Recursive normalized cutsNormalized cuts resultsNormalized cuts: Pro and conGraph cuts segmentationMarkov Random FieldsSlide 15Solving MRFs with graph cutsSlide 17Grab cuts and graph cutsColour ModelGraph cuts Boykov and Jolly (2001)Slide 21Moderately straightforward examplesDifficult ExamplesUsing graph cuts for recognitionSlide 25Limits of graph cutsGraph cuts: Pros and ConsFurther reading and resourcesRecap of Grouping and FittingLine detection and Hough transformRobust fitting and registrationClusteringEM and Mixture of GaussiansSegmentationNext section: RecognitionGraph-based SegmentationComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem02/25/10Last class•Gestalt cues and principles of organization•Mean-shift segmentation–Good general-purpose segmentation method –Generally useful clustering, tracking technique•Watershed segmentation–Good for hierarchical segmentation–Use in combination with boundary predictionToday’s class•Treating the image as a graph–Normalized cuts segmentation–MRFs Graph cuts segmentation•Recap•Go over HW2 instructionsiImages as graphs•Fully-connected graph–node for every pixel–link between every pair of pixels, p,q–similarity wij for each linkjwijcSource: SeitzSimilarity matrixIncreasing sigmaSegmentation by Graph Cuts•Break Graph into Segments–Delete links that cross between segments–Easiest to break links that have low cost (low similarity)•similar pixels should be in the same segments•dissimilar pixels should be in different segmentswA B CSource: SeitzCuts in a graph•Link Cut–set of links whose removal makes a graph disconnected–cost of a cut:ABOne idea: Find minimum cut•gives you a segmentation•fast algorithms exist for doing thisSource: SeitzBut min cut is not always the best cut...Cuts in a graphABNormalized Cut•a cut penalizes large segments•fix by normalizing for size of segments•volume(A) = sum of costs of all edges that touch ASource: SeitzRecursive normalized cuts1. Given an image or image sequence, set up a weighted graph: G=(V, E)–Vertex for each pixel–Edge weight for nearby pairs of pixels 2. Solve for eigenvectors with the smallest eigenvalues: (D − W)y = λDy–Use the eigenvector with the second smallest eigenvalue to bipartition the graph–Note: this is an approximation4. Recursively repartition the segmented parts if necessaryhttp://ww w. cs.berkeley.edu/~malik/papers/ SM-ncut.pdfDetails:Normalized cuts resultsNormalized cuts: Pro and con•Pros–Generic framework, can be used with many different features and affinity formulations–Provides regular segments•Cons–Need to chose number of segments–High storage requirement and time complexity–Bias towards partitioning into equal segments•Usage–Use for oversegmentation when you want regular segmentsGraph cuts segmentationMarkov Random FieldsedgesjijiiidatayydataydataEnergy,21),;,(),;(),;(yNode yi: pixel labelEdge: constrained pairsCost to assign a label to each pixelCost to assign a pair of labels to connected pixelsMarkov Random Fields•Example: “label smoothing” gridUnary potential 0 10 0 K1 K 0Pairwise Potential0: -logP(yi = 0 ; data)1: -logP(yi = 1 ; data) edgesjijiiidatayydataydataEnergy,21),;,(),;(),;(ySolving MRFs with graph cutsedgesjijiiidatayydataydataEnergy,21),;,(),;(),;(ySource (Label 0)Sink (Label 1)Cost to assign to 0Cost to assign to 1Cost to split nodesSolving MRFs with graph cutsedgesjijiiidatayydataydataEnergy,21),;,(),;(),;(ySource (Label 0)Sink (Label 1)Cost to assign to 0Cost to assign to 1Cost to split nodesGrab cuts and graph cutsGrab cuts and graph cuts Grab cuts and graph cutsGrab cuts and graph cutsUser InputResultMagic Wand (198?)Intelligent ScissorsMortensen and Barrett (1995)GrabCutRegionsBoundaryRegions & BoundarySource: RotherColour ModelColour Model Colour ModelColour ModelGaussian Mixture Model (typically 5-8 components)Foreground &BackgroundBackgroundForegroundBackgroundGRGRIterated graph cutSource: RotherGraph cutsGraph cuts Boykov and Jolly (2001)Boykov and Jolly (2001)Graph cutsGraph cuts Boykov and Jolly (2001)Boykov and Jolly (2001)ImageImage Min CutMin CutCut: separating source and sink; Energy: collection of edgesMin Cut: Global minimal enegry in polynomial timeForeground Foreground (source)(source)BackgroundBackground(sink)(sink)Source: RotherGraph cuts segmentation1. Define graph –usually 4-connected or 8-connected2. Define unary potentials–Color histogram or mixture of Gaussians for background and foreground3. Define pairwise potentials4. Apply graph cuts5. Return to 2, using current labels to compute foreground, background models22212)()(exp),(_ycxckkyxp otentialedge));(());((log)(_backgroundforegroundxcPxcPxpotentia lunaryModerately straightforward Moderately straightforward examples examples Moderately straightforward Moderately straightforward examples examples… GrabCut completes automatically GrabCut – Interactive Foreground Extraction 10Difficult ExamplesDifficult Examples Difficult ExamplesDifficult ExamplesCamouflage & Low ContrastHarder CaseFine structureInitial RectangleInitialResult GrabCut – Interactive Foreground Extraction 11Using graph cuts for recognitionTextonBoost (Shotton et al. 2009 IJCV)Using graph cuts for recognitionTextonBoost (Shotton et al. 2009 IJCV)Unary PotentialsAlpha Expansion Graph CutsLimits of graph cuts•Associative: edge potentials penalize different labels•If not associative, can sometimes clip potentials•Approximate for multilabel–Alpha-expansion or alpha-beta swapsMust satisfyGraph cuts: Pros and Cons•Pros–Very fast inference–Can incorporate recognition or high-level priors–Applies to a wide range of problems (stereo, image labeling, recognition)•Cons–Not always applicable (associative only)–Need unary terms (not used for generic segmentation)•Use whenever applicableFurther reading and resources•Normalized cuts and image segmentation (Shi and Malik)http://www.cs.berkeley.edu/~malik/papers/SM-ncu t .pdf•N-cut implementation http://www.seas.upenn.edu/~timothee/software/ncut/ncut.html•Graph