Luengo et al. introduce SMURFS – superpixels from multi-scale refinement of super-regions. The main idea is to alternatingly refine a regualr grid by merging superpixels into super-superpixels and splitting these super-superpixels again. This idea is illustrated in Figure 1. In particular, the merging of superpixels follows the approach by Felzenswalb and Huttenlocher  (like FH superpixels) with an added size constraint on the superpixels. Superpixels are merged until a rough average size of the super-superpixels is obtained. Then, these super-superpixels are splitted using an MRF formulation – this can be done in parallel for each region individually. The MRF takes into account the cluster centers (which are initially chosen randomly within the super-superpixels) in the unary term and employs a simple Pott's model as pairwise term. When not optimized individually, graph cuts can be employed.
In experiments, the authors consider different versions of the proposed method. For example, in a total of 10 iterations, we can split super-superpixels always into $K = 2$ or $K = 5$ superpixels. It is also not clear how to choose the corresponding seeds; the authors use random sampling or run $k$-means to identify seeds (which seems a bit weird as $k$-means would already produce superpixels, so no need to apply their scheme). Figure 2 shows qualitative results; I won't discuss quantitative results, though.