Segmentation ECE 847: Digital Image Processing Stan Birchfield

Segmentation ECE 847: Digital Image Processing Stan Birchfield

Segmentation ECE 847: Digital Image Processing Stan Birchfield Clemson University What is segmentation? Segmentation divides an image into groups of pixels Pixels are grouped because they share some local property (gray level, color, texture, motion, etc.) 0 3 7 11 21 3 boundaries labels pseudocolors

mean colors (different ways of displaying the output) algorithm used: Pedro F. Felzenszwalb and Daniel P. Huttenlocher, Efficient Graph-Based Image Segmentation, IJCV, 59(2), 2004 S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Other variants Segmentation = partitioning Carve dense data set into (disjoint) regions Divide image based on pixel similarity Divide spatiotemporal volume based on image similarity (shot detection) Figure / ground separation (background subtraction) Regions can be overlapping (layers) Grouping = clustering Gather sets of items according to some model If items are dense, then essentially the same problem as above (e.g., clustering pixels) If items are sparse, then problem has a slightly different flavor: Collect tokens that lie on a line (robust line fitting) Collect pixels that share the same fundamental matrix (independent 3D rigid motion) Group 3D surface elements that belong to the same surface The problems are closely related, but we will treat

sparse clustering in a separate lecture (model fitting) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Foreground / background separation Background subtraction provides figure-ground separation, which is a type of segmentation C. Wren et al., Pfinder: Real-Time Tracking of the Human Body http://vismod.media.mit.edu/vismod/demos/pfinder/ Two errors oversegmentation (hair should be one group) undersegmentation (water should be separated from trees) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Outline Human segmentation Standard algorithms: Split-and-merge Region growing Minimum spanning tree

Watershed algorithm Normalized cuts An experiment: What do you see? Just six dots S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Now what do you see? Three groups of dot pairs Why? Dots that are close together (proximity) are grouped together by the human visual system S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 And now? Again, three groups of dot pairs Why? Dots are similar in appearance (similarity) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 How about now? Again, three groups of dot pairs

Why? Dots move similarly (common fate) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Last one Again, three groups of dots Why? Dots are enclosed together (common region) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 But wait! Note that the common region can overwhelm the proximity tendency S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Gestalt psychology Gestalt school of psychologists emphasized grouping as the key to understanding visual perception. Recall: Context affects how things are perceived gestalt whole or group gestalt qualitat set of internal relationships that

makes it a whole Max Wertheimer, Laws of Organization in Perceptual Forms, 1923 http://psy.ed.asu.edu/~classics/Wertheimer/Forms/forms.htm S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Gestalt psychology (cont.) Familiar configuration S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Muller-Lyer illusion Lines are perceived as components of a whole rather than as individual lines. S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 3D interpretation of Muller-Lyer from http://www.michaelbach.de/ot/sze_muelue/ Can you see anything invisible? These are illusory contours, formed by grouping the circles This is the well-known Kanizsa triangle S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 More illusory contours

Grouping by invisible completions S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Two final examples What role is top-down playing? from http://www-static.cc.gatech.edu/classes/AY2007/cs4495_fall/html/materials.html Back to computer vision Outline Human segmentation Standard algorithms: Split-and-merge Region growing Minimum spanning tree Watershed algorithm Normalized cuts Segmentation as partitioning A partition of image is collection of sets S1, .., SN such that I = S1 U S2 U SN (sets cover entire image)

