A comprehensive study of clustering a class of 2D shapes

Kaliszewska, Agnieszka ; Syga, Monika

International Journal of Applied Mathematics and Computer Science, Tome 32 (2022) no. 1, pp. 95-109.

Résumé

The paper is concerned with clustering with respect to the shape and size of 2D contours that are boundaries of cross-sections of 3D objects of revolution. We propose a number of similarity measures based on combined disparate Procrustes analysis (PA) and dynamic time warping (DTW) distances. A motivation and the main application for this study comes from archaeology. The computational experiments performed refer to the clustering of archaeological pottery.

Détail

Keywords: shape representation, Procrustes distance, shape similarity, dynamic time warping, DTW, morphometrics, clustering, Kendall shape theory, archaeological pottery
Mots-clés : reprezentacja kształtu, podobieństwo kształtu, DTW, ceramika archeologiczna

Bibliographie

[1] [1] Albasri, S., Popescu, M. and Keller, J.M. (2019). Surgery task classification using procrustes analysis, 48th IEEE Applied Imagery Pattern Recognition Workshop, AIPR 2019, Washington, USA, pp. 1–6.

[2] [2] Aronov, B., Har-Peled, S., Knauer, C., Wang, Y. and Wenk, C. (2006). Fréchet distance for curves, revisited, in Y. Azar and T. Erlebach (Eds), Algorithms—ESA 2006, Springer, Berlin, pp. 52–63.

[3] [3] Auder, B. and Fischer, A. (2012). Projection-based curve clustering, Journal of Statistical Computation and Simulation 82(8): 1145–1168.

[4] [4] Borsuk, K. and Dydak, J. (1980). What is the theory of shape?, Bulletin of the Australian Mathematical Society 22(2): 161–198.

[5] [5] Cao, Y. and Mumford, D. (2002). Geometric structure estimation of axially symmetric pots from small fragments, Signal Processing, Pattern Recognition, and Applications, Crete, Greece.

[6] [6] Cohen-Addad, V., Kanade, V. and Mallmann-Trenn, F. (2018). Clustering redemption—Beyond the impossibility of Kleinberg’s axioms, Proceedings of the 32nd International Conference on Neural Information Processing Systems, Montreal, Canada, pp. 8526–8535.

[7] [7] Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F. and Mathieu, C. (2017). Hierarchical clustering: Objective functions and algorithms, Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, USA, pp. 378–397.

[8] [8] Davidson, I. and Ravi, S.S. (2007). Intractability and clustering with constraints, Proceedings of the 24th International Conference on Machine Learning, Corvalis, USA, pp. 201–208.

[9] [9] Dryden, I.L. (2000). Statistical shape analysis in archaeology, Spatial Statistics in Archaeology, Chieti, Italy.

[10] [10] Efrat, A., Fan, Q. and Venkatasubramanian, S. (2007). Curve matching, time warping, and light fields: New algorithms for computing similarity between curves, Journal of Mathematical Imaging and Vision 27(3): 203–216.

[11] [11] Eguizabal, A., Schreier, P.J. and Schmidt, J. (2019). Procrustes registration of two-dimensional statistical shape models without correspondences, CoRR abs/1911.11431.

[12] [12] Farris, J. (1969). On the cophenetic correlation coefficient, Systematic Zoology 18(3): 279–285.

[13] [13] da Fontoura Costa, L. and Cesar, R.M. (2010). Shape Analysis and Classification: Theory and Practice, CRC Press, Boca Raton.

[14] [14] Gilboa, A., Karasik, A., Sharon, I. and Smilansky, U. (2004). Towards computerized typology and classification of ceramics, Journal of Archaeological Science 31(6): 681–694.

[15] [15] Goodall, C. (1991). Procrustes methods in the statistical analysis of shape, Journal of the Royal Statistical Society B: Methodological 53(2): 285–339.

[16] [16] Gower, J.C. and Dijksterhuis, G.B. (2004). Procrustes Problems, Oxford University Press, Oxford.

[17] [17] Hosni, N., Drira, H., Chaieb, F. and Amor, B.B. (2018). 3D Gait recognition based on functional PCA on Kendall’s shape space, 2018 24th International Conference on Pattern Recognition (ICPR), Beijing, China, pp. 2130–2135.

[18] [18] Hristov, V. and Agre, G. (2013). A software system for classification of archaeological artefacts represented by 2D plans, Cybernetics and Information Technologies 13(2): 82–96.

[19] [19] Jain, A.K. (2010). Data clustering: 50 Years beyond k-means, Pattern Recognition Letters 31(8): 651–666.

[20] [20] Kaliszewska, A. and Syga, M. (2018). On representative functions method for clustering of 2D contours with application to pottery fragments typology, Control and Cybernetics 47(1): 85–108.

