# Robust Shape Regularity Criteria for Superpixel Evaluation

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis

► To cite this version:

Rémi Giraud, Vinh-Thong Ta, Nicolas Papadakis. Robust Shape Regularity Criteria for Superpixel Evaluation. IEEE International Conference on Image Processing (ICIP’17), Sep 2017, Beijing, China. pp.3455-3459. hal-01510062

HAL Id: hal-01510062

https://hal.science/hal-01510062

Submitted on 20 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
ROBUST SHAPE REGULARITY CRITERIA FOR SUPERPIXEL EVALUATION

Rémi Giraud¹,²

Vinh-Thong Ta¹,³

Nicolas Papadakis²

¹Univ. Bordeaux, LaBRI, CNRS, UMR 5800, F-33400 Talence, France.

²Univ. Bordeaux, IMB, CNRS, UMR 5251, F-33400 Talence, France.

³Bordeaux INP, LaBRI, UMR 5800, F-33405 Talence, France.

ABSTRACT

Regular decompositions are necessary for most superpixel-
based object recognition or tracking applications. So far in
the literature, the regularity or compactness of a superpixel
shape is mainly measured by its circularity. In this work, we
first demonstrate that such measure is not adapted for super-
pixel evaluation, since it does not directly express regularity
but circular appearance. Then, we propose a new metric
that considers several shape regularity aspects: convexity,
balanced repartition, and contour smoothness. Finally, we
demonstrate that our measure is robust to scale and noise and
enables to more relevantly compare superpixel methods.

***Index Terms***— Superpixels, Compactness, Quality measure

# 1. INTRODUCTION

The decomposition of an image into homogeneous areas,
called *superpixels*, has become a very popular pre-processing
step in many image processing and computer vision frame-
works. For most superpixel-based applications such as object
recognition [1, 2], labeling [3] or tracking [4, 5], the use
of regular decompositions [6, 7, 8, 9, 10, 11] where su-
perpixels roughly have the same size and regular shapes is
necessary. With such regularity, accurate superpixel features
can be computed and relevant information can be extracted
from their boundaries, while with irregular decompositions
[12, 13, 14, 15, 16], superpixels can have different sizes,
noisy boundaries and stretched shapes.

Most of recent methods allow the user to tune a compact-
ness parameter [6, 15, 7, 8, 9, 11] to produce superpixels of
variable regularity, that may affect the performances for a
given application. The search for optimal results and com-
parison between methods should thus be performed for sev-
eral regularity settings [17]. Moreover, most superpixel de-
composition methods compute a trade-off between adherence
to contours and shape compactness. The regularity is hence

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Two decompositions with square (left) and hexagonal (right) initialization using [6]. The circularity C is much higher for hexagons, and for the whole right image, despite the stretched hexagonal shapes at the borders, while the proposed SRC equally evaluates square and hexagon and provides more relevant regularity measure.</figcaption></figure>

an argument to compare decompositions with similar contour
adherence performances. Hence, clear regularity definition
and measure are necessary to evaluate superpixel methods.

In the superpixel literature, the regularity notion is usually
called *compactness*, and is mainly evaluated by the circular-
ity metric [17]. Although the circularity metric has since been
considered in many works [18, 15, 10, 11], and large bench-
marks [19, 20], the literature usually refers to the regularity as
the ability to produce convex shapes with non noisy bound-
aries. Moreover, for tracking application, the aim is to find
one-to-one superpixel associations across decompositions, so
compactness should be high for convex shapes with balanced
pixel repartition. In [7], the circularity is also discussed since
it does not consider the square as a highly regular shape. Fig-
ure 1 compares two decompositions computed with [6] using
initial square and hexagonal grids. Hexagons provide much
higher circularity, although both shapes should be considered
as regular. Since most methods start from a square grid and
iteratively refine the superpixel borders, it would make sense
to have high regularity for a square decomposition, and to
have a measure that is in line with the compactness parameter
evolution, that produces squares when set to maximum value.

**Contributions.** In this work, we first demonstrate that the circularity is not adapted to the superpixel context. We propose a new shape regularity criteria (SRC), that better expresses the regularity notion by considering the following aspects: shape convexity, balanced pixel repartition and contour smoothness. Finally, the relevance and the robustness of SRC are demonstrated with state-of-the-art superpixel methods applied to images of the Berkeley segmentation dataset [21].

