ECE 278 Final projectNormalized Cuts Normalized Cuts and Image Segmentationand Image SegmentationBaris SumengenJelena TešicVision Research LabElectrical and Computer engineeringJune 8, 2000Normalized CutsNormalized Cuts2Outlinen Introductionn Graph Partitioningn Grouping Algorithmn Experimentsn Resultsn Related Approachesn ConclusionJune 8, 2000Normalized CutsNormalized Cuts3Introductionn Segmentation method based on the paper by Jianbo Shi and JitendraMalik, CVPR 1997n Usage of low-level coherence of image attributes for candidate partitions generation n Set of points is presented as a weighted undirected graph G=(V, E) n Nodes of the graph – points in the feature spacen Weight W(i,j) – “distance measure” for nodes i and jnGraph Partitioning: nPrecise criterionnEfficient partition computationJune 8, 2000Normalized CutsNormalized Cuts4Graph Partitioningn Dissimilarity measure between two sets of graph G=(V, E), n Minimum cut Optimal bi-partitioningn Clustering method (Wu, Leathy, PAMI 1993) that favors outliersn Different cost function proposed: ,(,)(,)uAvBcutABwuv∈∈=∑,ABVAB∪=∩=∅(,)(,)(,)(,)(,)cutABcutABNcutABassoAVassoBV=+,(,)(,)uAtVassoAVwut∈∈=∑June 8, 2000Normalized CutsNormalized Cuts5Optimal Partitioning(,)ijdWij=∑n N – number of nodes in the graph Vn W – NxN symmetrical matrix with elements W(i,j)n D: n x – indication vector:n Final result:with the condition:12(,...,)NDdiagddd={}1,()1,()ixViAViA=+∈−∉()min()minTxyTyDWyNcutxyDy−=001,iiixiixdyd><−∈∑∑10TNdyd=MJune 8, 2000Normalized CutsNormalized Cuts6Optimal Partitioning- con’tn Solution comes from eigenvalue system:n Second constraint is satisfied for any eigenvector.Symmetric, semi-positive definite – Laplacian matrixn Using Rayleigh quotient and orthonormality of eigenvectors: Real valued solution to the Normalized Cut problem is the second smallest eigenvector of the generalized eigensystemn Graph is partitioned in two pieces using the second smallest eigenvaluen Ideal case: the signs of vector elements tells us how to split12zDy=()DWyDyλ−=1122()DDWDzzλ−−−=June 8, 2000Normalized CutsNormalized Cuts7The Grouping Algorithmn Use spatial proximity term and feature similarity terms to calculate weighted coefficients W(i,j)n Summarize information in W and Dn Find an approximate solution for the second smallest eigenvalue of the systemn Bipartition the graph by finding the best splitting point n Check the stability of the cut and decide on the current partition statusn Stop the recursion if Ncut exceeds certain limit()DWyDyλ−=June 8, 2000Normalized CutsNormalized Cuts8Experimentsn Different parameter values and feature desriptors222(,),ijijIXFFXXijWijeeXXrσσ−−−−=∗−<1(), intensity()[,sin(),cos()](),color[*,...,*](), texturenIiFivvshvshiIfIfi=ggggJune 8, 2000Normalized CutsNormalized Cuts9Results2 4 6 8 10 12 14 16 18 2024681012141618202 4 6 8 10 12 14 16 18 2024681012141618202 4 6 8 10 12 14 16 18 2024681012141618200.1,3.0,0.02,3.0IXrσσσ====0.1,5.0,0.01,4.0IXrσσσ====5 10 15 20 25 30510152025305 10 15 20 25 30510152025305 10 15 20 25 3051015202530June 8, 2000Normalized CutsNormalized Cuts105 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 3024681012141618205 10 15 20 25 302468101214161820June 8, 2000Normalized CutsNormalized Cuts115 10 15 20 25 302468101214165 10 15 20 25 30246810121416June 8, 2000Normalized CutsNormalized Cuts12Conclusionn Computational Complexityn Choice of Parametersn Stabilityn Heuristic methodsn