O. Veksler, Y. Boykov, P. Mehrani. Superpixels and supervoxels in an energy optimization framework. European Conference on Computer Vision, pages 211–224, 2010.

Veksler et al. propose a graph based superpixel algorithm - to be exact, the paper proposes two algorithms: Compact Superpixels and Constant Intensity Superpixels. In the following we focus on Constant Intensity Superpixels, as the algorithm shows better performance in practice. Note that we assume the image $I$ to be a grayscale image, however, the below description can easily be extended to color images. Initially the image is covered by overlapping squares such that each pixel is covered by multiple squares. Each square represents a superpixel and each pixel can get assigned to one of these squares. Then, the following energy is minimized using $\alpha$-expansion [1]:

$E(S) = \sum _{n = 1}^N\sum_{m = 1}^N w_{n,m} \psi_{n,m}(s(x_n), s(x_m)) + \sum_{n = 1}^N \theta_n(s(x_n))$

where $N$ is the number of pixels and $s(x_n)$ denotes the label of pixel $x_n$. Here, $\theta_n$ defines a data term which can be written as

$\theta_n(i) = |I(x_n) - I(S_i)|$, if $x_n$ is assigned to superpixel $S_i$, $0$ otherwise.

Note that this is a simplified formulation: Originally, instead of using the mean color $I(S_i)$ of the superpixel $S_i$, the color of the center pixel of the initial square is used (however, this would require to discuss an additional term enforcing this pixel to belong to $S_i$). Further, $\psi_{n,m}$ is a Potts model:

$\psi_{n,m}(i, j) = 1$, if $i \neq j$, $0$ otherwise.

The weights $w_{n,m}$ of neighboring pixels $x_n$ and $x_m$ are defined as follows:

$w_{n,m} = \lambda \exp\left(- \frac{(I(x_n) - I(x_m))^2}{2 \|x_n - x_m\|_2 \sigma^2}\right)$

where $\lambda$ is an adjustable parameter and $\sigma$ is set to the overall variance of the image.

Figure 1 shows superpixel segmentations obtained for images of the Berkeley Segmentation Dataset [2] using the original implementation available on Olga Veksler's webpage.

ba_bsd_4_cis ba_bsd_5_cis ba_bsd_6_cis ba_bsd_7_cis ba_bsd_8_cis

Figure 1 (click to enlarge): Superpixel segmentations obtained on images from the Berkeley Segmentation Dataset [2] using the Constant Intensity Superpixels algorithm.
  • [1] Y. Boykov, O. Veksler, R. Zabih. Fast approximate energy minimization via graph cuts. Transactions on Pattern Analysis and Machine Intelligence, Transactions on, pages 1222–1239, 2001.
  • [2] P. Arbeláez, M. Maire, C. Fowlkes, J. Malik. Contour detection and hierarchical image segmentation. Transactions on Pattern Analysis and Machine Intelligence, volume 33, number 5, pages 898–916, 2011.
What is your opinion on this article? Let me know your thoughts on Twitter @davidstutz92 or LinkedIn in/davidstutz92.