Si Sj = 0 for all i j (sets do not overlap) A predicate H(Si) measures region homogeneity H( R ) = { true if pixels in region R are similar false otherwise We want 1. Regions to be homogeneous H( Si ) = true for all i 2. Adjacent regions to be different from each other H( Si U Sj ) = false for all adjacent Si , Sj S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Two approaches

Splitting (Divisive clustering) Merging (Agglomerative clustering) start with single region covering entire image start with each pixel as a separate region repeat: split inhomogeneous regions repeat: merge adjacent regions if union is homogeneous even better:

repeat: split cluster to yield two distant components (difficult) even better: repeat: merge two closest clusters Property 2 is always true: H( Si U Sj ) = false for adjacent regions Property 1 is always true: H( Si ) = true for every region Goal is to satisfy Property 1: H( Si ) = true for every region Goal is to satisfy Property 2: H( Si U Sj ) = false for adjacent regions In practice, merging works much better than splitting S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Region splitting Start with entire image as a single region Repeat:

Split any region that does not satisfy homogeneity criterion into subregions Quad-tree representation is convenient Then need to merge regions that have been split Aa Ab Aa Ada B Adc Add C D S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Split-and-Merge Split-and-merge algorithm combines these two ideas Split image into quadtree, where each region satisfies homogeneity criterion Merge neighboring regions if their union satisfies criterion (like connected components)

image after split after merge S. L. Horowitz and T. Pavlidis, Picture Segmentation by a Tree Traversal Algorithm, 1976 S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 When to merge two clusters Inter-cluster distance can be computed by single-link clustering (dist. b/w closest elements) allows adaptation complete-link clustering (dist. b/w farthest elements) avoids drift groupaverage singlelink completelink group-average clustering (use average distance) good compromise root clustering (dist. b/w initial points of clusters) variation on complete-link

S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Dendrograms Dendrogram yields a picture of output as clustering process continues raw data clusters represented as tree from http://en.wikipedia.org/wiki/Dendrogram S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example HCS (hierarchical clustering scheme) a 1 b 6 8 7 4 c 4

5 2 d 5 3 e S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example HCS (hierarchical clustering scheme) min ab c 4 4 ab 5 2 d

ab 5 4 4 e cd e 3 cde max a b c d e 8 c 6 8 ab

5 2 d 2 1 5 3 ab 4 3 ab 7 8 8 7 3 e cd

5 e cde 5 2 1 a b c d e S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Region growing Start with (random) seed pixel as cluster Repeat: Aggregate neighboring pixels that are similar to cluster model Update cluster model with newly incorporated pixels This is a generalized floodfill When cluster stops growing, begin with new seed pixel and

continue An easy cluster model: Store mean and covariance of pixels in cluster Use Mahalanobis distance to cluster This leads to a natural threshold, e.g., 2.5 Update mean and covariance efficiently by keeping track of sum(x) and sum(x2) One danger: Since multiple regions are not grown simultaneously, threshold must be appropriate, or else early regions will dominate S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Region growing S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Region growing results S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Region growing, balloons S. C. Zhu and A.L Yuille, Region Competition: Unifying Snake/balloon, Region Growing and Bayes/MDL/Energy for Multi-band Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, no.9, pp.884-900, Sept. 1996. Stochastic relaxation

Geman and Geman Markov Random Field (MRF) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Minimum spanning tree Agglomerative clustering can be implemented by building graph using pixels as nodes Repeated merging becomes finding a minimum spanning tree in a graph from Pedro F. Felzenszwalb and Daniel P. Huttenlocher, Efficient Graph-Based Image Segmentation, IJCV, 59(2), 2004 http://people.cs.uchicago.edu/~pff/segment/ MST advantages Minimum spanning tree (MST) answers two important questions unaddressed by region growing: How to select the starting pixels? Among the several pixels adjacent to the region, which should be considered next? S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Image as a graph

Graph G=(V,E) ... ... vertices edges each pixel is a node in the graph vertex v is just a number v 0 edge e=(u,v) is a pair of vertices If undirected graph, then (u,v) (v,u) If weighted graph, then w(e) is weight of edge S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example 2 4 1 0 3 8 3 1 5 4 2 6 image 2 3 1

1 5 4 5 2 2 1 4 2 1 2 4 1 5 graph (using absolute difference in intensities) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Minimum spanning tree path is sequence of vertices: v0, v1, v2, ..., vk

such that (vi,vi+1) is edge for all i graph is connected if there exists a path b/w each pair of vertices graph is tree if connected and acyclic (no cycles) Examples: tree not a tree (contains a cycle) not a tree (not connected) Given a graph G=(V,E), the minimum spanning tree is a set of edges such that resulting graph is a tree the sum of all the edge weights is minimal S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskals MST algorithm 1. Initialize each vertex as separate set (or component or region) 2. Sort edges of E by weight (nondecreasing order) 3. T = (empty set) 4. for each edge (u,v) 1. if FindSet(u) FindSet(v) 1. T = T U {(u,v)} 2. Merge( u, v )

5. return T greedy algorithm yet optimal S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal implementation Kruskals algorithm is implemented similar to connected components that we saw before disjoint set data structure (equivalence table): a b c d e f g h i FindSet(u) recursively traces links (GetEquivalentLabel)

Merge(u,v) simply adds link b/w u and v (SetEquivalence) How does this relate to image segmentation? This procedure relates to a single image region; it finds the MST of each region inS.the image. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskals MST algorithm S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal example 8 7 9 6 1 0 9 2 2 1 a 2b 2 d 5 6 1e 9

3g 7 1h 0 2i image c f Minimum spanning tree graph sorted edges: a b a a b c c d e d e

e f g f g h hi h i disjoint set data structure S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal example 8 7 9 6 1 0 9 2 2 image 1 a 2b 2 d 5 6 1e 9

3g 7 1h 0 2i c f Minimum spanning tree (after step 4) graph sorted edges: a a a b b c d e d e e g e e

f g h i disjoint set data structure S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal example 8 7 9 6 1 0 9 2 2 1 a 2b 2 d 5 6 1e 9 3g 7 1h 0

2i image c f Minimum spanning tree (after step 7) graph sorted edges: a a a b a c a e e d e f g g e h

e i disjoint set data structure S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal example 8 7 9 6 1 0 9 2 2 Note: Pixels grouped correctly! image 1 a 2b 2 d 5 6 1e 9 3g 7

1h 0 2i c f Minimum spanning tree (before last step) graph sorted edges: a a a b a c a e e d e f a g

e h e i disjoint set data structure S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Kruskal example 8 7 9 6 1 0 9 2 2 1 a 2b 2 d 5 6 1e 9 3g 7

1h 0 2i image c f Minimum spanning tree (final) graph sorted edges: a a a b a c a a a d e f a g

a h a i disjoint set data structure S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 MST image segmentation First, smooth image by convolving with Gaussian Small variance (e.g., 2=0.5) is fine This step is important to produce floating point weights for edges Build graph from image: vertices are pixels edges connect adjacent vertices (e.g., 4-adjacency) edge weights are absolute intensity differences: w(u,v) = | I(u) I(v) | Run Kruskals algorithm on the graph, but only merge two regions if certain criteria are met While running the algorithm, we have a forest (set of trees)

properties are maintained for each tree trees are merged based on criteria (but we dont care about the trees themselves, so we only need to store the regions, i.e., the set of pixels not edges) When the algorithm finishes, the individual trees are the image regions S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 MST image segmentation (Felzenszwalb-Huttenlocher IJCV 2004) Initialize each pixel as separate set (or component or region) Sort edges of E by weight (nondecreasing order) for each edge (u,v) if FindSet(u) FindSet(v) and Note: weight must w(u,v) < min( mu + k/Nu, be floating point, b/c w(u,v) m mv + k/Nv) (since edges are

u considered in non-decreasing order); otherwise, once k/Nu < 1, no more merging will occur Merge( u, v ) } extra conditions mu = maximum weight of all edges in u MST Nu = number of pixels in u region kS.=Birchfield, parameter (e.g., 150 or 300) Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 MST image segmentation (oversimplified version does not work)

