A comprehensive study of clustering a class of 2D shapes

• Autorzy: Kaliszewska Agnieszka , Syga Monika

Identyfikatory

DOI

10.34768/amcs-2022-0008

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

shape representation; Procrustes distance; shape similarity; dynamic time warping; DTW; morphometrics; Kendall shape theory; archaeological pottery

PL

reprezentacja kształtu; podobieństwo kształtu; DTW; ceramika archeologiczna; morfometria

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2022
• Tom: Vol. 32, no. 1
• Strony: 95--109
• Opis fizyczny: Bibliogr. 43 poz., rys., tab., wykr.

Twórcy

autor

Kaliszewska Agnieszka

• Systems Research Institute Polish Academy of Sciences ul. Newelska 6, 01-447 Warsaw, Poland

autor

Syga Monika

• Faculty of Mathematics and Information Science Warsaw University of Technology ul. Koszykowa 75, 00-662 Warsaw, Poland

Bibliografia

• [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] 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] Auder, B. and Fischer, A. (2012). Projection-based curve clustering, Journal of Statistical Computation and Simulation 82(8): 1145–1168.
• [4] Borsuk, K. and Dydak, J. (1980). What is the theory of shape?, Bulletin of the Australian Mathematical Society 22(2): 161–198.
• [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] 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] 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] 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] Dryden, I.L. (2000). Statistical shape analysis in archaeology, Spatial Statistics in Archaeology, Chieti, Italy.
• [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] Eguizabal, A., Schreier, P.J. and Schmidt, J. (2019). Procrustes registration of two-dimensional statistical shape models without correspondences, CoRR abs/1911.11431.
• [12] Farris, J. (1969). On the cophenetic correlation coefficient, Systematic Zoology 18(3): 279–285.
• [13] da Fontoura Costa, L. and Cesar, R.M. (2010). Shape Analysis and Classification: Theory and Practice, CRC Press, Boca Raton.
• [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] Goodall, C. (1991). Procrustes methods in the statistical analysis of shape, Journal of the Royal Statistical Society B: Methodological 53(2): 285–339.
• [16] Gower, J.C. and Dijksterhuis, G.B. (2004). Procrustes Problems, Oxford University Press, Oxford.
• [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] 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] Jain, A.K. (2010). Data clustering: 50 Years beyond k-means, Pattern Recognition Letters 31(8): 651–666.
• [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] 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] Kendall, D.G. (1977). The diffusion of shape, Advances in Applied Probability 9(3): 428–430.
• [23] Kendall, D.G. (1989). A survey of the statistical theory of shape, Statistical Science 4(2): 87–99.
• [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] 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] 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] 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] Müller, M. (2007). Information Retrieval for Music and Motion, Springer, Berlin/Heidelberg.
• [29] Mountjoy, P.A. (1999). Regional Mycenaean Decorated Pottery, Deutsches Archäologisches Institut, Berlin.
• [30] Mumford, D. (1991). Mathematical theories of shape: Do they model perception?, Geometric Methods in Computer Vision, San Diego, USA, pp. 2–10.
• [31] Palacio-Niño, J. and Berzal, F. (2019). Evaluation metrics for unsupervised learning algorithms, CoRR abs/1905.05667.
• [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] 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] 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] 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] 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] Sharon, E. and Mumford, D. (2006). 2D-shape analysis using conformal mapping, International Journal of Computer Vision 70(1): 55–75.
• [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] Sokal, R.R. and Rohlf, J.F. (1962). The comparison of dendrograms by objective methods, Taxon 11(2): 33–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] 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] 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] 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.