7. Segmentation

In this chapter we are going to investigate a common task from computer vision, i.e., image segmentation. For this we want to partition the image domain \(\Omega \subset \R^d\) based on the features of an image \(f \colon \Omega \rightarrow \R^m\). First, we introduce the set of partitions of \(\Omega\) in which we have to search for a solution in image segmentation.

Definition 7.1 (Partition set)

Let \(\Omega \subset \R^n\), we call

\[\mathcal{P}_n \ \coloneqq \ \{ (\Omega_1, \dots, \Omega_n) \: : \: \Omega_i \neq \emptyset, \ \overline{\Omega} = \bigcup_{i=1}^n \Omega_i, \ \Omega_i \cap \Omega_j = \emptyset \ \forall i \neq j \}\]

the partition set of \(\Omega\).

In case of a gray value image, i.e., \(m = 1\), a simple idea is to binarize the image by separating intensities via a thresholding operation as defined in the following.

Definition 7.2 (Thresholding operation)

We transform a gray value image \(f \colon \Omega \rightarrow \R\) with respect to a threshold value \(t \in \R\) into a binary image \(B \colon \Omega \rightarrow \{0, 1\}\) via:

\[B(x) \ \coloneqq \ \begin{cases} 0, \quad &f(x) < t\quad \\ 1, \quad &f(x) \geq t. \end{cases}\]

The resulting binary image \(B\) can be seen as segmentation of \(\Omega\) into two compartments.

This reduces the problem of image segmentation to choosing the optimal threshold value \(t \in \R\). Often this is performed by statistical analysis of the image histogram, e.g., as performed in [] or [].

An alternative idea is to group image intensities based on defined criteria, which we denote as clustering, instead of separating them via thresholding. Clustering can be interpreted as unsupervised classification of patterns (observations, data items, or feature vectors) into groups, which we call clusters. This grouping is typically performed based on image features such as intensity values, local texture or gradient information.

Mathematically, we have a finite set of feature vectors \(\mathbf{f} := \{f_1, \dots f_N \}\) for \(N \in \N\) with \(f_i \in \R^n\). Our aim is to compute a reasonable partition \(P \in \mathcal{P}_f\) of the given data in different \(k \in \N\) clusters \(C_1, \dots C_k \subset \mathbf{f}\) for which the following conditions should hold:

1. The subregions \(\Omega_i \subset \Omega\) are homogeneous with respect to the given features \(\mathbf{f}\).

2. Neighbouring regions \(\Omega_i, \Omega_j \subset \Omega\) with \(\Omega_i \neq \Omega_j\) should be discriminable with respect to the given features \(\mathbf{f}\).

3. The subregions \(\Omega_i \subset \Omega\) should have simple geometry with smooth boundaries, i.e., no small holes, cusps, or frenzy boundaries.

A heuristic approach to compute such a clustering is to use the popular k-means algorithms. The idea is to group the data around representative feature vectors \(m := (m_1, \dots m_k)\) with \(m_i \in \R^n\) by minimizing the respective Euclidean distances to these representatives. For details see the lecture slides.