J. Shi, J. Malik. Normalized Cuts and Image Segmentation. Transactions on Pattern Analysis and Machine Intelligence, 2008.

This paper proposes a graph based image segmentation technique which can be applied to a given superpixel segmentation, as well. An image is interpreted as weighted undirected graph $G = (V,E)$. If a superpixel segmentation is given, each superpixel forms a node, otherwise each pixel represents a node. The goal is to bipartition the graph into two disjoint sets $A \subset V$ and $B \subset V$ by minimizing the normalized cut $NCut(A, B)$ given by

$NCut(A, B) = \frac{cut(A, B)}{assoc(A, V)} + \frac{cut(A, B)}{assoc(A, V)}$.

Here, $cut(A, B) = \sum_{u \in A, v \in B} w_{u,v}$ and $assoc(A ,V) = \sum_{u \in A, v \in V} w_{u,v}$ where $w_{u,v}$ denotes the weight between node $u$ and node $v$ (we assume a fully connected graph where $w_{u,v}$ may be zero).

As shown in the paper, this criterion can be minimized by discretizing the second smallest eigenvalue corresponding to the generalized eigenvalue problem

$(D - W)y = \lambda D y$.

Assuming the nodes to be consecutively numbered, the matrix $W$ holds the edge weights: $W_{u, v} = w_{u,v}$, and thus is symmetric. $D$ is a diagonal matrix where $D_{u,u} = \sum_{v \in V} w_{u,v}$. The edge weights $w_{u,v}$ can for example be defined as follows: $w_{u,v} = \exp(\| I(u) - I(v) \|_2^2/\sigma^2)$ if superpixels $u$ and $v$ have a common border, $w_{u,v} = 0$ otherwise. In this case, $I(u)$ denotes the color vector of the superpixel corresponding to node $u$ (this may be the mean color of the superpixel). The second smallest eigenvector needs to be discretized. Therefore, Shi et al. choose a threshold value minimizing the normalized cut. Further details can be found in the paper. Code is available online: original MatLab code and an implementation by Gori to generate superpixels.

What is your opinion on the summarized work? Or do you know related work that is of interest? Let me know your thoughts in the comments below: