Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Computer VisionMarch 2004 L1.1© 2004 by Davi GeigerImage SegmentationBased on the work of Shi and Malik, Carnegie Mellon and Berkleyand based on the presentation of Jianbo ShiComputer VisionMarch 2004 L1.2© 2004 by Davi Geiger•Edge detection by gradient operators•Linking by dynamic programming, voting, relaxation, …- Natural for encoding curvilinear grouping- Hard decisions often made prematurelyEdge-based image segmentationComputer VisionMarch 2004 L1.3© 2004 by Davi GeigerGrouping with Bayesian StatisticsBayes data structure = data generation model + segmentation modelX1X2Image asobservation fGrouping asstate Xf1f2)](log)|(log[min);(min XpXfpfXEXXSegmentation is to find a partitioning of an image, with generative models explaining each partition.Generative models constrain the observation data, f , and the prior model constrains the discrete states, X.The solution sought is the most probable state, or the state of the lowest energy.Texture modelsComputer VisionMarch 2004 L1.4© 2004 by Davi GeigerImage segmentation by pairwise similarities•Image = { pixels }•Segmentation = partition of image into segments•Similarity between pixels i and j Sij = Sji ≥ 0•Objective: “similar pixels, with large value of Sij, should be in the same segment, dissimilar pixels should be in different segments”SijComputer VisionMarch 2004 L1.5© 2004 by Davi GeigerRelational Graphs G=(V, E, S) V: each node denotes a pixel E: each edge denotes a pixel-pixel relationship  S: each edge weight measures pairwise similarity Segmentation = node partitioning break V into disjoint sets V1 , V2Computer VisionMarch 2004 L1.6© 2004 by Davi GeigerSolving MRF by Graph Partitioning  ppppp pNqqpqpfXUXXWfXE ),(),();(min)(,Some simple MRF models can be translated into graph partitioningpair relationshipsdata measuresL1 L2Computer VisionMarch 2004 L1.7© 2004 by Davi GeigerWeighted graph partitioningPixels i I = vertices of graph GEdges ij = pixel pairs with Sij > 0Similarity matrix S = [ Sij ]di = j Є G Sij degree of Ideg A = i Є A di degree of A GAssoc(A,B) = i Є A j Є B Sij SijijiAABComputer VisionMarch 2004 L1.8© 2004 by Davi GeigerCuts in a Graph•(edge) cut = set of edges whose removal makes a graph disconnected•weight of a cut: cut( A, B ) = i Є A, j Є B Sij =Assoc(A,B) •the normalized cut•Normalized Cut criteria: minimum cut(A,Ā)NCut( A,B ) = cut(A, B)( + ) 1 deg A 1 deg B ),(1jiijxxdS Computer VisionMarch 2004 L1.9© 2004 by Davi GeigerGrouping with Spectral Graph PartitioningSGP: data structure = a weighted graph, weights describing data affinitySegmentation is to find a node partitioning of a relational graph, with minimum total cut-off affinity.Discriminative models are used to evaluate the weights between nodes.The solution sought is the cuts of the minimum energy.)deg(),()deg(),(),(minBBAcutABAcutBANcut  Ai BjjiSBAcut ),(),(  Ai GjjiSA ),()deg(NP-Hard!Computer VisionMarch 2004 L1.10© 2004 by Davi GeigerNormalized Cut and Normalized Association•Minimizing similarity between the groups, and maximizing similarity within the groups are achieved simultaneously.)deg(),()deg(),(),(BBBAssocAAAAssocBANassoc )deg(),()deg(),(),(BBAcutABAcutBANcut ),(),()deg(),(2),(AAAssocBAAssocAasBANassocBANcutComputer VisionMarch 2004 L1.11© 2004 by Davi GeigerSome definitions.1)(,}1,1{ in vector a be Let );,(),( matrix, diag. thebe DLet ;),( matrix, similarity thebe Let ,AiixxjiSiiDSjiSSNjji•Rewriting Normalized Cut in matrix form:... ),(),( ;11)1()1)(()1(11)1)(()1( )Bdeg(B)A,()Adeg(B)A,(B)A,(0ixTTTTiiDiiDkDkxSDxDkxSDxcutcutNcutiComputer VisionMarch 2004 L1.12© 2004 by Davi GeigerGeneralized Eigenvalue problem•after simplification, we get.01},,1{ with ,)(),(  DybyDyyySDyBANcutTiTTy2iiAy2iiADxxSD )(Computer VisionMarch 2004 L1.13© 2004 by Davi GeigerComputer VisionMarch 2004 L1.14© 2004 by Davi GeigerBrightness Image SegmentationComputer VisionMarch 2004 L1.15© 2004 by Davi GeigerBrightness Image SegmentationComputer VisionMarch 2004 L1.16© 2004 by Davi GeigerComputer VisionMarch 2004 L1.17© 2004 by Davi GeigerResults on color segmentationComputer VisionMarch 2004 L1.18© 2004 by Davi GeigerMotion Segmentation with Normalized Cuts•Networks of spatial-temporal connections:- Motion “proto-volume” in space-timeComputer VisionMarch 2004 L1.19© 2004 by Davi