# DAVIDSTUTZ

JULY2015

D. Tang, H. Fu, X. Cao. Topology preserved regular superpixel International Conference on Multimedia and Expo, 2012.

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.

•  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.