Hu et al. propose minimum barrier superpixels (MBS) using a minimum barrier distance transform for generating superpixels. Instead of computing the distance transform explicitly, however, an iterative raster-scan approach is employed. In particular, the image is iteratively scanned in raster scan and reverse raster scan order; based on seed pixel, each pixel is assigned a label based on the minimum barrier distance defined along the path between seed pixel and current pixel. To obtain compact superpixels, the distance transform is augmented by a compactness term (i.e. considering the length of the path). The whole process is applied in a hierarchical manner; starting with a subsampled image, the image is divided into superpixels. The original seeds are then updated based on the computed superpixels and projected into the next-higher resolution. I refer to the paper for details beyond this very rough description.
In experiments, the authors compare against other superpixel algorithms. Figure 1 (see the paper for references) shows qualitative results on the BSDS500  dataset. Quantitatively, they argue that their approach performs equally well as ERS does but is significantly faster than the other approaches. The code can be found on GitHub: YinlinHu/MBS.