[21] [21] Kanevski, M. and Timonin, V. (2010). Machine learning analysis and modeling of interest rate curves, ESANN 2010: European Symposium on Artificial Neural Networks—Computational Intelligence and Machine Learning, Bruges, Belgium, pp. 47–52.

[22] [22] Kendall, D.G. (1977). The diffusion of shape, Advances in Applied Probability 9(3): 428–430.

[23] [23] Kendall, D.G. (1989). A survey of the statistical theory of shape, Statistical Science 4(2): 87–99.

[24] [24] Kleinberg, J. (2002). An impossibility theorem for clustering, Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS’02, Vancouver, Canada, p. 463–470.

[25] [25] Kotan, M., Öz, C. and Kahraman, A. (2021). A linearization-based hybrid approach for 3D reconstruction of objects in a single image, International Journal of Applied Mathematics and Computer Science 31(3): 501–513, DOI: 10.34768/amcs-2021-0034.

[26] [26] Leski, J.M. and Kotas, M.P. (2018). Linguistically defined clustering of data, International Journal of Applied Mathematics and Computer Science 28(3): 545–557, DOI: 10.2478/amcs-2018-0042.

[27] [27] Maiza, C. and Gaildart, V. (2005). Automatic classification of archaeological potsherds, 8th International Conference on Computer Graphics and Artificial Intelligence, 3IA’2005, Limoges, France, pp. 11–12.

[28] [28] Müller, M. (2007). Information Retrieval for Music and Motion, Springer, Berlin/Heidelberg.

[29] [29] Mountjoy, P.A. (1999). Regional Mycenaean Decorated Pottery, Deutsches Archäologisches Institut, Berlin.

[30] [30] Mumford, D. (1991). Mathematical theories of shape: Do they model perception?, Geometric Methods in Computer Vision, San Diego, USA, pp. 2–10.

[31] [31] Palacio-Niño, J. and Berzal, F. (2019). Evaluation metrics for unsupervised learning algorithms, CoRR abs/1905.05667.

[32] [32] Piccoli, C., Aparajeya, P., Papadopoulos, G.T., Bintliff, J., Leymarie, F., Bes, P., Van der Enden, M., P.J. and Daras, P. (2015). Towards the automatic classification of pottery sherds: Two complementary approaches, in A. Traviglia (Ed.), Across Space and Time, Amsterdam University Press, Amsterdam, pp. 463–474.

[33] [33] Pizarro, D. and Bartoli, A. (2011). Global optimization for optimal generalized procrustes analysis, CVPR’11: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, USA, pp. 2409–2415.

[34] [34] Sablatnig, R., Menard, C. and Kropatsch, W. (1998). Classification of archaeological fragments using a description language, European Association for Signal Processing (EUSIPCO), Rhodes, Greece, Vol. 2, pp. 1097–1100.

[35] [35] Sangalli, L.M., Secchi, P., Vantini, S. and Vitelli, V. (2010). Classification of functional data: Unsupervised curve clustering when curves are misaligned, 2010 JSM Proceedings, Vancouver, Canada, pp. 4034–4047.

[36] [36] Sangalli, L.M., Secchi, P., Vantini, S. and Vitelli, V. (2012). Joint clustering and alignment of functional data: An application to vascular geometries, in. A. Di Ciaccio et al. (Eds.), Advanced Statistical Methods for the Analysis of Large DataSets, Springer, Berlin/Heidelberg, pp. 34–43.

[37] [37] Sharon, E. and Mumford, D. (2006). 2D-shape analysis using conformal mapping, International Journal of Computer Vision 70(1): 55–75.

[38] [38] Siminski, K. (2021). An outlier-robust neuro-fuzzy system for classification and regression, International Journal of Applied Mathematics and Computer Science 31(2): 303–319, DOI:10.34768/amcs-2021-0021.

[39] [39] Sokal, R.R. and Rohlf, J.F. (1962). The comparison of dendrograms by objective methods, Taxon 11(2): 33–40.

[40] [40] Vogogias, A., Kennedy, J., Archambault, D., Smith, V.A. and Currant, H. (2016). MLCut: Exploring multi-level cuts in dendrograms for biological data, in C. Turkay and T.R. Wan (Eds), Computer Graphics and Visual Computing, Eurographics Association, Geneve.

[41] [41] Wierzchoń, S.T. and Kłopotek, M.A. (2015). Algorithms of Cluster Analysis, Information Technologies: Research and Their Interdisciplinary Applications 3, Polish Academy of Sciences, Warsaw.

[42] [42] Wilczek, J., Monna, F., Navarro, N. and Chateau-Smith, C. (2021). A computer tool to identify best matches for pottery fragments, Journal of Archaeological Science: Reports 37: 102891.

[43] [43] Zhou, F. and De la Torre, F. (2012). Generalized time warping for multi-modal alignment of human motion, 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, USA, pp. 1282–1289.