<footnote>This work has been carried out with financial support of the French State,
managed by the French National Research Agency (ANR) in the frame of
the GOTMI project (ANR-16-CE33-0010-01) and the Investments for the
future Program IdEx Bordeaux (ANR-10-IDEX-03-02) with the Cluster of
excellence CPU.</footnote>
## 2. SHAPE REGULARITY CRITERIA

### 2.1. Regularity Definition

The circularity C, introduced in [17] for superpixel evaluation, expresses the compactness of a shape S as follows:

$$C(S) = 4\pi|S|/|P(S)|^2, \quad (1)$$

where P(S) is the shape perimeter and |·| denotes the cardinality. This metric considers the compactness as the resolution of the isoperimetrical problem that aims to find the largest shape for a given boundary length. As stated in the introduction, the circularity does not express the shape regularity but only favor circular shapes. We propose a new shape regularity criteria (SRC) composed of three metrics, that each evaluates an aspect of the superpixel regularity.

**Solidity.** To evaluate the global convexity of a shape, we propose to consider its *solidity* (SO), i.e., the overlap with its convex hull CH. Such convex hull, containing the whole shape S, is illustrated in Figure 2 and can be computed using Delaunay triangulation. Perfectly convex shapes such as squares or circles will get the highest *solidity*:

$$SO(S) = |S|/|CH| \le 1. \quad (2)$$

**Balanced repartition.** The overlap with the convex hull is not sufficient to express the global regularity. Convex shapes such as ellipses or lines have the highest SO, but should be considered as perfectly regular only with a balanced pixel repartition. To measure it, we define a variance term Vxy:

$$V_{xy}(S) = \sqrt{\min(\sigma_x, \sigma_y)/\max(\sigma_x, \sigma_y)} \le 1, \quad (3)$$

with σx and σy, the standard deviations of the pixel positions x and y within S. Vxy = 1 if, and only if, σx = σy. In this case, the spatial repartition of the pixels around the barycenter is considered as well balanced.

**Contour smoothness.** Finally, the regularity of the superpixel borders must be considered. The *convexity* measure (CO) compares the number of boundary pixels of the shape and the one of its convex hull. Although this measure is generally in line with SO, it is mostly dependent on the border smoothness and penalizes noisy superpixels:

$$CO(S) = |P(CH)|/|P(S)| \le 1. \quad (4)$$

The proposed shape regularity criteria (SRC) is a combination of all regularity aspects and is defined as follows:

$$SRC(S) = \sum_k \frac{|S_k|}{|I|} SO(S_k) V_{xy}(S_k) CO(S_k), \quad (5)$$

where S = {S_k}k∈{1,...,|S|} is composed of |S| superpixels S_k, whose sizes are considered to reflect the overall regularity. The combination of SO and CO is related to the ratio between the Cheeger constant of the shape S and its convex hull CH. As stated in [22], the Cheeger measure is a pertinent tool to evaluate both convexity and boundary smoothness.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Convex hull example on a synthetic shape. The overlap between the shape (a) and its convex hull (b) is shown in (c). The shape is contained into the hull and the overlap is such that SO = 78%.</figcaption></figure>

### 2.2. Circularity vs SRC

Figure 3 compares the different metrics on synthetic shapes split into three groups, and generated with smooth (top) and noisy borders (bottom). The circularity presents several drawbacks. First, it is much lower for the *Square* than for the *Circle* and *Hexagon*, and even less than for the *Ellipse*. As shown in Figure 1, this is an issue when comparing superpixel methods starting from square and hexagonal grids, such as [7]. It also drops for the *Cross* and *Bean* although they are visually regular. In the bottom part of Figure 3, the circularity appears to be very dependent on the boundary smoothness, since noisy shapes have similar circularity and cannot be differentiated. Finally, standard shapes with smooth borders can have much higher circularity than regular ones. For instance, the noisy *Square* has a lower circularity than the *Bean*.

