Graph theoretic formulation

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.

Normalized cuts

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

Let:

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B,V)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B,V)}}}$

In the normalized cuts approach,^[2] 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.

The ncut algorithm

Let:

${\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

Also, let D be an ${\displaystyle n\times n}$ diagonal matrix with ${\displaystyle d}$ on the diagonal, and let ${\displaystyle W}$ be an ${\displaystyle n\times n}$ symmetric matrix with ${\displaystyle w_{ij}=w_{ji}}$.

After some algebraic manipulations, we get:

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(D-W)y}{y^{T}Dy}}}$

subject to the constraints:

• ${\displaystyle y_{i}\in \{1,-b\}}$, for some constant ${\displaystyle -b}$
• ${\displaystyle y^{t}D1=0}$

Minimizing ${\displaystyle {\frac {y^{T}(D-W)y}{y^{T}Dy}}}$ subject to the constraints above is NP-hard. To make the problem tractable, we relax the constraints on ${\displaystyle y}$, and allow it to take real values. The relaxed problem can be solved by solving the generalized eigenvalue problem ${\displaystyle (D-W)y=\lambda Dy}$ for the second smallest generalized eigenvalue.

The partitioning algorithm:

1. Given a set of features, set up a weighted graph ${\displaystyle G=(V,E)}$, compute the weight of each edge, and summarize the information in ${\displaystyle D}$ and ${\displaystyle W}$.
2. Solve ${\displaystyle (D-W)y=\lambda Dy}$ for eigenvectors with the second smallest eigenvalues.
3. Use the eigenvector with the second smallest eigenvalue to bipartition the graph (e.g. grouping according to sign).
4. Decide if the current partition should be subdivided.
5. Recursively partition the segmented parts, if necessary.

Computational Complexity

Solving a standard eigenvalue problem for all eigenvectors (using the QR algorithm, for instance) takes ${\displaystyle O(n^{3})}$ time. This is impractical for image segmentation applications where ${\displaystyle n}$ is the number of pixels in the image.

Since only one eigenvector, corresponding to the second smallest generalized eigenvalue, is used by the uncut algorithm, efficiency can be dramatically improved if the solve of the corresponding eigenvalue problem is performed in a matrix-free fashion, i.e., without explicitly manipulating with or even computing the matrix W, as, e.g., in the Lanczos algorithm. Matrix-free methods require only a function that performs a matrix-vector product for a given vector, on every iteration. For image segmentation, the matrix W is typically sparse, with a number of nonzero entries ${\displaystyle O(n)}$, so such a matrix-vector product takes ${\displaystyle O(n)}$ time.

For high-resolution images, the second eigenvalue is often ill-conditioned, leading to slow convergence of iterative eigenvalue solvers, such as the Lanczos algorithm. Preconditioning is a key technology accelerating the convergence, e.g., in the matrix-free LOBPCG method. Computing the eigenvector using an optimally preconditioned matrix-free method takes ${\displaystyle O(n)}$ time, which is the optimal complexity, since the eigenvector has ${\displaystyle n}$ components.

Software Implementations

scikit-learn^[3] uses LOBPCG from SciPy with algebraic multigrid preconditioning for solving the eigenvalue problem for the graph Laplacian to perform image segmentation via spectral graph partitioning as first proposed in ^[4] and actually tested in ^[5] and.^[6]

Algorithm

1. Given an image D, an object category is chosen, e.g. cows or horses.
2. The corresponding LPS model is matched to D to obtain the samples ${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. The objective function given by equation (2) is determined by computing ${\displaystyle E(m,\Theta _{i})}$ and using ${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. The objective function is minimized using a single MINCUT operation to obtain the segmentation m.