Initialize each pixel as separate set (or component or region) Sort edges of E by weight (nondecreasing order) for each edge (u,v) if FindSet(u) FindSet(v) and (w(u,v) < mu and w(u,v) < mv) or (Nu < k and Nv < k) Merge( u, v ) } extra conditions mu = maximum weight of all edges in u MST Nu = number of pixels in u region kS.=Birchfield, parameter (minimum region size) Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 MST image segmentation for each region, disjoint set data structure contains: max edge weight of all edges in regions MST number of pixels in region max edge weight:

num pixels: a b c d e f g h i Merge(u,v) is easy: set max edge weight to max of two values set num pixels to sum of two values S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 MST segmentation smoothing necessary for IsSimilar2 to work weights must be floats! do not use integer division!

(FindSet is redundant if u v passed instead) w will always be maximum } S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Segmentation examples from Pedro F. Felzenszwalb and Daniel P. Huttenlocher, Efficient Graph-Based Image Segmentation, IJCV, 59(2), 2004 http://people.cs.uchicago.edu/~pff/segment/ More examples * * Pictures from Mean Shift: A Robust Approach toward Feature Space Analysis, by D. Comaniciu and P. Meer http://www.caip.rutgers.edu/~comanici/MSPAMI/msPamiResults.htm Outline Human segmentation Standard algorithms: Split-and-merge Region growing Minimum spanning tree Watershed algorithm Normalized cuts

