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:
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:
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.
Figure 1 (click to enlarge): Superpixel segmentations obtained on images from the Berkeley Segmentation Dataset [2].
[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 this article? Let me know your thoughts on Twitter @davidstutz92 or LinkedIn in/davidstutz92.
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.