As can be seen in Figure 3, SO, Vxy and CO independently taken are not sufficient to express the compactness of a shape. The proposed SRC combines all defined regularity properties. For instance, SO is representative for all shapes, except for the *Ellipse* and W, since they both have large overlap with their convex hull. Vxy penalizes the *Ellipse* since it does not have a balanced pixel repartition, and CO considers the large amount of contour pixels in the W shape.

The three regular shapes get the highest SRC (≈ 1), and the standard shapes have similar measures. Since our metric is less sensitive to slight contour smoothness variations, SRC also clearly separates the three shape groups in the noisy case, contrary to C. Moreover, regular but noisy shapes, have comparable SRC to smooth standard ones, whereas noisy standard shapes still have higher SRC than irregular shapes with smooth contours, which can be considered as a relevant evaluation of regularity. Figure 4 also represents the regularity measures, where SRC appears to more clearly separates the three shape groups in both smooth and noisy cases.

Finally, circularity appears to very dependent on the shape size in Figure 5. As observed in [23], due to discrete computation, it can be superior to 1 (we threshold its value in Figure 5), and it drops with larger shapes. Hence, comparisons of methods on this metric would be relevant only with decompositions having the same superpixel number, i.e., superpixels with approximately the same size. Contrary to circularity, SRC provides much more consistent measure according to the superpixel size, e.g., the *Square* always has a SRC equal to 1.
<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Comparison of regularity metrics on synthetic shapes with smooth (top) and noisy borders (bottom). The circularity C only favors circular appearance and does not enable to differentiate regular and standard noisy shapes. The SRC metric tackles these issues and more clearly separates the three shape groups in both smooth and noisy cases. See text for more details.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 4:** C and SRC on smooth (left) and noisy shapes (right). SRC more clearly separates in both cases the three shape groups (regular in red, standard in green and irregular in blue).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** Comparison of circularity (C) and proposed shape regularity criteria (SRC) on shapes of various pixel sizes *p*.</figcaption></figure>

# 3. IMPROVED EVALUATION OF SUPERPIXEL METHODS

## 3.1. Validation Framework

To compare results of state-of-the-art methods, we consider the standard Berkeley segmentation dataset (BSD) [21], containing 200 test images of 321×481 pixels. At least 5 human segmentations are provided to compute evaluation metrics of contour adherence and respect of image objects.

<table><caption>**Table 1:** Comparison of the superpixel methods regularity averaged on the BSD images for several superpixel scales *K* = [50, 1000].</caption><thead><tr><th>Method</th><th>C</th><th>SRC</th></tr></thead><tbody><tr><td>SLIC [6]</td><td>0.438 ± 0.111</td><td>0.518 ± <strong>0.072</strong></td></tr><tr><td>ERGC [15]</td><td>0.367 ± 0.040</td><td>0.456 ± <strong>0.015</strong></td></tr><tr><td>WP [7]</td><td>0.483 ± 0.076</td><td>0.559 ± <strong>0.043</strong></td></tr><tr><td>LSC [8]</td><td>0.228 ± 0.046</td><td>0.327 ± <strong>0.035</strong></td></tr><tr><td>SCALP [11]</td><td>0.515 ± 0.115</td><td>0.586 ± <strong>0.073</strong></td></tr></tbody></table>

## 3.2. Evaluation of Superpixel Methods

In this section, we consider state-of-the-art methods that enable to set a compactness parameter: SLIC [6], ERGC [15], Waterpixels (WP) [7], LSC [8] and SCALP [11]. Decomposition examples with the associated Delaunay graph are illustrated in Figure 6. In Table 1, we demonstrate that SRC provides a more robust regularity measure of superpixel methods. We compute decompositions at several scales *K* (from 50 to 1000 superpixels), with the default compactness settings, and average the results on the 200 BSD images. SRC is more robust to the superpixel scale, since it reports lower variance.