Watershed segmentation Interpret (gradient magnitude) image as topographical surface: watershed line catchment basin All pixels in catchment basin are connected to minimum by monotonically decreasing path S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed algorithms Water immersion (Vincent-Soille) Puncture hole at each local minimum, immerse in water Grow level by level, starting with dark pixels Sorting step: For efficiency, precompute for each graylevel a list of pixels with that graylevel (histogram with pointers) Flooding step: Then, repeat: Breadth-first search (floodfill) of level g given flooding up to level g-1 For each pixel with value g, either assign to closest catchment basin or declare new catchment basin (geodesic influence zone) Tobogganing Find downstream path from each pixel to local minimum Difficult to define for discrete (quantized) images because of plateaus

S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Vincent-Soille algorithm new basin created g-1 g multiple basins extended: decision chosen by breadth-first search basin extended S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed from Gonzalez and Woods, Digital Image Processing Traditional watershed uses dams (But our implementation does not need dams) Watershed results (But the results from our implementation will be better than this) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Watershed leads to oversegmentation S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Markers solve this problem S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed Threshold image Compute chamfer distance Run watershed to get lines between objects Set these lines (skeletons) and blobs to zero in the gradient magnitude image for each x, y: grad(x,y) = max( grad(x,y), 1 ) if marker(x,y), grad(x,y) = 0 (Alternatively, use separate gradient and marker images) Only allow new basins where the value is zero S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Simplified Vincent-Soilles algorithm (Marker-based) only needs to be done once initially (can use connected components) { marker[p] = true (floodfill using marker image) (FIFO queue is important use std::queue or std::deque) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Simplified Vincent-Soilles algorithm (in detail) (Marker-based) only needs to be done once initially (can use connected components) {

FIFO queue is important to ensure that regions grow at equal rates (breadth-first search) (use std::queue or std::deque) marker( p ) = true (floodfill using marker image) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Simplified Vincent-Soilles algorithm (in detail) Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1

3 4 1 3 8 6 3 2 4 2 1 gradmag image S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1

5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 gradmag image 0: (1,3) 1: 2: 3: 4: 5: 6: 7: 8:

9: pixel list Step 1: Compute pixel list S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3

8 6 3 2 4 2 1 gradmag image 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: 3: 4: 5: 6: 7: 8: 9: Step 1: pixel list Compute pixel list S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4

3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 gradmag image 0: (1,3)

1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: 4: 5: 6: 7: 8: 9: Step 1: pixel list Compute pixel list S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7

1 3 4 1 3 8 6 3 2 4 2 1 gradmag image 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 1: pixel list Compute pixel list

S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4

2 1 u u u u u u u u u u u u u u u u u u u u u u u

u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 2: pixel list Set all pixels to unlabeled S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u

u u u u u u u u u u u u u u u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4)

2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 3: k=0 pixel list Grow catchment basins (none to grow) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2

7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u u u u u u u u

u u u u u u u u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1)

Step 4: k=0 pixel list Expand frontier (no frontier yet) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8

6 3 2 4 2 1 u u u u u u u u 0 u u u u u u u u u u

u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 5: k=0 pixel list Create new catchment basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example

8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1

