Duan and Lafarge introduce a superpixel-like algorithm to oversegment an image into convex polygons. To the best of my knowledge, this is the first work explicitly generating convex superpixels. While Voronoi diagrams can be used as initialization for several algorithms, these are usually deformed in a non-convex way to fit boundaries. The authors, in contrast, propose a method to adjust the initial Voronoi diagram to fit detected line segments. This is achieved by first detecting lien segments, refining these line segments as illustrated in Figure 1, and then adapting the previously sampled seed points (i.e. centers of the Voronoi cells) based on the detected line segments (Figure 1). Quantitatively, other superpixel algorithms outperform the proposed algorithm with respect to boundary adherence; however, the generated superpixels a compact and exhibit low leakage (in terms of Undersegmentation Error). Qualitative results are shown in Figure 2.
Figure 1: Top: illustration of the line segment refinement; bottom: illustration of the seed (also called anchor) perturbation.