Image segmentation using SCIP

This advanced practical dealt with image segmentation. We used a mixed-interger programming framework called SCIP. To read more about the classes and functions defined by SCIP, please refer to its documentation.

In our problem, we get an input image.

Input image

The pixels in the input image are clustered in so-called superpixels. This reduces the number of variables and thereby makes the problem easier to solve. The color of a superpixel is defined as the average color of its pixels.

Superpixels

Finally, we get so-called master nodes as input. These are special superpixels, in that every segment contains exactly one of them. They are marked by \(t_1,\dots,t_5\) in the following image. Given this input, we want to cover the image with disjoint segments. The superpixels in each segment should be similar in color. They are marked by thick black lines in the image.

Master nodes and segments

Mathematically, the input is the following:

• \(\mathcal{S}\): set of superpixels
• \(T\subseteq\mathcal{S}\): set of master nodes
• \(\mathcal{P}\subset2^\mathcal{S}\): set of connected segments, which each contain extactly one master node
• \(y_s\geq0\): color of superpixel \(s\in\mathcal{S}\)
• \(k=|T|\): number of segments to cover the image with
• \(r_P=\sum_{s\in P}|y_t-y_s|\): error of segment \(P\in\mathcal{P}\), where $t T$ is the single master node for which \(t\in P\)

The master problem is

\begin{align} &\min\quad \sum_{P\in\mathcal{P}} r_P\cdot x_P\\ &\text{s.t.}\quad \sum_{\{P\in\mathcal{P}:s\in P\}} x_P = 1 \quad\forall s\in\mathcal{S} \\ &\phantom{\text{s.t.}\quad} \sum_{P\in\mathcal{P}} x_P = k \\ &\phantom{\text{s.t.}\quad} x_P \in \{0,1\} \quad\forall P\in\mathcal{P} \end{align}

It is implemented in main.cpp.

Since there are exponentially many segments, we use column generation. Therefore, we need the dual problem, which has variables

• \(\mu_s\) for all \(s\in\mathcal{S}\): corresponding to the first constraint
• \(\lambda\): corresponding to second one The dual problem reads

  \begin{align} &\max\quad \sum_{s\in\mathcal{S}} \mu_s + k\cdot\lambda \\ &\text{s.t.}\quad \sum_{s\in P} \mu_s + \lambda \leq r_P \quad\forall P\in\mathcal{P} \\ &\phantom{\text{s.t.}\quad} \mu_s \text{ free} \quad\forall s\in\mathcal{S} \\ &\phantom{\text{s.t.}\quad} \lambda \text{ free} \end{align}

There is one pricing problem per master node \(t\). It has a binary variable \(x_s\) for every \(s\in\mathcal{S}\) and reads

\begin{align} &\min\quad \underbrace{\sum_{s\in\mathcal{S}} x_s\cdot|y_t-y_s|}_{=r_{\{s\in\mathcal{S}\ :\ x_s=1\}}} - \sum_{s\in\mathcal{S}} x_s\cdot\mu_s \\ &\text{s.t.}\quad \text{connectivity constraint} \\ &\phantom{\text{s.t.}\quad} x_t = 1 \\ &\phantom{\text{s.t.}\quad} x_{t'} = 0 \quad\forall t'\in T\setminus\{t\} \\ &\phantom{\text{s.t.}\quad} x_s \in\{0,1\} \quad\forall s\in\mathcal{S} \end{align}

The pricing problem, including a simple heuristic, is implemented in the class SegmentPricer.

To ensure connectivity of the new segment, we use a cutting planes approach. We look at the subgraph with vertices \(\{s\in\mathcal{S}:x_s=1\}\). If a component \(C\) is not connected to \(t\), we add a cut for each \(s\in C\):

\[\sum_{s'\in\delta(C)}x_{s'} \geq x_s\]

You can read more about this in the documentation for ConnectivityCons.