u u u u u u u u 0 0 u u u 0 u u u u u u u u u u u

gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 6: k=1 pixel list Grow catchment basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u

u u u 0 0 u u u 0 u u u u u u u u u u u gradmag image labels (shaded pixels are on frontier)

0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 7: k=1 pixel list Expand frontier (nowhere to go) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1

5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u u u u 0 0

u u u 0 u u 1 u u u u u u u 2 gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4)

7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 8: k=1 pixel list Create new basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4

1 3 8 6 3 2 4 2 1 u u u u u u u 0 0 0 u 1 u 0 u u

1 u u u u 1 u 2 2 gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 9: k=2 pixel list

Grow basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3

2 4 2 1 u u u u u u u 0 0 0 u 1 u 0 u u 1 u u u u

1 u 2 2 gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 10: k=2 pixel list Expand frontier (nowhere to go) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Watershed example

8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1

u u u u u u u 0 0 0 u 1 u 0 u u 1 u u u u 1 u 2 2

gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 11: k=2 pixel list Create new basins (none to create) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Fast forward Watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 0 0 0 0 0

0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 2 2 gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4)

2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) pixel list Final result (but note that ties can be broken in other ways) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7

1 3 4 1 3 8 6 3 2 4 2 1 There are two markers here, indicated by gradmag image S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u

u u u u u u u u u u u u u u u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4)

2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Steps 1 and 2 pixel list (initialization) are the same as before S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2

7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u u u u u u u u

u u u u u u u u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1)

Step 3: k=0 pixel list Grow catchment basins (none to grow) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3

8 6 3 2 4 2 1 u u u u u u u u u u u u u u u u u u

u u u u u u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 4: k=0 pixel list Expand frontier (no frontier yet) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2

1 u u u u u u u u 0 u u u u u u u u u u u u u 1 u

u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 5: k=0 pixel list Create new catchment basins (at markers) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u

u u u 0 0 u u u 0 u u u u u u u u 1 u u gradmag image labels (shaded pixels are on frontier)

0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 6: k=1 pixel list Grow catchment basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0

1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u u u u 0

0 u u u 0 u u u u u u u u 1 u u gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4)

4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 7: k=1 pixel list Expand frontier (nowhere to expand) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2

7 1 3 4 1 3 8 6 3 2 4 2 1 u u u u u u u u 0 0 u u

u 0 u u u u u u u u 1 u u gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1)

Skip step to create pixel list new catchment basins, because this is only done at markers S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3

8 6 3 2 4 2 1 u u u u u u u 0 0 0 u u u 0 u u u u

u u u 1 1 1 u gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 8: k=2 pixel list Grow catchment basins

S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2

4 2 1 u u u u u u u 0 0 0 u 1 u 0 u u 1 u u u u 1

1 1 1 gradmag image labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 9: k=2 pixel list Expand frontier S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8

9 4 3 6 7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u

u u 0 u u u 0 0 0 u 1 u 0 0 u 1 1 u u 1 1 1 1 1 gradmag image

labels (shaded pixels are on frontier) 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 10: k=3 pixel list Grow catchment basins S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed example 8 9 4 3 6

7 6 2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 u u u 0 u

u u 0 0 0 u 1 u 0 0 u 1 1 u u 1 1 1 1 1 gradmag image labels (shaded pixels are on frontier)

0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4) 4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) Step 11: k=3 pixel list Expand frontier (nowhere to expand) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Fast forward Marker-based watershed example 8 9 4 3 6 7 6

2 0 1 5 2 7 1 3 4 1 3 8 6 3 2 4 2 1 0 0 0 0 0 0 0

0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 gradmag image labels 0: (1,3) 1: (3,1), (2,3), (1,4), (4,4) 2: (2,1), (4,1), (1,2), (4,3) 3: (4,0), (3,2), (0,3), (2,4)