We also consider the standard undersegmentation error (UE) metric measuring the number of pixels that belong to several image objects, and the boundary recall (BR), that measures the detection of ground truth contours (defined for instance in [14]). The scale *K* is set to 300 superpixels, and the UE and BR results are averaged on the BSD images, decomposed with different compactness settings. Hence, for each method, UE and BR results are computed on several regularity levels. We consider the optimal UE and BR of each method, and the standard deviation between the corresponding C and SRC measures are respectively 0.0871 and 0.0803 for UE, and 0.0746 and 0.0694 for BR. The reduced variance demonstrates the relevance of our metric, since optimal decomposition performances of different methods, evaluated with UE and BR, are obtained for more similar SRC.
<figure><img src="image_6.png" /><figcaption>**Fig. 6:** Decomposition of a BSD image (top) and associated Delaunay graph (bottom) with methods default settings for *K*=200 superpixels.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Fig. 7:** Example of noisy superpixels computed from [6] with *K*=100 superpixels, for several compactness settings *m*.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 8:** Regularity evolution of noisy superpixels computed from [6] for several compactness settings on the BSD.</figcaption></figure>

### 3.3. Robustness to Noise

In this section, we further demonstrate the robustness of SRC to noisy boundaries. We randomly perturb the trade-off between contour adherence and compactness of SLIC [6] to generate noisy decompositions (see Figure 7). We compute decompositions for different values of compactness parameter *m*, and we report the C and SRC measures averaged on the BSD in Figure 8. The circularity appears to be impacted by the noisy borders, to such an extent that it does not express the global shape regularity that increases with *m*, since it drops from *m* = 75. Nevertheless, SRC is proportional to the evolution of the compactness parameter of [6], demonstrating that it better expresses the regularity of a decomposition, and is not mainly sensitive to contour smoothness.

### 3.4. Global Regularity Evaluation

This work and [17], that introduced circularity, focus on a local compactness definition, where each superpixel is independently evaluated. Such local evaluation seems in line with the visual regularity of the graphs (see Figure 6), but it does not

<figure><img src="image_9.png" /><figcaption>**Fig. 9:** Example of SLIC [6] and quadtree-based partitioning, with Delaunay graphs, connecting adjacent superpixel barycenters.</figcaption></figure>

consider the global size regularity within the whole decomposition. Although most methods such as [6, 7, 11] produce superpixels approximately containing the same number of pixels, other methods may produce partitions of irregular sizes [12, 14, 16]. In Figure 9, we represent an example of SLIC superpixels [6] and standard quadtree partition, which produces larger squares in areas with lower color variance. Decompositions are shown with their associated Delaunay graph, connecting barycenters of adjacent superpixels. Since it only produces square areas, the local regularity of such quadtree partition is high (SRC = 1), although the associated graph shows inconsistent distances between the barycenters of connected superpixels, contrary to the one of [6]. Numerical evaluation of graph regularity is a complex issue [24], and future works will investigate the global regularity notion and measure in the superpixel context.

## 4. CONCLUSION

In this paper, we focus on the notion of regularity, i.e., compactness in the superpixel context. We consider that a regular shape should verify these aspects: convexity, balanced reproduction and contour smoothness, and we define a new metric that better expresses the local regularity, and is robust to scale and noise. Most of decomposition methods tend to achieve a trade-off between segmentation accuracy and shape regularity. This work enables to relevantly compare superpixel algorithms and provides accurate regularity information on the decomposition inputs of superpixel-based pipelines. Nevertheless, local compactness measure does not express the global regularity notion, which will be investigated in future works.
## 5. REFERENCES

[1] J. Tighe and S. Lazebnik, "SuperParsing: Scalable non-parametric image parsing with superpixels," in *Proc. of European Conference on Computer Vision*, 2010, pp. 352-365.

[2] S. Gould, J. Zhao, X. He, and Y. Zhang, "Super-pixel graph label transfer with learned distance metric," in *Proc. of European Conference on Computer Vision*, 2014, pp. 632-647.

[3] R. Giraud, V.-T. Ta, A. Bugeau, P. Coupé, and N. Papadakis, "SuperPatchMatch: An algorithm for robust correspondences using superpixel patches," *IEEE Trans. on Image Processing*, 2017.

[4] S. Wang, H. Lu, F. Yang, and M. H. Yang, "Superpixel tracking," in *Proc. of IEEE International Conference on Computer Vision*, 2011, pp. 1323-1330.

[5] J. Chang, D. Wei, and J. W. Fisher, "A video representation using temporal superpixels," in *Proc. of IEEE Conf. on Computer Vision and Pattern Recognition*, 2013, pp. 2051-2058.

