CV Chapter 3 Segmentation

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

Theorem is that max-flow equals min-cut

1. 1951 Dantzig with O(n²mU)

2. 1997 Goldberg and Rao with O(x*log(n²/m)logU) with x is m^3/2 or n^2/3*m

3. n is #nodes m is #edges and U is maximum edge weight

1. Find source→sink path with positive capacity

2. Push maximum possible flow through path

3. Repeat until all paths are full

4. All full edges belong to cut

1. For cv with grid graphs with low connectivity

2. Dual search tree augmenting path algorithm (Boykov and Kolmogorov 2004)

2001 Boykov and Jolly with GrabCut

1. Interactive image segmentation // Fore- and background labeled with brush or bounding box

2. In newest version of MS Office

1. Object is coherent set of pixels

2. Psi(x,y)=gamma* Sum_mn delta(xn!=xm)*e(-beta*|ym-yn|²) //How to choose gamma?

1. Powerful based on MRF

2. Applicable for wide range of problems

3. Efficient for cv problems

4. Becoming standard

1. Limited class of models

2. Only approximative for multi-label cases

1. Limitation to binary energies is often nuisance

2. Problem is NP-hard with \geq 3 labels

Approximation algorithms for multi-label cases which are no guarantee for optimum

1. alpha-Expansion and 2. alphaBeta-Swap

1. Start with any initial solution

2. For each label compute optima s-t graph cut with energy decrease

3. Stop if no expansion would decrease energy

1. What things should be grouped?

2. What cues indicate groups?

1. “Grouping key to visual perception”

2. Elements of collection can have properties resulting from relations

3. “Whole is greater than sum of its parts”

1. Not grouped // . . . .

2. Proximity // .. .. .. ..

3. Similarity// ***..***

4. Common fate and region

5. Parallelism // << || >>

6. Symmetry // >< || <>

7. Continuity// Edges

8. Closure // o <>

1. Difficult for algorithms

2. Occlusion covers above factors

Group of pixel that belong together

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)