4: (3,0), (0,2), (4,2) 5: (2,0) 6: (1,1), (0,4), (3,4) 7: (1,0), (2,2) 8: (0,0), (3,3) 9: (0,1) pixel list Final result (but note that ties can be broken in other ways) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Marker-based watershed threshold chamfer watershed edges image or markers gradient magnitude watershed S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Why are ridges needed? threshold Ridge markers define background region Without them, one object will spill over into background and disappear image markers gradient magnitude watershed S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Another example image markers gradient magnitude watershed S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Outline Human segmentation Standard algorithms: Split-and-merge Region growing Minimum spanning tree Watershed algorithm Normalized cuts Graph theoretic clustering Represent tokens (which are associated with each pixel) using a weighted graph. affinity matrix (pij has affinity of 0) Cut up this graph to get subgraphs with strong interior links and weaker exterior links Application to vision originated with Shi and Malik at Berkeley S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Graph Representations a c d b

e 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0

1 1 0 Adjacency Matrix: W * From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Weighted Graphs a b c e 6 d 0 1 3 0 0 1

0 4 0 2 3 4 0 6 7 0 0 6 0 1 0 2 7 1 0 Weight Matrix: W * From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Minimum Cut A cut of a graph G is the set of

edges S such that removal of S from G disconnects G. Minimum cut is the cut of minimum weight, where weight of cut is given as w A, B xA, yB w x, y * From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Minimum Cut and Clustering * From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Image Segmentation & Minimum Cut Pixel Neighborhood Image Pixels w Similarity Measure Minimum Cut

* From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Minimum Cut There can be more than one minimum cut in a given graph All minimum cuts of a graph can be found in polynomial time1. H. Nagamochi, K. Nishimura and T. Ibaraki, Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10 (1997) 469-481. 1 * From Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Finding the Minimal Cuts: Spectral Clustering Overview Data Similarities Block-Detection * Slides from Dan Klein, Sep Kamvar, Chris Manning, Natural Language Group Stanford University Eigenvectors and Blocks Block matrices have block eigenvectors: 1= 2

2= 2 1 1 0 0 .71 0 1 1 0 0 .71 0 0 0

1 1 0 .71 0 0 1 1 0 .71 eigensolver 3= 0 4= 0 Near-block matrices have near-block eigenvectors: [Ng = -0.02 = -0.02 = 2.02 = 2.02

et al., NIPS 02] 1 3 2 1 1 .2 0 .71 0 1 1 0 -.2 .69 -.14

.2 0 1 1 .14 .69 0 -.2 1 1 0 .71 eigensolver 4 * Slides from Dan Klein, Sep Kamvar, Chris Manning, Natural Language Group Stanford University

Spectral Space e Can put items into blocks by eigenvectors: 1 1 1 .2 0 .71 0 1 1 0 -.2 .69 -.14

.2 0 1 1 .14 .69 0 -.2 1 1 0 .71 e1 e2 e2

Resulting clusters independent of row ordering: e1 1 .2 1 0 .71 0 .2 1 0 1 .14 .69 1 0

1 -.2 .69 -.14 0 1 -.2 1 0 .71 e1 e2 e2 * Slides from Dan Klein, Sep Kamvar, Chris Manning, Natural Language Group Stanford University The Spectral Advantage

The key advantage of spectral clustering is the spectral space representation: * Slides from Dan Klein, Sep Kamvar, Chris Manning, Natural Language Group Stanford University Clustering and Classification Once our data is in spectral space: Clustering Classification * Slides from Dan Klein, Sep Kamvar, Chris Manning, Natural Language Group Stanford University Measuring Affinity Intensity 1 2 aff x, yexp I x I y 2 2 i

Distance 2 aff x, yexp 1 2 x y 2 d Texture 2 aff x, yexp 1 2 cx cy 2 t * From Marc Pollefeys COMP 256 2003

Scale affects affinity affinity matrix: Four isotropic Gaussians are sampled: eigenvalues: data=0.2 Four large eigenvalues Drawbacks of Minimum Cut Weight of cut is directly proportional to the number of edges in the cut. Cuts with lesser weight than the ideal cut Ideal Cut * Slide from Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Graph cut A B

Goal is to split an image into two regions A and B The cost of the cut is the sum of the edge weights between the two regions: Note: We will assume undirected graph: S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Example A B S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example 1 A (large values) 7 6 1 3 7 8 3 0 5 9 2 4 image B

