Image Segmentation

Image Segmentation

• The goal of image segmentation is to break apart an image into simpler components
• Another goal is to identify groups of pixels that go together

The Goals of Segmentation

• Separate image into coherent “objects”
• Group together similar-looking pixels for efficiency of further processing
• "Superpixels" are the result of grouping similar-looking pixels

Hard to Judge Success

• It is hard to find segmentations that are "correct"

Gestalt Factors

• Some Gestalt factors include Proximity, Similarity, Common Fate, Common Region, Parallelism, Symmetry, Continuity and Closure
• Continuity explains figures by occlusion

Image Segmentation: Toy Example

• The basis of a toy example is that three intensity levels define three groups: one black, one gray, and one white
• Pixels get labels based on grayscale value

Segmentation as Clustering

• Customize clustering by changing the feature space.
• You can group pixels based on intensity or color similarity
• You can also group on intensity and position similarity or by texture similiarty

K-Means Clustering

• K-means clustering randomly initializes k cluster centers
• The algorithm iterates between two steps until completion
• The cluster centers are randomly initialized
• Given cluster centers, determine points in each cluster by finding the closest center, p, for each point, ci then puts p into cluster i
• Given points in each cluster, solve for ci by setting c₁ to be the mean of points in cluster i
• If c₁ has changed, repeat step two

K-Means: Chicken and Egg Problem

• The cluster centers could be allocated points to groups by assigning each to its closest center
• The group memberships could get the centers by computing the mean per group

K-Means Properties

• K-means clustering will always converge to a solution
• K-means clustering might be a local minimum, and not the global minimum

K-Means: Pros and Cons

• Simple and fast to compute
• Converges to a local minimum of within-cluster squared error
• Difficult to set k
• Sensitive to the initial centers and outliers
• Detects spherical clusters

Alternative to K-Means: Estimating k

• In many applications, k, the number of clusters is unknown
• Approaches to estimate k are often based more on heuristics than principle
• An alternative approach is non-parametric clustering
• We may know an estimate of the size of clusters, but not the number of clusters

Mean Shift

• Mean Shift is an alternative to K-means clustering, therefore setting k is unnecessary
• Instead, the need of an estimate of the size of the clusters
• The iterative procedure is as follows:
  • Start a cluster at a random data point
  • Look at all points underneath the cluster and estimate a centroid
  • Move the cluster to be centered at that centroid
  • Repeat step two until the centriod stops changing
  • Repeat steps 1-4 for each data point
• Mean shift is a simple, robust, non-parametric iterative procedure useful for estimating peaks in a distribution

Images as Complete Graphs

• Images can be depicted as fully-connected graphs
• Every pixel is a node(vertex) on a graph
• A link connects every pair of pixels, p,q
• Affinity weight Wpq for each link (edge), measures similarity

Segmentation by Graph Partitioning

• The graph breaks into Segments
• The algorithm deletes links that cross between segments
• The easiest links to break are those with low similarity
• Similar pixels are in the same segments
• Dissimilar pixels are in different segments

Cuts In a Graph

• Graph Cut is the set of links whose removal makes a great disconnected
• The cost of a graph cut is cut(A,B) = ∑ Wp.q
• A minimum must can be found using fast algorithms
• The weight of a minimum cut is proportional to the number of edges in the cut which tends to produce small, isolated components

Normalized Cut Definition

• Fix bias of Min Cut by normalizing for size of segments:
• Ncut(A, B) ​= ​_cut(A, B)_ / assoc(A) ​+ ​_cut(A, B)/ assoc(B)_
• Assoc(A) = sum of weights of all edges the touch A
• An approximate solution for minimizing the Ncut value: generalized eigenvalue problem

Computing Normalized Cuts

• Shown as equivalent to an interger programming problem, i.e.: minimize

  • y^(T) (D-W) y / y^(T (Dy)

  • Subject to the constraint that yi∈{1,b} and y^(T)D1= 0 where 1 vector of all 1's

• W, the affinity matrix
• D, the degree matrix (diagonal)

Approximating Normalized Cuts

• Integer programming problem is NP hard, so we must find an efficient approximation
• Instead simply solve continuous (real-valued)version
  • This corresponds to finding second smallest eigenvector of (D – W)y₁ = λ¡ Dyi

Spectral Analysis

• Examines the Eigen-decomposition of a graphs's Laplacian matrix
• The Laplacian of graph is N x N matrix
  • l(i, j) := deg(vi), if i = j , -1 if i ≠ j, and vi is adjacent to v, 0 otherwise
• The eigendecomposition is graph invariant meaning that i.e. not affected by renumbering nodes
• The eigenvalues of the Laplacian matrix of a graph have some interesting information
  • The second-smallest eigenvalue is a measure of the graph's connectivity
  • The number of zero eigenvalues is equalt to the number of connected components in the graph

More Spectral Analysis

• The principal eigenvector gives a measure of each node's centrality
  • Importance in garph, (PageRank uses a variant of this)
• The second smallest eigenvector partitions the graph into two tightly connected components

Normalized Cuts

• Created by Shi & Malik, 2000.
• The algorithm:
  • Build complete graph with affinity weights
  • Run eigendecomposition
  • Partition graph according to second smallest eigenvector
  • Recursively perform the first step on each partition

Normalized Cuts: Pros and Cons

• Pros:
  • Generic framework, flexible to choice of function that computes weights ("affinities") between nodes
  • Does not require model of the data distribution
  • Works well in practice
• Cons:
  • Time complexity can be high
  • Dense, highly connected garphs lead to many affinity computations for Solving eigenvalue problem
  • Preference for balances partitions

Minimum Spanning Trees (MST)

• Suppose edges are weighted
• The intention is a spanning tree of mimimum cost (sum of edge weights)

Kruskal's Algorithm

• Find a min weight edge
  • if it forms a cycles with edges already taken, throw it out, otherwise keep it

Back to Image Segmentation

• The goal is to reduce an image to a samll number of homogeneous regions ("segments")

Segmentation as a Graph Problem

• Represent an image as a graph
  • Vertices represent the image pixels
  • Edges bwetween adjacent pixels
  • Edge weights give differnce in color beiwwn pixels
• Goal: Find a small member of homoegeneous regions in the graph, such that the sum of edge weights in each composnent is low
• We can do this by finding a minumum spanning tree and then removing a few high weight edges

Felzenswalb & Huttenlocher Algorithm

• This algorithm considers properties of components, rather than edges when adding an edge
• The algorithm will only link components if the differsnce between tem is much less than differnce within them
  1. Sorts edges into (ei..en) by increasing weights
  2. Inuitalize S with one component per pixel
  3. For each ea in (e1...en) do:
  • if weights of ea a samll relatibe to internal difference of components, it connects

Running Time of F&H

• O( n log n) for surting in step 1 and O (n a(n)) for the remain steps
• Using unoion-find with math compression to reoresent the particion S

Recognition through Segmentation

• Many vision systems have tried to segmentation as an ideremdiate step,:
  1. Do segmentation on an image
  2. compute features (shape, color, etc.) for each segment
  3. Deciede wether each segment is a object or not

Segmentation: Caveats

• Image of setmenation is not a bottom-up problem
  • needs of ne dome a recognition simultaneouly
• Segmentation makes hard decisions
  • Making wrong decision can ne catastrophic for later steps if a system
• Difficult to avaluate; when is a segmentation succesful?