[6] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, "SLIC superpixels compared to state-of-the-art superpixel methods," *IEEE Trans. on Pattern Analysis and Machine Intelligence*, vol. 34, no. 11, pp. 2274-2282, 2012.

[7] V. Machairas, M. Faessel, D. Cárdenas-Peña, T. Chabardes, T. Walter, and E. Decencière, "Waterpixels," *IEEE Trans. on Image Processing*, vol. 24, no. 11, pp. 3707-3716, 2015.

[8] Z. Li and J. Chen, "Superpixel segmentation using linear spectral clustering," in *Proc. of IEEE Conf. on Computer Vision and Pattern Recognition*, 2015, pp. 1356-1363.

[9] J. Yao, M. Boben, S. Fidler, and R. Urtasun, "Real-time coarse-to-fine topologically preserving segmentation," in *Proc. of IEEE Conf. on Computer Vision and Pattern Recognition*, 2015, pp. 2947-2955.

[10] Y. Zhang, X. Li, X. Gao, and C. Zhang, "A simple algorithm of superpixel segmentation with boundary constraint," *IEEE Trans. on Circuits and Systems for Video Technology*, 2016.

[11] R. Giraud, V.-T. Ta, and N. Papadakis, "SCALP: Superpixels with contour adherence using linear path," in *International Conference on Pattern Recognition*, 2016.

[12] P. F. Felzenszwalb and D. P. Huttenlocher, "Efficient graph-based image segmentation," *International Journal of Computer Vision*, vol. 59, no. 2, pp. 167-181, 2004.

[13] M. Y. Liu, O. Tuzel, S. Ramalingam, and R. Chellappa, "Entropy rate superpixel segmentation," in *Proc. of IEEE Conf. on Computer Vision and Pattern Recognition*, 2011, pp. 2097-2104.

[14] M. Van den Bergh, X. Boix, G. Roig, B. de Capitani, and L. Van Gool, "SEEDS: Superpixels extracted via energy-driven sampling," in *Proc. of European Conference on Computer Vision*, 2012, pp. 13-26.

[15] P. Buyssens, M. Toutain, A. Elmoataz, and O. Lézoray, "Eikonal-based vertices growing and iterative seeding for efficient graph-based segmentation," in *Proc. of IEEE International Conference on Image Processing*, 2014, pp. 4368-4372.

[16] A. Rubio, L. Yu, E. Simo-Serra, and F. Moreno-Noguer, "BASS: Boundary-aware superpixel segmentation," in *International Conference on Pattern Recognition*, 2016.

[17] A. Schick, M. Fischer, and R. Stiefelhagen, "Measuring and evaluating the compactness of superpixels," in *International Conference on Pattern Recognition*, 2012, pp. 930-934.

[18] M. Reso, J. Jachalsky, B. Rosenhahn, and J. Ostermann, "Temporally consistent superpixels," in *Proc. of IEEE International Conference on Computer Vision*, 2013, pp. 385-392.

[19] A. Schick, M. Fischer, and R. Stiefelhagen, "An evaluation of the compactness of superpixels," *Pattern Recognition Letters*, vol. 43, pp. 71-80, 2014.

[20] D. Stutz, A. Hermans, and B. Leibe, "Superpixels: An evaluation of the state-of-the-art," *arXiv preprint arXiv:1612.01601*, 2016.

[21] D. Martin, C. Fowlkes, D. Tal, and J. Malik, "A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics," in *Proc. of IEEE International Conference on Computer Vision*, 2001, vol. 2, pp. 416-423.

[22] V. Caselles, G. Facciolo, and E. Meinhardt, "Anisotropic cheeger sets and applications," *SIAM Journal on Imaging Sciences*, vol. 2, no. 4, pp. 1211-1254, 2009.

[23] T. Roussillon, I. Sivignon, and L. Tougne, "Measure of circularity for parts of digital boundaries and its fast computation," *Pattern Recognition*, vol. 43, no. 1, pp. 37-46, 2010.

[24] R. Diestel, "Graph theory," *Graduate Texts in Mathematics*, 1997.