(small values) 0 2 1 4 5 2 1 5 7 2 2 1 graph 3 2 3 3 max cut

(using absolute difference in intensities) But no one knows how to compute max cut S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example (cont.) So we flip values around 6 A (large values) 7 6 1 3 7 8 3 0 5 9 2 4 image B (small values) 7 5 6 3 2 5

6 2 0 5 5 6 graph 4 5 4 4 min cut Here we flip using v = 7-v, but v=exp(-v2/22) is more common S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example (cont.) But if image were bigger 6 7 6 1 3 7 8 3 0

5 9 2 4 image 7 5 6 3 2 5 6 2 0 5 5 6 graph 4 5 4 min cut 4

9 cut The min cut would favor the corners S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 An example (cont.) So we normalize 6 7 6 1 3 7 8 3 0 5 9 2 4 image 7 5 6 3 2 5 6 2 0

1 5 6 graph 2 5 6 cut 4 min cut S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Association We approximate the region size with the association which is the sum of the edge weights between pixels in A and all the pixels V The larger the region, the larger the association S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts

A B To solve this problem, define the normalized cut: =AUB cut where association Here the cost of the cut is normalized by the total connection from the nodes in A and B to all the nodes in the graph J. Shi and J. Malik, Normalized Cuts and Image Segmentation, PAMI 2000 S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts It is easy to see that for any subgraphs A, B, and C Therefore, assuming : minimizing the normalized disassociation b/w groups = maximizing the normalized association w/i groups J. Shi and J. Malik, Normalized Cuts and Image Segmentation, PAMI 2000 S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Laplacian matrix What happens when you multiply a matrix by a binary vector on both sides? where S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Laplacian matrix Now define diagonal matrix D so that is the sum of row (or column) i of W, i.e., the total connection from node i to all other nodes (assuming W symmetric) What happens now? S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Laplacian matrix Putting these together, we see if W symmetric D-W is called the Laplacian matrix It is always positive semidefinite ( non-negative eigenvalues) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts

Straightforward substitution: If we let more derivation yields: S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts Solving the discrete problem is NP-hard Solution: Allow y to take on real values Then, to minimize Rayleigh quotient, solve generalized eigenvalue system: for eigenvector with minimum eigenvalue S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts But note that smallest eigenvalue will always be zero (=0 and y1=1), in which case all pixels are labeled A, and no pixels are labeled B Why? To avoid this trivial solution, we use second smallest eigenvalue by introducing constraint: This constraint is automatically satisfied : S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Why does constraint work? Convert generalized eigenvalue system into standard eigenvalue system: where Note that eigenvector with zero eigenvalue is always given by Therefore, eigenvector with zero eigenvalue of generalized system is Eigenvectors of symmetric matrix are mutually orthogonal: Therefore any other smallest is true for any non-trivial eigenvector. By minimizing with this constraint, we get the minimum non-trivial eigenvector

(i.e., the one with the second smallest eigenvalue) S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Normalized cuts Algorithm: Set up weighted graph G=(V,E) with vertices as pixels and edges between neighboring pixels Set weights to be a measure of similarity between nodes (color, texture, motion, proximity, ) Solve (D-W)y = D y for smallest eigenvectors (e.g., Lanczos method) Use eigenvector with second smallest eigenvalue to bipartition graph (by thresholding eigenvector) Note: second smallest eigenvalue of (D-W) is known as Fiedler value Recursively partition the segmented regions if necessary until all components are found S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847 Example Results Figure from Image and video segmentation: the normalised cut framework, by Shi and Malik, 1998 * Slide from Khurram Hassan-Shafique CAP5415 Computer Vision 2003 More Results F igure from Normalized cuts and image segmentation, Shi and Malik, 2000

* Slide from Khurram Hassan-Shafique CAP5415 Computer Vision 2003 Example I S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt Distance Matrix S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The second generalized eigenvector S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The first partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The second generalized eigenvector S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The second partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The fourth generalized eigenvector

