CV Chapter 3 Segmentation

1. Find representative centers and map pixels to nearest

2. Center minimizing SSD Sum|p-c|²

3. Center → Membership and Membership → Center

1. Randomly initialize k cluster center

2. Determine points for centers

3. If center is false for points update and repeat

1. Will find local but not always global minimum

2. Choose next proportional to |p-c|² till k centers with error O(log k)*optimal

1. Simple and fast

2. Converges to local minimum within cluster squared error

1. Which k? // NP-hard for even k=2

2. Sensitive to initial centers and outliers

3. Detects only convex clusters

4. Assuming means

1. 1D intensity similarity // Extended by position

2. 3D color similarity

3. 24D texture similarity // Possibilities from black to white

1. What is the probability that point p belongs to cluster c?

2. What is the shape of the cluster c?

Assume that pixel are generated by continuous function

1. K Gaussian blobs with means mye_j cov matrices Sigma_j and dim D

2. p(x|theta_j) = 1/2pi^(D/2)*|Sigma_j|^(1/2) * exp(-1/2 *(x-mye_)^T *Sigma_j^-1 *(x-mye_j) )

3. Select blob j with probability pi_j

4. Likelihood of x is weighted mixture of Gaussians p(x|theta) = Sigma_j^K pi_j(x|theta_j)

1. Maximize p(data|theta) = Prod_n^N p(x_n|theta)

2. Current blobs → Ownership // Expectation

3. Ownership probabilities → Update blobs // Maximization

gamma_j(xn_) ← value_j / Sigma_k^K value_k with value_j =pi_j * N(x_n|mye_j,Sigma_j)

1. N_j ← Sum_n^N gamma_j(x_n)

2. pi_j^new ← N_j/N

3. mye_j^new ← 1/N_j * Sigma_n^N gamma_j(x_n)*x_n

4. Sigma_j^new ← 1/N_j * Sigma_n^N gamma_j(x_n)*(x_n-mye_j^new)^(T+1)

1. Any clustering problem // Any model estimation problem

2. Missing data problem and finding outliers

3. segmentation problems color motion fore/background

1. Soft assignments between data and cluster

2. Generative model can predict novel points

3. Compact storage

1. Initialization // With some k-means iterations

2. Unknown number of components // Solution with model selection (AIC, BIC), Dirichlet process mixture

3. Which generative model?

1. Modes in histogram are local maximum of the density

2. Cluster is set of points in attraction of one mode

1. Initialize random seed and window W

2. Mean of W Sigma_xinW x*H(x)

3. Shift W to mean and redo 2. till convergence

1. Choose multiple windows

2. Run mean-shift segmentations parallel

3. Label the traversed points

1. Label all points choose in radius r

2. Label all points in search path

1. Model-free, no prior shape assumption

2. Only one parameter window size

3. Finds number of modes

4. Robust to outliers

1. Output depends on not trivial window size

2. Expensive (2s/image)

1. Rich probabilistic models for images

2. Lear local effects and get global effects out

3. Goal is to infer optimal labeling of MRF

1. Observed evidence on y-plane the image

2. Image scene compatibility function Phi(xi,yi)

3. Hidden true states on x-plane the scene

4. Neighborhood relations or scene scene compatibility function Psi(xi,xj)

Network joint probability p(x,y)=Prod_i Phi(xi,yi)* Prod_ij Psi(xi,xj)

Minimizing -log p(x,y)=-Sum_i log(Phi(xi,yi)) - Sum_ij log(Psi(xi,xj))

E(x,y) = Sum_i phi(xi,yi)) + Sum_ij psi(xi,xj)

1. Unary or single-node phi encoding local info // membership of pixel to a class

2. Pairwise psi encoding neighborhood info

1. Color modeled with MoG

2. Edge with contrast sensitive Potts model

1. Gibbs sampling

2. Simulated annealing

3. Iterated conditional modes (ICM)

4. Variational methods

5. Belief propagation

6. Graph cuts

1. Popular fast tool for certain class of energy functions

2. Convert MRF into source-sink graph (SSG)

3. Minimum cost cut with max-flow/min-cut in polynomial time

4. Only minimizes submodular binary energies (Boros and Hummer 2002)

1. E(s,s)+E(t,t)\leqE(s,t)+E(t,s)

2. Discrete equivalent to convexity

3. Every local is global minimum

1. wij = exp(- Diij/2*sigma²)

2. E(x,y) = Sum_i phi_i(xi) + Sum_ij wij * delta(xi!=xj)

1. Expect phi_i(s or t) ~ exp(-|Ii-(Is or It)|² /2*sigma²)

2. Is It are given expected intensities and can be re-estimated

3. Hard constrains are not required in general

4. Regional bias based on any intensity model with phi_i(Li)=-log p(Ii|Li) and Li s or t

1. Graph with vertices edges and costs

2. st-cut divides nodes between source and sink

3. Cost is sum of edges going from source to sink region

4. st-mincut has minimal cost