An Analysis of Normalized Cuts and Image Segmentation

Abstract

In this paper, a detailed summary and analysis over Shi and Malik’s paper on Normalized Cuts and Image Segmentation. Each section covers a summary and analysis of the respective portion of the original paper. The original paper can be found here: https://people.eecs.berkeley.edu/~malik/papers/SM-ncut.pdf

Wertheimer’s Perceptual Grouping Theory

In the introduction, Shi and Malik note that their research is based off of Wertheimer’s Perceptual Grouping Theory. This theory states that regions should be grouped together based on looking at the image on a higher level through objects and patterns.

Choosing the right Subset for Partitions

They notes that there are two key factors to choose the right subset when partitioning:

• Bayesian View of Subsets: You can look at a picture and classify it on a low level (brightness, color, texture, etc.) and mid/high level (symmetry, object Models, etc.)
• Hierarchy Partitions: Use low-level cues to form a hierarchical partition and Mid/High-Level knowledge to verify or selects new areas for the hierarchy. Essentially, go from the big picture downwards.

New Approach to Segmentation

On higher dimensional problems the greedy and gradient descent approach usually fails. The new approach uses grouping by splitting vertices into disjoint sets and keeping the similarity high within a set and low between sets. The partitions are then evaluated based on a loss known as a normalized cut.

Grouping as Graph Partitioning

Normalized Cut & Association: Previously, the regular cut was used as a loss function, however, it often cut isolated edges. In order to prevent this, a normalized cut was developed which used the cut as a fraction of the total edges. A similar method was used to normalize association.The goal of the Algorithm minimizing the disassociation between the groups and maximizing the association within the groups

Computing the Optimal Partition: Please note that for the sake of simplicity, most of the math has been omitted from the summary. In order the compute the optimal partition efficiently using the normalized cut, a generalized eigenvalue problem is solved. The eigenvalue problem is as follows:

(D-W)y = (lambda) (Dy)

The parts of the problem:

• D: An N x N (Where N = |V|) diagonal matrix
• W: An N x N symmetrical matrix such that W(i,j) = wij
• y: y = (1 + x) — b(1-x)

Check the original paper for the full details of each part of the eigenvalue system.

The Grouping Algorithm

There are four steps to the Grouping Algorithm proposed in this paper. In simple:

• First, get a graph of G = (V,E) and set weights to be the similarity between nodes.
• Solve (D-W)y = (lambda)Dy for the smallest eigenvalues
• Split the graph into two with the 2nd smallest eigenvalue’s eigenvector
• Recursively decide if another partition is necessary within current partitions

Some of the main points from each of the step include:

• Step 1: Uses spatial location and brightness value to determine the edge weight connecting the nodes
• Step 2: Finds the most useful eigenvector and eigenvalues using the Lanczos Method to decrease computation time
• Step 3: Since the eigenvectors are continuous, the splitting point is chosen where the resulting partition have the best Normalized Cut value.
• Step 4: Recursively partition and stop partitioning after Normalized Cut reaches a threshold. Additionally, ignore smoothly varying eigenvectors to avoid unstable cuts.

Recursive Two-Way Ncut: The Normalized Cut (Ncut) is the driving force that dictates how many partitions are allowed.

Simultaneous K-Way Cut with Multiple Eigenvectors: The Two-Way Ncut fails to cut oscillating eigenvectors and subsequent eigenvectors. Additionally, since it uses only the 2nd eigenvector, it is computationally wasteful.

K-Way Cut: The K-way cut will use the first n eigenvectors instead of one and uses a clustering algorithm to split it into groups. To exclude oscillating eigenvectors, there are 2 main approaches:

• Greedy Pruning: Iteratively merges 2 segments until only k segments are left.
• Global recursive Cut: Create a condensed version of the graph and recursively bipartition from there.

Experiments

In the experiments, a function, F(i), is used to output a feature vector based on the intensity, color, or texture. Through their experimentation, the algorithm grabs major components and ignores minor ones.

Motion Case: The image sequence is treated as a spatiotemporal dataset which is then used to calculate the motion distance through using the motion profile. A motion profile estimates the probability distribution of the image velocity.

Computation Time: There are two ways to reduce the computation time:

• Multiresolution Implementation: This is most effective to reduce time on larger images
• Parallel Computing: The matrix vector multiplication can be ran in parallel in future chips.

Choice of Graph Edge Weight: The weight function that was chosen for this problem:

w(x) = e^{(-d(x)/sigma)²}

This weight function was chosen for its versatility and simplicity but it is possible for weight functions to vary from region to region.

Relationship To Spectral Graph Theory

The idea of spectral graph theory is to describe properties of the original graph through studying the incidence and Laplacian matrix. The work presented in this paper relates to Spectral Graph Theory because it uses the theory to evaluate the approximation when compared to the normalized cut. Using work in spectral partitioning, the second smallest eigenvalue (Fiedler Value) often leads to a good ratio cut if the Fiedler Value is small.

Physical Interpretation: To analogize the eigenvalue System, a spring-mass system is presented. The parts of the analogy include:

• Physical Nodes: Represent the nodes within the system
• Spring: Connections between Nodes
• Spring Stiffness: Graph Edge Weight
• Mass: Total edge weight

The idea of this system is that when one node oscillates, nodes that have stronger weights attached to the oscillating node will also oscillate in a group. Weaker springs would then pop off, defining the partition of the image.

Relationship To other Graph Theoretic Approaches To Image Segmentation

Comparison with Related Eigenvector-Based Methods

• Similarity Between Normalized Cut and Average Cut: Both algorithms are trying to find a balanced partition.
• Similarity Between Normalized Association and Average Association: Both algorithms are trying to find tight clusters.

The average association has a bias for tight clusters and the average cut has bias for segmentation. However, a normalized cut tries to find a balance between clustering and segmentation.

Conclusion — Major Takeaways

• Perpetual Grouping should be from the top down. It should extract from the big picture and work its way down until it creates a hierarchial structure.
• Normalized Cut is a unbiased criteria; minimizing the normalized cut means maximizing the normalized association
• A generalized eigenvalue system is valuable in getting a real valued solution

Works Cited

• Shi,J., & Malik, J.(2000). Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 888–905