S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The third partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt Example II S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The structure of the affinity matrix S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt Generalized eigenvalues S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The first partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The second partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The third partition

S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The fourth partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt The fifth partition S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt Relationship between Average, Ratio, and Normalized Cuts Continuous Formulation Discrete Formulation Finding Clumps Average Association Assoc(A,A)/|A| + Assoc(B,B)/|B| Wx=xx Finding Splits Normalized Cut Cut(A,B)/assoc(A,V)+ Cut(A,B)/assoc(B,V) =2

(assoc(A,A)/assoc(A,V) + assoc(B,B)/assoc(B,V)) (D-W)x=xDx Average Cut Cut(A,B)/|A| + Cut(A,B)/|B| (D-W)x=xx S. Agarwal, www-cse.ucsd.edu/classes/fa01/cse291/eigen.ppt Other topics in normalized cuts Nystrom method (Fowlkes et al. 2004) In practice, the affinity matrix has low rank The eigenvectors of the matrix can be approximated by linearly interpolating the eigenvectors of a randomly sampled submatrix Greatly improves performance Swendsen-Wang cuts (Barbu and Zhu 2005) Probabilistic way of turning off edges Allows more general energy functionals S. Birchfield, Clemson Univ., ECE 847, http://www.ces.clemson.edu/~stb/ece847

Recently Viewed Presentations

  • Volunteer Services - SOSC

    Volunteer Services - SOSC

    Information is sent directly to [email protected] each time a step in the process has been completed by the volunteer. Electronic Letter of Recommendations Electronic minor letter of recommendations truly make the entire process electronic.
  • Why does the UK need new houses? - For Geography Teachers

    Why does the UK need new houses? - For Geography Teachers

    Why does the UK need new houses? Lesson 1 What factors affect population changes? How does that impact on the need for new homes? Why does the UK need new houses? How has the UK's population changed in the last...
  • SmartArt Graphics - Davis 9: BIM 1 Class

    SmartArt Graphics - Davis 9: BIM 1 Class

    SmartArt Graphics. Word has a variety of SmartArt graphics which you can use to illustrate and organize many different types of ideas. To get the most out of SmartArt, you'll need to know how to insert a SmartArt graphic, modify...
  • UH-60 LIMITS ENG %RPM 1 & 2 12

    UH-60 LIMITS ENG %RPM 1 & 2 12

    UH-60 LIMITS AIRSPEED LIMITS 193 Vne 180 Landing Light Ext. Search Light Ext. 170 1 Hyd Pump Inop 1 SAS Inop Gunner Win. Open 155 Skis Installed 150 Auto <16825 GW 2 Hyd Pump Inop 2 SAS Inop 145 Cabin...
  • Introduction to Animal Evolution

    Introduction to Animal Evolution

    Introduction to Animal Evolution AP Biology Crosby High School Characteristics of an Animal Multicellular, heterotrophic eukaryotes No cell wall Nervous tissue and muscle tissue Life History (Sexual rep. dominated by 2n) Fertilization creates 2n zygote Cleavage divides into multiple cells...
  • Library Linkeda Data - Corso - ADLUG

    Library Linkeda Data - Corso - ADLUG

    i-Like: Architecture i-Like: Components Moodle + Mahara = Mahoodle: The world's most popular LMS + E-Portfolio integrated by their communities, allowing to join didactics and Social Learning. And is all Open Source! Semantic Engine: Analyze metadata and texts, look up...
  • International arbitration and commercial contracts Giuditta ...

    International arbitration and commercial contracts Giuditta ...

    Invalidity/unenforceability based on excess of power (c) The award deals with a difference not contemplated by or not falling within the terms of the submission to arbitration, or it contains decisions
  • Genetic Architecture of Complex Traits - AU Pure

    Genetic Architecture of Complex Traits - AU Pure

    Sensitivity of maize to climate change in Denmark: an analysis using impact response surface [email protected] Ozturk Isik.1, Sillebak K. Ib1, Baby Sanmohan1, Vejlin Jonas1, Olesen E. Jørgen1