The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily concerned with graph theoretic approaches to image segmentation applying graph partitioning via minimum cut or maximum cut. Segmentation-based object categorization can be viewed as a specific case of spectral clustering applied to image segmentation.

The set of points in an arbitrary feature space can be represented as a weighted undirected complete graph G = (V, E), where the nodes of the graph are the points in the feature space. The weight ${\displaystyle w_{ij}}$ of an edge ${\displaystyle (i,j)\in E}$ is a function of the similarity between the nodes ${\displaystyle i}$ and ${\displaystyle j}$. In this context, we can formulate the image segmentation problem as a graph partitioning problem that asks for a partition ${\displaystyle V_{1},\cdots ,V_{k}}$ of the vertex set ${\displaystyle V}$, where, according to some measure, the vertices in any set ${\displaystyle V_{i}}$ have high similarity, and the vertices in two different sets ${\displaystyle V_{i},V_{j}}$ have low similarity.

Let G = (V, E, w) be a weighted graph. Let ${\displaystyle A}$ and ${\displaystyle B}$ be two subsets of vertices.

Let:

In the normalized cuts approach, for any cut ${\displaystyle (S,{\overline {S}})}$ in ${\displaystyle G}$, ${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$ measures the similarity between different parts, and ${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$ measures the total similarity of vertices in the same part.

Since ${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$, a cut ${\displaystyle (S^{*},{\overline {S}}^{*})}$ that minimizes ${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$ also maximizes ${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$.

Computing a cut ${\displaystyle (S^{*},{\overline {S}}^{*})}$ that minimizes ${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$ is an NP-hard problem. However, we can find in polynomial time a cut ${\displaystyle (S,{\overline {S}})}$ of small normalized weight ${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$ using spectral techniques.

Let: