Tang et al. propose a superpixel algorithm which generates a regular grid of superpixels, that is the superpixels can be arranged in an array where each superpixel has a consistent, ordered position. Given an edge map
defining the probability of an edge being present at pixel $x_n$, the algorithm proceeds in three steps. Firstly, a set of pixels are chosen as initial grid positions. This is done on a regular grid with horizontal step size $R_h$ and vertical step size $R_v$ given as
where $K$ is the desired number of superpixels. Let $\mu_1,\ldots,\mu_{K'}$ denote these positions (where $K'$ is the number of grid positions required to obtain $K$ superpixels). Secondly, the positions are moved towards maximum edge positions by choosing
where $N_R(\mu_i)$ defines a local search region around the position $\mu_i$. Finally, these grid positions define an undirected graph based on their relative positions. Neighboring positions are connected by the shortest path calculated on the undirected, weighted graph with weights
$w_{n,m} = \frac{1}{p(x_n) + p(x_m)}$
for neighboring pixels $x_n$ and $x_m$. The shortest path is computed using Dijkstra’s algorithm. The superpixels are then given by the enclosed regions.
An implementation is available on Fu's webpage. Figure 1 shows superpixels segmentations obtained using Topology Preserving Superpixels.
Figure 1 (click to enlarge): Superpixel segmentations obtained on images from the Berkeley Segmentation Dataset [1].
[1] 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.
Tang et al. propose a superpixel algorithm which generates a regular grid of superpixels, that is the superpixels can be arranged in an array where each superpixel has a consistent, ordered position. Given an edge map
$p: \{1,\ldots,W\} \times \{1,\ldots,H\} \rightarrow [0,1], x_n \mapsto p(x_n)$
defining the probability of an edge being present at pixel $x_n$, the algorithm proceeds in three steps. Firstly, a set of pixels are chosen as initial grid positions. This is done on a regular grid with horizontal step size $R_h$ and vertical step size $R_v$ given as
$R_v \approx \sqrt{\frac{K H}{W}}$, $R_h = \frac{K}{R_v}$
where $K$ is the desired number of superpixels. Let $\mu_1,\ldots,\mu_{K'}$ denote these positions (where $K'$ is the number of grid positions required to obtain $K$ superpixels). Secondly, the positions are moved towards maximum edge positions by choosing
$\mu_i = arg \max_{x_n \in N_R(\mu_i)}\{p(x_n) \exp(\frac{\|x_n − \mu_i\|_2}{2 \sigma})\}$
where $N_R(\mu_i)$ defines a local search region around the position $\mu_i$. Finally, these grid positions define an undirected graph based on their relative positions. Neighboring positions are connected by the shortest path calculated on the undirected, weighted graph with weights
$w_{n,m} = \frac{1}{p(x_n) + p(x_m)}$
for neighboring pixels $x_n$ and $x_m$. The shortest path is computed using Dijkstra’s algorithm. The superpixels are then given by the enclosed regions.
An implementation is available on Fu's webpage. Figure 1 shows superpixels segmentations obtained using Topology Preserving Superpixels.