# DAVIDSTUTZ

Check out the latest superpixel benchmark — Superpixel Benchmark (2016) — and let me know your opinion! @david_stutz
07thJULY2015

Y. Zhang, R. Hartley, J. Mashford, S. Burn. Superpixels via pseudoboolean optimization. International Conference on Computer Vision, 2011.

Zhang et al. propose a graph-based superpixel algorithm. First, the image is covered by overlapping vertical and horizontal strips such that each pixel is covered by exactly two vertical and two horizontal strips. This way, considering only the horizontal strips, each pixel is either labeled 0 or 1. $N$ being the number of nodes (that is, pixels), an energy similar to the one used for Constant Intensity Superpixels [1] is used:

$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))$

except that the data term $\theta_n$ is set to zero. The smoothing term $\psi_{n,m}$ is based on the following consideration. Numbering the horizontal strips such that $H_i \subseteq V$ is covered halfway by $H_{i + 1} \subseteq V$, where $V$ is the set of all nodes (that is, pixels), and considering neighboring pixels $x_n$ and $x_m$ such that $x_n$ lies above or at the same horizontal line as $x_m$, three cases are possible:

$x_n \in H_i \cap H_{i + 1}$ and $x_m \in H_i \cap H_{i + 1}$,
$x_n \in H_i \cap H_{i + 1}$ and $x_m \in H_{i+1} \cap H_{i+2}$,
$x_n \in H_i \cap H_{i+1}$ and $x_m \in H_{i+1} \cap H_{i+2}$,

Including two possible labels per pixel, there are twelve cases to consider. These cases get assigned different weights $w_{n,m}$ which are computed using a Gaussian kernel and the $L_1$ color distance, see their paper. The energy is optimized using max-flow. The final superpixel segmentation can be derived from the vertical and horizontal labels.

A C++ implementation is available at Zhang's webpage. Figure 1 shows superpixel segmentations obtained using the algorithm described above.

• [1] O. Veksler, Y. Boykov, P. Mehrani. Superpixels and supervoxels in an energy optimization framework. European Conference on Computer Vision, pages 211–224, 2010.
• [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 the summarized work? Or do you know related work that is of interest? Let me know your thoughts in the comments below or get in touch with me: