Graph Cuts for Image Segmentation

Introduction

This paper presents a graph cut approach to the image segmentation task. Considering the image to be a directed graph with two nodes representing the source (object) and the sink (background), the authors propose a combinatorial optimization framework for image segmentation using $s/t$ graph cuts. This is the first global optimization object extraction technique that is extensible to beyond 2-D images.

Method

Modeling the image as an undirected graph, $$ G = \langle V,E \rangle $$ $$\boldsymbol{Vertices:} \ v \ \in V $$ $$\boldsymbol{Edges:} \ e \ \in E \subset V X V$$ $$\boldsymbol{Source:} \ S; \boldsymbol{Sink:} \ T$$

The goal is to compute the best cut for an optimal segmentation. The cost associated with each cut is the sum of the costs of the edges being cut, so $$ |C| = \sum_{e \in C} w_e $$

The segmentation energy associated with the 8- (or 26-) neighborhood system $N$ is vectorized based on whether the pixel belongs to the foreground or the background and is stored in A, is described by the cost function $$ E(A) = \lambda R(A) + B(A), \ \text{where}$$

$R(A)$ is the regional term and $B(A)$ is the boundary term.

$$ R(A) = \sum_{p \in P} R_P(A_P)$$$$ B(A) = \sum_{{p,q} \in N} B_{p,q} \delta_{A_p \neq A_q} $$ where $$ \delta_{A_p \neq A_q} = \begin{cases} 1, & \text{if}\ A_p \neq A_q \\ 0, & \text{otherwise} \end{cases} $$

The coefficient $\lambda \ (\geq 0)$ specifies the relative weighting of the region properties term w.r.t. the boundary properties term. There is an assumption here that the individual penalties for the assignment of pixel $p$ to the ‘object’ and ‘background’ labels are given, and are $R_p(“obj”)$ and $R_p(“bkg”)$ respectively. $$ R_p(“obj”) = - ln P(I_P | “obj”)$$$$ R_p(“bkg”) = - ln P(I_P | “bkg”) $$

The boundary property of segmentation penalizes for discontinuities between two pixels of similar intensities. Moreover, this penalty should also be formulated in a way so that it decreases as a function of distance between the two pixels. $$ B_{p,q} \propto exp\Big(-\frac{(I_p - I_q)^2}{2\sigma^2}\Big).\frac{1}{dist(p, q)} $$$$ B_{p,q} = \begin{cases} 1, & \text{if}\ I_p = I_q \\ 0.2, & \text{otherwise} \end{cases} $$

The paper also puts in hard constraints in order to reduce the search space for the minimum cost cut. A priori knowledge of the labels of certain pixels can be used to initialize the algorithm and to edit the results. Also, hard constraints placed in one frame or one 2D slice can be used to constrain the search space across frames or in 3D volumes respectively. Moreover, hard constraints can be employed in a two-stage method - first they help constrain the search space, and then the intensities of these marked (seeded) pixels (or voxels) can be used to learn the intensity distribution histograms for “object” and “background”.

Each pixel in the image has 2 types of undirected edges - $n-links$, representing neighborhood linkage, and $t-link$, representing linkages to each terminal. Assuming that the edge weights are non-negative, the minimum cost cut can be calculated in polynomial time via algorithms for two terminal graph cuts.

Additionally, segmentation edition can also be computer efficiently by placing additional seeds to rectify incorrectly segmented regions. The edited segmentation is also a globally optimal segmentation that satisfies additional constraints (new seed points). This is a really useful feature as the segmentation results can be efficiently edited and corrected with minimal user input.

Results and Discussion

The results shown in the paper clearly demonstrate that the algorithm is not restricted by the topological properties of the segments, which can be a really favorable approach while segmenting 3D medical images. Moreover, as mentioned before, placing hard constraints in only a few frames can help segment entire sequences of frames (or 3D volumes).

However, there is a rather restricted set of constraints that can be used for the segmentation process. The paper also admits that they do not optimize the second order properties of the segmentation boundary.