Parameter-free Modelling of 2D Shapes with Ellipses

Introduction

Figure 1: Example outputs of the proposed method for two different human figures.

Our goal is to represent a given 2D shape with an automatically determined number of ellipses, so that the total area covered by the ellipses is equal to the area of the original shape without any assumption or prior knowledge about the object structure.

Different models (i.e., solutions involving different numbers of ellipses) are evaluated based on the Akaike Information Criterion (AIC). In order to minimise the AIC criterion, two variants are proposed and evaluated: (a) the augmentative method (AEFA) that gradually increases the number of considered ellipses (k) starting from a single one and, (b) the decremental method (DEFA) that decreases the number of ellipses starting from a large, automatically defined set.

The proposed methods (AEFA and DEFA) has been applied to more than 4,000 2D shapes included in standard as well as in home-build datasets. The obtained quantitative results demonstrate that the high performance of the proposed methods, that are compared with the method presented in [2] that employs the EM Algorithm [2] under random initialization of GMMs (EMAR).

Methodology

Figure 2: (a)-(e): The solutions proposed by AEFA using one to five ellipses. (f) the six circles in SCC that initialise GMM-EM for k = 6. (g) The solution of AEFA for k = 6. (h) the solution in case that circles were selected only based on their size, only. (i) the association of pixels to the final solution of AEFA for k = 6 ellipses. (i) the AIC and BIC criteria for different values of k. Captions show the estimated values of shape coverage ..

Figure 3: (a)-(f): The intermediate solutions proposed by DEFA using 11, 8, 7, 6, 5 and 4 ellipses. Captions show the estimated values of shape coverage .. (g) the skeleton of the 2D shape. (h) the association of pixels to k = 8 ellipses which is the final solution estimated by DEFA. (i) the AIC and BIC criteria for different values of k.

Experiments - Downloads

Figure 4:Representative success examples of AEFA method.

Figure 5: Representative success examples of DEFA method.

    • You can download the matlab code of AEFA , DEFA and EMAR methods proposed in [1,2].
    • You can download the 4,526 2D shapes (.rar), organized in 6 datasets that have been used in this work:
    • SISHA_SCALE dataset (544 images) [1]
    • SISHA_SHEAR dataset (544 images) [1]
    • SISHA-NOISE1 dataset (288 images) [1]
    • SISHA-NOISE2 dataset (288 images) [1]
    • LEMS dataset (1400 images) [3]
    • MPEG_7 dataset (1400 images) [4]
    • You can download the experimental results of AEFA, DEFA and EMAR on SISHA_SCALE, SISHA_SHEAR, LEMS and MPEG_7 datasets (3,950 2D shapes) (.rar).
    • You can download the experimental results of AEFA, DEFA and EMAR on SISHA-NOISE1 and SISHA-NOISE2 datasets (.rar).
    • See the corresponding readme.txt files for more details.

Related Publications

[1] C. Panagiotakis and A. Argyros, Parameter-free Modelling of 2D Shapes with Ellipses, Pattern Recognition, vol. 53, pp. 259-275, 2016. (.pdf) (sciencedirect) (AudioSlides (Elservier))

[2] R. Y. Da Xu, M. Kemp, Fitting multiple connected ellipses to an image silhouette hierarchically, IEEE Transactions on Image Processing 19 (7) (2010) 1673–1682.

[3] B. Kimia, A large binary image database, lems vision group at brown university, http://www.lems.brown.edu/~dmc/ (2002).

[4] L. J. Latecki, R. Lakamper, T. Eckhardt, Shape descriptors for non-rigid shapes with a single closed contour, in: IEEE Conference on Computer Vision and Pattern Recognition, Vol. 1, IEEE, 2000, pp. 424–429.